# Zebra

In this document we shine light on the inner working of the modified merkel-patricia tree of Zebra, by providing a detailed description of the datastructure and the behaviour when changes to the key value store are made.

## Datastructure
The tree structure and the actual storage location of the data is decoupled to provide an efficent and redundant free storage system.

The code utilizes the constant DEPTH = 8 to establish the tree's depth level before activating parallelism in the algorithm. This results in *2^8* unique threads, represented by the `DEPTH=8` constant, each paired with its own distinct hashmap for data storage. In those hashmaps we store the tree nodes and and the actual key-value pairs.

To understand better how each node and key-value pair is distributed over the hashfunction we use a simplified representation, where we set `DEPTH=1` and thus have `2^1` different threads and hashmaps.

  graph TD;
      T1-->X1((X1));
      X1-->X2((X2));
      X1-->X3((X3));
      X2-->A((A,1));
      X2-->B((B,1));
      X3-->C((C,1));
      X3-->D((D,1))

*(Here the T1 stands for table 1)*

H1: X1, X2, (A,1), (B,1)
H2: X3, (C,1), (E,1)

*(Here the H1 stands for hashmap 1)*

We can see that the nodes `X1` and `X2` are stored in the `H1` hashmap whereas `X3` is stored in `H2`. For bigger trees like `DEPTH=2` we just split the elements in four separate hashmaps.

If we have a tree that is bigger than the `DEPTH`, which is usually the case. Then the in the subtree all elements are stored in the same hashmap.

  graph TD;
      T1-->X1((X1));
      X1-->X3((X3));
    subgraph Hashmap 2
      X3-->C((C,1));
      X3-->X7((X7))
      X7-->D((D,1))
      X7-->Q((Q,1))
    end
    subgraph Hashmap 1
      X1-->X2((X2));
      X2-->A((A,1));
      X2-->B((B,1));
    end

### Multiple Tables

In Zebra it is possible to have multiple tables, each containing its own key-value pairs.

We see here two tables containing following elements

T1: (A,1), (B,1), (C,1), (D,1)
T2: (A,1), (B,1), (C,1), (E,1)

In tree form this looks like this:

<table>
<tr>
<td>

  graph TD;
      T1-->X1((X1));
      X1-->X2((X2));
      X1-->X3((X3));
      X2-->A((A,1));
      X2-->B((B,1));
      X3-->C((C,1));
      X3-->D((D,1))

</td>
<td>

  graph TD;
      T2-->X4((X4));
      X4-->X2((X2));
      X4-->X5((X5));
      X2-->A((A,1));
      X2-->B((B,1));
      X5-->C((C,1));
      X5-->E((E,1))

</td>
</tr>
</table>

As we examine the two graphs above two important points come into mind. First, they share the key-value pairs `(A,1), (B,1), (C,1)`, and second they share the node `X2`. If we now look at the distribution of the elements on the two hashmaps we can see a pattern.

H1: X1, X2, X4, (A,1), (B,1)
H2: X3, X5, (C,1), (D,1), (E,1)

The nodes and key-value pairs which are on the left on the tree are stored in `H1` and the others in `H2`. The same would apply if we would add `DEPTH=2` just by splitting up all the elements into four hashmaps instead of 2.

If two table have an overlapping structure (what is the case here), zebra optimizes the storage in such a way, that the subtree `X2` is only stored once for `T1` and `T2`.

  graph TD;
      T1-->X1((X1));
      X1-->X2((X2));
      X1-->X3((X3));
      X3-->C((C,1));
      X3-->D((D,1));
      T2-->X4((X4));
      X4-->X2((X2));
      X4-->X5((X5));
      X2-->A((A,1));
      X2-->B((B,1));
      X5-->C'((C,1));
      X5-->E((E,1))

## Insert
To understand how the algorithm works when a new key-value pair is inserted we have to look at the representation of the nodes in the tree and the entries stored in the hash tables.

struct Entry<Key: Field, Value: Field> {
    label: Label,
    node: Node<Key, Value>,
    references: References,
}

An Entry in the hashtable consists of following elements:
* **label**: Is the unique hash of the Node.
* **node** The actual node
* **references** The number of references to this node

pub(crate) enum Node<Key: Field, Value: Field> {
    Empty,
    Internal(Label, Label),
    Leaf(Wrap<Key>, Wrap<Value>),
}

The Node struct can come in following forms:
* **Empty** An empty node
* **Internal** An internal tree node, with two references to his children
* **Leaf** The node that containts a reference to the stored key-value pairs

We start with two tables with an overlapping subtree starting at **X3**. We denote `ref` as the number of reference to this node.

  graph TD;
      T1-->X1((X1, ref=1));
      T2-->X2((X2, ref=1));
      X1-->A((A,1, ref=1));
      X1-->X3((X3, ref=2));
      X3-->X5((X5, ref=1));
      X3-->B((B,1, ref=1));
      X5-->C((C,1, ref=1));
      X5-->D((D,1, ref=1));
      X2-->X3((X3, ref=2));
      X2-->E((E, 1, ref=1));

When we now insert `(D',1)` into table **T2** we get following trees.

  graph TD;
      T1-->X1((X1, ref=1));
      T2-->X2'((X2', ref=1));
      X1-->A((A,1, ref=1));
      X1-->X3((X3, ref=1));
      X3-->B((B,1, ref=1));
      X3-->X5((X5, ref=2));
      X5-->C((C,1, ref=1));
      X5-->D((D,1, ref=1));
      X2'-->X3'((X3', ref=1));
      X2'-->E((E, 1, ref=1));
      X3'-->X6((X6, ref=1));
      X3'-->B'((B,1, ref=1));
      X6-->D'((D',1, ref=1));
      X6-->X5((X5, ref=2));

Since **D'** differs from **D**, we have reduce the common subtree of T1 & T2 on **X5**.

If we would start from two identically trees and continously modifying the trees. We would push the nodes with `ref>1` further and further down. And thus eventually getting complettly disjoint trees.

### Delete

We start with the inital tree:

  graph TD;
      T1-->X1((X1, ref=1));
      T2-->X2((X2, ref=1));
      X1-->A((A,1, ref=1));
      X1-->X3((X3, ref=2));
      X3-->X5((X5, ref=1));
      X3-->B((B,1, ref=1));
      X5-->C((C,1, ref=1));
      X5-->D((D,1, ref=1));
      X2-->X3((X3, ref=2));
      X2-->E((E, 1, ref=1));

Now we like to delete the entry **D** from the table **T2**.

  graph TD;
      T1-->X1((X1, ref=1));
      T2-->X2((X2, ref=1));
      X1-->A((A,1, ref=1));
      X1-->X3((X3, ref=1));
      X3-->X5((X5, ref=1));
      X3-->B((B,1, ref=1));
      X5-->C((C,1, ref=1));
      X5-->D((D,1, ref=1));
      X2-->X3'((X3', ref=1));
      X2-->E((E, 1, ref=1));
      X3'-->C'((C,1, ref=1));
      X3'-->B'((B,1, ref=1));

Here the `ref` is used to decide whenever we can delete the **X3** subtree or if we need to create a new subtree. So for a specific node we can check whenever there exists an ancestor node with`ref > 1` . If this is the case we know that multiple tables using that node and we will not delete it.

If we would delete also **D** from **T1** then we would again end up with the shared subtree with the root **X3**. To figure out if a subtree with the root **X3** and the same structure already exists and thus check whenever we can merge it or not, we take advantage of hashes.

## Hash functions
Since we are working on the merkel-patricia tree, hash functions are a central part for various operations.

### Merkle Tree
The [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree) allows us to easily verify if two trees or subtrees are different and gives us validation that the content has not been changed. To adopt the concept in a concurrent environment we have modified some minor details.

By looking at the code we node that for each entry there exists an `Label`. This label represents the hash for either the internal node or the leaf node.

struct Entry<Key: Field, Value: Field> {
    label: Label,
    node: Node<Key, Value>,
    references: References,
}

pub(crate) enum Label {
    Internal(MapId, Bytes),
    Leaf(MapId, Bytes),
    Empty,
}

The `MapId` denotes in which hashmap the entry is saved and the `Bytes` is the hash of the element.

Each Key-value pair is stored in a Leaf node and having a leaf label. This leaf label is constructed from it's key and value: $H_{leaf} = H(H_{Key} || H_{Value})$.

On the other hand the internal nodes takes the hashes of his two child nodes and creates a new one out of it: $H_{internal} = H(H_{Left} || H_{Right})$.

For each internal node the left subtree and the right subtree can completelly independent calculated and thus executed in a parallel environment. By adding the `MapId` to the `Label` we can check if we can split the threads during the hash calcuation.

### Patricia Trie (Radix Tree)

The [patricia trie](https://en.wikipedia.org/wiki/Radix_tree) allows us to efficently find the correct location for a key-value pair in the tree. To calculate the correct path to the location the hash of the key is used $Path = H_{Key}$. Like that each bit is responsible for going left = 0 or going right = 1.

  graph TD;
      T1-->X1((X1));
      X1--0-->X2((X2));
      X1--1-->X3((X3));
      X2--0-->A((A,1));
      X2--1-->B((B,1));
      X3--0-->C((C,1));
      X3--1-->D((D,1))

In Zebra the hash is represented as the `Path` struct and is used in several usecases.

pub(crate) struct Path(Bytes);

## QA
* **What happens if we store the same Key with a different value ?**
Here we need to differentiate if multiple Is it stored under the same Path ? how is this possible?