Report detailed missing shard ranges

Previously we relied on finding how many possible (max) rings could be obtained
from the whole range.

The current approach is to apply some heuristics to report details across the
individual ranges. The algorithm is roughly as follows:

 * Find out the max number of rings that can be obtained (MaxN)

 * Assign MaxN to the all those ranges ^

 * Add individual ranges for leftover shards. These are alive shards but not
   part of the MaxN rings. These might form partial rings, and, if extra shards
   would come alive gain, form full rings.

 * Report shards which are missing completely and mark those as having a count
   of 0. These are shard ranges that are in the map but there are no live
   copies encountered. If any of these were to come back alive, they might
   complete one or more of the partial rings from the previous step or form new
   rings.

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.