Skip to content
Replai Let’s talk
Menu
Your system asks for reduced motion, so the figures show their key frames instead of playing.

Add, Delete, Rebuild, Replai

You ship semantic search over your help center in twenty lines. It works. Then the docs start changing.

By Dolev Ben Aharon, Founding Engineer

One support-docs assistant, seven acts · Flat vs IVF · measured on FAISS · 2026

An array of vectors drawn as a strip of cells. New rows drop in at the tail. Random rows turn into hatched tombstones. Every twelve seconds a sweep passes left to right, the tombstones vanish, the survivors slide left and the tail shrinks. Click a live cell to delete it.

Prologue · why we ran these numbers

At our size, reads and writes both cost

This post is about read and write operations on a very large vector database. We handle tens of millions of lines of code. We run many tenants, but even one codebase is large enough to start thinking hard about scale.

All of that code becomes vectors. People search the index all day, and the index changes all day: as work lands, files get rewritten, so inserts and deletes run while the searches are still running.

A read at that size cannot touch every row on every request, and you pay that cost again per user, per step, per tenant. Writes are worse: a delete moves rows that readers are still holding, and a rebuild takes a lock the whole system waits on. So before we picked an index, we measured what both really cost.

What follows is that work, told small: a support-docs assistant at eight thousand rows, the same problem at a size you can hold in your head.

One scan is never one scan

illustrative

Two lanes of stored rows drawn as strips of cells at the same cell size, so one cell costs the same in both. The top lane, the assistant in this post, is a short strip crossed by a single scan cursor that finishes and starts again, scan after scan. The bottom lane, one tenant, is four full rows of cells that fade off the right edge and keep going, with six cursors crawling across them at the same speed, one for each person asking at the same time. A counter beside each lane shows how many people are asking and how many scans have finished: the short lane passes thirty scans before the long lane finishes one.

Same loop, same cost per row. The only things that changed are how many rows there are and how many people are asking at once, and they multiply. Drawn to shape, not to scale: a real tenant's index runs orders of magnitude past the right edge.

None of it starts that way, though. It starts with twenty lines that work.

Act I · day one

Twenty lines, and it works

Let's use a company analogy. Someone in the company knows why the invoice job fails on Mondays. You just don't know who. So you ask all of them and keep the best answers. Someone new joins, they stand at the end of the row. The same goes for a flat index at eight thousand rows: nothing to tune, nothing to clean up, nothing to rebuild. Asking everyone takes milliseconds, and it never misses.

Two of three operations touch every row

Insert

O(1)

Strip of 24 cells. One new cell lands at the tail. Nothing else is touched.

touches 0 rows

Search

O(n)

touches 0 rows

Delete

O(n)

Strip of 24 cells. A cursor crosses every cell, one cell turns into a hatched tombstone, and every cell to its right shifts one slot left.

touches 0 rows

index  = np.vstack([index, v])         # insert  O(1)scores = index @ q                     # search  O(n)
top    = np.argsort(-scores)[:k]index  = np.delete(index, i, axis=0)   # delete  O(n)
At 8 000 rows that's fine. Every figure after this one is one of these three strips under load.

It stays the right answer longer than you would guess.

Act I · small scale

At small scale, just loop over everything

Your scan really does look at every vector, every time. That sounds slow, and at small scale it isn't. The rows sit next to each other, so the scan reads them in one straight line, which is the thing a processor does fastest.

IVF is the alternative you would reach for. It sorts the vectors into groups up front, then reads only the few groups closest to your question. Far fewer rows. But those groups sit all over memory, and the machine has to stop and wait for each one to arrive before it can read it. Fewer rows, more waiting.

So below a certain number of rows, reading all of them is the faster one. It is also the only one that never misses.

Sixty-four rows or sixteen, the clock says the same thing

slowed ~10⁷×

Two strips of memory, 64 cells each, drawn in 8 groups. The flat scan lights one whole group at a time and reads all 64 rows in 3.2 time units. IVF jumps to 2 of the groups; before each one it waits for the group to arrive, shown as a pulse, then reads its 8 rows. 16 rows, and the same 3.2 time units.

illustrative

Log–log chart of milliseconds per query against corpus size from 10 thousand to 10 million vectors. A dashed flat line with slope one and a dashed near-flat pruned-index line (IVF, graph) cross near 20 thousand vectors. Two hairlines mark the 200k and 800k delete-benchmark corpora. Two measured points, plotted free-standing, at 700 000 vectors: flat 51 ms, IVF with nprobe 64 3.0 ms.

Memory arrives in blocks, so the straight scan lights a whole block at once. IVF reads two groups instead of eight, but it waits for each group to arrive first; the pulse is that wait. Crossover sketch illustrative; solid marks measured: flat 51 ms, IVF (nprobe 64) 3.0 ms at 700 000 vectors, 384-d, one query.

Still, you try a real one. Just to see.

Act I · the temptation

A big win here, and nobody feels it

So you make the search faster. At 700 000 chunks, IVF took 3 ms. Flat took 51 ms. Seventeen times faster, measured.

Nobody notices. The same answer also spends two seconds waiting on the model, and 48 ms off a two second wait is 2 per cent. Speeding up one part does nothing when the slow part is somewhere else.

So you stay flat.

Seventeen times faster to search, two per cent faster to answer

real time

Two stacked latency bars at true scale. Flat: a 2 000 ms LLM call plus 51 ms of retrieval, 2 051 ms in total. IVF: 2 000 ms plus 3 ms, 2 003 ms in total. Below, a magnified view of the last 60 ms shows the retrieval segments: 51 ms against 3 ms, a difference of 48 ms, which is 2.3 percent of the turn.

True scale above; the last 60 ms magnified ×34 below. Search speed is not the reason to move to IVF here. The six acts after this one are. Measured at 700k vectors, 384-d.

Act II · the first delete

A flat delete moves everyone. An IVF delete moves one.

A senior person leaves and the desk by the window opens up. Everyone wants to move up one seat, so the whole row shifts.

That is what a delete does to a flat index. It takes the index for itself, then slides every row after the gap down one slot to close it.

IVF does not shuffle. It keeps a small table saying which group each row is in and where it sits, so a delete goes straight to that one group. The last row in the group drops into the empty desk and nobody else moves.

Flat only knows a row by its position; IVF knows where it lives

deletes: 0
Every flat delete moves the tail. An IVF delete touches one list: its last entry drops into the hole. A graph index cannot pull a row out without breaking the links into it, so it marks the row dead and cleans up later. Press Delete 10 and watch the counters.

You run it once on the real index and watch the clock.

Act II · the bill

One row costs you the whole index

So you time it. What you pay for is how big the index is, not how many rows you delete.

Sixteen times the rows costs seventeen times as much. But a thousand deletes sent together cost only a third more than deleting one row: one delete holds the index about as long as a thousand do. So send them together.

Every delete pays for the whole array once, so pay it once

Bar chart. Single delete on a flat 384-d index: 6 ms at 50 000 rows, 26 ms at 200 000, 103 ms at 800 000. Deleting 1 000 rows in one batch at 800 000 rows: 138 ms.

Deleting one row from a flat 384-d index, the index taken for itself each time. Sixteen times the rows costs seventeen times as much; on the same 800k index, a thousand ids sent together cost 34 % more. Measured; the 200k point matches the head delete in the next figure: worst-case positions.

And it matters enormously which row you picked.

Act II · the fine print

And the first row costs 60× the last

A delete does not move the whole array. It goes through the rows once and slides the ones after the hole down to close it, so the only rows that move are the ones after the first row you deleted.

Delete the last row of a 200k index and it takes 0.4 ms. Delete the first row and it takes 25 ms. Where you delete matters more than how many you delete.

# what a delete does, in pseudocode
j = 0
for i in range(ntotal):
    if sel.is_member(i): continue          # a deleted row: skip it, j stays behind
    if i > j: memmove(codes[j], codes[i])   # a kept row after a hole: slide it down
    j += 1

You pay for the rows that move, not the row you delete

Try: drag the marker with the mouse, tap or slide a finger on the strip, or focus the marker and press ←/→ (1 000 rows; hold Shift for 10 000) to choose which row to delete.

Delete the
row

A strip of 200 000 rows with a draggable delete marker. Rows before the marker stay in place; rows after it shift down one slot. Below, a straight line from 25 ms at row 0 to 0.4 ms at the last row shows the cost of the delete as a function of its position.

0.4 ms at the end is the fixed cost of the pass; 25 ms at the start is 200k rows copied. The cost rises evenly with the number of rows after the hole: ≈123 ns each, matching ≈129 ns in the previous figure. Both ends measured (200k rows, 384-d); the line between them is the model.

Act III · what comes back

Ask for five, get five

You ask for the five closest matches and three come back. That is the fear. It does not happen, and the reason is when the dead rows get dropped.

If the search skips the dead ones while it is walking, it keeps walking until it has five live ones. You asked for five, you get five.

The other way is to take the first five it finds and drop the dead ones afterwards. Same query, shorter answer.

Skip the dead while you walk and you still get five

k

Two lanes show the same twelve candidates ordered by distance from the query, three or four of them tombstoned. Lane A, selector during traversal: the walk skips dead candidates and fills all five result slots. Lane B, post-filter: the first five candidates are taken regardless, then the dead ones are removed, leaving three of five slots filled. Running 100 simulated queries: lane A returns k every time; lane B returns between two and five, about 3.5 on average.

k is how many results you ask for. Take the first k and drop the dead ones afterwards and you get fewer; skip them while walking and the search keeps going until it has k. Press Run 100 queries for the spread. Simulation: each query kills 20 to 40 % of its candidates at random (seeded); lane A walks past the drawn candidates until it has k.

Act IV · 03:00

So something has to sweep, once a night

Nothing you deleted is actually gone. A flat index has nothing else that can go wrong: no groups to go stale, nothing to repair. The only thing that degrades is the dead rows piling up in it. Every one is memory you still hold and a row the scan still touches. The rebuild drops them.

Between rebuilds the index carries everything you deleted

illustrative shape

Three-day time chart. The tombstone count climbs through each day, steeply in business hours, to roughly fifteen thousand, and drops to zero at the 03:00 rebuild, a sawtooth. The live-vector count, about thirty-six thousand, is a nearly flat line above. A dotted hairline marks 20 % of live. A scrubber reads out the time, the tombstone count and the memory those tombstones hold in megabytes.

When nightly stops being enough

Milvus20 %vector database
Qdrant20 %vector database
Lucene20 %the search engine under Elasticsearch

three systems, independently, compact when ~20 % of a segment is dead.

The rebuild isn't for speed; it takes out the trash. Live vectors (ink) barely change; tombstones and the memory they hold reset only at 03:00. Illustrative shape: 384-d float32, 1 536 B per vector, ~15 600 deletes a day, inserts matching. Dashed hairline: 20 % of live.

The sweep takes a lock. So does every delete. Who is waiting on whom?

Act IV · the pager

Log every lock, or you'll blame the wrong thing

A delete takes the index for itself. That is what the lock is. While the delete has the index, nobody else can touch it, and every search that arrives has to wait.

We measured a physical delete, one that really takes the rows out, on 800k rows: it holds the index for 103 ms. A search that arrives just after it starts waits nearly the whole time, 92 ms, then runs, and finishes late.

If all you log is search latency, a slow search is all you will see. So you go and tune the search. The search was never the problem, and the delete is nowhere in your graphs.

So log the lock. For every wait, write down who waited, how long, and what was holding the index. That log is what told us flat couldn't afford a physical delete, and it is what will tell us if that stops being true.

The search isn't slow. It's waiting.

illustrative

Timeline over 170 milliseconds, four lanes. Top lane, delete: a solid bar holds the index from 0 to 103 ms. Below it, search 1, search 2 and search 3 arrive at 11, 35 and 55 ms and wait, drawn hatched, until the delete lets go at 103 ms: waits of 92, 68 and 48 ms. All three then run at once, for about 40 ms each. A dashed line marks the moment the index comes free. Under the chart, a three-line wait log lists each search, how long it waited, and the delete that held the index.

wait log

who waitedhow longwhat held it
A search log records three slow searches and nothing else. The wait log records three waits, all behind one delete, which is the thing to fix. Illustrative: one delete of 800k rows holds the index for 103 ms (measured); the three searches, and when they arrive, are made up to show the shape.

Act V · the trade

IVF makes deletes cheap. Then the groups go stale.

At two million chunks the scan finally shows up in the numbers, so you switch to IVF. Deletes are microseconds now. That part works.

Here is the catch. IVF sorts the vectors into groups once, at the start, and gives each group a centre point. A search only opens the few groups whose centre is closest to the question. But those centres are never moved again. New data keeps arriving and it does not match the old grouping, so vectors land in a group whose centre is nowhere near them.

Now the answer you wanted sits in a group the search never opens. You can tell the search to open more groups and you will find it again, but you pay that on every query, forever.

The figure below is the whole thing in four steps: the groups as they start, new data arriving, what one search actually opens, and how far each group has drifted from its centre.

The groups are set once. The data keeps changing.

Try: press Next, or tap a step. Step 2 streams in new data. Step 3 lets you open more groups and watch what the search finds. Step 4 shows how far each group has drifted.

Two-dimensional scatter of an IVF index with eight fixed centroids and their Voronoi cells. Step 1 shows the training vectors filed by nearest centroid. Step 2 streams in 400 new vectors from a shifted distribution; vectors filed under another topic's centroid are ringed in vermillion, and each list's mean drifts away from its centroid. Step 3 places a query and probes one to eight cells, reporting recall of the query's ten true neighbours and the share of vectors scanned. Step 4 shows drift per list and lets you compare a few badly drifted lists against uniform drift at the same mean.

illustrative

recall −1 pt · tail latency 4×fixed centroids, 0.5 M updates on a 1.5 M baseSPFresh · SOSP ’23
recall 0.842 → 0.732IVF16384 under content driftDeDrift · ICCV ’23
“re-training an index is not supported … simpler to just construct a new one”FAISS FAQ
Illustrative 2-D projection. 617 vectors, nlist 8, k-means on a 301-vector sample; 400 arrivals, 3 of 8 topics moved. A ring marks a vector filed under another topic's centroid. Recall: share of the query's true 10 nearest neighbours inside the probed lists; latency modelled as proportional to vectors scanned. drift(i) in sandbox units with ‖ci‖ = 1, as for unit-norm embeddings. Tiles quote published measurements.

So you measure drift per list. Then you have to pick a number.

Act V · the threshold

So you alert on drift. On what number?

A freshly built index already has some drift: we measured 0.151. By the time the edited groups had drifted far enough to break searches in them, it measured 0.204.

So the number on its own tells you nothing. 0.151 is healthy here and might be broken somewhere else. Write down the drift the day you build the index, then alert when it rises above that.

Alert on the rise from the build-time baseline, not on the level

Alert on

Line chart of mean drift against days since the index was built, y axis from 0 to 0.25. A solid measured point at day 0 sits at 0.151, the baseline at build, marked by a dashed reference line. A dashed illustrative path rises to a solid vermillion point at 0.204 labelled recall collapse. A bell marks where each alert rule fires: a level threshold of 0.15 fires on day 0, a rise of 0.03 over the baseline fires several days before the collapse, and a level threshold of 0.20 fires less than a day before it.

illustrative path
Measured: 0.151 at build, 0.204 at the collapse. The path and day count are illustrative (collapse placed at day 11). A level threshold fires the day the index is built, or less than a day before the damage; a +0.03 rise over baseline fires days earlier.

Act VI · mid-flight

An edit lands mid-rebuild. Which version wins?

Both indexes now need rebuilding, and a rebuild takes minutes. People keep editing the whole time.

So you build the new index off to the side while the old index keeps serving. Every edit that lands goes to the old index and into a running list of what changed.

When the new index is ready you take it for about 100 ms, apply that list to it, and switch searches over. If the build fails, throw the list away: the old index never stopped, so there is nothing to undo.

Build off to the side, replay the journal under a 100 ms lock, flip

illustrative
beat 1 · serve + capture

Storyboard with a timeline. Three columns: the old index, a journal of edits, and a new index being built. Queries keep hitting the old index while edits land in it and in the journal. The new index builds from a snapshot. Under a lock of about 100 milliseconds the 214 journaled edits are replayed onto the new index, searches switch over, the journal is discarded and the old index is retired. If the build fails, the journal is discarded and the old index keeps serving.

The journal makes the swap boring. If the build fails, throw the journal away: the old index never stopped serving, so there is nothing to undo. Schematic: each square stands for many rows. Counts are the beat's numbers: 214 journaled edits, one ~100 ms lock.
index(now) = build(snapshot) + replay(journal since snapshot)

You have the algorithm. Now you have to find it an hour.

Act VI · when

Pick the window, not the hour

That's the how. The when is its own problem. Watch the server and learn where the dead hours actually are. They're not the same length every night. Measure how long a full reingest takes. Then fit the job to a gap big enough to finish it. A rebuild that runs out of window is worse than one that never started.

The quiet hour is not a clock time

illustrative

Try: drag the rebuild duration (or focus the slider and press ←/→), then switch the policy. Watch which nights flip red.

2 h 00 m
fits 0 of 7 nights

Seven small traffic charts, Monday to Sunday, each covering the night from 22:00 to 07:00. The quiet window, where traffic is below a threshold line, is shaded green and has a different length every night: from 1 h 20 m on Friday to 4 h on Sunday. Under each chart a rebuild bar of the chosen duration is placed either at 03:00 or at the start of the window. Where it runs past the window it turns red and hatched, and a red column marks the traffic it collides with. A summary line counts how many nights the rebuild fits.

Some nights the window is three hours, some ninety minutes. Watch traffic, not the clock, and notice when the rebuild outgrows every window. Traffic illustrative; each chart is one night, 22:00–07:00. Bar = rebuild; red = overrun.

Seven acts of it. Here is the whole thing on one page.

Act VII · what you'd tell yourself

What you'd tell yourself on day one

Everything above, on one page

Flat versus IVF: delete, rebuild reason, drift, search cost, what to monitor. Row labels link back to their sections.
TopicFlatIVF
Know which layer owns your latency before you optimize this one.Flat until it hurts. Measure per partition. Rebuild from the log.