Firewood: Compaction-Less Database Optimized for Efficiently Storing Recent Merkleized Blockchain State

:warning: Firewood is beta-level software. The Firewood API may change with little to no warning.

Firewood is an embedded key-value store, optimized to store recent Merkleized blockchain state with minimal overhead. Most blockchains, including Avalanche's C-Chain and Ethereum, store their state in Merkle tries to support efficient generation and verification of state proofs. Firewood is implemented from the ground up to directly store trie nodes on-disk. Unlike most state management approaches in the field, it is not built on top of a generic KV store such as LevelDB/RocksDB. Firewood, like a B+-tree based database, directly uses the trie structure as the index on-disk. There is no additional “emulation” of the logical trie to flatten out the data structure to feed into the underlying database that is unaware of the data being stored. The convenient byproduct of this approach is that iteration is still fast (for serving state sync queries) but compaction is not required to maintain the index. Firewood was first conceived to provide a very fast storage layer for the EVM, but could be used on any blockchain that requires an authenticated state.

By default, Firewood only attempts to store recent revisions on-disk and will actively clean up unused data when revisions expire. It keeps some configurable number of previous states in memory and on disk to power state sync and APIs which may occur at a few roots behind the current state. To do this, a new root is always created for each revision that can reference either new nodes from this revision or nodes from a prior revision. When creating a revision, a list of nodes that are no longer needed are computed and saved to disk in a future-delete log (FDL) as well as kept in memory. When a revision expires, the nodes that were deleted when it was created are returned to the free space. Firewood also supports archival mode via RootStore, which retains persisted historical revisions for lookup by root hash.

Hashes are not used to determine where a node is stored on disk in the database file. Instead space for nodes may be allocated from the end of the file, or from space freed from expired revision. Free space management algorithmically resembles that of traditional heap memory management, with free lists used to track different-size spaces that can be reused. The root address of a node is simply the disk offset within the database file, and each branch node points to the disk offset of that other node.

Firewood guarantees recoverability by not referencing the new nodes in a new revision before they are flushed to disk, as well as carefully managing the free list during the creation and expiration of revisions.

Architecture Diagram

Terminology

• Commit - Makes a proposal's state the latest committed state. Success does not guarantee that the state has been persisted.
• Persist - Writes committed state to the database files.
• Maximum persistence gap - The maximum number of committed revisions that can be ahead of the last persisted revision.
• Revision - A point-in-time state/version of the trie. This represents the entire trie, including all Key/Values at that point in time, and all Nodes.
• View - A read-only interface into a Revision, Proposal, or Reconstructed state.
• Node - A node is a portion of a trie. A trie consists of nodes that are linked together. Nodes can point to other nodes and/or contain Key/Value pairs.
• Hash - In this context, this refers to the merkle hash for a specific node.
• Root Hash - The hash of the root node for a specific revision.
• Key - Represents an individual byte array used to index into a trie. A Key usually has a specific Value.
• Value - Represents a byte array for the value of a specific Key. Values can contain 0-N bytes. A zero-length Value is valid under merkledb hashing. The Ethereum hash scheme rejects it on write.
• Key Proof - A proof that a Key exists within a specific revision of a trie. This includes the hash for the node containing the Key as well as all parents.
• Range Proof - A proof that consists of two Key Proofs, one for the start of the range, and one for the end of the range, as well as a list of all Key/Value pairs in between the two. A Range Proof can be validated independently of an actual database by constructing a trie from the Key/Values provided.
• Change Proof - A proof that consists of a set of all changes between two revisions.
• Put - An operation for a Key/Value pair. A put means "create if it doesn't exist, or update it if it does. A put operation is how you add a Value for a specific Key.
• Delete - An operation indicating that a Key should be removed from the trie.

This is the beginning of the README. Read the rest at the original. Read the full README ↗