In the last few years, data stores have changed, and “a lot” feels like an understatement. Around 2013 RocksDB was shipped, and it assumed a POSIX filesystem underneath it, because back then that was just what a fast key-value engine ran on. A decade or so later, key-value engines like SlateDB, and analytical table formats like Iceberg or Delta Lake, are running LSM-style structures straight against S3, where that assumption doesn’t hold anymore. This post is about what actually has changed to make that work.
An object-storage-native LSM tree isn’t a fundamentally new database architecture, it’s the same Log-Structured Merge-tree RocksDB has shipped for over a decade, but with the traditional POSIX filesystem replaced by immutable objects and a manifest updated via compare-and-swap (CAS). By running directly on cloud storage like AWS S3 or Google Cloud Storage, it adapts the classical design around three core characteristics:
- Separation of compute & storage: State is persisted in scalable, low-cost object stores rather than local NVMe drives.
- Immutable file alignment: Because LSM trees naturally write data sequentially into immutable files (Static Sorted Tables – SSTs), they natively match object storage’s write-once, read-many design.
- Cloud-optimised I/O: Compaction and read paths are optimised to handle object store latency, high GET/PUT bandwidth, and explicit API call costs.
RocksDB’s write path depends on three things that don’t really have anything to do with LSM trees, they’re just what a POSIX filesystem gives us for free: we can append a few bytes to an existing file, we can fsync those bytes and know they survived a crash, and we can atomically rename a temp file over a real one to make a change visible in one step. The WAL leans on the first two. The MANIFEST, RocksDB’s own record of “which SSTs currently exist”, leans on the third.
If any one of those is taken away, the system does not degrade gracefully, it just stop working. S3 takes away all three. There’s no append, a PUT replaces the whole object. There’s no fsync, durability is whatever the object store’s replication does behind the scenes, and it happens on a timescale of tens to hundreds of milliseconds instead of the low single digits a local NVMe fsync costs. And there’s no rename, only, since August 2024, a conditional PUT: “create this key, but only if it doesn’t already exist“.
S3 is limited by its design, we cannot make it faster, so what is the smallest change to an LSM tree’s write path that survives losing append, fsync, and rename, while leaving everything else, memtables, sorted runs, compaction, exactly as it was? To figure out the answer we need to inspect what each missing primitive was actually protecting.
Append and fsync existed to make a partial write durable, a handful of bytes, safely, before the file that holds them is complete. If we can’t do that cheaply anymore, the fix isn’t to find a workaround, it’s to stop needing partial durability at all: buffer writes in memory until we have a whole, complete, self-contained object worth writing, and pay one network round trip for the whole thing instead of one round trip per record. This is exactly what a memtable already is. Object storage doesn’t force a new component into the design here; it just makes the memtable’s flush threshold matter for latency in a way it never did locally.
Rename existed to make a set of files change atomically, so a reader never observes “half the new SSTs, half the old ones”. Once we can’t rename, the only way to keep that guarantee is to never let the set of files change in place at all: every SST, once written, is permanently immutable, and the only thing that ever changes is a single small pointer, a manifest, listing which immutable SSTs are currently live. Updating that pointer is now the one operation in the entire system that needs an atomic primitive, and it’s small and infrequent enough that a conditional PUT and a retry loop can carry it.
RocksDB’s SSTs were already immutable once flushed, that part isn’t new. What’s new is that immutability stops being an implementation detail and becomes a first-level citizen of the entire system. Locally, “immutable” mostly meant “compaction rewrites files instead of editing them“, a convenience for concurrency control inside one process. On object storage, immutability is the only reason concurrent readers and writers can share a table at all without coordinating. A reader holding an old manifest can keep reading old SSTs indefinitely, safely, even while a compaction job somewhere else is busy writing brand-new ones, because nothing the reader is looking at will ever be touched again. Nobody has to lock anything. Nobody has to tell the reader to wait. The old SSTs just sit there, unreferenced eventually, garbage, but never wrong.
This is the part worth a deep consideration, because it’s a genuine inversion of where durability lives. In RocksDB, the WAL is the thing standing between us and data loss, and the MANIFEST is comparatively an afterthought, a bookkeeping file rebuilt from the WAL if it ever gets confused. In an object-storage-native LSM, that hierarchy flips. The manifest, one small JSON or Avro object, updated by Compare-And-Swap (or Compare-And-Set, CAS), is the database. It’s the single point that defines “what does this table currently contain“, and every SST it doesn’t list, however durably it sits in S3, might as well not exist.
That’s why the commit path collapses to one operation: read the current manifest, compute the new one, try to write it at the next version number with put_if_absent. If someone else got there first, the write fails, not with data loss, with a clean, detectable rejection, and we retry against their version instead of ours. This is optimistic concurrency control, the same pattern MVCC databases have used internally for decades, except here the granularity is “the whole table’s file list” instead of “one row“, and the retry cost is a network round trip instead of a spinlock.
SlateDB applies this architecture directly to low-latency key-value workloads by flushing memtables and conditional-PUTing manifest updates directly to S3. Analytical table formats like Iceberg and Delta Lake aren’t point-lookup KV engines, but they apply this exact same paradigm to columnar datasets: raw data is stored in immutable Parquet objects, while state changes (like Merge-on-Read or Copy-on-Write updates) are committed by racing to swap a manifest pointer, either native in S3 or via an external catalog (e.g., Hive metastore, Glue, REST catalog). The underlying engine goals differ, but the storage mechanics are identical: never mutate in place, always write new immutable objects, and guard the active manifest with compare-and-swap.
The design reads cleanly on paper, but as always the best way to learn is hands-on. Below is a minimal engine, in memory buffering, immutable SSTs flushed as whole objects, a manifest committed by CAS-and-retry, and a compaction pass that merges and swaps atomically, against a fake object store that only exposes what S3 actually gives us: put, put_if_absent, get, list.
The example is going to be in Python for convenience using only built-in standard library modules. A simple python script.py should suffice to run it.
import bisect
import json
import time
from dataclasses import dataclass, field
class ConditionalWriteFailed(Exception):
"""The S3 analogue of a failed compare-and-swap on If-None-Match."""
class FakeObjectStore:
"""No append, no in-place edits. The only concurrency primitive is
'create this key, but only if it doesn't already exist.'"""
def __init__ (self, put_latency_ms=80):
self._objects: dict[str, bytes] = {}
self.put_latency_ms = put_latency_ms # simulated network cost
def put(self, key: str, data: bytes) -> None:
time.sleep(self.put_latency_ms / 1000)
self._objects[key] = data
def put_if_absent(self, key: str, data: bytes) -> None:
time.sleep(self.put_latency_ms / 1000)
if key in self._objects:
raise ConditionalWriteFailed(key)
self._objects[key] = data
def get(self, key: str) -> bytes:
return self._objects[key]
def list(self, prefix: str) -> list[str]:
return sorted(k for k in self._objects if k.startswith(prefix))
@dataclass
class SSTable:
"""Written once, never touched again. A real SST carries a sparse
block index and a Bloom filter so a miss doesn't cost a full fetch.
This one is small enough that the whole thing is the index."""
sst_id: str
entries: list[tuple[str, str | None]] # (key, value); None = tombstone
def get(self, key: str) -> str | None:
i = bisect.bisect_left([k for k, _ in self.entries], key)
if i < len(self.entries) and self.entries[i][0] == key:
return self.entries[i][1]
return None
def to_bytes(self) -> bytes:
return json.dumps(self.entries).encode()
@classmethod
def from_bytes(cls, sst_id: str, data: bytes) -> "SSTable":
return cls(sst_id, [tuple(e) for e in json.loads(data)])
@dataclass
class Manifest:
"""The one thing in this whole system that ever changes. Everything
it doesn't list might as well not exist."""
version: int
sst_ids: list[str] = field(default_factory=list)
def to_bytes(self) -> bytes:
return json.dumps({"version": self.version, "sst_ids": self.sst_ids}).encode()
@classmethod
def from_bytes(cls, data: bytes) -> "Manifest":
d = json.loads(data)
return cls(d["version"], d["sst_ids"])
class ObjectStoreLSM:
def __init__ (self, store: FakeObjectStore, table: str = "t1"):
self.store = store
self.table = table
self.memtable: dict[str, str | None] = {}
self.local_cache: dict[str, SSTable] = {}
self._cached_manifest: Manifest | None = None
self._ensure_manifest_exists()
def _manifest_key(self, version: int) -> str:
return f"{self.table}/manifest/{version:06d}.json"
def _ensure_manifest_exists(self):
if not self.store.list(f"{self.table}/manifest/"):
self.store.put_if_absent(self._manifest_key(0), Manifest(0, []).to_bytes())
def _current_manifest(self) -> Manifest:
"""Real systems cache this pointer and only re-fetch on a CAS
conflict, rather than paying LIST+GET on every read; that's what
the cache below is for. (They still need some way to notice a
*different* writer moved the pointer without telling this
process: a poll, a watch, or a version check on some other
operation. This toy has exactly one writer, so it never has to
solve that half of the problem.)"""
if self._cached_manifest is None:
latest_key = self.store.list(f"{self.table}/manifest/")[-1]
self._cached_manifest = Manifest.from_bytes(self.store.get(latest_key))
return self._cached_manifest
def _commit_append(self, new_sst_ids: list[str], retries: int = 5) -> Manifest:
"""For flush(): a new SST doesn't depend on anything else that
might land first, so on conflict it's always safe to replay it
on top of whatever the latest version turns out to be."""
for _ in range(retries):
current = self._current_manifest()
candidate = Manifest(current.version + 1, current.sst_ids + new_sst_ids)
try:
self.store.put_if_absent(
self._manifest_key(candidate.version), candidate.to_bytes()
)
self._cached_manifest = candidate
return candidate
except ConditionalWriteFailed:
self._cached_manifest = None # someone else landed that version -> re-read
raise RuntimeError("manifest commit did not converge. contention too high")
def _commit_replace(self, sst_ids: list[str], based_on: Manifest) -> Manifest | None:
"""For compact(): the merged output was computed from a specific
snapshot of SSTs (`based_on`). If someone else committed in the
meantime, that output may already be missing data. It can't be
patched by appending, only discarded. Returns None on conflict
so the caller redoes the merge from scratch, rather than risking
a manifest that silently drops or resurrects files."""
candidate = Manifest(based_on.version + 1, sst_ids)
try:
self.store.put_if_absent(
self._manifest_key(candidate.version), candidate.to_bytes()
)
self._cached_manifest = candidate
return candidate
except ConditionalWriteFailed:
self._cached_manifest = None
return None
def put(self, key: str, value: str | None) -> None:
self.memtable[key] = value # None = delete
def flush(self) -> None:
"""The entire durability cost of a batch: one PUT for the SST,
one CAS for the manifest. Compare that to a local WAL paying a
network-grade fsync on every single write (this is the whole
reason batching stopped being optional)."""
if not self.memtable:
return
sst_id = f"sst-{int(time.time() * 1_000_000)}"
sst = SSTable(sst_id, sorted(self.memtable.items()))
self.store.put(f"{self.table}/data/{sst_id}.json", sst.to_bytes())
self.local_cache[sst_id] = sst
self._commit_append([sst_id])
self.memtable.clear()
def get(self, key: str) -> str | None:
if key in self.memtable:
return self.memtable[key]
manifest = self._current_manifest()
for sst_id in reversed(manifest.sst_ids): # newest first
sst = self.local_cache.get(sst_id)
if sst is None:
data = self.store.get(f"{self.table}/data/{sst_id}.json")
sst = SSTable.from_bytes(sst_id, data)
self.local_cache[sst_id] = sst
if key in dict(sst.entries):
return sst.get(key)
return None
def compact(self, retries: int = 5) -> None:
"""Merge, write once, swap the manifest. A reader never sees a
half-merged table, only the manifest before this call, or after.
Note this can't reuse flush's retry strategy. Flush's new SST is
independent of whatever else lands first, so replaying it on top
of the latest version is safe. Compact's merged SST is a snapshot
of a specific set of inputs. If a conflicting write landed in
between, that merge might already be missing an SST's worth of
data, or about to make an already-superseded one look live again.
Patching the manifest instead of redoing the merge is how a
compaction can silently resurrect files it just made obsolete."""
for _ in range(retries):
manifest = self._current_manifest()
if len(manifest.sst_ids) < 2:
return
merged: dict[str, str | None] = {}
for sst_id in manifest.sst_ids: # oldest to newest, newer wins
sst = self.local_cache.get(sst_id) or SSTable.from_bytes(
sst_id, self.store.get(f"{self.table}/data/{sst_id}.json")
)
merged.update(dict(sst.entries))
new_id = f"sst-compacted-{int(time.time() * 1_000_000)}"
new_sst = SSTable(new_id, sorted(merged.items()))
self.store.put(f"{self.table}/data/{new_id}.json", new_sst.to_bytes())
self.local_cache[new_id] = new_sst
if self._commit_replace([new_id], based_on=manifest) is not None:
return
# someone else committed first. this merge is stale, redo it
del self.local_cache[new_id]
raise RuntimeError("compaction did not converge. contention too high")
# old SSTs are now garbage, unreferenced, but still sitting in
# S3 until something is confident no reader still needs them
Now let’s execute a simple example to see how it works. If everything goes as expected we will see the number ’43’ listed twice.
store = FakeObjectStore(put_latency_ms=20)
lsm = ObjectStoreLSM(store)
lsm.put("alice", "42")
lsm.put("bob", "17")
lsm.flush() # one PUT, one CAS (that's the whole commit)
lsm.put("alice", "43") # overwrite, still just sitting in memory
lsm.put("carol", "9")
lsm.flush() # manifest now references two SSTs
print(lsm.get("alice")) # "43" -> the newer SST wins
lsm.compact() # merge both, swap the manifest atomically
print(lsm.get("alice")) # still "43", now from one merged SST
Two methods carry the entire idea:
-
flush, which turns “durable” from a per-write cost into a per-batch one - the pair of commit strategies that replace
fsync-then-rename with compare-and-swap-then-retry
“Retry on conflict” isn’t a single reusable pattern, it depends on whether the operation retrying is additive (safe to replay on top of whatever won), or a function of a specific snapshot (unsafe to replay, has to be redone). Sorted runs, tombstones, newest-wins reads, merge-based compaction, all of it was present in the RocksDB approach. The object-storage-native part is entirely contained in how visibility gets established, not in the data structure.
Once the write path is solved, what’s left is making the read path fast, and that’s where Arrow, Flight SQL, and multi-tier caching actually earn their place as answers to problems the manifest-and-immutable-objects design creates on the read side.
Immutable SSTs mean a reader fetches whole objects or byte ranges from S3 constantly, so whatever format those objects are stored in had better not cost us a deserialisation pass on every fetch. That’s what Arrow buys: a columnar layout specified exactly enough, down to the byte, that a process can operate on a block pulled straight off the wire without constructing row objects first. Flight extends that further, its wire format is the in-memory format, so shipping a batch of results to a client skips the usual serialise-deserialise-reserialise round trip entirely.
And because every SST is now a network fetch away instead of a disk seek away, the cache in front of it has to be shaped for the access pattern that actually dominates, range scans, not point lookups. A three-tier hierarchy, RAM block cache, local NVMe as a cache of raw S3 bytes, and S3 itself as the source of truth is the same shape a buffer pool always had. What changes is the eviction policy: a point-lookup cache scores blocks mostly by recency, because a miss costs roughly the same either way. A range-scan cache has to score by how expensive a given fetch was relative to its size, and prefetch ahead of the scan cursor, because S3 rewards large sequential GETs far more than it rewards many small ones. Get that scoring wrong and every cache miss becomes a synchronous network stall sitting directly on our p99, no amount of clean manifest design upstream saves us from that.
None of this is a new architectural idea, though. It’s engineering effort spent making the consequences of “the filesystem is gone” fast, once we have already accepted the one substitution that made the whole thing possible in the first place.
Note on the toy engine: It skips a real local WAL for the sub-flush window (something still has to survive a crash between “written to the memtable” and “SST flushed”), garbage collection of orphaned SSTs after compaction, and Bloom filters, all things a production SlateDB or Iceberg deployment can’t skip. None of them change the substitution this whole post has been trying to explain for: an object-storage-native LSM tree is a normal LSM tree with the filesystem replaced by immutable objects and a manifest CAS. Everything harder than that is just making that one idea fast enough to matter.
Top comments (0)