Relational database design for incrementally transferable collections, part 1: How hard can it be?

This is part 1 of a series, and this part aims to explain a problem. In part 2 (appearing soon) we will look at some solutions.

Let’s start with a simple example. Say we’re running a library, and we’re using a relational database to keep track of loans. Let’s use PostgreSQL. Our library has a few counters where books can be checked out or returned, and those counters will register those events in a loan table, which could look somewhat like shown below.

+----+---------+-----------+------------------+------------------+
| id | book_id | patron_id | checked_out_at   | returned_at      |
|----+---------+-----------+------------------+------------------|
| 1  | 111     | 33        | 2026-09-01T08:08 | <null>           |
| 2  | 222     | 33        | 2026-09-02T10:10 | 2026-09-03T11:11 |
| 3  | 333     | 44        | 2026-09-03T12:12 | 2026-09-04T13:13 |
+----+---------+-----------+------------------+------------------+

The table holds two completed loans (as the books got returned), and one active loan. These loans are our collection of items.

And since the title says we’re going to talk about replication/synchronization, let’s say we want to download this collection of records to do some analysis on. We create an HTTP API at an /export-loans URL; when it’s hit we run SELECT * FROM loan, serialize to CSV, call it a day.

Time passes, our loans table keeps growing, the downloads are getting big and we’re also not the only ones downloading it. Downloading the whole collection of loans every time is not efficient. Ideally we’d be able to download just the loans that have been created or completed since our last download. We’d reconcile this “patch” of sorts with the collection as it already exists clientside, resulting in a consistent snapshot of the server’s state there – this is called incremental state transfer. Most often seen in APIs under the guise of pagination.

With the above table, if we would have requested the collection at 2026-09-02 11:00, we would have gotten:

+----+---------+-----------+------------------+------------------+
| id | book_id | patron_id | checked_out_at   | returned_at      |
|----+---------+-----------+------------------+------------------|
| 1  | 111     | 33        | 2026-09-01T08:08 | <null>           |
| 2  | 222     | 33        | 2026-09-02T10:10 | <null>           |
+----+---------+-----------+------------------+------------------+

At this point in time, loan #3 doesn’t exist yet, and loan #2 hasn’t been returned yet. We denote that the latest timestamp we see here is 2026-09-02 10:10. We’re going to use that timestamp in the next request, to get only mutations that have happened since then; we use the url /export-loans?changed-since=2026-09-02T10:10. The server will then filter the collection with WHERE greatest(checked_out_at, returned_at) >= '2026-09-02T10:10'.¹ Suppose we perform that request at 2026-09-04 14:14, we would get:

+----+---------+-----------+------------------+------------------+
| id | book_id | patron_id | checked_out_at   | returned_at      |
|----+---------+-----------+------------------+------------------|
| 2  | 222     | 33        | 2026-09-02T10:10 | 2026-09-03T11:11 |
| 3  | 333     | 44        | 2026-09-03T12:12 | 2026-09-04T13:13 |
+----+---------+-----------+------------------+------------------+

We see one addition (loan #3), and one mutation (loan #2). We reconcile this with our existing clientside state, and we’re done! We now have a snapshot of the server state, clientside. Or do we? While I have seen this same dead-simple approach implemented many times, there is a pernicious problem with our approach here: without elaborate precautions that we will examine in part 2 (appearing soon), this approach has a bug.

It will manifest itself not through a crash, but through silent data corruption: missing data on the receiving side. The bug can easily escape automated testing because it manifests itself only under conditions of high concurrency. And to make matters even worse, if someone complains that they’re missing records, then by the time we investigate the bug, we cannot reproduce it; our API response will in fact contain the record that was claimed missing. Pretty awful, as bugs go.

So what’s the crux of the bug? It’s that the timestamps (whichever one you pick, eg from these for PostgreSQL) do not necessarily become visible in chronological order. Sure, the timestamp values get instantiated in chronological order. But the transactions² do not necessarily commit in that same order. And thus, the external visibility of the effect of concurrent transactions is also not necessarily chronologically ordered. The following example of a pathologically sequenced flow may help:

-- Transaction A; a book is borrowed via one
-- of the library's checkout terminals.
-- The explicit transaction handling is for
-- illustration; without it, the INSERT would
-- still run inside an implicit 
-- single-statement transaction.

BEGIN;
INSERT INTO loan (
    book_id, client_id, checked_out_at
  )
  VALUES (
    444,     33,        clock_timestamp()
  );
  -- Let's say the timestamp's value
  -- generated here is today's
  -- 10:00:00.000000.

COMMIT;
-- time passes before the commit actually
-- returns (the confirmation that it's been
-- effectuated)
-- …
-- …
-- … waiting…
-- …
-- …
-- … still waiting…
-- …
-- …
-- …
-- ****************************************
-- * What would we see were we to hit our *
-- * /export-loans API at this moment?    *
-- ****************************************
-- …
-- …            
-- Commit effectuated only now :-/
-- The new loan row is now globally visible.

  -- Transaction B, from another checkout terminal.
  -- It starts a little bit later than the one of
  -- Transaction A.











  BEGIN;
  INSERT INTO loan (
      book_id, client_id, checked_out_at
    )
    VALUES (
      555,     44,        clock_timestamp()
    );
    -- Let's say the timestamp's value
    -- generated here is today's
    -- 10:00:00.123456, thus a little
    -- after Transaction A's timestamp.

  COMMIT;
  -- commit has returned more quickly than
  -- transaction A's, signifying that our new
  -- row is now globally visible.

  -- ****************************************
  -- * What would we see were we to hit our *
  -- * /export-loans API at this moment?    *
  -- ****************************************

In other words, the moment recorded in the timestamp is not the moment that the row will become globally visible. Transaction B, which started later and carries a later timestamp for its loan row, committed earlier than Transaction A. In the meantime, if we would have queried our API at /export-loans between transaction B and A committing, we’d have seen this:

+----+---------+-----------+----------------------------+------------------+
| id | book_id | patron_id | checked_out_at             | returned_at      |
|----+---------+-----------+----------------------------+------------------|
| 1  | 111     | 33        | 2026-09-01T08:08:00.000000 | <null>           |
| 2  | 222     | 33        | 2026-09-02T10:10:00.000000 | 2026-09-03T11:11 |
| 3  | 333     | 44        | 2026-09-03T12:12:00.000000 | 2026-09-04T13:13 |
| 5  | 555     | 44        | 2026-09-04T10:10:00.123456 | <null>           |
+----+---------+-----------+----------------------------+------------------+

The row with id 4 is not visible here yet; it’s in limbo pending transaction commit.³ The API client would duly note that the latest timestamp from among these is 2026-09-04T10:10:00.123456, and will use that in its subsequent request to do the incremental state transfer with: /export-loans?changed-since=2026-09-04T10:10:00.123456. And then, because row 4’s timestamp is earlier than this, row 4 will not be in the output even though it is committed and globally visible at the time of that subsequent request. And thus row 4 will never be merged into this client’s local state; the transient glitch results in persistent clientside data inconsistency.

At small scale, under low concurrency, on lightly loaded systems, this problem is not likely to occur. Yet, if I’d be offering a system like this to users I’d still want to fix it and not let this mantrap lie around. Let’s fix it. Curious about solutions? Then read part 2! (appearing soon)

Footnotes

One critique can be that using timestamps for such filters is not ideal:
- Timezones can be confusing. Sometimes people leave them out because of that, and then things get even more confusing because by that, they become implicit.
- Timestamp serialization formats can be underspecified, and being helpfully lenient with the parsing only adds to ambiguity.
- Time is continuous yet timestamps are discrete, with finite precision, resulting in rounding artifacts, and thus distinct events can get recorded with the same timestamp even though they took place at a different moment in time.
- A timestamp as a start of a range can be interpreted as an inclusive or exclusive. Here we interpret it as inclusive, to avoid missing any events – but that means we may get some record repetition at the /export-loans API.
- The database system’s system clock is usually not a reference clock. We’ll have to make very sure it’s never adjusted backwards when comparing it to a reference clock (eg, using NTP). Thus I’d prefer to use an event counter instead; stamping each record with a a monotonically increasing number; every addition or mutation is an event. But that’s not the point I’m trying to make here.
↩
And even if no transaction is created explicitly, a single statement is a “micro transaction”. ↩
The value for the id column here is automatically derived from a PostgreSQL sequence. Sequences are a resource through which operations in an uncommitted transaction can have an effect on the globally visible database state. That’s not very transactional indeed, but in order to assign IDs in concurrent transactions without causing collisions you need a coordination mechanism that works across those transactions, and this is one that avoids locking. Obviously locks are another coordination mechanism that lets transactions interact with eachother… but sprinkling locks everywhere is not the best for system throughput. ↩