> 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.
> A surprising number of systems exhibit this behavior, sadly.
I noticed [0, ∞] delivery semantics in a widely-used, internal/homegrown message delivery system at a big tech company once. The bug was easy to spot in the source code (which I was looking at for unrelated reasons), but the catch-22 is that engineers with the skills to notice these sorts of subtle but significant infra bugs are the same engineers who would've advised against building (or continuing to use) your own message delivery system in the first place when there are perfectly serviceable open source and SaaS options.
I think whether or not to build your own thing isn’t an obvious choice for a big company. You might have lots of other infrastructure to integrate with and adapting an existing solution might not work as well as making something from scratch that eg integrates with your storage layer or how you manage permissions. The choice may be between having a team dedicated to managing some third party thing (because in the real world these systems have bugs or cases that don’t perform well or need more hardware or rebalancing or whatever) and having a team dedicated to developing and managing an internal solution. The latter case can mean you get to take advantage of existing infrastructure, have less work integrating with this thing, and have in-house experts who can investigate and fix bugs.
I don’t think it’s as simple as always preferring to bring in external things.
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.
if you don't explicitly re-transmit the UDP packet. It would be at-most-once delivery right?
The IP routers in the path will not re-send the UDP packet on their own!
If you’re admitting into the discussion literally any conceivable buggy behavior from public routers you have no control over, then isn’t it pretty clear you can’t have any guarantees about anything whatsoever?
Hello and welcome to the internet. Enjoy your stay!
I think that is the point of these conversations. You shouldn't have application expectations that cannot be met in the real world. Even in your own data center you have far less control over your mirrored switches doing something dumb like sending a stream of packets twice out of their respective interfaces.
In some contexts, sure, you could say literally nothing is "guaranteed." But in this context, we're clearly talking about how distributed systems work in practice, and which behaviors you can reasonably achieve and what tradeoffs you must make. The article clearly states:
> There are essentially three types of delivery semantics: at-most-once, at-least-once, and exactly-once. Of the three, the first two are feasible and widely used.
But in the context you're talking about, even those first two are not "feasible." And in the context you're talking about, there's basically no point in talking about anything you can do to try to achieve certain behavior since there is technically no way to physically guarantee that. What you are saying is definitely not "the point of these conversations," because you're just saying that literally nothing can ever be absolutely guaranteed. Technically true, but not particularly helpful when you're designing real systems to solve real problems, and your systems will mostly operate on infrastructure that mostly does work as intended.
I work in financial data — lots of big ol’ UDP multicast streams getting replicated by big routers in private data centers on private lines.
In that context, everything bad can happen, but it rarely does. For example: packets most definitely get dropped, but not every packet does in practice. Packets can get double-sent, but again, not every packet in practice. Packets can get corrupted randomly, but again, not every packet in practice.
The hard mathematical guarantee: nothing at all! You will get a packet from 0 to N times, where N might be arbitrarily large.
The in-practice behavior: mostly kinda works, but be careful! Have a strategy for reordering, a strategy for detecting and handling dupes, and a strategy for when you need to just give up and start from scratch.
The internet is like that but if some router is screwing it up, you can’t call the owner and complain.
You're not trying hard enough. I spent an afternoon on the phone with an ISP in Boston letting them know their BGP was hosed, and consequently black hole'ing my traffic. I had the traceroutes and whois data to prove it.
Nowadays though, it is getting much harder to do so however. I know there's a secret IRC of black belt NetOps out there, but I haven't managed to figure out how to route myself there yet.
(Rumor has it there's a router out there with a reliably flaky network card that'll mangle the packets juuuuuust right. Personally, I think it's all hooey and someone has a really neat IPTables file complete with port knocking)
There's a bit of daylight between "feasible" and "guaranteed".
It turns out it really isn't that much daylight, and it's really easy to overestimate the size of that window. As you scale up, that window gets smaller and smaller, too, which makes it even more exciting.
Nevertheless, it is indeed where real systems are built.
I also disagree that realizing that nothing can be guaranteed is not important to building systems. The more you scale up, the more important it is. It's hugely important. It's one of the major things that separates people who can build real network systems at scale and those who can't. Far from the only such thing, but certainly one of the important ones.
In a broadcast scenario it only takes a temporary instability in the routing tables to cause packets to be duplicated. It's less of an issue nowadays, but you don't control the Internet. It's not a bug because it's not guaranteed that a message won't be delivered twice.
> you can’t have any guarantees about anything whatsoever?
On public networks, yes.
Of course in many cases andyou have to limit what edge cases you deal with unless you have infinite development time, but unexpectedly repeated UDP packets are definitely something that happens often enough to account for it if your protocol could be adversely affected by it.
Packets can and will be queued in multiple outgoing interfaces.
Dumb shit happens in network kit.
Also, the new SDN stuff sends packets multiple times over different paths on purpose. It's supposed to discard everything except the one that got there first, but...
In TCP in particular there can be a lot of duplication due to missed packets or packets that arrive just a little too late.
On noisy wifi you're transferring data, and the destination finally gets enough packets to send an ACK for the sliding window, only the source never gets the ACK, so it sends the packets it thinks you want but already have. Some of those get through, and the destination realizes it needs to send the ACK again because clearly you didn't get it the first time. Finally you resync and start getting new data, until the next cup of coffee goes into the microwave and it all repeats again.
Since many UDP protocols end up re-implementing half of TCP, you're going to have some of the same failure modes.
An easy-to-imagine scenario is that a router with multiple egress paths emits the UDP packet on multiple interfaces. The packets take different routes but both arrive at the destination.
With multiple egress paths different packets from the same stream can be sent using different routes and arrive to the destination at different order but each packet should be delivered at most once. Unless there is a bug in the router which duplicates packet - possible in theory but in 20+ year practice I haven't see one. This is not to say routers are bug free, just this exact problem is not what I would expect.
Switch A and B are connected to each other with two links, we'll call those 1 & 2.
They're supposed to run STP or bonding or something to make 1 & 2 a logical single link, but that's misconfigured, misbehaving, or just plain old buggy.
By sheer bad luck, switch B has currently overflowed its MAC lookup table, and is falling back to broadcast for your destination MAC.
You send a packet to switch A. Switch A looks up the destination MAC, and forwards the packet to link 1. Switch B receives the packet, has no idea where that MAC is, and forwards it to links 2-n. Switch A receives the packet, looks up the destination MAC, and and forwards the packet to link 1. Rinse, repeat. Observe packets sent by switch B on ports 3-n.
That's silly. If we followed your logic, there is no such thing as "at most once" delivery. It's actually "exactly-once" delivery, since if it is 0 it is not a delivery.
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.