[couchdb] branch add-stem-memory-blowup-test updated (3b05f7e -> a51ae79)

[va...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

vatamane pushed a change to branch add-stem-memory-blowup-test
in repository https://gitbox.apache.org/repos/asf/couchdb.git.


 discard 3b05f7e  Add test to ensure rev tree stemming doesn't take too much memory
     new a51ae79  Add test to ensure rev tree stemming doesn't take too much memory

This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version.  This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:

 * -- * -- B -- O -- O -- O   (3b05f7e)
            \
             N -- N -- N   refs/heads/add-stem-memory-blowup-test (a51ae79)

You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.

Any revisions marked "omit" are not gone; other references still
refer to them.  Any revisions marked "discard" are gone forever.

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.


Summary of changes:
 src/couch/test/eunit/couch_key_tree_tests.erl | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

[couchdb] 01/01: Add test to ensure rev tree stemming doesn't take too much memory

[va...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

vatamane pushed a commit to branch add-stem-memory-blowup-test
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit a51ae7997ffce2e67d3d97db443cefa23b7d56c1
Author: Nick Vatamaniuc <va...@gmail.com>
AuthorDate: Thu Mar 24 18:48:05 2022 -0400

    Add test to ensure rev tree stemming doesn't take too much memory
    
    `couch_key_tree:stem/2`, as seen in
    https://github.com/apache/couchdb/pull/3963, has a potential to consume quite a
    bit of memory. Replacing sets with maps helped in that case however, since
    stemming has a non-tail recursive section, there is a chance in future versions
    of Erlang to experience the same behavior again.
    
    As a safeguard, add a memory limit test by stemming a larger conflicted rev
    tree while limiting the maximum process heap size. For that, use the nifty
    `max_heap_size` process flag, which ensures a process is killed if it starts
    using too much memory.
    
    To reduce the flakiness, use a deterministic tree shape by using a hard-coded
    seed value and leave a decent margin of error for the memory limit.
    
    Ref: https://github.com/apache/couchdb/pull/3963
---
 src/couch/test/eunit/couch_key_tree_tests.erl | 48 ++++++++++++++++++++++++++-
 1 file changed, 47 insertions(+), 1 deletion(-)

diff --git a/src/couch/test/eunit/couch_key_tree_tests.erl b/src/couch/test/eunit/couch_key_tree_tests.erl
index f571139..d191541 100644
--- a/src/couch/test/eunit/couch_key_tree_tests.erl
+++ b/src/couch/test/eunit/couch_key_tree_tests.erl
@@ -96,7 +96,8 @@ key_tree_stemming_test_() ->
         [
             should_have_no_effect_for_stemming_more_levels_than_exists(),
             should_return_one_deepest_node(),
-            should_return_two_deepest_nodes()
+            should_return_two_deepest_nodes(),
+            should_not_use_excessive_memory_when_stemming()
         ]
     }.
 
@@ -528,3 +529,48 @@ should_return_two_deepest_nodes() ->
 merge_and_stem(RevTree, Tree) ->
     {Merged, Result} = couch_key_tree:merge(RevTree, Tree),
     {couch_key_tree:stem(Merged, ?DEPTH), Result}.
+
+should_not_use_excessive_memory_when_stemming() ->
+    ?_test(begin
+        % This is to preserve determinism
+        Seed = {1647, 841737, 351137},
+        Tree = generate_rev_tree(1000, 0.006, Seed),
+        % Without the optimization #91de482fd66f4773b3b8583039c6bcaf1c5727ec
+        % stemming would consume about 18_000_000 words. With it, it consumes
+        % 6_000_000. So, use 13_000_000 as a threshold.
+        Opts = [
+            monitor,
+            {max_heap_size, #{
+                size => 13000000,
+                error_logger => false,
+                kill => true
+            }}
+        ],
+        {_Pid, Ref} = spawn_opt(couch_key_tree, stem, [Tree, 1000], Opts),
+        % When it uses too much memory exit would be `killed`
+        Exit =
+            receive
+                {'DOWN', Ref, _, _, Res} -> Res
+            end,
+        ?assertEqual(normal, Exit)
+    end).
+
+generate_rev_tree(Depth, BranchChance, Seed) ->
+    rand:seed(exrop, Seed),
+    [{1, revnode(Depth, BranchChance)}].
+
+revnode(0, _) ->
+    {rev(), x, []};
+revnode(Depth, BranchChance) ->
+    case rand:uniform() < BranchChance of
+        true ->
+            {rev(), x, [
+                revnode(Depth - 1, BranchChance),
+                revnode(Depth - 1, BranchChance)
+            ]};
+        false ->
+            {rev(), x, [revnode(Depth - 1, BranchChance)]}
+    end.
+
+rev() ->
+    crypto:strong_rand_bytes(16).