UDP без потерь и переупорядочивания

UDP ничего не обещает: датаграмма может не дойти, прийти дважды или обогнать соседнюю. Обычно в ответ берут TCP или пишут свой протокол с повторными запросами. Оба пути платят за потерю как минимум одним round trip, и платят именно тогда, когда сеть и так перегружена. В статье разобран другой вариант: отправитель заранее добавляет в поток избыточные пакеты, и получатель восстанавливает потерянное сам, ни о чём не спрашивая. Это прямая коррекция ошибок (FEC, forward error correction) кодом Рида — Соломона.

В прошлой статье я сравнивал разные пути сетевого пакета в Linux: sendmmsg, io_uring, AF_XDP, DPDK и ядерный TCP. Библиотека dgram-io только передает датаграммы, надёжность в ней намеренно не реализована и должна жить уровнем выше. Здесь описан этот дополнительный уровень: rs-fec, header-only библиотека на C++17 без зависимостей.

Все цифры в статье, кроме оговорённых, получены на самой библиотеке: симуляции с детерминированной моделью потерь, по 1–2 миллиона пакетов на замер.

Содержание

1. Откуда берутся потери и переупорядочивание

2. Номер последовательности и главная проблема приёмника

3. Три способа закрыть дыру

4. Теория на примерах: от XOR до поля Галуа

5. Как выбрать k, r и глубину чередования

6. rsfec в коде

7. Буфер переупорядочивания

8. Как это решено в протоколах поверх UDP

9. Производительность

10. Ограничения

11. Ссылки

1. Откуда берутся потери и переупорядочивание

Потери в UDP почти никогда не происходят «на проводе» в смысле битых кадров. Чаще всего место кончается в какой-то очереди:

• буфер сокета получателя переполнен, приложение не успевает читать. Видно в nstat -az | grep -i udp как UdpRcvbufErrors;

• в RX-кольце сетевой карты нет свободного дескриптора, карта выбрасывает кадр сама. Счётчик зависит от драйвера: у ixgbe это rx_missed_errors в ethtool -S, у DPDK imissed в rte_eth_stats;

• микровсплеск на коммутаторе: несколько портов одновременно шлют в один, буфер порта кончается;

• ограничители в облаке. У AWS ENA есть счётчики pps_allowance_exceeded и bw_in_allowance_exceeded, пакеты сверх лимита сначала встают в очередь, а потом отбрасываются;

• на стороне отправителя sendmmsg может вернуть меньше, чем просили, а SO_SNDBUF бывает заполнен (UdpSndbufErrors).

Отсюда важное свойство: потери идут пачками. Переполненная очередь теряет не один пакет, а все, что пришли, пока она была полной. Модель «каждый пакет теряется независимо с вероятностью p» удобна для формул, но на практике оптимистична, и ниже будет видно, насколько.

Переупорядочивание внутри одного потока встречается реже, но встречается:

• несколько путей между хостами (ECMP, агрегация каналов), если хэш потока меняется или балансировка идёт не по потоку;

• несколько потоков или очередей на отправителе, которые шлют пакеты одного логического потока;

• повторная отправка: переотправленный пакет приходит позже соседей;

• восстановление через FEC само по себе. Потерянный пакет с номером 5 восстанавливается, когда пришли 6, 7, 8 и паритет. Для приложения он появляется после 8-го.

Последний пункт означает, что если вы добавляете FEC, переупорядочивание у вас будет всегда, даже в идеальной сети. Поэтому эти две задачи в статье решаются вместе.

2. Номер последовательности и главная проблема приёмника

Всё начинается с номера в заголовке каждой датаграммы. Он нумерует пакеты потока подряд: 0, 1, 2, … Получатель хранит next, номер пакета, который он ждёт следующим, и у каждого пришедшего пакета есть три варианта:

• seq == next: всё хорошо, отдаём приложению, next растёт;

• seq < next: дубликат или опоздавший пакет, который уже списали. Выбрасываем;

• seq > next: между ними дыра.

С третьим случаем и вся сложность. В момент, когда пришёл пакет 12, а ждали 10, приёмник не знает, потерялись ли 10 и 11 или просто задерживаются. Отличить потерю от переупорядочивания в моменте нельзя, можно только подождать. Сколько ждать, это компромисс: мало — и задержавшийся пакет объявляется потерянным, много — и каждая настоящая потеря стоит всему потоку этого времени, потому что пакеты после дыры ждут вместе с ней (head-of-line blocking, та же проблема, что у TCP).

Номер нужен 64-битный. 32-битный при миллионе пакетов в секунду переполняется примерно за 70 минут, и тогда сравнение seq < next приходится делать по модулю, что порождает отдельный класс ошибок.

3. Три способа закрыть дыру

Когда дыра обнаружена, закрыть её можно тремя способами.

Переспросить (NACK или ARQ). Получатель сообщает отправителю номера пропущенных пакетов, тот отправляет их ещё раз. Трафик тратится только на реальные потери. Цена: время обнаружения плюс round trip плюс обработка на отправителе. И отправитель должен хранить отправленное, пока его могут переспросить.

Дублировать. Отправлять всё дважды разными путями. Так устроены биржевые рассылки рыночных данных: CME MDP 3.0 и FAST-рассылки Мосбиржи идут двумя одинаковыми мультикаст-потоками A и B, получатель берёт из каждой пары тот пакет, что пришёл раньше. Накладные расходы 100%, зато защищает от всего, что не случается на обоих путях одновременно, включая отказ целого канала. Для оставшихся случаев у бирж есть TCP-сервис повторной отправки и снапшоты.

Прямая коррекция (FEC). На каждые k пакетов данных отправитель добавляет r пакетов паритета, и любые k из этих k + r восстанавливают остальные. Накладные расходы r/k, платятся всегда, даже когда ничего не теряется. Взамен восстановление не зависит от RTT.

Пример на цифрах, чтобы было видно, где выигрыш. Допустим, RTT 50 мкс, пакеты идут каждые 5 мкс, приёмник ждёт дыру 20 мкс, прежде чем считать её потерей.

• NACK: 20 мкс ожидания плюс 50 мкс на запрос и ответ, итого порядка 70 мкс на каждую потерю, плюс обработка на отправителе.

• FEC с k = 8, r = 2: пакет восстанавливается, когда пришли остальные пакеты его группы и паритет. В симуляции ниже это в среднем 4.6 пакетных интервала после потери, около 23 мкс, и не больше 9 интервалов, 45 мкс. От RTT это не зависит вообще: при межконтинентальном канале с RTT 100 мс восстановление займёт те же 23 мкс.

FEC и NACK хорошо сочетаются. FEC снимает частый случай, одиночные и короткие потери, а NACK закрывает редкие остатки, когда потерь в группе больше, чем паритета. Повторный запрос тогда нужен в десятки и сотни раз реже, и путь повторной отправки не становится горячим именно тогда, когда сеть перегружена.

4. Теория на примерах

4.1. Один паритет: XOR

Самый простой код. Возьмём три пакета по три байта: CAT, DOG и EMU. Паритет считается как побайтовый XOR:

C A T   43 41 54
D O G   44 4F 47
E M U   45 4D 55
-----   --------
XOR     42 43 46   = "BCF"

Теряется DOG. XOR всего, что дошло, вместе с паритетом:

C A T   43 41 54
E M U   45 4D 55
B C F   42 43 46
-----   --------
XOR     44 4F 47   = "DOG"

Работает, потому что x ^ x = 0: все известные пакеты взаимно уничтожаются, и остаётся неизвестный. Так устроен RAID 5, и так же устроен FEC в SMPTE 2022-1 для видео по IP и в SRT: там пакеты раскладывают в матрицу и считают XOR по строкам и столбцам.

Два нюанса, которые понадобятся дальше.

Пакеты разной длины. Короткие дополняются нулями до длины самого длинного в группе, иначе XOR не определён. Но тогда восстановленный HI превратится в HI\0\0\0, и приёмник не узнает, где он кончался. Поэтому кодируется не сам пакет, а блок [длина | байты | нули]. Длина восстанавливается вместе с данными. В rsfec это 16-битная длина перед датаграммой.

Два потерянных пакета. Если потерялись и CAT, и DOG, XOR даёт только CAT ^ DOG, одно уравнение с двумя неизвестными. Второй паритет тоже как XOR не поможет, это будет то же самое уравнение. Нужен паритет, который смешивает пакеты с разными весами.

4.2. Два паритета: нужна система уравнений

Упростим до чисел. Пусть пакеты состоят из одного числа каждый: a = 3, b = 5, c = 6. Считаем два паритета с разными коэффициентами:

P0 = 1·a + 1·b + 1·c
P1 = 1·a + 2·b + 3·c

Потерялись a и b, дошли c = 6, P0 и P1. Переносим известное вправо и получаем систему из двух уравнений с двумя неизвестными:

a +  b = P0 - c
a + 2b = P1 - 3c

Вычитаем первое из второго, находим b, потом a. Всё сводится к школьной алгебре, пока коэффициенты подобраны так, что система решается для любой пары потерь.

Осталось понять, в какой арифметике это считать.

4.3. Почему не обычные байты

С обычными целыми числами паритет растёт: a + 2b + 3c для байтов достигает 1530, это уже 11 бит, и паритет становится длиннее данных. Считать по модулю 256 нельзя: при решении системы нужно делить, а у двойки по модулю 256 нет обратного (2 · 128 = 0), и уравнение 2b = x имеет либо два решения, либо ни одного.

Деление работает по простому модулю. Возьмём модуль 7, то есть арифметику в поле из семи элементов, и повторим пример:

P0 = 3 + 5 + 6         = 14 mod 7 = 0
P1 = 3 + 2·5 + 3·6     = 31 mod 7 = 3

Теряем a и b:

a +  b = P0 - c  = 0 - 6  = 1  (mod 7)
a + 2b = P1 - 3c = 3 - 18 = 6  (mod 7)

b = 6 - 1 = 5
a = 1 - 5 = -4 = 3  (mod 7)

Оба значения восстановлены. Но 7 не помещается в байт так, чтобы байт использовался целиком, а ближайшее простое после 255, это 257, выходит за байт. Нужно поле ровно из 256 элементов, и оно существует, только устроено не как числа по модулю.

4.4. GF(256)

Поле Галуа GF(2^8) состоит из 256 элементов, и каждый байт в нём элемент. Байт читается как многочлен с коэффициентами 0 и 1: 0x13 = 0001 0011 = x^4 + x + 1.

Сложение: многочлены складываются покоэффициентно по модулю 2, то есть это XOR. Вычитание совпадает со сложением. Поэтому XOR-паритет из 4.1 это частный случай: все коэффициенты равны единице.

Умножение: многочлены перемножаются и берётся остаток от деления на неприводимый многочлен восьмой степени. В rsfec это x^8 + x^4 + x^3 + x + 1 (0x11b), тот же, что в AES. На практике умножение на 2 сводится к сдвигу влево, и если старший бит выпал, к XOR с 0x1b:

0x57 · 2 = 0xae              (старший бит был 0, просто сдвиг)
0xae · 2 = 0x15c → 0x5c ^ 0x1b = 0x47
0x47 · 2 = 0x8e
0x8e · 2 = 0x11c → 0x1c ^ 0x1b = 0x07

Умножение на произвольное число раскладывается по битам множителя. Пример из стандарта AES, FIPS-197: 0x13 = 0x10 + 0x02 + 0x01, значит

0x57 · 0x13 = 0x57·0x10 ^ 0x57·0x02 ^ 0x57·0x01
            = 0x07 ^ 0xae ^ 0x57
            = 0xfe

Главное: у каждого ненулевого элемента есть обратный, поэтому системы из 4.2 решаются так же, как по модулю 7, только сложение заменяется на XOR, а умножение берётся из таблицы 256 × 256. Библиотека строит её при первом обращении обычным умножением «сдвиг плюс XOR», а обратные элементы находит перебором.

Почему именно 0x11b. Для кода подходит любой неприводимый многочлен. Этот выбран потому, что инструкция Intel GFNI GF2P8MULB умножает именно в этом поле, по 16, 32 или 64 байта за инструкцию. Подробнее в разделе 9.

4.5. Какие брать коэффициенты

Паритет с номером i в группе считается так:

parity_i = C(i,0)·unit_0 + C(i,1)·unit_1 + ... + C(i,k-1)·unit_{k-1}

Когда потерялись e пакетов данных, приёмник берёт e паритетов, вычитает из них известные пакеты и получает систему e × e. Её матрица составлена из коэффициентов C на пересечении использованных паритетов и потерянных позиций. Чтобы код восстанавливал любые r потерь, любая такая квадратная подматрица должна быть обратимой.

Матрица Коши обладает этим свойством по построению: C(i,j) = 1 / (x_i + y_j), где все x_i и y_j попарно различны. Любая её квадратная подматрица тоже матрица Коши, а они всегда обратимы. В rsfec x_i = 255 - i, y_j = j. Для k = 4, r = 2 коэффициенты такие:

          j=0   j=1   j=2   j=3
паритет 0  1c    41    1a    cd
паритет 1  41    1c    cd    1a

Коэффициенты считаются за одно обращение к таблице обратных, заранее их хранить не нужно.

Предупреждение для тех, кто будет писать свой код. Популярное руководство Планка 1997 года по кодам Рида — Соломона строило коэффициенты из матрицы Вандермонда, и в систематической форме это не гарантирует решаемость всех подматриц. Позже Планк и Дин опубликовали к нему поправку. Код, написанный по исходному тексту, на части сочетаний потерь молча не восстанавливает. С матрицей Коши такой проблемы нет.

4.6. Систематический код

Пакеты данных уходят на провод без изменений, паритет идёт отдельными пакетами. Это называется систематическим кодом и на практике важнее, чем кажется:

• получатель, который не знает про FEC, продолжает работать, просто игнорируя паритет. Внедрять можно с одной стороны за раз;

• если потерь нет, декодер ничего не считает, данные проходят как есть;

• стоимость декодирования растёт с числом потерь: примерно k·e + e² проходов умножения со сложением по длине пакета, где e число потерянных.

5. Как выбрать k, r и глубину чередования

5.1. Независимые потери

Параметров три: k пакетов данных в группе, r пакетов паритета и глубина чередования D (о ней ниже). Если потери независимы с вероятностью p, группа не восстанавливается, когда в ней потеряно больше r пакетов из k + r. Приближённо это C(k+r, r+1) · p^(r+1). Точные значения:

Здесь вероятность отказа на группу. Две вещи видны сразу. Каждый дополнительный паритет умножает защиту примерно на 1/p. И при тех же 25% накладных группа 16 + 4 защищает на порядки лучше, чем 8 + 2, но ждать восстановления приходится вдвое дольше, группа длиннее.

5.2. Пачки потерь

Реальные потери, как сказано в разделе 1, идут пачками. Для проверки в репозитории есть loss.h: модель Гилберта — Эллиотта, цепь Маркова с двумя состояниями «доставляет» и «теряет». Задаётся она двумя числами, которыми удобно думать: долей потерь и средней длиной пачки. Генератор детерминированный, одинаковые (доля, пачка, seed) всегда теряют одни и те же пакеты, поэтому любой случай можно воспроизвести. Ради этого модель и написана вместо netem.

Симуляция: 2 миллиона пакетов данных, паритет идёт по тому же каналу и тоже теряется. В ячейках доля пакетов данных, которые не удалось восстановить. Воспроизводится make sweep, код в examples/loss_sweep.cpp, модель потерь детерминированная, и цифры при каждом запуске те же.

«Одиночные» в этой модели значит, что двух потерь подряд не бывает. «Пачки по 2» и «по 4» задают среднюю длину, сами длины распределены геометрически. Время восстановления измерено в пакетах на проводе от потери до момента, когда пакет восстановлен.

Что из этого следует:

• при тех же 1% потерь переход от одиночных к пачкам средней длины 2 ухудшает k = 8, r = 2 в 250 раз. Если вы подбирали параметры по формуле из 5.1, вы переоценили защиту;

• средняя длина пачки не равна максимальной. При средней длине 4 и геометрическом распределении каждая десятая пачка длиннее 8. Поэтому r·D = 8 при средней пачке 4 даёт не ноль, а 0.28%. Смотрите на распределение длин ваших пачек, а не на среднее;

• 5%, одиночные, у D = 4 хуже, чем у D = 1. Это артефакт модели: запрет двух потерь подряд защищает группу из подряд идущих пакетов, а при чередовании пакеты группы не соседи, и эта защита пропадает.

5.3. Чередование

Чередование (interleaving) раскладывает подряд идущие пакеты по D одновременно открытым группам по кругу. При D = 4 и k = 8:

seq:     0  1  2  3  4  5  6  7  8  9 10 11 ... 28 29 30 31
группа:  A  B  C  D  A  B  C  D  A  B  C  D ...  A  B  C  D

Пачка из четырёх потерь подряд, например 5–8, задевает группы B, C, D и A по одному разу, и каждая из них восстанавливается даже с r = 1. В общем виде пачка длины B задевает каждую группу не более чем ceil(B/D) раз, и восстанавливается, пока B ≤ r·D.

Чередование покупает устойчивость к пачкам не трафиком, а задержкой: группа теперь растянута на k·D пакетов, и в таблице выше время восстановления выросло с 4.6 до 17.7 пакетов.

5.4. Паритет тоже теряется пачкой

Здесь нашлась вещь, которую я не ожидал. Условие B ≤ r·D гарантирует восстановление, только если пачка задевает пакеты данных. Но паритет группы по умолчанию уходит сразу после её последнего пакета, и пачка, пришедшаяся на этот момент, забирает и данные, и паритет той же группы:

... d31258  [X d31259  X d31260  X P31232.0  X P31232.1]  d31261 ...

Группа 31232 здесь потеряла последний пакет данных и оба паритета, три потери при r = 2, хотя пачка длиной 4 при D = 4 и r = 2 должна была проходить.

Лечится это на отправителе: паритет не отправлять сразу, а складывать в очередь и выпускать по одному после каждого следующего пакета данных, выждав несколько пакетов. Симуляция: k = 8, r = 2, D = 4, 0.1% потерь пачками ровно по L пакетов, 2 миллиона пакетов, без FEC это около 2000 потерянных.

Библиотека отдаёт паритет вызывающему коду и не отправляет его сама именно поэтому: когда и как его пускать в сеть, решает транспорт. Задержка паритета добавляется ко времени восстановления, это надо учесть при выборе времени ожидания в буфере переупорядочивания (раздел 7).

5.5. Низкая частота и нагрузка

Группа закрывается, когда набралось k пакетов. При 100 пакетах в секунду это 80 мс ожидания для k = 8, и восстанавливать потери будет не быстрее. Поэтому в Params есть flush_us (по умолчанию 100 мкс): группу, которая открыта дольше, закрывает Encoder::poll, и её паритет уходит, пусть и с меньшим k. Вызывать poll нужно из цикла простоя.

Под нагрузкой полезно уметь уменьшать избыточность. Encoder::set_r(n) меняет число паритетов для групп, открытых после вызова, от 0 до исходного r. Каждая группа несёт свою геометрию в заголовке паритета, декодеру ничего сообщать не надо.

5.6. С чего начать

• k = 8, r = 1, D = 1: 12.5%, одиночные потери, минимальная задержка;

• k = 8, r = 2, D = 1: 25%, пачки до 2, разумное умолчание;

• k = 8, r = 2, D = 4: 25%, пачки до 8, задержка восстановления вчетверо больше, паритет отправлять с задержкой.

И измерить свои потери: доля, распределение длин пачек, как это меняется под нагрузкой. loss.h позволяет потом воспроизвести то же самое в тестах.

6. rsfec в коде

6.1. Минимальный пример

#include <rsfec/fec.h>

fec::Params p;                       // k=8, r=2, depth=1, flush_us=100
fec::Encoder enc(p);
std::vector<fec::Parity> parity;

// Отправитель: каждую исходящую датаграмму в кодер, номера подряд.
// Когда группа заполнилась, в parity добавляются r пакетов паритета.
enc.feed(seq, datagram, len, now_ns, parity);

// Получатель: всё, что пришло, в декодер.
fec::Decoder dec;                    // около 1.6 МБ, на маленьком стеке лучше в куче
std::vector<fec::Decoder::Recovered> out;
dec.feed_data(seq, datagram, len, out);
dec.feed_parity(par.first_seq, par.k_actual, par.depth, par.index,
                par.data, par.coded_len, out);
// в out восстановленные датаграммы, как только группа стала решаемой

Полная рабочая версия в examples/roundtrip.cpp: make example теряет два пакета из восьми и печатает восстановленные.

6.2. Формат на проводе

Заголовок паритета библиотека не сериализует, это ваша часть. Нужно передать пять полей: first_seq, k_actual, depth, index, coded_len, и сами байты. Например:

#pragma pack(push, 1)
struct DataHdr {                  // перед каждой датаграммой данных
  uint8_t  type;                  // 0
  uint64_t seq;
};
struct ParityHdr {                // перед байтами паритета
  uint8_t  type;                  // 1
  uint64_t first_seq;
  uint8_t  k_actual, depth, index;
  uint16_t coded_len;
};
#pragma pack(pop)

Кодировать можно датаграмму целиком, вместе с вашим заголовком: восстановленный пакет возвращается байт в байт таким, каким его видел кодер. Главное, чтобы кодер и декодер получали одни и те же байты.

6.3. Отправитель

fec::Params p;
p.depth = 4;
fec::Encoder enc(p);
std::vector<fec::Parity> par;
std::deque<Pending> parity_q;     // сериализованный паритет + номер, после которого можно слать

void send_message(const uint8_t* msg, uint32_t len) {
  const uint64_t now = now_ns();
  uint32_t dlen = build_datagram(buf, seq, msg, len);   // DataHdr + msg
  net_send(buf, dlen);
  enc.feed(seq, buf, dlen, now, par);
  for (const auto& x : par)
    parity_q.push_back(serialize(x, /*not_before=*/seq + 8));
  par.clear();
  // по одному паритету на пакет данных, с задержкой (раздел 5.4)
  if (!parity_q.empty() && seq >= parity_q.front().not_before) {
    net_send(parity_q.front());
    parity_q.pop_front();
  }
  ++seq;
}

void idle() {
  enc.poll(now_ns(), par);        // закрыть группы старше flush_us
  for (const auto& x : par) net_send(serialize(x));
  par.clear();
  // и дослать очередь паритета, раз данных всё равно нет
}

Одна ловушка: Parity::data указывает во внутренний буфер кодера и живёт только до следующего feed или poll. Сериализовать или копировать надо сразу.

Если feed вернул false, датаграмма длиннее FEC_MAX_UNIT (по умолчанию 1500). Отправьте её как есть, без защиты. Её номер кодер увидит как дыру и закроет группу раньше, поэтому соседние пакеты по ошибке к ней не припишутся.

Номера должны идти строго подряд. Членство в группе позиционное: пакет j группы это first_seq + j·depth. При пропуске, повторе или сбросе номера кодер закрывает текущую группу досрочно, а не гадает. Вы теряете часть защиты около разрыва, но не корректность.

6.4. Получатель

auto dec = std::make_unique<fec::Decoder>();
Reorder<1024> ro(/*hold_ns=*/100'000);     // раздел 7
std::vector<fec::Decoder::Recovered> rec;

void on_datagram(const uint8_t* p, uint32_t len) {
  const uint64_t now = now_ns();
  if (p[0] == 0) {                                   // данные
    const uint64_t seq = read_seq(p);
    dec->feed_data(seq, p, len, rec);
    ro.push(seq, p, len, now, deliver);
  } else {                                           // паритет
    const ParityHdr h = read_parity_hdr(p);
    dec->feed_parity(h.first_seq, h.k_actual, h.depth, h.index,
                     p + sizeof(ParityHdr), h.coded_len, rec);
  }
  for (const auto& r : rec)                          // восстановленные
    ro.push(r.seq, r.data, r.len, now, deliver);
  rec.clear();
}

void idle() { ro.poll(now_ns(), deliver); }

В декодер надо подавать и повторно отправленные пакеты, если у вас есть NACK: они могут достроить группу, которой не хватало одного пакета.

Декодер держит кольцо из последних FEC_WINDOW пакетов (по умолчанию 1024) и список групп, ждущих недостающих пакетов (FEC_MAX_PENDING, 64). Группа, от которой поток ушёл дальше половины окна, списывается и попадает в stats().unrecoverable. Эти пакеты дальше на совести NACK или буфера переупорядочивания.

7. Буфер переупорядочивания

Декодер отдаёт восстановленные пакеты в момент восстановления, то есть не по порядку. Если приложению нужен порядок, между декодером и приложением ставится буфер, который выдаёт пакеты строго по seq и ждёт дыру ограниченное время. В API библиотеки его нет, но он лежит в репозитории как пример, examples/reorder.h:

template <uint32_t N = 1024>  // window in packets
class Reorder {
 public:
  explicit Reorder(uint64_t hold_ns) : hold_ns_(hold_ns) {
    for (auto& s : ring_) s.seq = kEmpty;
  }

  // deliver(seq, data, len) is called once per packet, in seq order.
  template <class F>
  void push(uint64_t seq, const uint8_t* p, uint32_t len, uint64_t now_ns,
            F&& deliver) {
    if (seq < next_ || len > sizeof(Slot::data)) return;  // late or dup
    while (seq >= next_ + N) skip(deliver);  // does not fit: slide the window
    Slot& s = ring_[seq % N];
    if (s.seq == seq) return;  // duplicate
    s.seq = seq;
    s.len = len;
    std::memcpy(s.data, p, len);
    if (seq >= end_) end_ = seq + 1;
    poll(now_ns, deliver);
  }

  // Call from the idle loop too: a gap can expire while nothing arrives.
  template <class F>
  void poll(uint64_t now_ns, F&& deliver) {
    for (;;) {
      Slot& s = ring_[next_ % N];
      if (s.seq == next_) {  // the next packet in order is here
        deliver(next_, s.data, s.len);
        s.seq = kEmpty;
        ++next_;
        in_gap_ = false;
        continue;
      }
      if (end_ <= next_) return;  // no gap, just nothing yet
      // One timer per gap, not per packet: a run of losses is written off
      // at once when it expires, not hold_ns apiece.
      if (!in_gap_) {
        in_gap_ = true;
        gap_since_ = now_ns;
      }
      if (now_ns - gap_since_ < hold_ns_) return;
      ++lost_;
      ++next_;
    }
  }

  uint64_t lost() const { return lost_; }
  uint64_t next() const { return next_; }

 private:
  static constexpr uint64_t kEmpty = ~0ull;
  struct Slot {
    uint64_t seq;
    uint32_t len;
    uint8_t data[1500];
  };

  template <class F>
  void skip(F&& deliver) {
    Slot& s = ring_[next_ % N];
    if (s.seq == next_) {
      deliver(next_, s.data, s.len);
      s.seq = kEmpty;
    } else {
      ++lost_;
    }
    ++next_;
    in_gap_ = false;
  }

  Slot ring_[N];
  uint64_t next_ = 0;       // next seq to deliver
  uint64_t end_ = 0;        // one past the highest seq seen
  uint64_t gap_since_ = 0;
  uint64_t lost_ = 0;
  uint64_t hold_ns_;
  bool in_gap_ = false;
};

Несколько решений в нём, которые стоит объяснить.

Таймер один на дыру, а не на пакет. Если подряд потеряно пять пакетов, после истечения ожидания они списываются все сразу, а не по hold_ns каждый. Отсчёт сбрасывается только когда пакет выдан по порядку.

Переполнение окна. Если пришёл пакет, который дальше next + N, ждать больше нельзя, некуда класть. Буфер сдвигается, выдавая то, что есть, и списывая остальное.

Время ожидания связано с FEC. Если hold_ns меньше времени восстановления, буфер спишет пакет, который декодер восстановил бы через несколько микросекунд. Нижняя граница: (k·D + задержка паритета) × интервал между пакетами, а на низкой частоте flush_us. Для k = 8, D = 1 при 200 тысячах пакетов в секунду это около 45 мкс, плюс запас на джиттер.

Проверка, examples/in_order.cpp, запускается в make example. Миллион пакетов, k = 8, r = 2, 1% одиночных потерь, каждый сотый пакет задерживается на случайное число от 0 до 7 интервалов, ожидание 20 интервалов. Результат: 999 985 пакетов выданы строго по порядку и байт в байт, 13 189 из них восстановлены декодером, 15 не восстановлены и списаны буфером. Нарушений порядка ноль.

Эти 15 из миллиона и есть то, что закрывает NACK, если доставка должна быть полной.

8. Как это решено в протоколах поверх UDP

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

8.1. QUIC

QUIC (RFC 9000, под HTTP/3) восстанавливает потери только переспросом. Интересно в нём, как сделана нумерация. Номер пакета никогда не повторяется: при потере переотправляются не пакеты, а фреймы с данными, в новом пакете с новым номером. У TCP переотправленный сегмент несёт тот же номер, и без опции timestamps по подтверждению не понять, на какую из копий оно пришло. Поэтому такие замеры RTT приходится выбрасывать (алгоритм Карна). В QUIC этой неоднозначности нет.

Потерю отправитель объявляет по подтверждениям (RFC 9002): если подтверждён пакет, отправленный на 3 номера позже, или если с отправки прошло больше 9/8 RTT, а более поздний пакет уже подтверждён. Это ровно та дилемма из раздела 2, «потеря или задержка», решённая порогами. Потерянные данные приходят не раньше, чем примерно через RTT после того, как пришли бы без потери. Кроме того, потеря для QUIC сигнал перегрузки, и окно отправки уменьшается.

Порядок гарантируется внутри потока (stream), а потоков в соединении много, и потеря в одном не задерживает другие. Внутри потока блокировка из-за дыры остаётся. Для данных, которым порядок и надёжность не нужны, есть расширение RFC 9221, DATAGRAM-фреймы: они не переотправляются и не упорядочиваются, по сути это UDP внутри зашифрованного соединения с контролем перегрузки.

FEC в стандарте нет. В ранней версии gQUIC Google пробовал XOR-коррекцию: в экспериментах она не улучшила метрики, на трафике YouTube стало хуже, и её убрали ещё до стандартизации. В IETF есть черновики и исследовательские реализации FEC для QUIC, стандарта нет. Для веба это логично: RTT в десятки миллисекунд, потерь мало, и 10–25% лишнего трафика на каждое соединение не окупаются.

8.2. WebRTC и RTP

Видео- и аудиозвонки работают поверх RTP, и здесь используется всё сразу:

• у RTP-пакета 16-битный номер, приёмник ставит пакеты в jitter buffer. Это тот же буфер переупорядочивания с бюджетом задержки, только бюджет подстраивается под измеренный джиттер;

• потерю переспрашивают через RTCP NACK (RFC 4585), и отправитель повторяет пакет отдельным потоком RTX (RFC 4588), если повтор успевает к моменту воспроизведения;

• для видео есть FEC: ULPFEC (RFC 5109) и FlexFEC (RFC 8627), оба на XOR по маскам пакетов;

• для аудио свои приёмы: в Opus есть встроенный FEC, когда в пакет добавляется копия предыдущего кадра с низким битрейтом, и избыточность RED (RFC 2198), когда в пакет кладутся предыдущие кадры целиком.

Долю FEC libwebrtc подстраивает под измеренные потери и RTT: при коротком RTT дешевле переспросить, при длинном переспрос не успевает, и нужен FEC. Это ровно то сочетание, которое советуется в разделе 3.

8.3. SRT и RIST

SRT передаёт видео по интернету, от студии до студии. Основа в нём ARQ: приёмник сообщает о дыре сразу, как её увидел, и периодически повторяет список недостающего. Главная идея SRT в бюджете задержки: параметр latency, по умолчанию 120 мс. Каждый пакет отдаётся приложению через latency после отправки, по метке времени отправителя. Если пакет не удалось получить за это время, он выбрасывается (TLPKTDROP, too-late packet drop), и поток идёт дальше. Задержка постоянная и предсказуемая, а потери, которые не успели восстановить, приложение видит как дыры. Буфер из раздела 7 устроен так же, только ждёт дыру, а не каждый пакет.

С версии 1.4 в SRT есть FEC как фильтр пакетов: XOR по строкам и столбцам матрицы, как в SMPTE 2022-1. Например, fec,cols:10,rows:5 добавляет 15 паритетов на 50 пакетов (30%). Каждый столбец защищает 5 пакетов, идущих через 10, поэтому пачка до 10 потерь подряд задевает каждый столбец не больше раза и восстанавливается. FEC можно сочетать с ARQ или использовать вместо него.

RIST (спецификации VSF TR-06) решает ту же задачу поверх RTP: NACK и повтор, при необходимости FEC по SMPTE 2022-1.

8.4. KCP и kcp-go

KCP это ARQ-библиотека, которая сознательно тратит трафик ради задержки: выборочная и быстрая переотправка, не дожидаясь таймаута, таймаут растёт в 1.5 раза, а не вдвое, режим без задержки подтверждений. Автор оценивает выигрыш в 30–40% по средней задержке ценой 10–20% трафика по сравнению с TCP. Порядок KCP гарантирует.

kcp-go, реализация KCP на Go, добавляет к этому код Рида — Соломона (библиотека klauspost/reedsolomon). Построенный на ней туннель kcptun по умолчанию шлёт 3 паритета на 10 пакетов данных, это 30% накладных. Это ближайший по устройству аналог схемы из статьи: RS-FEC снимает большинство потерь, ARQ добирает остальное.

8.5. Aeron

Aeron распространён в финансах: надёжный UDP с юникастом и мультикастом, упорядоченная доставка, низкая задержка. Потери восстанавливаются только переспросом: приёмник видит дыру и отправляет NAK, в юникасте сразу, в мультикасте с задержкой, чтобы не устроить шквал запросов. Отправитель повторяет данные из своего буфера. FEC нет. Для дата-центра это разумно: RTT десятки микросекунд, и NAK стоит примерно столько же, сколько ожидание группы FEC.

8.6. Мультикаст и вещание: PGM, FLUTE

Когда получателей много, переспрос масштабируется плохо: без подавления одна потеря у тысячи подписчиков это тысяча NAK. В PGM (RFC 3208, надёжный мультикаст) есть подавление повторных NAK и два вида паритета Рида — Соломона: проактивный, который отправляется всегда, и паритет по запросу. У второго красивое свойство: если каждый получатель потерял по одному пакету группы, причём у всех разные, один паритетный пакет чинит всех сразу. Переотправка исходных пакетов так не умеет, ей пришлось бы повторить каждый. Поэтому RFC рекомендует паритет по запросу для больших групп получателей с некоррелированными потерями.

Крайний случай, когда обратного канала нет вообще: цифровое вещание, раздача файлов по мультикасту. Там только FEC. FLUTE и ALC (RFC 6726, RFC 5775) используют фонтанный код RaptorQ (RFC 6330): отправитель может сгенерировать сколько угодно разных пакетов восстановления, и получателю достаточно собрать чуть больше k любых из них.

8.7. Сводка

Что из этого следует.

Почти все сочетают FEC и переспрос с бюджетом задержки. Чистый переспрос выбирают там, где RTT мал или трафик дорог (QUIC, Aeron). Чистый FEC там, где обратного канала нет (вещание). Всё остальное смешивает оба в пропорции, зависящей от RTT.

XOR-схемы (SMPTE 2022-1, SRT, ULPFEC) дешевле в вычислениях, но матрица строк и столбцов восстанавливает не любые сочетания потерь: четыре потери в углах прямоугольника, по две в двух строках и двух столбцах, она не чинит. Код Рида — Соломона восстанавливает любые r потерь в группе. При современных SIMD-ядрах (раздел 9) разница в стоимости уже не важна.

FEC скрывает потери от контроля перегрузки. Если транспорт снижает скорость по потерям, как QUIC или TCP, считать их надо до восстановления, а не после. В rsfec для этого есть Decoder::stats().recovered: сколько пакетов пришлось восстановить.

Когда брать готовое. Если данные идут по интернету, нужны шифрование и честный контроль перегрузки, берите QUIC или, для видео, SRT: там решены вопросы, которые эта статья не затрагивает. Своё имеет смысл, когда бюджет задержки в микросекундах, RTT короткий, путь пакета свой (AF_XDP, DPDK, как в dgram-io), а шифрование не нужно или сделано ниже. Тогда rsfec это готовая деталь для такого транспорта, а не протокол целиком.

9. Производительность

9.1. Одна горячая операция

Всё кодирование и декодирование сводится к одной операции над буфером:

addmul(dst, src, n, c):   dst[i] ^= c · src[i]

Кодер делает r таких проходов на каждый пакет данных. Декодеру нужны проходы только при потерях.

Скалярная версия берёт строку таблицы умножения на c (256 байт) и делает по одному обращению на байт. Быстрее всего работает трюк с разбиением байта на полубайты (из работы Plank, Greenan, Miller, FAST 2013, он же используется в Intel ISA-L). Умножение в поле дистрибутивно относительно сложения, то есть XOR, поэтому

c · x = c · (x & 0x0f)  ^  c · (x & 0xf0)

Для фиксированного c обе половины принимают по 16 значений, и каждая таблица из 16 байт помещается в один SSE-регистр. Инструкция PSHUFB делает 16 табличных поисков за раз. Пример: c = 0x57, x = 0x83.

0x57 · 0x03 = 0xf9      (младший полубайт)
0x57 · 0x80 = 0x38      (старший полубайт)
0xf9 ^ 0x38 = 0xc1      = 0x57 · 0x83

На процессорах с GFNI то же делает одна инструкция GF2P8MULB, без таблиц. Отсюда выбор многочлена 0x11b в разделе 4.4.

9.2. Семь реализаций, выбор при запуске

В бинарник компилируются все ядра, от скалярного до GFNI с AVX-512, через атрибуты target у функций. Нужное выбирается по CPUID при первом вызове, флаги -m не нужны, и бинарник, собранный на старой машине, на новой использует GFNI.

Пропускная способность addmul на пакетах по 1400 байт (bench/bench_fec.cpp, единицы как их напечатал Google Benchmark на каждой машине):

Кодирование k = 8, r = 4 обходится в 147 нс на пакет с SIMD против примерно 2.4 мкс скалярно. На Sandy Bridge слитная форма addmul2, которая за один проход по источнику обновляет два паритета сразу, дала ещё 19% и снизила кодирование k = 8, r = 2 с 297 до 208 нс на пакет.

Две оговорки из этих прогонов.

Автовыбор не всегда прав. На m7i он берёт gfni_avx512, который там примерно на 10% медленнее gfni_avx2, из-за снижения частоты на 512-битных инструкциях. Закрепить ядро можно одним вызовом gf256::force_kernel("gfni_avx2"), автоматически это не определяется.

SIMD даёт запас, а не медиану. В сквозном тесте передачи сообщений по UDP на 200–300 тысячах сообщений в секунду p50 с SIMD и без него: 14.0 и 13.9 мкс, разницы нет. Скалярное ядро просто занимало около 70% ядра процессора вместо 4%. Заметно стало примерно с 400 тысяч сообщений в секунду.

9.3. Кэш

Окно декодера сначала было 8192 слота по 1500 байт, 12 МБ. Это больше последнего уровня кэша на машинах, где шли измерения, и кольцо вытесняло само себя на каждом круге. Восстановлению нужны только пакеты групп, которые ещё в пути, это k·D, поэтому окно уменьшено до 1024 слотов, 1.5 МБ. FEC_WINDOW это единственная настройка, от которой зависит, помещается ли путь приёма в кэш.

Кодер обнуляет строки паритета лениво, только до длины самого длинного пакета в группе. При 100-байтных пакетах полное обнуление 1502-байтной строки стоило бы на порядок больше, чем всё кодирование.

10. Ограничения

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

• Нет версии формата. Раскладка блока и построение матрицы Коши на практике стабильны, но до 1.0 не обещаны.

• Один Encoder и Decoder на поток выполнения. force_kernel вызывать до начала кодирования.

• Нужны GCC или Clang: атрибуты target и cpuid.h. MSVC не поддерживается. SIMD-ядра только для x86-64, на остальных архитектурах, CI проверяет arm64, работает скалярное.

• Датаграммы длиннее FEC_MAX_UNIT не защищаются.

• Граничные параметры задаются при компиляции: FEC_MAX_K 32, FEC_MAX_R 8, FEC_MAX_DEPTH 16, FEC_WINDOW 1024, FEC_MAX_PENDING 64.

Сборка: make test, make example, make bench (нужен Google Benchmark) или cmake -B build && cmake --build build && ctest --test-dir build. Библиотека header-only, cmake --install экспортирует пакет:

find_package(rsfec 0.1 REQUIRED)
target_link_libraries(app PRIVATE rsfec::rsfec)

Лицензия Apache-2.0. Код написан вместе с Claude (Anthropic), архитектурные решения и измерения мои.

11. Ссылки

Проекты:

• rs-fec

• Производительность сетевых бэкендов в Linux, прошлая статья

• dgram-io, семь путей пакета через Linux за одним интерфейсом, методика и замеры в BENCHMARKS.md

Коды Рида — Соломона и стирающие коды:

• I. Reed, G. Solomon, Polynomial Codes over Certain Finite Fields, 1960

• J. Blömer и др., An XOR-Based Erasure-Resilient Coding Scheme, ICSI TR-95-048, 1995, построение через матрицу Коши

• L. Rizzo, Effective Erasure Codes for Reliable Computer Communication Protocols, ACM SIGCOMM CCR, 1997

• J. Plank, A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems, 1997, и J. Plank, Y. Ding, Note: Correction to the 1997 Tutorial on Reed-Solomon Coding

• J. Plank, K. Greenan, E. Miller, Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions, FAST 2013

• Intel ISA-L, библиотека с оптимизированными стирающими кодами

• FIPS-197 (AES), раздел про арифметику в GF(2^8)

FEC в протоколах:

• RFC 5510, Reed-Solomon Forward Error Correction (FEC) Schemes

• RFC 8627, FlexFEC для RTP

• SMPTE ST 2022-1, FEC для видео по IP

Протоколы поверх UDP:

• RFC 9000 QUIC, RFC 9002 обнаружение потерь и контроль перегрузки в QUIC, RFC 9221 DATAGRAM

• RFC 4585 RTCP NACK, RFC 4588 RTX, RFC 5109 ULPFEC, RFC 2198 RED

• SRT, RIST

• KCP, kcp-go

• Aeron

• RFC 3208 PGM, RFC 6726 FLUTE, RFC 5775 ALC, RFC 6330 RaptorQ