6 ms·
No such thing as exactly-once delivery
- dondraper36 2y agoIt's admirable when vendors don't try to abuse theory to make their product look better. There was some blog post last week that supposedly proved the impossibility of exactly once delivery wrong, but that was quite expectedly another attempt to rename the standard terms.
- convolvatron 2y agoif you employ persistence to keep sequence numbers, and/or retransmissions and redundancy, you can drive the likelihood of distributed consensus over time arbitrarily close to probabilities where it doesn't matter anyways (like the earth suddenly being coincident with the sun). so what are we arguing about?
- sethammons 2y agothere is a group of people that say that there is no such thing as exactly-once-delivery and they are correct. There is also a group of people who cannot hear nor read nor process the word "delivery" in that term and instead insist that exactly-once-processing is easily achievable via [deduplication, idempotent actions, counters, ...]. They are correct as long as they acknowledge "processing" vs "delivery" -- and there are several who refuse to acknowledge that and don't believe the distinction matters and they are wrong.
- rwiggins 2y agoOut of curiosity, how would you describe TCP in these terms? Does the TCP stack's handling of sequence numbers constitute processing (on the client and server both I assume)? Which part(s) of a TCP connection could be described as delivery?
- wmf 2y agoFrom TCP's perspective it has delivered the data when read() returns successfully. This is also the point at which TCP frees the packet buffers. From the app's perspective, TCP is an at-most-once system because data can be lost in corner cases caused by failures. (Of course plenty of people on the Internet use different definitions to arrive at the opposite conclusion but they are all wrong and I am right.)
- YZF 2y agoI agree this is what you'd consider delivery. Also agree everyone else is wrong an I am right ;) The similar question in TCP is what happens when the sender writes to their socket and then loses the connection. At this point the sender doesn't know whether the receiver has the data or not. Both are possible. For the sender to recover it needs to re-connect and re-send the data. Thus the data is potentially delivered more than once and the receiver can use various strategies to deal with that. But sure, within the boundary of a single TCP connection data (by definition) is never delivered twice.
- wellpast 2y agois there a real difference between delivery and processing? In a streaming app framework (like Flink or Beam, or Kafka Streams), I can get an experience of exactly once "processing" by reverting to checkpoints on failure and re-processing. But what's the difference between doing this within the internal stores of a streaming app or coordinating a similar checkpointing/recovery/"exactly-once" mechanism with an external "delivery destination"?
- ithkuil 2y agoYes there is a difference and it's quite crucial to understanding how two groups of people can claim seemingly opposite things and both be correct. It's important to note that by processing here we don't just mean any "computing" but the act of "committing the side effects of the computation"
- wellpast 2y agoA typical delivery target is a data store or cache. Writing to such a delivery can be construed of as a “side effect”. But if you accept eventual consistency, achieving exactly once semantics is possible. Eg a streaming framework will let you tally an exactly once counter. You can flush the value of that tally to a data store. External observers will see an eventually consistent exactly-once-delivery result.
- ithkuil 2y agoUltimately the behavior that matters is the effective behaviour of the system. But a system is built by many components. You can build a reliable system out of unreliable components. You can build a transactional system out of non-transactional components. However you pay a price for that, because you have to bear the consequences of this substrate in other layers, often in your business logic too.
- sethammons 2y ago> You can flush the value of that tally to a data store What if you can't flush? You can't guarantee a flush: the sender or receiver can get powered off or otherwise get stuck for an indeterminate amount of time. That flush is the delivery. The data, is it stored in memory? Then it was lost when the process was killed.
- andrewflnr 2y agoNot that I disagree with getting terms exactly right, but if the "processing" that happens exactly once in your messaging system is firing a "delivery" event to a higher level of the stack (over a local channel), that's observationally indistinguishable from exactly-once delivery to that higher level, isn't it? What am I missing?
- wmf 2y agoNope, because that event could also be lost/duplicated.
- Izkata 2y agoIn the systems I'm used to, that "passing up" is a function call within the same codebase. There isn't a second delivery system for a message to be lost/duplicated, though sometimes they obscure it by making it look more like such a system.
- sethammons 2y agoPower gets cut. Now what? A process can fail between two function calls. When your power is restored, what happens with that mid-processing request? Lost or retried?
- andrewflnr 2y agoOver a local channel? Like same machine or even same process? I mean, yeah, you might have a bug that messes up the local "processing", but that's not a deep truth about distributed systems anymore, it's just a normal bug that you can and should fix.
- ViewTrick1002 2y agoThe problems always stem from the side effects. You can achieve exactly once like properties in a contained system. But if the processing contains for example sending an email then you need to apply said actions for all downstream actions, which is where exactly once as seen by the outside viewer gets hard.
- mike_hearn 2y agoEmail has the Message-Id header which is basically an idempotency ID.
- SpicyLemonZest 2y agoWhat you can't do, and what naive consumers of distributed systems often expect, is drive the probability arbitrarily low solely from the producer side. The consumer has to be involved, even if they consider themselves to be a single-node process and don't want to bother with transactionality or idempotency keys.
- mgsouth 2y agoVendor: "Exactly once is possible. We do it!" No, as a vendor you're either deliberately lying, or completely incompentent. Let's insert the words they don't want to. "We do exactly once good enough for your application!" How could you possibly know that? "We do exactly once good enough for all practical purposes!" So are my purposes practical? Am I a true scotsman? "We do exactly once good enough for applications we're good enough for!" Finally, a truthful claim. I'm not holding my breath. Edit: More directly address parent: It's not possible to even guarentee at-least-once in a finite amount of time, let alone exactly-once. For example, a high-frequency trading system wants to deliver exactly one copy of that 10-million-share order. And do it in under a microsecond. If you've got a 1.5 microsecond round trip, it's not possible to even get confirmation an order was received in that time limit, much less attempt another delivery. Your options are a) send once and hope. b) send lots of copies, with some kind of unique identifier so the receiver can do process-at-most-once, and hope you don't wind up sending to two different receiving servers.
- sidewndr46 2y agoThis didn't stop AWS from at one point declaring "none of the above" as their delivery guarantees for S3 events: https://www.hydrogen18.com/blog/aws-s3-event-notifications-probably-once.html https://www.hydrogen18.com/blog/aws-s3-event-notifications-p... From what I can tell my blog post eventually motivated them to change this behavior
- tombert 2y agoReminds me of this: https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing https://en.wikipedia.org/wiki/Fallacies_of_distributed_compu... Part of the reason I find distributed and concurrent computing so fascinating is that we lose so many assumptions about how computers are supposed to work; ordering guarantees, data actually arriving to destinations, fairness, etc. While it is of course possible for data to get lost or mangled in a single-threaded, non-distributed application, it's rare enough to where you often don't need to plan much around it. Once you add concurrency, and especially if you make it distributed, you suddenly have to plan around the eventuality of the messages not arriving, or arriving in the wrong order, or arriving multiple times. Personally, I've gotten into the habit of PlusCal and TLA+ for everything, and modeling in the assumption that stuff might never arrive or arrive multiple times, which can work as a very good sanity check (though it's of course not a silver bullet).
- Animats 2y agoThere's no such thing as finite-time arbitration for multiprocessor requests to memory, but it works anyway. This is similar. You can't guarantee time-bounded exactly once delivery, but after enough interchanges the probability of being wrong approaches zero. This shows up explicitly in blockchain systems, where confidence improves as the number of confirmation cycles increases.
- YZF 2y agoThis is the first time I'm hearing about the topic of arbitrating multiprocessor access to memory. Isn't there a trivial counterexample where the bandwidth is divided by the number of processors and each processor gets a timeslot? Processors, despite being a distributed system (well really every ASIC is), don't typically suffer from your classical distributed systems style issues because they have no failures, or rather they only have certain catastrophic failure modes that are low probability and well controlled for. Your typical distributed system to contrast has constant failures.
- Animats 2y ago> This is the first time I'm hearing about the topic of arbitrating multiprocessor access to memory. See [1]. This was a very real problem in early multiprocessor computer design. [1] https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 https://en.wikipedia.org/wiki/Arbiter_%28electronics%29
- fanf2 2y agoAre there many (or even any) multi-drop buses in modern computers? I get the impression that these days almost everything is point-to-point links. But I know less about what’s happening on silicon. I have seen talk of crossbar interconnects on microcontrollers, which (aiui) are more active, unlike passive buses?
- Animats 2y agoMemory controllers with more than one port have an internal arbiter. The ports are connected to various CPUs, GPUs, and I/O devices. Something has to sequence requests to the memory interface. Memory controllers used to be separate chips, but since about 2008 they're usually on the CPU die. Memory arbiters are where atomic operations on memory are actually implemented.
- dang 2y agoRecent and related: Yes, you can have exactly-once delivery - https://news.ycombinator.com/item?id=41598006 https://news.ycombinator.com/item?id=41598006 - Sept 2024 (133 comments) Also. Others? You cannot have exactly-once delivery (2015) - https://news.ycombinator.com/item?id=34986691 https://news.ycombinator.com/item?id=34986691 - March 2023 (217 comments) Show HN: Exactly-once delivery counter using Watermill messaging library - https://news.ycombinator.com/item?id=26888303 https://news.ycombinator.com/item?id=26888303 - April 2021 (9 comments) High-performance, exactly-once, failure-oblivious distributed programming (2018) - https://news.ycombinator.com/item?id=20562733 https://news.ycombinator.com/item?id=20562733 - July 2019 (26 comments) Exactly-once Semantics: How Kafka Does it - https://news.ycombinator.com/item?id=14670801 https://news.ycombinator.com/item?id=14670801 - June 2017 (39 comments) Delivering Billions of Messages Exactly Once - https://news.ycombinator.com/item?id=14664405 https://news.ycombinator.com/item?id=14664405 - June 2017 (133 comments) You Cannot Have Exactly-Once Delivery - https://news.ycombinator.com/item?id=9266725 https://news.ycombinator.com/item?id=9266725 - March 2015 (55 comments) Exactly-Once Messaging in Kafka - https://news.ycombinator.com/item?id=8880612 https://news.ycombinator.com/item?id=8880612 - Jan 2015 (8 comments) Exactly-Once Delivery May Not Be What You Want - https://news.ycombinator.com/item?id=8614264 https://news.ycombinator.com/item?id=8614264 - Nov 2014 (10 comments)
- thadt 2y ago> With that definition, SQS, Kafka, and Sequin are all systems that guarantee exactly-once processing. The term processing captures both the delivery of the message and the successful acknowledgment of the message. This terminology confuses my face. Maybe we need a better name for "exactly-once processing"? When I say "processing" I'm thinking of the actions that my program is going to take on said message - the very processing that they're talking about can fail. Can we not just say 'the message is held until acknowledgement'?
- theptip 2y agoThe simple way to visualize this is that all the processing can happen within a serializable transaction. If anything fails, the transaction rolls back. Marking the message as delivered is part of the same transaction.
- thadt 2y agoWhich means that the 'processing' in my application has to have the semantics of a serializable transaction. And it might not - as in the very example given in the post, where a processing application sends an email. Hence my complaint that making statements like "our system offers exactly once processing" can be completely correct - from the point of view of the messaging system. But it can be misleading to the casual reader in understanding how it fits into the broader solution, because the messaging system cannot guarantee that my application processes it exactly once. I'm saying the terminology doesn't feel right.
- griffgeorge 2y ago> That's why we don't say Sequin offers exactly-once delivery anywhere. We say it offers at-least-once delivery and exactly-once processing. The author should note that the homepage at https://sequinstream.com/ https://sequinstream.com/ does in fact claim that Sequin supports "Exactly-once delivery" under the "Key features" heading.
- 0xbadcafebee 2y agoI mean, you can do exactly-once delivery, it's just a more complex state machine with a specific design requirement. Here it is using mail: # Receive new mail message, incoming id '1234'. # No other writer knows about this message. $ echo "hello world" > incoming/1.1234.txt # If files stay in incoming/ too long, it means they probably failed writing, # and are thus stale and can be removed. # When the message is done being written, the writer moves it to a new state. $ mv incoming/1.1234.txt new/1.1234.txt # The writer can then report to the sender that the message was accepted. # In mail, this is seen as optional, as the whole point is to deliver the message, # not to make sure you inform the sender that you will deliver the message. # Here's the exactly-once bit: # If you need assurance of exactly-once delivery, split out the delivery portion # from the confirmation portion. # # Have one actor talk to the sender, and another actor queue the message in another # temporary queue, like 'accepted/'. Once the message is queued there, you tell the # client it is accepted, wait for successful termination of the connection, and then # move the message to the 'new/' queue. # # This way, if there is an error between accepting the message and confirming with # the sender, you can detect that and leave the message in 'accepted/' where you can # later decide what to do with it. (But it won't get picked up for processing) # The message is now ready to be picked up for processing. # To process the message, a processor picks up the new message and moves it to a new state. # # The processor adds an identifier '5678', so the processor can identify which file it's working on. # It can have extra logic to re-attempt processing on this ID if it fails. $ mv new/1.1234.txt process/1.1234.5678.txt # If the processor dies or takes too long, you can identify that (stale file, processor tracking its work, etc) # and this can be moved back to 'new/' for another attempt. Moving it back to 'new/' is still atomic so # there is no danger of another processor continuing to work on it. # Once the processor is done processing, it will move to the complete state. $ mv process/1.1234.5678.txt done/1.txt # If the processing file no longer exists, it means it was either already done, # or previously died and was moved back to 'new/'. This process all depends on a database [filesystem] using synchronous atomic operations [mv]. If your distributed system can't handle that, yeah, you're gonna have a hard time.
- mgsouth 2y agoSo that everyone's on the same page, perhaps you could clarify what "delivery" means to you? For example: * The human to whom the message is addressed reads it on their screen. * The email is inserted into that person's inbox. It's possible something will happen to the message after than point, before the addressee actually reads it, but that isn't what you're talking about. * The email has been accepted by a server operating as an endpoint for the addressee (their company's Exchange server), _and_ acknowledgement has been received by the sending server. * The above, but no guarentees about the sending server getting the acknowledgement. etc. [Edit: also, what "guarentee" means to you. 100%, 99.99999% is good enough, and so on.]
- notfed 2y agoTangent, but: this reminds me of many philosophical debates, e.g. "do we have free will?". What I've found is that usually what's happening is that the "debaters" assume different definitions of the thing they're debating about, which means they're really debating about two entirely different things, with the same name, and that's the real reason why they've come to different conclusions.
- rzzzt 2y agoOne recommendation I've read is that in such cases you should treat the single label you and your opponent have attached to two different ideas as forbidden. Describe it in more detail to reveal the difference (don't just swap words in the starting combination with their synonyms).
- wmf 2y agoThat's fine for discussions between experts but when a hundred noobs enter the discussion it's just unpaid tutoring. These threads are bringing out a lot of "I've discovered something all the distributed systems experts missed" energy.
- aidenn0 2y agoFor me "do we have free will" debate is useless because if the answer is "no" then that implies the result of the debate is predetermined and all involved lack any agency to change the outcome. Therefore any adult arguing the "no free will" side is either 1. Disingenuous 2. Purposefully playing Candyland as an adult. Either of which is so damaging to the Ethos that I lack any desire to continue the debate.
- magicalhippo 2y agoThis feels a bit like those relativity puzzles, for example the barn-pole paradox[1]. That is, delivered exactly-once seems to be a relative statement where one party can state they did deliver exactly-once while another party can disagree, and they're both correct relative to their local frames of reference. So, like how GR has no global conservation of energy, just local, could one say that distributed systems have no global conservation of messages, only local? Or am I just late night rambling again... [1]: https://en.wikipedia.org/wiki/Ladder_paradox https://en.wikipedia.org/wiki/Ladder_paradox
- hansvm 2y agoThe math of distributed system timings looks basically identical to the math of special relativity.
- socketcluster 2y agoThe "exactly once delivery is impossible" narrative got so strong that people feel that they have to redefine the word 'delivery' to make it fit the premise. If a message can be guaranteed to be received one or more times but results in a single entry being inserted into a database (e.g. in an idempotent way using UUIDs to enforce uniqueness), then clearly, a consumer reading the records from that database would only receive the message exactly once. If you consider the intended recipient to be the process, not the host, then the definition of 'delivery' allows you to claim that exactly-once delivery is possible. Of course this is a pragmatic, not mathematical argument. In theory you can't mathematically guarantee even at least once delivery because you can't guarantee that there's not going to be a Carrington event which will bring down the internet and drive humanity to extinction; thus preventing the consumer server from being rebooted.
- YZF 2y agoWhat about other messages though? The question isn't usually limited to one message in isolation, it's related to the state of the system as a whole. So sure, trivially, setting one bit where that bit is never cleared can only be done once, so any process setting that bit is also trivially (and not very usefully?) "exactly once delivery".
- mgsouth 2y agoOn the contrary, that is an extremely useful process, and is the basis for vast swathes of multiprocessing algorithms (such as "has this thing finished initializing", or "has it been freed"). However, it is "at most once", not "exactly once". The bit may never be set.
- YZF 2y agoFair enough. A single bit that can only get set can indeed be useful.
- BeeOnRope 2y agoIn a sense it's just kicking the can down the road: how you ensure the consumer reads the message only once? It may fail at some point after it has read the message but updated some state to reflect that. So it's not just a pointless argument about the semantics of the term "delivery": the fact that no communication channel can have exactly once delivery means that these systems are much more difficult to implement. For example, you can't just chain together 2 "exactly once" delivery systems into some longer one with a stateless middle node: instead you need some concept of idempotency that spans both systems or the middle node itself needs to de-duplicate (statefully) the first link and forward messages on to the second link.
- benlivengood 2y agoMessages don't have to be delivered more than once to achieve exactly-once processing; the receiver can offer a query interface for delivery status. If every attempt at delivery checks for a unique message ID and only sends the message if it has not been received then you get exactly-once delivery of the message, if not the metadata. Optimistically assuming the message has not been delivered yet will sometimes reduce average latency (most databases), but for very expensive messages it is better to check first (rsync)
- losvedir 2y agoIsn't there a race condition in the check, though? * X in transit to B * A asks B: Have you received X? B says No. * X gets to B. * A sends X.
- 3np 2y agoRight, and as you solve for this on a different layer, you end up having to choose between at-most-once and at-least-once at some point anyway. Proof is in the pudding if GP won't take my word for it ;) I think it's a useful excercise to attempt to disprove notions such as this. We shouldn't take all these "truths" for granted. But it does take some diving into it properly to appreciate the nuances and eventually get the underlying (as opposed to reasoning about it on a higher level, as we all are here).
- benlivengood 2y agoI've worked on a couple systems that achieve exactly-once processing and one took a at-most-once writing approach that backfilled missing events after the fact (6 nines of completeness was sufficient for ~hours), and another that took the approach of file-chunk ownership with retries by another worker if the destination files (distributed file system in another region) were too short once ownership expired, before chunks were marked fully complete and the next chunk was added to the work queue (transactionally).
- benlivengood 2y agoThere is multiple delivery if there are multiple senders, which can be avoided on the sending side by e.g. individual send-workers owning messages with a TTL and cancelling if they can't increase their ownership TTL if they haven't finished by the expiration
- dataflow 2y agoIf there is no such thing as exactly-once delivery because the recipient might not feel like deduplicating, then there can be no such thing as at-least-once delivery either, because the recipient might not feel like being endlessly available for delivery either. Or the mailman might not feel like (re-)attempting deliveries endlessly either. Or the sender might not feel like re-sending things endlessly either. Is this insightful? Surprising? What's the point of the debate?
- kelnos 2y ago> we don't say Sequin offers exactly-once delivery anywhere. We say it offers at-least-once delivery and exactly-once processing. Ugh, this is just a matter of semantics. Boring. If the receiver only acts on messages once, and will always have the opportunity to act on every single message, then for all practical purposes, it's exactly-once delivery.
- orf 2y agoAnd how do you guarantee it only acts on messages once? It’s the same problem. Even so, it’s very explicitly not exactly once delivery.
- exabrial 2y agoI mean… activemq delivers messages once and reliably… we push 12k msgs/s with a gig of ram and 2 cores about 25% cpu. Msg size is about 500 bytes - 500kb. It’d be faster but we don’t care. It also participates in an XA transaction… In 10 years of running it practically non stop up to volumes of 100kmsg/s with hundreds of network and disk issues, I’ve never ever seen even once a dupe message. Sure as the article is it could happen but in practice it doesn’t.
- orf 2y agoYou wouldn’t expect to see issues in a simple system in a steady-state. The problems arise when the system responds to other transient or unexpected issues. Try `kill -9`ing your consumers or unplugging a network cable and see what happens. Also, AMQP is most certainly not exactly once by any measure at all. Do you have any consistency checks or anything to validate duplicates?
- exabrial 2y agoWe don’t use AMQP. And kill -9 is for amateurs. Pull plugs.
- orf 2y agoManually pulling plugs is for amateurs: automate or die Either way, you’re getting duplicate deliveries if you’re using >1 machine. And if you’re not, what are you adding to the conversion?
- exabrial 2y agoUh… we’re not. Sorry to disappoint you.
- orf 2y agoI have never crashed my car, yet I acknowledge it is between a possibility and a certainty, depending on the situation. Saying “Well I’ve driven 100k miles and never crashed” doesn’t add much. Also, not sure how you’re consistency checking 100k messages per second over that many years.
- orf 2y agoA lot of developers assume exactly once semantics, often implicitly, and have no metrics or consistency checks in place to detect issues. Or the issues are silently hidden - I.e the same database row updated with the same value. I remember working on a system in AWS that hooked a SNS topic into a Data Firehose, which then delivered the data to S3. I was expecting rare duplicates and the system accounted for that. After a week I audited the data and found that the duplicate rate varied between 5% and 8% per hour - much much higher than anticipated. And this is purely within a managed integration between two managed components.
- mike_hearn 2y agoThe rule is simple: - Within a transactional system you can have exactly once processing (as they call it here). - Crossing the boundaries between two transactions requires idempotency IDs to deduplicate redeliveries and restore exactly-once inside the new transaction. Email is an oft-cited example but is a transactional system that supports idempotency IDs (the Message-ID). Deliver the same email twice with the same message IDs and email systems are supposed to deduplicate. Gmail at least would do that, iirc.
- andrewaylett 2y agoIt's worth remembering that the same applies for person-to-person interactions too -- there's nothing magical about software that makes it somehow more susceptible to this kind of problem, it's just often easier to resolve with people. Especially if you're close enough for so-called "real time" communication. Exactly-once delivery means solving the Byzantine Generals problem, and since that's not possible, neither is exactly-once delivery. Which isn't to say you can't get a good enough approximation, but you'll still only have an approximation.