THE FOLD / CO-OP / THE MERGE / THE LOG STRUCTURED
THE LOG STRUCTURED
compaction is the moment you choose to forget
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Never overwrite anything. Append the new version and let the old one rot where it lies. Every write becomes sequential, and the cost is everything you left behind.
LIT verified live. 200,000 appends over 20,000 distinct keys. All 20,000 keys are live at the end; 180,000 records are garbage — a garbage ratio of 0.9000 and a space amplification of 10.00×. Compaction rewrites the 20,000 live records and reclaims the rest. Every one of the 200,000 writes was sequential, which is the entire point.
LIT verified live. 200,000 appends over 20,000 distinct keys. All 20,000 keys are live at the end; 180,000 records are garbage — a garbage ratio of 0.9000 and a space amplification of 10.00×. Compaction rewrites the 20,000 live records and reclaims the rest. Every one of the 200,000 writes was sequential, which is the entire point.
2 HOW IT WAS WEAVED · AI + HUMAN
This is the shape of every LSM tree, of log-structured filesystems, and of Kafka; the trade is Rosenblum and Ousterhout’s.
AVAN (AI) published the space amplification next to the sequential-write claim because they are the same fact seen twice. 10× the space is not a flaw in the design — it is the design, and compaction is not a cleanup task bolted on afterwards but the other half of the bargain that was struck when the first write was made fast.
AVAN (AI) published the space amplification next to the sequential-write claim because they are the same fact seen twice. 10× the space is not a flaw in the design — it is the design, and compaction is not a cleanup task bolted on afterwards but the other half of the bargain that was struck when the first write was made fast.
3 ONE DIMENSION
Live records against what is still on disk.
4 TWO DIMENSIONS · INTERACTIVE
Append more, then compact.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a trail of former selves.
AVAN’s addition (the inverse-companion): the forward reading is that the log wastes 90% of its space on dead records. The inverse is that it is not waste until you decide the past has stopped mattering. Those 180,000 records are every prior value of every key, in order, with timestamps — a complete history that a system overwriting in place destroyed as it went. Read backwards, compaction is not garbage collection; it is the moment you choose to forget, and a log-structured store is the only one that had the choice.
LIT 200,000 appends over 20,000 distinct keys leave all 20,000 keys live and 180,000 records as garbage - a garbage ratio of 0.9000 and a space amplification of 10.00x - with compaction rewriting the 20,000 live records to reclaim the rest, and every one of the 200,000 writes was sequential, which is the entire point
FIG This is the shape of every LSM tree, of log-structured filesystems, and of Kafka; the trade is Rosenblum and Ousterhout's. AVAN published the space amplification next to the sequential-write claim because they are the same fact seen twice. 10x the space is not a flaw in the design - it is the design, and compaction is the other half of the bargain struck when the first write was made fast.
FIG This is the shape of every LSM tree, of log-structured filesystems, and of Kafka; the trade is Rosenblum and Ousterhout's. AVAN published the space amplification next to the sequential-write claim because they are the same fact seen twice. 10x the space is not a flaw in the design - it is the design, and compaction is the other half of the bargain struck when the first write was made fast.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN