Introducing Firewood: A Next-Generation Database Built for High-Throughput Blockchains

Patrick O’Grady and Ron Kuris

Ava Labs is thrilled to announce the developer preview of Firewood, a multi-year effort to write a state-of-the-art database optimized for storing Merkleized blockchain state from scratch in Rust. As leading researchers across the blockchain space have pointed out, efficient state management is one of the primary bottlenecks to scaling blockchains to reach global scale. Firewood tackles this bottleneck by reducing the overhead of inserting, modifying, storing, and deleting Merkleized state with a purpose-built storage stack. Firewood, unlike many other databases used to manage blockchain state today, is not built on top of a generic key-value store such as LevelDB/RocksDB and instead uses the trie structure of the data as an index on-disk that never needs to be compacted. Firewood also cleans up old state in-place and never needs to be pruned.

Many projects use some form of a Tree data structure for storing blockchain state because it allows for quick post-execution result comparison (using the root of the Trie) and for verifiable data synchronization between untrusted peers (any blob of data can be quickly verified to be a subset of the Trie). This choice, however, is not without tradeoffs. There are theoretical inefficiencies of using Merkle Tries for this task, like the increasingly large number of “inner” trie nodes that must be read from disk and updated per value modification or the hash-based addressing of nodes that can result in “random” writes/reads all over disk, which puts immense strain on the databases used to persist them.

Traditionally, projects that employ Merkle Tries have relied on existing key-value embedded databases, like LevelDB or RocksDB, to efficiently manage this workload even though they are unaware and unoptimized for how the Trie-structured data is written/read during block verification/state syncing. This “misalignment” leads, in practice, to significant overhead of either disk I/O (constant compaction), size (not tracking whether state is still used), and serialization/deserialization of Trie data structures to support high-throughput blockchain workloads.

Firewood, a replacement for the LevelDB/RocksDB + Merkle Trie overlay typically used in blockchain projects, is built from the ground up for efficiently storing and reading Merkleized blockchain state under load. Efficient, in this context, means [1] only storing the active state on-disk (overwriting state that is no longer used on-the-fly), [2] using the structure of the Merkle Trie to index data on-disk directly instead of a separate LSM Tree (which avoids any compaction), and [3] location-aware storage of Trie data that is often read at the same time, and [4] fast but still crash-recoverable using a Write-Ahead-Log. To learn more about how this is achieved, take a look at ava-labs/firewood.

Over the coming months, we will release a series of reproducible benchmarks comparing the performance of Firewood to other blockchain databases, including our own MerkleDB. Firewood and MerkleDB will share a common Merkle Trie format that will allow them to be used interchangeably with a re-genesis event. The final goal of all this work is the eventual integration of Firewood into all Virtual Machines (X/P/C/HyperSDK) that Ava Labs maintains to unlock differentiated scalability across the Avalanche Network.

Firewood is well on its way to production-readiness but is still being very actively developed. There is a TON of room to contribute, especially if you are familiar with low-level disk access primitives. You can view a list of outstanding tasks here. We believe opening Firewood to the world now, although it is not yet complete, will supercharge development and innovation on what we believe will be a game-changing technology for the entire Avalanche Ecosystem.

‍

+++

About Ava Labs

Ava Labs makes it simple to deploy high-performance solutions for Web3, led by innovations on Avalanche. The company was founded by Cornell computer scientists, who partnered with Wall Street veterans and early Web3 leaders to execute a promising vision for redefining the way people build and use open, permissionless networks. Ava Labs is redefining the way people create value with Web3.

Website | Twitter | LinkedIn | Facebook

About Avalanche

Avalanche is a smart contracts platform that scales infinitely and regularly finalizes transactions in less than one second. Its novel consensus protocol, Subnet infrastructure, and HyperSDK toolkit enable Web3 developers to easily launch powerful, custom blockchain solutions. Build anything you want, any way you want, on the eco-friendly blockchain designed for Web3 devs.

‍

SHARE //