17 ms·

You cannot have exactly-once delivery (2015)

189 points by babelfish 4y ago

qeternity 4y ago
Mirror - https://archive.is/VQsIr https://archive.is/VQsIr
deleted 4y ago
[deleted]
fizwhiz 4y ago
Exactly Once = At least once + Idempotence
- paxys 4y ago
  So, the opposite of exactly once
  - echelon 4y ago
    No, if your datastore is online (the only way you're functioning anyway), store an idempotency key, vector clock, etc. with transactional semantics. In active / active setups, there are other strategies such as partitioning and consensus.
  - sokoloff 4y ago
    Not exactly. If you have a business problem where you’re thinking “But I really, really need the effect of exactly-once; what can I do?”, GP’s post has the answer.
    - fsckboy 4y ago
      OP's idea should be idempotence + at least once idempotence isn't necessarily commutative.
  - fizwhiz 4y ago
    With idempotence, you shift the problem from "deliver X exactly once" to "make it seem like X was delivered exactly once". In most systems, exactly-once is really "effectively exactly once".
    - paxys 4y ago
      That's my point. You are simply converting the problem to a new form, not actually solving it. Hey here's a solution to the halting problem – always assume yes, and then figure out the edge cases. How do you do that? Well that's on you, I did my job. In a distributed system that needs exactly-once delivery, implementing perfect idempotence is equally impossible.
      - nawgz 4y ago
        Idempotency - famously complex. No one has ever successfully implemented it, great point.
        paxys 4y ago
        If you don't think idempotency can be complex then you haven't really worked on serious distributed computing problems.
        nawgz 4y ago
        If you don't think your analogy is a miss then you haven't really read any serious literature.
      - burnished 4y ago
        Converting a problem to a new form that you know how to better solve, or at least hope is more tractable, is a time honored mathematical and CS tradition
  - naasking 4y ago
    It can be exactly once at the application level just not exactly once at the more fine-grained message level. The fact that it's not exactly once at that lower level doesn't really matter, the semantics at the application level is what we care about.
    - kybernetikos 4y ago
      Exactly. In practice there are probably a bunch of other things happening over the wire we also don't care about, handshakes and keepalives and negotiation and splitting and encryption and latency measuring and backpressure... It doesn't matter, in a variety of systems, at the application layer it is fine for the user to assume they will see a delivery to their code exactly once and that's what the user cares about. A delivery didn't mean some internal bytes travelled across the wire, it means your clients received a call. That's why if you search for exactly once delivery you'll see a bunch of products claiming to have it (e.g kafka).
- hackerdad 4y ago
  This!
- tunesmith 4y ago
  This is called "Effectively Once".
  - tunesmith 4y ago
    (first heard it coined by Viktor Klang)
- crazygringo 4y ago
  Which the author admits three quarters of the way through: > The way we achieve exactly-once delivery in practice is by faking it. Either the messages themselves should be idempotent, meaning they can be applied more than once without adverse effects, or we remove the need for idempotency through deduplication. Honestly I don't get why this is "faking it" though. It seems like the author's definition of "exactly once" is so purist as to essentially be a strawman. This is "exactly once" in practice. Like are there other people claiming that this purist version of exactly-once does exist?
  - hn_go_brrrrr 4y ago
    The distinction is how you design. You don't need idempotence with a mythical "exactly once" system. Conversely, when you're debugging a system built on top of "at least once", you need to keep that property in mind in case the bug you're tracking down is lost idempotence.
  - kevincox 4y ago
    Because idempotence can be very hard to achieve. You usually can't just write the message ID to a DB and ignore messages with a matching ID because if you crash while processing then you need to start over again. But you can't just write it at the end because then all of your processing steps need to be idempotent (so why are you bothering to write the ID?). I've seen very few systems that have general idempotency baked in. Often it ends up being specific to the application. In some cases you can have simple solutions like upon crashing reload all of the state from an authoritative source. In some cases your messages result in simple idempotent operations such as "insert message with a unique ID" or "mark a message with a unique ID as read" but even then these are becoming quite related to business logic. Basically idempotency is a powerful tool to create a solution but it is no silver bullet. That is why it is important to understand the underlying problem.
  - majormajor 4y ago
    It can be very hard to get idempotency right. It can get way harder when your initial design made incorrect assumptions about the delivery semantics you were using, so you didn't know you'd need it. Edit for example: Someone could have a low-latency problem that seems like it could be a fit for a streaming application. They could look at docs and see "ooh, with Flink I can do exactly-once writes to Kafka" in one place, and choose to use that. But if they don't dig deeply into what that means, they may miss the latency impacts of having to checkpoint every time to commit a set of writes to Kafka. And by the time they figure this out, managing both "low latency" and "exactly once" in the code they wrote might be a really hairy problem.
- purpleblue 4y ago
  It's not "equal". If you guarantee "exactly once", you design your systems differently than "at least one with idempotence". A system designed for exactly once will be less complicated than a system designed for at least once + idempotence, which is why it is ideal but impossible.
- jerf 4y ago
  I think we need to keep the concepts separate because otherwise people get confused. You can not receive a message exactly once. Yes, it's not that hard, if you know this is an issue, to build a system where receiving the same message more than once won't cause a bad thing to happen. There's a few principled ways to do this, and some less principled ways that will still mostly work. But that's not because you built a system that successfully delivers messages exactly once... you build a system that successfully processes messages exactly once, even if delivery occurs multiple times. The delivery still occurred multiple times. Even if your processing layer handled it, that may have other consequences worth understanding. Wrapping that up in a library may present a nice API for some programmer, but it doesn't solve the Byzantine General problem. Whenever someone insists they can build Exactly Once with [mumble mumble mumble great tech here] I guarantee you there's a non-empty set of human readers coming away with the idea they can successfully create systems based on exactly-once delivery. After all, I built some code based on exactly-once delivery last night and it's working fine on my home ethernet even after I push billions of messages through it. We're really better of pushing "There is no such thing as Exactly Once, and the way you deal with is [idempotence/id tracking/whatever]", not "Yes there is such a thing as Exactly Once delivery (see fine print about how I'm redefining this term)". The former produces more accurate models in human brains about what is going on and is more likely to be understood as a set of engineering tradeoffs. The latter seems to produce a lot of confusion and people not understanding that their "Exactly Once" solution isn't a magic total solution to the problem, but is in fact a particular point on the engineering tradeoff spectrum. In particular, the "exactly once" solutions can be the wrong choice for certain problems, like multiplayer game state updates, where it may be a lot more viable to think 1-or-0 and some timestamping and the ability to miss messages entirely and recover, rather than building an "exactly once" system.
  - naasking 4y ago
    > But that's not because you built a system that successfully delivers messages exactly once... you build a system that successfully processes messages exactly once, even if delivery occurs multiple times. I think the difference might be partly semantic. If processing at the messaging level is idempotent + at least once, then message delivery to the application level is exactly once. People mostly only care about the application level not the lower levels where they might just build on a library or system that handles that logic for them.
- FooBarWidget 4y ago
  Theoretically true, and easy to say. But the hard part is actually implementing this in the context of business problems. What if you need to call external services that you don't control, and they don't provide idempotence? Like sending emails. Or worse: you send a message to a warehouse to deliver an item, and they deliver duplicates...
  - lll-o-lll 4y ago
    Yeah the duplicate email thing is a classic problem, but I’m not sure it’s one of “idempotence”. This can happen in any (intended to be) transactional operation that creates a side affect. Hit an error, roll-back, side-affect can’t be rolled back. Retry - side-affect happens again. Wouldn’t the general approach be to have unique message identifiers and queue side-affects? Maybe I’m missing lots of subtleties.
    - Mavvie 4y ago
      Email is absolutely something that requires idempotence to avoid sending duplicates. Even if your code is perfect and you don't send emails until after you commit your transaction, the actual http request to the email provider could fail in a way where the email is sent but your system can't tell. Idempotency (either via a token in the request, or another API to check the result of the previous request) is required to prevent duplicates. And this requires the third party service to support idempotency; there's nothing you can do on your side to enable it if their service doesn't support it.
      - HiJon89 4y ago
        What if your system is the one actually sending the emails (ie, you are the 3rd party in this scenario)
- stonemetal12 4y ago
  Until the bill comes anyway. Having to provision extra bandwidth for useless dups, extra processing power for useless updates, etc.
- doctor_eval 4y ago
  AFAIK the point of exactly once delivery, in the context of message passing, is to abstract delivery concerns away from the application layer and into the messaging layer, so that the application can depend on the exactly-once semantics without having to write logic for it. The problem with this is similar to the problems with two-phase commit in distributed databases: there are unavoidable failure cases. Most of the time it works just fine, but if you write your application to depend on this impossible feature, and it fails - which, given enough time, will certainly happen - then the cleaning up the mess can be much more effort (and have much wider business implications) than simply dealing with the undesirable behaviour of reality in the first place. Or to put it another way: exactly once semantics can never be reliably extracted away from the application, so if you need it, it needs to be part of your application.
- dilyevsky 4y ago
  Good thing most things in the real world are idempotent then!
OnlyRepliesToBS 4y ago
[dead]
deathanatos 4y ago
> There are essentially three types of delivery semantics: at-most-once, at-least-once, and exactly-once. Oh, there's a fourth kind: "none-of-the-above", i.e., neither at-most-once or at-least-once. The message gets delivered between [0, ∞] times. Maybe it gets delivered … maybe not. Your message is like UDP packet. A surprising number of systems exhibit this behavior, sadly.
- ibotty 4y ago
  I guess you mean "[0, ∞)". You cannot have infinitive delivery in computer systems.
  - deathanatos 4y ago
    Oh IDK. So, if you look at it juuuust right, ELK can be considered as delivering messages … log messages. Normally our ELK system exhibited the behavior I described above: our logging component would make best efforts to ensure that log messages did get delivered. But there was no ID on the log message when it was submitted: double-submission would result in the message getting duplicated. The message was only removed from the queue of messages that needed to be submitted if the ACK was successfully received. The local queue was only so big: if the application continued to log but couldn't submit to ELK, well, it would just discard the messages², so messages might not get delivered period, even when the client was fine, (e.g., during network outages).¹ That was all fine and good (the consequences of a log message getting delivered twice or not delivered under normal circumstances is "whatever"). One day, the team managing ELK misconfigured it, causing all log submission to start failing. This … didn't get detected? (I mean, as a consumer of the service, what are you going to do, log the error?) Worse, some logs were first routed through the local syslog daemon. It decided to log that it couldn't send the message to a local log file, and then retry without backup, and never gave up. (And, of course, there's not log rotation on that local log file.) So we noticed the problem when the disk filled up … and then realized basically every VM in the fleet was doing this. So it felt like ∞] that day. But yes, mathematically, that bound should be ∞). ¹there is some decent discussion in the thread below my OP about whether this technically counts as "0 deliveries". ²the logic being that crashing due to inability to log is not worth it. It noted the failure on its stderr … but you had to know to look.
AlbertCory 4y ago
I decided a long time ago in 3+Mail that we could occasionally have messages delivered twice, or not at all, but there was no easy way to be sure neither ever happened. So you bias it to "twice."
bjornsing 4y ago
Why not mention the architecture that comes closest to exactly-once delivery? If you store a Kafka offset along with your application state in a transactional datastore, then for all intents and purposes you have exactly-once delivery semantics. This is something I really like about Kafka’s design.
- infamouscow 4y ago
  I suspect it's not mentioned because in the real world there are ways to work around this limitation. And because those work arounds actually work, there's nothing interesting to say. The post is much ado about nothing.
  - bjornsing 4y ago
    Yes, it’s always possible to build a big pile of workarounds. I agree.
- kevincox 4y ago
  This is again assuming that you have no side effects. Imagine that you want to email users based on a list in Kafka. You read the offset in a transaction and update it. But do you send the email inside the transaction or after closing it? You are back to picking between at-least-once and at-most-once.
  - taspeotis 4y ago
    Just put the offset in the email to users and make them keep track of it??
    - remram 4y ago
      Move the problem to another system does not solve the problem. Someone is necessarily dealing with it.
      - morelisp 4y ago
twawaaay 4y ago
Of course you can have exactly-once delivery. I mean... we know how to construct software that will transfer money from one account to another, exactly once. It really isn't rocket science but it does require a little bit of understanding of various tradeoffs that you are making. It is a bit like saying that we can't have straight lines. Of course, if you zoom in far enough to see individual atoms, every physical surface will look jagged. But in practical terms we can have straight lines and surfaces to a good enough approximation. It means specifying what "straight" means and figuring out how to measure it and how to produce "straight" according to specification and measurements. Engineering is about knowing and making tradeoffs. Every device we have ever created has to contend with limitations of physical existence. Engineering is about accomplishing goals in presence of those limitations. A person who says "you can't deliver a message exactly once" clearly lives in an idealised, theoretical world. I would urge to leave your ivory tower for a second and see how engineers in real world accomplish what you say is not possible. I get that this knowledge is useful -- but don't publish it as gospel. "You cannot have exactly-once delivery" is true, but not the same kind of truth as "you can't travel faster than light". No engineering can get you to travel faster than light. But engineering can get you as close to exactly-once delivery as you want to the point where the original statement stops being meaningful for real life problems.
- skybrian 4y ago
  You can’t do any transfer by any particular deadline if the network is down. Assuming the network will recover in time may be a reasonable assumption sometimes, though.
  - deleted 4y ago
    [deleted]
  - dllthomas 4y ago
    If "the network might be down arbitrarily long" is a possibility, you cannot have at least once delivery, either.
    - preseinger 4y ago
Nican 4y ago
I have been toying with the idea lately of using a transactional database (like SQL) to manage some of the very important queues. Using a transaction to retrieve an item from the queue, and locking the row using "SELECT FOR UPDATE" and "SKIP LOCKED". Such that the row gets locked on read, and several workers can read from the table at the same time. Within the same transaction, other work is done, and everything gets committed to the database as a single atomic operation. CockroachDB (a consensus/raft distributed database) recently added supported for SKIP LOCKED, but I still have yet to work on this idea.
- kevincox 4y ago
  It can definitely work. It is a pretty good way to avoid the distributed systems problem by avoiding having a distributed system. Of course there are other concerns with using a database as a queue (mostly at high throughput) but for most cases it will work well.
- scarface74 4y ago
  Using a database as a queue. What could possibly go wrong? I guess everyone has to make this mistake once in their career. Funny enough, when I searched for “database as a queue”, my own comment from four years ago came up as the fourth result. https://news.ycombinator.com/item?id=18774559 https://news.ycombinator.com/item?id=18774559
- rowls66 4y ago
  I have worked on a system that took exaclty this approach for ~17 years. The database was Oracle, at the time we started 'SKIP LOCKED' was not even a documented feature of the Oracle DBMS. It is now. The approach worked quite well for us and happily working today at several large banks. Also, Oracle sells what I think they call AMQ (Advanced Message Queing) that provides a messaging API but uses the DBMS for storage. No idea how it performs relative to dedicated persistent messaging solutions, but I would guess that it probably good enough for many workloads.
candiddevmike 4y ago
I'd tell you an exactly once delivery joke but you may not get it.
- danw1979 4y ago
  I’d tell you an idempotency joke but I think you might have heard it before…
  - setuids 4y ago
    I'm sure it won't make a difference
  - yamtaddle 4y ago
    You can go ahead. It won't modify the state-of-having-heard-it.
- antod 4y ago
  "Now listen very carefully, I shall say this only once." I suspect that quote will meet Resistance.
aftbit 4y ago
If you want to reason about a world that has random software and hardware failures, than you cannot really have any kind of pure results. A backhoe could cut your network cable at exactly the wrong point, or a malfunctioning network switch could decide to insert the right extra few bytes in exactly the wrong place, changing the meaning of your message without altering any of the checksums. As the scale of your application increases, the chance of this sort of chaos increases as well. The question then becomes how to reason in the face of chaos, what sorts of error rates are acceptable, and how to build systems that can recover from supposedly impossible states. If your bank's software makes an error, they have established processes to determine that and correct the balance of accounts.
- bob1029 4y ago
  This line of "what if an asteroid hits the primary & DR data centers in the same microsecond" thinking is why we settled on running our product on 1 VM with SQLite in-proc. After taking our customers through this same kind of apocalyptic rabbit hole conversation, they tend to agree with this architecture decision. The cost of anticipating the .00001% that might never come is completely drowned out by the massive, daily 99%-certain headache that is managing a convoluted, multi-cloud cluster. Many times the business owners will get the message and finally reveal that they have always had access to a completely ridiculous workaround involving literal paper & pen that is just as feasible in 2023 as it was in the 18th century.
  - morelisp 4y ago
    In my experience the customers, and even the POs, are the easy ones to convince. “We get 99% of the uptime for 30% of the price? Great!” It’s the resume-driven mid dev in the next office you’ve got to watch out for.
    - CuriousSkeptic 4y ago
      or the dev who spent a few nights and weekends rescuing the system after one of those 1% failures the customer, as it turns out, has no patience for at all
xg15 4y ago
Maybe I didn't get the point. Of course we can't have exactly-once delivery directly in the layer of an unreliable network - but it seems pretty easy to construct it on a higher layer if your network stack supports at-least-once delivery: Just assign each message a unique ID during sending, then track those IDs in the receiver side and discard duplicates. And you need those IDs anyway so you can generate ACKs. Isn't this basically what every "reliable" transport (TCP, HTTP3, message queues...) does?
- danpalmer 4y ago
  > then track those IDs in the receiver side Now you need a database. Do you also need exactly-once delivery to the database? Now the service is no longer stateless too, which means scalability is a problem. Maybe you decide to make it just an in-process cache for de-duping, but that needs expiring and now the semantics are exactly-once within a given time period, and not across service restarts. We can definitely solve this with higher level constructs, but they're not free, and they can introduce the same issues themselves. > Isn't this basically what every "reliable" transport (TCP, HTTP3, message queues...) does? TCP does this, to solve retries at the TCP layer. HTTP3 does this to solve issues at the HTTP3 layer. Message queues might solve this for the message queue, depends. But none of these solve the product level, or the user experience level, or other higher levels where these issues still crop up. They're issues you have to solve at every layer in some way.
  - sorokod 4y ago
    Do you also need exactly-once delivery to the database? Yes, with uniqueness constraint. the service is no longer stateless too, which means scalability is a problem Do you have a specific problem in mind?
    - hinkley 4y ago
      It's probably more accurate to say that toy systems can maintain the illusion of exactly-once for a while, but it doesn't scale. You can't keep a record of every message ever seen in a message based system. Message passing systems exist to handle rates of traffic that cannot be achieved by rolling your own event queue as a thin wrapper around other tools like databases. It's not just the storage, it's the throughput. The first time I encountered RabbitMQ it could only handle 60 messages per second with delivery guarantees. We already had our own bespoke system that used a database to handle a couple multiples of that. So we ended up limping along with what we had.
jurschreuder 4y ago
Ok so maybe the letter gets sent more than once but the message gets sent exactly once, because the messages are numbered and you only process each number once. If you get a letter with the same number you already read you don't even open it. In Kafka this is also handled this way, events are numbered, and you request "latest" from the last one you processed. In our eventstreaming it's also done like this, it may surprise you that Kafka is just an implementation of eventstreaming and not the same as. With Kafka the offset of the consumers, or until which number it had already processed, used to be handled by the ZooKeeper but is migrated to the consumers. There is on "exactly one consumer gets the message" done by the ZooKeeper, all consumers get all the messages from the topics they subscribed to. If you want exactly on exactly one consumer you should create different topics. So not true.
- chias 4y ago
  I think there is a useful distinction here though -- you're by definition doing processing there on a "non-exactly-once delivery" system in order to get your "exactly-once" result, and by definition anything that requires exactly-once message delivery must do this process itself: it cannot abstracted away into a separate system. So, in essence, you can never have "I will get this exactly once", and at best you can only ever have "I will have a plan for what to do if I get this more than once".
  - chacham15 4y ago
    > So, in essence, you can never have "I will get this exactly once", and at best you can only ever have "I will have a plan for what to do if I get this more than once". I dont understand this at all. TCP has exactly once message delivery that the application layer is completely unaware of...
    - majormajor 4y ago
      TCP isn't guaranteed delivery if the receiver crashes; that's what queues and similar persistent systems are introduced to solve, but at-least-once is what you normally get outside of specialized two-phase (write then commit later) idempotent (so writing a second time is OK if the first one was never committed since your producer died and restarted from an earlier position, say) systems, AFAIK.
dang 4y ago
Discussed at the time: You Cannot Have Exactly-Once Delivery - https://news.ycombinator.com/item?id=9266725 https://news.ycombinator.com/item?id=9266725 - March 2015 (55 comments)
- xg15 4y ago
  So evidently the article did fail exactly-once delivery.
  - danw1979 4y ago
    Fail delivery of what ?
    - xg15 4y ago
      Delivery to HN.
javaunsafe2019 4y ago
I mean isn’t it just the same as with a real world package/message. It just depends on how much effort you are willed to put into your desired delivery model?! … But guaranteed is nothing, never.
stickfigure 4y ago
My company (among other things) routes print-on-demand orders to various print companies. Some of their APIs have mechanisms to ensure idempotency, some don't. The last time I pressed the issue, I was asked - and I quote - "Can't you just send the order only once?" The thing is, having a print company that gets the printing part right is more important than having one that gets the API right. I use them anyway, and accept the risk that there will very occasionally be duplicate orders. At least in my business, it's just tshirts. A few months ago I bought a fairly expensive cordless vacuum from hoover.com. I was charged once, but two of them arrived. I suspect I know why.
- deleted 4y ago
  [deleted]
- thaumasiotes 4y ago
  > The last time I pressed the issue, I was asked - and I quote - "Can't you just send the order only once?" What did they suggest you should do if you sent the order once and it didn't arrive?
- jwr 4y ago
  I have these sorts of facepalmable discussions from time to time. The last time was with a company that provides an invoicing service through an API. They are (and I am not shitting you) unable to ensure unique invoice numbers and told me to "just don't try to open and issue more than one invoice at any time".
- liftm 4y ago
  I suspect they also don't have an API to check the orders you sent?
  - stickfigure 4y ago
    That would make it too easy! Most just offer get-by-id (their ID, of course). Some don't even offer that; they just post a webhook on shipment.
- belter 4y ago
piyh 4y ago
I was completely naive to distributed systems until I was field promoted to owning one after tons of attrition with no backfilling roles. It was a system built by people that also didn't have distributed system experiences. It was not enjoyable at all, and at least once delivery was a consistent headache that required infrequent but time consuming remediation.
- InCityDreams 4y ago
  "was field promoted"....could you explain what you mean? To myself, it's always been a military term. As far as 386 pc's etc go....?
  - sieabahlpark 4y ago
    It literally just means internally promoted
    - tripa 4y ago
      There is a certain nuance of “in war time” (as opposed to school time). It's the case here, but isn't automatic.
anonymousDan 4y ago
This article reads like someone who has a very superficial understanding of the theory he/she claims proves his/her point. For starters, the two generals problem does not prevent one party knowing a message they sent previously was delivered exactly once. It just prevents both parties knowing about some common knowledge in the presence of message loss. Not that I am claiming to be any better!
tonymet 4y ago
the workaround is de-duplication & idempotency
iainmerrick 4y ago
This article spends a long time discussing idempotency but only mentions deduplication in passing. Can’t you de-dupe by attaching a UUID to messages?
- remram 4y ago
  To a point. You can do that in your own system, but at some point down the line you interact with something that cannot or does not want to de-duplicate based on UUID, such as a different system, or a person. Then you have to choose between at-least-once or at-most-once.
lisper 4y ago
> We must choose between the lesser of two evils, which is at-least-once delivery in most cases. This can be used to simulate exactly-once semantics by ensuring idempotency or otherwise eliminating side effects from operations. There is a third option besides idempotency and eliminating side-effects: give each message a unique ID, use that to keep a record of which messages have been processed, and don't process the same message twice.
- Kalium 4y ago
  How does this work? This means the consumers have to somehow know the IDs of every message that's been sent and if it's been processed. Either you have a shared database and all consumers are local, in which case why are you passing messages at all, or you have a distributed system somehow. If you have a distributed system, you've got this problem, and going recursive probably won't help much. Or I've missed something.
  - iainmerrick 4y ago
    It depends what you mean by “processed”. If there’s some particular action you want to take in response to the message, then you put the database next to wherever that action takes place. If it’s a notification displaying on a phone, the phone holds a DB that tracks what notifications have been shown. You can’t reliably show a notification on exactly one of a user’s devices. But that’s no biggie; display it exactly once per device, remove it everywhere when acknowledged anywhere.
    - Kalium 4y ago
      That sounds like at-least-once delivery with recipient systems tracking known received messages. Which is to say faking exactly-once with the power of idempotency, rather than exactly-once. This is academic with enough abstraction, but when you're designing a system and implementing the work of processing a message it can be a pretty important distinction. Especially if you're past the point where the list of seen items becomes a chokepoint for synchronization between consumers. > You can’t reliably show a notification on exactly one of a user’s devices. But that’s no biggie; display it exactly once per device, remove it everywhere when acknowledged anywhere. Potentially messy. Now you have two distributed system messages - the initial notification and the ack.
yodsanklai 4y ago
> FLP and the Two Generals Problem are not design complexities, they are impossibility results. These are impossibility results given various assumptions and requirements that may not hold in practice, or may be too restrictive. For one thing, i suppose we're pretty happy with a probabilistic solution as long as we can get the probability below an acceptable threshold.
jongjong 4y ago
This article is incorrect. > The way we achieve exactly-once delivery in practice is by faking it. Either the messages themselves should be idempotent, meaning they can be applied more than once without adverse effects, or we remove the need for idempotency through deduplication. The author is wildly overestimating the complexity of the solution by ignoring the existence of a very simple but critical concept: UUIDs If the client generates and assigns a UUID to each message it sends, the receiver can easily check if a specific message was already received before by comparing it against previously received UUIDs and can discard duplicates. The title of the article is misleading because exactly-once delivery is in fact possible by deduplication. The deduplication can occur automatically (without having to know any context about the message beyond its UUID); it can occur BEFORE the delivery of the message to the consumer... So the title and entire premise of the article is incorrect. What the author should really be saying is that more than one copy of the same message may occasionally pass through the network due to failures... But they are misleading in suggesting that it's not possible to deliver exactly one copy or that deduplication is a herculean task when in fact it's trivial.
- birdyrooster 4y ago
  If all of your agents are seeing the UUID for the first time, they cannot deduplicate amongst themselves without quorum or shared state which has race conditions itself. It’s non trivial.
  - vlovich123 4y ago
    But not impossible.
    - birdyrooster 4y ago
      Depending on your ability to share state between these agents it could very well be impossible. It depends on other factors.
  - EdwardDiego 4y ago
    Yeah, non trivial is correct. A common Kafka approach is to partition by key, so that a given UUID will only be placed on one partition, and we're guaranteed that any further messages with that key will also be placed on that partition, so handled by the same consumer. Then create a change-log topic that's co-partitioned by key with the input topic. And then funk around with partition assignment strategies so if consumer X is assigned partition 10 of the input topic, then it's also assigned partition 10 of the change-log topic. Then add RocksDB as a fast state store on a persistent volume claim, as restoring state fresh from your change-log topic turns out to take about 7 minutes. And then realise you've just reimplemented bits of Kafka Streams poorly.
throwaway892238 4y ago
What is this guy smoking? Send a UDP packet from one node and receive it on another. Exactly-once delivery. If what he really means is "guaranteed to be delivered exactly once", then, yeah, no, of course not, because if your network goes down, you can't send anything. Over a network. You can, of course, just have one big fat machine and have two nodes in the machine and send the packet from the one node to another in the one big giant machine. There's no "network" to go down, unless somebody slices into the machine with a red-hot katana. You can also have a fully-connected topology where every machine is hard-wired into every other machine, and every machine will route for every other machine. There's no real "network" to go down; as long as there are 2 hosts that aren't dead, a message from one will get to another. What I find amusing is that well before you get into truly hard distributed system problems, for a sufficiently complex implementation/application, your apps will be riddled with so many bugs and so many operational problems that the thing is going to fall over way before a well-built network goes down.
- sethammons 4y ago
  I'd tell you a joke about UDP, but you might not get it
  - javcasas 4y ago
    I have a wifi repeater/range extender. I call it repeater, because often when pinging with it, I get duplicated packets. I know, I know, it's ICMP, not UDP, but yeah, don't tell me the joke. I may get tired of hearing it again and again.
jverce 4y ago
Funny how the author later worked on NATS [1] which supports exactly-once semantics [2]. -- [1] https://nats.io/ https://nats.io/ [2] https://docs.nats.io/using-nats/developer/develop_jetstream/model_deep_dive#exactly-once-semantics https://docs.nats.io/using-nats/developer/develop_jetstream/...
lxe 4y ago
> Therefore consumer applications will need to perform deduplication or handle incoming messages in an idempotent manner. > The way we achieve exactly-once delivery in practice is by faking it. Either the messages themselves should be idempotent, meaning they can be applied more than once without adverse effects, or we remove the need for idempotency through deduplication. Doesn't have to be a "true" exactly-once. Just practically so. It's like saying "humans can't actually fly... they are faking it by using machines".
deleted 4y ago
[deleted]
stefs 4y ago
am i correct in assuming that all of this is true for non-distributed systems as well, just less likely?
belter 4y ago
"You Cannot Have Exactly-Once Delivery" - 8 years ago | 55 comments https://news.ycombinator.com/item?id=9266725 https://news.ycombinator.com/item?id=9266725

189 points by babelfish 4y ago

qeternity 4y ago

Mirror - https://archive.is/VQsIr https://archive.is/VQsIr

deleted 4y ago

[deleted]

fizwhiz 4y ago

Exactly Once = At least once + Idempotence

paxys 4y ago
So, the opposite of exactly once
- echelon 4y ago
  No, if your datastore is online (the only way you're functioning anyway), store an idempotency key, vector clock, etc. with transactional semantics. In active / active setups, there are other strategies such as partitioning and consensus.
- sokoloff 4y ago
  Not exactly. If you have a business problem where you’re thinking “But I really, really need the effect of exactly-once; what can I do?”, GP’s post has the answer.
  - fsckboy 4y ago
    OP's idea should be idempotence + at least once idempotence isn't necessarily commutative.
- fizwhiz 4y ago
  With idempotence, you shift the problem from "deliver X exactly once" to "make it seem like X was delivered exactly once". In most systems, exactly-once is really "effectively exactly once".
  - paxys 4y ago
    That's my point. You are simply converting the problem to a new form, not actually solving it. Hey here's a solution to the halting problem – always assume yes, and then figure out the edge cases. How do you do that? Well that's on you, I did my job. In a distributed system that needs exactly-once delivery, implementing perfect idempotence is equally impossible.
    - nawgz 4y ago
      Idempotency - famously complex. No one has ever successfully implemented it, great point.
      - paxys 4y ago
        If you don't think idempotency can be complex then you haven't really worked on serious distributed computing problems.
        nawgz 4y ago
        If you don't think your analogy is a miss then you haven't really read any serious literature.
    - burnished 4y ago
      Converting a problem to a new form that you know how to better solve, or at least hope is more tractable, is a time honored mathematical and CS tradition
- naasking 4y ago
  It can be exactly once at the application level just not exactly once at the more fine-grained message level. The fact that it's not exactly once at that lower level doesn't really matter, the semantics at the application level is what we care about.
  - kybernetikos 4y ago
    Exactly. In practice there are probably a bunch of other things happening over the wire we also don't care about, handshakes and keepalives and negotiation and splitting and encryption and latency measuring and backpressure... It doesn't matter, in a variety of systems, at the application layer it is fine for the user to assume they will see a delivery to their code exactly once and that's what the user cares about. A delivery didn't mean some internal bytes travelled across the wire, it means your clients received a call. That's why if you search for exactly once delivery you'll see a bunch of products claiming to have it (e.g kafka).
hackerdad 4y ago
This!
tunesmith 4y ago
This is called "Effectively Once".
- tunesmith 4y ago
  (first heard it coined by Viktor Klang)
crazygringo 4y ago
Which the author admits three quarters of the way through: > The way we achieve exactly-once delivery in practice is by faking it. Either the messages themselves should be idempotent, meaning they can be applied more than once without adverse effects, or we remove the need for idempotency through deduplication. Honestly I don't get why this is "faking it" though. It seems like the author's definition of "exactly once" is so purist as to essentially be a strawman. This is "exactly once" in practice. Like are there other people claiming that this purist version of exactly-once does exist?
- hn_go_brrrrr 4y ago
  The distinction is how you design. You don't need idempotence with a mythical "exactly once" system. Conversely, when you're debugging a system built on top of "at least once", you need to keep that property in mind in case the bug you're tracking down is lost idempotence.
- kevincox 4y ago
  Because idempotence can be very hard to achieve. You usually can't just write the message ID to a DB and ignore messages with a matching ID because if you crash while processing then you need to start over again. But you can't just write it at the end because then all of your processing steps need to be idempotent (so why are you bothering to write the ID?). I've seen very few systems that have general idempotency baked in. Often it ends up being specific to the application. In some cases you can have simple solutions like upon crashing reload all of the state from an authoritative source. In some cases your messages result in simple idempotent operations such as "insert message with a unique ID" or "mark a message with a unique ID as read" but even then these are becoming quite related to business logic. Basically idempotency is a powerful tool to create a solution but it is no silver bullet. That is why it is important to understand the underlying problem.
- majormajor 4y ago
  It can be very hard to get idempotency right. It can get way harder when your initial design made incorrect assumptions about the delivery semantics you were using, so you didn't know you'd need it. Edit for example: Someone could have a low-latency problem that seems like it could be a fit for a streaming application. They could look at docs and see "ooh, with Flink I can do exactly-once writes to Kafka" in one place, and choose to use that. But if they don't dig deeply into what that means, they may miss the latency impacts of having to checkpoint every time to commit a set of writes to Kafka. And by the time they figure this out, managing both "low latency" and "exactly once" in the code they wrote might be a really hairy problem.
purpleblue 4y ago
It's not "equal". If you guarantee "exactly once", you design your systems differently than "at least one with idempotence". A system designed for exactly once will be less complicated than a system designed for at least once + idempotence, which is why it is ideal but impossible.
jerf 4y ago
I think we need to keep the concepts separate because otherwise people get confused. You can not receive a message exactly once. Yes, it's not that hard, if you know this is an issue, to build a system where receiving the same message more than once won't cause a bad thing to happen. There's a few principled ways to do this, and some less principled ways that will still mostly work. But that's not because you built a system that successfully delivers messages exactly once... you build a system that successfully processes messages exactly once, even if delivery occurs multiple times. The delivery still occurred multiple times. Even if your processing layer handled it, that may have other consequences worth understanding. Wrapping that up in a library may present a nice API for some programmer, but it doesn't solve the Byzantine General problem. Whenever someone insists they can build Exactly Once with [mumble mumble mumble great tech here] I guarantee you there's a non-empty set of human readers coming away with the idea they can successfully create systems based on exactly-once delivery. After all, I built some code based on exactly-once delivery last night and it's working fine on my home ethernet even after I push billions of messages through it. We're really better of pushing "There is no such thing as Exactly Once, and the way you deal with is [idempotence/id tracking/whatever]", not "Yes there is such a thing as Exactly Once delivery (see fine print about how I'm redefining this term)". The former produces more accurate models in human brains about what is going on and is more likely to be understood as a set of engineering tradeoffs. The latter seems to produce a lot of confusion and people not understanding that their "Exactly Once" solution isn't a magic total solution to the problem, but is in fact a particular point on the engineering tradeoff spectrum. In particular, the "exactly once" solutions can be the wrong choice for certain problems, like multiplayer game state updates, where it may be a lot more viable to think 1-or-0 and some timestamping and the ability to miss messages entirely and recover, rather than building an "exactly once" system.
- naasking 4y ago
  > But that's not because you built a system that successfully delivers messages exactly once... you build a system that successfully processes messages exactly once, even if delivery occurs multiple times. I think the difference might be partly semantic. If processing at the messaging level is idempotent + at least once, then message delivery to the application level is exactly once. People mostly only care about the application level not the lower levels where they might just build on a library or system that handles that logic for them.
FooBarWidget 4y ago
Theoretically true, and easy to say. But the hard part is actually implementing this in the context of business problems. What if you need to call external services that you don't control, and they don't provide idempotence? Like sending emails. Or worse: you send a message to a warehouse to deliver an item, and they deliver duplicates...
- lll-o-lll 4y ago
  Yeah the duplicate email thing is a classic problem, but I’m not sure it’s one of “idempotence”. This can happen in any (intended to be) transactional operation that creates a side affect. Hit an error, roll-back, side-affect can’t be rolled back. Retry - side-affect happens again. Wouldn’t the general approach be to have unique message identifiers and queue side-affects? Maybe I’m missing lots of subtleties.
  - Mavvie 4y ago
    Email is absolutely something that requires idempotence to avoid sending duplicates. Even if your code is perfect and you don't send emails until after you commit your transaction, the actual http request to the email provider could fail in a way where the email is sent but your system can't tell. Idempotency (either via a token in the request, or another API to check the result of the previous request) is required to prevent duplicates. And this requires the third party service to support idempotency; there's nothing you can do on your side to enable it if their service doesn't support it.
    - HiJon89 4y ago
      What if your system is the one actually sending the emails (ie, you are the 3rd party in this scenario)
stonemetal12 4y ago
Until the bill comes anyway. Having to provision extra bandwidth for useless dups, extra processing power for useless updates, etc.
doctor_eval 4y ago
AFAIK the point of exactly once delivery, in the context of message passing, is to abstract delivery concerns away from the application layer and into the messaging layer, so that the application can depend on the exactly-once semantics without having to write logic for it. The problem with this is similar to the problems with two-phase commit in distributed databases: there are unavoidable failure cases. Most of the time it works just fine, but if you write your application to depend on this impossible feature, and it fails - which, given enough time, will certainly happen - then the cleaning up the mess can be much more effort (and have much wider business implications) than simply dealing with the undesirable behaviour of reality in the first place. Or to put it another way: exactly once semantics can never be reliably extracted away from the application, so if you need it, it needs to be part of your application.
dilyevsky 4y ago
Good thing most things in the real world are idempotent then!

OnlyRepliesToBS 4y ago

[dead]

deathanatos 4y ago

> There are essentially three types of delivery semantics: at-most-once, at-least-once, and exactly-once. Oh, there's a fourth kind: "none-of-the-above", i.e., neither at-most-once or at-least-once. The message gets delivered between [0, ∞] times. Maybe it gets delivered … maybe not. Your message is like UDP packet. A surprising number of systems exhibit this behavior, sadly.

ibotty 4y ago
I guess you mean "[0, ∞)". You cannot have infinitive delivery in computer systems.
- deathanatos 4y ago
  Oh IDK. So, if you look at it juuuust right, ELK can be considered as delivering messages … log messages. Normally our ELK system exhibited the behavior I described above: our logging component would make best efforts to ensure that log messages did get delivered. But there was no ID on the log message when it was submitted: double-submission would result in the message getting duplicated. The message was only removed from the queue of messages that needed to be submitted if the ACK was successfully received. The local queue was only so big: if the application continued to log but couldn't submit to ELK, well, it would just discard the messages², so messages might not get delivered period, even when the client was fine, (e.g., during network outages).¹ That was all fine and good (the consequences of a log message getting delivered twice or not delivered under normal circumstances is "whatever"). One day, the team managing ELK misconfigured it, causing all log submission to start failing. This … didn't get detected? (I mean, as a consumer of the service, what are you going to do, log the error?) Worse, some logs were first routed through the local syslog daemon. It decided to log that it couldn't send the message to a local log file, and then retry without backup, and never gave up. (And, of course, there's not log rotation on that local log file.) So we noticed the problem when the disk filled up … and then realized basically every VM in the fleet was doing this. So it felt like ∞] that day. But yes, mathematically, that bound should be ∞). ¹there is some decent discussion in the thread below my OP about whether this technically counts as "0 deliveries". ²the logic being that crashing due to inability to log is not worth it. It noted the failure on its stderr … but you had to know to look.

AlbertCory 4y ago

I decided a long time ago in 3+Mail that we could occasionally have messages delivered twice, or not at all, but there was no easy way to be sure neither ever happened. So you bias it to "twice."

bjornsing 4y ago

Why not mention the architecture that comes closest to exactly-once delivery? If you store a Kafka offset along with your application state in a transactional datastore, then for all intents and purposes you have exactly-once delivery semantics. This is something I really like about Kafka’s design.

infamouscow 4y ago
I suspect it's not mentioned because in the real world there are ways to work around this limitation. And because those work arounds actually work, there's nothing interesting to say. The post is much ado about nothing.
- bjornsing 4y ago
  Yes, it’s always possible to build a big pile of workarounds. I agree.
kevincox 4y ago
This is again assuming that you have no side effects. Imagine that you want to email users based on a list in Kafka. You read the offset in a transaction and update it. But do you send the email inside the transaction or after closing it? You are back to picking between at-least-once and at-most-once.
- taspeotis 4y ago
  Just put the offset in the email to users and make them keep track of it??
  - remram 4y ago
    Move the problem to another system does not solve the problem. Someone is necessarily dealing with it.
    - morelisp 4y ago

twawaaay 4y ago

Of course you can have exactly-once delivery. I mean... we know how to construct software that will transfer money from one account to another, exactly once. It really isn't rocket science but it does require a little bit of understanding of various tradeoffs that you are making. It is a bit like saying that we can't have straight lines. Of course, if you zoom in far enough to see individual atoms, every physical surface will look jagged. But in practical terms we can have straight lines and surfaces to a good enough approximation. It means specifying what "straight" means and figuring out how to measure it and how to produce "straight" according to specification and measurements. Engineering is about knowing and making tradeoffs. Every device we have ever created has to contend with limitations of physical existence. Engineering is about accomplishing goals in presence of those limitations. A person who says "you can't deliver a message exactly once" clearly lives in an idealised, theoretical world. I would urge to leave your ivory tower for a second and see how engineers in real world accomplish what you say is not possible. I get that this knowledge is useful -- but don't publish it as gospel. "You cannot have exactly-once delivery" is true, but not the same kind of truth as "you can't travel faster than light". No engineering can get you to travel faster than light. But engineering can get you as close to exactly-once delivery as you want to the point where the original statement stops being meaningful for real life problems.

skybrian 4y ago
You can’t do any transfer by any particular deadline if the network is down. Assuming the network will recover in time may be a reasonable assumption sometimes, though.
- deleted 4y ago
  [deleted]
- dllthomas 4y ago
  If "the network might be down arbitrarily long" is a possibility, you cannot have at least once delivery, either.
  - preseinger 4y ago

Nican 4y ago

I have been toying with the idea lately of using a transactional database (like SQL) to manage some of the very important queues. Using a transaction to retrieve an item from the queue, and locking the row using "SELECT FOR UPDATE" and "SKIP LOCKED". Such that the row gets locked on read, and several workers can read from the table at the same time. Within the same transaction, other work is done, and everything gets committed to the database as a single atomic operation. CockroachDB (a consensus/raft distributed database) recently added supported for SKIP LOCKED, but I still have yet to work on this idea.

kevincox 4y ago
It can definitely work. It is a pretty good way to avoid the distributed systems problem by avoiding having a distributed system. Of course there are other concerns with using a database as a queue (mostly at high throughput) but for most cases it will work well.
scarface74 4y ago
Using a database as a queue. What could possibly go wrong? I guess everyone has to make this mistake once in their career. Funny enough, when I searched for “database as a queue”, my own comment from four years ago came up as the fourth result. https://news.ycombinator.com/item?id=18774559 https://news.ycombinator.com/item?id=18774559
rowls66 4y ago
I have worked on a system that took exaclty this approach for ~17 years. The database was Oracle, at the time we started 'SKIP LOCKED' was not even a documented feature of the Oracle DBMS. It is now. The approach worked quite well for us and happily working today at several large banks. Also, Oracle sells what I think they call AMQ (Advanced Message Queing) that provides a messaging API but uses the DBMS for storage. No idea how it performs relative to dedicated persistent messaging solutions, but I would guess that it probably good enough for many workloads.

candiddevmike 4y ago

I'd tell you an exactly once delivery joke but you may not get it.

danw1979 4y ago
I’d tell you an idempotency joke but I think you might have heard it before…
- setuids 4y ago
  I'm sure it won't make a difference
- yamtaddle 4y ago
  You can go ahead. It won't modify the state-of-having-heard-it.
antod 4y ago
"Now listen very carefully, I shall say this only once." I suspect that quote will meet Resistance.

aftbit 4y ago

If you want to reason about a world that has random software and hardware failures, than you cannot really have any kind of pure results. A backhoe could cut your network cable at exactly the wrong point, or a malfunctioning network switch could decide to insert the right extra few bytes in exactly the wrong place, changing the meaning of your message without altering any of the checksums. As the scale of your application increases, the chance of this sort of chaos increases as well. The question then becomes how to reason in the face of chaos, what sorts of error rates are acceptable, and how to build systems that can recover from supposedly impossible states. If your bank's software makes an error, they have established processes to determine that and correct the balance of accounts.

bob1029 4y ago
This line of "what if an asteroid hits the primary & DR data centers in the same microsecond" thinking is why we settled on running our product on 1 VM with SQLite in-proc. After taking our customers through this same kind of apocalyptic rabbit hole conversation, they tend to agree with this architecture decision. The cost of anticipating the .00001% that might never come is completely drowned out by the massive, daily 99%-certain headache that is managing a convoluted, multi-cloud cluster. Many times the business owners will get the message and finally reveal that they have always had access to a completely ridiculous workaround involving literal paper & pen that is just as feasible in 2023 as it was in the 18th century.
- morelisp 4y ago
  In my experience the customers, and even the POs, are the easy ones to convince. “We get 99% of the uptime for 30% of the price? Great!” It’s the resume-driven mid dev in the next office you’ve got to watch out for.
  - CuriousSkeptic 4y ago
    or the dev who spent a few nights and weekends rescuing the system after one of those 1% failures the customer, as it turns out, has no patience for at all

xg15 4y ago

Maybe I didn't get the point. Of course we can't have exactly-once delivery directly in the layer of an unreliable network - but it seems pretty easy to construct it on a higher layer if your network stack supports at-least-once delivery: Just assign each message a unique ID during sending, then track those IDs in the receiver side and discard duplicates. And you need those IDs anyway so you can generate ACKs. Isn't this basically what every "reliable" transport (TCP, HTTP3, message queues...) does?

danpalmer 4y ago
> then track those IDs in the receiver side Now you need a database. Do you also need exactly-once delivery to the database? Now the service is no longer stateless too, which means scalability is a problem. Maybe you decide to make it just an in-process cache for de-duping, but that needs expiring and now the semantics are exactly-once within a given time period, and not across service restarts. We can definitely solve this with higher level constructs, but they're not free, and they can introduce the same issues themselves. > Isn't this basically what every "reliable" transport (TCP, HTTP3, message queues...) does? TCP does this, to solve retries at the TCP layer. HTTP3 does this to solve issues at the HTTP3 layer. Message queues might solve this for the message queue, depends. But none of these solve the product level, or the user experience level, or other higher levels where these issues still crop up. They're issues you have to solve at every layer in some way.
- sorokod 4y ago
  Do you also need exactly-once delivery to the database? Yes, with uniqueness constraint. the service is no longer stateless too, which means scalability is a problem Do you have a specific problem in mind?
  - hinkley 4y ago
    It's probably more accurate to say that toy systems can maintain the illusion of exactly-once for a while, but it doesn't scale. You can't keep a record of every message ever seen in a message based system. Message passing systems exist to handle rates of traffic that cannot be achieved by rolling your own event queue as a thin wrapper around other tools like databases. It's not just the storage, it's the throughput. The first time I encountered RabbitMQ it could only handle 60 messages per second with delivery guarantees. We already had our own bespoke system that used a database to handle a couple multiples of that. So we ended up limping along with what we had.

jurschreuder 4y ago

Ok so maybe the letter gets sent more than once but the message gets sent exactly once, because the messages are numbered and you only process each number once. If you get a letter with the same number you already read you don't even open it. In Kafka this is also handled this way, events are numbered, and you request "latest" from the last one you processed. In our eventstreaming it's also done like this, it may surprise you that Kafka is just an implementation of eventstreaming and not the same as. With Kafka the offset of the consumers, or until which number it had already processed, used to be handled by the ZooKeeper but is migrated to the consumers. There is on "exactly one consumer gets the message" done by the ZooKeeper, all consumers get all the messages from the topics they subscribed to. If you want exactly on exactly one consumer you should create different topics. So not true.

chias 4y ago
I think there is a useful distinction here though -- you're by definition doing processing there on a "non-exactly-once delivery" system in order to get your "exactly-once" result, and by definition anything that requires exactly-once message delivery must do this process itself: it cannot abstracted away into a separate system. So, in essence, you can never have "I will get this exactly once", and at best you can only ever have "I will have a plan for what to do if I get this more than once".
- chacham15 4y ago
  > So, in essence, you can never have "I will get this exactly once", and at best you can only ever have "I will have a plan for what to do if I get this more than once". I dont understand this at all. TCP has exactly once message delivery that the application layer is completely unaware of...
  - majormajor 4y ago
    TCP isn't guaranteed delivery if the receiver crashes; that's what queues and similar persistent systems are introduced to solve, but at-least-once is what you normally get outside of specialized two-phase (write then commit later) idempotent (so writing a second time is OK if the first one was never committed since your producer died and restarted from an earlier position, say) systems, AFAIK.

dang 4y ago

Discussed at the time: You Cannot Have Exactly-Once Delivery - https://news.ycombinator.com/item?id=9266725 https://news.ycombinator.com/item?id=9266725 - March 2015 (55 comments)

xg15 4y ago
So evidently the article did fail exactly-once delivery.
- danw1979 4y ago
  Fail delivery of what ?
  - xg15 4y ago
    Delivery to HN.

javaunsafe2019 4y ago

I mean isn’t it just the same as with a real world package/message. It just depends on how much effort you are willed to put into your desired delivery model?! … But guaranteed is nothing, never.

stickfigure 4y ago

My company (among other things) routes print-on-demand orders to various print companies. Some of their APIs have mechanisms to ensure idempotency, some don't. The last time I pressed the issue, I was asked - and I quote - "Can't you just send the order only once?" The thing is, having a print company that gets the printing part right is more important than having one that gets the API right. I use them anyway, and accept the risk that there will very occasionally be duplicate orders. At least in my business, it's just tshirts. A few months ago I bought a fairly expensive cordless vacuum from hoover.com. I was charged once, but two of them arrived. I suspect I know why.

deleted 4y ago
[deleted]
thaumasiotes 4y ago
> The last time I pressed the issue, I was asked - and I quote - "Can't you just send the order only once?" What did they suggest you should do if you sent the order once and it didn't arrive?
jwr 4y ago
I have these sorts of facepalmable discussions from time to time. The last time was with a company that provides an invoicing service through an API. They are (and I am not shitting you) unable to ensure unique invoice numbers and told me to "just don't try to open and issue more than one invoice at any time".
liftm 4y ago
I suspect they also don't have an API to check the orders you sent?
- stickfigure 4y ago
  That would make it too easy! Most just offer get-by-id (their ID, of course). Some don't even offer that; they just post a webhook on shipment.
belter 4y ago

piyh 4y ago

I was completely naive to distributed systems until I was field promoted to owning one after tons of attrition with no backfilling roles. It was a system built by people that also didn't have distributed system experiences. It was not enjoyable at all, and at least once delivery was a consistent headache that required infrequent but time consuming remediation.

InCityDreams 4y ago
"was field promoted"....could you explain what you mean? To myself, it's always been a military term. As far as 386 pc's etc go....?
- sieabahlpark 4y ago
  It literally just means internally promoted
  - tripa 4y ago
    There is a certain nuance of “in war time” (as opposed to school time). It's the case here, but isn't automatic.

anonymousDan 4y ago

This article reads like someone who has a very superficial understanding of the theory he/she claims proves his/her point. For starters, the two generals problem does not prevent one party knowing a message they sent previously was delivered exactly once. It just prevents both parties knowing about some common knowledge in the presence of message loss. Not that I am claiming to be any better!

tonymet 4y ago

the workaround is de-duplication & idempotency

iainmerrick 4y ago

This article spends a long time discussing idempotency but only mentions deduplication in passing. Can’t you de-dupe by attaching a UUID to messages?

remram 4y ago
To a point. You can do that in your own system, but at some point down the line you interact with something that cannot or does not want to de-duplicate based on UUID, such as a different system, or a person. Then you have to choose between at-least-once or at-most-once.

lisper 4y ago

> We must choose between the lesser of two evils, which is at-least-once delivery in most cases. This can be used to simulate exactly-once semantics by ensuring idempotency or otherwise eliminating side effects from operations. There is a third option besides idempotency and eliminating side-effects: give each message a unique ID, use that to keep a record of which messages have been processed, and don't process the same message twice.

Kalium 4y ago
How does this work? This means the consumers have to somehow know the IDs of every message that's been sent and if it's been processed. Either you have a shared database and all consumers are local, in which case why are you passing messages at all, or you have a distributed system somehow. If you have a distributed system, you've got this problem, and going recursive probably won't help much. Or I've missed something.
- iainmerrick 4y ago
  It depends what you mean by “processed”. If there’s some particular action you want to take in response to the message, then you put the database next to wherever that action takes place. If it’s a notification displaying on a phone, the phone holds a DB that tracks what notifications have been shown. You can’t reliably show a notification on exactly one of a user’s devices. But that’s no biggie; display it exactly once per device, remove it everywhere when acknowledged anywhere.
  - Kalium 4y ago
    That sounds like at-least-once delivery with recipient systems tracking known received messages. Which is to say faking exactly-once with the power of idempotency, rather than exactly-once. This is academic with enough abstraction, but when you're designing a system and implementing the work of processing a message it can be a pretty important distinction. Especially if you're past the point where the list of seen items becomes a chokepoint for synchronization between consumers. > You can’t reliably show a notification on exactly one of a user’s devices. But that’s no biggie; display it exactly once per device, remove it everywhere when acknowledged anywhere. Potentially messy. Now you have two distributed system messages - the initial notification and the ack.

yodsanklai 4y ago

> FLP and the Two Generals Problem are not design complexities, they are impossibility results. These are impossibility results given various assumptions and requirements that may not hold in practice, or may be too restrictive. For one thing, i suppose we're pretty happy with a probabilistic solution as long as we can get the probability below an acceptable threshold.

jongjong 4y ago

This article is incorrect. > The way we achieve exactly-once delivery in practice is by faking it. Either the messages themselves should be idempotent, meaning they can be applied more than once without adverse effects, or we remove the need for idempotency through deduplication. The author is wildly overestimating the complexity of the solution by ignoring the existence of a very simple but critical concept: UUIDs If the client generates and assigns a UUID to each message it sends, the receiver can easily check if a specific message was already received before by comparing it against previously received UUIDs and can discard duplicates. The title of the article is misleading because exactly-once delivery is in fact possible by deduplication. The deduplication can occur automatically (without having to know any context about the message beyond its UUID); it can occur BEFORE the delivery of the message to the consumer... So the title and entire premise of the article is incorrect. What the author should really be saying is that more than one copy of the same message may occasionally pass through the network due to failures... But they are misleading in suggesting that it's not possible to deliver exactly one copy or that deduplication is a herculean task when in fact it's trivial.

birdyrooster 4y ago
If all of your agents are seeing the UUID for the first time, they cannot deduplicate amongst themselves without quorum or shared state which has race conditions itself. It’s non trivial.
- vlovich123 4y ago
  But not impossible.
  - birdyrooster 4y ago
    Depending on your ability to share state between these agents it could very well be impossible. It depends on other factors.
- EdwardDiego 4y ago
  Yeah, non trivial is correct. A common Kafka approach is to partition by key, so that a given UUID will only be placed on one partition, and we're guaranteed that any further messages with that key will also be placed on that partition, so handled by the same consumer. Then create a change-log topic that's co-partitioned by key with the input topic. And then funk around with partition assignment strategies so if consumer X is assigned partition 10 of the input topic, then it's also assigned partition 10 of the change-log topic. Then add RocksDB as a fast state store on a persistent volume claim, as restoring state fresh from your change-log topic turns out to take about 7 minutes. And then realise you've just reimplemented bits of Kafka Streams poorly.

throwaway892238 4y ago

What is this guy smoking? Send a UDP packet from one node and receive it on another. Exactly-once delivery. If what he really means is "guaranteed to be delivered exactly once", then, yeah, no, of course not, because if your network goes down, you can't send anything. Over a network. You can, of course, just have one big fat machine and have two nodes in the machine and send the packet from the one node to another in the one big giant machine. There's no "network" to go down, unless somebody slices into the machine with a red-hot katana. You can also have a fully-connected topology where every machine is hard-wired into every other machine, and every machine will route for every other machine. There's no real "network" to go down; as long as there are 2 hosts that aren't dead, a message from one will get to another. What I find amusing is that well before you get into truly hard distributed system problems, for a sufficiently complex implementation/application, your apps will be riddled with so many bugs and so many operational problems that the thing is going to fall over way before a well-built network goes down.

sethammons 4y ago
I'd tell you a joke about UDP, but you might not get it
- javcasas 4y ago
  I have a wifi repeater/range extender. I call it repeater, because often when pinging with it, I get duplicated packets. I know, I know, it's ICMP, not UDP, but yeah, don't tell me the joke. I may get tired of hearing it again and again.

jverce 4y ago

Funny how the author later worked on NATS [1] which supports exactly-once semantics [2]. -- [1] https://nats.io/ https://nats.io/ [2] https://docs.nats.io/using-nats/developer/develop_jetstream/model_deep_dive#exactly-once-semantics https://docs.nats.io/using-nats/developer/develop_jetstream/...

lxe 4y ago

> Therefore consumer applications will need to perform deduplication or handle incoming messages in an idempotent manner. > The way we achieve exactly-once delivery in practice is by faking it. Either the messages themselves should be idempotent, meaning they can be applied more than once without adverse effects, or we remove the need for idempotency through deduplication. Doesn't have to be a "true" exactly-once. Just practically so. It's like saying "humans can't actually fly... they are faking it by using machines".

deleted 4y ago

[deleted]

stefs 4y ago

am i correct in assuming that all of this is true for non-distributed systems as well, just less likely?

belter 4y ago

"You Cannot Have Exactly-Once Delivery" - 8 years ago | 55 comments https://news.ycombinator.com/item?id=9266725 https://news.ycombinator.com/item?id=9266725