search

omni-network / omni

Monorepo for Omni node, contracts and other related tools
https://omni.network
GNU General Public License v3.0
93 stars 54 forks source link

Binary search offset cache #2368

Open sideninja opened 3 weeks ago

sideninja commented 3 weeks ago

During attestation offset search, we are returning the consensus block height at which the offset was found, which can be then used in the next search as a starting height; we call this cursor.

During the offset search, even if the cursor was provided, we still do a binary forward search between cursor (or 0 on cold cache) and latest, which does a lot of iterations (average 30 from metrics). In cases where relayer is catching up the difference between cursor and latest can be big; this means a wide range will be searched with a binary search, but every time a binary search finds attestations with a higher offset, this knowledge can be reused in the next offset search.

One way to reuse this knowledge is to keep an in-memory cache of offsets found, which only get evicted from the cache once the cursor is bigger than the cached offset value. Having this kind of cache means we can exhaust it for follow-up searches.

Additionally the binary search is currently not effective because it's performed between cursor and latest by default, which can be improved by doing a forward exponential search to find bigger offset and then doing a binary search between those two values.

sideninja commented 1 week ago

This issue will be re-evaluated after the relayer bootstrap is implemented, at that time we can gauge if the added complexity is worth it.