Improve fabric_util get_db timeout logicimprove-get-db-timeouts

Previously, users with low {Q, N} dbs often got the `"No DB shards could be
opened."` error when the cluster is overloaded. The hard-coded 100 msec timeout
was too low to open the few available shards and the whole request would crash
with a 500 error.

Attempt to calculate an optimal timeout value based on the number of shards and
the max fabric request timeout limit.

The sequence of doubling (by default) timeouts forms a geometric progression.
Use the well known closed form formula for the sum [0], and the maximum request
timeout, to calculate the initial timeout. The test case illustrates a few
examples with some default Q and N values.

Because we don't want the timeout value to be too low, since it takes time to
open shards, and we don't want to quickly cycle through a few initial shards
and discard the results, the minimum inital timeout is clipped to the
previously hard-coded 100 msec timeout. Unlike previously however, this minimum
value can now also be configured.

[0] https://en.wikipedia.org/wiki/Geometric_series

Fixes: https://github.com/apache/couchdb/issues/3733

2 files changed, 64 insertions, 2 deletions

diff --git a/rel/overlay/etc/default.ini b/rel/overlay/etc/default.ini
index d3710ce44..93aa1ca59 100644
--- a/rel/overlay/etc/default.ini
+++ b/rel/overlay/etc/default.ini
@@ -276,6 +276,7 @@ bind_address = 127.0.0.1
 ; all_docs_concurrency = 10
 ; changes_duration = 
 ; shard_timeout_factor = 2
+; shard_timeout_min_msec = 100
 ; uuid_prefix_len = 7
 ; request_timeout = 60000
 ; all_docs_timeout = 10000
diff --git a/src/fabric/src/fabric_util.erl b/src/fabric/src/fabric_util.erl
index 9dd8e71fa..e07ab7b55 100644
--- a/src/fabric/src/fabric_util.erl
+++ b/src/fabric/src/fabric_util.erl
@@ -107,8 +107,12 @@ get_db(DbName, Options) ->
     % suppress shards from down nodes
     Nodes = [node()|erlang:nodes()],
     Live = [S || #shard{node = N} = S <- Shards, lists:member(N, Nodes)],
-    Factor = list_to_integer(config:get("fabric", "shard_timeout_factor", "2")),
-    get_shard(Live, Options, 100, Factor).
+    % Only accept factors > 1, otherwise our math breaks further down
+    Factor = max(2, config:get_integer("fabric", "shard_timeout_factor", 2)),
+    MinTimeout = config:get_integer("fabric", "shard_timeout_min_msec", 100),
+    MaxTimeout = request_timeout(),
+    Timeout = get_db_timeout(length(Live), Factor, MinTimeout, MaxTimeout),
+    get_shard(Live, Options, Timeout, Factor).
 
 get_shard([], _Opts, _Timeout, _Factor) ->
     erlang:error({internal_server_error, "No DB shards could be opened."});
@@ -134,6 +138,25 @@ get_shard([#shard{node = Node, name = Name} | Rest], Opts, Timeout, Factor) ->
         rexi_monitor:stop(Mon)
     end.
 
+get_db_timeout(N, Factor, MinTimeout, MaxTimeout) ->
+    %
+    % The progression of timeouts forms a geometric series:
+    %
+    %     MaxTimeout = T + T*F + T*F^2 + T*F^3 ...
+    %
+    % Where T is the initial timeout and F is the factor. The formula for
+    % the sum is:
+    %
+    %     Sum[T * F^I, I <- 0..N] = T * (1 - F^(N + 1)) / (1 - F)
+    %
+    % Then, for a given sum and factor we can calculate the initial timeout T:
+    %
+    %     T = Sum / ((1 - F^(N+1)) / (1 - F))
+    %
+    Timeout = MaxTimeout / ((1 - math:pow(Factor, N + 1)) / (1 - Factor)),
+    % Apply a minimum timeout value
+    max(MinTimeout, trunc(Timeout)).
+
 error_info({{timeout, _} = Error, _Stack}) ->
     Error;
 error_info({{Error, Reason}, Stack}) ->
@@ -400,3 +423,41 @@ do_isolate(Fun) ->
 
 
 -endif.
+
+
+get_db_timeout_test() ->
+    % Q=1, N=1
+    ?assertEqual(20000, get_db_timeout(1, 2, 100, 60000)),
+
+    % Q=2, N=1
+    ?assertEqual(8571, get_db_timeout(2, 2, 100, 60000)),
+
+    % Q=2, N=3 (default)
+    ?assertEqual(472, get_db_timeout(2 * 3, 2, 100, 60000)),
+
+    % Q=3, N=3
+    ?assertEqual(100, get_db_timeout(3 * 3, 2, 100, 60000)),
+
+    % Q=4, N=1
+    ?assertEqual(1935, get_db_timeout(4, 2, 100, 60000)),
+
+    % Q=8, N=1
+    ?assertEqual(117, get_db_timeout(8, 2, 100, 60000)),
+
+    % Q=8, N=3 (default in 2.x)
+    ?assertEqual(100, get_db_timeout(8 * 3, 2, 100, 60000)),
+
+    % Q=256, N=3
+    ?assertEqual(100, get_db_timeout(256 * 3, 2, 100, 60000)),
+
+    % Large factor = 100
+    ?assertEqual(100, get_db_timeout(2 * 3, 100, 100, 60000)),
+
+    % Small total request timeout = 1 sec
+    ?assertEqual(100, get_db_timeout(2 * 3, 2, 100, 1000)),
+
+    % Large total request timeout
+    ?assertEqual(28346, get_db_timeout(2 * 3, 2, 100, 3600000)),
+
+    % No shards at all
+    ?assertEqual(60000, get_db_timeout(0, 2, 100, 60000)).