Yes, you can have exactly-once delivery

http://blog.rongarret.info/2024/09/yes-you-can-have-exactly-once-delivery.html

by lisper • 2 years ago

54 133 2 years ago

blog.rongarret.info

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• 2 years ago

But you sometimes delivered the bytes twice, before getting the receipt, surely?

theamk2• 2 years 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.

toast0• 2 years 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.

Filligree2• 2 years ago

You keep sending it until you get an acknowledgement back. As the article points out, this does assume nobody cut the wire.

deathanatos• 2 years 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.")

tacitusarc3• 2 years 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• 2 years 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.

jchw3• 2 years 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.

schobi• 2 years ago

Same understanding: On the receiver side, we are going to drop duplicates (by processing, or by having no effect on the grass cutting any more). Thus, the end user is then seeing only one effect, one message delivered. The effect of delivery "message received" or "grass is cut" is achieved.

But still, the sender might need to send more than once (until confirmation). From the cost at the sender "sending multiple packages" or "sending more grass cutters" this is still the scenario "send one or more".

Sorry to fuel the fire... it is about the definition of "delivery"

theamk2• 2 years ago

We are talking network stack, so there is no actions - just data hand-off to the actual application code.

Someone arrives at your house, gives you a package, says "this is order 123". You thank them, they leave, but then they are hit by a car before they can report this. You unpack the package and use it.

Next day, someone else arrives at your house, gives you a package, says "this is order 123". You thank them, they leave. You know you've already received order 123, so you throw package away without even taking it into the house.

This happens few more times, but you don't care, your trash can is big.

Done! You now have "exactly once delivery".

Now, some might argue this is "exactly once processing" and you should only count what the delivery person does.. but this depends on where you draw the boundary. I draw it at "I am taking the package into the house", and I've only ever took one package there, so it was exactly-once for me.

The key part here is cost. I am assuming that opening package and using its contents is hard and takes a long time; while answering the door and throwing the package away is easy. This is definitely the case with modern networking stack, which re-transmits stuff all the time, and where the loss rate is very low.

tacitusarc3• 2 years ago

As this is a semantic debate over the definition of delivery, I asked my very non-technical wife if she thought in the scenario you described, the package was delivered exactly once. She said obviously not, and this discussion is very stupid, and I should stop participating in it. So there’s that.

jongjong2• 2 years 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.

qaq4• 2 years ago

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

lisper42• 2 years 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."

jongjong2• 2 years 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.

nhumrich• 2 years ago

You seem to be missing the point though. Wanting "exactly once delivery" in practice is like saying, "I shouldn't need to worry about dedupes at the application level". Which is everyone's dream, but the seniors are saying, "yes, you have to handle it at the application level, there is no way around that".

qaq4• 2 years 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.

lisper42• 2 years ago

You apparently missed this part:

two_handfuls6• 2 years 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.

computerfan4944• 2 years 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.

bhaney2• 2 years 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.

Groxx3• 2 years 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• 2 years 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.

philipswood• 2 years ago

So if you build systems using messaging middleware you get to choose upfront whether you are going to use XA with exactly-once semantics and pay the performance penalty for that or whether you will implement your business logic idempotently on processing instead.

You can do this across a whole landscape of vendors.

So this whole class of "that's impossible" responses sounds to me (as an ex-brick layer) like "obviously you can't stack bricks next to each other perfectly straightly - so building walls is clearly impossible".

So it feels a bit jarring when several vendors allow you to do this impossible thing.

Google for JMS and exactly-once and you can find documentation with several products on exactly how to do this.

One example: https://www.atomikos.com/Blog/TheSimpleSecretOfExactlyOnceDe...

sam_lowry_• 2 years ago

Gosh, only after this comment I understood why so many programmers litter the code with retries, even though they seem superfluous.

Spivak• 2 years ago

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 processing bit so that from the perspective of your application code it really is exactly-once.

bhaney2• 2 years ago

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

Those people would be better served by approximately two sentences clarifying that exactly-once processing is a different thing that can be achieved with at-least-once delivery and idempotency, rather than 20+ rambling paragraphs of redefining formal terms.

Ferret7446• 2 years ago

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

jchw3• 2 years ago

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?

jhanschoo• 2 years ago

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.

My understanding is that these happen IRL all the time in the guise of healing a network split or rebooting crashed nodes or bring new uninitialized servers into the system. Of course, IRL you usually translate the result to needing a different strategy to bring these systems up to speed beyond a certain threshold. But these thresholds and strategies and changing the number of nodes in the system are application-dependent, so the fiction of unbounded messages/memory/time helps focus the formal analysis and result.

In the context of, say, a distributed KV store, it cautions you that unless you have said other strategy, you will end up with an inconsistent system or failure state if your message buffers are more space-constrained than required.

Izkata• 2 years ago

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.

This is exactly where the argument is coming from. The same people who will say "you can get at most once or at least once, but not only once" don't realize they're doing the exact same thing as the "you can get only once" people, when they criticize the conflation of delivery and processing. They'll argue "delivery" and "processing" have to be kept separate because of memory/storage/bandwidth/etc it uses up in the retries, which is why "only once delivery" can't exist and they actually mean "only once processing", but if you keep that reasoning in mind, there's also no such thing as "at least once delivery" - you'll run out of something at some point (or even just hit your retry limit) and have to drop the retries, resulting in no delivery.

The people saying you can get "only once delivery" by using "at least once"+idempotency are working under other group's definitions, then getting annoyed when the definitions are changed so this implementation of "only once" isn't allowed.

lisper42• 2 years 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.

pyrolistical2• 2 years ago

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

lisper42• 2 years 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".

mlyle14• 2 years ago

The problem is, you're using strong language like "under any reasonable definition of 'delivery'." But everyone else is defining delivery differently than you, referring to the delivery of the message to the system itself. Your language implies everyone else is unreasonable.

When your argument depends upon everyone else being unreasonable, maybe you're the one being unreasonable.

Yes, we can make the processing that occurs in response to those delivered message(s) idempotent. But in the end, the system has to either deal with:

1. messages being delivered once or lost entirely, or

2. messages being delivered once or multiple times

You are over-explaining a way to deal with situation #2 (detect duplicates at the endpoint).

lisper42• 2 years ago

referring to the delivery of the message to the system itself

And how do you define "the system itself"?

stackghost5• 2 years ago

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.

lisper42• 2 years ago

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?

tacitusarc3• 2 years ago

Right, but the meaning of “delivery” in human communication is still different from how you are using it…

lisper42• 2 years ago

I disagree. If I'm an actual general in a fort with a gate, and I tell the gate guards to inspect messages brought in by couriers and not allow couriers carrying duplicate messages to enter, the ones that the guards let through are still delivering those messages to me.

noaoh• 2 years ago

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.

bigstrat2003• 2 years ago

I'm sorry people are being such utter jerks about this. Honestly, the comments on this are an embarrassment. Even if you are wrong, there's absolutely no call for the tone a lot of the comments are taking.

lisper42• 2 years ago

Thanks.

Jach2• 2 years ago

This has been a fun thread to read, though not reflecting highly on HN. For what it's worth, I agree with you that the original adage kicking this off is kind of silly, and basically wrong. For further enjoyment I found this interesting blog post from another PhD that addresses things more comprehensively (and also basically agrees with you): https://www.mydistributed.systems/2021/10/exactly-once-deliv...

The opening lines include: "The exact definition, however, is not agreed upon in the community. As a result, there is a debate on whether EOD is possible or impossible to achieve." If nothing else, I and probably others learned today that this is apparently a debate that can quickly turn into a flamewar. And I thought flamewars were mostly dead!

Another interesting paper that came up, as I have an interest in TLA+ proofs: "LogPlayer: Fault-tolerant Exactly-once Delivery using gRPC Asynchronous Streaming" https://arxiv.org/abs/1911.11286 It seems there's no problem in the community to do things like prove fault-tolerant exactly-once delivery, even if such terminology isn't universally agreed on.

lisper42• 2 years ago

Thank you for that link! You just saved me a lot of time reinventing that wheel.

lukeasrodgers• 2 years 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.

stackghost5• 2 years 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".

lisper42• 2 years 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.

stackghost5• 2 years 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.

brigadier1323• 2 years 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...

lisper42• 2 years ago

It seems like this person does not understand what exactly once delivery actually means.

Then by all means, enlighten me.

brigadier1323• 2 years 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.

benreesman• 2 years 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.

upeguiborja2• 2 years ago

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

lisper42• 2 years ago

Yes, that's true, but that's often a reasonable assumption.

upeguiborja2• 2 years 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.

jumploops• 2 years 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• 2 years 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_handfuls6• 2 years 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• 2 years 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.

Yes, you can have exactly-once delivery

Related Stories