(couchdb) branch main updated: Remove unique_integer bottleneck from couch_lru

[va...@apache.org]

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

vatamane pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/couchdb.git


The following commit(s) were added to refs/heads/main by this push:
     new 6531b8621 Remove unique_integer bottleneck from couch_lru
6531b8621 is described below

commit 6531b862185fd4c77128715c2f52dcd2e8c62360
Author: Nick Vatamaniuc <va...@gmail.com>
AuthorDate: Mon Aug 5 14:36:33 2024 -0400

    Remove unique_integer bottleneck from couch_lru
    
    Previously, couch_lru used `unique_integer([monotonic,positive])` to generate
    incrementing integer keys. That call take a global VM lock [1]:
    
    > Strictly monotonically increasing values are inherently quite expensive to
    generate and scales poorly.
    
    This is especially bad now that we have sharded couch_server instances, each
    with it's own LRU. We don't want them all to bottleneck waiting on each other
    to generate their integers.
    
    [1] https://www.erlang.org/doc/apps/erts/erlang.html#unique_integer/1
---
 src/couch/src/couch_lru.erl | 78 +++++++++++++++++++++++++++------------------
 1 file changed, 47 insertions(+), 31 deletions(-)

diff --git a/src/couch/src/couch_lru.erl b/src/couch/src/couch_lru.erl
index bf3f63a11..a062d5a3a 100644
--- a/src/couch/src/couch_lru.erl
+++ b/src/couch/src/couch_lru.erl
@@ -15,33 +15,35 @@
 
 -include("couch_server_int.hrl").
 
--type cache() :: {gb_trees:tree(), #{binary() => pos_integer()}}.
+-type cache() :: {non_neg_integer(), gb_trees:tree(), #{binary() => non_neg_integer()}}.
 
 -spec new() -> cache().
 new() ->
-    {gb_trees:empty(), #{}}.
+    {0, gb_trees:empty(), #{}}.
 
 -spec insert(binary(), cache()) -> cache().
-insert(DbName, {Tree, #{} = Map} = Cache) ->
+insert(DbName, {Counter, Tree, #{} = Map} = Cache) ->
     case Map of
         #{DbName := Old} ->
             update_int(Old, DbName, Cache);
         #{} ->
-            New = couch_util:unique_monotonic_integer(),
-            {gb_trees:insert(New, DbName, Tree), Map#{DbName => New}}
+            Counter1 = Counter + 1,
+            Tree1 = gb_trees:insert(Counter1, DbName, Tree),
+            Map1 = Map#{DbName => Counter1},
+            {Counter1, Tree1, Map1}
     end.
 
 %% Update bumps the entry but only if it already exists. If it doesn't exist,
 %% it won't be inserted.
 
 -spec update(binary(), cache()) -> cache().
-update(DbName, {Tree, #{} = Map} = Cache) ->
+update(DbName, {_Counter, _Tree, Map} = Cache) ->
     case Map of
         #{DbName := Old} ->
             update_int(Old, DbName, Cache);
         #{} ->
             % We closed this database before processing the update.  Ignore
-            {Tree, Map}
+            Cache
     end.
 
 %% Attempt to close the oldest idle database. This function also cleans deleted
@@ -50,19 +52,20 @@ update(DbName, {Tree, #{} = Map} = Cache) ->
 %% all bumped entries are lost as heap garbage.
 
 -spec close(cache()) -> {true, cache()} | false.
-close({Tree, _} = Cache) ->
+close({_Counter, Tree, #{} = _Map} = Cache) ->
     close_int(gb_trees:next(gb_trees:iterator(Tree)), Cache).
 
 %% internals
 
-update_int(Old, DbName, {Tree, #{} = Map}) ->
-    New = couch_util:unique_monotonic_integer(),
-    Tree1 = gb_trees:insert(New, DbName, gb_trees:delete(Old, Tree)),
-    {Tree1, Map#{DbName := New}}.
+update_int(Old, DbName, {Counter, Tree, #{} = Map}) ->
+    Counter1 = Counter + 1,
+    Tree1 = gb_trees:insert(Counter1, DbName, gb_trees:delete(Old, Tree)),
+    Map1 = Map#{DbName := Counter1},
+    {Counter1, Tree1, Map1}.
 
-close_int(none, {_Tree, #{}}) ->
+close_int(none, {_Counter, _Tree, #{}}) ->
     false;
-close_int({Lru, DbName, Iter}, {Tree, #{} = Map} = Cache) ->
+close_int({Lru, DbName, Iter}, {Counter, Tree, #{} = Map} = Cache) ->
     CouchDbs = couch_server:couch_dbs(DbName),
     CouchDbsPidToName = couch_server:couch_dbs_pid_to_name(DbName),
 
@@ -73,16 +76,20 @@ close_int({Lru, DbName, Iter}, {Tree, #{} = Map} = Cache) ->
                     true = ets:delete(CouchDbs, DbName),
                     true = ets:delete(CouchDbsPidToName, Pid),
                     exit(Pid, kill),
-                    {true, {gb_trees:delete(Lru, Tree), maps:remove(DbName, Map)}};
+                    Tree1 = gb_trees:delete(Lru, Tree),
+                    Map1 = maps:remove(DbName, Map),
+                    {true, {Counter, Tree1, Map1}};
                 false ->
                     true = couch_server:unlock(CouchDbs, DbName),
                     couch_stats:increment_counter([couchdb, couch_server, lru_skip]),
-                    close_int(gb_trees:next(Iter), update(DbName, Cache))
+                    Cache1 = update(DbName, Cache),
+                    close_int(gb_trees:next(Iter), Cache1)
             end;
         false ->
-            NewTree = gb_trees:delete(Lru, Tree),
-            NewIter = gb_trees:iterator(NewTree),
-            close_int(gb_trees:next(NewIter), {NewTree, maps:remove(DbName, Map)})
+            Tree1 = gb_trees:delete(Lru, Tree),
+            Iter1 = gb_trees:iterator(Tree1),
+            Map1 = maps:remove(DbName, Map),
+            close_int(gb_trees:next(Iter1), {Counter, Tree1, Map1})
     end.
 
 -ifdef(TEST).
@@ -114,15 +121,16 @@ couch_lru_test_() ->
 
 t_new(_) ->
     Cache = new(),
-    ?assertMatch({_, _}, Cache),
-    {Tree, Map} = Cache,
+    ?assertMatch({_, _, _}, Cache),
+    {0, Tree, Map} = Cache,
     ?assert(gb_trees:is_empty(Tree)),
     ?assert(is_map(Map) andalso map_size(Map) == 0).
 
 t_insert(_) ->
-    {Tree, Map} = insert(?DB1, new()),
+    {Counter, Tree, Map} = insert(?DB1, new()),
     ?assertEqual(1, gb_trees:size(Tree)),
     ?assertEqual(1, map_size(Map)),
+    ?assertEqual(1, Counter),
     ?assertMatch(#{?DB1 := _}, Map),
     #{?DB1 := Int} = Map,
     ?assert(is_integer(Int)),
@@ -133,26 +141,29 @@ t_insert_duplicate(_) ->
     % We technically allow this, but is this right? Should we always use update
     % instead which would reap the old LRU entry
     %
-    {Tree, Map} = insert(?DB1, insert(?DB1, new())),
+    {Counter, Tree, Map} = insert(?DB1, insert(?DB1, new())),
     ?assertEqual(1, gb_trees:size(Tree)),
     ?assertEqual(1, map_size(Map)),
+    ?assertEqual(2, Counter),
     ?assertMatch(#{?DB1 := _}, Map),
     ?assertMatch([{_, ?DB1}], gb_trees:to_list(Tree)).
 
 t_update(_) ->
     % Insert followed by update.
-    {Tree, Map} = update(?DB1, insert(?DB1, new())),
+    {Counter, Tree, Map} = update(?DB1, insert(?DB1, new())),
     ?assertEqual(1, gb_trees:size(Tree)),
     ?assertEqual(1, map_size(Map)),
+    ?assertEqual(2, Counter),
     ?assertMatch(#{?DB1 := _}, Map),
     #{?DB1 := Int} = Map,
     ?assertEqual([{Int, ?DB1}], gb_trees:to_list(Tree)).
 
 t_update_non_existent(_) ->
     % Updating a non-existent item is a no-op
-    {Tree, Map} = update(?DB2, insert(?DB1, new())),
+    {Counter, Tree, Map} = update(?DB2, insert(?DB1, new())),
     ?assertEqual(1, gb_trees:size(Tree)),
     ?assertEqual(1, map_size(Map)),
+    ?assertEqual(1, Counter),
     ?assertMatch(#{?DB1 := _}, Map),
     #{?DB1 := Int} = Map,
     ?assertEqual([{Int, ?DB1}], gb_trees:to_list(Tree)).
@@ -164,10 +175,11 @@ t_close_unlocked_idle({Dbs, DbsPids, [Pid1, _]}) ->
     % There is one db handle and it's idle. It should get closed.
     Cache = insert(?DB1, new()),
     Res = close(Cache),
-    ?assertMatch({true, {_, #{}}}, Res),
-    {true, {Tree, Map}} = Res,
+    ?assertMatch({true, {_, _, #{}}}, Res),
+    {true, {Counter, Tree, Map}} = Res,
     ?assert(gb_trees:is_empty(Tree)),
     ?assert(is_map(Map) andalso map_size(Map) == 0),
+    ?assertEqual(1, Counter),
     ?assertNot(is_process_alive(Pid1)),
     ?assertEqual([], ets:lookup(Dbs, ?DB1)),
     ?assertEqual([], ets:lookup(DbsPids, Pid1)).
@@ -185,17 +197,20 @@ t_close_bump_busy_all({_Dbs, _DbsPids, [Pid1, _]}) ->
 
 t_close_bump_busy_one({Dbs, DbsPids, [Pid1, Pid2]}) ->
     % One busy handle gets bumped, the idle one closed.
-    {_, Map} = Cache = insert(?DB2, insert(?DB1, new())),
+    {Counter, _, Map} = Cache = insert(?DB2, insert(?DB1, new())),
     meck:expect(couch_db, is_idle, fun
         (?DB1) -> false;
         (?DB2) -> true
     end),
     meck:reset(couch_stats),
-    {true, {Tree1, Map1}} = close(Cache),
+    {true, {Counter1, Tree1, Map1}} = close(Cache),
     ?assert(is_process_alive(Pid1)),
     ?assertNot(is_process_alive(Pid2)),
     ?assertEqual(1, ets:info(Dbs, size)),
     ?assertEqual(1, ets:info(DbsPids, size)),
+    ?assertEqual(2, Counter),
+    % Counter1 is 3 because we bumped the busy one. So 2 inserts + 1 update.
+    ?assertEqual(3, Counter1),
     ?assertEqual(1, meck:num_calls(couch_stats, increment_counter, 1)),
     ?assert(is_process_alive(Pid1)),
     ?assertEqual(1, gb_trees:size(Tree1)),
@@ -211,12 +226,13 @@ t_close_entry_one_is_missing({Dbs, _, [_Pid1, Pid2]}) ->
     % it should be auto-removed from LRU
     Cache = insert(?DB2, insert(?DB1, new())),
     ets:delete(Dbs, ?DB1),
-    {true, {Tree1, Map1}} = close(Cache),
+    {true, {Counter1, Tree1, Map1}} = close(Cache),
     % One entry was removed, one was closed. There should be
     % nothing left in the LRU.
     ?assert(gb_trees:is_empty(Tree1)),
     ?assert(is_map(Map1)),
     ?assertEqual(0, map_size(Map1)),
+    ?assertEqual(2, Counter1),
     ?assertNot(is_process_alive(Pid2)).
 
 t_multiple_inserts_and_close(_) ->
@@ -225,7 +241,7 @@ t_multiple_inserts_and_close(_) ->
     % during the close traversal, if one instances was busy and the other idle,
     % we'd crash with function clause in a function clause in gb_trees:delete/2
     % (See issue #5166 for details)
-    {_, Map} = Cache = insert(?DB1, insert(?DB1, new())),
+    {_, _, _} = Cache = insert(?DB1, insert(?DB1, new())),
     meck:expect(couch_db, is_idle, 1, meck:seq([meck:val(false), meck:val(true)])),
     ?assertEqual(false, close(Cache)).