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/23 18:22:02 UTC
[couchdb] 05/06: convert node ids to uuids
This is an automated email from the ASF dual-hosted git repository.
rnewson pushed a commit to branch prototype/fdb-layer-ebtree-immutable
in repository https://gitbox.apache.org/repos/asf/couchdb.git
commit 81e0704f4cc1e6f5a30779d8e28d74898edd28ed
Author: Robert Newson <rn...@apache.org>
AuthorDate: Thu Jul 23 19:15:33 2020 +0100
convert node ids to uuids
---
src/ebtree/src/ebtree.erl | 50 +++++++++++++++++++++++++++--------------------
1 file changed, 29 insertions(+), 21 deletions(-)
diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 08ca2bc..bbe5728 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -51,10 +51,9 @@
-define(META, 0).
-define(META_ORDER, 0).
--define(META_NEXT_ID, 1).
-define(NODE, 1).
--define(NODE_ROOT_ID, 0).
+-define(NODE_ROOT_ID, <<0>>).
-define(underflow(Tree, Node), Tree#tree.min > length(Node#node.members)).
-define(at_min(Tree, Node), Tree#tree.min == length(Node#node.members)).
@@ -98,7 +97,6 @@ open(Db, Prefix, Order, Options) when is_binary(Prefix), is_integer(Order), Orde
not_found ->
erlfdb:clear_range_startswith(Tx, Prefix),
set_meta(Tx, Tree, ?META_ORDER, Order),
- set_meta(Tx, Tree, ?META_NEXT_ID, 1),
set_node(Tx, Tree, #node{id = ?NODE_ROOT_ID}),
init_order(Tree, Order);
ActualOrder when is_integer(ActualOrder) ->
@@ -455,7 +453,7 @@ insert(Db, #tree{} = Tree, Key, Value) ->
Root0 = get_node(Tx, Tree, ?NODE_ROOT_ID),
case ?is_full(Tree, Root0) of
true ->
- OldRoot = Root0#node{id = new_node_id(Tx, Tree)},
+ OldRoot = Root0#node{id = new_node_id()},
FirstKey = first_key(OldRoot),
LastKey = last_key(OldRoot),
Root1 = #node{
@@ -474,8 +472,8 @@ insert(Db, #tree{} = Tree, Key, Value) ->
split_child(Tx, #tree{} = Tree, #node{} = Parent0, #node{} = Child) ->
{LeftMembers, RightMembers} = lists:split(Tree#tree.min, Child#node.members),
- LeftId = new_node_id(Tx, Tree),
- RightId = new_node_id(Tx, Tree),
+ LeftId = new_node_id(),
+ RightId = new_node_id(),
LeftChild = remove_pointers_if_not_leaf(#node{
id = LeftId,
@@ -610,12 +608,12 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
Sibling = get_node(Tx, Tree, SiblingId),
NewNodes = case ?at_min(Tree, Sibling) of
true ->
- Merged = merge(Tx, Tree, Child1, Sibling),
+ Merged = merge(Tree, Child1, Sibling),
update_prev_neighbour(Tx, Tree, Merged),
update_next_neighbour(Tx, Tree, Merged),
[Merged];
false ->
- {Left, Right} = rebalance(Tx, Tree, Child1, Sibling),
+ {Left, Right} = rebalance(Tree, Child1, Sibling),
update_prev_neighbour(Tx, Tree, Left),
update_next_neighbour(Tx, Tree, Right),
[Left, Right]
@@ -647,11 +645,11 @@ delete(Tx, #tree{} = Tree, #node{} = Parent0, Key) ->
end.
-merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
+merge(#tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
[Left, Right] = sort(Tree, [Node1, Node2]),
#node{
- id = new_node_id(Tx, Tree),
+ id = new_node_id(),
level = Level,
prev = Left#node.prev,
next = Right#node.next,
@@ -659,14 +657,14 @@ merge(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = N
}.
-rebalance(Tx, #tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
+rebalance(#tree{} = Tree, #node{level = Level} = Node1, #node{level = Level} = Node2) ->
[Left0, Right0] = sort(Tree, [Node1, Node2]),
Members = lists:append(Left0#node.members, Right0#node.members),
{LeftMembers, RightMembers} = lists:split(length(Members) div 2, Members),
- Left1Id = new_node_id(Tx, Tree),
- Right1Id = new_node_id(Tx, Tree),
+ Left1Id = new_node_id(),
+ Right1Id = new_node_id(),
Left1 = remove_pointers_if_not_leaf(Left0#node{
id = Left1Id,
@@ -777,7 +775,7 @@ set_node(Tx, #tree{} = Tree, #node{} = Node) ->
erlfdb:set(Tx, Key, Value).
-node_key(Prefix, Id) when is_binary(Prefix), is_integer(Id) ->
+node_key(Prefix, Id) when is_binary(Prefix), is_binary(Id) ->
erlfdb_tuple:pack({?NODE, Id}, Prefix).
@@ -1029,7 +1027,7 @@ new_node_id_if_cacheable(Tx, #tree{} = Tree, #node{} = Old, #node{} = New) ->
if
MembersChanged andalso NodeIsCacheable ->
clear_node(Tx, Tree, New),
- New#node{id = new_node_id(Tx, Tree)};
+ New#node{id = new_node_id()};
true ->
New
end.
@@ -1045,10 +1043,8 @@ node_is_cacheable(#node{}) ->
true.
-new_node_id(Tx, Tree) ->
- NextId = get_meta(Tx, Tree, ?META_NEXT_ID),
- set_meta(Tx, Tree, ?META_NEXT_ID, NextId + 1),
- NextId.
+new_node_id() ->
+ crypto:strong_rand_bytes(16).
%% remove prev/next pointers for nonleaf nodes
@@ -1059,10 +1055,22 @@ remove_pointers_if_not_leaf(#node{} = Node) ->
Node#node{prev = undefined, next = undefined}.
+print_node(#node{level = 0} = Node) ->
+ io:format("#node{id = ~s, level = ~w, prev = ~s, next = ~s, members = ~w}~n~n",
+ [b64(Node#node.id), Node#node.level, b64(Node#node.prev), b64(Node#node.next),
+ Node#node.members]);
+
print_node(#node{} = Node) ->
- io:format("#node{id = ~w, level = ~w, prev = ~w, next = ~w, members = ~w}~n~n",
- [Node#node.id, Node#node.level, Node#node.prev, Node#node.next, Node#node.members]).
+ io:format("#node{id = ~s, level = ~w, prev = ~s, next = ~s, members = ~s}~n~n",
+ [base64:encode(Node#node.id), Node#node.level, b64(Node#node.prev), b64(Node#node.next),
+ [io_lib:format("{~w, ~w, ~s, ~w}, ", [F, L, b64(P), R]) || {F, L, P, R} <- Node#node.members]]).
+
+
+b64(undefined) ->
+ undefined;
+b64(Bin) ->
+ base64:encode(Bin).
%% tests