Trie

We use Merkle-Patricia Trie to store blockchain state. Trie is persistent, which means that insertion of new node actually leads to creation of a new path to this node, and thus root of Trie after insertion will also be represented by a new object.

Here we describe its implementation details which are closely related to Runtime.

Main structures

Trie

Trie stores the state - accounts, contract codes, access keys, etc. Each state item corresponds to the unique trie key. All types of trie keys are described in the TrieKey section. You can read more about this structure on Wikipedia.

Trie is stored in the RocksDB, which is persistent across node restarts. Trie communicates with database using TrieStorage. On the database level, data is stored in key-value format in DBCol::State column. There are two kinds of records:

  • trie nodes, for the which key is constructed from shard id and RawTrieNodeWithSize hash, and value is a RawTrieNodeWithSize serialized by a custom algorithm;
  • values (encoded contract codes, postponed receipts, etc.), for which the key is constructed from shard id and the hash of value, which maps to the encoded value.

So, value can be obtained from TrieKey as follows:

  • start from the hash of RawTrieNodeWithSize corresponding to the root;
  • descend to the needed node using nibbles from TrieKey;
  • extract underlying RawTrieNode;
  • if it is a Leaf or Branch, it should contain the hash of the value;
  • get value from storage by its hash and shard id.

Note that Trie is almost never called directly from Runtime, modifications are made using TrieUpdate.

TrieUpdate

Provides a way to access storage and record changes to commit in the future. Update is prepared as follows:

  • changes are made using set and remove methods, which are added to prospective field,
  • call commit method which moves prospective changes to committed,
  • call finalize method which prepares TrieChanges and state changes based on committed field.

Note that finalize, Trie::insert and Trie::update do not update the database storage. These functions only modify trie nodes in memory. Instead, these functions prepare the TrieChanges object, and Trie is actually updated when ShardTries::apply_insertions is called, which puts new values to DBCol::State part of the key-value database.

TrieStorage

Stores all Trie nodes and allows to get serialized nodes by TrieKey hash using the retrieve_raw_bytes method.

There are two major implementations of TrieStorage:

  • TrieCachingStorage - caches all big values ever read by retrieve_raw_bytes.
  • TrieMemoryPartialStorage - used for validating recorded partial storage.

Note that these storages use database keys, which are retrieved using hashes of trie nodes using the get_key_from_shard_id_and_hash method.

ShardTries

This is the main struct that is used to access all Tries. There's usually only a single instance of this and it contains stores and caches. We use this to gain access to the Trie for a single shard by calling the get_trie_for_shard or equivalent methods.

Each shard within ShardTries has their own cache and view_cache. The cache stores the most frequently accessed nodes and is usually used during block production. The view_cache is used to serve user request to get data, which usually come in via network. It is a good idea to have an independent cache for this as we can have patterns in accessing user data independent of block production.

Primitives

TrieKey

Describes all keys which may be inserted to Trie:

  • Account
  • ContractCode
  • AccessKey
  • ReceivedData
  • PostponedReceiptId
  • PendingDataCount
  • PostponedReceipt
  • DelayedReceiptIndices
  • DelayedReceipt
  • ContractData

Each key is uniquely converted to Vec<u8>. Internally, each such vector is converted to NibbleSlice (nibble is a half of a byte), and each its item corresponds to one step down in Trie.

TrieChanges

Stores result of updating Trie.

  • old_root: root before updating Trie, i.e. inserting new nodes and deleting old ones,
  • new_root: root after updating Trie,
  • insertions, deletions: vectors of TrieRefcountChange, describing all inserted and deleted nodes.

TrieRefcountChange

Because we remove unused nodes during garbage collection, we need to track the reference count (rc) for each node. Another reason is that we can dedup values. If the same contract is deployed 1000 times, we only store one contract binary in storage and track its count.

This structure is used to update rc in the database:

  • trie_node_or_value_hash - hash of the trie node or value, used for uniting with shard id to get DB key,
  • trie_node_or_value - serialized trie node or value,
  • rc - change of reference count.

Note that for all reference-counted records, the actual value stored in DB is the concatenation of trie_node_or_value and rc. The reference count is updated using a custom merge operation merge_refcounted_records.