xavcochran

I made a byte-range cache for object storage.

For full hits it's zero copy. On a miss, it fetches only the missing bytes from object storage needed to serve the request.

It merges overlapping ranges and coalesces concurrent misses into one object storage request.

I use it primarily for a full-text search implementation that uses tantivy which was adapted to be transactional and run on object storage.

With our implementation, a full-text search only requires 2 round trips to object storage. The first trip gets the manifests so we know which blob files we need to fetch for the given search. The second trip gets the blobs determined by the manifests in parallel.

Each request first hits the range cache so that rather than downloading the whole split file (which can get large 100s MBs), it either gets a hit and returns, or has a miss and gets the specific bytes it needs.

If some of the data from an object storage request overlaps the data already in the range cache it merges it so you have continuous byte arrays to read from. e.g. let cache = {some_key: [0..100]} and a new request for `some_key` retrieves [50..200] from object storage, the new data in the cache would become {some_key: [0..200]}

Thought it was pretty neat and that it could be useful to some folks who are working with object storage.

In this post I want to talk about my experience building a database using RocksDB and why I switched to LMDB.

When I first started building HelixDB (https://helix-db.com), a graph-vector database written in Rust, I didn’t know which storage engine to use. After some chatgpt-driven development (lol) I went with RocksDB.

RocksDB worked well and we were able to build it quickly. Initial benchmarks showed good speed for both reads and writes; all was looking fine. Then came the time to deploy Helix in the cloud for a customer. During development, I was building on my mb pro so build times were not excruciating (~7 mins). However, in the cloud, we were deploying Helix on small aws instances. It would take over 40 minutes for Helix to build in the cloud, and sometimes it would just crash.

I started looking for a fix. Given graph DBs are read heavy when it comes to traversals, all things pointed to LMDB being a good option. I spent 6 hours changing over the graph engine to use LMDB under the hood. On the first build it took 40 seconds on my macbook, a 90% decrease, and in the cloud it was now building in ~4 mins. We also got a 60% read performance increase due to LMDB’s B-Tree storage architecture. Now I know RocksDB is still the king for writes and can be written to in parallel whereas LMDB can only be written to synchronously. At first the write slowdown was a worry, however, I was able to make some key design decisions that meant we are still able to write millions of nodes and edges to helix per second, save a huge amount of space on disk, and make reads even faster for graph and vector traversals.

The first thing I did was change the way we were storing keys. Originally we were naïvely storing keys as UUID strings which take up 36 bytes each. I changed this to UUIDv6 unsigned 128 bit integers which take up 16 bytes each (56% storage space saving). This change also allowed for something else. UUID v6 keys include the time of creation as part of the key meaning keys are lexicographically ordered based on creation time. This allowed me to use LMDB’s put flags (APPEND for nodes and edges and APPEND_DUP for direction storage) which makes LMDB insert the new item at the end of the db rather than traversing the tree internally to find the right place for it (APPEND_DUP also stores items with duplicate keys under one key instead of many).

This led to an extreme speed up of both reads and writes. Our current write speed is up to 5 million nodes per second and up to 700k edges per second. Note that the difference between the nodes and the edges is due to the fact we are storing the direction of each edge for each node separately. While this slows down the edge insertion (without inserting the direction, edge insertion is 5 million per second), it massively increases the read performance for edge traversals, which is a payoff we think is necessary. Our 1-hop performance is great as well with a performance with a performance of 5-100 μs (microseconds) per hop (dependant on start node) on a dataset of 65 million nodes and 1.9 billion edges. Note that all bulk reads are currently single threaded in HelixDB and we’re currently implementing parallel LMDB iterators via the Heed library with the guys from Meilisearch.

So with all that being said, I think LMDB wins the storage engine battle with the caveat that it is completely down to preference, workload and implementation.

Quickly touching on the vector side of Helix, from these performance improvements, our insertion performance is at around 2-5ms (dependent on the vector) and 3ms per vector search (with cosine similarity with 1M vectors).

Would love to hear more about people’s experience with LMDB, RocksDB or another storage engine, especially if people have found crazy performance boosts/hacks.

PS: We love feedback :)

See our code and our optimizations here: https://github.com/HelixDB/helix-db

The benefit of baking in the dimension and size of individual elements (the precision) is the fact that the size will be known at compile time meaning it can be allocated on the stack instead of being heap allocated.

We utilize some of LMDB's optimizations such as the APPEND put flags. We also make use of LMDB handling duplicates as a one-to-many key instead of duplicating keys. This means we can get all values for one key in one call rather than a call for each duplicate.

For keys we are using UUIDs, but using the v6 timestamped uuids so that they are easily lexicographically ordered at creation time. This means keys inserted into LMDB are inserted using the APPEND flag, meaning LMDB shortcuts to the rightmost leaf in its B-Tree (rather than starting at the root) and appends the new record. It can do this because the records are ordered by creation time meaning each new record is guaranteed to be larger (in terms of big-endian byte order) than the previous record.

We also store the UUIDs as u128 values for two reasons. The first is that a u128 takes up 16 bytes where as a string UUID takes up 36 bytes. This means we store 56% less data and LMDB has to decode 56% less bytes when doing code accesses.

For the outgoing/incoming edges for nodes, we store them as fixed sizes which means LMDB packs them in, removing the 8 byte header per Key-Value pair.

In the future, we are also going to separate the properties from the stored value as empty property objects still take up 8 bytes of space. We will also make it so nothing is inserted if the properties are empty.

You can see most of this in action in the storage core file: https://github.com/HelixDB/helix-db/blob/main/helixdb/src/he...

Looking at your benchmarks you say for inserting 1k edges its around 500,000 ns/iteration. Is this 500,000 ns/per edge insertion or for all 1k of them?

thank you! any feedback would be much appreciated

SPALDE*

there is also the fact that the more dimensions you have for embedded data the more diluted the embedding becomes so it is unusual to go anywhere near the limits of vector length!

very interesting, will look into this. I know for a fact that you cannot compile the likes of LMDB and RocksDB to work with WASM but this looks promising for our custom storage engine to be able to make it work with the browser. Thanks for this!

We will definitely look into it. The SPLADE models look promising!

to add to George's reply, for helix to run on the browser with WASM the storage engine has to be completely in memory. At the moment we use LMDB which uses file based storage so that does't work with the browser. As George said, we plan on making our own storage engine and as part of that we aim to have an in-memory implementation.

thanks for the question! we chose f64 as a default for now as just to cover all cases and we believed that basic vector operations would not be our bottleneck initially. As we optimize our HNSW implementation, we are going to add support for f32 and binary vectors and drop using Vec<f64/f32> and instead use [f64/f32; {num_dimensions}] to avoid unnecessary heap allocation!

apart from the fact Cozo seems to be pretty dead, we use a different storage engine which makes our reads much faster. based on their benchmarks I estimate our most of our reads to be 10x faster. I think our query language is much simpler, and easy to understand than Datalog which is what they use.

Assuming you are using GPUs for model inference, the best way to set it up would have the DB and a separate server to send inference requests. Note that we plan on support custom model endpoints and on the database side so you probably won't need the inference server in the future!

Thanks for the kind words! At the moment the query language transpilation is quite unstable but we are in the process of a large remodel which we aim to finish in the next day or so. This will make the query language compilation far more robust, and will return helpful error messages (like the rust compiler). The other thing is the core traversals are currently single threaded, so aggregating huge lists of graph items can take a bit of a hit. Note however, that we are also implementing parallel LMDB iterators with the help of the meilisearch guys to make aggregation of large results much faster.