Patching LMDB: how we made Meilisearch’s vector store 3× faster

[In Meilisearch v1.6](https://www.meilisearch.com/blog/meilisearch-1-6), we revolutionized search by combining the precision of full-text search with the intelligence of AI. This hybrid approach isn't just another feature—it's a fundamental reimagining of how search should work. Today, we'll pull back the curtain on our implementation and show why Meilisearch's unique approach to hybrid search delivers superior results.

Join us as we explore the mechanics of hybrid search, examine conventional implementation methods, and reveal how Meilisearch's innovative solution raises the bar for search relevance.

## What is hybrid search?

Search is always about finding the documents that are the most relevant to a user’s query.

Hybrid search is about combining the results of two complementary approaches to search: full-text search and semantic search.

[Full-text search](https://www.meilisearch.com/blog/how-full-text-search-engines-work) analyzes the words that appear in a query in a lexical manner, excelling at correcting typos and completing incomplete queries. It is also fast, and its results are easy to understand in retrospect.

[Semantic search](https://www.meilisearch.com/blog/semantic-search) leverages Large Language Model (LLM) technology to understand the meaning of words in the query. It excels at finding documents that contain synonyms to the user’s query and other similar concepts.

Both search approaches build a list of relevant documents according to their respective methods. Hybrid search combines these lists to produce a final list of results.

The golden question is, how to combine them?

![Diagram containing two lists of documents as shapes (squares for full-text, diamonds or triangles for semantic), and an arrow with an interrogation mark that produces a new list of documents containing both kinds of shapes](https://unable-actionable-car.media.strapiapp.com/how_to_merge_55aea77e87.png)

## The traditional way of mixing results is flawed

The traditional method of mixing the results from both lists is called [_Reciprocal Rank Fusion_ (RRF)](https://medium.com/@devalshah1619/mathematical-intuition-behind-reciprocal-rank-fusion-rrf-explained-in-2-mins-002df0cc5e2a), because it considers the **rank** of the documents in each list of results, and uses that as a basis to compute the final list of results.

In this context, the rank of the document refers to its position in the list of results, indicating how close it appears to the top.

For example, in a list of 20 documents, the result ranked first can be attributed 20 points. RRF can then attribute points to documents in each of the lists, sum the points for each document, and reorder the documents accordingly. Here’s a [detailed explanation](https://learn.microsoft.com/en-us/azure/search/hybrid-search-ranking) about an implementation of RRF on Azure AI Search.

However, this method of mixing results is flawed, because to function properly, it assumes that documents from all the lists of results are of comparable relevance: that is, all the documents in all lists are “good documents” that we want to return.

![Keyword search. Pikachu uses "imprecise query". It's super effective!](https://unable-actionable-car.media.strapiapp.com/pikachu_hybrid_search_f4f9e6c29f.jpg)

But, like Pokémons, each search method is vulnerable to different types of search queries. Covering for the weakness of the other method is the whole point of mixing them!

So let’s say you’re using a query that is fine for semantic search, but gives underwhelming results for keyword search. Using RRF, you might get some variant of the following:

![Illustrated example of the downfall of rank fusion](https://unable-actionable-car.media.strapiapp.com/RFF_merge_789ff4e216.png)

Recursive rank fusion is like wasting fine chocolate by mixing it with spoiled milk!

To address this issue, we require additional information about the documents listed in our results.

## Ranking is not enough: Scoring documents

The main idea is that you can score _how_ relevant a document is from 0 (not relevant at all) to 1 ("perfect” match), independently of its rank in the list.

Naturally, documents closer to the top of the list are more relevant, but the first document might be anywhere between 0 and 1. Then, you compare the scores in both lists and rank the documents across both lists that way.

Fortunately, Meilisearch already scores documents for full-text search (for more details about this, refer to [our previous article about scoring](https://www.meilisearch.com/blog/from-ranking-to-scoring)), and semantic search natively ranks documents depending on how similar they are to the query (although the details are complicated).

So we have a score for both full-text search and semantic search, but can we compare them?

## Making the scores comparable

When you have two scores ranging from 0.0 to 1.0, it can be tempting to compare them, but for this to work, similarly relevant documents must be scored similarly with both methods.

One difficulty that arises when performing this comparison is that the models used in semantic search tend to use only a portion of the full vector space they could use, resulting in vectors that have a similarity of at least 0.5 even for texts that appear entirely dissimilar. Furthermore, even very similar texts might be capped in similarity around 0.7, which will cause them to rank lower than good full-text results.

Fortunately, Meilisearch provides the tools to solve that particular problem. Meilisearch allows you to perform an affine transformation to the scores of the semantic search, so that the scores can be offset by the observed mean similarity between vectors, and the results that are packed around that mean similarity can be spread more in the 0.0, 1.0 space. For more details, refer to [the documentation on the](https://www.meilisearch.com/docs/reference/api/settings#distribution) `distribution` [field](https://www.meilisearch.com/docs/reference/api/settings#distribution).

For models known to Meilisearch (such as OpenAI models), a suitable default distribution is already applied to configured embedders, so users don’t have to configure it themselves!

With this operation, our scores are comparable, and depending on the query, the method that produces the most relevant documents will be favored by the hybrid search

![Failing example, running with Meilisearch, yields better results](https://unable-actionable-car.media.strapiapp.com/meili_merge_9bb48a7b7d.png)

## What else goes into making hybrid search right?

Scoring documents is a decisive relevancy advantage of Meilisearch over the traditional approach based on Reciprocal Rank Fusion, but there are a lot more aspects involved in making hybrid search right:

- We developed our bespoke vector store, [arroy](https://github.com/meilisearch/arroy), to leverage our database backend (LMDB) and meet our performance target. Arroy supports Approximate Nearest Neighbor search, multiple distances, native document filters, and binary quantization. Arroy doesn’t block a reader while writing or a writer while reading, and allows for incremental updates.
- We kept flexibility in mind with the mantra of making easy things simple, and hard things possible: users that are new to hybrid search can quickly setup an embedder with our default provider and configuration, but users can also carefully optimize their embedding process with multiple supported provider (or even the ability to provide your own with [REST embedders](https://www.meilisearch.com/docs/learn/ai_powered_search/configure_rest_embedder) and [user-provided embeddings](https://www.meilisearch.com/docs/learn/ai_powered_search/search_with_user_provided_embeddings)) and [document templates](https://www.meilisearch.com/docs/learn/ai_powered_search/document_template_best_practices) to customize how documents are turned into text to embed.
- Best-in-class full-text search engine, seamlessly integrated with semantic search, with support for efficient and expressive [sorting and filtering](https://www.meilisearch.com/docs/learn/filtering_and_sorting/working_with_dates) of documents.

Search is foundational; it needs to be rock solid to reliably serve the needs of your application. Meilisearch’s hybrid search implementation scores documents to merge results while preserving their relevancy. Scores also power the [federated search](https://www.meilisearch.com/docs/learn/multi_search/multi_search_vs_federated_search#what-is-federated-search%3F), a generalized version of semantic search that unifies results from multiple lists of intermediate hits.

Our users use federated search to perform hybrid searches across multiple vector stores, frequently combining image and text search requests.

## Why Meilisearch's hybrid search stands apart

Meilisearch's innovative approach to hybrid search goes beyond simply combining full-text and semantic search results.

By implementing a sophisticated scoring system instead of traditional rank fusion, carefully calibrating score comparability, and building a robust technical foundation with arroy, we've created a hybrid search solution that consistently delivers more relevant results.

This thoughtful implementation ensures that the strengths of each search method are preserved while compensating for their weaknesses, setting a new standard for search relevance in modern applications.

Why traditional hybrid search falls short (and how we fixed it)

When you're handling millions of documents in a search engine, every millisecond counts. That's why we've completely reimagined how Meilisearch processes data with our new indexer in v1.12. We've rewritten our indexer—the core component that processes your documents and builds search structures—from the ground up. The result? A faster, more efficient, and more scalable system.

This complete redesign fundamentally changes how our search engine handles data. In this article, we'll show you how we've achieved up to 4x faster document updates and 30% smaller database sizes, and what this means for your applications.

## A foundation for the future

We've named this release `Indexer edition 2024`, reflecting our vision to build a foundation that will power Meilisearch's performance for years to come. Inspired by [Rust's edition model](https://doc.rust-lang.org/edition-guide/editions/index.html), this isn't just an update—it's a new chapter in Meilisearch's evolution, setting the stage for future innovations in search technology.

(Also like Rust editions, we took the year it was developed rather than the year it was released 😁)

## Why would you write a new indexer?

![the-doctor-meme.jpg](https://unable-actionable-car.media.strapiapp.com/the_doctor_meme_1f1323b0c6.jpg "The Doctor would not rewrite an indexer")

_The Doctor would not rewrite an indexer_

You need a _very_ strong reason to re-write an indexer. And we had one.

As our CTO Kero put it bluntly in his blog post: [Meilisearch is too slow](https://blog.kerollmops.com/meilisearch-is-too-slow). The new indexer is our answer to that challenge—a ground-up rewrite to dramatically improve speed.

The main goal of the new indexer is to improve the indexing speed of larger indexes with dozens of millions of documents, to relieve some of the stress on our infrastructure, to better exploit the resources of the machine, and to address some long-running pain points in a structured way.

## The crux of the matter: performance improvements

![Meme from the Jurassic Park movie with a t-rex (10m document updates) chasing a Jeep (Meilisearch)](https://unable-actionable-car.media.strapiapp.com/sometimes_more_speed_e32b6e5390.jpg "Sometimes you really gotta go faster")

_Sometimes you really gotta go faster_

In various scenarios, the new indexer is faster, sometimes multiple times faster, than the already optimized v1.11 indexer.

On machines with multiple cores, good IO and a lot of RAM, performance is vastly increased. Inserting new documents is twice as fast, while incrementally updating documents in a large database is x4 faster!

While the goal was to improve performance on bigger machines, we were successful in keeping similar or better performance for more modest machines with fewer cores and humble RAM (good IO remains vital to a database, though).

Additionally, for Cloud customers, we’re exploring optimizing our build by using native CPU instruction and [link-time-optimization (LTO),](https://llvm.org/docs/LinkTimeOptimization.html) yielding up to 12% improvements. We’re also considering advanced techniques like [profile-guided optimization (PGO)](https://doc.rust-lang.org/rustc/profile-guided-optimization.html), which so far has yielded an additional 12% improvement over native instructions and LTO.

## How it’s done: more parallelism, fewer I/O operations, pipelining writes

Meilisearch used to split a payload of documents into multiple chunks (roughly one per indexing thread), and would then work each chunk throughout the entire extraction process. Once a chunk was finished, it would then be persisted in the database.

This approach had a couple of drawbacks, performance-wise:

- As a lot of temporary data was extracted at the same time, it had to be written to disk and then read back to be persisted in the database, causing a lot of I/O operations.

- As the chunks were built independently of each other, they could result in us writing the same key to the database for each chunk, again causing unnecessary writes.

- As the chunks would finish computing at the same time on average, the indexing process would intensively use all the CPUs while computing the chunks, but then be solely single-threaded while writing everything to the database.

![old-process.png](https://unable-actionable-car.media.strapiapp.com/old_process_75e046f6ab.png "Simplified representation of the previous indexing process")

_Simplified representation of the previous indexing process_

In the new indexer, Meilisearch iterates in parallel over documents, performing a single extraction operation at a time. The result of that extraction is then merged in parallel, to compute the list of keys and values to send to the database. These keys and values are sent to the writer thread in a channel that acts as a pipeline, reducing the time where the merger threads wait for the writer thread.

![waits-faster.jpg](https://unable-actionable-car.media.strapiapp.com/waits_faster_36160c6cfb.jpg "The merger threads wait less thanks to pipelining")

_The merger threads wait less thanks to pipelining_

We successfully made the merger step parallel thanks to a key insight: while the extraction steps split documents between multiple threads, the merger step has to split database keys between multiple threads. For instance, to build the reverse index that matches a word with the list of documents that contain that word, each thread reads some of the documents to extract the words it contain, then all the documents containing a word are merged into a single list.

To make this possible, all threads during the extraction step deterministically hashes each word it encounters. Then during the merger step, words to handle are partitioned between threads depending on their hash value.

![new-process.png](https://unable-actionable-car.media.strapiapp.com/new_process_a34768ffec.png "Simplified representation of indexing process edition 2024")

_Simplified representation of indexing process edition 2024_

The drawback to this new approach is that some CPU-intensive operations, such as document tokenization, have to be duplicated across all steps. Still, merging in parallel utilizes a machine's multiple cores much more, reducing the time Meilisearch spends single-threaded.

Furthermore, by not duplicating key writes, the database size has been reduced by more than 30%.

## Better RAM control and usage

Meilisearch uses [bumpalo](https://docs.rs/bumpalo/latest/bumpalo/) to improve RAM control. Bumpalo is an arena allocator that allows to bulk deallocate memory and to query how much memory was allocated in an arena.

Arena allocators are often used in video games for objects that have to be recreated on each game frame, because allocating in an arena is very cheap (just a pointer bump), and deallocating can happen in bulk (yet another pointer bump) as long as no destructor has to be run.

In some regards, indexing documents with Meilisearch also has “frames”. In the new indexing approach, we can even detect two kinds of such frames: A very short-lived frame that corresponds to the work done on each document. And a longer-lived frame that starts at the beginning of each extraction step, and ends right after the merger is done sending everything to the writer. The “document” arena contains all allocations related to reading and tokenizing that document, while the “extraction” arena contains all allocations related to the data being extracted that will then be merged and written to the database.

![new-process(1).png](https://unable-actionable-car.media.strapiapp.com/new_process_1_ffaf674cd9.png)

During this process, Meilisearch queries the size of the “extraction” arena to detect when its RAM usage is above the threshold. When this happens, Meilisearch spills excess data to disk, so that the RAM usage stays in control.

If the extracted data fits in RAM, it never hits the disk, yielding fewer I/O operations.

## Faster and more reliable task cancellation

Historically, in the previous indexer, chunks of documents used to be very small, so it made sense to allow cancellation only after a chunk was done processing. Unfortunately, small chunks were inefficient when writing temporary data to disk, so we decided to switch to a “one chunk per core” model a few versions ago. This had an adverse effect on cancellation, as it would be processed almost at the end of the indexing process after all threads finished processing their chunk.

As the new Meilisearch iterates on documents, and further split the process by each extraction step, task cancellation is faster than ever, routinely being processed under 1s!

![cancel-all-the-tasks.jpg](https://unable-actionable-car.media.strapiapp.com/cancel_all_the_tasks_16b21cbbec.jpg "For all of you who regret sending all these documents at once")

_For all of you who regret sending all these documents at once_

## Better error messages

The new architecture exposes the document id to all extractors. This means that error messages can be enriched with this information as was done in [this PR](https://github.com/meilisearch/meilisearch/pull/5153): knowing which document caused the error allows for more effective troubleshooting.

## Better observability with progress

Lastly, the new indexer brings better observability to the table: because we know both which step we’re at and how many documents have been handled for this step, we can expose this information in the newly added `batches` [](https://www.notion.so/Enhance-visibility-on-batched-tasks-1194b06b651f810b8fe0fab5d72846a8?pvs=21)[route](https://www.notion.so/Enhance-visibility-on-batched-tasks-1194b06b651f810b8fe0fab5d72846a8?pvs=21) as a `progress` object.

```
{
  "uid": 160,
  "progress": {
    "steps": [
      {
        "currentStep": "processing tasks",
        "finished": 0,
        "total": 2
      },
      {
        "currentStep": "indexing",
        "finished": 2,
        "total": 3
      },
      {
        "currentStep": "extracting words",
        "finished": 3,
        "total": 13
      },
      {
        "currentStep": "document",
        "finished": 12300,
        "total": 19546
      }
    ],
    "percentage": 37.986263
  },
  "details": {
    "receivedDocuments": 19547,
    "indexedDocuments": null
  },
  "stats": {
    "totalNbTasks": 1,
    "status": {
      "processing": 1
    },
    "types": {
      "documentAdditionOrUpdate": 1
    },
    "indexUids": {
      "mieli": 1
    }
  },
  "duration": null,
  "startedAt": "2024-12-12T09:44:34.124726733Z",
  "finishedAt": null
}
```

In the above, we know that we finished extracting the words of 12300 out of 19546 documents. There are a total of 13 indexing steps, and we finished 3 of them already, for a global completion of 37.986263%.

Note that the `progress` object should only be used for display purposes, we do not guarantee that the step names or number remain the same from one version to the next.

Adding the `progress` object is a boon for the engine's observability, which already scored us concrete wins. We identified the bottleneck in a customer’s workload just by repeatedly calling the `batches` route and looking at which step was frequently seen.

## The best is yet to come!

The new indexer reaches new heights in maintainability with its structure that decouples the “business” extractors from its support functions (cancel, progress, reading a document), allowing us to quickly iterate on features, such as new settings to fine-tune the indexing behavior and the [AI stabilization](https://www.meilisearch.com/blog/meilisearch-1-13). In the future, we plan on adding progress to the settings tasks, enriching finished batches with the timing of each step. Feel free to share your ideas about what you’d like to see in Meilisearch on the [product discussion](https://github.com/orgs/meilisearch/discussions). If you’re new to Meilisearch, you can also try it for free on our Cloud.

Introducing Meilisearch's next-generation indexer: 4x faster updates, 30% less storage

_This blog post was originally published on kero's [personal blog](https://blog.kerollmops.com/meilisearch-indexes-embeddings-7x-faster-with-binary-quantization)._

<Callout intent="note">
This is one blog post in a series:
- [Spotify-Inspired: Elevating Meilisearch with Hybrid Search and Rust](https://blog.kerollmops.com/spotify-inspired-elevating-meilisearch-with-hybrid-search-and-rust)
- [Multithreading and Memory-Mapping: Refining ANN Performance with Arroy](https://blog.kerollmops.com/multithreading-and-memory-mapping-refining-ann-performance-with-arroy-in-rust)
- [Meilisearch Expands Search Power with Arroy's Filtered Disk ANN](https://blog.kerollmops.com/meilisearch-expands-search-power-with-arroy-s-filtered-disk-ann)
- [How Meilisearch Updates a Millions Vector Embeddings Database in Under a Minute](https://blog.kerollmops.com/how-meilisearch-updates-a-millions-vector-embeddings-database-in-under-a-minute)
- Meilisearch Indexes Embeddings 7x Faster with Binary Quantization.
</Callout>

For the past year at Meilisearch, [we’ve been working hard on hybrid search](https://github.com/meilisearch/meilisearch/issues/3838), which mixes keyword search with semantic search using [Arroy: our vector store, based on a Spotify technology](https://blog.kerollmops.com/spotify-inspired-elevating-meilisearch-with-hybrid-search-and-rust). A vector store is a data structure that efficiently stores embeddings (vectors) for fast and relevant retrieval, called Approximate Nearest Neighbors (ANN) search.

When our customers started to use arroy heavily, some of them started reaching the machine limits. For example, for a customer with a 768 dimensions model, we found out that we couldn’t index more than 15M of embeddings on a machine with 64GiB of RAM.

### Binary Quantization to the Rescue

The concept behind this elaborate term is that we are going to *quantize* the embeddings. Quantizing a number involves spreading it into a defined number of values; for *binary* quantization, two values can be represented on a single bit, e.g., 0.2561 becomes 1, and -0.568 becomes -1.

This implies that we could convert a 32-bit float number into a 1-bit number, which would divide the disk and RAM usage by 32. That would mean we could index up to 480M embeddings with 64GiB of RAM, instead of being limited to 15M embeddings.

An issue we faced is that bits cannot represent -1 and 1 but only 0 and 1. We had to use some tricks to make it work and fake 0s into -1s in our computations. For example, one of the functions that we had to optimize a lot was the function in charge of converting a binary quantized vector to 32-bit float vectors.

We do not publicly expose raw quantized embeddings and utilize this function to provide real 32-bit float embeddings to the users. However, the primary reason for converting 1-bit quantized embeddings to 32-bit floats is to ensure high precision when [generating hyperplanes to group embeddings together](https://blog.kerollmops.com/spotify-inspired-elevating-meilisearch-with-hybrid-search-and-rust#spotify-s-hyperplane-trees-for-efficient-anns) and maintaining relevant ANNs.

![Profiling backtrace showing slow 1-bit to 32-bit float conversion](https://unable-actionable-car.media.strapiapp.com/68747470733a2f2f692e696d6775722e636f6d2f497165713649562e706e67_596adc5fd5.png)

_Converting a quantized embedding back to 32-bit floating points takes up to 24.21s on a 1m53s run._

Below is the SIMD neon-specific version of this function. It processes raw bytes corresponding to a 1-bit quantized embedding, converting them into a properly aligned 32-bit float embedding. Using masks, the function separates the low and high bits, processing them in batches of four in 128-bit registers, which are then transformed into four 32-bit floats. These values are collectively written to the output vector.

```rust
unsafe fn to_vec_neon(bytes: &[u8]) -> Vec<f32> {
    let mut output: Vec<f32> = vec![0.0; bytes.len() / u32::BITS];
    let output_ptr = output.as_mut_ptr();
    let low_mask = [0b_0000_0001, 0b_0000_0010, 0b_0000_0100, 0b_0000_1000];
    let high_mask = [0b_0001_0000, 0b_0010_0000, 0b_0100_0000, 0b_1000_0000];
    let ones = unsafe { vld1q_dup_f32(&1.0) };
    let minus = unsafe { vld1q_dup_f32(&-1.0) };

    for (current_byte, base) in bytes.iter().enumerate() {
        unsafe {
            let base = *base as u32;
            let base = vld1q_dup_u32(&base);
            for (i, mask) in [low_mask, high_mask].iter().enumerate() {
                let mask = vld1q_u32(mask.as_ptr());
                let mask = vandq_u32(base, mask);
                // 0xffffffff if equal to zero and 0x00000000 otherwise
                let mask = vceqzq_u32(mask);
                let lane = vbslq_f32(mask, minus, ones);
                let offset = output_ptr.add(current_byte * 8 + i * 4);
                vst1q_f32(offset, lane);
            }
        }
    }

    output
}
```

_<a href="https://x.com/lemire/status/1835700368648323261">Daniel Lemire doesn't seem to have found a better algorithm</a>_ 🤭

### The Results

We chatted about the theoretical benefits of this approach earlier, but how does it work out in real life? Here are different tables summarizing the results for you.

<details>
  <summary>Open to see the original benchmarks</summary>
  <img src="https://unable-actionable-car.media.strapiapp.com/68747470733a2f2f692e696d6775722e636f6d2f67667765626b592e706e67_a96a995c7c.png"  alt="Original arroy benchmark results"/>
</details>

#### Embeddings with 1024 Dimensions

When examining small embeddings, we can observe a significant impact on relevancy due to binary quantization. The primary advantages of this approach lie in faster insertion times and reduced storage requirements. It is not advisable to enable this feature for small embeddings, as they already occupy minimal disk space. Storing over four million 1024-dimensional embeddings requires just 8 GiB of disk space.

| Version                 | Recall @1 | Recall @20 | Recall @100 | Indexing time | Search time | On disk size |
|-------------------------|-----------|------------|-------------|---------------|-------------|--------------|
| Cosine                  | **1.00**  | **0.72**   | **0.84**    | 491s          | **23s**     | 8 GiB        |
| Binary Quantized Cosine | 0.87      | 0.50       | 0.52        | **147s**      | 27s         | **850 MiB**  |

#### Embeddings with 1536 Dimensions

Binary quantization proves advantageous for managing larger embeddings. It significantly reduces search times, utilizing just 15% of the original disk space. Indexing about 500,000 1536-dimensional embeddings is achieved in a quarter of the time. Despite this, there remains a noticeable impact on relevancy...

| Version                 | Recall @1 | Recall @20 | Recall @100 | Indexing time | Search time | On disk size |
|-------------------------|-----------|------------|-------------|---------------|-------------|--------------|
| Cosine                  | **1.00**  | **0.82**   | **0.90**    | 1219s         | 50s         | 13 GiB       |
| Binary Quantized Cosine | **1.00**  | 0.70       | 0.70        | **235s**      | **47s**     | **2 GiB**    |

#### Embeddings with 3072 Dimensions

The impact of binary quantization on large embeddings is evident. While relevance may be slightly affected, the reduction in disk usage, search time, and indexing time is significant. Being able to store the same number of embeddings with just 15% of the space and index 6 times faster is a major achievement! It takes half as much disk space to store a million 3072-dimensional binary quantized embeddings than four million 1024-dimensional embeddings.

| Version                 | Recall @1 | Recall @20 | Recall @100 | Indexing time | Search time | On disk size |
|-------------------------|-----------|------------|-------------|---------------|-------------|--------------|
| Cosine                  | **1.00**  | **0.86**   | **0.92**    | 4000s         | 150s        | 26 GiB       |
| Binary Quantized Cosine | **1.00**  | 0.77       | 0.77        | **560s**      | **100s**    | **4 GiB**    |

### Conclusion

The impact of binary quantization on recall was expected to decrease, given the reduced information in the algorithm. However, for datasets with over 1500 dimensions, the impact on recall is relatively minor compared to the significant benefits in disk space and indexing speed.

In practice, we observed that space utilization decreased not by 32 times but by just 15% of the original space, a notable achievement. This is primarily due to arroy storing not only user vectors but also internal nodes for efficient searching. Split nodes (hyperplanes) are retained as full 32-bit floats to maintain precision.

- Indexing speed improves nearly 5 times with 1536 dimensions and about 7 times with 3072 dimensions.
- Disk size shrinks to around 6.5 times smaller.
- Search time shows slight improvements for embeddings starting at 1536 dimensions.

We recommend using Meilisearch/arroy's binary quantization feature for OpenAI users with large embeddings. In an upcoming article, we will compare Meilisearch/arroy with competitors, focusing on our Filtered DiskANN feature. Stay tuned!

Meilisearch indexes embeddings 7x faster with binary quantization

Meilisearch is too slow

_This is part 4 of a series of blog posts_ [_originally published on Clément Renault's blog_](https://blog.kerollmops.com/how-meilisearch-updates-a-millions-vector-embeddings-database-in-under-a-minute)_. Begin the journey with_ [_part 1_](/blog/spotify-inspired-hybrid-search-and-rust/)_,_ [_part 2_](/blog/refining-ann-performance-with-rust/)_ and_ [_part 3_](/blog/arroy-filtered-disk-ann/)_ This blog post considers that you’ve already read parts 1 and 2._

In this blog post, we’ll talk about how we implemented incremental indexing in [Arroy](https://github.com/meilisearch/arroy). By incremental, we mean that when inserting or deleting items in a tree, we can update only the required parts instead of rebuilding everything.

At Meilisearch, that’s essential because our users usually send updates regularly, and their content constantly changes. Rebuilding everything from scratch is very costly and won’t give a good experience; that’s why we already spent a lot of time on our latest release to make all the [data structures support incremental indexing](https://github.com/meilisearch/meiliSearch/releases/tag/v1.6.0) and arroy being one of them, we _HAD TO_ implement it as well!

The theory
----------

The following schema shows a high-level view of what should happen when adding and deleting documents into an existing tree.

As a reminder, arroy is a vector store based on [LMDB](http://www.lmdb.tech/doc/), an embedded transactional memory-mapped key-value store. It stores your vectors in trees composed of three kinds of nodes:

*   The split nodes - Store information on which item IDs are spread out between its left and right.
*   The descendants' nodes - Store multiple item IDs.
*   The items - A single vector.

For the following examples, we’ll consider the descendants node cannot contain **more** than two items and that the closer the IDs are, the closer the items are in space. For example, the item `1` is close to the item `2` but is farther from the item `10`.

![First step before inserting elements in the tree](https://unable-actionable-car.media.strapiapp.com/tamo_1_9ea29125b9.png)

Here, we’re trying to insert items `2` and `7` and delete items `3` and `11`.

Following what we do on the search, we split the items to insert between the left and right split nodes. But the deleted items are no longer present in the database! We don't have their associated vector, and therefore we'll need to iterate over all the leaves to find and delete them.

Fortunately, since we use roaring bitmaps, this list doesn't consume much memory, and since we never update it, we can share it with every thread without ever copying it 🎉

![Second step inserting element in the tree](https://unable-actionable-car.media.strapiapp.com/tamo_2_e4cd099c77.png)

Notice how the items to insert were balanced between the left and right split nodes. In the next step, we’ll follow the same process and split both lists of items to insert on the split node.

![Third step inserting into elements in the tree](https://unable-actionable-car.media.strapiapp.com/tamo_3_ab539d2465.png)

It’s on this step that all the good stuff happens. From the left to the right:

*   The first descendant node gets its item `3` removed, and item `2` added.
*   The second descendant node gets too big and must be replaced by a new split node.
*   The item `8` becomes a descendant containing both the items `7` and `8`.
*   After deleting item `10` in the last descendant node, we replace it with a direct link to an item to reduce the number of nodes in the tree (and improve search time by reducing the number of lookups).

![Last step inserting elements in the tree](https://unable-actionable-car.media.strapiapp.com/tamo_4_b07ebb4b8f.png)

Now that you’ve seen all the steps of our incremental indexing process, we’re still going to take a few notes on what happened:

*   In the first three steps, we had to read all of the tree nodes, which, by default, is equal to the total number of items in the database.
*   In the last step, we had to write four new tree nodes. Previously we would have rewritten the whole tree. The number of writes, which is the slowest operation in databases, is reduced to the bare minimum.
*   The process works on a single tree which means we can still multi-thread the computation of every tree.
*   The IDs aren’t sequential anymore, which doesn't play well with the ID generation strategy described in [Writing the tree in parallel](https://blog.kerollmops.com/multithreading-and-memory-mapping-refining-ann-performance-with-arroy).

How did we fix the ID generation?
---------------------------------

At the start of the indexing process, we need to gather all the existing tree IDs.  
The information we need to generate new nodes are:

*   The total number of tree nodes used to know when to stop building trees.
*   The « holes » in the used IDs that we want to re-use. This fragmentation is produced when we edit the trees.
*   The highest ID existing in the trees to generate the next new IDs.

![Selecting the next ID in the Roaring Bitmap](https://unable-actionable-car.media.strapiapp.com/tamo_5_1f7bb6a273.png)

The « simple » idea is to have a counter for the total number of tree nodes. A counter that we can increment to generate new fresh IDs. The most challenging part is to pick an available ID shared between threads and without big mutexes.

It took me quite some time to find a solution for this last point; I implemented a whole complex solution (150loc) that I ended up [rewriting entirely from scratch](https://github.com/meilisearch/arroy/pull/56/commits/0bf68e21cfd97ff00c7ef5a0ec116ba34c43c6a5) in one hour for an easy and more efficient solution. We're going to see all the ideas we went through before finding our final solution.

### Sharing an iterator over the available IDs

The first and most straightforward idea that comes to mind is to create and share an iterator over all the available IDs.

```rust
let mut available_ids = available_ids.into_iter();

roots.into_par_iter().for_each(|root| {
    // stuff
    let next_id = available_ids.next();
    // stuff
});
```

If you’re familiar with Rust, you’ll notice immediately that the `for_each` _cannot_ capture a mutable reference over the `available_ids` because we use the `into_par_iter` method from Rayon that execute the next methods on the iterator in a multi-threaded way. Which means we can't call `.next()`.

By using a mutex (short for [mutual exclusion](https://en.wikipedia.org/wiki/Mutual_exclusion)), we can make it compile:

```rust
let mut available_ids = Mutex::new(available_ids.into_iter());

roots.into_par_iter().for_each(|root| {
    // stuff
    let next_id = available_ids.lock().unwrap().next();
    // stuff
});
```

That is safe and will yield the right results, but won’t scale well as all the threads have to wait for each other on the lock.

### Let each thread own its list of IDs

When you need to remove a lock, a common solution is to split the work beforehand so each thread can work to its full capacity without ever having to know what’s happening on the other threads. That’s the solution [I implemented initially](https://github.com/meilisearch/arroy/pull/56/files/dc782ea61ef84f0ad8ad20e092476494d6eacc0c). The idea is to explode the roaring bitmap into as many smaller roaring bitmaps as there are trees to update.

The following function can split a roaring bitmap into `n` sub-bitmaps of equal size:

```rust
pub fn split_ids_in(available: RoaringBitmap, n: usize) -> Vec<RoaringBitmap> {
    // Define the number of elements per sub-bitmap
    let chunk_size = available.len() / n as u64;
    let mut ret = Vec::new();

    let mut iter = available.into_iter();
    for _ in 0..(n - 1) {
        // Create a roaring bitmap of `chunk_size` elements from the iterator without consuming it
        let available: RoaringBitmap = iter.by_ref().take(chunk_size as usize).collect();
        ret.push(available);
    }
    // the last element is going to contain everything remaining
    ret.extend(iter);

    ret
}
```

With this function available, it's then trivial to use one bitmap per tree to update with the [`zip`](https://docs.rs/rayon/latest/rayon/iter/trait.IndexedParallelIterator.html#method.zip) method on the parallel iterators of Rayon:

```rust
let available_ids = split_ids_in(available_ids, roots.len());

roots.into_par_iter().zip(available_ids).for_each(|(root, available_ids)| {
    let mut available_ids = available_ids.into_iter();
    // stuff
    let next_id = available_ids.next();
    // Here, we can use the available_ids without any locks or inter-thread synchronization
    // stuff
});
```

This works well while we're updating the already existing root trees. But later on, we may want to create new trees from scratch, and we can't know in advance how many new trees we’ll need to create. That's an issue because, without this information, we don't know how many sub-bitmaps we need to create.

At this point, I couldn’t see an easy fix to this problem, but I made the assumption that we rarely create a lot of new trees and that all new trees would use a lot of IDs. This means, giving all the IDs to the **first** new tree would _probably work out_ (it’s hard to be 100% sure without monitoring it in prod).

### The final solution

The previous solution was complex and did not even work perfectly. While I was scrolling through the documentation of the Roaring Bitmap, I saw [the `select` method](https://docs.rs/roaring/latest/roaring/bitmap/struct.RoaringBitmap.html#method.select) and immediately understood how I could make the initial approach works.

This method lets you get the values in your bitmap by index in an efficient way.  
For example, with the following values in a bitmap: `13, 14, 15, 98, 99, 100`:

*   `select(0)` returns `13`.
*   `select(3)` returns `98`.
*   `select(5)` returns `100`.
*   `select(6)` returns `None`.

With that in mind, if we share the bitmap with all threads in **read-only** and share the index in the bitmap as an atomic number, we can have multiple threads get available IDs at the same time with lock-free synchronization.

Once the `select` method returns `None`, it means we can stop picking IDs from the bitmap and instead simply generate new IDs from scratch with the old method.  
Even if it's super fast, calling the `select` method still takes some time, so once a thread gets a `None` returned from the method, we're going to update an atomic boolean telling us if there are still values to look at in the bitmap. If not, we can skip calling `select` and directly generate a new ID.

With that in mind, the cool `ConcurrentNodeIds` structure we showed you before in part 2 got a little bit more complex but it still let us generate IDs fairly without any locks!

```rust
/// A concurrent ID generator that will never return the same ID twice.
pub struct ConcurrentNodeIds {
    /// The current tree node ID we should use if no other IDs are available.
    current: AtomicU32,
    /// The total number of tree node IDs used.
    used: AtomicU64,

    /// A list of IDs to exhaust before picking IDs from `current`.
    available: RoaringBitmap,
    /// The current Nth ID to select in the bitmap.
    select_in_bitmap: AtomicU32,
    /// Tells if you should look in the roaring bitmap or if all the IDs are already exhausted.
    look_into_bitmap: AtomicBool,
}

impl ConcurrentNodeIds {
    /// Creates an ID generator returning unique IDs, avoiding the specified used IDs.
    pub fn new(used: RoaringBitmap) -> ConcurrentNodeIds {
        let last_id = used.max().map_or(0, |id| id + 1);
        let used_ids = used.len();
        let available = RoaringBitmap::from_sorted_iter(0..last_id).unwrap() - used;

        ConcurrentNodeIds {
            current: AtomicU32::new(last_id),
            used: AtomicU64::new(used_ids),
            select_in_bitmap: AtomicU32::new(0),
            look_into_bitmap: AtomicBool::new(!available.is_empty()),
            available,
        }
    }

    /// Returns a new unique ID and increases the count of IDs used.
    pub fn next(&self) -> Result<u32> {
        if self.look_into_bitmap.load(Ordering::Relaxed) {
            let current = self.select_in_bitmap.fetch_add(1, Ordering::Relaxed);
            match self.available.select(current) {
                Some(id) => Ok(id),
                None => {
                    self.look_into_bitmap.store(false, Ordering::Relaxed);
                    Ok(self.current.fetch_add(1, Ordering::Relaxed))
                }
            }
        } else {
            Ok(self.current.fetch_add(1, Ordering::Relaxed))
        }
    }
}
```

Performances in practice
------------------------

I haven’t run a lot of benchmarks yet (I would like to, though, and may update this post later), but on my benchmarks with a few hundred thousand items, here are the results I get:

![Performance improvement showed on a graph](https://unable-actionable-car.media.strapiapp.com/tamo_6_8c737d7e95.png)

*   On average, we get more than a 10x speedup after three batches of items indexed.
*   The little bumps we observe afterward that make us go from ~700ms to ~3s are due to the creation of new trees as the number of items increases.
*   I expect this benchmark to represent a worst-case scenario:
    *   All my item IDs are randomly generated, which means there are very few duplicates/updates but always new insertions and more writing.
    *   My vectors are also randomly generated with a uniform distribution, which means there shouldn’t be clusters as we observe in a real-life dataset.

This feature is now being used on production data with millions of documents, and we've seen numbers in the range of 9000 items added on a 2M items database in under a minute.

* * *

[Meilisearch](https://meilisearch.com/?ref=blog.meilisearch.com) is an open-source search engine enabling developers to build state-of-the-art experiences while enjoying simple, intuitive DX. 

For more things Meilisearch, you can join the community on [Discord](https://discord.gg/meilisearch/?ref=blog.meilisearch.com) or subscribe to the [newsletter](https://dub.sh/meili-newsletter). You can learn more about the product by checking out the [roadmap](https://roadmap.meilisearch.com/?ref=blog.meilisearch.com) and participating in [product discussions](https://github.com/orgs/meilisearch/discussions?ref=blog.meilisearch.com).

How Meilisearch updates a database with millions of vector embeddings in under a minute

_This is part 3 of a series of blog posts_ [_originally published on my personal blog_](https://blog.kerollmops.com/meilisearch-expands-search-power-with-arroy-s-filtered-disk-ann)_._ _Begin the journey with_ [_part 1_](/blog/spotify-inspired-hybrid-search-and-rust/) _and_ [_part 2_](/blog/refining-ann-performance-with-rust/)_._

We can store vectors in [Arroy](https://github.com/meilisearch/arroy) and efficiently compute the search tree nodes, but we still need some features to make it usable in Meilisearch. Our full-text search engine has great support for filtering; selecting subsets of documents is an essential feature to support. For instance, one of our biggest clients requires the ability to filter through over 100 million YouTube video metadata and their associated image embeddings to effectively select videos released within specific time frames, such as a single day or week. This represents the scalability and responsiveness challenges we aim to address with our filtering system, making it a perfect use case to tailor our developments.

Meilisearch supports the following operators on the filterable attributes of your documents: `<`, `<=`, `=`, `!=` `>=`, and `>`. Internally, we extensively [use `RoaringBitmap`s](https://github.com/RoaringBitmap/roaring-rs), which are well-optimized sets of integers that support fast binary operations like unions and intersections. When the engine receives a user request with filters, it first computes the subset of documents from the filter that will be inputted into the search algorithms, the one that ranks documents by quality. This subset is represented by a `RoaringBitmap`.

How was it working before Arroy?
--------------------------------

Ranking only the subset of filtered documents has been working well since 2018, but now that we have a new data structure to search on, we need to look at how to implement it. The engine had already supported the vector store feature for months but was inefficient. We were using an in-memory HNSW and were deserializing the whole data structure in memory, searching for the nearest neighbors of the target vector, which was returning an iterator.

```Rust
fn vector_store(db: Database, subset: &RoaringBitmap, target_vec: &[f32]) -> Vec<DocumentID> {
    // This takes a lot of time and memory.
    let hnsw = db.deserialize_hnsw();

    let mut output = Vec::new();
    for (vec_id, vec, dist) in hnsw.nearest_neighbors(target_vec) {
        let doc_id = db.document_associated_to_vec(vec_id).unwrap();
        if !output.contains(&doc_id) {
          output.push(doc_id);
          if output.len() == 20 { break }
        }
    }

    output
}
```

You may wonder why we are retrieving the document ID associated with the vector ID. Meilisearch supports multiple vectors by document since the beginning of the vector store feature. This is unfortunate because we must look up every vector we are iterating. We need to maintain this lookup table. The iterator can iterate on the whole vector dataset if the subset is small enough, e.g., `document.user_id = 32`. We want the document operations to be atomic and consistent, so we have to store the HNSW on disk and avoid having to maintain synchronization between the LMDB transactions and this vector store data structure. Ho! And the library doesn't support incremental insertion. We must reconstruct the HNSW in memory from scratch every time we insert a single vector.

Integrating Arroy in Meilisearch
--------------------------------

As we worked on updating Meilisearch to include the new vector store, arroy, we tried out mob programming for the first time. This is where we all code together at the same time. It might sound like it would slow us down, but it actually made us super productive! By tackling problems together right as they came up, we got arroy fitted into Meilisearch much faster than if we'd worked alone.

Arroy is different because it doesn’t return an iterator to give back search results. Now, our search engine is smarter and can figure out the exact number of results it needs to give back, even when there are filters to consider. This teamwork improved our search tool and showed us that working together is key when facing big tech challenges.

#### Filtering while searching in Arroy

You can find a description of the arroy internal data structure in [part 1 of this series](https://blog.kerollmops.com/spotify-inspired-elevating-meilisearch-with-hybrid-search-and-rust). Here is a list of the different kinds of nodes you can find:

*   The item nodes. The original vectors that the user provides. The small points on the left.
*   The normal nodes, also called split planes. They represent hyperplanes that split subsets of item nodes in half.
*   The descendant nodes. They are the tree leaves composed of the item IDs you'll find if you follow a certain normal node path.

![split-plane-combined-schema](https://unable-actionable-car.media.strapiapp.com/spli_plane_b53ab895e8.png)

A typical search will load all the normal nodes in a binary heap associated with an infinite distance. Remember that there are a lot of randomly generated trees, and there are, therefore, a lot of entry points. Ascending distances order the binary heap; the shortest nodes found will be popped first.

In the search algorithm, we pop the nearest item from this heap. If it's a normal node, we fetch the left and right sides of the hyperplane:

*   If we find normal nodes again, we associate the distance from the hyperplane with positive and negative distances from the targeted/queried vector.
*   If we find descendant nodes, we do not push them into the queue but rather directly add them to the potential output list as they represent the nearest vectors we have found.

You probably noticed where I want to go, but this is where magic happens. We modified arroy to store the list of descendants in `RoaringBitmap`s instead of a raw list of integers. This is another improvement compared to the original Spotify library, as those lists weigh less. Doing an intersection with the filtered subset is way easier now.

However, there is always an issue: the vector IDs are not the document IDs, and Meilisearch, after executing the filters, only knows about the documents. Iterating on the lookup table, I talked about before, constructing the final bitmap with all the vector IDs corresponding to the filtered documents would not be efficient when many documents are part of this subset, e.g., `document.user_id != 32`. I do not recommend using an `O(n)` algorithm in the search functions.

#### Using multiple indexes for efficient filtering

Fortunately, we developed a fun feature that wasn't meant to be used that way in arroy: the support for multiple indexes in a single LMDB database. We originally developed the multiple indexes feature to be able only to open a single LMDB database to store different vector types. Yes! In Meilisearch v1.6, you can describe the different embedders that live in a single index. You can identify the different vectors with different numbers of dimensions and distance functions you can store in a single document. Defining multiple vectors for a single document associated with the same embedder is also possible.

The indexes are identified by an `u16`. This feature can trick the algorithm into being even more efficient than the previous HNSW solution. Using one store by embedder and vector in a document is interesting because we can now identify the vectors using the document ID. No more lookup database and vector IDs. The vector IDs are reduced to the document IDs. We can use the output of the filters to filter the arroy indexes.

The search algorithm is different on the Meilisearch side. We request the nearest neighbors in every arroy index, sort the results by document ID to be able to deduplicate them and not return the same document multiple times, sort them again by distance, and then return only the top twenty documents. It may seem complex, but we are talking about twenty documents by the number of vectors for a single document. Usually, users will have a single vector.

```Rust
fn vector_search(
    rtxn: &RoTxn,
    database: Database,
    embedder_index: u8,
    limit: usize,
    candidates: &RoaringBitmap,
    target_vector: &[f32],
) -> Vec<(DocumentId, f32)> {
    // The index represents the embedder index shifted and
    // is later combined with the arroy index. There is an arroy
    // index by vector for a single embedded in a document.
    let index = (embedder_index as u16) << 8;
    let readers: Vec<_> = (0..=u8::MAX)
        .map(|k| index | (k as u16))
        .map_while(|index| arroy::Reader::open(rtxn, index, database).unwrap())
        .collect();

    let mut results = Vec::new();
    for reader in &readers {
        let nns = reader.nns_by_vector(rtxn, target_vector, limit, None, Some(candidates)).unwrap();
        results.extend(nns_by_vector);
    }

    // Documents can have multiple vectors. We store the different vectors
    // into different arroy indexes, we must make sure we don't find the nearest neighbors
    // vectors that correspond to the same document.
    results.sort_unstable_by_key(|(doc_id, _)| doc_id);
    results.dedup_by_key(|(doc_id, _)| doc_id);

    // Sort back the documents by distance
    results.sort_unstable_by_key(|(_, distance)| distance);
    results
}
```

The design philosophy behind these improvements
-----------------------------------------------

We're trying to make Meilisearch flexible enough for everyone's needs. Whether your documents are powered by a single embedding, like the kind OpenAI's nifty tools generate, or mixing it up with text and image embeddings, as many e-commerce sites do, we want your search experience to be seamless. We haven't forgotten you for the power users working with multiple embeddings from multi-modal embedders. Our latest improvements ensure that everyone gets to update and fine-tune their search indexes incrementally, making the whole process as smooth as butter.

Big thanks to everyone: Wrapping this up, a huge shout-out to the squad – [@dureuill](https://github.com/dureuill), [@irevoire](https://github.com/irevoire), and [@ManyTheFish](https://github.com/ManyTheFish) – for their genius and grunt work that brought our ideas to life. And watch out for [@irevoire](https://github.com/irevoire)'s upcoming article, where he'll explain how we've implemented incremental indexing in Arroy—meaning you can add new vectors without rebuilding everything from scratch. More on that soon!

You can comment about this article on [Lobste.rs](https://lobste.rs/s/hdokyh/meilisearch_expands_search_power_with), [Hacker News](https://news.ycombinator.com/), [the Rust Subreddit](https://www.reddit.com/r/rust/comments/18pqxdz/meilisearch_expands_search_power_with_arroys), or [X (formerly Twitter)](https://x.com/kerollmops/status/1738837058628551148?s=46&t=0s6OFYJM-Oyl_WD-1jijQA).

* * *

[Meilisearch](https://meilisearch.com/?ref=blog.meilisearch.com) is an open-source search engine that not only provides state-of-the-art experiences for end users but also a simple and intuitive developer experience.

For more things Meilisearch, you can join the community on [Discord](https://discord.gg/meilisearch/?ref=blog.meilisearch.com) or subscribe to the [newsletter](https://meilisearch.us2.list-manage.com/subscribe?u=27870f7b71c908a8b359599fb&id=79582d828e&ref=blog.meilisearch.com). You can learn more about the product by checking out the [roadmap](https://roadmap.meilisearch.com/?ref=blog.meilisearch.com) and participating in [product discussions](https://github.com/orgs/meilisearch/discussions?ref=blog.meilisearch.com).

Meilisearch expands search power with Arroy's Filtered Disk ANN

_This is part 2 of a series of blog posts_ [_originally published on my personal blog_](https://blog.kerollmops.com/multithreading-and-memory-mapping-refining-ann-performance-with-arroy)_. Begin the journey with_ [_part 1_](/blog/spotify-inspired-hybrid-search-and-rust/)_._

Wouldn't it be great to show you how a single-threaded, memory-mapped key-value store can be more efficient than a hand-written memory-mapped solution? I faced issues while porting the Spotify disk-based Approximate Nearest Neighbors library to Rust and, more specifically, to LMDB. Those issues were primarily due to LMDB and memory safety. Here is the story.

To remind you, [Arroy](https://github.com/meilisearch/arroy) is a library that stores embeddings (vectors of floats) on disk. Some data structures are generated on top of those vectors, which look like trees governed by normals used to recursively split the vectors dataset into subdomains. But you can read more about this in [part 1](/blog/spotify-inspired-hybrid-search-and-rust/ of this series.

### How does Annoy generate the tree nodes?

Annoy, the Spotify library stores the nodes on disk, the item nodes (the ones containing the embeddings), and the other nodes that we will call tree nodes in this article. The advantage of doing this is double:

*   The program's memory usage is low and optimized by the OS as all the nodes live in a memory-mapped file.
*   The concept is simple: Access a node by using its ID. The library will find its offset on disk by using a simple multiplication.

However, there are downsides to doing that. All nodes: items with embeddings along with the tree nodes must have the same size, and If a user wants to identify its embedding using the ID 231, the library will increase the file size to the ID multiplied by the node size. For example, with a vector of 768 dimensions, storing a single item with the ID 231 will generate a file of more than 6.5 TiB.

In generating the final data structure, the tree nodes are all written to disk in the same file as the user item containing the embeddings. Those tree-building processes run in parallel, one running process by tree, and, therefore, requires a lot of synchronization when defining the newly created node ID and the memory area reserved for it, most importantly, when the memory-mapped file is too small to accept more nodes, only a single thread must grow the file, so a mutex is used on top of the mutable memory-map and around a `node_id` variable. One interesting property of tree generation is that the generation process only requires the original user item with embeddings.

### The challenges we encountered when porting it to LMDB

A fun fact is that it is the first time in a long time that I have written C++, and the first time I asked ChatGPT to code for me because I was not confident in doing C++ and feared falling into some segfault. I needed a small program to deserialize embeddings from stdin and give them to Annoy. The chatbot's code was mostly effective, but it omitted a critical [empty vector check](https://gist.github.com/Kerollmops/d0e434016b1a698ec9bdbd86d268885e#file-par_build_tree-cpp-L74), which led to a segmentation fault...

The main obstacle to porting it to LMDB is that writing into this key-value store is single-threaded. It doesn't support concurrent write operations to maintain a correctly balanced BTree. Fun incoming!

#### Reading the user item nodes from different threads

We have used LMDB at Meilisearch since the beginning. It is a well-maintained key-value store used in Firefox and maintained by the OpenLDAP developers. It is memory-mapped and does not maintain a user-end cache of the entries in memory but instead gives you a pointer to the memory-mapped area on disk. The main advantage is that you can keep a pointer to this area for as long as your read transaction lives. Ho yeah! Because it is a transactional key-value store that supports atomic committing, too!

But tree generation doesn't require referring to the generated nodes but only the user items. We previously saw that LMDB gives direct pointers into the memory-mapped file without maintaining any intermediate cache (that could be invalidated). There is another quirk with LMDB: you cannot share a read-only transaction between multiple threads, i.e., `RoTxn: !Sync` and you cannot move the write transaction between threads, i.e., `RwTxn: !Send + !Sync`. Ho! And there is no way to create a read-transaction on uncommitted changes. This is an issue because we want to generate the data-structures trees in the same transaction where we store the items.

But magic is everywhere, starting with the following small and fun data structure. The principle is to keep the pointers to the internal user items with embeddings in a `Vec<*const u8>`. Thanks to Rust, we can ensure, at compile time, that the pointers will live long enough by keeping the lifetime in the struct. Using the `&'t RwTxn` to get the `&'t RoTxn` by using `Deref` also ensures that we cannot modify the database while reading in it by using a `&'t mut RwTxn`. [According to the leading developer of LMDB](https://bugs.openldap.org/show_bug.cgi?id=10138#c9), it is safe to share those pointers between threads and why I implemented `Sync` for this structure.

```Rust
pub struct ImmutableItems<'t, D> {
    item_ids: RoaringBitmap,
    constant_length: Option<usize>,
    offsets: Vec<*const u8>,
    _marker: marker::PhantomData<(&'t (), D)>,
}

impl<'t, D: Distance> ImmutableItems<'t, D> {
    pub fn new(rtxn: &'t RoTxn, database: Database<D>, index: u16) -> heed::Result<Self> {
        let mut item_ids = RoaringBitmap::new();
        let mut constant_length = None;
        let mut offsets = Vec::new();

        for result in database.items()? {
            let (item_id, bytes) = result?;
            assert_eq!(*constant_length.get_or_insert(bytes.len()), bytes.len());
            item_ids.push(item_id);
            offsets.push(bytes.as_ptr());
        }

        Ok(ImmutableLeafs { item_ids, constant_length, offsets, _marker: marker::PhantomData })
    }

    pub fn get(&self, item_id: ItemId) -> heed::Result<Option<Leaf<'t, D>>> {
        let len = match self.constant_length {
            Some(len) => len,
            None => return Ok(None),
        };
        let ptr = match self.item_ids.rank(item_id).checked_sub(1).and_then(|offset| self.offsets.get(offset)) {
            Some(ptr) => *ptr,
            None => return Ok(None),
        };
        let bytes = unsafe { slice::from_raw_parts(ptr, len) };
        ItemCodec::bytes_decode(bytes).map(Some)
    }
}

unsafe impl<D> Sync for ImmutableItems<'_, D> {}
```

You have also probably noticed some other fun optimizations in this simplified version of the data structure. We also know that the user-item nodes have a constant length, so I decided to store it only once, reducing the offsets vector's size by two. Considering that our objective is to store 100M vectors and that this vector is in memory, we shrunk its size from 1526 MiB to 763MiB, which is not much, but better than nothing.

#### Writing the tree nodes in parallel

Ok! Now that we know how to store pointers to items and share them between threads without any user-end synchronization, we need to generate the tree nodes using it. We already know how to deal with LMDB at Meilisearch and decided to implement the same workaround. To write in parallel into LMDB, write into different, independent files and merge everything afterward. This leverages the [Share-Nothing principle](https://en.wikipedia.org/wiki/Shared-nothing_architecture) and isolates the algorithms. This drastically reduces the number of synchronization points [compared to the original C++ code](https://github.com/spotify/annoy/blob/2be37c9e015544be2cf60c431f0cccc076151a2d/src/annoylib.h#L1344-L1445) (look at the `.lock/unlock` calls) to a single line in our code: the atomically increasing global tree node ID.

```Rust
pub fn next_node_id(&self) -> u64 {
    self.0.fetch_add(1, Ordering::Relaxed)
}
```

Our functions that generate normal split nodes based on the user-item nodes are now simply writing the nodes into independent files. The [nodes are appended into a file](https://github.com/meilisearch/arroy/blob/4f193fd534acd357b65bfe9eec4b3fed8ece2007/src/parallel.rs#L20-L71), and the on-disk offsets and bounds are stored into a vector, a single `usize` by node. Using Rayon, we run all tree-generation functions in parallel and, once completed, retrieve the files and boundaries to write the uniquely identified nodes into LMDB sequentially.

### Performances comparison

Our objective at Meilisearch is to support 100M embedding of around 768 dimensions. If we store those as `f32` vectors without any [dimensionality reduction](https://en.wikipedia.org/wiki/Dimensionality_reduction), it would be equivalent to `100M * 768 * 4 = 307B`, in other words, 286 GiB to store the vectors raw, without any internal tree nodes, i.e., no way to search in them efficiently.

If you don't specify the number of trees to generate, the algorithm will continue to create trees while the number of tree nodes is smaller than the number of item vectors. At the end, there must be roughly the same number of tree nodes and items.

#### Discovering the limit of vectors we can index

Arroy and Annoy use memory mapping extensively but in slightly different ways. In a previous article from [@dureuill](https://github.com/dureuill), we saw that [operating systems do not have infinite memory-map space](/blog/dynamic-virtual-address-management/ So, let's dive into performance results.

I noticed something strange when running Arroy with 25M vectors of 768 dimensions. The CPUs were not used, and the program seemed to read the SSD/NVMe a lot, too much 🤔 The tree generation algorithm is splitting the vector space into subdomains with fewer vectors. Still, it must first find the appropriate normal to split the entire domain, and for that, it randomly selects many items. Unfortunately, my machine only has 63 GiB of memory, and indexing those 25M items requires more than 72 Gib. Annoy was also struggling in the same way.

![We cannot index 25M vectors of 768 dimensions with 63 GiB](https://unable-actionable-car.media.strapiapp.com/annoy_arroy_e83f58691c.png)

After investigating, I understood why the whole swap space and memory mapping limits were reached. Not only the item nodes were not only _768 \* 4 bytes_ because we store the norm and other stuff alongside the vectors, but in the case of Arroy, LMDB needs to maintain BTree data structures around the entries, and those are also tacking memory-mapped space. Both programs request random item nodes unavailable in memory, so the OS fetches them from the disk, which takes time. Ho and every single thread is doing that in parallel. CPUs are simply awaiting the disk.

So, after some dichotomy, I found the point where arroy successfully used all of the memory without being bound to the disk speed. It can index 15.625M on a 63 GiB machine. You can see on this htop screenshot that the disk read speed is at zero as all of the vectors fit in RAM, that arroy is writing the tree nodes to disk, and that the CPUs are doing their best. It took less than seven hours to process.

![Successfully indexing 15.6M vector of 768 dimensions with 63 GiB](https://unable-actionable-car.media.strapiapp.com/annoy_arroy2_a873d31d2d.png)

But... Annoy cannot index this same number of documents. It suffers from the same issue we saw before: high disk read and low CPU usage. But why? I needed clarification because the nodes have the same format, the number of item vectors to index is the same, and the algorithm has been ported. So, what is the difference between both solutions?

For those who looked into the C++ codebase and were probably hinted by the memory mapping issue described earlier, you probably noticed this slight difference: Arroy is writing the generated tree nodes into different raw files when Annoy, on the contrary, is [reserving space into the memory-mapped file and directly writing into it](https://github.com/spotify/annoy/blob/2be37c9e015544be2cf60c431f0cccc076151a2d/src/annoylib.h#L1354-L1370). By doing this trick, the OS needs to keep much more space in the memory-mapped area and is forced to invalidate the item nodes from the cache to keep the just-written tree nodes hot in the cache, slowing down the system for no reason, as the tree nodes are not necessary for the algorithm.

So, after even more dichotomy to find the Annoy limits on a 63 GiB machine, I discovered that it could roughly index 10M vectors in five hours.

#### The share nothing principle to the win

So Arroy can index 36% more vectors on the same machine, but how long does it take? Wouldn't it be faster to write into the same file in parallel instead of copying all those tree nodes in a single-threaded way? It will be a much shorter paragraph as I only did some small tests, but Arroy is always faster!

|  | number of vectors | number of threads | building time |
| --- | --- | --- | --- |
| Annoy | 96k | 1 | 5min 38s |
| arroy | 96k | 1 | **3min 45s** |
| Annoy | 96k | 12 | 1min 9s |
| arroy | 96k | 12 | **54s** |
| Annoy | 10M | 12 | 5h 40min |
| arroy | 10M | 12 | **4h 17min** |
| Annoy | 15.625M | 12 | \-- |
| arroy | 15.625M | 12 | **7h 22min** |

Now, you probably tell me that I will need around 400GiB of memory to index 100M vectors, and you are probably right, but [@irevoire](https://github.com/irevoire) will talk about incremental indexing in a future article. I did a linear regression for fun. With those 12 threads and the required memory, I predicted it would take one day, 22 hours, and 43 min 😬. Ho! As we also use this vector store in Meilisearch, we need to provide ways to filter this data structure at search time. This is the next article in this series.

You can comment about this article on [Lobste.rs](https://lobste.rs/s/87aheu/multithreading_memory_mapping_refining), [Hacker News](https://news.ycombinator.com/), [the Rust Subreddit](https://old.reddit.com/r/rust/comments/18jmuoe/multithreading_and_memorymapping_refining_ann), or [X (formerly Twitter)](https://x.com/Kerollmops/status/1735941213516140814).

[Part 3](/blog/arroy-filtered-disk-ann/) of this series is now available, exploring further advancements in our search with Arroy's Filtered Disk ANN.

* * *

[Meilisearch](https://meilisearch.com/?ref=blog.meilisearch.com) is an open-source search engine that not only provides state-of-the-art experiences for end users but also a simple and intuitive developer experience.

For more things Meilisearch, you can join the community on [Discord](https://discord.gg/meilisearch/?ref=blog.meilisearch.com) or subscribe to the [newsletter](https://meilisearch.us2.list-manage.com/subscribe?u=27870f7b71c908a8b359599fb&id=79582d828e&ref=blog.meilisearch.com). You can learn more about the product by checking out the [roadmap](https://roadmap.meilisearch.com/?ref=blog.meilisearch.com) and participating in [product discussions](https://github.com/orgs/meilisearch/discussions).

Multithreading and Memory-Mapping: Refining ANN performance with Arroy

_This is part 1 of a series of blog posts_ [_originally published on my personal blog_](https://blog.kerollmops.com/spotify-inspired-elevating-meilisearch-with-hybrid-search-and-rust)_._

Uniting keyword and semantic search
-----------------------------------

At Meilisearch [we are working hard on hybrid search](https://github.com/meilisearch/meilisearch/issues/3838), mixing the widespread keyword search algorithm with the not-so-common semantic search. The former is very good at exact matching, while the latter finds stuff you can _describe_ better.

I will explain why we even talk about [Meilisearch/arroy](https://github.com/meilisearch/arroy) and why it is important to us. The semantic search was something new to us. The principle is quite simple: documents are associated with vectors (lists of floats), and the closer they are to each other, the closer they are semantically. When a user queries the engine, you compute the embeddings (vectors) of the query and do an approximate nearest neighbor search to get the nth closest items to the user query. Fun fact: after all this time, Annoy [is still among the top competitors](https://ann-benchmarks.com/gist-960-euclidean_10_euclidean.html), so imagine when we will finally release Arroy.

Seems simple, right? Do you **really** think this series of blog posts will talk about a dead simple subject? Join us on a journey as [@irevoire](https://github.com/irevoire) and I ([@Kerollmops](https://github.com/Kerollmops)), with the assistance of [@dureuill](https://github.com/dureuill), work on porting this cutting-edge library to Rust.

Optimizing storage and search for high-dimension embeddings
-----------------------------------------------------------

The embeddings are something between 768 and 1536 dimensions. We have customers at Meilisearch who want to store over 100M of them. Embeddings that were not modified by any dimension reduction algorithm use 32-bit floats. This means storing this data will take between 286 GiB and 572 GiB, depending on the dimensions.

[Yes, it fits in RAM](https://yourdatafitsinram.net/), but at what cost? Storing on disk is much cheaper. Ho! And it is only the raw vectors. I assure you that doing an approximate neighbors search among all vectors in `O(n)` will be quite slow. So we decided to store them on disk. We have looked at many different solutions before choosing Spotify/Annoy. Initially, we used the HNSW from instant-distance Rust crate, another data structure, to do an ANNs (approximate nearest neighbors) search. However, it is not disk-based; everything lives in memory, which is unpractical.

Spotify's hyperplan trees for efficient ANNs
--------------------------------------------

Spotify worked on a cool C++ library to search in enormous vector sets. The algorithm generates multiple trees that refer to the vectors. The tree nodes are random hyperplanes that split subsets of vectors in half. The root node splits the whole set of vectors in half, and the left and right branches split the subsets of vectors recursively again until the subset is small enough. When we perform an ANNs search, we go through all the root trees and decide whether to go on the hyperplanes' left or right, depending on the haystack provided. The advantage is that every node and vector is directly stored in a memory-mapped file.

![Hyperplanes mapped to binary trees](https://unable-actionable-car.media.strapiapp.com/blog_arroy_1_76462ae24c.png)

The way Annoy and Arroy generate hyperplanes to split the vector space

At the end of the tree, we can see the descendants' nodes. Those define the final list of leaf vectors that fit on this side of the recursive split nodes above. It is a list of unsigned integers the user provides. Annoy represents them as slices of `u32`s, but we decided to go [with RoaringBitmaps](https://roaringbitmap.org/about/) to reduce their size. Annoy cannot compress them because they have a fun constraint: All nodes, user leaf vectors, split nodes, and descendants must be the same size to be accessible using offsets on disk.

The above image shows the way a split plane can be represented. A hyperplane splits a subset of nodes here in two dimensions, but imagine that with 768 to 1536 dimensions. Each hyperplane creates two subsets of points recursively split by another hyperplane. Once the number of points to split is small enough, we create a descendants node containing the item IDs corresponding to these points. Furthermore, the embeddings of the points are never duplicated in memory; we refer to them by their IDs.

Adapting Annoy to LMDB
----------------------

So, if it works so well, why must we port it to Rust? One, because I follow the _Rewrite it in Rust_ dogma 😛, two because this is a C++ library with a lot of horrifying hacks and undefined behaviors, and three because Meilisearch is based on LMDB, an atomic, transaction-based, memory-mapped key-value store. Moreover, [since 2015, they have wanted to use LMDB](https://github.com/spotify/annoy/issues/96), but they have yet to achieve it; it requires a lot of time to change the data structures accordingly.

LMDB uses a BTree to order the entries, and it takes more space for the intermediate data structures than annoy, which directly identifies vectors using the offset in the file. Another advantage of using this key-value store is managing incremental updates. It is easier to insert and remove vectors. Suppose you insert a vector identified by a high 32-bit integer in Annoy. In that case, it will allocate a lot of memory to store it as the dedicated offset, increasing the file size if necessary.

In Meilisearch and Arroy, [we use heed, a typed LMDB Rust wrapper](https://github.com/meilisearch/heed), to avoid undefined behavior, bugs, and stuff related to C/C++ libraries. We, therefore, use `&mut` and `&` extensively to be sure that we are not modifying the key-value store entries while keeping references inside it, and we make sure that the read-write transactions can't be referenced or sent between threads. But that will be for another story.

We first thought using this key-value store would make Arroy slower than Annoy. However, LMDB writes its pages in memory before writing them to disk, which seems much faster than directly writing into mutable memory-mapped areas. On the other hand, LMDB doesn't guarantee the memory alignment of the values that Annoy's file format permits; we'll talk about that later.

Optimizing vector handling with SIMD
------------------------------------

The most CPU-intensive task that Arroy was supposed to do was to try to split clouds of vectors in half. This requires computing a massive number of distances in hot loops. But we read the embeddings from a memory-mapped disk. What could go wrong?

```rust
fn align_floats(unaligned_bytes: &[u8]) -> Vec<f32> {
    let count = unaligned_bytes.len() / mem::size_of::<f32>();
    let mut floats = vec![f32::NAN; count];
    cast_slice_mut(&mut floats).copy_from_slice(unaligned_bytes);
    floats
}
```

We used Instrument on macOS to profile our program and discovered a lot of time was spent moving stuff around, i.e., `_platform_memmove`. The reason is that reading unaligned floats from disk is undefined behavior, so we were copying our floats into an aligned memory area as shown above. Cost: An allocation by reading plus a calling `memmove`.

![Profiling showing a big memmove usage](https://unable-actionable-car.media.strapiapp.com/blog_arroy_2_c34c821b3c.png)

Profiling shows a lot of memory copies to align bytes

While porting the distance function from C++ to Rust, we used the Qdrant SIMD-optimized distance functions without modifying them beforehand. Although, [being aware of the performance cost of reading unaligned memory](https://dwrensha.github.io/capnproto-rust/2020/01/11/unaligned-memory-access), we decided to execute the distance functions on unaligned floats, making sure not to represent it as a `&[f32]` as it would be undefined behavior. The functions take raw slices of bytes and deal with them using pointers and SIMD functions. We unlocked performances. The distances functions were slower, but it compensated the `memmove`s and allocations!

![Profiling showing no memmove usage](https://unable-actionable-car.media.strapiapp.com/blog_arroy_3_519276495b.png)

Directly dealing with unaligned memory removed the copies

Similarly to the `memmove` calls, we can see that the `_platform_memcmp` function is taking a lot of space here. The reason is that LMDB uses this standard function to compare key bytes and decide whether a key is lexicographically located above or below another key in the tree. It is used whenever we read or write in LMDB. [@irevoire](https://github.com/irevoire) drastically reduced the size of the keys and saw an important gain in performance. We further tried using the `MDB_INTEGERKEY`, which makes LMDB compare memory using the computer endianness, but it was complex to use and not showing significant performance gains.

Upcoming challenges
-------------------

While porting this cool algorithm to Rust and LMDB, we were missing one of the most important features: Multithreading the tree building. The main reason for this missing feature is LMDB, which does not support concurrent writes to disk. It is part of the beauty of this library; writing is deterministic. We already know LMDB very well, and we will explain how we leveraged the power of LMDB in part 2 of this series and how we beat the Spotify library.

In addition to equalizing the current Annoy features, we needed more for Meilisearch. We implemented [Microsoft's Filtered-DiskANN feature](https://harsha-simhadri.org/pubs/Filtered-DiskANN23.pdf) in Arroy. By providing the subset of item IDs we want to retrieve, we avoid searching the whole trees to fetch the approximate nearest neighbors. We will talk about this in a soon-to-be-released article.

In Meilisearch v1.6, we've optimized performance for updating only document parts, as with vote counts or view numbers. The described single-threaded version of Arroy constructs tree nodes anew for each vector adjustment. [@irevoire](https://github.com/irevoire) will explore Arroy's incremental indexing in his next article, a capability not offered by Annoy.

You can comment about this article on [Lobste.rs](https://lobste.rs/s/4pw9kf/spotify_inspired_elevating_meilisearch), [Hacker News](https://news.ycombinator.com/), [the Rust Subreddit](https://old.reddit.com/r/rust/comments/18dq493/spotifyinspired_elevating_meilisearch_with_hybrid), or [X (formerly Twitter)](https://twitter.com/Kerollmops/status/1733158652444369286).

[Part 2](/blog/refining-ann-performance-with-rust/ and [part 3](/blog/arroy-filtered-disk-ann/ of this series are now available, exploring further advancements in ANN algorithms with Rust.

* * *

[Meilisearch](https://meilisearch.com/?ref=blog.meilisearch.com) is an open-source search engine that not only provides state-of-the-art experiences for end users but also a simple and intuitive developer experience.

For more things Meilisearch, you can join the community on [Discord](https://discord.gg/meilisearch/?ref=blog.meilisearch.com) or subscribe to the [newsletter](https://meilisearch.us2.list-manage.com/subscribe?u=27870f7b71c908a8b359599fb&id=79582d828e&ref=blog.meilisearch.com). You can learn more about the product by checking out the [roadmap](https://roadmap.meilisearch.com/?ref=blog.meilisearch.com) and participating in [product discussions](https://github.com/orgs/meilisearch/discussions).

Meilisearch latest news and company updates