Кто и где: команда Google NW, представленная на SIGCOMM 2017.

Оригинал статьи здесь: https://dl.acm.org/citation.cfm?id=3 ACM Library/Carousel

TL;DR для спешащих гениев:

Из-за масштаба постоянного тока NW приходится иметь дело с миллионами потоков. Формирование скорости в промежуточных блоках (переключателях) не работает должным образом, со слишком большим количеством состояний для сохранения и неспособностью решать проблемы в отправителе/получателе. Коммутация с малой буферизацией вызывает слишком много падений, а с глубокой буферизацией — перегрузку, задержку и джиттер. Следовательно: формирование скорости на хостах.

Текущие методы — Полимеры, Иерархические Token-бакеты и Fair-Queueing/Pacing — показывают слишком большую нагрузку на ЦП.

Карусель — это новая, улучшенная реализация формирования трафика как отправляющими, так и принимающими узлами.

  • Пакеты аннотируются временем отправки, которое отражает желаемую скорость и темп. (Например, чтобы замедлить поток, запланируйте время отправки пакетов в этом потоке дальше друг от друга) и распределите BW между несколькими потоками.
  • Единая очередь Time-wheel содержит все пакеты, проиндексированные по их меткам времени отправки. Планировщик повторно опрашивает и отправляет следующий пакет из очереди, время отправки которой истекло. Колесо синхронизации содержит только указатели на фактические пакеты, поэтому не использует много памяти.

  • Они модифицируют гостевой драйвер VirtIO, чтобы он отправлял сигнал «complete» только при отправке пакета, в отличие от обычного, когда пакеты передаются от хоста к сетевой карте. Это означает, что отправляющее приложение не будет передавать пакеты, которые должны быть поставлены в очередь (или отброшены) в сетевом адаптере, если скорость отправки ниже, чем скорость создания пакетов приложения.

  • Для решения проблемы Incast (и, как правило, управления скоростью на получателе, который распределяет BW между входящим потоком) они модифицируют DTCCP, чтобы манипулировать последовательностью ACK № возвращаемых пакетов TCP, чтобы заставить отправителя снизить скорость до желаемой.
  • В многоядерных/многопроцессорных системах они реализуют один экземпляр Shaper на ядро ​​и хеш-потоки к одному из этих экземпляров. Для обработки агрегатов потоков, где потоки одного и того же агрегата могут хешироваться в разные экземпляры, они используют глобальный элемент, который выделяет некоторую часть BW для агрегата каждому экземпляру, получает фактические данные об использовании для каждого потока из экземпляров и пересчитывает новая фракция для периодического выделения каждому экземпляру.
  • Результаты: хорошее соответствие скорости целевой скорости при снижении загрузки ЦП на 8% (эквивалентно 4,6 ядрам, высвобождаемым для полезной работы на 72-ядерной машине).

Резюме и примечания

Контроль и формирование скорости трафика переносится на хосты, поскольку маршрутизаторы не могут масштабироваться до миллионов потоков.

Текущее управление/формирование скорости, как это сделано в Linux, слишком дорого и медленно для хостов (10% ЦП), а также имеет проблемы с HOL и неточность. Итак, Google представляет здесь новую, улучшенную реализацию.

«Необходимость масштабирования до миллионов потоков на сервер при применении сложной политики означает, что формирование трафика должно осуществляться в основном на конечных хостах. Эффективность и действенность этого формирования трафика конечного хоста становится все более важным фактором для работы как центров обработки данных, так и глобальных сетей. К сожалению, существующие реализации были построены для совсем других требований, например, только для потоков WAN, небольшого количества классов трафика, скромных требований к точности и простых политик. Благодаря измерению видеотрафика у крупного поставщика облачных услуг мы показываем, что производительность формирования трафика конечного хоста является основным препятствием для масштабирования виртуализированной сетевой инфраструктуры. Существующее ограничение скорости конечного хоста потребляет значительное количество ресурсов ЦП и памяти; например, формирование в сетевом стеке Linux использует 10% ЦП сервера для выполнения стимуляции; формирование в гипервизоре без необходимости отбрасывает пакеты, страдает от блокировки заголовка строки и неточности и не обеспечивает противодавление вверх по стеку.

Мы представляем дизайн и реализацию Carousel, улучшения существующего механизма формирования трафика на основе ядра. Carousel масштабируется до десятков тысяч потоков и классов трафика и поддерживает сложные механизмы распределения полосы пропускания как для глобальной сети, так и для связи центра обработки данных».

Три ключевые идеи:

  • Единый формирователь очередей для всех потоков, использующий время в качестве основы для выпуска пакетов, в частности, колесо синхронизации.
  • JIT-освобождение ресурсов на более высоких уровнях в сочетании с фактическим отправлением пакета
  • Каждый формирователь работает на отдельном ядре с безблокировочной координацией между ядрами.

Предыстория — потребность и проблема с текущим решением

Контроль скорости для каждого потока необходим для эффективного использования NW, справедливого распределения BW и хорошего пользовательского опыта. Глубокие буферы уменьшают загруженность, но увеличивают задержку и ухудшают работу пользователей. Для этой статьи «Формирование трафика» = контроль скорости впрыска (путем управления промежутками между пакетами в потоке) + принудительное применение ограничения скорости для потоков и агрегатов потоков.

Формирование трафика в ЦОД также мотивируется системами управления перегрузкой на основе скорости (например, TIMELY, BBR).

Масштаб проблемы приводит к подходу на основе хоста:

Рассмотрим 500 виртуальных машин на одном хосте, где каждая виртуальная машина взаимодействует в среднем с 50 другими виртуальными конечными точками (другими виртуальными машинами, внутренними службами ЦОД и т. д.). Это создает потоки 25 000 VM-to-Endpoint для управления, изоляции и применения некоторой политики SLA. Теперь умножьте на тысячи серверов.

Формирование в средних блоках (переключателях) не масштабируется: у них недостаточно буферов и недостаточно состояния для удержания такого количества потоков. Кроме того, узкое место может быть на конечном узле — сетевом адаптере (например, Incast), гипервизоре и т. д. — поэтому промежуточные блоки никак не могут помочь. Итак, нужно делать любое формирование и любую буферизацию на краю.

«Необходимость масштабирования до миллионов потоков на сервер при применении сложной политики означает, что формирование трафика должно осуществляться в основном на конечных хостах».

Текущие системы управления/формирования скорости на основе хоста слишком затратны с точки зрения потребления ресурсов.

Они исследуют текущие хост-системы:

Policers — потоки, отправляемые в классы, чья скорость измеряется с помощью счетчиков Token-Bucket, а пакеты выше Rate (+ разрешен пакет) отбрасываются (Policers не буферизуются).

HTB — иерархические сегменты токенов — потоки, классифицированные по классам, и классы, назначенные формирователям, которые буферизуют пакеты до тех пор, пока они не смогут быть отправлены в соответствии с желаемой скоростью. Шейперы организованы в виде дерева и могут заимствовать «кредиты» у шейперов, разделяющих родительский узел дерева шейпинга. Чтобы предотвратить неограниченное накопление очереди, некоторое обратное давление отправляется обратно в ОС, чтобы сказать ей прекратить отправку. Если выбора нет, пакеты отбрасываются, но этого следует избегать. Linux использует малые очереди TCP, которые по умолчанию ограничивают буферизацию на поток до 128 КБ — два полноразмерных сегмента TCP. Работа HTB на потоках-агрегатах

FQ/Pacing – встроенный в Linux Qdisc (дисциплина организации очередей), который управляет синхронизацией и справедливой организацией очередей для потоков TCP и UDP. Стимулирование выполняется с использованием схемы «дырявого ведра», и пакеты отправляются на основе их прогнозируемого времени отправки (пакеты, время отправки которых находится далеко в будущем, задерживаются — «подгоняются»). FQ/Pacing работает для каждого TCP/UDP-соединения, не обрабатывает агрегаты потоков и работает с точностью до сегмента TSO. Обычно цель состоит в том, чтобы иметь 1 сегмент TSO за 1 мс.

Они показывают, что все 3 из этих механизмов являются дорогостоящими и имеют нежелательные свойства в сегодняшних реализациях:

Политики — низкая стоимость ресурсов (отсутствие буферов, простая логика передачи/отбрасывания), но плохое соответствие целевой скорости (как из-за того, что они используют включение/выключение, чтобы попытаться эмулировать целевую скорость, так и из-за отбрасывания пакетов). вызывает резкое снижение скорости TCP)

Кроме того, там, где произведение BW-Delay велико (и контроллеры домена имеют каналы с высокой полосой пропускания, что делает это обычным явлением), ограничителям нужны большие всплески — порядка RTT потока, но большие всплески проблематичны, с плохим соответствием скорости при малых значениях. масштаб времени и перегрузка коммутаторов с неглубокой буферизацией на пути.

HTB — хорошее соответствие скорости, но дорогое количество циклов ЦП. Для эксперимента netperf с 1 байтом HTB снизил максимальное количество кадров в секунду с 800 000 до 600 000. Основные затраты связаны с тем, что HTB необходимо использовать глобальную блокировку Qdisc для каждого пакета, поставленного в очередь. По мере того, как добавляется больше потоков и HTB требуется больше классов, все становится хуже.

FQ/Pacing: хорошее соответствие скорости, но для реализации требуется высокая загрузка ЦП. Их измерения показывают, что FQ/Pacing стоит около 10% циклов процессора. Они даже измерили другую схему стимуляции — QUICK (которая выполняет стимуляцию в пользовательском пространстве с размером MTU), и это также показало, что это дорого в циклах ЦП.

Они отмечают, что высокая стоимость ЦП FQ/Pacing и HTB НЕ связана с плохой реализацией — она присуща логике механизма, которая требует синхронизации между несколькими очередями и ядрами, включая получение блокировки для каждого полученного пакета. А когда очереди разрастаются до больших размеров, чтобы поддерживать большое количество потоков — все плохо масштабируется.

Нижняя линия:

  1. Вам необходимо формирование трафика (управление скоростью, справедливое распределение, соблюдение квот).
  2. Это нужно делать на хостах, а не в мидлбоксах
  3. Существующие решения имеют существенный недостаток, что наиболее важно, они слишком дороги и представляют собой компромисс между точностью и стоимостью, как показано ниже.

Вывод: необходимо разработать новое, лучшее решение для формирования трафика на основе хоста è Carousel.

Карусель

Карусельный дизайн Принципы/цели

  1. Работайте правильно с TCP (и другими средствами управления перегрузкой более высокого уровня): соблюдайте правильный темп, избегайте всплесков
  2. Обратное давление на отправляющее приложение, чтобы избежать потери пакетов при увеличении очередей. Лучше заставить приложение не отправлять пакет, который придется буферизовать (затрачивая ресурсы) или, что еще хуже, отбрасывать сетевую подсистему хоста.
  3. Избегайте блокировки HOL
  4. Эффективно используйте ЦП и память: избегайте накладных расходов на обработку нескольких очередей, а также затрат и задержек на синхронизацию между элементами.

Карусельное решение

Формирование одиночной очереди с использованием меток времени отправки.

  1. Всем отправляемым пакетам назначается время отправки, которое отражает желаемую скорость и квоту полосы пропускания для потока. (например, потоку, который должен получить меньший BW, назначается время отправки с большим интервалом. Если поток отправляет пакет каждые 10 микросекунд, он получает 2X BW потока, которому назначается слот для отправки каждые 20 микросекунд)
  2. Пакеты помещаются в колесо времени — очередь, индексируемую по времени, в порядке времени их отправки. Планировщик повторно извлекает из очереди пакеты, время отправки которых (только что) истекло, и отправляет их на сетевую карту. Порядок отправленных пакетов зависит от времени их отправки, которое может отличаться от порядка, в котором они прибыли в очередь из приложений, поэтому это форма очереди PIFO (вталкивание, первый выход). . Скорость пакетов из каждого потока и распределение BW между потоками контролируются метками времени отправки, которые получает каждый пакет, что устанавливает его место в очереди колеса времени.

Отложенное завершение

  1. Приложение ожидает «полный» сигнал от сетевой подсистемы, чтобы сообщить ему, что пакет был обработан, и оно может отправить следующий. Обычная ситуация такая же, как в «а» на рисунке — Драйвер становится владельцем пакета и отправляет «полный» сигнал. Проблема в том, что в этот момент пакет еще не отправлен — он находится в буфере, ожидая отправки. Если приложение должно отправлять много пакетов подряд, все они должны быть буферизованы в сетевой карте, что требует как памяти для хранения, так и циклов ЦП для управления очередями.
  2. Таким образом, они модифицируют гостевой драйвер (например, VirtIO), чтобы он НЕ отправлял этот сигнал соревнования, а вместо этого заставляли сетевую карту отправлять его приложению, когда пакет фактически исключен из очереди и отправлен, как показано на рисунке «b».

Реализация этого, которую они используют, является обобщением стандарта Linux «малых очередей TCP» (TSQ). Прямой контроль скорости завершения сигналов служит противодавлением для замедления отправки приложения, когда это необходимо.

Противодавление со стороны ресивера

Иногда возникает необходимость оказывать обратное давление на удаленных отправителей со стороны получателя (например, для случаев использования incast только получатель видит слишком много входящих пакетов, и каждый сервер может думать, что он отправляет с правильной скоростью).

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

Для этого они манипулируют ACK, отправляемыми обратно передатчикам. Доступ к источникам контролируется по скорости, косвенно противодействуя потокам, которые занимают слишком много BW.

В TCP они фактически изменяют порядковые номера ACK в заголовках (байтах, которые были подтверждены ACK), используя расширение для DTCCP следующим образом:

Алгоритм отслеживает для каждого потока последний подтвержденный порядковый номер (SNa), время последнего подтверждения (Ta) и последний полученный порядковый номер (SNr). >). Первые две переменные отслеживают порядковый номер последних подтвержденных байтов и время отправки подтверждения.

Для исходящего пакета от получателя к отправителю мы проверяем номер подтверждения в пакете. Мы используем его для обновления SNr. Затем мы меняем это число на основе следующей формулы:

NewAckSeqNumber =min((now −Ta)×Rate+SNa, SNr ).

«Мы обновляем Ta до now и SNa до NewAckSeqNumber, если SNa меньше, чем NewAckSeqNumber».

Подтверждения генерируются Carousel, когда на верхнем уровне не было сгенерировано ни одного пакета в течение времени MTU/Rate.

Переменная Rate устанавливается либо через систему распределения пропускной способности, либо как общая доступная пропускная способность, деленная на количество потоков.

Многоядерное/многопроцессорное решение

Иногда одной очереди недостаточно для обработки всего трафика, особенно для многоядерных или многопроцессорных систем. Для многоядерных ЦП они реализуют один экземпляр колеса синхронизации на ядро, но НЕ создают полностью синхронизированную систему с жесткой связью, чтобы избежать затрат на эту синхронизацию, особенно необходимости получения блокировки для каждого полученного пакета.

Вместо этого каждый поток хешируется для данного экземпляра очереди колеса времени и одного экземпляра Soft-NIC. Этого достаточно, чтобы сформировать заданный единый поток. Агрегаты могут включать потоки, каждый из которых может быть хэширован в разные экземпляры. Таким образом, применение группового формирования означает, что каждая очередь должна внести свою долю в подмножество совокупного трафика, приземлившегося в этом экземпляре. Чтобы решить эту проблему по разумной цене, они используют «NBA» — расположение NIC-уровня BW A. Эта глобальная функция берет ограничение для агрегата потока и периодически распределяет его части для каждой временной метки для каждого ядра, используя алгоритм заполнения водой, чтобы получить максимальную и минимальную справедливость между ними. Каждый экземпляр временной метки периодически предоставляет NBA актуальные данные об использовании потока для повторного расчета того, какой экземпляр должен получить какую часть совокупности. Таким образом, если потоки на одном ядре используют меньше своей справедливой доли, лишняя часть передается другим ядрам. Если они используют слишком много, то временная метка остановит их на этом ядре. Обновления NBA/Core выполняются лениво, чтобы избежать необходимости блокировать путь данных. Это не совсем точно, но достаточно хорошо и дешево.

Выбор параметра Time Wheel

  1. Гранулярность слота: контролирует размер пакета и наименьший промежуток между пакетами (таким образом, максимальная скорость, которую можно задать). Они обнаружили, что при гранулярности от 8 до 16 микросекунд они получают отличное соответствие скорости.
  2. Горизонт временного колеса: представляет максимальную задержку, с которой пакет может столкнуться в формирователе (и, следовательно, минимальную поддерживаемую скорость). Произведение гранулярности слотов и количества слотов.

Результаты

Низкая стоимость ЦП, лучшее соответствие скорости

Карусель на 8 % лучше по затратам на загрузку ЦП, чем FQ/Pacing и HTB (= на 20 % эффективнее в использовании ЦП, связанном с работой в сети), и на 6 % лучше в соответствии скорости с желаемой целью. Скорость повторной передачи TCP остается прежней.

Точность карусели – это разница между запланированным (расчетным) временем отправки, проставленным на пакетах, и фактическим временем отправки. Они обнаружили, что 90% пакетов отправляются с отклонением меньше, чем гранулярность слота в 2 микросекунды. Это связано с округлением в меньшую сторону при назначении меток времени, которые рассчитываются в наносекундах, слотам, единицей времени которых являются две микросекунды.

Опыт производства:

Google использует Carousel в производстве. Они сообщают, как trey начал с запуска PoC, в котором использовалось 25 серверов, разбросанных по всему миру, каждый из которых обслуживал 38 Гбит/с в 50 000 одновременно активных потоков (вероятно, обслуживая YouTube для мобильных клиентов).

На рисунке показан результат для 5 таких серверов.

Используемая метрика — это Гбит/с/ЦП, полученная путем деления общего исходящего трафика на количество ЦП, а затем деленного на использование (например, 18 Гбит/с от 72 ЦП при загрузке 50% дает вам 18 Гбит/с/(72*50%) = отметка 0,5 Гбит/с/ЦП). Это лучший показатель, чем прямая загрузка ЦП, поскольку система направляет новые запросы на наименее загруженный ЦП. Таким образом, более эффективная машина получит больше клиентских запросов.

Результаты показывают, что Carousel лучше, чем FQ, и при том же уровне загрузки ЦП Carousel может передавать на 8% больше трафика.

На машине с 72 ЦП это эквивалентно увеличению количества ЦП на 4,6 на машину.

Они подразумевают, что результаты были достаточно хорошими, поэтому Carousel теперь широко используется в производстве.

Заключительные мысли/примечания (не в статье)

  1. Они внедрили Carousel в программную сетевую карту, но обратите внимание, что она могла быть реализована в ядре и может быть выгружена на аппаратную (интеллектуальную) сетевую карту.
  2. Карусель требует, чтобы оператор мог изменить гостевой драйвер и, возможно, стек TCP, используемый хостом (здесь они изменяют DTCCP). Хотя это может быть жизнеспособным вариантом для Google (и других крупных операторов), похоже, что у некоторых операторов DC не будет этой опции, поскольку арендаторы могут захотеть использовать свои собственные драйверы.
  3. На «голом» хостинге, где оператор DC не имеет никакого контроля над операционной системой хоста, кажется, что Carousel и подобные системы могут работать только в том случае, если они полностью разгружены на сетевую карту, и эта сетевая карта находится под полным контролем. оператора ДК.
  4. кажется, что отложенное завершение (вместо драйвера, чтобы сетевая карта отправляла события завершения, когда пакет исключен из очереди) может быть полезно в целом, даже вне контекста карусели, для предотвращения чрезмерного накопления очереди. Реализация этого почти наверняка потребует модификации стека TCP/IP хостов и, возможно, гостевых драйверов.