# Thoughts over Gossamer current Trie design

_note: I was 100% influenced by substrate/parity-trie-crate implementation and by conversations with Diego_

Given that our trie is memory inefficient, even though the prunning happens every finalization is usual that the memory consuption increases when finalization delays. The problem also appears on startup from snapshots where Gossamer loads the trie from database where every node and its value will be loaded into the memory in order to construct the trie.

Our current trie supports V0 and V1 node encoding, which means that only trie nodes created or updated by a runtime using `state_version: 1` will be tagged as V1, other trie nodes (that was previously created by a runtme using `state_version: 0`) will not be affected. This tag is important to calculate the trie root hash, where a V1 node that contains a value greater than 32 bytes only needs to provide the hash of the value instead of the value itself, while V0 nodes will provide its value no matter its size.

### Iteration one: introducing a persistence layer

Currently, as mentioned, Gossamer can holds huge amounts of bytes in a single trie due to the fact the we keep the whole trie in memory.

One first solution to starting envolving our trie to use less memory space is to hold only references to those values, instead of holding the raw values.

We can improve from a trie that uses unexpected amount of bytes like this:

To a trie that uses up to 32 bytes at maximum:


_note: is worth to mention that this should only be used for raw values greater than 32, otherwise we can keep the value inline_

This is possible to implement currently in our code base:
- The *node* struct currently has a field called `IsHashed`,
- We will need to adjust the `trie.Put`, to create the `prefixed key` for the hashed value then update the field `IsHashed` to true so will be possible to differentiate when it is a hash or a simple raw value with size less than or equal 32
- keep the correct variant for the version (if the node is **V0** use `LeafVariant` or `BranchVariant`, if the node is **V1** then use `LeafVariantWithHashedValue` or `BranchVariantWithHashedValue`), even thought storing only the hash as its value
- for deletion we should remove the node and if needed removing its value from the persistence layer.

**_prefixed key_**: _while hashing a node's raw value and storing it in the persistence layer we need to store the reference to it and this reference a concatenation of the node's key with the hash, that is needed to avoid hash colision, given the fact that sometimes the same value can exists for different keys_

In the following example, we have a trie where all its nodes were made by a runtime using `state_version: 0` which means that all nodes are in the V0, given all the previous modfication Gossamer would be capable of storing values greater than 32 in the persistence layer so when encoding the trie nodes Gossamer would know what is each node version and if the node holds or not a hashed value which makes possible to query the persistence layer to retrieve the raw value and insert in the encoding byte


While in this example we have a trie that contains 2 nodes created by a runtime that is usign `state_version: 1` and their storage value size goes beyond 32 bytes, so those 2 nodes will contains a `version` equals to **V1**, and by default our trie will store them in the persistence layer and keep only the hash value in the storage value, so when encoding the trie only those two nodes will be encoded accordingly V1 without querying the persistency layer (since the hash is already there)


This iteration also improves the `StorageState.LoadFromDB` since the amount of data to be decoded will be much less, but we can improve even more using lazy loading.

This first iteration aims to introduce the persistency layer and it should work fine with V1/V0 node encoding without much effort.

We should notice that interacting with the persistence layer is not a cheap operation so introducing a cache layer is worth to cache common used keys.

### Iteration two: soft lazy loading

The trie encoding is just the concatenation of all its nodes encoding

Currently, Gossamer encodes the trie and stores it in the database using its root hash as the key, and whenever needed that trie Gossamer retrieves the encoded bytes and decode the **whole** trie into memory again, even its child tries, as we can see in the next image.

_note: child tries are already lazy loaded, whenever the runtime needs a child trie the trie state queries the database for the child trie loading it completely to memory and then performing the operation. This can be improved by only loading the trie path needed for some operation_

And the full constructed trie is used by the runtime instance through the method `instance.SetContextStorage`, now the runtime has full access and perform operations to the trie.

The big provider for such operations is an implementation of the interface `runtime/Storage` which contains some method such as `Put`, `Get`, `NextKey`, `StartTransaction`, `CommitTransaction` ..., all the operations that the host exposes to the runtime layer. Currently the single implementation for this interface is the instance called `lib/runtime/storage/TrieState`, this object is some sort of wrapper to the trie, it implements a nested transaction layer that allows the runtime to perform operations to a snapshot trie and can commit or rollback those operations.


Given the first iteration where the persistence layer was introduced, instead of loading the raw values directly to the trie memory Gossamer will only load up to 32 bytes to the database, also removing the necessity of loading child tries to the memory (improvement that need to be done to `lib/trie/database.go` at method `loadNode()`.


### Iteration three: hard lazy loading [WIP]

This iteration aims to only loads into memory specific trie paths needed for operations also consuming the encoded bytes, left only not decoded parts.

_challenge: do we need to start from scratch?_

_challenge: does substrate have a smart way to tackle trie lazy load that requires us to rewrite/translate their implementation?_

_challenge: with this approach is decoding a branch node, since the branch node can store up to 16 children nodes (from index 0 to 15) and we need to decode a child from index N will not be trivial to skip all the encoded bytes that belongs to children from 0 to N - 1_

_challenge: resume from the left not decoded bytes whenever needed given a partial trie already loaded into memory_

_challenge: merge the in memory modified trie with the non touched decoded bytes left_