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

161–170 of 247 posts

Re: Falsehoods programmers believe about TCP

#161

Post by Ayyyyyron »

Izkata wrote: post #155
Ayyyyyron wrote: post #145

Earlier quoted context omitted.

The principal difference between 'at most once' and 'at least once' is whether a sender re-tries when it is unsure if the recipient has received the message. If the recipient's ack never makes it back, then a sender cannot know whether they actually received the message or not (the two-generals problem). So this hypothetical middleman will receive a packet, check that it's not a duplicate, and forward it to the recip…

> So this hypothetical middleman will receive a packet, check that it's not a duplicate, and forward it to the recipient it's proxying for. How will it know that the recipient has actually received it? It seems like the answer is in the first part, the "check that it's not a duplicate". Implement at-least-once but with a unique token to identify the request, and the receiver sends back acknowledgement with that token…

Yes, but the handoff can fail in the same way (it can't know if the thing it's handing off to actually got it). But the application can also just be resilient to that with idempotent operations and have the handoff be at-least-once.

Re: Falsehoods programmers believe about TCP

#162

Post by lisper »

Ayyyyyron wrote: post #160
lisper wrote: post #151

Earlier quoted context omitted.

> So this hypothetical middleman will receive a packet, check that it's not a duplicate, and forward it to the recipient it's proxying for. That's not how I would implement exactly-once on top of at-lest-once. I would do it at the recipient, not at the intermediate nodes. > 'exactly once' delivery is impossible because you can't know if the recipient actually got the message But the recipient can know.

But the recipient is not one atomic thing - we're assuming perfect communication between the process/driver/hardware receiving the packets and doing the duplicate detection and the process which wants to receive the message exactly once. There's still communication happening there, and it can still fail. Buffers fill, processes pause for arbitrary delays which exceed timeouts, etc. Your assumptions based on your mode…

> we're assuming perfect communication between the process/driver/hardware receiving the packets and doing the duplicate detection and the process which wants to receive the message exactly once

My claim is not that you can provide exactly-once delivery unconditionally. My claim is that if you can provide at-least-once delivery then you can turn that into exactly-once delivery. The word "delivery" is not rigorously defined, but IMO any reasonable definition necessarily entails a certain level of reliability at the receiving node.

Re: Falsehoods programmers believe about TCP

#164

Post by kmeisthax »

lisper wrote: post #64
solatic wrote: post #22

Related: you can get at most once delivery or at least once delivery; you cannot get exactly once delivery. If I had a dollar for every junior who thought that a lack of exactly once delivery guarantees was a bug...

If you can get at-least-once delivery, why can you not build exactly-once on top of that? [UPDATE] Apparently I need to be more explicit about this. My question is: if I can get at-least-once delivery, why can I not build an abstraction layer on the receiving node that provides the illusion of exactly-once delivery? It seems like it should be a simple matter of keeping a log of received messages, and discarding dupli…

The problem is that sometimes your application intends to send messages[0] multiple times. If your "log-and-discard" system was implemented naively then each node could only ever send each possible message once and only once. Ever.

That would be like:

Alice: "Honey, where did you put the keys?"

Bob: "They're up on the counter."

(The next day...)

Alice: "Honey, where did you put the keys?"

Bob: (nothing, I already received this message, it could have echoed off the walls from yesterday)

What you need is for all sent messages to have unique IDs that will never repeat, and then log those. That's known as an idempotency token.

But even then, logging all those UUIDs forever is probably not a good idea for disk usage. At some point you'll have to trash old message logs and hope you don't have a rogue network router retransmitting six month old messages or something.

[0] Or the moral equivalent of messages, e.g. HTTP POST requests

Re: Falsehoods programmers believe about TCP

#165

Post by nirui »

> If the connection breaks while an ACK is outstanding, the sender will have no way of knowing whether the segment was received

The real question is, why this should be a problem that TCP must solve? TCP gives you a bidirectional waterflow-like pipe, and that's enough for you to create many useful applications. TCP never provided guarantee for correct delivery, that's your job.

For example, if a HTTP request is interrupted before the respond is received, the sender should assume the request never reach the server and try again with a new connection, while the server should mitigate duplicated requests (reject or return a successful code).

Well, maybe that's the point of the article, because many web pages gets confused if you send duplicated requests to them.

Re: Falsehoods programmers believe about TCP

#166

Post by Ayyyyyron »

lisper wrote: post #162
Ayyyyyron wrote: post #160

Earlier quoted context omitted.

But the recipient is not one atomic thing - we're assuming perfect communication between the process/driver/hardware receiving the packets and doing the duplicate detection and the process which wants to receive the message exactly once. There's still communication happening there, and it can still fail. Buffers fill, processes pause for arbitrary delays which exceed timeouts, etc. Your assumptions based on your mode…

> we're assuming perfect communication between the process/driver/hardware receiving the packets and doing the duplicate detection and the process which wants to receive the message exactly once My claim is not that you can provide exactly-once delivery unconditionally. My claim is that if you can provide at-least-once delivery then you can turn that into exactly-once delivery. The word "delivery" is not rigorously d…

I agree with your claim, a recipient can cope with at-least-once delivery by being idempotent. You're right.

The meaningful distinction is that something on the recipient needs to be idempotent because the message might get received twice. The application can be oblivious to this, so long as you assume that channel to be perfect.

People on the Internet won't like you calling it 'exactly once delivery' because it's not exactly once - it's an idempotent at-least-once. Which is great! But the statement of the at-least/at-most problem is making a decision to re-try. There's no middle ground, I either have to retry or not. People won't like a claim that 'exactly once' delivery is possible, because it isn't, it's just moving the at-least-once-ness to somewhere else.

Re: Falsehoods programmers believe about TCP

#167

Post by lisper »

kmeisthax wrote: post #164
lisper wrote: post #64

Earlier quoted context omitted.

If you can get at-least-once delivery, why can you not build exactly-once on top of that? [UPDATE] Apparently I need to be more explicit about this. My question is: if I can get at-least-once delivery, why can I not build an abstraction layer on the receiving node that provides the illusion of exactly-once delivery? It seems like it should be a simple matter of keeping a log of received messages, and discarding dupli…

The problem is that sometimes your application intends to send messages[0] multiple times. If your "log-and-discard" system was implemented naively then each node could only ever send each possible message once and only once. Ever. That would be like: Alice: "Honey, where did you put the keys?" Bob: "They're up on the counter." (The next day...) Alice: "Honey, where did you put the keys?" Bob: (nothing, I already rec…

> What you need is for all sent messages to have unique IDs that will never repeat, and then log those. That's known as an idempotency token.

So your problem is not really a problem because you yourself present the solution. The real problem is:

> But even then, logging all those UUIDs forever

But you don't need to log them all forever. Just make the UUIDs sequential, and all you need then is to keep track of the smallest id that has not yet been received. (You can be more efficient by storing more state, but it's not necessary. Remember, we're assuming at-least-once deliver here, so you can always force retransmission by not acknowledging receipt.)

Re: Falsehoods programmers believe about TCP

#168

Post by erik_seaberg »

nirui wrote: post #165

> If the connection breaks while an ACK is outstanding, the sender will have no way of knowing whether the segment was received The real question is, why this should be a problem that TCP must solve? TCP gives you a bidirectional waterflow-like pipe, and that's enough for you to create many useful applications. TCP never provided guarantee for correct delivery, that's your job. For example, if a HTTP request is inter…

The server may or may not have seen the request, and the https://en.wikipedia.org/wiki/Two_Generals%27_Problem proves it impossible to know in every case (no matter how many acks, the last could be dropped). A request that alters state should be retried using the same idempotency key, and the server should try to ack with whether the requested work already happened.

Re: Falsehoods programmers believe about TCP

#169

Post by akira2501 »

lisper wrote: post #128
akira2501 wrote: post #110

Earlier quoted context omitted.

The mechanism you're describing already exists. TCP has sequence numbers. It can drop duplicate data. The difference between "processing" and "delivery" relates to "network capacity." Process handling wastes capacity in favor of latency. Delivery handling increases latency in favor of capacity. Systems which have "exactly once" delivery typically do so with "send/receive" and "release/delete" message pairs. You need…

> The mechanism you're describing already exists. Yes, I know, which makes it all the more bizarre that people are claiming that this is impossible. > Systems which have "exactly once" delivery typically do so... Ah, so exactly-once delivery is possible after all?

If your goal is simply to look smart then absorbing the subtlety of what is said to you before you reply should be top of list.

Re: Falsehoods programmers believe about TCP

#170

Post by devman0 »

jerf wrote: post #111
devman0 wrote: post #95

Earlier quoted context omitted.

Falsehoods programmers believe: the OSI model is useless

Sure, it's misleading, needs a lot of "interpretation" doing a non-trivial amount of the lifting to make it map to anything in the real world, mismatches things that happen in the real world while leaving no room for other things that happen in the real world a lot, and will lead anyone who tries to use it to understand the real world deeply astray, but it isn't always wrong about absolutely everything so it has some…

Analogies are rarely perfect, that's why they are analogies. The OSI model isn't intended to be perfect and yeah there are a lot of details that leak between layers, but is also expected, any non-trivial abstraction is always going to be leaky. That doesn't mean it useless or absent of value in discussion at appropriate levels.
Post reply on HN