skip to content

Writing an entry and its application-maintained index takes two operations. What can a reader see between them, and what if the second fails?

level: middleimportance: must knowfreq 63%

answer

  1. one fact, several separate operations
  2. the window is at least a round trip
  3. order picks which lie, not whether
  4. a crash makes the window permanent
  5. verify what the index handed you

basics

~20 s

Between the two operations the index and the entry disagree, so a reader sees either side of the window: an index pointing at an unchanged entry, or an entry no index knows of. If the second never lands, the disagreement is permanent.

solid answer

~50 s

The two writes are separate operations with real time between them, and a concurrent reader landing inside that window sees one of them and not the other. Change an address and write the forward entry first: for the length of the window the index still resolves the old address to the account and does not resolve the new one. Write the index first and the reverse holds. If the process dies, the connection drops or the second operation is refused, the window never closes and the divergence is permanent — the index outlives the fact it describes. Two remedies exist, and both belong to the tier's concurrency tools rather than to index design: group the steps so the store applies them as one unit, where it offers that, or guard the pair with an optimistic check-and-set. Neither exists on every store, and a grouped write does not necessarily roll back.

code

pseudocode · 20 lines
pseudocode
// changing an account's email address, against a placeholder store interface
account = store.read("account:1042")
old_address = account.email
account.email = new_address

store.write("account:1042", account)
// window opens: the index still resolves old_address, and does not resolve new_address
store.remove("index:account-by-email:" + old_address)
store.write("index:account-by-email:" + new_address, "account:1042")
// window closes

// a reader inside the window, and the check that makes it survivable
key = store.read("index:account-by-email:" + new_address)
if key is empty:
    treat as not found and retry later
else:
    entry = store.read(key)
    if entry.email != new_address:
        // the index is stale; do not trust what it returned
        treat as not found

go deeper

for a junior

Recall that the two writes are independent: the store applies each when it arrives and knows nothing about them belonging together.

for a middle

Describe the window from a reader's side for both write orders, and name the three durable states a failure between the writes can leave behind.

for a senior

Argue a write order on the grounds of which failure the caller can detect, and add read-side verification so a stale index entry is not believed.

for a principal

Treat the window as a property of the design rather than a bug: state what the service promises about it, and whether a lookup with this failure mode belongs in the tier at all.

## Two writes, one fact An **application-maintained index** is a second entry the application writes so it can look something up by a value. Keeping it true means that one logical change — an account's email address moving from one value to another — is expressed as a sequence of separate operations against the store: 1. write the forward entry, `account:1042`, with the new address inside it; 2. remove the index entry for the old address; 3. write the index entry for the new address, pointing at `account:1042`. The store has no idea those three belong together. It applies each one when it arrives and reports success for each independently. Everything in this question falls out of that. ## The window, and what a reader sees inside it Between step one and step three there is a period — short, but real, and at least one network round trip long — in which the index and the entry describe different worlds. A concurrent reader who arrives inside it sees exactly one of these, depending on the order you chose: | Order | Inside the window, a read by the old address | Inside the window, a read by the new address | |---|---|---| | Forward entry first | resolves, and returns an account whose address no longer matches | finds nothing | | Index first | finds nothing | resolves, and returns an account whose address has not changed yet | Neither order is free of the window; they only choose which lie the reader is told. That is worth saying out loud in an interview, because the instinct is to look for a write order that removes the problem, and there isn't one. What an order does buy you is a choice of **which** failure is cheaper for your callers — usually the one that returns nothing over the one that returns a confidently wrong answer, because a caller can retry an absence and cannot detect a wrong hit. ## When the window never closes The window is a correctness problem only because it can be left open forever. Between two operations the process can be killed, the connection can drop, the caller can time out and give up, or the store can refuse the write because it has hit its memory ceiling. Any of those leaves a durable disagreement: - **A dangling index entry** — the index resolves an address to a key that no longer holds what it claims, or holds nothing at all. - **An unindexed entry** — the account exists and is readable by key, but the access path cannot find it, so a uniqueness check passes and a duplicate gets created. - **A stale pointer to a live entry** — the worst of the three, because both reads succeed and nothing looks broken; the reader gets an answer nobody checked. None of these announces itself. The store reports no error, no counter moves, and the disagreement is discovered later by a user, not by the tier. ## The remedies, and their limits Two remedies exist and both are the tier's concurrency tools rather than anything about index design: 1. **Group the steps** so the store applies them as one unit, where the store offers such a construct. This closes the crash window between them. 2. **Guard the pair with an optimistic check-and-set**, so a writer that was overtaken retries rather than overwriting. Both carry a caveat worth volunteering. Not every store in this class offers either, and where a grouped write exists it is not automatically a transaction — a grouped write may apply every step it was given rather than rolling back when one of them is rejected, which is a different guarantee from the one the word suggests. So even with a remedy in place, the honest design still assumes the index can be wrong and still carries a repair pass. Where the store's own grouping is unavailable, the fallback is to make the divergence self-healing: order the writes so the survivable failure is the one you get, and have readers verify what the index handed them rather than trusting it. ## Verification at read time The cheap, general mitigation is a check on the reader's side: after resolving the address to a key and reading the entry, confirm the entry still carries the address you looked up. If it does not, the index entry is stale, and the reader can treat the lookup as a miss and, optionally, remove the offending index entry on the spot. That turns every read into a small repair and keeps the divergence from compounding — at the cost of one comparison and the discipline of making every reader do it.

  • Which of the two orders would you choose, and on what grounds?
    Write the forward entry first, so the failure mode inside the window is a lookup that finds nothing rather than one that returns a wrong account. A caller can retry an absence and will usually treat it as a miss; a caller cannot detect that a successful lookup handed it the wrong entry. Choose the failure your callers can see.
  • The team says a grouped write makes the window disappear. What do you add to that?
    That it closes the crash window between the operations on stores that offer one, which is genuinely valuable, but it is not a transaction by default — a grouped write may apply the steps it was given rather than rolling back a rejected one, and some stores in this class offer no grouping at all. The repair pass survives the remedy.
  • Does having every reader verify the entry remove the need for a repair pass?
    No. Verification protects the reader who arrives, but an index entry nobody reads is never checked, and an entry that was never indexed is never resolved to in the first place, so a read-side check cannot discover it. Read-side verification bounds the damage; only a pass driven from the authoritative source finds what nobody asked for.

saying these in an interview costs you the question

  • Claims a write order exists that removes the window
  • Assumes every store offers a grouped write and that it rolls back
  • Thinks the store reports an error when the two disagree
  • Trusts the entry the index resolved to without checking it
  • Treats the window as too short to matter at production rates