Paprika icon indicating copy to clipboard operation
Paprika copied to clipboard

Speed up access to block ancestors

Open Scooletz opened this issue 1 year ago • 1 comments

Currently, whenever a value is retrieved from Paprika, a list of ancestors is walked through to find whether or not the given value can be provided by it. It's optimized as it uses Xor filter to check whether the given block can serve the read or not. Still, it requires a lot of reads because it always loops over:

https://github.com/NethermindEth/Paprika/blob/0b36ee9daf34f0160e678253489b140fed786a3d/src/Paprika/Chain/Blockchain.cs#L1037-L1055

These reads could be sped up using various approaches.

Proposals

  1. squashing the anscestors: when the block is created for processing, squash ancestors so that they can serve values fast (proposed by: @benaadams @LukaszRozmej)
  2. use a Dictionary<ulong, ushort> which would map hash -> ancestor depth that would point to the first ancestor that has the hash set. This would be much easier and lighter to create. If no value for the given ulong, this means the db should be hit.

While the first approach would save lookups making them direct (one lookup against one value) the second could provide removal of Xor filters altogether or put Xor only on top of the map created in this way (this should be measured whether it's worth it)

Scooletz avatar May 09 '24 09:05 Scooletz

Could you assign me, please?

etimofeeva avatar May 09 '24 13:05 etimofeeva

This has been done with #345 introduction

Scooletz avatar Aug 29 '24 14:08 Scooletz