2D-Filtermaps in Reth

Transcript

[music] [music] Thank you Mario. >> Yeah, anything works. So hi everyone, I'm Aayosh. I'm here to present my project on implementing 2D filter maps in RAT during the VPF cohort. So before how we understand how filter map works, we have to understand how bloom filter works and the problem with it. Assuming we all know how bloom filter works. I'm not going to go deep into this, but just to recap, the bloom filter scans all the log block headers and then finds the candidate blocks and looks into those candidate blocks, reads those receipts and gets you the data.

But uh now that the blocks are very busy, the bloom filter is uh very saturated and most of those blocks receives are wasted because uh there are just there are just too many false positives in bloom with bloom filters. On the other hand, filter maps can get you directly the candidate blocks without scanning through all the block headers and then you can look into those block headers and it never misses a match and it has far fewer false positives than Bloom. So this is my cohort timeline week by week. I started off with learning red's codebase and how GAT implemented the uh 2D filter maps in their codebase and all all the ideas regarding the filter maps.

Um and then I planned the project and I started building with in layers and I tested each layer each step against test data. But the problem with that was the when I was building every layer, I was building with every feature I wanted in in the end and the code just grew too big. So about a month and a half ago, I had to audit all the code and had to remove uh some of the core features and extra parts from the code. And I finished the lean version that I could benchmark and lastly I added the crash recovery and metrics and then I measured it on mainet.

So builder maps is part of EIP745. Uh it is part of pure 8 but it got replaced by superseded by another EIP called uh another EIP that is 8304 this year. But the filter maps are still served as a shipped shipped as a local index in Gat since last year. And uh before the cohort I had built my own indexer and bloom was one reason why it was slow. So I had already I already had some knowledge with uh bloom filters and the also in the previous cohort it was started in Wrath but it was never finished. So I thought it was a good project to continue.

Um I chose cat because uh it already ships the builder maps in production. It has exact and every rules uh tested in production and both the EIPs are still draft as of today. Um then I ported [snorts] each part uh the log values rows and columns math and uh some part of the pipelines to Wrath but the storage part was a little different because RAT has its own database. Uh it is MTPX if you know about it. So this is how filter map works. Uh we take all the addresses and logs and we index them in order and we assign positions on this um global index and about six uh 65,500

uh positions make up one map and that is about 20 blocks. So this is how a map looks like. We to calculate a row we take the hash of the value either value is either an address or a topic we hash it we do some other math on it and we get the rows and for the columns we take the global positions from the global index this is the global index with dict position from here and we do some different kind of math on uh this positions and get the columns and then we mark it on the map and then we in the storage we only store non- empty rows we the rows the row number will be the uh keys and the columns will be the values of those keys in the database. So

I started off with uh MDPX but it was a poor fit. MTBX is the RAT's own codebase database. Uh it only allows one writer for all Wrath operations. So all the block rights and index rights have to wait for each other and new because it's a B+ uh trees database uh all the new records can land between the old ones and it has to rearrange itself and uh about every 3 days we delete 2.1 million of uh rows for the maps to to save storage and MDBX does the does this one by one using the cursor. So I moved the whole index to its own ros DB. Now the block rightes

and index rightes don't have to wait for each other and then the new records go to the memory first get sorted and then it goes to the storage and the we can delete the uh data in three range delet. So it's much easier and efficient to delet with rocks db. This is how we read a query. When you submit a query using the ETH get logs, uh we take the values, address or topic from the from that query. We hash it. We do the same math we did on the rows and we get the row number. And after we get the row number, we can look up for those rows in the database. We get all the columns uh for those rows. We take the columns, we do the reverse math we did with the column and we get the global

positions back. So this is the global positions. We get the the global global positions from the columns and then we can check with uh which which block this positions falls into and we can we get those candidate blocks from there. Then we go through those candidate blocks. We look into those block receipts and get the data from there. This is the whole design. So for the right side in background the indexer is indexing all the final finalized blocks and it builds the maps with its rows and columns and it stores to the rocks DB.

And for the read side when you submit a log queries first we check if the blocks are in the index range or not. If it is we use the bloom path sorry we use the flintter maps path and uh read the database get the rows all that and then we finally read the receipts if not we we use the bloom path but in both parts we have to check the receipts of uh those blocks. So how much does this help? So before I get to the numbers this is how I benchmarked. I built another tool which runs scripts uh sending the it get lock queries. Sends the same it get lock queries to the

uh to a node I set up on the same machine with same binary with index on once and index off. So these are the three queries I ran. First one is rare contracts. So there are contracts, credit addresses and second is transfers to one wallet and the third one is tax indexers with thousand pools. So these are the results. Um these are the results for rare contracts. As you can see as as the range grows the time grows with it uh for the head headed bloom path and this as you can so as you can see the slope is much steeper. So it grows with with

the requests with the blocks and on the other hand filter map stays between the one millisecond to 7 milliseconds between 1 and 7 milliseconds and it doesn't grow as much as filter blooms with as the range grows. So uh an indexer doesn't send all the like if it has a big query it doesn't send it in one sweep. uh it it sends the queries to,000 blocks per per request breaks it down and I um I emitted that I simulated that and this is the result I got. So for red contracts the header boom header bloom

takes about 400 seconds more than 400 seconds and pill maps takes only about sub 1 seconds and same for the wallet transfers takes about 450 seconds and pillar maps takes 1.2 seconds. The index indexer is an exception. It is about 8% slower because uh both the paths read the same amount of receipts and it has and filter maps have to do the rows and column match and reads uh on the top of those block reading those blocks receipts.

So I also tested it under load. I I set up uh 1 to 64 clients which is processes uh and all all of them sends one queries sends the three queries we discussed to uh one mainet node that runs the index and it serves seven to eight times more um queries per second than the bloom path. So where this project stands right now uh right now it works. It is faster than bloom filter in many cases except some of them like text indexer and but it we only finalize the we only index the

finalized blocks. So about 100 blocks uh at the head is not indexed and they still use bloom filters and for about 2.335 million blocks it takes about 26 gigs of uh storage. So what's next is uh the missing features I removed. I was working on it but the code grew too big and I wanted to finish the project before this presentation. So I have to still implement the reorg handling if you if we were to index till head we have to handle the reorgs and also the checkpoints and back fills. So we can index in reverse. So you can query the recent uh recent blocks much faster than the than the usual path does.

Yeah, that was it. It was pretty small, but oops. >> Thanks so much. Any questions? Any thoughts? Anyone? Yeah, we get that. >> Um, for the test suit, like the test that you ran for the benchmarks, uh, is that uh, open sourced? >> Is it a >> Yes. Yes. These are the QR codes if you want to check out. >> Okay. Can you scan the FM bench? [snorts] >> Anyone?

>> Was it? >> Yeah. Just like that. Okay. Uh Aish, thank you so much. It's been incredible work. I have to say like honestly there is uh I would say red uh attracts the most contributors out of all the clients. So it's not easy to [music]