erigontech / erigontech/erigon
commitment: hierarchical branch cache + delayed writes + parallel trie computation
- Dominant language
- Go
- Stars
- 3.6k
- Forks
- 1.5k
- Avg merge
- 1d 16h
- Merged PRs (30d)
- 455
Description
## Background
Commitment (Patricia trie hashing) is the bottleneck in the parallel execution pipeline. During sync, commitment takes 1.5–2.6x longer than execution per batch. At tip, commitment dominates per-block latency (seconds vs hundreds of ms for exec).
Three techniques exist in various stages of readiness that, combined, can significantly reduce commitment cost:
1. **Hierarchical branch cache** — from `add_execution_context_with_caches` branch (`branchCache` with fixed-size arrays for trie depth < 4, LRU fallback for deeper paths)
2. **Delayed trie writes** — already in main (`SetDeferCommitmentUpdates` / `FlushPendingUpdates` / `ApplyDeferredBranchUpdates`)
3. **Parallel trie computation** — already in main (`ConcurrentPatriciaHashed` / `ParallelHashSort` with 16-goroutine nibble parallelism), but not activating during sync
These need to be combined into a unified commitment optimization. Currently:
- The branch cache is part of a large breaking change (`ExecutionContext` replacing `SharedDomains`) that can't merge yet
- Delayed trie writes exist but are not wired into the main parallel execution flow
- Parallel trie computation exists but the structural condition (`CanDoConcurrentNext`) never fires during sync, so it runs in `mode=direct` (single-threaded)
## Goal
Extract the specialized commitment cache from `add_execution_context_with_caches`, wire it with delayed trie writes, and enable parallel trie computation. This is independent of the `ExecutionContext` refactor — we're extracting the cache as a standalone improvement.
## Current branch read path
```
unfoldBranchNode → readBranchAndCheckForFlushing
├── check deferred updates (ApplyDeferredUpdates if prefix is pending)
└── branchFromCacheOrDB
├── WarmupCache.GetBranch (if warmup ran) ← ephemeral, per-computation
└── ctx.Branch → SharedDomains.DomainGet → MDBX ← cold read, expensive
```
The current `WarmupCache` is ephemeral — built during warmup phase, consumed during computation, discarded. It does not persist across commitment computations. The new `branchCache` is persistent and exploits the trie access pattern.
## Design: hierarchical persistent branch cache
From `add_execution_context_with_caches`, the key insight is that trie branch access follows a predictable depth distribution:
| Depth (nibbles) | Array size | Description |
|------------------|-----------|-------------|
| 0 (root state) | 1 | `KeyCommitmentState` — most frequently accessed |
| 0 (root branch) | 1 | Single trie root branch |
| 1 nibble | 16 | First-level children |
| 2 nibbles | 256 | Second-level |
| 2.5 nibbles | 4096 | Third-level |
| 3 nibbles | 65536 | Fourth-level |
| > 3 nibbles | LRU | Deep paths — bounded LRU cache |
For depths 0–3 (which cover the hottest nodes), lookups are O(1) array index — no hashing, no allocation, no eviction. This matters because:
- Root + level-1 branches are read on **every** key during `unfoldBranchNode`
- There are only 16 level-1 branches (one per nibble)
- These hot nodes dominate the MDBX read profile during commitment
```go
type branchCache struct {
state ValueWithTxNum[BranchData] // commitment state (root hash + metadata)
t0 ValueWithTxNum[BranchData] // root branch
t1 [16]ValueWithTxNum[BranchData] // depth-1 branches
t2 [256]ValueWithTxNum[BranchData] // depth-2 branches
t3 [4096]ValueWithTxNum[BranchData] // depth-2.5 branches
t4 [65536]ValueWithTxNum[BranchData] // depth-3 branches
deep *lruCache[Path, BranchData] // deeper paths — bounded LRU
}
```
**Write-through**: when `PutBranch` is called (either inline or via `FlushPendingUpdates`), the cache is updated alongside MDBX. The cache is always fresh.
**Persistent across computations**: unlike `WarmupCache`, the `branchCache` lives on `SharedDomainsCommitmentContext` and persists across batch boundaries. Hot branches stay cached.
## Combining the three techniques
### Phase A: Extract and wire the hierarchical branch cache
1. Port `branchCache` from `add_execution_context_with_caches` into `execution/commitment/` as a standalone type
2. Add `branchCache` to `SharedDomainsCommitmentContext` (or `HexPatriciaHashed`)
3. Wire into `branchFromCacheOrDB`: check `branchCache` before MDBX read
4. Wire into `PutBranch`: write-through to `branchCache` alongside MDBX write
5. Wire into `ApplyDeferredBranchUpdates`: update cache entries for flushed branches
**Expected impact**: eliminates MDBX reads for depth 0–3 branches. These are the most frequently accessed nodes — root branch is read O(N) times per computation where N = number of keys. At 300k keys per sync batch, this eliminates ~300k MDBX reads for just the root branch.
**Files**: `execution/commitment/branch_cache.go` (new), `execution/commitment/hex_patricia_hashed.go`, `execution/commitment/commitmentdb/commitment_context.go`
### Phase B: Wire delayed trie writes into the parallel flow
The infrastructure exists (`SetDeferCommitmentUpdates`, `FlushPendingUpdates`, `ApplyDeferredBranchUpdates`) but isn't used in the main parallel execution path.
1. In `exec3_parallel.go`, enable `SetDeferCommitmentUpdates(true)` before `ComputeCommitment`
2. After `ComputeCommitment` returns the root hash, call `FlushPendingUpdates` to batch-apply all deferred branch writes
3. `FlushPendingUpdates` already uses parallel workers (`runtime.NumCPU()`) for `ApplyDeferredBranchUpdates`
**Expected impact**: reduces branch write overhead during trie traversal. Instead of N individual `PutBranch` calls scattered across the computation, branches accumulate in memory and are flushed in bulk. This reduces MDBX write amplification and improves cache locality.
**Key interaction with Phase A**: deferred writes update the `branchCache` at flush time, so subsequent reads within the same computation see fresh data (handled by `readBranchAndCheckForFlushing` which already checks deferred state).
**Files**: `execution/stagedsync/exec3_parallel.go`, `db/state/execctx/domain_shared.go`
### Phase C: Enable parallel trie computation during sync
`ConcurrentPatriciaHashed` splits the trie into 16 subtries by first nibble and processes them in parallel. Currently gated by `CanDoConcurrentNext()` which checks a structural condition on the trie root that apparently never fires during sync.
1. Investigate why `CanDoConcurrentNext()` returns false during sync — is this a fundamental constraint or a configuration issue?
2. If the structural condition can be relaxed (e.g. after the first full computation establishes the root), enable it
3. If not, explore an alternative: use `ParallelHashSort` (which exists in `hex_concurrent_patricia_hashed.go`) to process key sorting and warmup in parallel, even if the main hash computation remains single-threaded
**Key interaction with Phase A**: the `branchCache` is shared across the 16 subtrie goroutines. Since each subtrie works on a disjoint nibble prefix, cache reads don't conflict. Cache writes need synchronization (per-tier atomics or a lock).
**Key interaction with Phase B**: deferred writes from 16 parallel subtries must be coordinated. Either each subtrie has its own deferred buffer (merged at the end) or deferred writes use a concurrent map.
**Files**: `execution/commitment/hex_concurrent_patricia_hashed.go`, `execution/commitment/hex_patricia_hashed.go`
## Interaction with other work
- **#19791** (commitment pipelining): async `ComputeCommitment` + BAL-driven warmup. Phases A and B here make the commitment computation itself faster; #19791 makes it concurrent with execution. Complementary.
- **#19798** (event stream extraction): the `commitConsumer` in the fan-out dispatcher is where Phases B and C wire in.
- **#19711** (ibs-2cache phase 2+3): must merge first — cleans the write path that feeds `TouchKey`.
- **`add_execution_context_with_caches`**: Phase A extracts the cache without the `ExecutionContext` breaking change. When `ExecutionContext` eventually merges, the cache moves to `CommitmentDomain.branchCache` (already designed there).
## Ordering
```
Phase A (branch cache) ← standalone, can start after #19711 merges
│
├── Phase B (delayed writes) ← builds on A (cache updated at flush time)
│
└── Phase C (parallel trie) ← builds on A (shared cache) + B (deferred coordination)
```
Phase A is the highest-impact standalone change. Phases B and C build on it incrementally.
## Out of scope
- `ExecutionContext` refactor (big breaking change, separate timeline)
- Serial execution path (unchanged)
- Domain-specific caches for accounts/storage/code (separate from commitment cache)
Contributor guide
Assessment
This issue has not been assessed yet.