Almost Exactly Once: Segment's Billion-Message Dedupe Ledger
The one rule of a data pipeline is that it must never lose data, so every layer guarantees at-least-once delivery: retry until a message is acknowledged. But Segment's public API sits at the one boundary where retries can't be made clean: mobile clients. A phone enters a tunnel mid-upload, the events land, the response dies, and the client re-sends what the server already received - measured at 0.6% of all events in a four-week window, enough to swing an e-commerce customer between profit and loss. Amir Abu Shareb's post describes the dedupe system built in three months: every message carries a client-generated unique ID, Kafka routes each ID to the same worker, and an embedded per-worker database (RocksDB) answers 'seen this before?' in memory. Under load the dedup window shrinks instead of the system falling over, and after a crash workers repair their records against the output stream, the source of truth. The result: 200 billion messages through, 60 billion keys held, 100 times the old capacity at a fraction of the cost.
Put a phone in a tunnel and watch it re-send events the server already has — then turn the ledger on and watch the bloom-filter fast path eat the duplicates. Spike the load and see the guarantee window shrink instead of the system falling over; crash a worker mid-publish and repair its ledger against the output topic; then sneak an aged-out duplicate past the window and meet the guarantee's honest edge.
Problem
The post opens with the pipeline's prime directive - data can be delayed or re-ordered, never dropped - and its standard consequence: at-least-once delivery everywhere, meaning a message is never considered delivered until it is firmly acknowledged, and is retried until it is. Inside Segment, this works cleanly: its own services recover from failures with retries, re-delivery, and locking. There is one place it doesn't work cleanly, and the post calls it out: the front door, where outside clients send data straight to the public API.
The motivating picture is concrete: booking a hotel from a phone on a bus, the app uploading usage events to Segment's servers, the bus entering a tunnel. Some events have been processed; the response never arrives; the client, correctly, retries and re-sends the same events the server technically already received. Nothing is misbehaving. The client cannot tell a lost request from a lost response, and on mobile networks that ambiguity is routine, not exceptional. Segment's server metrics put a number on it: about 0.6% of events ingested within a four-week window are duplicates of messages already received. The post is direct about why that matters: for an e-commerce app generating billions in revenue, a 0.6% discrepancy can be the difference between a profit and a loss of millions.
And the post is equally direct about the ceiling: getting anything close to exactly-once delivery takes a design where every failure case is handled as part of the architecture, not bolted on afterward, and even then it is essentially impossible to have messages delivered only ever once. The dedupe problem itself is deceptively simple (if you have seen this message ID, discard it; otherwise publish it and record the ID, as one step), with a de-duplication window setting how long IDs are remembered. Everything hard lives in two words: performance (deduplicating billions of events at low latency and acceptable cost) and correctness (durably remembering what has been seen across crashes, while never emitting a duplicate).
Solution
Identity comes first: every incoming message is tagged with a unique messageId generated by the client, a UUIDv4 (a random identifier any programming language can produce), with the API assigning one only when the client doesn't. The post names the road not taken: no vector clocks or sequence numbers (other, more complex ways of ordering and identifying events), because those raise client complexity, and a plain unique ID lets anyone in almost any language send data. The whole exactly-once ambition rests on the smallest possible client obligation.
The architecture reads off Kafka, a durable log that stores the message stream on disk and lets it be replayed. Incoming API calls are split into individual messages and written to a Kafka input topic (a named stream), partitioned by messageId, so the same ID is always handled by the same worker. That routing is the key trick: instead of searching one central database for a single ID among hundreds of billions, each worker only has to answer 'seen this?' for its own slice, a search space orders of magnitude smaller. The dedupe worker is a small Go program that reads its partitions, checks each message against a local ledger, and publishes only the new ones to an output topic.
That ledger is an embedded RocksDB database on each worker's local disk. Embedded means it runs inside the worker process rather than as a separate server reached over the network, which is the whole cost win over the previous setup: a fleet of Memcached servers that held every key in memory and forced a hard choice: either accept the occasional cache failure, or double the spend on always-on backup copies. RocksDB's shape (a log-structured merge-tree, which turns all writes into fast sequential appends) fits the workload's three simultaneous demands: checking whether a mostly-new key exists, writing new keys fast, and aging out old ones. The existence check is the textbook case for a bloom filter: a small in-memory structure that answers either 'definitely not seen' or 'possibly seen', so the common case (a brand-new message) is settled in memory without touching the disk files at all, and only a 'possibly' pays for a full lookup. Reads and writes are batched (many IDs looked up at once), trading random disk access for faster sequential access.
The most important design choice is in how old keys are removed: deletion is bound by size, not by time. Rather than a fixed expiry timer per key, each worker caps its database size and deletes oldest-first, so a load spike shrinks the de-duplication window instead of toppling the system, and if the window drops under 24 hours the on-call engineer is paged. So under pressure the guarantee weakens in a measured, monitored way rather than the system crashing - the deliberate opposite of the old Memcached setup, where a flood of expiries would spike the CPU and exhaust memory.
Correctness closes the loop, and the post is honest that no single all-or-nothing step spans the three acts: writing to RocksDB, publishing to the output topic, and acknowledging the input. A crash can land between any two. The fix is to crown one system as authoritative: the output topic is the source of truth, doing double duty as the durable log, with RocksDB treated as a checkpoint that is verified against it. A message isn't acknowledged from the input until RocksDB has persisted it; on restart after a crash, the worker consults the output topic and repairs whichever side fell behind. EBS snapshots (point-in-time copies of the disk) protect the ledger against corruption. And replacing a worker is straightforward: pause it, detach its disk, and re-attach that same disk to the new one, which keeps the partition assignment intact. Three months in production: 1.5 TB of keys on disk, roughly 60 billion keys held, 200 billion messages through, at 100 times the old system's tracking capacity.
Tradeoffs
- At-least-once is the only honest contract with a phone in a tunnel, so all the deduplication complexity moves to the server side. Segment deliberately rejects vector clocks and sequence numbers to keep the client's whole job at 'generate a unique ID' (anyone, any language), and accepts having to remember sixty billion IDs as the price. The other members of the class negotiate deduplication with their callers; Segment's callers can't negotiate, so the pipeline itself has to swallow the duplicates, because the front door can't turn them away.
- Partitioning by messageId turns a global lookup into a local one. Routing the same ID to the same worker shrinks the search space by orders of magnitude and is what makes a small per-worker ledger workable at all, but it also makes that routing load-bearing: replacing a worker has to preserve its partition assignment (pause the worker, detach its disk, re-attach it to the replacement), so the routing guarantee is now part of the correctness argument, not just a performance tweak.
- Giving each worker its own local ledger, with no shared coordination, is cheaper and fails more gracefully than a shared cache fleet. RocksDB on a local disk replaced Memcached's memory-resident key set and its dilemma (accept occasional failures, or double the spend on hot standby copies) by pushing failover to cheap cold storage and snapshots instead. The trade: each worker now runs a real database (write-ahead log, compaction, snapshots) rather than just calling a cache, and 'zero coordination' is only true because Kafka's partition map is quietly doing the coordinating.
- Capping the ledger by size rather than by time lets the guarantee flex under pressure instead of letting the system break. A fixed time window fails hard: a load spike fills the store and the system falls over for everyone. A fixed size fails soft: the window shrinks, duplicates older than the shrunken window can slip through, and the on-call pager fires when the window thins past 24 hours. Segment chose to degrade the promise in a measurable way rather than let availability drop suddenly, and put a monitor on exactly the point where the promise thins.
- When no single transaction can span three systems, you pick one as authoritative and repair toward it. A crash between the RocksDB write, the output publish, and the input acknowledgment leaves them disagreeing, and instead of building distributed transactions Segment names the output topic as both the source of truth and the durable log, with RocksDB as a checkpoint reconciled against it on restart. Recovery logic replaces transaction machinery; the one leftover risk, which the post mentions only in passing ('aside from Kafka failures'), is that if the source of truth itself goes down, the design has no answer - that single failure is deferred rather than solved.
- 'Exactly once' is really shorthand for at-least-once plus a bounded memory of what has been seen, and the post never pretends otherwise. The guarantee holds only within a window that is itself load-dependent, duplicates from outside that window are possible by design, and 0.6% is the honest measure of what the ambiguity costs when unmitigated. The achievement isn't a mathematical proof of exactly-once; it is driving a measured error rate to nearly zero within an explicit, monitored boundary, at a fraction of the previous cost.
Patterns in this article
- Idempotency Keys
The furthest the pattern reaches from where it started: no contract, no stored response replayed, no request/response boundary at all. The messageId (a client-generated unique ID, chosen over more complex schemes to keep the client's job as close to nothing as possible) doubles as the routing key, the primary key, and the identity in a pipeline-wide dedupe ledger that settles the ambiguity downstream because the boundary can't. Across five companies the same key has been a contract term (Stripe), a client discipline (Shopify), a piece of server interior (Airbnb), a platform default (AWS), and here, pure infrastructure - one idea seen from five distances.
- Single-Writer Ownership
The same idea Segment uses elsewhere, applied again here. Just as its Centrifuge system gives each instance sole ownership of its own jobs database, the dedupe pipeline splits the work up by message ID so that each worker's local RocksDB answers 'seen this?' for its own slice alone, with no coordination needed between workers. The ownership boundary is again what turns a global problem (search hundreds of billions of keys) into a local one (search your own partition's), and again the partition map is the quiet coordinator that makes 'coordination-free' actually true.
- Designated Source of Truth
When no single all-or-nothing step can span the RocksDB write, the output-topic publish, and the input acknowledgment, Segment doesn't build distributed transactions; it names one system authoritative. The output topic becomes both the durable log and the final source of truth, RocksDB is demoted to a checkpoint, and on every restart the checkpoint is repaired against the truth. Recovery-by-reconciliation replaces transactions; the cost is that the availability of the source of truth itself becomes the one failure mode the design defers rather than solves.
Also solving this
Other systems in behindscale's Ambiguous failure under retry class: