Incremental sync cursors

Deep dive

How it works

Parts:

• change index — ordered by seq, one live change per key
• tombstone — a change with value = None, so deletes can travel
• cursor — opaque token: epoch + last seen seq, held by the client
• safe point — lowest uncommitted seq minus 1; pages never pass it
• horizon — seq below which history and tombstones are purged

Operations (numbered steps):

1. Every write to a synced row gets a monotonically increasing seq from the server and replaces the row's previous change (one live change per key). A delete is a row with value = None (tombstone).
2. First sync: no cursor. The server returns pages in seq order, each with has_more and a cursor for the page's last seq.
3. Later syncs: the client sends the cursor; the server runs WHERE seq > cursor ORDER BY seq LIMIT page+1. The extra row is the has_more test, so no count query is needed.
4. The client applies changes (upsert or delete by key) and stores the new cursor in the same local transaction. Crash before storing = the same page again, so applying must be idempotent; last-write-wins per key makes it so.
5. Visibility: seq is reserved inside the writer's transaction but the row becomes visible at commit, and commits can finish out of order. Serving a page up to the highest visible seq would let the cursor jump past a change that commits later, so it is lost for that client forever. Pages therefore stop below the lowest uncommitted seq.
6. Retention: the server purges tombstones (and the history) below a horizon. A cursor below the horizon cannot be answered correctly, because deletes may be missing: reply Expired, the client wipes and restarts without a cursor. A cursor also names the log incarnation (epoch), so a restore from backup invalidates old cursors.

writes:   seq1 a   seq2 b   seq3 c(pending)   seq4 d(committed)
page up to: lowest pending - 1 = 2   -> client cursor 2; seq4 is held back until seq3 commits

Code

Server side: change index by seq, one live change per key, tombstones, two-phase begin/commit with the safe point, paginated pull, tombstone GC with an expiry horizon. Compiled and tested (pagination, empty poll keeps the cursor, update and delete applied on a client mirror, out-of-order commit not skipped, expired and bad cursors).

use std::collections::BTreeMap;

#[derive(Debug, Clone, PartialEq)]
pub struct Change { pub seq: u64, pub key: String, pub value: Option<String> } // None = tombstone

#[derive(Debug, PartialEq)]
pub enum SyncError { BadCursor, Expired } // Expired = HTTP 410: client must full-resync

/// Cursor = epoch (log incarnation) + last seq the client has seen, base-16 text.
/// Treat it as opaque on the client; the server may change the format.
pub fn encode(epoch: u32, seq: u64) -> String { format!("{epoch:x}.{seq:x}") }
pub fn decode(c: &str) -> Result<(u32, u64), SyncError> {
    let (e, s) = c.split_once('.').ok_or(SyncError::BadCursor)?;
    Ok((u32::from_str_radix(e, 16).map_err(|_| SyncError::BadCursor)?,
        u64::from_str_radix(s, 16).map_err(|_| SyncError::BadCursor)?))
}

pub struct Page { pub changes: Vec<Change>, pub cursor: String, pub has_more: bool }

/// Server side. One row per key: the newest change for it (older ones are superseded).
pub struct ChangeFeed {
    epoch: u32,
    next_seq: u64,
    by_seq: BTreeMap<u64, Change>,   // ordered index on seq
    seq_of: BTreeMap<String, u64>,   // key -> its current seq
    pending: BTreeMap<u64, ()>,      // allocated but not yet committed seqs
    horizon: u64,                    // changes with seq <= horizon may be purged (tombstone GC)
}

impl ChangeFeed {
    pub fn new(epoch: u32) -> Self {
        Self { epoch, next_seq: 1, by_seq: BTreeMap::new(), seq_of: BTreeMap::new(), pending: BTreeMap::new(), horizon: 0 }
    }
    /// Phase 1 (inside the writer's transaction): reserve a seq.
    pub fn begin(&mut self) -> u64 { let s = self.next_seq; self.next_seq += 1; self.pending.insert(s, ()); s }
    /// Phase 2 (at commit): make the change visible. Commits may arrive out of seq order.
    pub fn commit(&mut self, seq: u64, key: &str, value: Option<&str>) {
        self.pending.remove(&seq);
        if let Some(old) = self.seq_of.insert(key.to_string(), seq) { self.by_seq.remove(&old); }
        self.by_seq.insert(seq, Change { seq, key: key.to_string(), value: value.map(str::to_string) });
    }
    /// Pages never pass the lowest uncommitted seq, so a late commit cannot be skipped.
    fn safe_upto(&self) -> u64 { self.pending.keys().next().map_or(self.next_seq - 1, |p| p - 1) }

    pub fn pull(&self, cursor: Option<&str>, limit: usize) -> Result<Page, SyncError> {
        let after = match cursor {
            None => 0,
            Some(c) => {
                let (e, s) = decode(c)?;
                if e != self.epoch || s < self.horizon { return Err(SyncError::Expired); }
                s
            }
        };
        let upto = self.safe_upto();
        let mut changes: Vec<Change> = if after >= upto { Vec::new() } else {
            self.by_seq.range(after + 1..=upto).take(limit + 1).map(|(_, c)| c.clone()).collect() };
        let has_more = changes.len() > limit;
        changes.truncate(limit);
        // Next cursor: last returned seq, or (when nothing is new) the safe point, so the client never re-scans.
        let next = if has_more { changes.last().unwrap().seq } else { upto.max(after) };
        Ok(Page { changes, cursor: encode(self.epoch, next), has_more })
    }
    /// Purge tombstones at or below `upto`; cursors older than this now need a full resync.
    pub fn gc_tombstones(&mut self, upto: u64) {
        self.horizon = self.horizon.max(upto);
        let dead: Vec<u64> = self.by_seq.range(..=upto).filter(|(_, c)| c.value.is_none()).map(|(s, _)| *s).collect();
        for s in dead { if let Some(c) = self.by_seq.remove(&s) { self.seq_of.remove(&c.key); } }
    }
}

The client loop is loop { page = pull(cursor); apply(page); store(cursor); if !page.has_more { break } }, with Expired mapped to "wipe local copy, restart with no cursor".

Complexity and constants

• Pull: one index range scan, O(log n + page). Cost is page size times row size, not collection size.
• Cursor: here two hex numbers, order of 10 bytes; real ones are often a few dozen to a few hundred bytes (they may embed filters or a signature).
• Log size: one row per live key plus tombstones until the horizon. Tombstone retention trades storage against how long an offline client may stay away before a full resync.
• Cost drivers: bytes per page, requests per sync (page size, long-poll instead of tight polling), and the full resync a too-old cursor triggers, which is the expensive path.

Efficiency

• Cost: a pull is one index range scan, O(log n + page), with the new cursor in the same response. The cursor here is two hex numbers, order of 10 bytes; real ones are often a few dozen to a few hundred. An idle sync is one small request and an empty page. A too-old cursor forces a full resync, the expensive path. Bound: bytes per page and requests per sync (network and radio wake-ups on mobile).
• Levers:
  • larger pages — fewer round trips (order of) — bounded by memory and how long a read transaction may stay open
  • long-poll or watch that says "changed after cursor X" — removes most empty polls (Kubernetes list-then-watch, CouchDB longpoll) — mobile and many idle clients
  • keep only the newest change per key — a client away for a day gets each key once however often it changed (above) — hot keys
  • one ordered index on seq for all clients — no per-client cursor table or bookkeeping writes (above) — many clients
  • tombstone horizon as a rule — bounds storage against how long a client may stay offline — long-lived collections
• Naive → standard → state of the art:
  • full fetch and client-side diff · O(dataset) every sync
  • cursor plus page, polled · O(log n + page) per pull, no server state per client
  • cursor plus push or long-poll for changes, compacted per key · O(changes) per client, no empty polls

Implementation notes

• Make the cursor opaque and versioned: clients must only store and echo it, so the server can change its layout, add the epoch or sign it.
• Do not use wall-clock time as seq; ties and skew lose changes. If you need time, use a hybrid logical clock, or take seq from a counter that commit order respects.
• In a SQL database a sequence is not commit ordered: values are handed out at nextval time and a rolled back transaction leaves a gap (PostgreSQL sequences). Either stamp seq at commit under a lock, or hold back pages with a safe point as in the code (for example using the oldest in-flight transaction).
• Treat gaps as normal: Gmail history ids are increasing but not contiguous. Never use "seq == last + 1" as a completeness check.
• Page in seq order and keep the page size small enough to hold read locks briefly.
• Make the horizon a rule (retain tombstones N days) and log cursor age on each pull, so you see how often clients expire.

Pitfalls

• Skipped changes from out-of-order commits (step 5): rare, hard to reproduce, silent.
• Tombstones purged too early: clients keep deleted rows forever. Expire the cursor, never "just return fewer deletes".
• Cursor tied to a query: a changed filter or sort with an old cursor returns inconsistent results. Bind the filter into the cursor or reject mismatches (Calendar requires the same query parameters with a sync token).
• Storing the cursor before applying the page loses data on a crash; apply and store atomically.
• Restore from backup or a failover that rewinds seq: old cursors point into the future. An epoch in the cursor catches it.
• Bumping seq on no-op writes wakes every client for nothing.

Variants and alternatives

In production

Google Calendar (sync token, 410 Gone forces a full sync), Gmail (history id, 404 means full sync), Google Drive (changes page token), Microsoft Graph delta queries (delta token, tombstones as @removed; tokens expire), Dropbox (/files/list_folder returns a cursor and has_more; /files/list_folder/continue takes it), CouchDB (_changes?since=, last_seq is opaque), Kubernetes (list returns resourceVersion; watch resumes from it; 410 Gone when compacted).

Implementations

Sources

• Google, Synchronize resources efficiently (Calendar API sync tokens, 410 handling). docs
• Google, Synchronize clients with Gmail and users.history.list (history id, 404 and full sync). docs · reference
• Microsoft, Microsoft Graph delta query overview (opaque delta tokens, expiry, 410). docs
• Kubernetes documentation, API concepts (efficient detection of changes, resourceVersion, 410 Gone). docs
• Apache CouchDB documentation, /{db}/_changes. docs
• Google, Drive API: changes. docs
• Dropbox, HTTP API documentation (/files/list_folder, /files/list_folder/continue). docs
• Electric, HTTP API (shape log offset and handle). docs