Slow Down

You want to send Mira a video. It is a few hundred megabytes, and you are sending it from a fast desktop with a fast disk to her laptop, which is old and is writing the file to a slow drive as it arrives. Your machine can put pieces on the wire far faster than her machine can take them off, and it is time to see what that does.

Recall the receiving side from Chapter 11. Pieces arrive at Mira’s operating system, are placed by number into a buffer, and sit there until her program calls read and takes them. The buffer is a fixed size, say sixty-four kilobytes, which is about forty-five pieces’ worth. That is plenty for a chat, and plenty for a photograph if her program reads promptly.

Her program is not reading promptly. It reads a piece, writes it to the slow drive, waits for the drive, and reads the next. Meanwhile your machine is sending pieces as fast as the wire will carry them, which is many times faster than her drive. The buffer fills. Forty-five pieces are sitting in it unread, and piece forty-six arrives. There is nowhere to put it, and her operating system does the only thing it can, which is to drop it.

Now Chapter 11 takes over and makes things worse. You get no acknowledgement for forty-six, so your timer fires and you resend it, into a buffer that is still full, because her program has read perhaps two pieces in the meantime. It is dropped again. You resend forty-seven, forty-eight and forty-nine, all of which were also dropped, all into the same full buffer. The path between you is now carrying a steady stream of pieces that arrive only to be thrown away, plus their retransmissions, plus the retransmissions of those. The wire is busy and almost nothing useful is getting through.

Nothing is broken, not the wire, not the path, not the router. Mira’s machine is slower than yours, and the tower has no way to express that. Acknowledgements say how far she has got. They do not say that she has no room for more.

The receiver knows how much room it has. It is the size of the buffer minus what is sitting in it unread. So it tells the sender, in every acknowledgement: everything up to piece 40, and room for 5 more. And the sender takes on a rule, which is never to have more unacknowledged pieces in flight than the receiver has room for. If Mira says room for five, you may send pieces 41 through 45 and then you stop, however much more you have to send and however fast your wire is, until an acknowledgement arrives saying that she has read some and there is room again.

Her program reads three pieces off the buffer. Her operating system sends an acknowledgement for everything up to 43, with room for 8. Now you may send through 51, and so on. The sender’s pace is set by the receiver’s reading, which is set by the drive. Your desktop sends as fast as her laptop can take it and not one piece faster, and nothing is dropped and nothing is resent. The amount of room the receiver advertises is called the window, and the mechanism is called flow control. It costs two bytes in every acknowledgement, and it is the difference between a transfer that completes and one that thrashes for ever.

Now Mira’s drive stalls for a moment, because some other program on her laptop is also writing to it. Her program stops reading altogether, her buffer fills to the top, and her next acknowledgement says room for zero. You stop, correctly, since there is nothing you are allowed to send. Then her drive recovers. Her program reads twenty pieces, and her operating system sends an acknowledgement with room for 20. That acknowledgement is lost on the way, as Chapter 11 told you acknowledgements can be.

Look at the two ends. You are waiting for an acknowledgement that opens the window. It was sent and lost, and nothing will prompt her to send another, because acknowledgements are sent in response to data and you are not sending any, because the window is closed. She is waiting for data and you are waiting for permission. Both sides are behaving correctly, and both will wait for ever.

This is a deadlock, and it is a real one that real implementations hit. The fix is small, and it is a timer again. When the sender is stopped by a zero window it does not stop completely. Every so often it sends a single tiny piece, one byte, just past the edge of what it is allowed, purely to provoke an acknowledgement. The acknowledgement that comes back carries the current window, and if the window has opened the sender resumes. This is called a zero-window probe, and it is another instance of the rule from Chapter 13: when silence would be ambiguous, say something.

Everything so far has been the two operating systems talking to each other. Now look up, at your program, because this is where the chapter earns its place in the story. Your program called write on the socket with a few hundred megabytes of video, and it expected the call to return promptly, the way it always has. Chapter 9 warned you that one day it would not. This is the day.

Your operating system took those bytes and started sending pieces, keeping a copy of each in the send buffer, which is Chapter 11’s buffer for resends. Then Mira’s window closed and your operating system stopped sending. Your program is still writing. Bytes are still arriving at the send buffer and none are leaving it, and it too is a fixed size, so it fills.

Now your program calls write with the next chunk of video. The send buffer is full and the operating system has nowhere at all to put the bytes. It does what it did in Chapter 9 when there was nothing to read: it parks your program. The write call does not return. Your program is stopped in the middle of the call, and it will stay stopped until Mira’s laptop reads enough that her window opens, that acknowledgement reaches your machine, your operating system drains some of the send buffer onto the wire, and room appears for the bytes your program is holding.

Trace the chain of causes backwards. Mira’s disk is slow, so her program reads slowly, so her receive buffer fills, so her window closes, so your operating system stops sending, so your send buffer fills, so your program is parked inside a write call. A slow disk on one machine has stopped a program on another, through six links, without any of those links having done anything wrong. I find this one of the more satisfying chains of cause and effect in the subject.

That chain has a name. When the slowness of the consumer travels back through the system and slows the producer, rather than the producer overwhelming the consumer or data piling up somewhere in between, the system is said to have backpressure. Backpressure is the single property that most reliably separates systems that degrade under load from systems that fall over under it.

Your program, parked in that write, has been handed a decision it did not ask for. It is the same decision every producer of data faces the moment its consumer is slower than it is, and there are three options and no more. The first is to wait, which is what blocking does. The program stops until there is room. It is correct and it is simple, and it costs you the loop, because a program parked inside write is not at the top of its loop asking what is ready, and every other conversation it is holding is now frozen. Chapter 15 is about that.

The second is to drop, and throw away what cannot be sent. For a video file that is absurd. For a live video call it is the right thing, since a frame that is late is a frame nobody wants, and Chapter 17 will take that fork.

The third is to buffer it yourself. Instead of blocking, you put the bytes in a queue inside your own program and come back to them later. This feels like a solution and it is the most dangerous of the three, because the queue has no size limit unless you give it one, and if the consumer stays slow the queue grows without bound until the program runs out of memory and dies. You have not solved the problem. You have moved it out of a place with a limit into a place without one.

There is no fourth choice. Every system that moves data from a fast thing to a slow thing, whether a socket, a queue, a pipe between programs, a stream of events, or a request to a server, is doing one of these three, whether its author knows it or not. The ones that fall over are the ones whose author did not know, and buffered without bound by default.

Your video reaches Mira at the speed of her drive, with nothing dropped and nothing resent, because her machine tells yours how much room it has and yours believes it. You have also learned what it means when write blocks. It means that someone, somewhere down the line, is slower than you, and the tower has faithfully carried that fact all the way back up to your program. That is not a fault; it is the system working. What you do about it is the subject of the next chapter, because you promised the operating system that you would never park the loop, and write has just parked it.