Merge pull request #26 from cloudant/more-detailed-ranges-report

Report detailed missing shard ranges

1 files changed, 118 insertions, 7 deletions

diff --git a/src/custodian/src/custodian_util.erl b/src/custodian/src/custodian_util.erl
index 6aa5f589f..6e0382c4f 100644
--- a/src/custodian/src/custodian_util.erl
+++ b/src/custodian/src/custodian_util.erl
@@ -71,19 +71,73 @@ fold_dbs(Id, Shards, State) ->
     IsSafe = fun(#shard{node = N}) -> lists:member(N, State#state.safe) end,
     IsLive = fun(#shard{node = N}) -> lists:member(N, State#state.live) end,
     TargetN = State#state.n,
-    Range = [0, ?RING_END],
+    LiveShards = lists:filter(IsLive, Shards),
+    SafeShards = lists:filter(IsSafe, Shards),
     Acc0 = State#state.acc,
-    Acc1 = case mem3_util:calculate_max_n(lists:filter(IsLive, Shards)) of
-        TargetN -> Acc0;
-        LiveN -> (State#state.callback)(Id, Range, {live, LiveN}, Acc0)
+    Acc1 = case mem3_util:calculate_max_n(LiveShards) of
+        LiveN when LiveN < TargetN ->
+            LiveRanges = get_range_counts(LiveN, LiveShards, Shards),
+            lists:foldl(fun({Range, N}, FAcc) ->
+                (State#state.callback)(Id, Range, {live, N}, FAcc)
+            end, Acc0, LiveRanges);
+        _ ->
+            Acc0
     end,
-    Acc2 = case mem3_util:calculate_max_n(lists:filter(IsSafe, Shards)) of
-        TargetN -> Acc1;
-        SafeN -> (State#state.callback)(Id, Range, {safe, SafeN}, Acc1)
+    Acc2 = case mem3_util:calculate_max_n(SafeShards) of
+        SafeN when SafeN < TargetN ->
+            SafeRanges = get_range_counts(SafeN, SafeShards, Shards),
+            lists:foldl(fun({Range, N}, FAcc) ->
+                (State#state.callback)(Id, Range, {safe, N}, FAcc)
+            end, Acc1, SafeRanges);
+        _ ->
+           Acc1
     end,
     {ok, State#state{acc = Acc2}}.
 
 
+get_range_counts(MaxN, Shards, AllShards) ->
+    Ranges = ranges(Shards),
+    AllRanges = ranges(AllShards),
+
+    % Get a list of ranges that were used to fill the MaxN rings. Also return
+    % whatever was left (not part of the rings).
+    {UnusedRanges, UsedRanges} = get_n_rings(MaxN, Ranges, []),
+
+    % All the ranges that participated in filling the N rings will get
+    % their number of copies set to MaxN.
+    UsedCounts = update_counts(UsedRanges, #{}, 1, fun(_) -> MaxN end),
+
+    % Add ranges that were present but didn't get picked in the rings
+    PresentCounts = update_counts(UnusedRanges, UsedCounts, 1, fun(N) ->
+        max(N + 1, MaxN)
+    end),
+
+    % Handle shards that are not present at all. Mark these ranges as missing.
+    Missing = [R || R <- AllRanges, not lists:member(R, Ranges)],
+    RangeCounts = update_counts(Missing, PresentCounts, 0, fun(_) -> 0 end),
+
+    % Report only shards with counts =< MaxN
+    RangeCounts1 = maps:filter(fun(_, N) -> N =< MaxN end, RangeCounts),
+    lists:sort(maps:to_list(RangeCounts1)).
+
+
+update_counts(Ranges, Acc0, Init, UpdateFun) ->
+    lists:foldl(fun({B, E}, Acc) ->
+        maps:update_with({B, E}, UpdateFun, Init, Acc)
+    end, Acc0, Ranges).
+
+
+ranges(Shards) ->
+    lists:map(fun(S) -> [B, E] = mem3:range(S), {B, E} end, Shards).
+
+
+get_n_rings(N, Ranges, Rings) when N =< 0 ->
+    {Ranges, Rings};
+get_n_rings(N, Ranges, Rings) ->
+    Ring = mem3_util:get_ring(Ranges),
+    get_n_rings(N - 1, Ranges -- Ring, Rings ++ Ring).
+
+
 cluster_n() ->
     list_to_integer(config:get("cluster", "n", "3")).
 
@@ -150,3 +204,60 @@ custodian_ddoc() ->
         {<<"validate_doc_update">>, ?CUSTODIAN_VALIDATION}
     ],
     couch_doc:from_json_obj({Props}).
+
+
+-ifdef(TEST).
+-include_lib("eunit/include/eunit.hrl").
+
+
+get_range_counts_test_() ->
+    [?_assertEqual(Res, get_range_counts(N, Shards, AllShards)) || {N, Shards,
+            AllShards, Res} <- [
+        % No shards are present. There is a full range shard that would
+        % fit. Report that range as missing.
+        {0, [], [full()], [{{0, ?RING_END}, 0}]},
+
+        % Can't complete the ring. But would complete it if had the
+        % {2, ?RING_END} interval available.
+        {0, [sh(0, 1)], [sh(0, 1), sh(2, ?RING_END)], [{{2, ?RING_END}, 0}]},
+
+        % Can complete the ring only 1 time. Report that range as the
+        % one available with a count of 1
+        {1, [full()], [full(), full()], [{{0, ?RING_END}, 1}]},
+
+        % Can complete the ring only 1 time with a full range shard, but
+        % there is also {2, ?RING_END} that would complete another the
+        % the ring as well if {0, 1} was present.
+        {1, [sh(2, ?RING_END), full()], [sh(0, 1), sh(2, ?RING_END), full()],
+            [
+                {{0, 1}, 0},
+                {{0, ?RING_END}, 1},
+                {{2, ?RING_END}, 1}
+            ]
+        },
+
+        % Can complete the ring 2 times [{0, 2},{3, ?RING_END)] and full(),
+        % and there is remnant of a 5, 9 range that would comlete the ring
+        % as well if {0, 4} and {10, ?RING_END} were present. So report
+        {2, [sh(0, 2), sh(3, ?RING_END), sh(5, 9), full()], [sh(0, 2), sh(3,
+            ?RING_END), full(), sh(0, 4), sh(5, 9), sh(10, ?RING_END)],
+            [
+                {{0, 2}, 1},
+                {{0, 4}, 0},
+                {{0, ?RING_END}, 1},
+                {{3, ?RING_END}, 1},
+                {{5, 9}, 1},
+                {{10, ?RING_END}, 0}
+            ]
+        }
+    ]].
+
+
+full() ->
+    #shard{range = [0, ?RING_END]}.
+
+
+sh(B, E) ->
+    #shard{range = [B, E]}.
+
+-endif.