keys_fsm_snip.erl

%% @private                                                                                                                                                                                                                                                                   
%% @doc Find a minimal set of covering VNodes                                                                                                                                                                                                                                 
find_coverage([], _, _, _, _, Coverage) ->
    {ok, lists:sort(Coverage)};
find_coverage(KeySpace, [], _, _, _, Coverage) ->
    {insufficient_vnodes_available, KeySpace, lists:sort(Coverage)};
find_coverage(KeySpace, Available, NVal, PartitionCount, Offset, Coverage) ->
    Res = next_vnode(KeySpace, NVal, PartitionCount, Offset, Available),
        case Res of
        {0, _, _} -> % out of vnodes                                                                                                                                                                                                                                          
            find_coverage(KeySpace, [], NVal, PartitionCount, Offset, Coverage);
        {_NumCovered, Vnode, _} ->
            {value, {Vnode, Covers}, UpdAvailable} = lists:keytake(Vnode, 1, Available),
            UpdCoverage = [{Vnode, ordsets:intersection(KeySpace, Covers)} | Coverage],
            UpdKeySpace = ordsets:subtract(KeySpace, Covers),
            find_coverage(UpdKeySpace, UpdAvailable, NVal, PartitionCount, Offset, UpdCoverage)
    end.

%% @private                                                                                                                                                                                                                                                                   
%% @doc Find the next vnode that covers the most of the                                                                                                                                                                                                                       
%% remaining keyspace. Use VNode id as tie breaker.                                                                                                                                                                                                                           
next_vnode(KeySpace, NVal, PartitionCount, Offset, Available) ->
    %% Create a tuple of data used by compare_next_vnode                                                                                                                                                                                                                      
    %% to choose a node in the case that the coverage counts                                                                                                                                                                                                                  
    %% are equal.                                                                                                                                                                                                                                                             
    TieBreakerData = {(length(KeySpace) >= NVal), PartitionCount, Offset},
    CoverCount = [{covers(KeySpace, CoversKeys), VNode, TieBreakerData} || {VNode, CoversKeys} <- Available],
    hd(lists:sort(fun compare_next_vnode/2, CoverCount)).

%% @private                                                                                                                                                                                                                                                                   
compare_next_vnode({CA, VA, {FinalVNode, PartitionCount, Offset}}, {CB, VB, _}) ->
    if
        CA > CB -> %% Descending sort on coverage                                                                                                                                                                                                                             
            true;
        CA < CB ->
            false;
        true ->
            case FinalVNode of
                true ->
                    ((VA+Offset) rem PartitionCount) < ((VB+Offset) rem PartitionCount); %% If equal coverage choose the lower node.                                                                                                                                          
                false ->
                    ((VA+Offset) rem PartitionCount) > ((VB+Offset) rem PartitionCount) %% If equal coverage choose the upper node.                                                                                                                                           
            end
    end.