Nagle, delayed ACKs and small writes

Nagle and the delayed ACK

In 1984 John Nagle described a network collapsing under its own headers: terminal sessions sent each keystroke as a packet of its own, one byte of data behind 40 bytes of IP and TCP header. His rule, Nagle’s algorithm, is this: while data the connection has sent is unacknowledged, new small writes, those shorter than the MSS, are held, and they go out together when the acknowledgement arrives or when they fill a segment. Full segments are never held. A stream of small writes then leaves at one segment per round trip, at the price that a small write can wait a round trip it had no need to wait. Linux holds a small segment only while an earlier small segment is unacknowledged, a slightly relaxed form, and applies the rule to every TCP socket by default.

The delayed acknowledgement is the same thrift at the other end. A receiver that waits a little before acknowledging may find its program replying, so that the reply carries the acknowledgement for free, or a second segment arriving, so that one acknowledgement covers both. The standard allows the delay, caps it at 500 ms and asks for an acknowledgement for at least every second full-sized segment. Linux’s delayed-ACK timer starts at its minimum, 40 ms, and can grow to 200 ms. A Linux connection acknowledges every segment at once for its first few, in quick-ack mode, and leaves that mode once the conversation looks interactive, its program replying soon after each request, because then a reply will usually be there to carry the acknowledgement.

Each rule is sensible alone. Together they can stall one common pattern, write-write-read: the sender writes a message in two pieces and then waits for the reply. The first piece goes at once, since nothing is in flight. The second is small and the first is unacknowledged, so Nagle holds it. At the far side the first piece is half a message, which the program cannot answer, and a single small segment, which the kernel does not acknowledge at once. Each side waits for the other until the delayed-ACK timer fires. Across one switch, the first piece arrives, the peer’s delayed-ACK timer expires, its ACK returns, and only then does the held piece leave.

If the timer is 40 ms and this pattern triggers on each exchange, every message costs about 40 ms, so a request-and-reply protocol built on the pattern manages 25 exchanges a second, whatever the link can carry.

Linux adds a shorter hold of its own, autocorking, on by default. A small write made while an earlier packet of the same socket is still in the qdisc or the card’s transmit ring is held until the card’s completion for that packet has been processed, so that the two leave together. It applies with Nagle off as well, and lasts a few microseconds, or tens if transmit interrupts are coalesced. Even whole-message writes can encounter autocorking when a previous packet remains queued; packet traces reveal whether it matters.

The options

TCP_NODELAY turns Nagle’s algorithm off for one socket: every write is sent as soon as the congestion and receive windows allow, however small. What it costs is what Nagle was written to prevent, a program that writes in pieces sending many small packets, each with 70 bytes of envelope and FCS. So it comes with a discipline: build each message whole and write it with one call, or gather its pieces into one call with write_vectored, the writev system call. It does nothing to the far side’s delayed acknowledgements, and does not need to, because Nagle no longer holds a small write for them. Congestion and receive-window limits can still make the sender wait for acknowledgements.

TCP_CORK is the opposite instruction. While it is set, the socket sends only full segments and holds partial ones, for at most 200 ms, and clearing it sends whatever is held at once. It is for a sender that writes a header, a body and a trailer in three calls and wants them in one segment, and while both options are set the cork wins over TCP_NODELAY. A cork that is never cleared costs 200 ms a message. MSG_MORE is a cork for one call: a flag on send that says more follows, so the data waits for the next send without the flag, and the two system calls of setting and clearing the option are saved.

TCP_QUICKACK acts on the receiving side. It puts the socket in quick-ack mode, but the kernel leaves the mode again by its own rules, so a program that depends on it sets it after every recv, a system call each time. It changes only the acknowledgements this box sends. Autocorking has no socket option; it is the sysctl net.ipv4.tcp_autocorking, for the whole box.

What it costs

From write to the wire, a small segment that nothing holds takes 2–5 µs, 8,000–20,000 cycles and two to five budgets, of which 1–4 µs is the sending thread’s own core inside the call. Serialisation adds 152 ns for the 190-byte frame at 10 GbE, 61 ns at 25 GbE. The indirect costs follow the packet: a transmit completion and its poll on some core, the acknowledgement’s whole receive path, and the bytes held in kernel memory until it arrives. Two threads writing to one socket queue on its lock, and a message either writes in pieces can interleave with the other’s.

The holds are where the orders of magnitude are. Autocorking costs a few to tens of microseconds on a second small write too close behind the first. Nagle alone costs a round trip on a small write made while another is in flight: tens of microseconds across one switch, 70 ms to a venue 35 ms away. Nagle meeting a delayed acknowledgement costs up to 40 ms against Linux, 160 million cycles and forty thousand budgets, and more against a stack with a longer timer. A forgotten cork costs 200 ms; a full send buffer or a zero window, however long the far side takes to read. None of these appears in the return value of write, only as time.

Worked example: a cancel-replace leaves

The order gateway thread is pinned to core 6 and writes to a TCP connection to the venue’s order gateway, in the same rack, one switch away. The strategy has decided, within its 1 µs, to move a resting order: a cancel-replace, 120 bytes. The frame is 14 + 20 + 32 + 120 = 186 bytes, 190 with the FCS, 152 ns on the wire at 10 GbE.

Written with one call on a socket with TCP_NODELAY, the message reaches the wire 2–5 µs after write is called. The card serialises it in 152 ns, the switch forwards it in 300–500 ns, and the venue’s card has it in memory a few hundred nanoseconds later: about 3–6 µs from the call to the venue’s card, before the venue’s own receive path begins. The decision took 1 µs, and leaving took two to five times as long, almost all of it the kernel’s.

Now suppose the gateway writes each message as a 16-byte header by one write_all and the 104-byte body by a second, and leaves Nagle on, as every socket starts. That is the write-write-read of the timeline above. The venue delays its acknowledgements, as Linux does once orders and replies have been alternating on a connection, so, if the delayed-ACK interaction occurs, the cancel-replace is whole at the venue about 40 ms after the strategy decided: forty thousand budgets, long enough for the price the order meant to avoid to have traded many times, on each affected exchange. Quick ACKs or packet merging can prevent this pattern, so the stall is not guaranteed by two writes alone. Against a venue 35 ms away the arithmetic is worse. The header arrives at 35 ms, the delayed acknowledgement leaves at 75 ms and arrives back at 110 ms, and the body arrives at 145 ms, 110 ms after a single write would have. With Nagle off and the two writes kept, the body follows the header by about a microsecond, or by a few more if autocorking holds it for the header’s transmit completion. One write per message costs nothing extra.

The other way to lose time is to lose the core. If the gateway thread shares core 6 with another thread and is preempted between the decision and the write, the cancel-replace waits out the other thread’s time slice: Chapter 2’s 1–4 ms, a thousand to four thousand budgets. A gateway pinned to a core of its own, writing each message once to a socket with Nagle off, pays the 2–5 µs and nothing else.

Seeing it

ss -ti prints, beside each connection’s round trip, timeout, congestion window and retransmit counts, the fields that belong to the send side. ato:40 is the delayed-ACK timeout the socket is using. lastsnd, lastrcv and lastack are the milliseconds since the socket last sent data, received data and received an acknowledgement. unacked counts segments in flight, and notsent, when it appears, counts bytes written and not yet sent, which is where a Nagle hold or a cork shows while it lasts.

tcpdump -ttt -nn -i <iface> host 10.0.0.7 and port 9000 captures the connection and prints, before each packet, the time since the one before it. A Nagle stall is unmistakable: a short data segment from the gateway, a zero-length acknowledgement from the venue stamped about 0.040 seconds later, and the gateway’s held segment a few microseconds after that. nstat -az prints the kernel’s protocol counters as totals, zeros included (without -a, the change since its last run): TcpOutSegs and TcpRetransSegs count segments sent and sent again, TcpExtDelayedACKs acknowledgements this box held until its timer fired, and TcpExtTCPAutoCorking the writes autocorking held. tc -s qdisc show dev <iface> prints each qdisc with its counters, among them dropped, requeues for packets the driver handed back because its ring was full, and backlog, what is queued at that moment; a backlog that is ever non-zero on the gateway’s queue is a small order waiting behind something else.

The kernel can also say what “sent” meant for each write. With SO_TIMESTAMPING and its transmit flags, the socket’s error queue receives a stamp when the bytes entered the qdisc, when the driver handed them to the card, when the card put them on the wire, if it stamps transmissions, and when the far side acknowledged them: the 2–5 µs taken apart write by write, and the closest the kernel comes to telling the program that its bytes arrived.