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

91–100 of 140 posts

Re: Yes, you can have exactly-once delivery

#91

Post by mlyle »

lisper wrote: post #89
mlyle wrote: post #80

Earlier quoted context omitted.

Having a clear system boundary is required for analysis. Knowing that messages will be delivered 1+ times gives us a variety of ways we could choose to deal with this on the endpoint, with different vulnerabilities. (Getting "exactly once" processing usually requires making various kinds of resilience tradeoffs based on timing windows, storage requirements, etc). > It seems a bit pedantic to deny that someone can fly…

> You're calling people out by name I am? Where? > Getting "exactly once" processing usually requires making various kinds of resilience tradeoffs based on timing windows, storage requirements, etc Yes, of course. But that's not the same as "impossible".

> I was reading Hacker News a few days ago and stumbled on a comment posted by ...

Re: Yes, you can have exactly-once delivery

#92

Post by Jach »

tacitusarc wrote: post #58
theamk wrote: post #37

Earlier quoted context omitted.

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…

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.

Smart wife. My take on the whole thing is that it's not wise to reason from non-technical metaphors around packages or lawn mowing when the reality is electronic systems. I don't know if it's any wiser but what I like to do is work my way up from the basics. What does delivery mean? Start with two wires, one for signal and one for common ground. (Or just one wire, and pretend you can use earth-return reliably.) If that isn't enough to resolve what terms should mean, consider them with differential signaling. If that still isn't enough to get it, consider them with relay nodes. If at some point "delivery" has changed definitions to suddenly forbid something that previously wasn't forbidden, maybe you've made a mistake.

Re: Yes, you can have exactly-once delivery

#93

Post by jhanschoo »

jchw wrote: post #41
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…

> 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.

Re: Yes, you can have exactly-once delivery

#94

Post by sam_lowry_ »

Groxx wrote: post #20
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…

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…

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

Re: Yes, you can have exactly-once delivery

#95

Post by plorkyeran »

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 have a reliable connection between “you” and the deduplicator, then “you” aren’t receiving messages over an unreliable connection at all and so the claim that you can’t have exactly once delivery over an unreliable connection isn’t applicable in the first place. You’re receiving messages over a reliable connection and what happens upstream of that is irrelevant.

Re: Yes, you can have exactly-once delivery

#96

Post by lisper »

mlyle wrote: post #91
lisper wrote: post #89

Earlier quoted context omitted.

> You're calling people out by name I am? Where? > Getting "exactly once" processing usually requires making various kinds of resilience tradeoffs based on timing windows, storage requirements, etc Yes, of course. But that's not the same as "impossible".

> I was reading Hacker News a few days ago and stumbled on a comment posted by ...

Really? That is what causes you to question whether or not I'm acting in good faith?

If that's what you call "calling people out by name" I guess we'll just have to agree to disagree.

Re: Yes, you can have exactly-once delivery

#97

Post by mlyle »

lisper wrote: post #96
mlyle wrote: post #91

Earlier quoted context omitted.

> I was reading Hacker News a few days ago and stumbled on a comment posted by ...

Really? That is what causes you to question whether or not I'm acting in good faith? If that's what you call "calling people out by name" I guess we'll just have to agree to disagree.

The whole refusal to accept that a field could legitimately define something differently than how you prefer, and then running off to blog about it and name names... and then coming around for round II of flamewar... with ever more splitting of hairs in definitions... is not awesome.

You are especially well-answered here, I think: https://news.ycombinator.com/item?id=41599131

One reason the delivery / processing distinction exists because very often the application needs to atomically persist "I have received this message" with any other state changes made as a result of processing that message for correctness. You can't generally solve this with a layer put on top, even on the same machine. If it's not atomic, then you can still deliver duplicates to the application or end up never delivering to the application. (Power goes out when one side has written but not the other).

So, the state change to "already received" and the changes you want to make in response to the message being received have to happen together. TCP or even a message queueing implementation with a persistence layer cannot solve this problem for you. Thus, the application needs to deal with multiple delivery.

Imagine a "subtract $5 from my bank account" message with no ID on the message itself, and a layer "on top" that gives IDs and tries to ensure exactly once delivery. If the layer "on top" does not change state at the exact time $5 is deducted from the account, bad things can happen-- and in practice this is impossible. Hence, the application needs to be able to cope with the "subtract $5" being delivered to it multiple times, and this deduping has to be intimately tied to it subtracting the $5 (processing).

Re: Yes, you can have exactly-once delivery

#98

Post by qaq »

lisper wrote: post #64
two_handfuls wrote: post #50

Earlier quoted context omitted.

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.

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…

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.

Re: Yes, you can have exactly-once delivery

#99

Post by Jach »

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…

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.

Post reply on HN