Проблема производительности TCP вызванная взаимодействием алгоритма Наггла (Naggle’s Algorithm) и отложенным подтверждением (Delayed ACK)

Ниже представлен перевод статьи  Stuart Cheshire, которую он опубликовал  20 мая 2005 года. Оригинал статьи можно посмотреть по адресу http://www.stuartcheshire.org/papers/NagleDelayedAck/.

На этой странице описывается проблема производительности TCP, которая является результатом малоизвестного взаимодействия между алгоритмом Наггла и отложенным подтверждением (delayed ACK). По крайней мере, я думаю, что он малоизвестен, т. к., не видел задокументированной её где-то ещё, при этом во время моей работы в Apple я сталкивался с этой проблемой производительности снова и снова (первый раз случился, когда я писал код для PPCToolbox over TCP  в 1999 году). Поэтому, я считаю, что пришло время, чтобы эта проблема была наконец-то задокументирована.

Говоря вкратце, существует много механизмов, которые делают TCP поистине превосходным, подобно быстрой ретрансляции (fast retransmit), которые работают превосходно когда существует непрерывный поток данных для работы машины состояний TCP. Если вы отправляете блок данных и затем останавливаетесь в ожидании сообщения уровня приложения с другой стороны, то машина состояния может споткнуться. Это отчасти подобно тому, как водяной насос теряет напор в трубе — до тех пор, пока труба полна воды, водяной насос работает хорошо, но если в трубе мало воды и она смешана с воздухом, то насос начинает работать вхолостую, т.к. крыльчатке нечего проталкивать далее.

Если вы пишете протокол уровня приложения с возможностью запроса/ответа используя TCP протокол, то следствием этого будет, то что вы захотите сделать вашу имплементацию как минимум с двойным буфером: отправив ваш первый запрос и ожидая ответа на него, вы формируете и отправляете второй запрос. Затем, когда вы получаете ответ от первого, то формируете и отправляете третий запрос. Таким образом, у вас всегда есть два отправленных запроса. Пока вы ожидаете ответа на запрос n, запрос n+1 находится за ним, продолжая проталкивать данные.

Интересно, что выигрыш производительности который вы получаете при замене алгоритма с одним буфером, на двух-, трех- или четырёхбуферный алгоритм нелинеен. Имплементация алгоритма двойной буферизации обычно даёт почти все улучшение производительности, которое можно получить, имплементируя алгоритм с тройной, четверной или ещё большим количеством буферов обычно даёт лишь минимальный прирост. Так происходит потому, что неважно как много данных в пайплайне, важно, что в пайплайне есть хоть какие-то данные следующие за пакетом, ответ на который вы ожидаете получить. До тех пор, пока существует хотя бы один пакет с данными следующий за пакетом, ответ на который вы ожидаете, этого будет достаточно для устранения патологического снижения производительности описанного здесь. Существование как минимум четырех или пяти пакетов с данными, достаточно для срабатывания механизма быстрой ретрансляции, в случае потери пакета, который вы ожидаете.

Пример использования: программа тестирования производительности WiFi

В этом документе я опишу мою последнюю встречу с подобным плохим взаимодействием между алгоритмом Наггла и отложенным подтверждением: тестируемая программа использовалась для тестирования соответствия WiFi. Данная программа тестирует скорость имплементации WiFi непрерывно отправляя 100 000 байт данных через TCP и затем ожидая подтверждения уровня приложения, что данные были получены. В Windows достигалась скорость 3,5Mb/s требуемая для прохождения теста; в Mac OS X достигалось всего-лишь 2,7Mb/s и тест проваливался. Наивное (и ошибочное) заключение было бы в том, что Windows быстрее, а Mac OS X медленнее. Однако истина не так очевидна. Настоящее объяснение заключалась в том, что тест был неправильно написан и в Mac OS X удалось увидеть проблему, в то время как в Windows посчастливилось избежать этого.

Инженеры обнаружили, что уменьшение размера оправляемого буфера со 100 000 байт до 99 912 байт увеличивало скорость до 5,2Mb/s и легко проходило тест. Но уже при размере буфера в 99 913 байт скорость снижалась до 2,7Mb/s и тест проваливался. Ясно, что происходящее здесь являлось более интересным, чем простое замедление работы беспроводной сетевой карты или драйвера.

Диаграмма ниже показывает трассировку пакета TCP с проваленной передачи данных, которая достигает только 2,7Mb/s, созданную используя tcptrace и jPlot.

Следующая диаграмма показывает трассировку пакета при использовании 99912-байтового блока, который достигает скорости 5,2Mb/s и успешно проходит тест.

В худшем из случаев код успешно отправляет данные с 0 до 200ms, затем ничего не делает с 200 до 400ms, затем отправляет данные вновь с 400 до 600ms, затем вновь ничего не делает с 600 до 800ms. Почему же в действительности происходят паузы? Для понимания этого необходимо понимать механизм отложенного подтверждения и алгоритм Наггла.

Отложенное подтверждение

Отложенное подтверждение означает, что TCP не подтверждает немедленно каждый полученный TCP сегмент (когда вы это читаете, думайте об интерактивной SSH сессии, к примеру, а не о сессии массивной передачи данных). Если вы получаете единственный TCP сегмент, вы ожидаете от 100 до 200 миллисекунд исходя из предположения, что получающее приложение будет вероятно формировать ответ (например, каждый раз когда sshd получает строку, то сервис формирует символы для эхо в ответе). Вы не захотите, чтобы TCP стек отправлял пустой ответ ACK, а следом за ним, спустя 1мс пакет с данными TCP, поэтому когда вы выполняете небольшую задержку, вы можете объединить пакет ACK совместно с пакетом данных в один. Пока всё хорошо, но что если приложение не формирует никаких данных в ответ? В этом случае какая разницу делает небольшая задержка? Если нет данных в ответ, то клиент может не ожидать ничего, не так ли? И клиент уровня приложения может и не ожидать ничего, но стек TCP в конце может ожидать, и это то место, где алгоритм Наггла выходит на сцену.

Алгоритм Наггла

Для более эффективной работы вы хотите отправлять полноразмерные пакеты TCP с данными. Алгоритм Наггла говорит, что если у вас есть несколько байт для отправки, но их не набирается на полный пакет, и вы уже имеете переданные, но не подтвержденные пакеты в пути, тогда вы должны ожидать до тех пор, пока либо приложение не даст вам больше данных для передачи, достаточных для создания ещё одного полноразмерного пакета с данными, или же ожидать завершения подтверждения неподтвержденных пакетов в пути, с тем, чтобы неподтвержденных пакетов больше не осталось.
Обычно это хорошая идея. Алгоритм Наггла защищает сеть от тупых приложения, которые делают нечто похожее, в то время как наивный стек TCP может отправить 100 000 однобайтовых пакетов.

for (i=0; i<100000; i++) 
    write(socket, &buffer[i], 1);

Проблема взаимодействия в том, что сейчас есть что-то на стороне отправителя, ожидающее ответа от сервера. Это что-то и является алгоритмом Наггла ожидающим подтверждения для данных в пути, которые были отправлены ранее.
Следующую вещь, которую нужно знать это то, что отложенное подтверждение применяется в единственному пакету. Если второй пакет прибывает, то ACK формируется незамедлительно. Таким образом, TCP будет отвечать на каждый второй пакет немедленно. Отправьте два пакета и вы немедленно получите ACK. Отправьте три пакета и вы получите немедленное подтверждение о доставке первых двух пакетов и 200 миллисекундную задержку перед подтверждением третьего.
Вооружённые этой информацией, мы можем сейчас понять, что происходит. Давайте взглянем на числа:

99,900 байт = 68 полноразмерных 1448-байтовых пакетов, плюс 1436 байт дополнительно
100,000 байт = 69 полноразмерных 1448-байтовых пакетов, плюс 88 байт дополнительно

С 99 000 байтами, вы отправляете 68 полноразмерных пакетов. Наггл удерживает последние 1436 байт, затем:

  • Ваш 68 пакет (чётный) немедленно подтверждается получателем.
  • Наггл получает ACK и выпускает оставшиеся 1436 байт
  • Получатель получает оставшиеся 1436 байт и задерживает отправку ACK
  • Серверное приложение формирует однобайтовый ответ-подтверждение уровня приложения о доставке
  • Удерживаемый ACK объединяется с этим одним байтом и отправляется сразу

…и всё проходит (относительно) гладко.

Сейчас рассмотрим случай со 100 000 байт. Вы отправляете поток из 69 полноразмерных пакетов. Наггл удерживает последние 88 байт. Затем:

  • Получатель подтверждает каждый второй пакет вплоть до 68 пакета
  • Прибывает ещё один, 69 пакет
  • Задерживаемое подтверждение означает, что получатель не подтвердит этот пакет до тех пор пока
    1. Не получит некоторой порции данных из локального процесса, или
    2. Другой пакет от отправителя
  • Локальный процесс не будет формировать ответ, т. к. он ещё не получил полностью 100 000 байт ещё
  • Отправитель не будет отправлять последний пакет, потому что Наггл, не позволит это сделать до тех пор, пока не получит подтверждение от получателя

Теперь мы получили дедлок, с результатами убивающими производительность:

  • Наггле не отправит последнюю часть данных, до тех пор пока не получит подтвреждение
  • Отложенное подтверждение не будет отправлено до тех пор пока не получит некоторые данные для ответа
  • Серверный процесс не будет формировать ответ до тех пор пока не получит все данные
  • Но Наггл не будет отправлять последнюю часть данных… и т. д.

Таким образом, в конце каждого 100 000-байтового блока мы получаем эту небольшую нелепую паузу. В конце-концов, отложенный таймер подтверждения срабатывает и взаимная блокировка расклинивается до следующего раза. На гигабитной сети эти огромные 200-миллисекундные задержки могут быть разрушительными для протокола передачи данных уровня приложения. Подобные паузы могут ограничить количество запросов/ответов до не более пяти в секунду, в сети где есть возможность тысяч транзакций в секунду или больше. В данном тесте должна быть возможность передачи каждого 100 000-байтного блока через гигибитный Ethernet менее чем за одну миллисекунду. Вместо этого, т. к. происходит остановка и ождание каждого блока, вместо использования двойной буферизации, как это рекомендовано выше, отправка каждого 100 000-байтного блока занимает 1ms + 200ms = 201ms, делая тест более медленным примерно в 200 раз чем это должно быть.

Почему же Windows не пострадала от этой проблемы?

В системах Windows размер сегмента TCP равен 1460 байтам. На Mac OS X и других системах, которые добавляют таймстамп TCP, размер сегмента на 12 байт меньше — 1448 байт.
А это значит, что на Windows 100 000-байт представлены в виде 68 полноразмерных пакетов, плюс дополнительные 720 байт. Т.к. 68 чётное, то по чистой случайности приложение обошло взаимодействие алгоритма Наггла с отложенным подтверждением.

При этом на Mac OS X 100 000 байт представлены 69 полноразмерными 1448-байтными пакетами с дополнительными 88 байтами. Т.к. 69 нечётное, то на Mac OS X раскрыл проблему приложения.

Грубый способ решения проблемы, не такой эффективный как подход с использованием двойной буферизации, заключается в том, чтобы приложение отправляло каждое семантически значимое сообщение используя единственный вызов write (либо копируя сообщение в продолжающийся буфер, либо используя операции подобные sendmsg) и установке параметра сокета TCP_NODELAY, тем самым блокирую работу алгоритма Наггла. И хотя подобное решение устранят текущую проблему, однако может всё ещё вызывать другие проблемы свойственные, если не использовать двойную буферизацию, в частности если последний пакет ответа будет потерян, то не будет пакетов следующие за ним и вызывающие сработку быстрой ретрансляции.

Обновление от ноября 2012 года. Какой текущий статус проблемы?

В то время как подход двойной буферизации защищаемый здесь (продолжать двигаться вперёд вместо блокирования и ожидания завершения каждой операции) остаётся лучшим решением, однако улучшение сетевого кода в настоящее время уменьшает влияние подобной взаимной блокировки алгоритма Наггла.

Mac OS X v10.5 “Leopard” выпущенный в октябре 2007 года и более поздние обновления включают имплементацию изменения Грега Миншалла которые он задокументировал в декабре 1998 года. Но я не знаю, имплементированы ли подобные изменения на других операционных системах.

Алгоритм Наггла говорит, что если есть любые неподтверждённые отправленные сообщения, тогда вы не можете отправлять следующий урезанный пакет. Модификации Миншалла несколько смягчает это правило, говоря, что если вы уже отправили один урезанный пакет, то в этом случае не можете отправлять следующий. Другими словами одна попытка отправки урезанного пакета у вас есть, но только лишь одна. Многочисленные урезанные пакеты до сих пор не позволяются т. к. могут нанести вред сети. Плохо написанное приложение, которое выполняет множество небольших непрерывных записей будет всё также объединять эти маленькие записи в более эффективный большой пакет, при этом приложение, которое отправляет большой пакет не будет иметь задержку при отправке последнего урезанного пакета. Единственный урезанный пакет в конце большой записи не будет задержан, т. к. предшествующие исходящие пакеты были полноразмерными.
Важность того, чтобы алгоритм Наггла не отключался была изложена в письме Грега Миншалла:

Обратите внимание, что в некоторых случаях текущий алгоритм Наггла может иметь серьёзное негативное влияние на производительность некоторых приложений, отключение же алгоритма Наггла может серьезно отрицательно влиять на интернет. Таким образом, ничего из этого сообщения, равно как из вложенного черновика не должно рассматриваться как совет для любого разработчика приложений отключать алгоритм Наггла. Текущий алгоритм Наггла очень важен для защиты здоровья интернета; предлагаемые изменения [я надеюсь] дадут подобный уровень защиты.

Перевод выполнил A.Saushkin специально для Цифровой Лаборатории