Optimise slasher storage of attester data

[michaelsproul]

Description

The slasher database is still growing, but ideally we would like it to settle down to an approximately constant size. I initially thought this was a problem with pruning (#1890), but it seems that isn't the case.

Analysing a slasher DB from mainnet which has been in use since genesis 4 months ago, we see a large number of pages in use for the attesters sub-database. In a DB of ~95 GiB the breakdown is roughly:

• 55.4 GiB for the attesters (14527008 leaf pages x 4 KiB), 448M entries 😱
• 37.8 GiB for the indexed_attestations (9898253 leaf pages) 29M entries
• 2 GiB for everything else

Shrinking the indexed_attestations data is the subject of #2112.

To shrink the attesters data will require a database schema change. Currently each entry is at least 80 bytes:

• 8 bytes: target epoch (key)
• 8 bytes: validator index (key)
• 32 bytes: the hash of the attestation data (value)
• 32 bytes: the hash of the indexed attestation (value)

Given this, we might naïvely expect the attesters DB to be 33 GiB (448M x 80 bytes) . What's the extra 22 GiB?? My current theory is that it's the previous versions of some items, which is how LMDB implements multi-version concurrency control (MVCC). There's some more info in this presentation from the LMDB creator:

http://schd.ws/hosted_files/buildstuff14/96/20141120-BuildStuff-Lightning.pdf

I quite like LMDB, and I'm willing to cop the ~2x overhead to retain its speediness. Hence I think our best option is to make that sub-database intrinsically smaller. Some ideas:

• The attestation data hash is present only for speed, it could be looked up from the indexed attestation. Although this would require us to do hashing, which would be too slow for every incoming attestation... so a bit of a non-starter.
• We could normalise the data so that there's a layer of indirection between the attesters DB and the 32 byte hashes. Add two new tables: indexed_attestation_hashes and attestation_data_hashes which map u64 => Hash256. This would shrink the two 32 byte hashes in the attesters DB to 16 bytes total, plus the total size of the _hashes tables, which should be small due to the number of attesters per attestation.
• We could use 5 bytes to encode the validator index (max validator registry size is 2**40)
• We could use 2 bytes to encode the target epoch (store it modulo history_length/4096)

The last 3 of these optimisations would bring attester entries to 16 + 7 = 23 bytes, a great reduction from 80! This might yield an attesters table of max size 19.19 GiB (448M * 23 bytes * 2 versions). Which gives us some headroom as the validator set grows!

Version

Lighthouse v1.2.1

Extra Info

Complete database stats for the DB described above:

$ mdb_stat -a -e slasher_db
Environment Info
  Map address: (nil)
  Map size: 274877906944
  Page size: 4096
  Max pages: 67108864
  Number of pages used: 24775669
  Last transaction ID: 868787
  Max readers: 126
  Number of readers used: 0
Status of Main DB
  Tree depth: 1
  Branch pages: 0
  Leaf pages: 1
  Overflow pages: 0
  Entries: 7
Status of attesters
  Tree depth: 5
  Branch pages: 135183
  Leaf pages: 14527008
  Overflow pages: 0
  Entries: 448178532
Status of current_epochs
  Tree depth: 3
  Branch pages: 5
  Leaf pages: 727
  Overflow pages: 0
  Entries: 112640
Status of indexed_attestations
  Tree depth: 5
  Branch pages: 179246
  Leaf pages: 9898253
  Overflow pages: 0
  Entries: 28548391
Status of max_targets
  Tree depth: 3
  Branch pages: 20
  Leaf pages: 2525
  Overflow pages: 0
  Entries: 110722
Status of metadata
  Tree depth: 1
  Branch pages: 0
  Leaf pages: 1
  Overflow pages: 0
  Entries: 2
Status of min_targets
  Tree depth: 3
  Branch pages: 110
  Leaf pages: 14526
  Overflow pages: 0
  Entries: 112640
Status of proposers
  Tree depth: 3
  Branch pages: 55
  Leaf pages: 8109
  Overflow pages: 0
  Entries: 129717

[rauljordan]

Hi @michaelsproul we ended up going with this schema: prysmaticlabs/prysm#8720 to help us reduce the size. We also incorporated the idea of 5 byte validator indices and 2 byte epochs modulo history_length. We ended up incorporating attesting indices as a quick-and-dirty way of reducing duplication in the db in our case