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:

The server gets a message it has already stored. How can it tell?

by sender and textby how close in timeby an ID the phone gave it

↑ Guess first

storedrecognised: not stored, ACKed againa repeat Ben sees

Ben sees

–

Repeats

–

Caught, not stored

–

No dedupstore whatever arrivesRemember recent IDsseen within 32 s: not storedUnique key(sender, message ID) stored once

The app is killed and resends message 3 from its outbox an hour later Other messages

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 IDmessage ID消息 IDA unique ID the client gives each message before sending it, unchanged on resends. The server uses it to recognise a resend.See the glossary (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 header, and a request repeated with the same key charges only once. It has a window too: the docs 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, 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 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

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.