Topic 5.6
Upserts, Deletes and Consistency
In one line
Documents change while people search. Stores handle this by appending a new row and marking the old one dead (a tombstone), clearing the dead rows later (compaction), and, when copies exist, by making a reader wait until its copy has seen the write.
Think of it like this
A school notice board. When a notice changes, you do not scrub the old paper off the board while children read it. You pin the new notice on top, and put a red cross on the old one. At the end of the week the caretaker takes down all the crossed notices and tidies the board. The cross is a tombstone and the tidy-up is compaction.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Tombstone
- A marker that says a row is deleted. The row stays until compaction.
- Compaction
- Rebuilding storage without the dead rows.
- Upsert
- Insert, or replace if the id already exists, in one step.
- Replica
- A copy of the data, used to serve reads. It can lag behind.
- Primary
- The copy that accepts writes.
- Read your own writes
- A guarantee that after you write something, your next read sees it.
- Replication lag
- How far behind a replica is.
Step by step
01Step 1: only append
The Store never changes a row in place. It appends and flips a flag. This keeps writes cheap and safe while searches read the rows.
02Step 2: upsert
If the id already has a live row, mark it dead and append the new one. slot remembers which row is the live one for each id.
def upsert(self, item_id, vector):
if item_id in self.slot:
self.rows[self.slot[item_id]][2] = False
self.rows.append([item_id, vector, True])
self.slot[item_id] = len(self.rows) - 103Step 3: delete and search
Delete flips the flag. Search keeps only live rows. In the output, after deleting A the top two change from A,B to B,D, and the stats show one dead row.
04Step 4: move a point
B is upserted with a new vector pointing the wrong way. Now there are two rows for B, only one alive, and the top two become D,C. Search never shows the old B.
05Step 5: compact
Rebuild the list from live rows only and recompute the slot positions. The rows drop from 5 to 3 and the answers are the same. The reason to compact is space and speed, never correctness.
06Step 6: the lagging replica
In the second example the primary has 3 writes, the replica applied 2, and the third edit moved D3. A search on the replica still returns the old answer (D5). Given the position of the user's write, read sends the query to the primary until the replica catches up.
Try it yourself
- 1
Predict the stats
Before running, add
store.delete("C")after the move and write down rows, live and dead. Then run it. - 2
Compact earlier
Move the
compact()call to just afterdelete("A"). Do the stats and results of the later lines change? - 3
Make the replica fully caught up
In the second example, call
replica.catch_up(primary, 3)before the first search. Which lines change? - 4
Write an order bug
In
upsertswap the two parts: append the new row first and look up the old slot afterwards. What goes wrong withslot? (Follow the stats.)
Code & diagrams
A real store does the same in files and index structures instead of a list, and compacts in the background.
Expected output
loaded: rows=4 live=4 dead=0 top2=A,B
deleted A: rows=4 live=3 dead=1 top2=B,D
B moved: rows=5 live=3 dead=2 top2=D,C
after compaction: rows=3 live=3 dead=0 top2=D,CReplication here is two objects and a list. Real systems ship the log over a network, so lag is measured in milliseconds to seconds, and it can grow during a heavy write burst.
Expected output
before the edit: D5
replica, no care: D5
with a position: D3 (from the primary: the replica is behind)
after the replica syncs: D3 (from the replica)Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Forget to mark the old row dead
In the Python tab, delete the line self.rows[self.slot[item_id]][2] = False # tombstone: ... inside upsert (leave the if with pass in its place) and run.
Myth vs fact
Myth
Deleting a point frees its space immediately.
Fact
Usually it marks the point dead. Space is returned when the store compacts or rebuilds.
Myth
After I save a document it is searchable at once.
Fact
Depends on the store and on replicas. Some make writes visible after a short delay. Design the product so it copes, for example with a position check.
Myth
Delete then insert is the same as an upsert.
Fact
Between the two calls a search finds neither version. Use a real upsert or a transaction.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Watch the dead ratio (dead rows / all rows) and the size of the index on disk as metrics. A rising ratio is the signal to compact, and a rising index size without rising data is a leak.
- ▸
Deletes can be a privacy requirement (a user asks for removal). Marking dead may leave data on disk until compaction. Know when physical removal happens in your store, and delete from backups and logs on your own schedule.
- ▸
Databases you may already run do the same thing under other names. In PostgreSQL an UPDATE or DELETE leaves the old row version in place until VACUUM removes it, and an HNSW index entry stays until then too. In Lucene-based engines such as Elasticsearch, deleted documents are marked and only dropped when segments merge, and a new document becomes searchable after the next refresh (about a second by default). Read your store's documentation for when a write becomes visible.
- ▸
Batch writes: thousands of single upserts are slower and churn the index more than batches of hundreds. Phase 4's pipeline batches embedding calls, so batch the store writes too.
Remember this
- 1
Why this topic exists. Phase 4 re-ingests documents when they change (Topic 4.7). The store must accept those writes while searches continue, never show a deleted document, never show both the old and the new version, and not slowly fill up with dead data.
- 2
Upsert. "Insert or replace by id." With stable ids (Topic 5.4) one call per chunk is enough. In SQL it is
INSERT ... ON CONFLICT (id) DO UPDATE, as shown in the pgvector README. Prefer upserts to "delete then insert": a search that runs between the two calls would find neither version. - 3
Delete and tombstones. Rewriting a big index in place for every delete is slow and hard to do safely while others read it. Many index structures therefore only mark a point dead and skip it in searches. The example shows it:
delete("A")leaves 4 rows, 3 live and 1 dead, and search results already ignore A. Updating a point is the same: the old row is marked dead and a new row is appended, so "B moved" leaves 5 rows and 3 live ones. - 4
The cost of tombstones. Dead rows still take space, and some structures still visit them while searching. In a graph index the dead node may still lie on a path. The more updates and deletes, the more waste, and the slower and bigger the index. A graph index in particular can lose quality if a large share of its nodes is dead.
- 5
Compaction. The cure is to rebuild without the dead rows, sometimes called vacuum, merge, optimise or reindex depending on the product. After
compact()the example has 3 rows, all alive, with the same search results as before. It costs time and memory while it runs. pgvector's README notes that vacuuming an HNSW index can take a while and suggests reindexing first (REINDEX INDEX CONCURRENTLY) and then vacuuming. Schedule compaction for quiet hours and trigger it when the dead share passes a threshold (Topic 5.10). - 6
Consistency and reading your own writes. When data is copied to replicas, a copy can be a little behind. A user who edits a document and then searches may not see their edit. The second example models it: a replica that has applied 2 of 3 writes still answers with the old vector. A common fix is to remember the position of your write and read from a replica only once it has reached that position, otherwise from the primary. Single-node stores avoid this, and some stores make a new point searchable only after a short delay, so check your product's documentation on when a write becomes visible.
- 7
Index builds and rebuilds. Changing the embedding model, the distance or the chunker means building a whole new index. Do it beside the old one and switch when it is ready, so search never stops (Topic 5.10).
Explain it without notes
What is a tombstone and why do stores use them?
What does compaction do, and what does it cost?
Why is upsert safer than delete followed by insert?
What is "reading your own writes" and how can a replica break it?
Practice
Write dead_ratio(rows) where rows is a list of (id, alive) pairs. Return the share of dead rows as a number between 0 and 1, and 0 for an empty list. Print it with 2 decimals for 5 rows with 2 dead.
Write compact(rows) that returns the rows with the dead ones removed, order kept. Print the ids that remain.
Trade-offs
- ↔
Tombstones: cheap, safe deletes and updates, at the price of waste until compaction.
- ↔
Frequent compaction: less waste, more background work and brief slowdowns.
- ↔
Reading from replicas: more read capacity, possible stale reads.
Done when you can
Done when you can explain tombstones and compaction in your own words.
Done when you can write an upsert that retires the old version.
Done when you can name a way to read your own writes with replicas.
Done when you can say which metrics tell you it is time to compact.