6 ms·

If you can get at-least-once delivery, why can you not build exactly-once on top of that? [UPDATE] Apparently I need to be more explicit about this. My questi

• to11mtm 2y ago
  Because 'exactly once' delivery is arguably a misnomer, you usually really want 'at least once delivery with acks and idempotent processing on the other side'. The difference is subtle but important in practice and specification.
  • lisper 2y ago
    > you usually really want 'at least once delivery with acks and idempotent processing on the other side'. Why? I'm pretty sure I really want (the illusion of) exactly-once delivery, and it seems to me that I can implement that pretty easily given at-least-once delivery. Why would I not want that? > The difference is subtle but important Why?
    • ZephyrBlu 2y ago
      > I'm pretty sure I really want (the illusion of) exactly-once delivery Do you know what idempotency is? This is exactly what he described. Idempotency is important to prevent unwanted behaviour for duplicate actions. If you have "exactly-once", and accidentally execute the action twice that could cause problems.
      • lisper 2y ago
        > Do you know what idempotency is? Yes. > This is exactly what he described. So? Idempotency and an exactly-once delivery abstraction are not the same thing.
        • sethammons 2y ago
          Agreed. Idempotent _processing_, not delivery.
          • lisper 2y ago
            Uh, what exactly do you think is "agreed" here? My claim is that idempotent processing can produce exactly-once delivery, and so the original claim that you "cannot have exactly-once delivery" is false.
            • sethammons 2y ago
              Change your words from "delivery" to "processing" and you in alignment with reality. Idempotent processing is exactly once processing. This is true. Delivery is from the sender's point of view, not the recipient. How the recipient processes the information, idempotently or not, is not the concern of the sender. "Cannot have exactly-once delivery" is true and is as true as not dividing by zero. Read about the two general's problem. It is, quite literally, impossible to have exactly once delivery. Like, your friend is in the other room, and you shout "someone is at the door" - how do you _know_ your friend heard you? If you shout again, you are attempting another delivery. What do you do if your friend doesn't respond? In exactly once delivery, you guarantee they heard you in the other room. In exactly once processing, you can shout a couple of times until you hear them acknowledge. You may think that this is not material and at the end of the day, as long as one thing is processed, then who cares? Well, you have to understand how delivery can fail otherwise you will handle the failure incorrectly. Is it safe to try again? If I say "transfer money from me to you", and I don't hear back, is it safe to again say "transfer money from me to you" again? Will I be double charged?
              • lisper 2y ago
                > Change your words from "delivery" to "processing" and you in alignment with reality. You are not the first to say this, but so far no one has been able to explain what the difference between "delivery" and "processing" is. How do you do "delivery" (on a computer) without also doing (at least some) "processing"? > Delivery is from the sender's point of view, not the recipient. I don't see what difference that makes. In fact, I don't see why a "point of view" should enter into it at all. Whether a message has been "delivered" or not (whatever that actually turns out to mean) is (it seems to me) a property of the system, independent of anyone's point of view.
      • lttlrck 2y ago
        > Do you know what idempotency is? This is exactly what he described. Is it though? It seems like a false equivalency, even if the outcome is approximately the same?
    • to11mtm 2y ago
      You can absolutely abstract 99% of it out. But not 100%. At some point, a counter move on the delivery has to be stored... -somewhere-. And sure you -can- make it very very close to EOD and for some subsets you can totally do EOD, but you are, realistically, better off with ALOD+Ack once it makes its way into a system. There's always that 'moving the counter' problem. The upshot is, things tend to get faster, easier to code review, and simpler to test. Pragmatically speaking, I've found devs are better able to handle ALOD+ACK than "Exactly once but because reality you might get a message that's doubled because you couldn't persist the ack". And I'll note I'm possibly extra pedantic about this because I've had a month and a half of dealing with the fallout of people trusting low-code salesmen alongside gartner reports leading to a 'you people thought this was exactly once and it was not' sort of problem.
      • lisper 2y ago
        > But not 100%. Why not? > At some point, a counter move on the delivery has to be stored... -somewhere-. What is a "counter move on the delivery"?
        • sethammons 2y ago
          Read the two general's problem. It is a mathematical impossibility. The counter is the delivery counter. Delivery, delivery + 1
          • lisper 2y ago
            What makes you think the 2GP is relevant here? The 2GP has to do with coordination and consensus, not exactly-once delivery.
            • sethammons 2y ago
              You are correct
• shepherdjerred 2y ago
  You can get exactly once processing, but not exactly once delivery. https://bravenewgeek.com/you-cannot-have-exactly-once-delivery/ https://bravenewgeek.com/you-cannot-have-exactly-once-delive...
  • lisper 2y ago
    That seems like a distinction without a difference to me. Why should I care if the thing I get exactly one of is called "processing" or "delivery"?
    • jerf 2y ago
      Because you need to understand that your processing code is constrained by the fact that you can't get exactly-once delivery. You must write your processing code to handle it one way or another. There's some libraries that try to wrap the abstraction of processing exactly once around the code, but those libraries still impose constraints on the sort of code you can write. They can make it easier but they can't fully remove the need to think about how your processing code works. It isn't exactly the same. This is why people like me insist it's important to understand that you can not have exactly-once delivery. There is no library that can make that just go away, they can only shuffle around exactly where the lumps under the carpet live, and if one programs with the mistaken idea that these libraries really do solve "exactly once" delivery, one will get into deep trouble. Possibly the "my architecture is fundamentally broken and can't be rescued" sort of trouble.
      • lisper 2y ago
        > Because you need to understand that your processing code is constrained by the fact that you can't get exactly-once delivery. Why do I need to understand that? Why can I not put an abstraction layer that provides me with the illusion of exactly-once delivery? > There is no library that can make that just go away Well, this is the thing that I dispute. I believe that there is a library I can write to make it go away if I have at-least-once delivery. In fact, I claim that writing such a library is an elementary exercise. The TCP protocol is an existence proof. Where is the flaw in my reasoning?
• akira2501 2y ago
  You cannot while maintaining the half-duplex behavior of the current system.
  • lisper 2y ago
    Why not? (Please see the update on my OP before answering that.)
    • akira2501 2y ago
      The mechanism you're describing already exists. TCP has sequence numbers. It can drop duplicate data. The difference between "processing" and "delivery" relates to "network capacity." Process handling wastes capacity in favor of latency. Delivery handling increases latency in favor of capacity. Systems which have "exactly once" delivery typically do so with "send/receive" and "release/delete" message pairs. You need additional round trips to actually accomplish this at the "delivery" layer.
      • lisper 2y ago
        > The mechanism you're describing already exists. Yes, I know, which makes it all the more bizarre that people are claiming that this is impossible. > Systems which have "exactly once" delivery typically do so... Ah, so exactly-once delivery is possible after all?
        • akira2501 2y ago
          If your goal is simply to look smart then absorbing the subtlety of what is said to you before you reply should be top of list.
          • lisper 2y ago
            What subtlety do you think I have failed to absorb?
• Ayyyyyron 2y ago
  The principal difference between 'at most once' and 'at least once' is whether a sender re-tries when it is unsure if the recipient has received the message. If the recipient's ack never makes it back, then a sender cannot know whether they actually received the message or not (the two-generals problem). So this hypothetical middleman will receive a packet, check that it's not a duplicate, and forward it to the recipient it's proxying for. How will it know that the recipient has actually received it? If the receiver doesn't ack the message in some way, which causes your abstraction to re-transmit the message again, then it exhibits 'at least once' behavior. If it the abstraction only ever forwards the message along once and doesn't care whether the recipient acknowledged it or not, then it exhibits 'at most once' behavior. As a more concise answer - 'exactly once' delivery is impossible because you can't know if the recipient actually got the message. If you assume a perfect communication channel, then I agree the problem is trivial, but I challenge you to find such a channel! Even on the same machine, interprocess communication can fail in all sorts of fun ways.
  • lisper 2y ago
    > So this hypothetical middleman will receive a packet, check that it's not a duplicate, and forward it to the recipient it's proxying for. That's not how I would implement exactly-once on top of at-lest-once. I would do it at the recipient, not at the intermediate nodes. > 'exactly once' delivery is impossible because you can't know if the recipient actually got the message But the recipient can know.
    • Ayyyyyron 2y ago
      But the recipient is not one atomic thing - we're assuming perfect communication between the process/driver/hardware receiving the packets and doing the duplicate detection and the process which wants to receive the message exactly once. There's still communication happening there, and it can still fail. Buffers fill, processes pause for arbitrary delays which exceed timeouts, etc. Your assumptions based on your model are correct, but your model doesn't include that communication. But all models have some level of detail they care about, and assuming the computer always works is a perfectly valid model for plenty of cases. It's just not all of them. You'll be able to create real-world cases where this abstraction is faced with a choice of whether to retry or not, and at that moment it will be unable to deliver exactly once.
• kmeisthax 2y ago
  The problem is that sometimes your application intends to send messages[0] multiple times. If your "log-and-discard" system was implemented naively then each node could only ever send each possible message once and only once. Ever. That would be like: Alice: "Honey, where did you put the keys?" Bob: "They're up on the counter." (The next day...) Alice: "Honey, where did you put the keys?" Bob: (nothing, I already received this message, it could have echoed off the walls from yesterday) What you need is for all sent messages to have unique IDs that will never repeat, and then log those. That's known as an idempotency token. But even then, logging all those UUIDs forever is probably not a good idea for disk usage. At some point you'll have to trash old message logs and hope you don't have a rogue network router retransmitting six month old messages or something. [0] Or the moral equivalent of messages, e.g. HTTP POST requests
  • lisper 2y ago
    > What you need is for all sent messages to have unique IDs that will never repeat, and then log those. That's known as an idempotency token. So your problem is not really a problem because you yourself present the solution. The real problem is: > But even then, logging all those UUIDs forever But you don't need to log them all forever. Just make the UUIDs sequential, and all you need then is to keep track of the smallest id that has not yet been received. (You can be more efficient by storing more state, but it's not necessary. Remember, we're assuming at-least-once deliver here, so you can always force retransmission by not acknowledging receipt.)