Building a Database on S3

11 min read

Building a database on S3 — this is the title of a seminal paper written in 2008, almost 18 years ago. But we are suddenly noticing a spike in databases being built on top of S3 now, in 2026. Why is that the case?

S3 in 2008

When the paper was written, building a database on S3 meant working around two features S3 lacked entirely: strong consistency and atomic conditional writes (compare-and-swap). Both are so foundational to a database that the paper had to bolt on other AWS services just to fake them.

Consistency — and why S3 didn't have it

Consistency in a storage system means: once a write completes, every subsequent read returns that new value. If client A writes x = 5 and client B reads x afterwards, B sees 5 — not some older value. This "read-your-writes" guarantee is what lets a database trust its own storage.

S3 in 2008 did not offer that. It operated on an eventual consistency model: data is replicated across multiple geographically distributed storage nodes, and after a write, some replicas could still briefly hold the old version — so a read that arrived at the wrong replica could return stale data. Worse, overwrites followed a strict "last-writer-wins" policy: if two writers overwrote the same object, whichever put landed last simply replaced the other, silently.

For a database, that's poison: pages you just wrote may not be the pages you read back, and concurrent writes can destroy each other without either writer knowing.

Compare-and-Swap — and why S3 didn't have it

Compare-and-swap (CAS) is an atomic conditional write: "store this new value, but only if the object is still in the state I last saw." In practice, the client sends its update along with the identifier of the version it based the update on (for S3, that would be the object's ETag — a version fingerprint). The store performs the write only if the current version matches; otherwise it rejects the update and tells the client to retry. CAS is the fundamental primitive for coordinating concurrent writers without locks — it's how lock-free data structures are built.

S3 in 2008 had no CAS, no conditional put, and no locks of any kind. The consequences were predictable:

• No atomic updates: if two clients fetched the same 100 KB page, updated different records locally, and uploaded the page back, the second put silently erased the first client's changes — the classic lost update problem.
• No synchronization: S3 provided no mechanism whatsoever to coordinate concurrent writers.

The Workaround: SQS

Because writing directly to S3 pages risked collisions, the paper routed coordination through SQS (Amazon's queue service) to fill the primitive gap:

1. As an append log (Pending Update, or "PU", queues): instead of overwriting shared pages in place, every edit was converted into a small message describing the change — a pending update — and appended to a dedicated SQS queue. Background applier processes drained these queues and periodically applied batches of pending updates to the actual S3 pages, one applier per page at a time. This turned risky random overwrites into safe appends: clients never touched shared pages directly, so two clients editing different records on the same page could never erase each other mid-write.
2. As a lock manager (LOCK queues): SQS's receive operation supported visibility timeouts (temporarily hiding a message from other consumers). The paper used a single token message inside an SQS queue as a makeshift distributed lock, guaranteeing that only one client could write a given page to S3 at a time.

So the 2008 answer to "can you build a database on S3?" was: yes — if you also glue on a queue service to emulate the consistency and atomicity your storage lacks. It worked, but it took two extra services to paper over what a database foundation really needs.

But Why Build a Database on S3 at All?

Given the missing consistency, high latency, and absent Compare-and-Swap primitives — why did the authors still make the case? The motivation was the promise of utility computing for web applications. They argued that for web-scale applications, scalability and availability are absolute necessities, while strict ACID consistency can be relaxed to eventual consistency. The features of S3 that overrode its technical downsides:

• Virtually infinite scalability: unbounded storage capacity and aggregate throughput — performance stays essentially constant regardless of database size or number of concurrent clients, unlike single-server or shared-disk databases that degrade under load.
• 100% read and write availability: multi-datacenter replication guarantees clients can always read and write, never blocked by hardware failures, backups, or other clients' locks.
• Predictable pay-by-use cost: zero upfront capital investment in hardware, data centers, or over-provisioned bandwidth — operational cost scales linearly with actual usage.
• Zero infrastructure management: no disk management, hardware maintenance, manual backups, or server administration.
• Built-in persistence and replication: multi-datacenter durability handled automatically — data never lost to individual component crashes.

The authors demonstrated that with lightweight application-level protocols (SQS log queues and caching) layered on top, developers could recover the necessary database guarantees — atomicity, monotonic consistency — while keeping the massive operational and financial advantages of utility storage.

How SQS Bridges the Gaps

S3 delivers availability and infinite scalability, but its eventual consistency and page-level overwrites create two hard database problems: lost updates from concurrent page writes, and no transaction atomicity. SQS solves both — acting as an intermediate logging and synchronization layer between clients and S3.

Overcoming Consistency: No More Lost Updates

The setup: S3 stores records clustered into large page units (e.g., 100 KB). If two clients concurrently modify different records on the same page and each uploads its version of the page, the second put silently erases the first client's changes. SQS resolves this with PU Queues and LOCK Queues:

• Decoupled write buffering (PU Queues): instead of writing full pages directly, clients create small, idempotent redo log records (insert, update, delete) and push them to the page's Pending Update queue. Primary and secondary B-trees each have PU queues for index updates; each data page has one for record updates.
• Distributed synchronization (LOCK Queues): every PU queue is paired with a LOCK queue holding a single "token" message, so only one checkpointer at a time can touch a given page.
• The checkpoint protocol:
  1. A checkpointer first acquires the token from the LOCK queue via receive(URI, 1, timeout). If another client holds it, the checkpoint attempt terminates immediately.
  2. The checkpointer fetches the current page from S3, applies up to 256 pending log records from the PU queue, and puts the updated page back — all before the lock timeout expires.
  3. On success, processed log records are deleted from the PU queue, and the lock token automatically becomes visible again when its visibility timeout expires.
• Monotonic write ordering: SQS delivers messages best-effort, with no strict FIFO guarantee. To enforce monotonic consistency, page headers and log records carry (client_id, counter_value) pairs, letting the checkpointer sort records chronologically and preventing out-of-order application.

Overcoming Atomicity: All-or-Nothing Transactions

The remaining hole: if a client crashes mid-commit, some of its log records may already sit in PU queues while others are lost — half a transaction, violating atomicity. SQS plugs this with client-specific ATOMIC Queues and a three-step commit:

1. Staging: the client packs all of the transaction's log records (tagged with a unique transaction ID) into its personal ATOMIC queue, ending with a special commit(id) marker. The moment that sequence lands, the transaction is officially committed and durable.
2. Forwarding: the client asynchronously forwards the records from its ATOMIC queue to the target page/index PU queues, deleting each batch from the ATOMIC queue as it propagates.
3. Cleanup: once every record has reached its PU queue, the client deletes the commit(id) marker.

Failure recovery — winners vs. losers: on restart after a crash, a client scans its ATOMIC queue. Records that match a valid commit(id) marker are winners — committed transactions, safely re-forwarded to their PU queues. Records with no matching marker are losers — fragments of incomplete transactions, immediately discarded. That's all-or-nothing execution, recovered instead of enforced.

And because every redo record is designed to be idempotent, applying the same record twice during recovery causes no corruption.

What's the State of S3 Now?

Both of the gaps the 2008 paper had to work around are gone. S3 is now strongly consistent and has a native Compare-and-Swap primitive — and that is the answer to the question this post opened with.

Strong read-after-write consistency (December 1, 2020). Announced at AWS re:Invent 2020, S3 began automatically delivering strong read-after-write consistency for all GET, PUT, and LIST operations, in all regions, at no extra cost. After a write completes, every subsequent read sees it — no more stale replicas, and no more client-side TTL caching, counters, or delayed read retries to paper over eventual consistency (AWS announcement).

Conditional writes — existence checks (August 20, 2024). S3 added support for If-None-Match: "*", letting applications refuse to overwrite an object that already exists — a create-only primitive that prevents accidental overwrites (AWS announcement).

Conditional writes — Compare-and-Swap (November 25, 2024). S3 expanded conditional writes to evaluate If-Match against an object's ETag — a native CAS primitive. Read-modify-write operations can now execute atomically directly on object storage, with no external lock managers, token messages, or queue systems like SQS required (AWS announcement).

Put plainly: everything the 2008 authors had to fake with PU queues, LOCK queues, and ATOMIC queues, S3 now does natively. Combined with S3's original strengths — infinite scalability, 100% availability, pay-by-use pricing, zero infrastructure management — the storage layer itself finally became a viable database foundation. That's why, almost 18 years after the paper, 2026 is suddenly full of databases built directly on top of S3 — coordinating on S3 itself with conditional writes, and fetching data fast with the byte-range and parallel-read techniques covered in S3 Data Fetching Techniques.

Conclusion

So — does it make sense now why there's been a spike in databases built on object storage since 2024? S3 got strong consistency in 2020, then landed native CAS primitives with conditional writes in 2024. Once the storage layer could guarantee read-your-writes and atomic updates on its own, the last technical excuse for bolting on SQS-style workarounds disappeared — and the economics (infinite scale, availability, pay-by-use) were always too good to ignore. A few of the databases riding that wave: Turbopuffer (vector and full-text search directly on S3), Chroma (its wal3 write-ahead log built purely on S3 conditional writes), Neon (Postgres with storage on S3), Databend (S3-native analytics warehouse), and ClickHouse (S3-backed tables for data lakehouse workloads).

The 2008 paper asked the right question 18 years too early. S3 just needed 16 more years to grow the two features the answer required.

Related reads

• S3 Data Fetching Techniques — how S3-native engines read data fast: block sizes, byte ranges, parallel fetches
• The Log Structured Merge Tree — the storage engine architecture these databases layer on top of object storage
• SSTables: The Sorted String Table — the immutable sorted file format S3-native engines write