Still too slow when there is not enough RAM

[irevoire]

We made a huge rework of the arroy architecture to allow us to index large dataset with little RAM, but it's still not enough.

Context

A bit of context on why we did all that and the way we did it, then we'll see the issue I'm still encountering.

Before

What we were doing was basically:

1. Get the pointer to all the vectors in a memory-mapped region that won't change during the whole indexing process
2. Every time we update or create a node, we instead write it to a temporary file that will be written to the database at the end of the indexing process
3. Insert the new elements in the current tree; each thread can work on its own tree in parallel
   1. If a descendant becomes too big in the process, we split it and create a new sub-tree from here
   2. We have to scan the whole database to remove the deleted elements
4. If we need more trees, we can build them in parallel at the tree level
5. We retrieve all the temporary files and write them to the database

When the whole database doesn't fit in RAM that process causes a few issues:

• During 3, to know if an item must go to the left or right of a split node, we have to compare it against the normal of that node, which means we have to load all the items in RAM and compare them against the split node. If the items don't fit in RAM, that's an issue because for each split node, we're going to read on disk, and that's worth it because it's done in parallel with all cores.
• During 3.1, the issue is exacerbated because even if all the "new items to insert" fit in RAM, we're now pulling new random vectors from the database and using them to create split nodes, which generates a ton of random reads as well
• Finally, during 4, even if it happens less often than the rest, we're reading the whole database at once

Now

Our new strategy to avoid all these issues works like this:

1. Get the pointer to all the vectors in a memory-mapped region that won't change during the whole indexing process
2. Same as before, when we have to write something, we write it to a temporary file that will be written to the database at the end of the indexing
3. First we want to insert the new elements in the current trees:
   1. Compute ahead of time how many vectors fit in RAM and retrieve their ptr
   2. Insert them in the tree. We have to compare them against the normal as before, but now, since everything fits in RAM, they should only be read once. Multiple threads can do this work in parallel for all the trees.
   3. When a leaf becomes too large and must be split into a subtree, we store all the IDs it contains in RAM and don't split it now.
   4. Come back to 1 until there are no vectors left
4. We now have a list of leaves that are too large and must be exploded into a subtree
5. For each missing tree, we add a new leaf to this list that contains the IDs of the whole database
6. At this point, we won't ever read a tree node again from the database
7. We explode the leaves to create all the subtrees required
   1. Each thread pops one large leaf and does the step 3 on it.
   2. Then it iterates over the list of leaves generated, the ones that are too large are pushed again in the list of large leaves and will be processed by this thread or another
8. We retrieve all the temporary files and write them to the database

Most of the work was finished in #130, where I parallelized the code, and a few bug fixes were done afterwards.

The issue

When the size of the database exceeds the RAM, we're once again doing a ton of random reads and nothing else.
Here's what it looks like:

• The RAM increases by a few megabytes, and then we start swapping 2 GiB of RAM and spending 99% of our time on IO wait
• During this time, we're barely writing anything to the disk, just reading and refreshing our pages over and over again

It's kinda expected that we have to do a lot of random reads on the disk. But here it's at a level where absolutely nothing makes any progress

[irevoire]

Even though that makes the issue even worse by reducing our RAM even more and forcing more reads, I was starting to suspect the kernel to be the one throwing away hot pages for no reason, so just to see what would happen, I used a large buffer to store the vectors that fits in RAM and ensure the kernel would not flush them away, and I noticed something funny:
Sometimes the throughput of the disk gets really slow: 2025-06-19T16:20:24.782127Z WARN ThreadId(03) arroy::writer: [BEFORE BUILDING THE TREE] filling the bump with vectors took: 11.28s. It contains 1534 items, has a capacity of 5242880
Here I had only two threads running and filling a vector with a capacity of 5MiB took 11.28s, that means the disk had a throughput of 0.44MiB/s.
Any random SSD nowadays is at least 100 times better, with a throughput of 50MiB/s, and a good SSD should reach about 4GiB/s in random read.

We can clearly see it when profiling the program, 99% of the time is spent doing page fault:

The issue here is that we're running on a high-end network disk, and it has huuuuge latency.
But it doesn't mean it has a terrible throughput; they advertise it as if it has 1GiB/s of throughput (probably way less on random read, but we can at least target a good 50MiB/s).

---

So, my strategy is to batch the read by having way more threads running at the same time.
With 40 threads doing smaller reads together, we can see that most of them synchronize while stuck on read:

Here, since I increased the quantity of threads drastically, it means each thread only has 18.75MiB (19660800B) of RAM available for themselves.
Also, I'm using half of the RAM in actual allocation, so that only leaves the other half of the RAM for the memory map, which in turn has to refresh its page more often.
But still, now the threads are still stuck for about 15s, a bit slower than before, except there are 40 of them, which gives me a throughput of roughly 50MiB/s, yay that's what I was expecting 🎉

---

Another issue with this experiment is that I also noticed that rayon was becoming extremely slow from time to time.
Most of the time, inserting a new task takes between 30ms and 500ms.
But sometimes I saw it jump to literal dozens of seconds (and I only had 8 threads on this screenshot)

Since all my threads are being synchronized by the slow read, maybe there is a huge lock contention on rayon at the time of creating the new task?

---

What I'm wondering now is: Is there a way, in a sync program, of prefetching memory-mapped data that fits in RAM instead of allocating everything in RAM twice + having a ton of threads that increase the amounts of work I have to do 🤔

[irevoire]

What I'm wondering now is: Is there a way, in a sync program, of prefetching memory-mapped data that fits in RAM instead of allocating everything in RAM twice + having a ton of threads that increase the amounts of work I have to do 🤔

So, quickly after writing this message I discovered madvise. I updated my code and ran the benchmarks again and although it seems like we're reading a lot more data (not even sure because I removed bumpalo and cannot really measure reading time) it didn't solve the issue at all.
All the charts stay the same:

A tons of read and nothing is making any progress 😩

---

Another idea I had was that maybe when the quantity of ram was getting smaller we were reading each items significantly more.
So, I put a counter every time we access an item. By that, I mean the vector is used in a comparison:

• When creating the trees in two_means
• And when remaining item in a tree

Then I started indexing 100_000 vectors with different amounts of RAM and that's the result:

• with unlimited RAM: read count: 22_995
• with 750MiB: read count: 19_046
• with 250MiB: read count: 19_876
• with 125MiB: read count: 18_461
• with 50MiB: read count: 17_881
• with bare minimum: read count: 18_143

Basically, it seems like the amount of RAM you have is pretty much insignificant compared to the number of reads you do on the vectors. That's not what I was expecting.

Maybe I cannot just check one item and should count all reads and then divide that by the total number of items to get a better average.

[irevoire]

Maybe I cannot just check one item and should count all reads and then divide that by the total number of items to get a better average.

I did that, but it didn't drastically change the quantity of "read" we are doing:

After a bit more investigation, I understand why we observe that behavior!

• with unlimited RAM:

2025-06-22T09:29:22.804542Z  WARN main ThreadId(01) arroy::writer: read count: 64_553_166
2025-06-22T09:29:22.804558Z  WARN main ThreadId(01) arroy::writer: total page read: 64_553_166
2025-06-22T09:29:22.804560Z  WARN main ThreadId(01) arroy::writer: average read per vector: 645
2025-06-22T09:29:22.804562Z  WARN main ThreadId(01) arroy::writer: total split attempts: 15_168
2025-06-22T09:29:22.804563Z  WARN main ThreadId(01) arroy::writer: total split nodes: 8_050
2025-06-22T09:29:22.804565Z  WARN main ThreadId(01) arroy::writer: split failure: 7_118

• with 1KiB of RAM:

2025-06-22T09:38:26.807583Z  WARN main ThreadId(01) arroy::writer: read count: 41_760_263
2025-06-22T09:38:26.807598Z  WARN main ThreadId(01) arroy::writer: total page read: 41_760_263
2025-06-22T09:38:26.807600Z  WARN main ThreadId(01) arroy::writer: average read per vector: 417
2025-06-22T09:38:26.807602Z  WARN main ThreadId(01) arroy::writer: total split attempts: 15_122
2025-06-22T09:38:26.807603Z  WARN main ThreadId(01) arroy::writer: total split nodes: 8_149
2025-06-22T09:38:26.807605Z  WARN main ThreadId(01) arroy::writer: split failure: 6_973

The more RAM we have and the more chance of failing a split we have. Plus, when we fail a split with a lot of elements in RAM we have to read them all again.
That means, the more RAM we have, the slower the indexing process, BUT the better the tree and the faster the searches!
Also, this "issue" could be improved a lot with a better split generation.
But anyway, that means it's not my main issue.

---

Something misleading with the logs above is that I wrote total page read: 41_760_263, that's interesting, but we don't know where the pages are loaded from, and can't really make much of this number.

[irevoire]

With Bumpalo, it's easy to count the actual number of vectors I'm pulling from the disk into my buffer before working, so I did that and here is the quantity of bytes I had to pull from the disk to index a few vectors:

bytes to read: [7.62939 GiB, 794.009 GiB, 13.8037 TiB]
vectors      : [1000, 10000, 100_000]
Time to index with a 30MiB/s throughput:
["4 minutes + 20.417 seconds", "7 hours + 31 minutes + 42.163 seconds", "5 days + 14 hours + 1 minute + 15.331 seconds"]
Time to index with a 100MiB/s throughput:
["1 minute + 18.125 seconds", "2 hours + 15 minutes + 30.649 seconds", "1 day + 16 hours + 12 minutes + 22.599 seconds"]

Here I got these numbers by considering I had absolutely no RAM, so it's the worst-case scenario, but we see that it increases exponentially, which is no good 😬
Theoretically, we're supposed to reach about 100MiB/s, but in practice, since arroy and LMDB force us to do a lot of random reads that never happen, we're way closer to 30MiB/s than 100.
And that also doesn't take into account all the CPU time, but it seems negligible considering how large these numbers are.

---

What are the next steps now that we have understood the issue was deep within the arroy algorithm itself?

• See if the work we did had any good impact on datasets that almost fit in RAM, maybe it's still worth it to release this code
• We could try to reduce the number of write by doing better/smaller splits, reducing the number of trees, and quantizing the data without losing as much relevancy
• See how other competitors do on a similar setup, today, as far as I know, only Qdrant and diskANN are supposed to work on a limited machine