Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Falsehoods programmers believe about TCP

lwn.net

Post reply on HN
Print view View original

231–240 of 247 posts

Re: Falsehoods programmers believe about TCP

#231

Post by shepherdjerred »

lisper wrote: post #229
shepherdjerred wrote: post #226

Earlier quoted context omitted.

> All you need to do is discard duplicates at the receiver. ...yes, which would be exactly once _processing_ but not exactly once _delivery_. Unless you're wanting to redefine "exactly once delivery" to mean "at least once delivery but I'm calling it exactly once because I have a strategy to cope with duplicate messages"

> exactly once _processing_ but not exactly once _delivery_ What exactly is the difference? What counts as "delivery"? How do you do "delivery" (on a computer) without doing at least some "processing"?

Delivery is communication between two actors. Processing is what one actor (the receiver) does with a message.

Communication is when two actors exchange a message. Communication is generally done over an unreliable medium because in practice there is no way to communicate without the potential of failure.

1. Exactly once communication between two actors over an unreliable medium is impossible. At the very least you have to account for the possibility of failure of the medium, so you might need to re-send messages.

2. At least once communication between two actors is possible -- just re-send a message until the receive acknowledges the message.

3. Because a message might be re-sent, the receiver must be able to cope with duplicate messages. This is what you're describing. This might be done by making message processing idempotent or tracking which messages you've seen before. In either case, you have achieve exactly once processing. That is, if a receiver is given the same message multiple times, only the first receive of the messages changes the state of the receiver.

---

> But exactly-once delivery is not only possible, it's trivial.

Considering that many in the field consider this problem to be impossible (or, at best, extremely difficult, e.g. https://www.confluent.io/blog/exactly-once-semantics-are-pos...), this should be a huge red flag to yourself that you're missing something. Everyone has blind spots and that's okay, but hopefully you understand that there's a pretty big mismatch here.

Alternatively, it's possible that this problem _really_ is trivial and you have some unique insight which means there's a great opportunity for you to write a paper or blog post.

Re: Falsehoods programmers believe about TCP

#232

Post by sethammons »

lisper wrote: post #230
sethammons wrote: post #228

Earlier quoted context omitted.

Change your words from "delivery" to "processing" and you in alignment with reality. Idempotent processing is exactly once processing. This is true. Delivery is from the sender's point of view, not the recipient. How the recipient processes the information, idempotently or not, is not the concern of the sender. "Cannot have exactly-once delivery" is true and is as true as not dividing by zero. Read about the two gene…

> Change your words from "delivery" to "processing" and you in alignment with reality. You are not the first to say this, but so far no one has been able to explain what the difference between "delivery" and "processing" is. How do you do "delivery" (on a computer) without also doing (at least some) "processing"? > Delivery is from the sender's point of view, not the recipient. I don't see what difference that makes.…

I gave two concrete examples. What about each of those examples is not landing?

One of shouting at your friend. You want to make sure your friend knows someone is at the door. Two: you tell your computer to transfer money and you don't want to be doubled charged.

More in depth: you click send money on a computer. The computer connects to another computer and sends data to it over an unreliable network. Computer A sends data over the network to B, just like you shouting to your friend you think is in the other room. Data can be lost / your friend might not hear you. Usually, the other computer says "acknowledged, I got your message" - and that is how know that B is moving money or your friend is getting the door. If A never hears back, should A try again? If B gets two requests to move $25, should that be deduplicated or was there two actual requests and $50 should be moved? To know how to solve that, you have to first admit that you might get 0, 1, or multiple messages delivered to B when A wants to send 1 message.

Read the two general's problem. It is the gateway to distributed computing.

Re: Falsehoods programmers believe about TCP

#233

Post by sethammons »

lisper wrote: post #220
sethammons wrote: post #194

Earlier quoted context omitted.

Read the two general's problem. It is a mathematical impossibility. The counter is the delivery counter. Delivery, delivery + 1

What makes you think the 2GP is relevant here? The 2GP has to do with coordination and consensus, not exactly-once delivery.

You are correct

Re: Falsehoods programmers believe about TCP

#234

Post by bcoates »

rcxdude wrote: post #207
bcoates wrote: post #53

Earlier quoted context omitted.

This is a popular saying that is basically wrong. You have very limited guarantees around an arbitrarily bad partition, but this is also a detectable condition. Lots of defective systems exist, but in general non-defective systems generally guarantee "exactly once delivery or detected failure"

That sounds like "at most once" to me

If you unplug the network you can't send messages, correct.

Other people upthread have already gone over how you can't separate delivery from message processing and how TCP's attempt to do so makes it defective (unless you layer a whole additional system on top of it rendering most of TCP's design irrelevant)

If you were trying to make a new, non-broken system on top of TCP or otherwise, allowing multiple delivery doesn't add any correctness/robustness benefits -- it just makes messages cheaper to send and receive. There is no "at most once or at least once" choice except in the pickwickian sense that if you don't require delivery or delivery confirmation you can save the effort of even trying.

Re: Falsehoods programmers believe about TCP

#235

Post by paulddraper »

Rygian wrote: post #225
paulddraper wrote: post #154

Earlier quoted context omitted.

More immediate response to disconnection. Rather than "IDK keep sending but I haven't heard ACK in a while"

When the disconnection is brief, there's no need to respond to it. It's the conceptual equivalent of your phone "helpfully hanging up" when you change the phone from one ear to the other during a call.

It's the conceptual equivalent of your phone helpfully hanging up when you turn on airplane mode.

Re: Falsehoods programmers believe about TCP

#236

Post by lisper »

shepherdjerred wrote: post #231
lisper wrote: post #229

Earlier quoted context omitted.

> exactly once _processing_ but not exactly once _delivery_ What exactly is the difference? What counts as "delivery"? How do you do "delivery" (on a computer) without doing at least some "processing"?

Delivery is communication between two actors. Processing is what one actor (the receiver) does with a message. Communication is when two actors exchange a message. Communication is generally done over an unreliable medium because in practice there is no way to communicate without the potential of failure. 1. Exactly once communication between two actors over an unreliable medium is impossible. At the very least you h…

> hopefully you understand that there's a pretty big mismatch here

Yep. But on the other hand, 1) I have a Ph.D. in CS, and 2) I have yet to see anyone in this thread actually produce a reference to a reliable source to back up the assertion that exactly-one delivery is impossible. Indeed, the one reference you provided has a headline "Exactly-Once Semantics Are Possible" so you are actually supporting my position here.

Finally, I will point out something that should be obvious but apparently isn't: "exchanging a message" between computers over a network is a metaphor. There is not anything that is actually exchanged, no material transferred from one computer to another. There is only information sent in the form of electrical signals which results in state changes in the receiving system, so there is no clean boundary between "communication" and "what the receiver does with a message". Receiving a message in the context of a computer network is necessarily "doing something" with that message. There is no other way to "receive" a message.

Re: Falsehoods programmers believe about TCP

#237

Post by lisper »

sethammons wrote: post #232
lisper wrote: post #230

Earlier quoted context omitted.

> Change your words from "delivery" to "processing" and you in alignment with reality. You are not the first to say this, but so far no one has been able to explain what the difference between "delivery" and "processing" is. How do you do "delivery" (on a computer) without also doing (at least some) "processing"? > Delivery is from the sender's point of view, not the recipient. I don't see what difference that makes.…

I gave two concrete examples. What about each of those examples is not landing? One of shouting at your friend. You want to make sure your friend knows someone is at the door. Two: you tell your computer to transfer money and you don't want to be doubled charged. More in depth: you click send money on a computer. The computer connects to another computer and sends data to it over an unreliable network. Computer A sen…

> I gave two concrete examples.

Neither of which was on point because they both ignored how exactly-once delivery can be done.

> Read the two general's problem.

The 2GP is not on point because it's about achieving consensus, not exactly-once delivery. Achieving consensus is indeed impossible with unreliable messaging, but that has nothing to do with exactly-once delivery.

Re: Falsehoods programmers believe about TCP

#238

Post by Rygian »

paulddraper wrote: post #235
Rygian wrote: post #225

Earlier quoted context omitted.

When the disconnection is brief, there's no need to respond to it. It's the conceptual equivalent of your phone "helpfully hanging up" when you change the phone from one ear to the other during a call.

It's the conceptual equivalent of your phone helpfully hanging up when you turn on airplane mode.

Turning on airplane mode explicitly signals "sever all communications" in a way that making a quick adjustement of an ethernet plug does not.

Re: Falsehoods programmers believe about TCP

#239

Post by yetihehe »

speff wrote: post #192
ahoka wrote: post #100

Earlier quoted context omitted.

The screen knows what color it displays at all times. It knows this because it knows what it doesn't. By subtracting what it does from what it doesn’t, or what it doesn’t from what it does (whichever is greater), it obtains a difference, or deviation. The controller board uses deviations to generate corrective commands to drive the display from a state where it does not display black to a state where it does, and arr…

For the uninitiated: The Missile Knows Where It Is[1] [1]: https://youtu.be/bZe5J8SVCYQ

There is also version for those already initiated [1].

[1] https://www.youtube.com/watch?v=_LjN3UclYzU

Re: Falsehoods programmers believe about TCP

#240

Post by account42 »

foota wrote: post #123
cubano wrote: post #89

Earlier quoted context omitted.

Uhhh....how does the screen show black?

It depends afaict. OLED screens have a per-pixel light, and they turn off pixels to make black. LCDs have a single large backlight and pixels that the light shines through and they can change color (but not turn off) so in that case they turn as opaque as possible, but don't completely block the light.

Black pixels in an OLED still reflect some light so their are not completely black either.
Post reply on HN