Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Delivering Billions of Messages Exactly Once

segment.com

Post reply on HN
Print view View original

41–50 of 141 posts

Re: Delivering Billions of Messages Exactly Once

#41

Post by sethev »

kmicklas wrote: post #32
mamon wrote: post #20

"Exactly once" model of message is theoretically impossible to do in distributed environment with nonzero possibility of failure. If you haven't received acknowledgement from the other side of communication in the specified amount of time you can only do one of two things: 1) do nothing, risking message loss 2) retransmit, risking duplication But of course that's only from messaging system point of view. Deduplicatio…

> there is no foolproof way of implementing that pseudocode's "has_seen(message.id)" method Wait why? Just because you'd have to store the list of seen messages theoretically indefinitely?

There's also a race condition in there when you receive the duplicate before publish_and_commit is done doing its thing - assuming they're not actually serializing all messages through a single thread like the pseudocode implies.

What they've done is shift the point of failure from something less reliable (client's network) to something more reliable (their rocksdb approach) - reducing duplicates but not guaranteeing exactly once processing.

Re: Delivering Billions of Messages Exactly Once

#42

Post by squiguy7 »

I wonder how they partition by "messageID" they use to ensure that the de-duplication happens on the same worker. I would imagine that this affects their ability to add more brokers in the future.

Perhaps they expect a 1:1 mapping of RocksDB, partition, and de-duplication worker.

Re: Delivering Billions of Messages Exactly Once

#43

Post by gsmethells »

Why do I get the feeling this is repeating TCP features at the Message level? There must a protocol that can hide this exactly once need away. TCP doesn't create downloads, generally, that are bad and fail their checksum test, hence packets that make up the file are not duplicated.

Re: Delivering Billions of Messages Exactly Once

#45

Post by hilbertseries »

timdorr wrote: post #28
wonderwonder wrote: post #9

Would something like AWS SQS not scale for something like this? We currently push about 25k daily transactions over SQS, obviously no where near the scale of this, just wondering about what limitations we will bump into potentially.

The limitations are most likely on price. For the 200B messages they've already processed in the last 3 months, that would be $100,000 total on just the SQS FIFO queue, or $33,333 per month. And that's not counting data transfer.

As long as everything is in ec2 data transfer will be free. You're cost calculations are also off base. You'll need to send, receive and delete every message that you process via SQS. These can all be done in batches of 10. So it's 200B * 3/10 * .50 / million, which comes out to 60k over 3 months. Still not cheap, Kinesis is probably the better option in this case if you want an AWS managed service.

Re: Delivering Billions of Messages Exactly Once

#48

Post by newobj »

I don't want to ever see the phrase "Exactly Once" without several asterisks behind it. It might be exactly once from an "overall" point of view, but the client effectively needs infinitely durable infinite memory to perform the "distributed transaction" of acting on the message and responding to the server.

Imagine:

- Server delivers message M

- Client process event E entailed by message M

- Client tries to ack (A) message on server, but "packet loss"

- To make matters worse, let's say the client also immediately dies after this

How do you handle this situation? The client must transactionally/simultaneously commit both E and A/intent-to-A. Since the server never received an acknowledgment of M, it will either redeliver the message, in which case some record of E must be kept to deduplicate on, or it will wait for client to resend A, or some mixture of both. Note: if you say "just make E idempotent", then you don't need exactly-once delivery in the first place...

I suppose you could go back to some kind of lock-step processing of messages to avoid needing to record all (E,A) that are in flight, but that would obviously kill throughput of the message queue.

Exactly Once can only ever be At Least Once with some out-of-the-box idempotency that may not be as cheap as the natural idempotency of your system.

EDIT: Recommended reading: "Life Beyond Distributed Transactions", Pat Helland - http://queue.acm.org/detail.cfm?id=3025012

Re: Delivering Billions of Messages Exactly Once

#49

Post by Cieplak »

newobj wrote: post #48

I don't want to ever see the phrase "Exactly Once" without several asterisks behind it. It might be exactly once from an "overall" point of view, but the client effectively needs infinitely durable infinite memory to perform the "distributed transaction" of acting on the message and responding to the server. Imagine: - Server delivers message M - Client process event E entailed by message M - Client tries to ack (A)…

Basically the Two General's Problem, eh?

https://en.wikipedia.org/wiki/Two_Generals%27_Problem

Re: Delivering Billions of Messages Exactly Once

#50

Post by newobj »

Cieplak wrote: post #49
newobj wrote: post #48

I don't want to ever see the phrase "Exactly Once" without several asterisks behind it. It might be exactly once from an "overall" point of view, but the client effectively needs infinitely durable infinite memory to perform the "distributed transaction" of acting on the message and responding to the server. Imagine: - Server delivers message M - Client process event E entailed by message M - Client tries to ack (A)…

Basically the Two General's Problem, eh? https://en.wikipedia.org/wiki/Two_Generals%27_Problem

Exactly.
Post reply on HN