erigontech / erigontech/erigon

Improve commitment data locality by reworking how keys are assembled

Open
#17,838 13 comments 0 reactions 1 assignee Assigned to @awskii View on GitHub
performance
Dominant language
Go
Stars
3.6k
Forks
1.5k
Avg merge
1d 16h
Merged PRs (30d)
455

Description

The way we store commitment seems to not be the optimum way due to how we are assembling the keys.

I observed that while studying bloatnet data bc it become so evident (as you'll see in the pics below), but this is something that occurs in regular chains as well.

First lets recap how data is stored in commitment:

- the key is the MPT path (acc [+storage] post keccak).
- the path is then prefixed by 00 or 1 in order to indicate odd/even amount of nibbles + pad the slice in case of odd nibbles.

The result is given a commitment path, it is completely sharded by odd/even components in the DB, see how the path `2fbc66f2fb06bae7076b9f2e895396464b2341d649be9e3ec063a68a4cf5cd239e10a4ab6` is spread through 2 different regions of the DB:

Image

Image

this is not optimal bc it is potentially forcing each path read (in case of unfold) to touch 2 separate (cold) continuous areas in DB, and to write to separate continuous sections (in case of fold).

I'm not sure the historical reasons it is done this way, but I can't see any reason to keep it.

I can see that key transformation is done here: https://github.com/erigontech/erigon/blob/main/execution/commitment/keys_nibbles.go#L49

which is called by Branch/PutBranch while interacting with the DB. I don't see those prefixes involved with any other calculation. AFAIK we always reference fullpaths everywhere (could someone confirm?)

It seems we are follow the notation explained here: https://ethereum.org/developers/docs/data-structures-and-encoding/patricia-merkle-trie/#specification , but I don't think we need to follow that part of the spec or why it is applicable. I also don't see the prefixes 02 and 3 (odd/even leaf) in my dataset.

I think we can safely apply the following transformation to keys:

(before)
prefix + MPT path

(after)
MPT path + prefix (now suffix)

that way:

- we preserve the semantics of the keys (odd/even) while keeping the keys non ambiguous.
- the first byte of the path is always aligned with the first byte of the key, making the entire tree a sorted block in DB, improving data locality while traversing the tree.

**IMPORTANT**

- This is a big breaking change that invalidates all existing keys
- Chaindata must be migrated or deleted
- Existing commitment snapshots must be regenerated or converted (commitment v2?)
- Due to key change, that is a breaking change that makes new code incompatible with old commitment snapshots, and the rollout must be planned very carefuly.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.