# Chapter 4: Duplicates > Resends bring duplicates. How does the server tell “I have already stored this one”? IM Systems in Depth · https://im.liko.page/en/duplicates/ At the end of chapter 3, Ben saw Ana’s “I’m downstairs” twice. Chapter 3’s fix caused it: the message arrived, the server’s acknowledgment was lost on the way back, the phone thought the message had not arrived and sent it again, and the server stored two copies. At the book’s 10% loss, about 10% of messages go this way (some are stored three times; about 11 extra copies per 100 messages). The real share is far smaller, but v1 carries 4,000,000 messages a day: even 0.1% duplicated is 4,000 a day. Resending is right; it cannot go. The problem to solve is a different one: **when the server receives a message it has already stored, how does it know?** ## 1. Watch it fail Below are chapter 3’s 8 messages, in “wait for the ACK, resend without it” mode, now with a row for what Ben sees: *[Interactive figure: open the page to use it, https://im.liko.page/en/duplicates/]* With “No dedup”, message 7’s ACK is lost, the resent copy is stored too, and Ben sees 7 twice. Now tick “The app is killed and resends message 3 from its outbox an hour later”: another real case. The app sent 3, was killed by the OS before the ACK came back, and resent it from the outbox the next time it opened. Ben sees one more 3. First, why the two “obvious” fixes do not work: - **By sender and text**: same person, same words, within a few seconds, so treat it as a repeat? But Ana really does send “ok” twice. Swallowing a second message the user meant to send is worse than showing two. - **By the id the server gives**: the server gives a message an id when it stores it, but that id goes back to the phone inside the ACK, and the ACK is exactly what was lost. When the phone resends, it does not have that id. ## 2. The fix: the phone names each message - **A client message ID** (not the id the server gives when it stores the message) is generated by the phone **before the first send**, without asking the server. The simplest is a 128-bit random number; “device + counter” also works, but the counter must be saved on disk with the outbox, so it never starts over after a restart or a reinstall. The ID sits in the outbox with the message (on disk, chapter 3), and every resend carries the same ID: the automatic ones, the one after an app restart, and the one the user taps after seeing “!”. It only has to be unique among one sender’s messages, so what the server recognises is “sender + message ID”. - **The server remembers the IDs it has seen recently.** When a message with a known ID arrives, it does not store it again; it **sends the same ACK again**, with the server id from the first time (and, from chapter 5, its seq). The phone ends up exactly as if the first ACK had not been lost. Switch the simulator above to “Remember recent IDs”: the second copy of 7 is recognised and marked “seen”, and Ben sees it once. ## 3. Estimate: how long to remember, and how much - By the simulator’s resend schedule (chapter 3: the last try at 15 s, giving up at 31 s), remembering IDs for **32 seconds** is enough. v1 peaks at 139 messages a second: 139 × 32 ≈ **4,400 IDs**; at 32 bytes each (16 for the ID itself, plus the sender and a time), about **142 KB**. - A real app with no network keeps waiting and resends once it reconnects (chapter 3), so a resend can arrive minutes later; the real window follows reconnect times, say 5 minutes: 139 × 300 ≈ **42,000 IDs, about 1.3 MB**. The hash table’s own overhead makes that two or three times larger, still trivial: keep it in memory. - At v3’s peak of 13,900 messages a second: 32 s is about 440,000 IDs, 14 MB; 5 minutes is about **4.2 million IDs, 133 MB**, split across many message servers (chapter 27), a small share on each. - Over 10,000 simulated messages (without the hour-late resend): with no dedup Ben sees 1,113 repeats (11.1%); with the last 32 seconds of IDs remembered, none. ## 4. The hole in the window, and the real guarantee Look again at message 3, resent an hour later: by the time it arrives, the server has long forgotten 3, so it stores another copy. A repeat later than the window gets past the window. That is not rare: - the app is killed after sending, opened again an hour later, and resends from its outbox; - chapter 3’s “shown failed, actually stored”: the last ACK was lost, the user sees the red “!” and taps resend. So the real guarantee lives in the database: **a unique key on (sender, message ID)**. The server inserts as usual; if the message is a repeat, the insert fails on the unique key, the server knows “already stored”, reads the original row and sends the same ACK. The window of recent IDs stays, but only as a **fast path**: nearly all repeats arrive within seconds and are recognised in memory, saving an insert bound to fail and the read after it. One more detail, about concurrency: two copies of one message can reach two threads, or two servers, at the same moment, and “check the window, then insert” lets both think they have not seen it. So the unique key always has the last word: only one of the two inserts succeeds, and the other hits the conflict and reads the original. And an ID goes into the window only after its insert has really succeeded; otherwise, if the insert failed, the next resend would be taken for “seen” and dropped. Switch to “Unique key”: message 3, an hour late, is caught too. The cost: - One more unique index to maintain on every insert; one more read when a repeat hits it. - Dedup relies on the phone keeping its word: IDs must not collide (enough random bits, or a counter really saved), and a resend must never change its ID. ## 5. Other answers - **Ask the server for an ID first, then send**: one more round trip for every message; and the request for the ID can be lost just the same, so the problem only moves one step earlier. - **An increasing number per device**: the server keeps only the highest number seen from each device, and anything not above it is a repeat; one number replaces the whole window. The cost: the phone must send strictly in order. If 5 is stored while 4 is still being resent, 4 will be taken for a repeat and dropped when it arrives, and chapter 3’s outbox has several messages in flight at once. XMPP stream management (XEP-0198) counts in this in-order way. The number the server gives each conversation is a different thing, for ordering: chapter 5. - **Idempotency keys in payment APIs**: the same idea. Stripe’s API, for one, takes an [`Idempotency-Key`](https://docs.stripe.com/api/idempotent_requests) header, and a request repeated with the same key charges only once. It has a window too: the [docs](https://docs.stripe.com/api/idempotent_requests) say keys are kept for at least 24 hours, and a key reused after it expires counts as a new request. - **Telegram**: the method for sending a message takes a client-generated [`random_id`](https://core.telegram.org/method/messages.sendMessage), documented as being there to prevent a message being sent twice: the same as this chapter’s client message ID. One layer down, every MTProto message also carries a `msg_id`, and [the protocol](https://core.telegram.org/mtproto/description) has the receiver remember the last N and ignore one that is the same, or lower than all it remembers (`msg_id` grows with time, so lower means older): the same “remember recent IDs”, used at the transport layer. **In practice**: in a system the author worked on, dedup used two unique IDs: one was the IM system’s own message ID, the one in this chapter; the other was the business’s own ID. Say a business system sends a notice through the server API, the call times out, and it retries on its own: to the IM those are two new sends with two different message IDs, and only the business’s ID can tell they are the same thing. Each layer covers its own part: the IM’s ID stops resends on the network, the business’s ID stops the business’s own retries, the same idea as Stripe’s idempotency key. ## 6. This chapter’s decision *[Interactive figure: open the page to use it, https://im.liko.page/en/duplicates/]* **Decision card** - Problem: Chapter 3’s resends can store the same message several times, and Ben sees repeats. - Choice: The phone generates a message ID before the first send and keeps it on every resend; the server remembers recent IDs (only after the insert succeeds), and stores a repeat no more but ACKs it again as before; in the database, sender + message ID is a unique key that catches later and simultaneous repeats. - Cost: One more unique index, and one more read on a repeat; the phone must make sure its IDs do not collide. - Revisit when: The repeated ACK must also carry the original seq (chapter 5); IDs remembered separately once the message service runs on many servers (chapter 27); once the ACK goes out on writing to a log, dedup must happen before the log write (chapter 28). - Other answers: Ask the server for an ID first (one more round trip, same problem); idempotency keys in payment APIs (the same idea); Telegram’s random_id (the same approach). The sending side now neither loses nor repeats messages. Next chapter: Ana and Ben send a line at almost the same moment, and the two of them see the two lines in different orders.