Repace gb_trees/dict with ets in couch_lru

This replaces the current implementation of couch_lru with one based on
a linked list in ets. Benchmarked externally this version is roughly 50%
faster.

2 files changed, 224 insertions, 54 deletions

diff --git a/src/couch/src/couch_lru.erl b/src/couch/src/couch_lru.erl
index 6ad7c65cd..d13218ac2 100644
--- a/src/couch/src/couch_lru.erl
+++ b/src/couch/src/couch_lru.erl
@@ -11,54 +11,167 @@
 % the License.
 
 -module(couch_lru).
--export([new/0, insert/2, update/2, close/1]).
 
--include("couch_server_int.hrl").
+
+-export([
+    new/0,
+    push/2,
+    pop/1,
+    peek_newest/1,
+    update/2,
+
+    % Test functions
+    to_list/1
+]).
+
+
+-record(node, {
+    dbname,
+    prev,
+    next
+}).
+
 
 new() ->
-    {gb_trees:empty(), dict:new()}.
-
-insert(DbName, {Tree0, Dict0}) ->
-    Lru = couch_util:unique_monotonic_integer(),
-    {gb_trees:insert(Lru, DbName, Tree0), dict:store(DbName, Lru, Dict0)}.
-
-update(DbName, {Tree0, Dict0}) ->
-    case dict:find(DbName, Dict0) of
-    {ok, Old} ->
-        New = couch_util:unique_monotonic_integer(),
-        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}
+    TableOpts = [protected, set, {keypos, #node.dbname}],
+    {ets:new(?MODULE, TableOpts), undefined, undefined}.
+
+
+push(DbName, T0) when is_binary(DbName) ->
+    {Table, Head, Tail} = remove(DbName, T0),
+    case {Head, Tail} of
+        {undefined, undefined} ->
+            % Empty LRU
+            ok = add_node(Table, #node{dbname = DbName}),
+            {Table, DbName, DbName};
+        {Head, Head} ->
+            % Single element LRU
+            ok = add_node(Table, #node{dbname = DbName, next = Head}),
+            ok = set_prev(Table, Head, DbName),
+            {Table, DbName, Head};
+        {Head, Tail} ->
+            ok = add_node(Table, #node{dbname = DbName, next = Head}),
+            ok = set_prev(Table, Head, DbName),
+            {Table, DbName, Tail}
+    end.
+
+
+pop({_Table, undefined, undefined} = T0) ->
+    {undefined, T0};
+pop({_Table, _Head, Tail} = T0) when is_binary(Tail) ->
+    {Tail, remove(Tail, T0)}.
+
+
+peek_newest({_Table, Head, _Tail}) ->
+    Head.
+
+
+update(DbName, {Table, _, _} = T0) when is_binary(DbName) ->
+    case get_node(Table, DbName) of
+        undefined ->
+            % We closed this database beore processing the update. Ignore
+            T0;
+        _ ->
+            push(DbName, T0)
+    end.
+
+
+to_list({_, undefined, undefined}) ->
+    [];
+to_list({_Table, Head, Head}) when is_binary(Head) ->
+    [Head];
+to_list({Table, Head, Tail}) when is_binary(Head), is_binary(Tail) ->
+    to_list(Table, Head, []).
+
+
+to_list(Table, undefined, Nodes) ->
+    true = length(Nodes) == ets:info(Table, size),
+    lists:reverse(Nodes);
+to_list(Table, Curr, Nodes) when is_binary(Curr) ->
+    false = lists:member(Curr, Nodes),
+    Node = get_node(Table, Curr),
+    to_list(Table, Node#node.next, [Curr | Nodes]).
+
+
+% Internal
+
+remove(DbName, {Table, Head, Tail}) when is_binary(DbName) ->
+    case get_node(Table, DbName) of
+        undefined ->
+            {Table, Head, Tail};
+        Node ->
+            ok = set_next(Table, Node#node.prev, Node#node.next),
+            ok = set_prev(Table, Node#node.next, Node#node.prev),
+            ok = del_node(Table, Node),
+            NewHead = if DbName /= Head -> Head; true ->
+                Node#node.next
+            end,
+            NewTail = if DbName /= Tail -> Tail; true ->
+                Node#node.prev
+            end,
+            {Table, NewHead, NewTail}
     end.
 
-%% Attempt to close the oldest idle database.
-close({Tree, _} = Cache) ->
-    close_int(gb_trees:next(gb_trees:iterator(Tree)), Cache).
-
-%% internals
-
-close_int(none, _) ->
-    false;
-close_int({Lru, DbName, Iter}, {Tree, Dict} = Cache) ->
-    case ets:update_element(couch_dbs, DbName, {#entry.lock, locked}) of
-    true ->
-        [#entry{db = Db, pid = Pid}] = 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),
-            {true, {gb_trees:delete(Lru, Tree), dict:erase(DbName, Dict)}};
-        false ->
-            ElemSpec = {#entry.lock, unlocked},
-            true = ets:update_element(couch_dbs, DbName, ElemSpec),
-            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)})
-end.
+
+get_node(_Table, #node{} = Node) ->
+    Node;
+get_node(Table, DbName) ->
+    case ets:lookup(Table, DbName) of
+        [] ->
+            undefined;
+        [Node] ->
+            Node
+    end.
+
+
+%% get_next(Table, #node{next = undefined}) ->
+%%     undefined;
+%% get_next(Table, #node{next = DbName}) ->
+%%     [Node] = ets:lookup(Table, DbName),
+%%     Node;
+%% get_next(Table, DbName) when is_binary(DbName) ->
+%%     Node = #node{} = get_node(Table, DbName),
+%%     get_next(Table, Node).
+%%
+%%
+%% get_prev(Table, #node{prev = undefined}) ->
+%%     undefined;
+%% get_prev(Table, #node{prev = DbName}) ->
+%%     [Node] = ets:lookup(Table, DbName),
+%%     Node;
+%% get_prev(Table, DbName) when is_binary(DbName) ->
+%%     Node = #node{} = get_node(Table, DbName),
+%%     get_prev(Table, Node).
+
+
+add_node(Table, #node{} = Node) ->
+    true = ets:insert_new(Table, Node),
+    ok.
+
+
+del_node(Table, #node{} = Node) ->
+    MSpec = {Node, [], [true]},
+    1 = ets:select_delete(Table, [MSpec]),
+    ok.
+
+
+set_next(_, undefined, _) ->
+    ok;
+set_next(Table, #node{dbname = DbName}, Next) ->
+    set_next(Table, DbName, Next);
+set_next(Table, Node, #node{dbname = Next}) ->
+    set_next(Table, Node, Next);
+set_next(Table, NodeDbName, NextDbName) when is_binary(NodeDbName) ->
+    true = ets:update_element(Table, NodeDbName, {#node.next, NextDbName}),
+    ok.
+
+
+set_prev(_, undefined, _) ->
+    ok;
+set_prev(Table, #node{dbname = DbName}, Prev) when is_binary(DbName) ->
+    set_prev(Table, DbName, Prev);
+set_prev(Table, Node, #node{dbname = DbName}) ->
+    set_prev(Table, Node, DbName);
+set_prev(Table, NodeDbName, PrevDbName) when is_binary(NodeDbName) ->
+    true = ets:update_element(Table, NodeDbName, {#node.prev, PrevDbName}),
+    ok.
diff --git a/src/couch/src/couch_server.erl b/src/couch/src/couch_server.erl
index c4b7bf199..dffd15856 100644
--- a/src/couch/src/couch_server.erl
+++ b/src/couch/src/couch_server.erl
@@ -348,13 +348,70 @@ maybe_close_lru_db(#server{dbs_open=NumOpen, max_dbs_open=MaxOpen}=Server)
         when NumOpen < MaxOpen ->
     {ok, Server};
 maybe_close_lru_db(#server{lru=Lru}=Server) ->
-    case couch_lru:close(Lru) of
+    case close_lru(Lru) of
         {true, NewLru} ->
             {ok, db_closed(Server#server{lru = NewLru}, [])};
+        {false, NewLru} ->
+            {{error, all_dbs_active}, Server#server{lru = NewLru}}
+    end.
+
+
+close_lru(Lru) ->
+    NewestDbName = couch_lru:peek_newest(Lru),
+    close_lru(NewestDbName, Lru).
+
+
+close_lru(NewestDbName, Lru) ->
+    case couch_lru:pop(Lru) of
+        {undefined, NewLru} ->
+            {false, NewLru};
+        {DbName, NewLru} ->
+            case close_lru_int(DbName) of
+                true ->
+                    {true, NewLru};
+                false ->
+                    case DbName == NewestDbName of
+                        true ->
+                            {false, NewLru};
+                        false ->
+                            close_lru(NewestDbName, couch_lru:push(DbName, NewLru))
+                    end;
+                skip ->
+                    case DbName == NewestDbName of
+                        true ->
+                            {false, NewLru};
+                        false ->
+                            close_lru(NewestDbName, NewLru)
+                    end
+            end
+    end.
+
+
+close_lru_int(DbName) ->
+    case ets:update_element(couch_dbs, DbName, {#entry.lock, locked}) of
+        true ->
+            [#entry{db = Db, pid = Pid}] = 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),
+                    true;
+                false ->
+                    ElemSpec = {#entry.lock, unlocked},
+                    true = ets:update_element(couch_dbs, DbName, ElemSpec),
+                    couch_stats:increment_counter([
+                            couchdb,
+                            couch_server,
+                            lru_skip
+                        ]),
+                    false
+            end;
         false ->
-            {error, all_dbs_active}
+            skip
     end.
 
+
 open_async(Server, From, DbName, {Module, Filepath}, Options) ->
     Parent = self(),
     T0 = os:timestamp(),
@@ -385,11 +442,11 @@ open_async(Server, From, DbName, {Module, Filepath}, Options) ->
     db_opened(Server, Options).
 
 handle_call(close_lru, _From, #server{lru=Lru} = Server) ->
-    case couch_lru:close(Lru) of
+    case close_lru(Lru) of
         {true, NewLru} ->
             {reply, ok, db_closed(Server#server{lru = NewLru}, [])};
-        false ->
-            {reply, {error, all_dbs_active}, Server}
+        {false, NewLru} ->
+            {reply, {error, all_dbs_active}, Server#server{lru = NewLru}}
     end;
 handle_call(open_dbs_count, _From, Server) ->
     {reply, Server#server.dbs_open, Server};
@@ -432,7 +489,7 @@ handle_call({open_result, T0, DbName, {ok, Db}}, {Opener, _}, Server) ->
             true = ets:insert(couch_dbs_pid_to_name, {DbPid, DbName}),
             Lru = case couch_db:is_system_db(Db) of
                 false ->
-                    couch_lru:insert(DbName, Server#server.lru);
+                    couch_lru:push(DbName, Server#server.lru);
                 true ->
                     Server#server.lru
             end,
@@ -478,8 +535,8 @@ handle_call({open, DbName, Options}, From, Server) ->
             {ok, Server2} ->
                 {ok, Engine} = get_engine(Server2, DbNameList),
                 {noreply, open_async(Server2, From, DbName, Engine, Options)};
-            CloseError ->
-                {reply, CloseError, Server}
+            {CloseError, Server2} ->
+                {reply, CloseError, Server2}
             end;
         Error ->
             {reply, Error, Server}