# Incremental diff SSZ storage

## Goal

Improve Ethereum Consensus Layer node 'cold' or archive beacon state database:
- reduce DB size
- increase load speed

## Highlights
- The LevelDB database took **8.6 Gb** per 65K epoch states starting from the Altair hardfork (which is **~10Gb per year**)
- It takes **~190ms** on average (~280ms in the worst case) to read a random `BeaconState` instance from DB

## Idea

Many back up systems use incremental schema. I.e. they store initial full snapshot and then write only changes with some time period. To make the process of backup and recovery more effective the changes are organized into hierarchical structure.

E.g. every month the system stores changes relative to the initial full snapshot and then every day the system stores changes relative to the monthly state. That way restoring backup for some specific date requires:
- Load initial full snapshot
- Load and apply monthly diff
- Load and apply daily diff to the previous result

The similar approach was tested with respect to the binary SSZ representation of CL `BeaconState`


SSZ diffs are basically arranged to a tree like structure. To get an arbitrary epoch state SSZ we need to get corresponding yearly state SSZ snapshot and then incrementally apply monthly, weekly, ..., every-16-epochs, and finally epoch diffs

## Idea improvements

### Compression

Many `BeaconState` fields could be compressed pretty well. E.g. the whole state could be compressed (with Gzip) to about 60% of its original size. Thus all the diffs are stored compressed

#### Full snapshot compression note

While optimizing load performance it was noted that `Snappy` compressor significantly outperforms `Gzip` on decompressing speed while still yields quite affordable compression rate

### State `balances` field

It was noticed that a `balances` diff for neighbor epoch states contain >95% of equal values and thus is a good candidate for compression.

E.g. for some state (with ~400K validators):
- **3170**Kb: raw field SSZ size
- **3170**Kb: the same size for regular binary diff
- **1760**Kb: compressed regular binary diff
- **35**Kb: compressed `balances` `UInt64` values diff relative to the previous epoch state

Since we want to save a lot of space by storing balance diffs between neighbor epoch states we need to slightly redesign the diff schema for the last `EpochX1` step: we want to make diff as usual with the exception of the SSZ part corresponding to the `balances` field. So this is kind of 'composite' diff

We would also need to perform more steps when recreating a state SSZ:


### From Tree to DAG

The improved schema saves a lot of space however requires much more diffs to be loaded and applied.
The further idea for improvement is to separate `balances` diff and the rest of the whole binary diff.
Thus to restore a state the original schema is used for everything except `balances` SSZ. For `balances` part we use the 'iterative' approach. The final step is merging both `Rest Diff` and `Balances Diff` results


Worth to mention that prior to this scheme applying any diff at any stage resulted in a complete beacon state SSZ (the white graph vertices), however after splitting the schema applying `Balances Diff` results in just that part of SSZ where `balances` are serialized. Applying `Rest Diff` results in SSZ with 'nothing' in place of `balances`.

Such results appear as yellow vertices and are represented with a `SparseBytes` structure which is effectively just a byte array where some bytes are 'missing'

This DAG approach looks pretty flexible and potentially allows to combine different diff approaches throughout any levels

## The schema which was tested

Below is the summary of the actual schema used for testing:

| Name | Period (epochs) | Diff type | Sparse result | Compression |
|-------------------------------|-----------------|----------------------------------|---------------|------------------|
| eearSchema | 65536 | Snapshot | No | Snappy |
| eonthSchema | 8192 | Simple binary diff | No | Gzip |
| eekSchema | 2048 | Simple binary diff | No | Gzip |
| eaySchema | 256 | Simple binary diff | No | Gzip |
| epochX64Schema | 64 | Composite(UInt64, Simple binary) | No | Gzip |
| epochX16Schema | 16 | Composite(UInt64, Simple binary) | No | Gzip |
| epochX1MergeSchema | 1 | | No | |
| \\--->epochX1BalancesSchema | 1 | UInt64 diff | Yes | Gzip |
| \\--->epochX1RestSchema | 1 | Simple binary diff | Yes | Gzip |

## Size details

| Name | Count | Size(Mb) | Diff size |
|-------------------------------|-------|----------|-----------|
| eearSchema | 2 | 51 | 25496666 |
| eonthSchema | 8 | 98 | 12189263 |
| eekSchema | 32 | 163 | 5083683 |
| eaySchema | 255 | 1066 | 4181279 |
| epochX64Schema | 1004 | 1159 | 1154297 |
| epochX16Schema | 3796 | 2023 | 532831 |
| epochX1MergeSchema | | | |
| \\---> epochX1BalancesSchema | 61681 | 3435 | 55694 |
| \\---> epochX1RestSchema | 61681 | 1656 | 26853 |

## Drawbacks

- No `hash_tree_root` is stored. I.e. obtaining hash of any element of a freshly loaded state would required full rehashing
- Next hardfork spec changes might potentially introduce much more entropy to state diffs so the disk space gain would become less impressive

## Potential improvements

- Include slot grained states which would allow to load _any_ state without replaying state transitions. Implementing this would increase DB size x2-x3 for post Altair states according to very rough estimations
- Saving state performance optimization. It is now implemented naively and takes around 1000ms
- Further optimize DB space and load performance
- It's possible to implement 'partial' SSZ load. This could potentially be useful to optimize access to just a part of a state

## Proof of Concept

Prototype source: https://github.com/Nashatyrev/heku-tools/tree/master/apps/state-db

Modified Teku (modify SSZ Writer to annotate data chunks with their GIndexes): https://github.com/Nashatyrev/teku/tree/hack/state-db