# Erigon Storage Design[^1]

- Store state in plain kv db.
- Store historical changesets explicitly to support versioning.
- Rebuild ethereum compatible merkle trie root hashes on the fly [^4].

## Versioning

Skipped the logic of incarnation for simple.

| Table | Key | Value |
| ------------------ | ------------------------------- | ------------------------------------------------------------ |
| Account History | `(address, block number)` | Set of block numbers that changes the account. |
| Account ChangeSets | `block number` | For the accounts that's changed in current block, store the *prior* value. |
| Storage History | `(address, slot, block number)` | Set of block numbers that changes the contract storage slot. |
| Storage ChangeSets | `block number` | For the contract storage slots that's changed in current block, store the *prior* value. |
| Plain States | `address` or `(address, slot)` | The latest states. |

# history: bucket for account history or storage history
# changeset: bucket for account changesets or storage changesets
# plain_states: bucket for the plain states.

def find_by_history(key, block_number):
    '''
    find the state in the beginning of the block_number
    for account, key is `address`,
    for contract storage, key is `(address, slot)`.
    '''
    bitmap = history[key + block_number]
    # try to find the smallest block which is >= block_number
    change_block, ok = bitmap.seek(block_number)
    if ok:
        # return the state recorded in the changeset
        return changeset[change_block].find(key)
    # return the latest state
    return plain_states[key]

## DupSort

Almost all keys[^5] enabled dupsort[^2] flag to avoid physical duplication of common prefixes of keys.

## BitMaps

Account history and storage history values are encoded as roaring bitmaps[^3].

Bitmap sizes on different work loads:

| Total blocks | Interval | Bitmap size | Chunks |
| ------------ | -------- | ----------- | ------ |
| 100000000 | 100 | 2041484 | 1047 |
| 100000000 | 1000 | 215260 | 111 |
| 100000000 | 10000 | 32652 | 17 |
| 10000 | 100 | 228 | 1 |
| 10000 | 1000 | 48 | 1 |

One bitmap may get stored as multiple consecutive chunks because of value size limit of underlying db, the chunks are indexed by the maximum value stored in the chunk, and the last chunk is indexed by `^uint64(0)`, since the bitmap is append-only, only the last chunk will be modified, and lookup can be done by seeking the chunk key first, so only need to load a single chunk.

## References

[^1]: https://github.com/ledgerwatch/erigon/blob/devel/docs/programmers_guide/db_walkthrough.MD
[^2]: https://github.com/ledgerwatch/erigon/blob/devel/docs/programmers_guide/dupsort.md
[^3]: https://github.com/RoaringBitmap/roaring
[^4]: https://github.com/ledgerwatch/erigon/blob/devel/docs/programmers_guide/guide.md#organising-ethereum-state-into-a-merkle-tree
[^5]: https://github.com/ledgerwatch/erigon-lib/blob/main/kv/tables.go#L600