В данной статье мне хотелось бы рассказать о самом популярном протоколе, обеспечивающем надежную доставку сообщений мультикаста. Этот протокол называется PGM (pragmatic general multicast). Другие надежные протоколы поверх мультикаста (IP Multicast) такие как LBT-RM (от 29west) и SmartSockets (от TIBCO Software) являются, так или иначе, модификацией или реализацией PGM.
Как и многие другие хорошие нововведения в сетевом программном обеспечении и оборудовании, спецификация PGM зародилась внутри Cisco Systems. Основная проблема, которую пытались решить в процессе стандартизации надежного мультикаста это контроль и зашита от заторов в сети. Заторы обычно могут произойти из-за сообщений, которые заведомо не смогут быть обработаны слушателями или избытка служебных пакетов которые снижают полезную пропускную способность протокола.
Принципы, используемые в TCP, благодаря которым интернет работает эффективно, не подходят для мультикаста. Протокол TCP позволяет динамически менять количество данных, которые были отправлены, но еще не были подтверждены (transmission window) так чтобы отправитель TCP сообщений мог подстраиваться под слушателя. Понятно, что это не годится в случае, когда слушателей много, а отправитель один.
Типы пакетов
Для начала определимся с терминологией. Протокол содержит следующие типы пакетов:
ODATA – полезные данные, посылаемые через мультикаст (IP Multicast)
NAK – пакет с негативным подтверждением, посылается уникастом (обычно UDP) слушателем который обнаружил пропавший ODATA следующему узлу дерева пути
NCF – подтверждение получения NAK, который узел дерева отправляет мультикастом всем слушателям в подсети в которой NAK был получен
RDATA – пакет данные которого дублируют ODATA, публикуемый отправителем на мультикаст топике в ответ на полученный NAK
SPM – сообщения пути и хертбиты, пакеты публикуемы по мультикаст через равные промежутки времени и в отсутствие ODATA пакетов
Основные особенности протокола
Давайте рассмотрим такой пример: у нас есть сетка на 100 тачек, каждая из которых имеет самое разное железо и операционную систему. Мы разрабатываем серверное приложение, которое рассылает сообщения через разные малые интервалы времени (например, цену акции) приложениям которые запушены на этих тачках. Использовать в этом случае транспортные уникаст протоколы, значит производить копирование данных для каждого клиента. Сложность отправки пакета будет расти линейно при увеличении числа подписчиков. Мультикаст это как раз та замечательная технология, которая позволит отправить один пакет нескольким слушателям, произведя всего одну запись в буфер сокета на стороне отправителя, копирование пакета произойдет на роутере. Таким образом, увеличение количества слушателей не будет влиять на время доставки пакета.
Здорово, но тут есть проблема: мультикаст также как и UDP не гарантирует доставку и порядок пакетов. Даже далеким от торговли на бирже людям, думаю не трудно догадаться, что случится с приложением, которое пропустит квоту по какому то символу. Если подписчик это робот осуществляющий автоматическую покупки\продажи по каким-то стратегиям то не получив квоту робот не узнает что цена изменилась и может произвести не выгодную сделку. Наиболее естественный способ обеспечить гарантированность доставки это использовать подтверждение полученных сообщений (positive acknowledgment) как в TCP. Но тут возникает две проблемы – первая это то, что серверу придется обрабатывать подтверждение от каждого подписчика, т е сложность опять станет линейной и вторая это большое количество мультикаста одних и тех же данных, когда пакеты часто теряются.
Протокол PGM решает первую проблему тем что, вместо подтверждения каждого полученного сообщения, этот протокол подтверждает каждое пропавшее сообщение (negative acknowledgment). Каждый пакет протокола содержит порядковый номер и PGM слушатель посылает подтверждение отправителю пакета уникастом, если обнаруживает, что один из порядковых номеров пропущен. Чтобы исключить возможность потерю последнего пакета в серии (tail-loss) PGM источник в отсутствии полезных сообщений посылает специальные пакеты — хертбиты (heartbeats) задача которых поддержать актуальный порядковый номер на стороне слушателя.
Для решения второй проблемы PGM хранит и поддерживает в актуальном состоянии дерево пути от каждого отправителя мультикаст сообщений до слушателей. Каждый узел дерева знает, откуда ему пришел пакет и в случае если лист дерева (слушатель мультикаст сообщений) обнаружил, что пакет не получен, подтверждение потерянного пакета может подняться вверх от листа к корню дерева (отправитель мультикаст сообщений). На каждом узле дерева выставляется состояние, означающее, что в подсети потерян пакет. При повторной отправке потерянный пакет может игнорироваться на узлах, где это состояние не выставлено и дойдет только до тех подсетей, где произошла потеря пакета. Поддержание дерева пути достигается благодаря сообщениям пути (path messages) которые посылаются в мультикаст группы через равные промежутки времени каждым отправителя.
Не стоит путать сообщения для поддержания актуального порядкового номера или хертбиты и сообщения пути. Хотя они дублируют информацию, которую доставляют до слушателей, но они различаются тем, что сообщения пути посылаются через равные промежутки времени, в то время как хертбиты посылаются по более сложному алгоритму. Хертбиты задаются двумя параметрами: начальным таймаутом хертбита и количеством хертбитов. Первый хертбит посылается через таймаут после последнего пакета. Второй хербит посылается через вдвое больший таймаут после предыдущего хертбита. И так пока не будет отправлено нужное количество хертбитов.
Схематически это выглядит как то так:
|____|_________|__________________|_________________________________|____
время t ->
где первая черточка это последний пакет с полезной нагрузкой, а остальные это хертбиты.
NAK шторм
Не все так гладко в PGM как это может показаться на первый взгляд. Многие кто пытается использовать PGM бросают это дело из-за проблемы известной как NAK шторм. Если мы вернемся к примеру с сетью, по которой рассылаются квоты на акции, то там NAK шторм может произойти, если один из слушателей будет слишком медленным, и не будет успевать читать данные из буфера сокета. Приходящие пакеты будут игнорироваться из-за того что буфер забит и такой клиент будет посылать много NAK пакетов (crying baby receiver). В ответ на это отправителю придется публиковать RDATA пакеты, что увеличит нагрузку на отправителе и на всех его мультикаст подписчиков, часть из которых тоже может стать медленными клиентами. Опасен NAK шторм тем, что у одного источника PGM пакетов может быть очень много слушателей. Обработав один NAK и отправив RDATA пакет, источник тут же может получить NAK на тот же ODATA пакет от другого слушателя. Плюс к этому слушатель обнаруживший потерю ODATA пакета будет посылать NAK до тех пор, пока не получит NCF. Это все может привести к значительному снижению эффективности протокола, так как большая часть пропускной способности сети будет тратиться на пересылку NAK, NCF и RDATA вместо ODATA.
Протокол PGM имеет несколько механизмов позволяющих снизить негативное влияние различного рода заторов в сети. Количество NAK, которые получает источник можно уменьшить с помощью специальных слушателей мультикаст сообщений – агрегаторов NAK (designated receiver). Такие агрегаторы слушают NAK в подсети и посылают только один NAK источнику от всей подсети. Существуют роутеры способные самостоятельно агрегировать NAK от подсети, это PGM роутеры.
Также PGM позволяет наличие специальных элементов сети (designated local repairer или designated local retransmitter), которые могут самостоятельно отвечать пакетами RDATA на NAK. Это позволяет выстраивать топологию, в которой медленные клиенты не влияли на работу слушателей из других подсетей.
Также PGM позволяет выставлять различные опции – таймауты и счетчики для подавления NAK шторма. Подбор этих таймаутов это отдельная магия, в которой и заключается вся сложность работы с PGM. На стороне слушателей это
- время которое проходит после обнаружения потери пакета до того как сгенерируется первый NAK
- время, которое проходит до повторной отправки NAK, если NCF не был получен
- время, которое проходит от получения NCF до посылки нового NAK, если RDATA не был получен
- максимальное количество NAK, которое может отправить слушатель
На стороне отправителя это
- время, которое проходит между получением первого NAK и отправкой RDATA
- время в течение, которого игнорируются дублирующие NAK после отправленного RDATA
- ограничение на темп, которым отправляются пакеты RDATA (байт в секунду)
В общем, думаю из всего вышесказанного нетрудно догадаться, почему PGM и его вариации стали так популярны при разработке систем с низким временем отклика (low-latency systems). Этот протокол имеет меньшее время отклика по сравнению с надежными протоколами, использующими позитивное подтверждение пакетов, и позволяет увеличивать количество слушателей сообщений без ухудшения времени отклика.
Вопрос для размышления. Почему GFS и Hadoop используют TCP вместо надежного мультикаста? Известный факт, что все данные реплицируются в GFS и HFS, по крайней мере, на три разных бокса. Неужели самостоятельно копировать пакеты из сокета в сокет выходит более эффективно или надежно чем реплицировать пакеты на сетевом оборудовании?
