Towards Decentralized Lookup of 200 Million KV Entries

This work has been sponsored by Protocol Labs through their devgrants program! It is still ongoing, this article will be updated with examples and the current status of the project.

The code is currently in a very prototype state. It will be cleaned up and support all the features listed here.

Why?

With newer decentralized technlogies, most of the work tends to be done client side on static data. This requires downloading all the data to the client though. What if we want to perform a lookup in a dataset of 200 million entries without actually downloading the full thing? The IPLD project and ecosystem aim to provide tools that make this possible. In particular, this is the exact usecase for a HAMT or hash array mapped trie. Marek has a good introduction to this data structure and how it works. The IPLD team has provided a specification for how the structure can be laid out within IPLD blocks.

There are libraries in multiple languages that provide the ability to perform lookups, as well as build up HAMTs. However, building and updating a very large HAMT with hundreds of millions of entries poses an entirely new challenge. This is the specific usecase I’m aiming to solve with my Rust HAMT library.

Insertion

Rust provides fine grained control over memory, which is why it was choosen for this project. The trie is stored in memory akin to a linked list, where nodes have pointers to child nodes. When inserts are done, the changes are performed in memory. The conversion to a spec compliant IPLD HAMT is not done until all inserts are completed. This approach works well up to tries with tens of millions of small elements. However, for hundreds of millions of elements, memory usage ends up being too high. Therefore, the hamt-rs library will support serializing blocks onto disk. If this is required, inserts are performed as described in the update section.

This article will be updated with examples!

Updates

A IPLD HAMT has a CID for every block that can be used to uniquely identify it. Access to the CID is something I’d like to provide in hamt-rs. However, when changes are made, hamt-rs does not update CIDs instantly, as it requires updating every element back up to the root, so access to the CID should not be provided in this state.

This is achieved by using Rust’s type system as a state machine, allowing access to the CID when all of them have been recalculated and denying access when there is an update.

This is also the basis for very efficient partial updates. When a node is not is memory, it is fetched from the disk. Its child nodes are not loaded into memory, but instead represented as a verified stub. To update a specific element, only the nodes on its path are loaded into memory and since the sibiling nodes on every layer are verified stubs, they also do not have to be loaded into memory to calculate the new CID of the overall HAMT.

Performance

Preliminary performance tests show that 10 million entries can be inserted in ~15 seconds. This is pretty decent, but there is a glaring issue that could improve performance between 10 to 100x - cache locality.

Each node in the hashmap is laid out somewhat like this.

stuct Node {
    map: Bitvec,
    data: Vec<Node|Vec<Element>>
}

This is because the data is a sparse array, and a bitmap is used to save space as per the HAMT spec. Additionally, vectors are used for the data because its length is variable. This means that to interpret a node, there are 3 to 4 memory accesses required. While doing it like this made prototyping much easier, the next step for improving performance is to incorporate const generics, which Rust recently stabalized. It may be possible that the performance benefits of using a static array are worthwhile even at the cost of increased memory usage.