Modify the key format from a hash of the data to be write_version|node_path_in_tree

[cool-develope]

ref: #548

[tac0turtle]

@catShaark want to collaborate with @cool-develope on this work? I see you started the work already

[catShaark]

Yes I do

[cool-develope]

@catShaark, I couldn't follow your approach. We can get children's paths through the parent path.

// Node represents a node in a Tree.
type Node struct {
	key           []byte
	value         []byte
	hash          []byte
	version       int64
	size          int64
	path          []byte // the path of binary tree
	leftVersion   int64 // the version of left child
	rightVersion  int64 // the version of right child
	leftNode      *Node
	rightNode     *Node
	subtreeHeight int8
	persisted     bool
}

I am just preparing the initial PR, will discuss later.

[cool-develope]

If we use the node key as path_of_tree | version, we can't interact with rotate.
When balancing the tree, the tree would be restructured and we should update all restructured nodes in DB. It's too expensive.

I am suggesting the alternative way, instead of path_of_tree | version we will use updated_order_number, refer to the below diagram. I assumed LRU (least recently used) algorithm is applied here. If so, it will improve access performance.

cc @marbar3778

[catShaark]

If we use the node key as path_of_tree | version, we can't interact with rotate. When balancing the tree, the tree would be restructured and we should update all restructured nodes in DB. It's too expensive.

I don't think we need to update all the keys, we can simply add a field to store the old key and the left/right node's old key. If we use the nonce value, we will still have to add that field.

Tho I agree with you that using a nonce value instead of path_of_tree is more efficient in term of simplicity and provides us with more data locality.

[alexanderbez]

I'm not really following the proposal here, but I thought the entire point was that the keys on disk are prefixed with height/version. This makes layout on disk much more efficient.

cc @ValarDragon

[tac0turtle]

This conversation got me thinking it would be good to capture both approaches in an adr.

[catShaark]

I think the 2 approaches don't differ much, either way we need to add NodeKey, LeftChildNodeKey, RightChildNodeKey field to the Node struct and have the node saving, key/value setting logic, ... to handle/use those field

[ValarDragon]

Got an explanation from Marko (Agreed prior post doesn't explain this well. Next time please include example keys!) Also what exactly are you calling an LRU algorithm?

Doing things off of a write nonce does not make sense to me. This is bad for data locality of a key across versions?

Also I think the whole framing around pivots is pretty off, just model a pivot as a new set of writes?

[cool-develope]

I updated the diagram. Here LRU means we will re-visit the recently updated nodes probably.
I agree with @alexanderbez , Nonce almost is similar to version|height. It requires n * log(n) space but version|path require n * n space. To reduce the size of the node struct, I vote version|height structure. as @ValarDragon mentioned, we need to add leftChildVersion and rightChildVersion.

[tac0turtle]

@cool-develope your suggestion seems in line with this issue #137

[cool-develope]

@cool-develope your suggestion seems in line with this issue #137

Yeah, it's almost the same.
I realized that version|height model also doesn't work. Because when balancing the tree, we may have nodes with the same height.
The Nonce model is not about using once and throwing away. As you can see in the above diagram, it represents all nodes including orphans. Also, it doesn't destroy any data locality.