search

NethermindEth / Paprika

A custom storage engine of Nethermind, benefiting from the alignment of the underlying data structure with the layout of State & Storage trees of Ethereum.
GNU Lesser General Public License v3.0
91 stars 14 forks source link

Bottom page #405

Closed Scooletz closed 3 weeks ago

Scooletz commented 1 month ago

This PR introduces a BottomPage that allows accumulating a lot of data changes before flushing them out as a DataPage. To make it work a BottomPage provides two pointers Left and Right that allow to divide keys to two buckets only. Then, on the next level, grandchildren are created if needed. This allows right now to create 7 bottom pages (1 on the 0th level, 2 on the 1st level, 4 on the 3rd level) which greatly reduces greedy fan outs. This could be pushed further with the next level and some more overflow logic if needed.

The structure can be optimized to be used to roll up DataPage on delete. At the same time such big deletes seem to be unlikely.

Similar to #387

Benchmarks

Database size reduced to 269GB, comparing to RocksDb of Nethermind with 158GB. Access times seem to be not impacted at all. Usually it can be up to 1 more level to query.

image

image

github-actions[bot] commented 4 weeks ago

Code Coverage

Package Line Rate Branch Rate Health
Paprika 85% 80% ➖
Summary 85% (4738 / 5583) 80% (1572 / 1960) ➖

Minimum allowed line rate is 75%