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

Linked overflow #387

Closed Scooletz closed 1 month ago

Scooletz commented 2 months ago

This PR changes how overflow pages work. Instead of having a complex logic of splitting keys by the first nibble (a part of it, masked to match the number of buckets), a simple linked list is used. This introduces some overhead for finding a value as all the elements in the list must be traversed, but can greatly decrease the amount of pages used for storing data.

Currently, a single LeafOverflowPage will point only to another one, making a chain of length of 2. This already shows nice size reduction. If generalized, this can be a succinct implementation with one or maybe two levels more.

github-actions[bot] commented 2 months ago

Code Coverage

Package Line Rate Branch Rate Health
Paprika 85% 80% ➖
Summary 85% (4534 / 5347) 80% (1422 / 1787) ➖

Minimum allowed line rate is 75%

Scooletz commented 2 months ago

image

Scooletz commented 1 month ago

Closed in favor of #405 that if modified to use the linked list, can be make it a bit better by separating the type of the page.