You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by rn...@apache.org on 2020/07/27 11:06:44 UTC
[couchdb] branch prototype/fdb-layer-ebtree-sunday-musings created
(now e038f97)
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a change to branch prototype/fdb-layer-ebtree-sunday-musings
in repository https://gitbox.apache.org/repos/asf/couchdb.git.
at e038f97 include level in fdb key
This branch includes the following new commits:
new 6a83e06 Remove unnecessary collate_raw function
new e038f97 include level in fdb key
The 2 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.
[couchdb] 01/02: Remove unnecessary collate_raw function
Posted by rn...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a commit to branch prototype/fdb-layer-ebtree-sunday-musings
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit 6a83e06a60274263d8681f85fd95ccd264ac1c0c
Author: Robert Newson <rn...@apache.org>
AuthorDate: Sun Jul 26 16:56:34 2020 +0100
Remove unnecessary collate_raw function
(this was too cute not to steal from davisp)
---
src/ebtree/src/ebtree.erl | 7 ++-----
1 file changed, 2 insertions(+), 5 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index f08e1e9..74dee4b 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -80,7 +80,7 @@ open(Db, Prefix, Order) ->
-spec open(term(), binary(), pos_integer(), list()) -> #tree{}.
open(Db, Prefix, Order, Options) when is_binary(Prefix), is_integer(Order), Order > 2, Order rem 2 == 0 ->
ReduceFun = proplists:get_value(reduce_fun, Options, fun reduce_noop/2),
- CollateFun = proplists:get_value(collate_fun, Options, fun collate_raw/2),
+ CollateFun = proplists:get_value(collate_fun, Options, fun erlang:'=<'/2),
EncodeFun = proplists:get_value(encode_fun, Options, fun encode_erlang/3),
Tree = #tree{
@@ -962,9 +962,6 @@ usort_members(#tree{} = Tree, List) ->
lists:usort(CollateWrapper, List).
-collate_raw(K1, K2) ->
- K1 =< K2.
-
%% encoding function
encode_erlang(encode, _Key, Value) ->
@@ -1066,7 +1063,7 @@ reduce_stats(Rs, true) ->
collation_fun_test_() ->
- Tree = #tree{collate_fun = fun collate_raw/2},
+ Tree = #tree{collate_fun = fun erlang:'=<'/2},
[
?_test(?assert(greater_than(Tree, 4, 3))),
?_test(?assertNot(greater_than(Tree, 3, 4))),
[couchdb] 02/02: include level in fdb key
Posted by rn...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a commit to branch prototype/fdb-layer-ebtree-sunday-musings
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit e038f9755b31505117bbcf346b83f5cc795f3365
Author: Robert Newson <rn...@apache.org>
AuthorDate: Sun Jul 26 18:28:34 2020 +0100
include level in fdb key
this puts all the leafs together in part of the key space, maybe we can
read ahead.
---
src/ebtree/src/ebtree.erl | 72 ++++++++++++++++++++++++-----------------------
1 file changed, 37 insertions(+), 35 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 74dee4b..1528a1a 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -172,7 +172,7 @@ fold(Db, #tree{} = Tree, Fun, Acc) ->
Acc1 :: term().
fold(Db, #tree{} = Tree, Fun, Acc, Options) ->
{_, Reduce} = erlfdb:transactional(Db, fun(Tx) ->
- Root = get_node(Tx, Tree, ?NODE_ROOT_ID),
+ Root = get_node(Tx, Tree, ?NODE_ROOT_ID, ?NODE_ROOT_ID),
fold(Db, Tree, Root, Fun, Acc, Options)
end),
Reduce.
@@ -184,32 +184,32 @@ fold(Db, #tree{} = Tree, #node{} = Node, Fun, Acc, Options) ->
fwd -> Node#node.members;
rev -> lists:reverse(Node#node.members)
end,
- fold(Db, #tree{} = Tree, Members, Fun, Acc, Options);
+ fold(Db, #tree{} = Tree, Node#node.level, Members, Fun, Acc, Options).
-fold(_Db, #tree{} = _Tree, [], _Fun, Acc, _Options) ->
+fold(_Db, #tree{} = _Tree, _Level, [], _Fun, Acc, _Options) ->
{ok, Acc};
-fold(Db, #tree{} = Tree, [{K, V} | Rest], Fun, Acc0, Options) ->
+fold(Db, #tree{} = Tree, 0, [{K, V} | Rest], Fun, Acc0, Options) ->
case Fun({visit, K, V}, Acc0) of
{ok, Acc1} ->
- fold(Db, Tree, Rest, Fun, Acc1, Options);
+ fold(Db, Tree, 0, Rest, Fun, Acc1, Options);
{stop, Acc1} ->
{stop, Acc1}
end;
-fold(Db, #tree{} = Tree, [{F, L, P, R} | Rest], Fun, Acc0, Options) ->
+fold(Db, #tree{} = Tree, Level, [{F, L, P, R} | Rest], Fun, Acc0, Options) ->
case Fun({traverse, F, L, R}, Acc0) of
{ok, Acc1} ->
- Node = get_node(Db, Tree, P),
+ Node = get_node(Db, Tree, Level - 1, P),
case fold(Db, Tree, Node, Fun, Acc1, Options) of
{ok, Acc2} ->
- fold(Db, Tree, Rest, Fun, Acc2, Options);
+ fold(Db, Tree, Level, Rest, Fun, Acc2, Options);
{stop, Acc2} ->
{stop, Acc2}
end;
{skip, Acc1} ->
- fold(Db, Tree, Rest, Fun, Acc1, Options);
+ fold(Db, Tree, Level, Rest, Fun, Acc1, Options);
{stop, Acc1} ->
{stop, Acc1}
end.
@@ -380,7 +380,7 @@ group_reduce(Db, #tree{} = Tree, StartKey, EndKey, GroupKeyFun, UserAccFun, User
AccFun :: fun(), Acc0 :: term()) -> term().
range(Db, #tree{} = Tree, StartKey, EndKey, AccFun, Acc0) ->
erlfdb:transactional(Db, fun(Tx) ->
- range(Tx, Tree, get_node(Tx, Tree, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
+ range(Tx, Tree, get_node(Tx, Tree, ?NODE_ROOT_ID, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
end).
@@ -391,14 +391,14 @@ range(Tx, #tree{} = Tree, #node{level = 0} = Node, StartKey, EndKey, AccFun, Acc
LastKey = last_key(Node),
case Node#node.next /= undefined andalso less_than_or_equal(Tree, LastKey, EndKey) of
true ->
- range(Tx, Tree, get_node(Tx, Tree, Node#node.next), StartKey, EndKey, AccFun, Acc1);
+ range(Tx, Tree, get_node(Tx, Tree, 0, Node#node.next), StartKey, EndKey, AccFun, Acc1);
false ->
Acc1
end;
range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
ChildId = find_child_id(Tree, Node, StartKey),
- range(Tx, Tree, get_node(Tx, Tree, ChildId), StartKey, EndKey, AccFun, Acc).
+ range(Tx, Tree, get_node(Tx, Tree, Node#node.level - 1, ChildId), StartKey, EndKey, AccFun, Acc).
%% @doc Finds all key-value pairs for the specified range in reverse order.
@@ -413,7 +413,7 @@ range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
AccFun :: fun(), Acc0 :: term()) -> term().
reverse_range(Db, #tree{} = Tree, StartKey, EndKey, AccFun, Acc0) ->
erlfdb:transactional(Db, fun(Tx) ->
- reverse_range(Tx, Tree, get_node(Tx, Tree, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
+ reverse_range(Tx, Tree, get_node(Tx, Tree, ?NODE_ROOT_ID, ?NODE_ROOT_ID), StartKey, EndKey, AccFun, Acc0)
end).
@@ -424,14 +424,14 @@ reverse_range(Tx, #tree{} = Tree, #node{level = 0} = Node, StartKey, EndKey, Acc
FirstKey = first_key(Node),
case Node#node.prev /= undefined andalso less_than_or_equal(Tree, StartKey, FirstKey) of
true ->
- reverse_range(Tx, Tree, get_node(Tx, Tree, Node#node.prev), StartKey, EndKey, AccFun, Acc1);
+ reverse_range(Tx, Tree, get_node(Tx, Tree, 0, Node#node.prev), StartKey, EndKey, AccFun, Acc1);
false ->
Acc1
end;
reverse_range(Tx, #tree{} = Tree, #node{} = Node, StartKey, EndKey, AccFun, Acc) ->
ChildId = find_child_id(Tree, Node, EndKey),
- reverse_range(Tx, Tree, get_node(Tx, Tree, ChildId), StartKey, EndKey, AccFun, Acc).
+ reverse_range(Tx, Tree, get_node(Tx, Tree, Node#node.level - 1, ChildId), StartKey, EndKey, AccFun, Acc).
%% @doc Inserts or updates a value in the ebtree
@@ -449,7 +449,7 @@ insert(_Db, #tree{} = _Tree, ?MAX, _Value) ->
insert(Db, #tree{} = Tree, Key, Value) ->
erlfdb:transactional(Db, fun(Tx) ->
- Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID),
+ Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID, ?NODE_ROOT_ID),
case ?is_full(Tree, Root0) of
true ->
OldRoot = Root0#node{id = new_node_id(Tx, Tree)},
@@ -518,7 +518,7 @@ update_prev_neighbour(_Tx, #tree{} = _Tree, #node{prev = undefined} = _Node) ->
ok;
update_prev_neighbour(Tx, #tree{} = Tree, #node{} = Node) ->
- Left = get_node(Tx, Tree, Node#node.prev),
+ Left = get_node(Tx, Tree, Node#node.level, Node#node.prev),
set_node(Tx, Tree, Left#node{next = Node#node.id}).
@@ -526,7 +526,7 @@ update_next_neighbour(_Tx, #tree{} = _Tree, #node{next = undefined} = _Node) ->
ok;
update_next_neighbour(Tx, #tree{} = Tree, #node{} = Node) ->
- Left = get_node(Tx, Tree, Node#node.next),
+ Left = get_node(Tx, Tree, Node#node.level, Node#node.next),
set_node(Tx, Tree, Left#node{prev = Node#node.id}).
@@ -539,7 +539,7 @@ insert_nonfull(Tx, #tree{} = Tree, #node{level = 0} = Node0, Key, Value) ->
insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
ChildId0 = find_child_id(Tree, Node0, Key),
- Child0 = get_node(Tx, Tree, ChildId0),
+ Child0 = get_node(Tx, Tree, Node0#node.level - 1, ChildId0),
{Node1, Child1} = case ?is_full(Tree, Child0) of
true ->
{Parent, LeftChild, RightChild} = split_child(Tx, Tree, Node0, Child0),
@@ -575,12 +575,12 @@ insert_nonfull(Tx, #tree{} = Tree, #node{} = Node0, Key, Value) ->
-spec delete(Db :: term(), Tree :: #tree{}, Key :: term()) -> #tree{}.
delete(Db, #tree{} = Tree, Key) ->
erlfdb:transactional(Db, fun(Tx) ->
- Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID),
+ Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID, ?NODE_ROOT_ID),
case delete(Tx, Tree, Root0, Key) of
% if only one child, make it the new root.
#node{level = L, members = [_]} = Root1 when L > 0 ->
[{_, _, ChildId, _}] = Root1#node.members,
- Root2 = get_node(Tx, Tree, ChildId),
+ Root2 = get_node(Tx, Tree, L - 1, ChildId),
clear_node(Tx, Tree, Root2),
set_node(Tx, Tree, Root2#node{id = ?NODE_ROOT_ID});
Root1 ->
@@ -597,12 +597,12 @@ delete(_Tx, #tree{} = _Tree, #node{level = 0} = Node, Key) ->
delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
ChildId0 = find_child_id(Tree, Parent0, Key),
- Child0 = get_node(Tx, Tree, ChildId0),
+ Child0 = get_node(Tx, Tree, Parent0#node.level - 1, ChildId0),
Child1 = delete(Tx, Tree, Child0, Key),
case ?underflow(Tree, Child1) of
true ->
SiblingId = find_sibling_id(Tree, Parent0, ChildId0, Key),
- Sibling = get_node(Tx, Tree, SiblingId),
+ Sibling = get_node(Tx, Tree, Parent0#node.level - 1, SiblingId),
NewNodes = case ?at_min(Tree, Sibling) of
true ->
Merged = merge(Tx, Tree, Child1, Sibling),
@@ -732,8 +732,8 @@ meta_key(Prefix, MetaKey) when is_binary(Prefix) ->
%% node persistence functions
-get_node(Tx, #tree{} = Tree, Id) ->
- Key = node_key(Tree#tree.prefix, Id),
+get_node(Tx, #tree{} = Tree, Level, Id) ->
+ Key = node_key(Tree#tree.prefix, Level, Id),
Future = erlfdb:get(Tx, Key),
Value = erlfdb:wait(Future),
decode_node(Tree, Id, Key, Value).
@@ -746,7 +746,7 @@ clear_nodes(Tx, #tree{} = Tree, Nodes) ->
clear_node(Tx, #tree{} = Tree, #node{} = Node) ->
- Key = node_key(Tree#tree.prefix, Node#node.id),
+ Key = node_key(Tree#tree.prefix, Node#node.level, Node#node.id),
erlfdb:clear(Tx, Key).
@@ -765,20 +765,21 @@ set_node(Tx, #tree{} = Tree, #node{} = _From, #node{} = To) ->
set_node(Tx, #tree{} = Tree, #node{} = Node) ->
validate_node(Tree, Node),
- Key = node_key(Tree#tree.prefix, Node#node.id),
+ Level = if Node#node.id == ?NODE_ROOT_ID -> ?NODE_ROOT_ID; true -> Node#node.level end,
+ Key = node_key(Tree#tree.prefix, Level, Node#node.id),
Value = encode_node(Tree, Key, Node),
erlfdb:set(Tx, Key, Value).
-node_key(Prefix, Id) when is_binary(Prefix), is_integer(Id) ->
- erlfdb_tuple:pack({?NODE, Id}, Prefix).
+node_key(Prefix, Level, Id) when is_binary(Prefix), is_integer(Level), is_integer(Id) ->
+ erlfdb_tuple:pack({?NODE, Level, Id}, Prefix).
%% @doc Walks the whole tree and checks it for consistency.
%% It also prints it to screen.
validate_tree(Db, #tree{} = Tree) ->
erlfdb:transactional(Db, fun(Tx) ->
- Root = get_node(Db, Tree, ?NODE_ROOT_ID),
+ Root = get_node(Db, Tree, ?NODE_ROOT_ID, ?NODE_ROOT_ID),
validate_tree(Tx, Tree, Root)
end).
@@ -790,15 +791,16 @@ validate_tree(_Tx, #tree{} = Tree, #node{level = 0} = Node) ->
validate_tree(Tx, #tree{} = Tree, #node{} = Node) ->
print_node(Node),
validate_node(Tree, Node),
- validate_tree(Tx, Tree, Node#node.members);
+ validate_tree(Tx, Tree, Node#node.level, Node#node.members).
-validate_tree(_Tx, #tree{} = _Tree, []) ->
+
+validate_tree(_Tx, #tree{} = _Tree, _Level, []) ->
ok;
-validate_tree(Tx, #tree{} = Tree, [{_F, _L, P, _R} | Rest]) ->
- Node = get_node(Tx, Tree, P),
+validate_tree(Tx, #tree{} = Tree, Level, [{_F, _L, P, _R} | Rest]) ->
+ Node = get_node(Tx, Tree, Level - 1, P),
validate_tree(Tx, Tree, Node),
- validate_tree(Tx, Tree, Rest).
+ validate_tree(Tx, Tree, Level, Rest).
validate_node(#tree{} = Tree, #node{} = Node) ->