The State Trie Storage Problem — Flat DBs and Path-Based Storage TODO

Algorithms · Day 73 / 100 · E. Data & Storage Engines (Day 69-81)

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.

Where it lands in Jayverse

• Number: the research site's historical-reading queries face the same archive-node-versus-reconstructed-DB tradeoff. Decide up front whether Number reconstructs state from events into its own store rather than paying per-query archive-node cost.
• Devnet: document whether the hosted Anvil keeps full historical state or prunes it. This snapshot/pruning policy is the same storage-layout choice, and decides what queries any service can run against devnet.
• gitboard: price any dashboard query of past settlement state against this lookup-cost table. Do this before choosing to hit an archive node live instead of a maintained index.

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/.

한국어

상태 트리 저장 문제 TODO

Algorithms · Day 73 / 100 · E. 데이터·스토리지 엔진 (Day 69–81)

flat DB·경로 기반 스토리지

개념

이더리움 상태는 논리적으로 Merkle Patricia Trie지만, 이 구조를 그대로 키-값 DB에 담으면 계정 하나를 읽는 데 루트부터 리프까지 여러 번의 랜덤 조회가 필요하고 노드가 해시로 키잉되어 저장 지역성이 없다. 그래서 실행 클라이언트들은 계정과 스토리지 슬롯을 평평한 키로 직접 저장하는 flat/snapshot 레이아웃을 따로 두어 읽기를 한 번의 조회로 만들고, 트리는 루트 계산과 증명 생성 용도로 유지한다. 트리 노드 저장 방식은 노드 내용의 해시를 키로 쓰는 hash 기반과 트리 안에서의 경로를 키로 쓰는 path 기반으로 나뉘며, path 기반은 같은 경로의 이전 버전을 덮어써서 디스크 증가를 억제하는 대신 과거 상태 조회를 위해 별도의 되돌리기 저널이 필요하다. 결국 설계는 읽기 속도, 디스크 증가량, 과거 상태 보존, 증명 생성 능력 사이의 트레이드오프다. 상태 크기 증가 문제도 이 저장 레이아웃과 프루닝 정책 위에서 다뤄진다.

노드 동기화 속도, 디스크 사용량, 아카이브 노드 운영 비용이 전부 이 레이아웃 선택에서 결정되고, 인프라 비용 논의가 실은 이 얘기이기 때문이다.

코드 · 수식

# 상태 트리 저장 문제 — 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

연습

실행 클라이언트 문서에서 hash 기반과 path 기반 스토리지 스킴 설명을 읽고, 계정 잔액 조회·특정 과거 블록 상태 조회·머클 증명 생성 세 작업의 비용을 두 방식에 대해 표로 정리하기.

실무 · Verex 연결

Verex에서 과거 시장 상태나 정산 시점 잔액을 조회하는 인덱서를 만들 때, 아카이브 노드에 의존할지 이벤트를 받아 자체 DB로 상태를 재구성할지가 바로 이 비용 구조에서 갈린다.

Jayverse에서의 위치

• Number: 리서치 사이트의 과거 데이터 조회는 아카이브 노드 의존과 자체 DB 재구성 사이의 동일한 트레이드오프를 겪는다. Number가 쿼리마다 아카이브 노드 비용을 내는 대신 이벤트로부터 자체 저장소에 상태를 재구성할지 미리 정한다.
• Devnet: 호스팅된 Anvil이 전체 과거 상태를 보존하는지 가지치기하는지 문서화한다. 이 스냅샷/가지치기 정책이 바로 이 저장 계층 선택이며, devnet에서 어떤 서비스가 어떤 쿼리를 할 수 있는지를 결정한다.
• gitboard: 과거 정산 상태를 조회하는 대시보드 쿼리는 이 조회 비용 표에 따라 값을 매긴다. 유지되는 인덱스 대신 아카이브 노드를 실시간으로 두드리기로 결정하기 전에 이를 한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.