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

Yes, you can have exactly-once delivery

blog.rongarret.info

Post reply on HN
Print view View original

41–50 of 140 posts

Re: Yes, you can have exactly-once delivery

#41

Post by jchw »

bhaney wrote: post #11

In case you're someone who actually knows anything about distributed systems and you're not looking forward to slogging through this long article filled with claims like "I have a PhD in AI so I know what I'm talking about" to find where the author made their mistake, let me save you the time. It's the typical conflation of exactly-once delivery with exactly-once processing, which the author acknowledges and then cho…

Honestly, I really do find the traditional nomenclature to be a little pointless. It seems like the classic saying assumes that it's somehow okay to assume infinite time for re-delivery, but not infinite memory for memoization for some reason. On the other hand, in real life there aren't unlimited numbers of messages and you rarely want to accept infinitely stale messages either, so it's a bit moot. I'd go as far as to say that in practice you really can't guarantee a message will be delivered and processed because you will have finite bounds on time, the absolute best you can do is at least guarantee that it either was definitely processed once or probably was not and handle it accordingly. (I formerly wrote "definitely" for the latter, thinking you could do this with two-phase commit, and then realized after walking away from the computer that you absolutely can't guarantee that, of course. Distributed systems are such a pain to reason about.)

Do I misunderstand?

Re: Yes, you can have exactly-once delivery

#42

Post by lisper »

stackghost wrote: post #24
lisper wrote: post #14

Author here. Most commenters still seem to be missing the point, despite the fact that I explicitly say this in the opening sentence: "This post is ostensibly about an obscure technical issue in distributed systems, but it's really about human communications." and reiterate it at the end: "This post was intended to be about human communication more than distributed systems or network protocols." I really don't know h…

Your proposed definition of "delivery" is absurd. If you have duplicate things, then you've clearly been delivered more than one thing. There is no way to deliver something exactly once, and yet the receiver has more than one thing such that they can throw all but one thing away. It's okay to admit you were mistaken.

> If you have duplicate things, then you've clearly been delivered more than one thing.

Yes, that's true. But this doesn't turn on what "delivery" means, it turns on what "you" means. If "you" are downstream of a de-duplication mechanism, then "you" can get exactly once-delivery. Why is that so absurd?

Re: Yes, you can have exactly-once delivery

#43

Post by dragonwriter »

lisper wrote: post #25
pyrolistical wrote: post #18

Earlier quoted context omitted.

Don’t use technical terms like “exactly-once delivery” if you don’t have want it to be interrupted as technical

It is hard to make the point that "exactly-once delivery" is not a technical term without referring to it. If you think it is a technical term, would you kindly point me to a definition? I'm particularly interested in learning how "exactly-once delivery" is distinguished from "exactly-once processing".

Draw a diagram containing a source system, a destination system, and an unreliable communication channel between them. The destination system also has an output with no unreliable communications channel.

Exactly-once delivery means that a message sent from the source system reaches the destination system exactly once, and its result reaches the output channel exactly once as a consequence.

Excactly-once processing means that a message sent from the source system produces the expected output from the destination system once, even though it may be received by the destination system more than once.

(That's a little sloppy because it could use more discussion of the conditions in which it won't be received zero times, and how those are different between exactly-once and at-most-once delivery, but that's mostly beside the point because it isn't part of the distinction between exactly-once delivery and exactly-once processing. And, while definitely technical, they always involved a somewhat idealized view of the destination system, because all communications channels, including those internal to a single device, have some degree of unreliability.)

Re: Yes, you can have exactly-once delivery

#44

Post by computerfan494 »

lisper wrote: post #42
stackghost wrote: post #24

Earlier quoted context omitted.

Your proposed definition of "delivery" is absurd. If you have duplicate things, then you've clearly been delivered more than one thing. There is no way to deliver something exactly once, and yet the receiver has more than one thing such that they can throw all but one thing away. It's okay to admit you were mistaken.

> If you have duplicate things, then you've clearly been delivered more than one thing. Yes, that's true. But this doesn't turn on what "delivery" means, it turns on what "you" means. If "you" are downstream of a de-duplication mechanism, then "you" can get exactly once-delivery. Why is that so absurd?

You're correct, but in my experience the vast majority of code written is not downstream of a usable de-duplication mechanism.

Re: Yes, you can have exactly-once delivery

#45

Post by noaoh »

lisper wrote: post #14

Author here. Most commenters still seem to be missing the point, despite the fact that I explicitly say this in the opening sentence: "This post is ostensibly about an obscure technical issue in distributed systems, but it's really about human communications." and reiterate it at the end: "This post was intended to be about human communication more than distributed systems or network protocols." I really don't know h…

I had a similar thought as what's in your post, but didn't share because I thought the reaction would be something like this. I personally would word this as you can achieve exactly once semantics by combining at least once delivery with idempotency.

Re: Yes, you can have exactly-once delivery

#46

Post by two_handfuls »

jongjong wrote: post #31
qaq wrote: post #12

Earlier quoted context omitted.

you can't in general case because you don't have infinite memory for dedupe.

Good point but you don't need infinite memory. You can set expiries to discard, for example. Expiries and timeouts can be defined as part of the protocol. You can impose reasonable constraints per-socket on the buffer size for spam prevention. There is a lot of wiggle room. On the sender side, you can require an ACK response for each message UUID and rebroadcast only if the ACK is not received within a certain timefr…

Right, but all this assumes timing guarantees that are not present in the original impossibility result.

Re: Yes, you can have exactly-once delivery

#47

Post by Ferret7446 »

Spivak wrote: post #36
bhaney wrote: post #11

In case you're someone who actually knows anything about distributed systems and you're not looking forward to slogging through this long article filled with claims like "I have a PhD in AI so I know what I'm talking about" to find where the author made their mistake, let me save you the time. It's the typical conflation of exactly-once delivery with exactly-once processing, which the author acknowledges and then cho…

This article isn't for you then, this article is for people who have casually heard that exactly once delivery is impossible and take it to mean exactly once processing is impossible. When someone talks about at-least-once and at-most-once in the context of well-known queueing systems they say will say delivery but will mean processing, because as you say, they're the same in practice. You typically hide the processi…

I think the words "delivery" and "processing" are taught around middle school. There's probably no need to have an article for it.

Re: Yes, you can have exactly-once delivery

#48

Post by warkdarrior »

jchw wrote: post #13
valzam wrote: post #8

Earlier quoted context omitted.

In particular what exactly once delivery implies that I do not have to worry about it in my processing logic. I can build a `count += 1` and it will always be exactly correct. The notion that there is no distinction between exactly once delivery and exactly once processing is very odd to me. In practice my processing needs to accommodate duplicates to be correct. If I had exactly once delivery my processing could be…

The point is that it doesn't matter exactly where the deduplication matters. It could happen in your own processing code, or something upstream of it, like a queue library of some kind. That's pretty much what the entire article is saying; it's hard to meaningfully distinguish what part is actually delivery versus processing. e.g. most people would consider the guarantees imparted by the TCP stack are indeed part of…

> The point is that it doesn't matter exactly where the deduplication matters.

Actually the point is that once deduplication is done at some layer, the layers above it will have to re-achieve exactly-once delivery.

"Yes, the TCP layer did deliver this message only once, but the receiving software crashed right after, so now the sender has to send it again."

Re: Yes, you can have exactly-once delivery

#49

Post by srkiNZ »

lisper wrote: post #42
stackghost wrote: post #24

Earlier quoted context omitted.

Your proposed definition of "delivery" is absurd. If you have duplicate things, then you've clearly been delivered more than one thing. There is no way to deliver something exactly once, and yet the receiver has more than one thing such that they can throw all but one thing away. It's okay to admit you were mistaken.

> If you have duplicate things, then you've clearly been delivered more than one thing. Yes, that's true. But this doesn't turn on what "delivery" means, it turns on what "you" means. If "you" are downstream of a de-duplication mechanism, then "you" can get exactly once-delivery. Why is that so absurd?

If "you" are "downstream" of a "de-duplication mechanism" how do you ensure "exactly once delivery" between "you" and the "de-duplication mechanism"?

Re: Yes, you can have exactly-once delivery

#50

Post by two_handfuls »

lisper wrote: post #19
qaq wrote: post #9

Well pretty confused. You can't get exactly once delivery using proposed solution in general case because you can not have infinite memory for dedupe.

You apparently missed this part: "Just for the sake of completeness I should point out that removing duplicates at the receiver is a pretty extreme oversimplification of what you would do in practice to provide exactly-once delivery. A complete solution would almost certainly be an example of Greenspun's Tenth Law applied to the TCP protocol rather than Common Lisp."

Can you explain this point? I think you are trying to say the application would include an implementation of TCP? I don't see how this is related to memory.
Post reply on HN