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

121–130 of 141 posts

Re: Delivering Billions of Messages Exactly Once

#121

Post by yomritoyj »

vacri wrote: post #107
Cieplak wrote: post #49

Earlier quoted context omitted.

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

> Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. This isn't true. There is a point where both sides have confirmed receipt of the last new info (the original confirmation back to the initial sender), and further confirmation is just icing. What kind of genera…

It is the acknowledgement of the receipt of the last message that is important. Wikipedia is not entirely clear on this one. The source of the problem are higher-order statements: "A knows that B knows that A knows ...".

Suppose A sends the message to B, B sends an ack to A but A's ack back to B is lost. Now both A and B know the time of the attack but B considers it possible that [A does not know that B knows]. B thinks if A really does not know that B knows then A may not attack out of the consideration of the possibility that B does not know. And this possibility may make B call off the attack even if B knows.

Each round of successful exchange increase the order of statements that are known, but there is a statement of higher order which is still not known and which can cause the attack to unravell inductively.

Look up 'Rubinstein's e-mail game' for a choice of payoffs that causes no attack to happen for any positive probability, howsoever small, of a message getting lost.

Re: Delivering Billions of Messages Exactly Once

#122

Post by pfarnsworth »

Sounds very cool. A couple of questions I had:

1) What happens if they lose their rocksdb with all of the messageIds?

2) Is their kafka atleast-once delivery? How do they guarantee that kafka doesn't reject their write? Also, assuming they have set up their kafka for at least once delivery, doesn't that make the output topic susceptible to duplicates due to retries, etc?

3) >Instead of searching a central database for whether we’ve seen a key amongst hundreds of billions of messages, we’re able to narrow our search space by orders of magnitude simply by routing to the right partition.

Is "orders of magnitude" really correct? Aren't you really just narrowing the search space by the number of partitions in kafka? I suppose if you have a hundred partitions, that would be 2 orders of magnitude, but it makes it sound like it's much more than that.

Re: Delivering Billions of Messages Exactly Once

#123

Post by wuch »

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

I would say this problem is quite different than Two Generals, because client doesn't need to know that acknowledgment has been received, i.e., a solution doesn't require the receipt of message to be common knowledge. It it sufficient that server stops trying to send the message once it has received the ACK.

Re: Delivering Billions of Messages Exactly Once

#124

Post by wuch »

wenc wrote: post #114
Spearchucker wrote: post #96

Earlier quoted context omitted.

The protocol is in fact quite simple: 1. Sender sends message. 2. If no acknowledgement from recipient is returned to sender, resend message until an acknowledgement is received from recipient. 3. If recipient receives message, check store to see if it's been received before. 4. If it's not in the store, store it, acknowledge receipt to sender, and process it. 5. If it's already in the recipient's store, acknowledge…

What if the "acknowledge receipt to sender" message gets lost?

Server will keep trying to send the message. Each time the client responds with receipt. Eventually communication succeeds and protocol is done. The major drawback is requirement of persistent storage on the client.

Re: Delivering Billions of Messages Exactly Once

#125

Post by Spearchucker »

wuch wrote: post #124
wenc wrote: post #114

Earlier quoted context omitted.

What if the "acknowledge receipt to sender" message gets lost?

Server will keep trying to send the message. Each time the client responds with receipt. Eventually communication succeeds and protocol is done. The major drawback is requirement of persistent storage on the client.

That's not a drawback - it's an advantage. It enables store-and-forward, i.e. on- and offline use. The client remains functional without a connection to the server.

Re: Delivering Billions of Messages Exactly Once

#126

Post by goldenkey »

bmsatierf wrote: post #38

In terms of connectivity, we deal with a similar problem here at CloudWalk to process payment transactions from POS terminals, where most of them rely on GPRS connections. Our network issues are nearly 6 times higher (~3.5%) due to GPRS, and we solved the duplication problem with an approach involving both client and server side. Clients would always ensure that all the information sent by the server was successfully…

lòok maah no race cawnditions!!

Re: Delivering Billions of Messages Exactly Once

#127

Post by xenadu02 »

wbl wrote: post #105
rusanu wrote: post #99

Earlier quoted context omitted.

> it's still something that has to be dealt with somewhere Database programmers have the means to deal with it off-the-shelf: BEGIN TRANSACTION ... COMMIT. When your queues are in the database, this becomes trivial. Even without the system I'm talking about (Service Broker) that has the queues stored in the database, most regular messaging systems do support enrolling into a distributed transaction and achieve an ato…

But the application still has to deal with processing the same message twice if it dies before ACK.

The ACK is also a transaction. Something like this:

1. Receive from server, commit state = NEW, UNACK 2. Send ACK to server, get confirmation from server, commit state = NEW, ACK 3. Start processing, commit state = PROC 4. Got results, commit state = FIN, UNACK 5. Send FIN to server, commit state = FIN, ACK

Each commit is a database transaction where you write the results of that step along with the new state. If anything fails along the way the work-in-progress is discarded along with the state change. The server has an equivalent so if it gets a duplicate ACK for the same (or earlier) state it can ignore it.

In this example, if the client crashes between 1-2, in #2 never gets confirmation, or crashes trying to commit the "NEW, ACK" state then it will retry. The server has already committed the fact that it sent the value to the client and is awaiting an ACK. If it saw the ACK and gets a duplicate it ignores it. If it never saw the first ACK then it will see the second(+) attempt and commit that it saw the ACK before sending confirmation to the client.

Re: Delivering Billions of Messages Exactly Once

#128

Post by spullara »

tejasmanohar wrote: post #103
spullara wrote: post #47

This isn't the solution I would architect. It is much easier to de-duplicate when processing your analytics workload later and you don't need to do so much work.

That's not true for all the hundreds of real-time integrations that Segment sends data to. Many are write-only.

Fair. For that case this solution makes more sense than the pure analytics case.

Re: Delivering Billions of Messages Exactly Once

#129

Post by vacri »

yomritoyj wrote: post #121
vacri wrote: post #107

Earlier quoted context omitted.

> Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. This isn't true. There is a point where both sides have confirmed receipt of the last new info (the original confirmation back to the initial sender), and further confirmation is just icing. What kind of genera…

It is the acknowledgement of the receipt of the last message that is important. Wikipedia is not entirely clear on this one. The source of the problem are higher-order statements: "A knows that B knows that A knows ...". Suppose A sends the message to B, B sends an ack to A but A's ack back to B is lost. Now both A and B know the time of the attack but B considers it possible that [A does not know that B knows]. B th…

There comes a point in the chain where both sides have got the initial message, and confirmation that the other side has confirmed the message.

message 1 -> attack!

message 2 -> sure!

message 3 -> I got your sure! At this point, general A knows the message got through

message 4 -> I got your confirmation! At this point, general B knows that general A got the reply

message 5 -> I got your confirmation confirmation! At this point, general A is sure that both parties know when the attack is. General A knows that the confirmation got through, and Gen A is good to go.

message 6 -> conf^n! At this point, General B knows that the confirmation got through, and Gen B is good to go.

message 7 => icing

Even if message 6 doesn't get through, message 2 and 4 have, so general A knows that both generals know. Message 3 tells general B that both generals know - all that's missing is the nice-to-have confirmation.

You don't need to keep on confirming the last message ad infinitum, because that doesn't add new data about the original message and who knows it. If messenger 77 were to be captured by the city, it's not like the generals would call off the attack because they weren't sure of the timing info.

Perhaps another way of putting it: this isn't a continuous string of information that gets added to. It's a set of discrete parcels of information. The additional messages only add information about the veracity of the later parcels, not the initial ones.

Re: Delivering Billions of Messages Exactly Once

#130

Post by maffydub »

vacri wrote: post #129
yomritoyj wrote: post #121

Earlier quoted context omitted.

It is the acknowledgement of the receipt of the last message that is important. Wikipedia is not entirely clear on this one. The source of the problem are higher-order statements: "A knows that B knows that A knows ...". Suppose A sends the message to B, B sends an ack to A but A's ack back to B is lost. Now both A and B know the time of the attack but B considers it possible that [A does not know that B knows]. B th…

There comes a point in the chain where both sides have got the initial message, and confirmation that the other side has confirmed the message. message 1 -> attack! message 2 -> sure! message 3 -> I got your sure! At this point, general A knows the message got through message 4 -> I got your confirmation! At this point, general B knows that general A got the reply message 5 -> I got your confirmation confirmation! At…

The point is that it's not just about knowledge - it's about agreement.

A and B must not attack alone, i.e. A must not attack if B is not going to attack, and B must not attack if A is not going to attack.

Now, message 1 (from A to B) says "attack!". So B knows that A wants B to attack.

...but A mustn't attack alone, so A won't attack unless A receives B's confirmation. So B sends message 2 ("sure!").

...but B mustn't attack unless B knows that A is going to attack, and A will only attack if A has received message 2. So A has to send another message to confirm receipt of message 2.

...and so on.

None of these confirmations are simply "nice-to-have" - if you need to be 100% sure that you're both going to attack, you need to ensure that every confirmation you send has been received by your peer.

Post reply on HN