The State Trie Storage Problem — Flat DBs and Path-Based Storage TODO
Concept
Ethereum state is logically a Merkle Patricia Trie, but storing that structure directly in a key-value database means reading a single account requires several random lookups from root to leaf, and since nodes are keyed by hash there's no storage locality at all. So execution clients maintain a separate flat/snapshot layout that stores accounts and storage slots directly under flat keys, turning a read into a single lookup, while keeping the trie itself around only for computing the root and generating proofs. Trie node storage splits into hash-based schemes, which key a node by the hash of its contents, and path-based schemes, which key a node by its position in the trie; path-based storage overwrites the previous version at the same path to curb disk growth, but then needs a separate rollback journal to support querying historical state. In the end the design is a tradeoff among read speed, disk growth, retention of past state, and proof-generation capability — and the state-growth problem is fought on top of exactly this storage-layout and pruning-policy choice.
Node sync speed, disk usage, and archive-node operating cost are all determined by this layout choice — infrastructure-cost discussions are, underneath, actually about this.
Code & Formula
# 상태 트리 저장 문제 — flat DB·경로 기반 스토리지 — 해시 기반 트리 순회 vs 평평한 키-값 조회의 비용을 비교한다.
# 계정 하나를 읽을 때 해시 기반 트리는 루트부터 여러 번의 랜덤 조회가 필요하지만, flat 레이아웃은 조회 1회로 끝난다.
import hashlib
def h(x):
return hashlib.sha256(x).hexdigest()
class HashTrieDB:
"""각 노드가 (부모+값)의 해시로 키잉되어, 리프까지 가려면 노드 수만큼 랜덤 조회가 필요하다."""
def __init__(self):
self.node_content = {} # node_hash -> 원래 값 (증명 등에 쓰이는 실제 데이터)
self.parent_of = {} # node_hash -> parent node_hash (None = 체인의 시작)
self.disk_seeks = 0
def build_path(self, values):
parent = None
for v in values:
node_hash = h((str(parent) + v).encode())
self.node_content[node_hash] = v
self.parent_of[node_hash] = parent
parent = node_hash
return parent # 마지막 노드 해시 (조회 대상)
def get_leaf(self, leaf_hash):
cur = leaf_hash
while cur is not None:
self.disk_seeks += 1 # 노드 하나 읽을 때마다 랜덤 조회 1회
cur = self.parent_of[cur]
return self.node_content[leaf_hash]
class FlatDB:
"""계정 주소를 바로 키로 써서 조회가 O(1)에 끝난다."""
def __init__(self):
self.store = {}
self.disk_seeks = 0
def put(self, key, value):
self.store[key] = value
def get(self, key):
self.disk_seeks += 1
return self.store[key]
DEPTH = 8
trie = HashTrieDB()
leaf_hash = trie.build_path([f"node{i}" for i in range(DEPTH)])
trie.get_leaf(leaf_hash)
flat = FlatDB()
flat.put("account-0xabc", "balance=1000")
flat.get("account-0xabc")
print(f"해시 기반 트리: 계정 1개 조회에 {trie.disk_seeks}회 랜덤 조회 (트리 깊이={DEPTH})")
print(f"flat DB: 계정 1개 조회에 {flat.disk_seeks}회 조회")
print(f"→ flat 레이아웃이 조회를 {trie.disk_seeks}배 줄인다 (트리는 루트 계산·증명 용도로 별도 유지)")
docs/code/algorithms/algorithms-73.py
Exercise
Read an execution client's documentation on its hash-based vs. path-based storage scheme, then table out the cost of three operations — account balance lookup, historical state lookup at a specific past block, and Merkle proof generation — under each scheme.
Practical Connection
When building an indexer for Verex that looks up past market state or balances at settlement time, whether to depend on an archive node or reconstruct state into your own DB from events is decided exactly by this cost structure.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.