Why you can't build an ordered log out of S3 objects alone
S3 keeps bytes safe but has no order between objects. One record in a transactional data store gives it.
- Published
- Reading
- 7 min
- Tags
- #engineering
Storage doesn’t order keys
S3’s consistency is strong, but its unit is one key. A successful PUT is visible to every GET and LIST that starts after it [1]. Across keys, the documentation is explicit [1]:
Updates are key-based. There is no way to make atomic updates across keys. For example, you cannot make the update of one key dependent on the update of another key unless you design this functionality into your application.
Concurrent writes to one key resolve as last-writer-wins, and S3 states that the order it receives them in cannot be predicted [1]. LIST returns keys in lexicographical order in general purpose buckets and in no documented order in directory buckets [2].
Hive tables show what happens when a listing is the source of truth. Iceberg’s documentation explains that Hive’s file listings make atomic table changes impossible and, on eventually consistent stores, return incorrect results [3]. S3’s strong consistency since 2020 fixes the stale listing, not the atomicity: a table defined by a listing still cannot change several files in one step.
The commit decides order
Iceberg keeps table state in a tree of immutable files: data files, manifests, a manifest list per snapshot, and a metadata file at the root. The current table is whichever metadata file one pointer names, and the spec requires the catalog to swap that pointer with a conditional write: V+1 is written only if the pointer still says V. The spec calls this a check-and-put [4]:
- Create new table metadata based on the current version V.
- Write it to a unique file,
<V+1>-<random-uuid>.metadata.json. - Ask the catalog to swap the pointer from V to V+1.
- If the swap fails, another writer created V+1 first; go back to step 1.
Everything before step 3 is the durability track: the writer PUTs files in any order, and none is visible because no pointer names it. Step 3 is the only step that decides order. Each snapshot is optimistically assigned the next sequence number, and a failed commit gets a new one on retry [4]. A file written first can end up with a higher sequence number. The commit order is the history.
Linearizability makes that order the one every reader sees. Jepsen defines it as [5]:
every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations: e.g., if operation A completes before operation B begins, then B should logically take effect after A.
Once a swap to V+1 returns success, any later load must see V+1 or later. A store that serves V from a lagging replica lets the next writer build on a stale base. The spec’s older rename-based scheme is marked unsafe in object stores [4]; S3 has no atomic rename.
| Transactional store | Conditional write | Scope |
|---|---|---|
| DynamoDB | Condition expression on a row version [6] [7] | One item; TransactWriteItems for up to 100 [8] |
| Spanner | Externally consistent transaction [9] | Any set of rows |
| S3 object | If-Match on the ETag [10] | One key |
| S3 rename | None | Unsafe [4] |
Crashes leave garbage, not corruption
Nothing is visible until the swap, so every crash before it has the same outcome.
| Writer crashes | Readers see | Recovery |
|---|---|---|
| Before the swap | Version V | Rerun; orphans are cleaned later |
| During the swap, outcome unknown | V, V+1, or later | Read the pointer; if it names a later version, walk its metadata log back to V+1 and look for this writer’s file |
| After the swap | V+1 or later | None |
The current pointer alone is not enough. If this writer’s swap succeeded and another writer then committed V+2, the pointer names V+2. A writer that reads that as failure and retries an append adds its data twice.
A file no pointer names is in no table version. Readers start from the pointer, not a listing, so it costs storage and corrupts nothing. This holds only if every attempt writes new names; If-None-Match: * enforces it, since the first conditional write to a name wins [10].
Why this got easy after 2020
AWS made all S3 requests strongly consistent in December 2020 [13], and Iceberg dropped its extra consistency checks [6]. That settled the durability track. The ordering track still needed a separate store, because S3 could not refuse a write; Delta Lake uses DynamoDB “to provide the mutual exclusion that S3 is lacking” [14]. S3 added conditional writes with If-None-Match in August 2024 [15], and If-Match for writes, a conditional write on one key, in November 2024 [10]. DynamoDB and Spanner provide the same guarantee across several records [8] [9].
The same split works for a log
A Kafka-style partition is an ordered log, and the same tracks apply. On the durability track, the broker writes record batches to S3 as segment objects under new names. On the ordering track, each partition has one pointer record listing its committed segments and the next offset.
Offsets play the role of sequence numbers: they are assigned when the pointer advances, not when bytes land. The segment holds batches in relative order, and the pointer records its base offset. A broker that loses a race takes the next free offsets without rewriting the segment, because no offset is written into it.
A produce request maps onto the commit steps:
- Read the partition pointer: version V, next offset N.
- Write the segment to S3 under a unique name.
- Swap the pointer from V to V+1, adding the segment at base offset N.
- On success, acknowledge the producer with offset N. On failure, go back to step 1 with the same segment.
The producer is acknowledged only after step 3. A crash before it leaves an orphan segment and an unacknowledged request the producer retries. A crash during it is resolved as in the crash table: look for the segment in the pointer’s history first.
Batching amortizes the round trip. The broker collects produce requests from many producers, writes them as one segment, and commits them with one swap. Requests that arrive during a commit join the next batch, so the commit rate stays fixed while bytes per commit grow with load.
What it costs
Every commit pays a pointer round trip after the bytes are durable.
The pointer also serializes writers. As an illustrative estimate: at about 10 ms per conditional write, one pointer supports at most about 100 commits per second. Batching 50 produce requests per commit turns that into 5,000 requests per second; with 4 MiB segments, about 400 MiB/s. Lost races lower the ceiling further, and the store has its own: a DynamoDB partition delivers at most 1,000 write units per second, and transactional writes cost two per item [16] [8].
When designing a system on object storage, write the bytes wherever durability is cheapest, keep the order in one record in a transactional store, and make the cleanup job use the same conditional write as the writers.
References
- Amazon Web Services. Amazon S3 data consistency model. Amazon S3 User Guide.
- Amazon Web Services. ListObjectsV2. Amazon S3 API Reference.
- Apache Iceberg. Reliability. Iceberg documentation.
- Apache Iceberg. Iceberg Table Spec. Sections “Optimistic Concurrency”, “Sequence Numbers”, “Commit Conflict Resolution and Retry”, “File System Tables”, and “Metastore Tables”.
- Jepsen. Linearizability. Jepsen consistency models.
- Apache Iceberg. Iceberg AWS Integrations. Iceberg documentation.
- Amazon Web Services. DynamoDB condition expression CLI example. Amazon DynamoDB Developer Guide.
- Amazon Web Services. Amazon DynamoDB Transactions: How it works. Amazon DynamoDB Developer Guide.
- Google Cloud. Spanner: TrueTime and external consistency. Spanner documentation.
- Amazon Web Services. How to prevent object overwrites with conditional writes. Amazon S3 User Guide.
- Apache Iceberg. Maintenance. Iceberg documentation.
- Apache Iceberg. Spark Procedures: remove_orphan_files. Iceberg documentation.
- Amazon Web Services. Amazon S3 now delivers strong read-after-write consistency automatically for all applications. AWS What’s New, December 2020.
- Delta Lake. Storage configuration. Delta Lake documentation.
- Amazon Web Services. Amazon S3 now supports conditional writes. AWS What’s New, August 2024.
- Amazon Web Services. Best practices for designing and using partition keys effectively. Amazon DynamoDB Developer Guide.
Arun Lakshman Ravichandran