skip to content

Change Tokens & Tombstones

Incremental sync pulls only what changed since an opaque token, learns of deletes from tombstones, and falls back to a full resync when the token expires. Interviewers ask how a client catches up.

on this pageshow

explore

questions

6

In a mobile mail client that pulls changes by sync token, when should it save the new token, and why then?

level: middleimportance: must knowfreq 47%

answer

  1. the token names a state
  2. opaque: store it, never parse it
  3. same transaction as the changes
  4. saved early means skipped changes
  5. re-applying a page is harmless

basics

~20 s

Save the new token only in the same local transaction that commits the changes it covers. Saved earlier, a kill skips those changes for good; saved with them, a kill at worst repeats a pull the client applies idempotently.

solid answer

~50 s

The token is the server's opaque name for a state: "you have everything up to here". Saving it is a claim that the local database holds that state, so it must be true when written. I apply the created, updated and deleted records and write the new token in **one transaction**. A kill before the commit changes nothing, and the next pull repeats the request. Writing the token first opens a window where a kill leaves the token ahead of the data, and those changes are never asked for again. I make applying idempotent — upsert by id, delete if present — so a repeated page is harmless. With paged changes, each page's intermediate token commits with that page, so a long catch-up resumes where it stopped. If the response carries only ids, I commit the token with a durable list of ids still to fetch.

code

pseudocode · 15 lines
pseudocode
function pull_changes(scope):
  token = store.read_token(scope)
  loop:
    response = server.changes(since = token)
    if response.error == "token_invalid":
      return start_full_resync(scope)
    store.transaction:
      for id in response.deleted:
        store.delete_if_present(id)
      for record in response.created_or_updated:
        store.upsert(record)
      store.write_token(scope, response.new_token)
    token = response.new_token
    if not response.more_changes:
      return done

go deeper

for a junior

Remember the rule: the token is stored exactly as the server sent it and is saved in the same transaction as the changes it covers.

for a middle

Walk through the three orderings and what a kill does in each, and explain why idempotent apply turns the worst case into repeating a page.

for a senior

Cover paged catch-up with intermediate tokens, ids-only responses with a durable to-fetch list, and one pull per scope at a time.

for a principal

Treat the token contract as an API decision: per-folder or per-account scope, page limits and newest-first paging shape how fast a long-absent phone becomes usable.

## What a sync token is A mobile mail client that syncs incrementally keeps a **sync token**: a string the server returned with its last answer, meaning "the state you have caught up to". The next pull sends it back and asks for changes since that state. The rules for handling it are short: - It is **opaque**. The server may encode a counter, a journal position or a composite of several states, and may change the encoding in any release. The client never parses it, compares two tokens or builds one. - It belongs to a **scope** the server defines — one per account, or one per folder. The client stores each token next to the collection it describes. - It is **durable app data**, kept in the same local database as the messages, not in memory and not in a disposable cache folder the operating system may clear. ## The ordering rule Saving the token is a statement: "the local store now reflects this server state". The statement must never be false. So a pull goes like this: 1. Read the stored token and request changes since it. 2. Open one local transaction. 3. Apply the deletes (delete if present), then the creates and updates (upsert by id). 4. Write the new token in the same transaction. 5. Commit. Both native platforms may end a backgrounded app's process at any time to reclaim memory, so any gap between steps is a gap a kill can land in. The single transaction removes the gap. ## Early, together or late | When the token is written | A kill between data and token leaves | Result | |---|---|---| | Before the changes | token ahead of the data | changes silently skipped until a full resync | | In the same transaction | both or neither | correct | | After, as a separate write | data ahead of the token | the next pull repeats those changes | The first row is the dangerous one, because nothing notices: the stored token is perfectly valid, the server happily answers from it, and the skipped flag changes or deletions never come back. The third row is safe as long as applying changes is **idempotent** — an upsert by id writes the same values again, and deleting an absent id does nothing. That is why idempotent apply matters even with the single transaction: it makes "repeat a page" the worst case of every failure. ## Paged changes and intermediate tokens A phone back after two weeks may be thousands of changes behind. Servers usually cap a response and say "more changes to come", returning an **intermediate token** that names the partial state the page brings the client to. Treat each page as its own unit: apply it and write its intermediate token in one transaction, then ask again from that token. A kill on page 30 of 40 resumes at page 30, not page 1, and the inbox reads from the local store throughout, so the user is never staring at a spinner while the backlog drains. Some servers send the most recent changes first, which makes the screen right sooner while older changes page in behind it. ## Ids-only responses When the change response lists only ids, the records still have to be fetched. Writing the token before they arrive would recreate the dangerous row of the table. Two safe shapes: - Fetch the changed records first, then apply them and the token together. - Or commit the token together with a durable **to-fetch list** of the created and updated ids, then fetch in batches and clear each id as its record lands. A kill leaves the list behind, so the next run finishes the fetch instead of forgetting it. ## One pull per scope at a time Two pulls running with the same stored token both receive overlapping changes and both write a token. If the slower one commits last, it can write older record versions and an older token over the newer result. Running one pull per scope at a time, with later triggers coalesced into a follow-up pull, removes the race; that coordinator is a separate design question about sync triggers. ## Summary - The token is opaque, scoped and durable. - It is written in the same transaction as the changes it covers, never before. - Apply is idempotent, so the only failure mode left is repeating work. - Large catch-ups page with intermediate tokens and stay usable throughout.

  • Why must the client never compare or parse two tokens to decide which is newer?
    The token is opaque: the server may encode a counter, a journal position or a composite of several states, and may change the encoding without notice. Only the server can interpret it. The client's whole job is to send back the last token it committed and store whichever token the server returns next.
  • What breaks if two pulls run at once with the same stored token?
    Both receive overlapping changes and both write a token. If the slower response commits last, it can write older versions of some messages and an older token over the newer result. One pull per scope at a time, with later triggers folded into a single follow-up pull, removes the race.
  • If the change response lists only ids, how do you keep the ordering rule?
    Either fetch the records before committing anything, or commit the token together with a durable to-fetch list of the created and updated ids, then fetch them in batches and clear each id as its record lands. A kill between the two leaves the list behind, so the next run completes the fetch.

A bookmark in a long book: you move it after you have read the page, not before you start it. Moved early, a sudden interruption means you skip a page without knowing; moved late, you merely reread a paragraph.

  • Save the new token as soon as the response arrives, before applying it.
  • The client can parse the token to see how far behind it is.
  • Applying the same change page twice corrupts the local data.
  • Keeping the token in memory and writing it when the app goes to background is enough.
  • A paged catch-up that is interrupted must restart from the original token.
open as a page

A mobile mail client returns after 60 days and the server rejects its sync token; how should it resync without losing unsent writes or re-downloading unchanged mail?

level: seniorimportance: must knowfreq 44%

basics

~20 s

Treat the rejection as "cannot compute changes", not "delete everything". List server messages with version tags, fetch only new or changed ones, delete local ones absent from the complete listing, and keep the outbox to replay on top.

open as a page

In a mobile mail client that syncs incrementally, why must deleted messages arrive as tombstones rather than simply being left out?

level: juniorimportance: should knowfreq 40%

basics

~20 s

An incremental pull returns only what changed, so a message missing from it is simply unchanged. The server must name each deleted message's id as a tombstone; otherwise the phone keeps showing mail that is gone everywhere else.

open as a page

On first launch of a mobile mail client with 40,000 messages, what should it sync first, and how should it backfill the rest?

level: middleimportance: should knowfreq 38%

basics

~20 s

Fetch the folder list and the newest page of inbox headers first, capture a change token, and show the inbox. Then backfill older mail in resumable pages, fetching bodies on demand, while delta pulls from that token keep it current.

open as a page

In a mobile mail client, a push nudge, a reconnect and an app foreground arrive within seconds; how should sync triggers be designed so they cause one pull?

level: seniorimportance: should knowfreq 41%

basics

~20 s

Route every trigger to one sync coordinator per account that allows one pull in flight. A trigger during a pull only sets a rerun flag, so a burst costs at most one more pull; a push nudge is a hint, not data.

open as a page

In a mobile mail client, how should an incoming sync pull be merged so it never hides the user's own unsent changes?

level: seniorimportance: should knowfreq 36%

basics

~20 s

Keep the server's last-confirmed state apart from pending outbox operations. A pull updates only the server layer; the screen shows it with pending operations replayed on top, so an offline flag stays set until confirmed or rejected.

open as a page