8 ms·

Yes, you can have exactly-once delivery

54 points by lisper 2y ago

supportengineer 2y ago
Over 20 years ago I worked with some specialized commercial software, Cyclone, that did guaranteed delivery of files. Guaranteed as in the legal sense. If the server sent back a ticket number to the sending client, it was a LEGAL assurance that the file was received, because there was a contract in place with financial penalties. The time stamps were particularly important in the legal contract. So, there are a lot of ways you can have exactly-once delivery, especially when talking about the application level of the 7 layer burrito model.
- hinkley 2y ago
  But you sometimes delivered the bytes twice, before getting the receipt, surely?
  - theamk 2y ago
    I am sure there were some duplicate packets on the wire - it's a normal part of most network protocols. The important thing is that as far as user was concerned, it was exactly-once.
deleted 2y ago
[deleted]
toast0 2y ago
I don't see how you can guarantee at least one delivery, but maybe I've seen too many things disappear off busses, never to be seen again.
- Filligree 2y ago
  You keep sending it until you get an acknowledgement back. As the article points out, this does assume nobody cut the wire.
  - deathanatos 2y ago
    SEND --> SEND --> <-- ACK <-- ACK (this node was *suuuper* slow due to page thrashing.) Don't try to "fix" it, either; there's no way to do that. You make the job idempotent, in some manner: make it such that receiving the message and processing it twice is safe. (This is what TFA eventually capitulates to, but tries to call it "exactly once delivery", even in cases where deliver is occurring more than once. I don't think this view is pedagogically useful, which is partly why we say "exactly once delivery is impossible.")
tacitusarc 2y ago
I appreciate the insights here, but I am struggling to understand how “exactly one” can equate to “eliminate duplicates”. Let’s say someone arrived at my house and cut my grass, and I failed to confirm they had done so, so the company sent someone over to cut my grass again, maybe multiple times. It seems silly to claim my grass was cut exactly once, despite it consistently remaining at the same height. Obviously it was cut multiple times, just not with much effect after the first. The point of exactly-once is that the server and client don’t need to expend pointless effort on duplicates… right?
- valzam 2y ago
  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 much simpler. If I could get exactly once delivery for free I would always choose it in a heartbeat.
  - jchw 2y ago
    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 delivery and not processing, but your TCP stack is having to do a lot of processing work to actually maintain the logical stream of bytes.
    - warkdarrior 2y ago
      > 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."
jongjong 2y ago
Yes of course you can have exactly once delivery if you clearly define who/what the receiver is. You can easily deduplicate messages on the receiving end based on UUIDs created by the sender for example... Since they are duplicates of the exact same message, it doesn't matter which one is 'the original'. It makes sense to worry about this only if you're worried about wasting bandwidth in the event of network instability (since the same message may sometimes traverse the network multiple times) but that's not generally something engineers should worry about. It's ironic how some people use this to try to talk down to 'junior' developers. Anyone can memorise hearsay about distributed systems but few can speak from experience.
- qaq 2y ago
  you can't in general case because you don't have infinite memory for dedupe.
  - lisper 2y ago
    You apparently missed this: "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."
  - jongjong 2y ago
    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 timeframe. You don't necessarily need a sophisticated algorithm to get a good practical solution which solves real problems.
    - two_handfuls 2y ago
      Right, but all this assumes timing guarantees that are not present in the original impossibility result.
qaq 2y ago
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.
- lisper 2y ago
  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."
  - two_handfuls 2y ago
    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.
    - lisper 2y ago
      I was responding to this: > You can't get exactly once delivery using proposed solution in general case because you can not have infinite memory for dedupe. That is a specific criticism of a specific and highly oversimplified algorithm for de-duplication that I described purely for illustrative purposes, not as a suggestion for how de-duplication should actually be implemented. Actual implementation of de-duplication is much more complicated, but a solved problem that I didn't think I needed to rehash. A real implementation doesn't require infinite memory. (Actually, even the naive algorithm doesn't require infinite memory, just unbounded memory. Those are not the same.)
      - qaq 2y ago
        You certainly do need to rehash it or provide a link to it being solved without constraints on time window, msgs rates and msgs sizes. You also most certainly want to build it and provide it as service because no existing product claims this capability in unbounded case.
computerfan494 2y ago
At the end of the day the author and those they are arguing with mostly agree, they simply disagree on what the word "delivery" means. Given the author's background, I wonder if the issue is that they're focused mainly on lower levels of the stack, while those who disagree mainly work with traditional applications that do things like send email, respond to webhooks, update databases, etc. The reason I think it's important to be pedantic about distinguishing between "delivery" and "processing" is that I have seen plenty of higher level systems that have incorrectly not implemented idempotency and had bugs as a result. I have seen many folks be confused by Kafka's "Exactly-Once Semantics" feature and introduce major bugs into message processing pipelines. The author, who clearly understands these fundamental design challenges, is not my problem. It's everyone else who struggles to design safe, idempotent exactly-once systems.
bhaney 2y ago
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 chooses to ignore because they're basically the same for practical purposes, as if this somehow changes the reality of the delivery itself and the restrictions on its guarantees. Yes, everyone knows you can layer an idempotency mechanism on top of at-least-once delivery to achieve exactly-once processing (so long as you're willing to tie up memory/storage for an infinite amount of time). But this does not equate to exactly-once delivery, and you know that.
- Groxx 2y ago
  Yea... this is kinda inflammatory but I honestly have to agree with it. The post largely summarizes as "you can have exactly-once delivery if you re-define it to be at-least-once processing with idempotency". Those are different things. In fact, that's the entire point behind saying that it's impossible. You can't design a system that is exactly-once at any level, so don't even bother trying. If someone wants you to guarantee something will happen, you can point to that impossibility to say "you need to retry, it's not optional, and anyone who tells you otherwise is lying to you". That has happened to me multiple times in my career; it's a thing charlatans keep trying to sell to businesses, and businesses eat it up because it sounds so much magically simpler than what their engineers keep telling them needs to be done. Because it is magic. It doesn't exist.
  - EGreg 2y ago
    This is sorta like the argument about CAP impossibility theorem while in practice consensus algorithms work 99.999% of the time. Or like Shannon’s information theory showing impossibility of compression, while many compression algorithms work well on actual data. This seems to me the same. In practical applications, you can indeed have the at-least-once delivery with an idempotency / backpressure system, and work 99% of the time, and be unavailable 1% of the time.
lisper 2y ago
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 how I could have made this any clearer.
- pyrolistical 2y ago
  Don’t use technical terms like “exactly-once delivery” if you don’t have want it to be interrupted as technical
  - lisper 2y ago
    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".
    - mlyle 2y ago
      A 4 year old piece laying out the exact difference as it's understood and how people use the terms: https://blog.bulloak.io/post/20200917-the-impossibility-of-exactly-once/ https://blog.bulloak.io/post/20200917-the-impossibility-of-e... I read similar content at least 2 decades ago... > While exactly-once-delivery is not possible, we have a way out: Exactly-once processing. Exactly-once processing is the guarantee that even though we may receive a message multiple times, in the end, we observe the effects of a single processing operation. This can be achieved in two ways: > Deduplication: dropping messages if they are received more than once > Idempotent processing: applying messages more than once has precisely the same effect as applying it exactly once (I view deduplication as a special case of idempotency).
      - lisper 2y ago
lukeasrodgers 2y ago
Here is my understanding, roughly: - say you need a messaging system to communicate between different components - that messaging system is a 3rd party library or tool, it has no knowledge of your needs or architecture - therefore it can have no knowledge of what counts as a duplicate message, it either just blasts your message off once, or blasts them off until it gets an ack, it is up to the software you build around this component to avoid duplicate processing - so yes of course you can build "exactly once processing" on top of an "at least once delivery" system - but it still makes sense to talk about the distinction between delivery and processing, and "exactly once delivery is impossible" is still (in OP's terms) a "useful" claim I haven't personally used kafka but it and similar systems (I vaguely recall some work by Pat Helland that may fall into a similar bucket) could possibly be said to a) constitute messaging systems, b) provide exactly once delivery semantics, in that they are less of a library and more of a framework that provide a concept of "duplicate message" that you basically buy into by using those systems. You could then argue that "if it provides exactly once delivery it is not a messaging system", maybe there's a good argument there or maybe it's just pedantry.
stackghost 2y ago
>a simple matter of keeping track of all the delivered messages and removing duplicates Ron, if you have received duplicate messages then by definition you have been delivered that message more than once. I don't have a PhD in computer science so maybe you can explain how this constitutes "exactly once".
- lisper 2y ago
  > if you have received duplicate messages then by definition you have been delivered that message more than once Yes. So? If you don't include a mechanism for ensuring exactly-once delivery then you will not be guaranteed exactly-once delivery. But if you do, you will. It doesn't actually require a Ph.D.
  - stackghost 2y ago
    >> if you have received duplicate messages then by definition you have been delivered that message more than once >Yes. Okay, I'm glad we agree that delivering something multiple times and discarding the duplicates is not exactly-once delivery.
    - lisper 2y ago
      As you have described it, you are right, it's not. But presumably the thing discarding the duplicates then does something with the non-duplicates, like deliver then to something else. That is exactly-once delivery.
      - stackghost 2y ago
        You wrote in the post: >This post was intended to be about human communication more than distributed systems or network protocols But resorting to technical minutiae as you have done doesn't seem germane to "human communication". Honestly, seeing such mental gymnastics just to avoid losing face on an internet argument is really disappointing.
brigadier132 2y ago
It seems like this person does not understand what exactly once delivery actually means. It's not about being able to do something exactly once if the author is reading this...
- lisper 2y ago
  > It seems like this person does not understand what exactly once delivery actually means. Then by all means, enlighten me.
  - brigadier132 2y ago
    I don't want to get into a debate over semantics with you. You've redefined exactly once delivery to mean that if you have a layer of abstraction that hides that a message was delivered multiple times then it is "exactly once" delivery. That's not what exactly once delivery is. You clearly disagree but taking well understood and researched terms and redefining them to make a point is a complete waste of time for everyone. Nobody cares about what your personal definition of exactly once delivery is, they care about the definition that is used in literally all of distributed systems research.
    - lisper 2y ago
      I'm not asking for a debate. I'm simply asking you to tell me what "exactly once delivery" actually means in a way that isn't circular and doesn't beg the question of whether or not it is possible, i.e. the definition that is used in literally all of distributed systems research. So far no one has been able to do that.
      - Filligree 2y ago
        Delivery is what happens when the signals cross from the wire into the network interface card. Depending on the layer you’re operating on, you might instead say it’s the call to recv, or the DMA transfer. The point is that it’s logically a memcpy with no further processing. Just a memcpy. The physical data transfer. It’s easy to build a reliable message-passing system on top of that, but any such system will either involve further processing or else be vulnerable to data loss.
benreesman 2y ago
This stuff is studied to hell and back, there is a formalism. This stuff is practiced at staggering scale and the heuristics and cheat-while-no-one-looks stuff is gamed to within an inch of its life. There is an acknowledged nexus of the two in the public domain: https://jepsen.io/consistency https://jepsen.io/consistency.
upeguiborja 2y ago
It is only possible if the channel between your "abstraction layer" (call it another system, processing, etc) and your receiver is 100% reliable.
- lisper 2y ago
  Yes, that's true, but that's often a reasonable assumption.
  - upeguiborja 2y ago
    The main confusion I see is that at-least-once delivery on a 99% reliable channel can be erroneusly called exactly once delivery 99 out of 100 times. It could be reasonable depending on the scale of your communication exercise, but if you have hundreds of thousands of receivers then asumption will surely start to fail.
    - lisper 2y ago
      The kind of reliability I'm talking about where "100% reliable" is a reasonable assumption is inside the boundaries of a single server, i.e. a CPU, memory bus, and I/O peripherals including a NIC and non-volatile storage. Yes, things can and do fail inside that boundary, but if you start taking that into account things get much more complicated. You are also no longer in the realm of distributed systems at that point, which is the context in which the controversy about exactly-once delivery arises.
jumploops 2y ago
If I receive multiple hamburgers via DoorDash, but only eat one, it’s not “exactly-once delivery.” The extra step where I give my neighbor(s), compost, or otherwise discard the N+1 hamburgers is a processing step. My house can only hold so many hamburgers, and I can only process so many after eating my lucky chosen one. This is what we (distributed systems thinkers) refer to when we say “delivery” — anything after the DoorDash step is up to us, the consumer, to process. Yes, this definition is confusing to new programmers, because it makes it hard to reason about everyday systems, but it’s this exact type of definition that we need so that we can build the proper abstractions, as the author has done in his post, to make our applications behave the way we want.
Fire-Dragon-DoL 2y ago
Isn't "exactly once processing" also incorrect, since it's all always "at most once": the system could go down and never come back online, that would result in a missed processing
- two_handfuls 2y ago
  All these guarantees are of the form "if (...) then: exactly once processing." You'll find that, indeed, those assumptions must include ruling out permanent link failures.
gbonik 2y ago
So it seems it boils down to the difference between "delivery" and "processing". I think we can make this distinction formally. For a given communication channel C, we can define "delivery via C" as a message showing up successfully at the receiver end of C. This definition seems unambiguous. Now, we can phrase our "theorem" more carefully: For an arbitrary given communication channel C, exactly-once delivery via C is generally impossible. The important part here is "For an arbitrary given communication channel C". By adding a layer of deduplication on top of C, we would be constructing a new logical communication channel C', via which exactly-once delivery is indeed possible. But that would be a different channel C', not the original channel C that we were given. In this context, we can refer to delivery via C' as "processing" relative to the original channel C.

54 points by lisper 2y ago

Over 20 years ago I worked with some specialized commercial software, Cyclone, that did guaranteed delivery of files. Guaranteed as in the legal sense. If the server sent back a ticket number to the sending client, it was a LEGAL assurance that the file was received, because there was a contract in place with financial penalties. The time stamps were particularly important in the legal contract. So, there are a lot of ways you can have exactly-once delivery, especially when talking about the application level of the 7 layer burrito model.

hinkley 2y ago
But you sometimes delivered the bytes twice, before getting the receipt, surely?
- theamk 2y ago
  I am sure there were some duplicate packets on the wire - it's a normal part of most network protocols. The important thing is that as far as user was concerned, it was exactly-once.

deleted 2y ago

[deleted]

toast0 2y ago

I don't see how you can guarantee at least one delivery, but maybe I've seen too many things disappear off busses, never to be seen again.

Filligree 2y ago
You keep sending it until you get an acknowledgement back. As the article points out, this does assume nobody cut the wire.
- deathanatos 2y ago
  SEND --> SEND --> <-- ACK <-- ACK (this node was *suuuper* slow due to page thrashing.) Don't try to "fix" it, either; there's no way to do that. You make the job idempotent, in some manner: make it such that receiving the message and processing it twice is safe. (This is what TFA eventually capitulates to, but tries to call it "exactly once delivery", even in cases where deliver is occurring more than once. I don't think this view is pedagogically useful, which is partly why we say "exactly once delivery is impossible.")

tacitusarc 2y ago

I appreciate the insights here, but I am struggling to understand how “exactly one” can equate to “eliminate duplicates”. Let’s say someone arrived at my house and cut my grass, and I failed to confirm they had done so, so the company sent someone over to cut my grass again, maybe multiple times. It seems silly to claim my grass was cut exactly once, despite it consistently remaining at the same height. Obviously it was cut multiple times, just not with much effect after the first. The point of exactly-once is that the server and client don’t need to expend pointless effort on duplicates… right?

valzam 2y ago
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 much simpler. If I could get exactly once delivery for free I would always choose it in a heartbeat.
- jchw 2y ago
  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 delivery and not processing, but your TCP stack is having to do a lot of processing work to actually maintain the logical stream of bytes.
  - warkdarrior 2y ago
    > 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."

jongjong 2y ago

Yes of course you can have exactly once delivery if you clearly define who/what the receiver is. You can easily deduplicate messages on the receiving end based on UUIDs created by the sender for example... Since they are duplicates of the exact same message, it doesn't matter which one is 'the original'. It makes sense to worry about this only if you're worried about wasting bandwidth in the event of network instability (since the same message may sometimes traverse the network multiple times) but that's not generally something engineers should worry about. It's ironic how some people use this to try to talk down to 'junior' developers. Anyone can memorise hearsay about distributed systems but few can speak from experience.

qaq 2y ago
you can't in general case because you don't have infinite memory for dedupe.
- lisper 2y ago
  You apparently missed this: "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."
- jongjong 2y ago
  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 timeframe. You don't necessarily need a sophisticated algorithm to get a good practical solution which solves real problems.
  - two_handfuls 2y ago
    Right, but all this assumes timing guarantees that are not present in the original impossibility result.

qaq 2y ago

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.

lisper 2y ago
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."
- two_handfuls 2y ago
  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.
  - lisper 2y ago
    I was responding to this: > You can't get exactly once delivery using proposed solution in general case because you can not have infinite memory for dedupe. That is a specific criticism of a specific and highly oversimplified algorithm for de-duplication that I described purely for illustrative purposes, not as a suggestion for how de-duplication should actually be implemented. Actual implementation of de-duplication is much more complicated, but a solved problem that I didn't think I needed to rehash. A real implementation doesn't require infinite memory. (Actually, even the naive algorithm doesn't require infinite memory, just unbounded memory. Those are not the same.)
    - qaq 2y ago
      You certainly do need to rehash it or provide a link to it being solved without constraints on time window, msgs rates and msgs sizes. You also most certainly want to build it and provide it as service because no existing product claims this capability in unbounded case.

computerfan494 2y ago

At the end of the day the author and those they are arguing with mostly agree, they simply disagree on what the word "delivery" means. Given the author's background, I wonder if the issue is that they're focused mainly on lower levels of the stack, while those who disagree mainly work with traditional applications that do things like send email, respond to webhooks, update databases, etc. The reason I think it's important to be pedantic about distinguishing between "delivery" and "processing" is that I have seen plenty of higher level systems that have incorrectly not implemented idempotency and had bugs as a result. I have seen many folks be confused by Kafka's "Exactly-Once Semantics" feature and introduce major bugs into message processing pipelines. The author, who clearly understands these fundamental design challenges, is not my problem. It's everyone else who struggles to design safe, idempotent exactly-once systems.

bhaney 2y ago

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 chooses to ignore because they're basically the same for practical purposes, as if this somehow changes the reality of the delivery itself and the restrictions on its guarantees. Yes, everyone knows you can layer an idempotency mechanism on top of at-least-once delivery to achieve exactly-once processing (so long as you're willing to tie up memory/storage for an infinite amount of time). But this does not equate to exactly-once delivery, and you know that.

Groxx 2y ago
Yea... this is kinda inflammatory but I honestly have to agree with it. The post largely summarizes as "you can have exactly-once delivery if you re-define it to be at-least-once processing with idempotency". Those are different things. In fact, that's the entire point behind saying that it's impossible. You can't design a system that is exactly-once at any level, so don't even bother trying. If someone wants you to guarantee something will happen, you can point to that impossibility to say "you need to retry, it's not optional, and anyone who tells you otherwise is lying to you". That has happened to me multiple times in my career; it's a thing charlatans keep trying to sell to businesses, and businesses eat it up because it sounds so much magically simpler than what their engineers keep telling them needs to be done. Because it is magic. It doesn't exist.
- EGreg 2y ago
  This is sorta like the argument about CAP impossibility theorem while in practice consensus algorithms work 99.999% of the time. Or like Shannon’s information theory showing impossibility of compression, while many compression algorithms work well on actual data. This seems to me the same. In practical applications, you can indeed have the at-least-once delivery with an idempotency / backpressure system, and work 99% of the time, and be unavailable 1% of the time.

lisper 2y ago

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 how I could have made this any clearer.

pyrolistical 2y ago
Don’t use technical terms like “exactly-once delivery” if you don’t have want it to be interrupted as technical
- lisper 2y ago
  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".
  - mlyle 2y ago
    A 4 year old piece laying out the exact difference as it's understood and how people use the terms: https://blog.bulloak.io/post/20200917-the-impossibility-of-exactly-once/ https://blog.bulloak.io/post/20200917-the-impossibility-of-e... I read similar content at least 2 decades ago... > While exactly-once-delivery is not possible, we have a way out: Exactly-once processing. Exactly-once processing is the guarantee that even though we may receive a message multiple times, in the end, we observe the effects of a single processing operation. This can be achieved in two ways: > Deduplication: dropping messages if they are received more than once > Idempotent processing: applying messages more than once has precisely the same effect as applying it exactly once (I view deduplication as a special case of idempotency).
    - lisper 2y ago

lukeasrodgers 2y ago

Here is my understanding, roughly: - say you need a messaging system to communicate between different components - that messaging system is a 3rd party library or tool, it has no knowledge of your needs or architecture - therefore it can have no knowledge of what counts as a duplicate message, it either just blasts your message off once, or blasts them off until it gets an ack, it is up to the software you build around this component to avoid duplicate processing - so yes of course you can build "exactly once processing" on top of an "at least once delivery" system - but it still makes sense to talk about the distinction between delivery and processing, and "exactly once delivery is impossible" is still (in OP's terms) a "useful" claim I haven't personally used kafka but it and similar systems (I vaguely recall some work by Pat Helland that may fall into a similar bucket) could possibly be said to a) constitute messaging systems, b) provide exactly once delivery semantics, in that they are less of a library and more of a framework that provide a concept of "duplicate message" that you basically buy into by using those systems. You could then argue that "if it provides exactly once delivery it is not a messaging system", maybe there's a good argument there or maybe it's just pedantry.

stackghost 2y ago

>a simple matter of keeping track of all the delivered messages and removing duplicates Ron, if you have received duplicate messages then by definition you have been delivered that message more than once. I don't have a PhD in computer science so maybe you can explain how this constitutes "exactly once".

lisper 2y ago
> if you have received duplicate messages then by definition you have been delivered that message more than once Yes. So? If you don't include a mechanism for ensuring exactly-once delivery then you will not be guaranteed exactly-once delivery. But if you do, you will. It doesn't actually require a Ph.D.
- stackghost 2y ago
  >> if you have received duplicate messages then by definition you have been delivered that message more than once >Yes. Okay, I'm glad we agree that delivering something multiple times and discarding the duplicates is not exactly-once delivery.
  - lisper 2y ago
    As you have described it, you are right, it's not. But presumably the thing discarding the duplicates then does something with the non-duplicates, like deliver then to something else. That is exactly-once delivery.
    - stackghost 2y ago
      You wrote in the post: >This post was intended to be about human communication more than distributed systems or network protocols But resorting to technical minutiae as you have done doesn't seem germane to "human communication". Honestly, seeing such mental gymnastics just to avoid losing face on an internet argument is really disappointing.

brigadier132 2y ago

It seems like this person does not understand what exactly once delivery actually means. It's not about being able to do something exactly once if the author is reading this...

lisper 2y ago
> It seems like this person does not understand what exactly once delivery actually means. Then by all means, enlighten me.
- brigadier132 2y ago
  I don't want to get into a debate over semantics with you. You've redefined exactly once delivery to mean that if you have a layer of abstraction that hides that a message was delivered multiple times then it is "exactly once" delivery. That's not what exactly once delivery is. You clearly disagree but taking well understood and researched terms and redefining them to make a point is a complete waste of time for everyone. Nobody cares about what your personal definition of exactly once delivery is, they care about the definition that is used in literally all of distributed systems research.
  - lisper 2y ago
    I'm not asking for a debate. I'm simply asking you to tell me what "exactly once delivery" actually means in a way that isn't circular and doesn't beg the question of whether or not it is possible, i.e. the definition that is used in literally all of distributed systems research. So far no one has been able to do that.
    - Filligree 2y ago
      Delivery is what happens when the signals cross from the wire into the network interface card. Depending on the layer you’re operating on, you might instead say it’s the call to recv, or the DMA transfer. The point is that it’s logically a memcpy with no further processing. Just a memcpy. The physical data transfer. It’s easy to build a reliable message-passing system on top of that, but any such system will either involve further processing or else be vulnerable to data loss.

benreesman 2y ago

This stuff is studied to hell and back, there is a formalism. This stuff is practiced at staggering scale and the heuristics and cheat-while-no-one-looks stuff is gamed to within an inch of its life. There is an acknowledged nexus of the two in the public domain: https://jepsen.io/consistency https://jepsen.io/consistency.

upeguiborja 2y ago

It is only possible if the channel between your "abstraction layer" (call it another system, processing, etc) and your receiver is 100% reliable.

lisper 2y ago
Yes, that's true, but that's often a reasonable assumption.
- upeguiborja 2y ago
  The main confusion I see is that at-least-once delivery on a 99% reliable channel can be erroneusly called exactly once delivery 99 out of 100 times. It could be reasonable depending on the scale of your communication exercise, but if you have hundreds of thousands of receivers then asumption will surely start to fail.
  - lisper 2y ago
    The kind of reliability I'm talking about where "100% reliable" is a reasonable assumption is inside the boundaries of a single server, i.e. a CPU, memory bus, and I/O peripherals including a NIC and non-volatile storage. Yes, things can and do fail inside that boundary, but if you start taking that into account things get much more complicated. You are also no longer in the realm of distributed systems at that point, which is the context in which the controversy about exactly-once delivery arises.

jumploops 2y ago

If I receive multiple hamburgers via DoorDash, but only eat one, it’s not “exactly-once delivery.” The extra step where I give my neighbor(s), compost, or otherwise discard the N+1 hamburgers is a processing step. My house can only hold so many hamburgers, and I can only process so many after eating my lucky chosen one. This is what we (distributed systems thinkers) refer to when we say “delivery” — anything after the DoorDash step is up to us, the consumer, to process. Yes, this definition is confusing to new programmers, because it makes it hard to reason about everyday systems, but it’s this exact type of definition that we need so that we can build the proper abstractions, as the author has done in his post, to make our applications behave the way we want.

Fire-Dragon-DoL 2y ago

Isn't "exactly once processing" also incorrect, since it's all always "at most once": the system could go down and never come back online, that would result in a missed processing

two_handfuls 2y ago
All these guarantees are of the form "if (...) then: exactly once processing." You'll find that, indeed, those assumptions must include ruling out permanent link failures.

gbonik 2y ago

So it seems it boils down to the difference between "delivery" and "processing". I think we can make this distinction formally. For a given communication channel C, we can define "delivery via C" as a message showing up successfully at the receiver end of C. This definition seems unambiguous. Now, we can phrase our "theorem" more carefully: For an arbitrary given communication channel C, exactly-once delivery via C is generally impossible. The important part here is "For an arbitrary given communication channel C". By adding a layer of deduplication on top of C, we would be constructing a new logical communication channel C', via which exactly-once delivery is indeed possible. But that would be a different channel C', not the original channel C that we were given. In this context, we can refer to delivery via C' as "processing" relative to the original channel C.