couchdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dav...@apache.org
Subject [1/9] couch commit: updated refs/heads/HACK-benchmark-COUCHDB-3191-improve-couch-lru-performance to 4c4cebc
Date Mon, 17 Oct 2016 21:35:53 GMT
Repository: couchdb-couch
Updated Branches:
  refs/heads/HACK-benchmark-COUCHDB-3191-improve-couch-lru-performance [created] 4c4cebc00


Rewrite couch_lru

This changes couch_lru from using a gb_tree and dict to a pair of
khashes. Using these we can implement an approximation of a standard
linked list by using references as links and looking up each node in the
nodes khash.

COUCHDB-3191


Project: http://git-wip-us.apache.org/repos/asf/couchdb-couch/repo
Commit: http://git-wip-us.apache.org/repos/asf/couchdb-couch/commit/39357ed8
Tree: http://git-wip-us.apache.org/repos/asf/couchdb-couch/tree/39357ed8
Diff: http://git-wip-us.apache.org/repos/asf/couchdb-couch/diff/39357ed8

Branch: refs/heads/HACK-benchmark-COUCHDB-3191-improve-couch-lru-performance
Commit: 39357ed8102e9ea3367a012ed17c9a0940cdc38f
Parents: fb12795
Author: Paul J. Davis <paul.joseph.davis@gmail.com>
Authored: Thu Oct 13 10:13:20 2016 -0500
Committer: Paul J. Davis <paul.joseph.davis@gmail.com>
Committed: Thu Oct 13 10:36:23 2016 -0500

----------------------------------------------------------------------
 src/couch_lru.erl | 314 +++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 277 insertions(+), 37 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/couchdb-couch/blob/39357ed8/src/couch_lru.erl
----------------------------------------------------------------------
diff --git a/src/couch_lru.erl b/src/couch_lru.erl
index d58eb69..7f30513 100644
--- a/src/couch_lru.erl
+++ b/src/couch_lru.erl
@@ -11,52 +11,292 @@
 % the License.
 
 -module(couch_lru).
--export([new/0, insert/2, update/2, close/1]).
+
+
+-export([
+    new/0,
+    insert/2,
+    update/2,
+    close/1
+]).
+
+% Debugging
+-export([
+    to_list/1,
+    validate/1
+]).
 
 -include_lib("couch/include/couch_db.hrl").
 
+
+-record(lru, {
+    dbs,
+    nodes,
+    head,
+    tail
+}).
+
+
+-record(node, {
+    dbname,
+    prev,
+    next
+}).
+
+
 new() ->
-    {gb_trees:empty(), dict:new()}.
-
-insert(DbName, {Tree0, Dict0}) ->
-    Lru = erlang:now(),
-    {gb_trees:insert(Lru, DbName, Tree0), dict:store(DbName, Lru, Dict0)}.
-
-update(DbName, {Tree0, Dict0}) ->
-    case dict:find(DbName, Dict0) of
-    {ok, Old} ->
-        New = erlang:now(),
-        Tree = gb_trees:insert(New, DbName, gb_trees:delete(Old, Tree0)),
-        Dict = dict:store(DbName, New, Dict0),
-        {Tree, Dict};
-    error ->
-        % We closed this database before processing the update.  Ignore
-        {Tree0, Dict0}
+    {ok, Dbs} = khash:new(),
+    {ok, Nodes} = khash:new(),
+    #lru{
+        dbs = Dbs,
+        nodes = Nodes
+    }.
+
+
+insert(DbName, Lru) ->
+    #lru{
+        dbs = Dbs,
+        nodes = Nodes,
+        head = Head,
+        tail = Tail
+    } = Lru,
+    Node = #node{
+        dbname = DbName
+    },
+    Ref = erlang:make_ref(),
+    not_found = khash:lookup(Dbs, DbName),
+    ok = khash:put(Dbs, DbName, Ref),
+    ok = khash:put(Nodes, Ref, Node),
+    {NewHead, NewTail} = case {Head, Tail} of
+        {undefined, undefined} ->
+            {Ref, Ref};
+        {_, _} when is_reference(Head), is_reference(Tail) ->
+            set_next(Lru, Tail, Node),
+            set_prev(Lru, Node, Tail),
+            {Head, Node}
+    end,
+    Lru#lru{
+        head = NewHead,
+        tail = NewTail
+    }.
+
+
+update(DbName, Lru) ->
+    #lru{
+        dbs = Dbs,
+        head = Head,
+        tail = Tail
+    } = Lru,
+    case khash:get(Dbs, DbName) of
+        Tail ->
+            % This was already the LRU entry, ignore
+            Lru;
+        Ref when is_reference(Ref) ->
+            % Get neighbors of EntryPid
+            {Prev, Next} = get_links(Lru, Ref),
+
+            % Remove Ref from link order
+            set_next(Lru, Prev, Next),
+            set_prev(Lru, Next, Prev),
+
+            % Adjust Head if necessary
+            NewHead = if
+                Ref == Head -> Next;
+                true -> Head
+            end,
+
+            % Move Ref to end of link order
+            set_next(Lru, Tail, Ref),
+            set_links(Lru, Ref, Tail, undefined),
+
+            Lru#lru{
+                head = NewHead,
+                tail = Ref
+            };
+        undefined ->
+            % We closed this database before processing the update.  Ignore
+            Lru
+    end.
+
+
+close(Lru) ->
+    #lru{
+        head = Head
+    } = Lru,
+    close(Lru, Head).
+
+
+to_list(Lru) ->
+    #lru{
+        head = Head
+    } = Lru,
+    if Head == undefined -> []; true ->
+        to_list(Lru, Head)
     end.
 
-close({Tree, _} = Cache) ->
-    close_int(gb_trees:next(gb_trees:iterator(Tree)), Cache).
 
-%% internals
+validate(Lru) ->
+    #lru{
+        dbs = Dbs,
+        nodes = Nodes,
+        head = Head,
+        tail = Tail
+    } = Lru,
+    try
+        Size = khash:size(Dbs),
+        Size = khash:size(Nodes),
+        case {Head, Tail} of
+            {undefined, undefined} ->
+                0 = khash:size(Dbs);
+            {H, T} when is_reference(H), is_reference(T) ->
+                validate(Lru, H)
+        end,
+        true
+    catch _:_ ->
+        false
+    end.
+
 
-close_int(none, _) ->
+close(_, undefined) ->
     erlang:error(all_dbs_active);
-close_int({Lru, DbName, Iter}, {Tree, Dict} = Cache) ->
+
+close(Lru, Ref) ->
+    #lru{
+        nodes = Nodes
+    } = Lru,
+    #node{
+        dbname = DbName,
+        next = Next
+    } = khash:get(Nodes, Ref),
     case ets:update_element(couch_dbs, DbName, {#db.fd_monitor, locked}) of
-    true ->
-        [#db{main_pid = Pid} = Db] = ets:lookup(couch_dbs, DbName),
-        case couch_db:is_idle(Db) of true ->
-            true = ets:delete(couch_dbs, DbName),
-            true = ets:delete(couch_dbs_pid_to_name, Pid),
-            exit(Pid, kill),
-            {gb_trees:delete(Lru, Tree), dict:erase(DbName, Dict)};
+        true ->
+            [#db{main_pid = Pid} = Db] = ets:lookup(couch_dbs, DbName),
+            case couch_db:is_idle(Db) of
+                true ->
+                    true = ets:delete(couch_dbs, DbName),
+                    true = ets:delete(couch_dbs_pid_to_name, Pid),
+                    exit(Pid, kill),
+                    remove_ref(Lru, Ref);
+                false ->
+                    Op = {#db.fd_monitor, nil},
+                    true = ets:update_element(couch_dbs, DbName, Op),
+                    couch_stats:increment_counter([
+                        couchdb,
+                        couch_server,
+                        lru_skip
+                    ]),
+                    NewLru = update(DbName, Lru),
+                    close(NewLru, Next)
+            end;
         false ->
-            true = ets:update_element(couch_dbs, DbName, {#db.fd_monitor, nil}),
-            couch_stats:increment_counter([couchdb, couch_server, lru_skip]),
-            close_int(gb_trees:next(Iter), update(DbName, Cache))
-        end;
-    false ->
-        NewTree = gb_trees:delete(Lru, Tree),
-        NewIter = gb_trees:iterator(NewTree),
-        close_int(gb_trees:next(NewIter), {NewTree, dict:erase(DbName, Dict)})
+            remove_ref(Lru, Ref),
+            close(Lru, Next)
     end.
+
+
+to_list(_Lru, undefined) ->
+    [];
+
+to_list(Lru, Ref) ->
+    #node{
+        dbname = DbName,
+        next = Next
+    } = khash:get(Lru#lru.nodes, Ref),
+    [DbName | to_list(Lru, Next)].
+
+
+validate(Lru, Ref) ->
+    #lru{
+        dbs = Dbs,
+        nodes = Nodes,
+        head = Head,
+        tail = Tail
+    } = Lru,
+    #node{
+        dbname = DbName,
+        prev = Prev,
+        next = Next
+    } = khash:get(Nodes, Ref),
+    Ref = khash:get(Dbs, DbName),
+    if
+        Prev == undefined ->
+            Ref = Head;
+        is_reference(Prev) ->
+            Ref = (khash:get(Nodes, Prev))#node.next
+    end,
+    if
+        Next == undefined ->
+            Ref = Tail;
+        is_reference(Next) ->
+            Ref = (khash:get(Nodes, Next))#node.prev
+    end,
+    validate(Lru, Next).
+
+
+remove_ref(Lru, Ref) ->
+    #lru{
+        dbs = Dbs,
+        nodes = Nodes,
+        head = Head,
+        tail = Tail
+    } = Lru,
+
+    #node{
+        dbname = DbName,
+        prev = Prev,
+        next = Next
+    } = khash:get(Nodes, Ref),
+
+    ok = khash:del(Dbs, DbName),
+    ok = khash:del(Nodes, Ref),
+
+    set_next(Lru, Prev, Next),
+    set_prev(Lru, Next, Prev),
+
+    NewHead = if
+        Ref == Head -> Next;
+        true -> Head
+    end,
+
+    NewTail = if
+        Ref == Tail -> Prev;
+        true -> Tail
+    end,
+
+    Lru#lru{
+        head = NewHead,
+        tail = NewTail
+    }.
+
+
+set_prev(_Lru, undefined, _) ->
+    ok;
+
+set_prev(Lru, Ref, Prev) ->
+    Node = khash:get(Lru#lru.nodes, Ref),
+    khash:put(Lru#lru.nodes, Ref, Node#node{
+        prev = Prev
+    }).
+
+
+set_next(_Lru, undefined, _) ->
+    ok;
+
+set_next(Lru, Ref, Next) ->
+    Node = khash:get(Lru#lru.nodes, Ref),
+    khash:put(Lru#lru.nodes, Ref, Node#node{
+        next = Next
+    }).
+
+
+set_links(Lru, Ref, Prev, Next) ->
+    Node = khash:get(Lru#lru.nodes, Ref),
+    khash:put(Lru#lru.nodes, Ref, Node#node{
+        prev = Prev,
+        next = Next
+    }).
+
+
+get_links(Lru, Ref) ->
+    Node = khash:get(Lru#lru.nodes, Ref),
+    {Node#node.prev, Node#node.next}.


Mime
View raw message