Надёжность поверх UDP: acks, переотправка, перегрузка

Весь netcode из прошлого урока считал, что пакеты как-то доходят. Но мы с самого начала выбрали UDP, а он не гарантирует ни доставку, ни порядок, ни отсутствие дубликатов. Снапшоты и ввод эфемерны: потерялся пакет, придёт следующий, свежее. А вот рукопожатие, выстрелы и убийства терять нельзя и показывать дважды нельзя. Значит, нужна выборочная надёжность: для важного с переотправкой, для остального без. Сегодня построим её руками: нумерацию с закольцовыванием, систему подтверждений с битовым полем, очередь переотправки, оценку RTT и контроль перегрузки. А в конце замкнём весь третий проект: симулятор плохого канала и golden-трейсы как страховка детерминизма. Это финал блока.

Почему не взять TCP ради надёжности

Соблазн вернуться к TCP велик: он же всё это умеет. Но TCP даёт надёжность на весь поток сразу, и мы видели цену: head-of-line blocking заморозит свежие снапшоты ради переотправки устаревших. Нам же нужна надёжность точечная: переотправлять только то, что нельзя терять, а позиции игроков пусть теряются на здоровье. TCP такого не умеет, поэтому строим своё поверх UDP, ровно ту надёжность, которая нужна, и ни байтом больше.

Нумерация с закольцовыванием

Каждый пакет несёт свой порядковый номер. Чтобы заголовок был маленьким, номер это u16, а он рано или поздно переполнится: после 65535 идёт 0. Наивное сравнение a > b на стыке сломается: пакет 0 «меньше» пакета 65535, хотя пришёл позже. Поэтому сравниваем с поправкой на закольцовывание:

/// Истинно, если a новее b с учётом закольцовывания u16.
///
/// a считается больше b, если разница меньше половины диапазона вперёд.
pub fn sequence_greater_than(a: u16, b: u16) -> bool {
    ((a > b) && (a - b <= 32768)) || ((a < b) && (b - a > 32768))
}

Идея простая: считаем a новее b, если по кольцу до него меньше половины диапазона вперёд. Тогда 0 корректно оказывается новее 65535. Без этой аккуратности соединение сходило бы с ума раз в 65536 пакетов, и поди потом отладь такое.

Подтверждения: один ack за 33 пакета

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

/// Заголовок надёжного пакета. Едет в начале каждой датаграммы игрового канала.
pub struct Header {
    pub protocol_id: u32,
    pub sequence: u16,  // мой номер
    pub ack: u16,       // последний номер, что я получил от тебя
    pub ack_bits: u32,  // битовое поле: какие 32 номера до ack я тоже получил
}

Хитрость в ack_bits. Один ack подтверждает один пакет, а ack-bitfield подтверждает ещё 32: бит n стоит, если получен пакет ack - (n+1). Так один заголовок подтверждает до 33 пакетов разом.

/// Битовое поле подтверждений: бит n стоит, если получен номер
/// remote_sequence - (n + 1).
fn ack_bits(&self) -> u32 {
    let mut bits = 0u32;
    for n in 0..32u16 {
        let seq = self.remote_sequence.wrapping_sub(n + 1);
        if self.received.exists(seq) {
            bits |= 1 << n;
        }
    }
    bits
}

Зачем такая избыточность? Потому что подтверждения сами едут по UDP и сами теряются. Будь у нас один ack на пакет, потеря подтверждения выглядела бы как потеря данных, и мы зря переотправили бы доставленное. С битовым полем потерянное подтверждение повторится в следующих 32 пакетах, и отдельная надёжность для самих acks не нужна. Красивое самоисцеление.

Помечай пакеты потерянными и смотри, как меняется ack_bits и сколько пакетов подтверждает один заголовок. Снизу калькулятор сравнения номеров покажет, почему на стыке 65535 и 0 наивное сравнение врёт.

Переотправка как следствие, а не таймер

Тут механизм складывается особенно ладно. Надёжное сообщение не имеет своего таймера переотправки. Оно просто лежит в очереди, пока не подтверждено, и едет в каждом подходящем пакете:

/// Ставит надёжное сообщение в очередь. Оно поедет в ближайших пакетах и будет
/// повторяться, пока не подтвердится.
pub fn send_reliable(&mut self, payload: Vec<u8>) {
    let id = self.next_reliable_id;
    self.next_reliable_id = self.next_reliable_id.wrapping_add(1);
    self.outgoing_reliable.push_back(OutgoingReliable { id, payload, last_sent: None });
}

Когда приходит подтверждение пакета, мы снимаем из очереди все надёжные сообщения, которые в нём ехали:

// Снимаем надёжные сообщения, которые ехали в этом подтверждённом пакете.
if let Some(ids) = self.sent_reliable_ids.get(acked_seq).cloned() {
    for id in ids {
        self.outgoing_reliable.retain(|m| m.id != id);
    }
}

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

RTT и контроль перегрузки

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

fn update_rtt(&mut self, sample: f64) {
    if self.rtt == 0.0 {
        self.rtt = sample;
    } else {
        self.rtt += (sample - self.rtt) * RTT_SMOOTHING; // EWMA
    }
    self.rto = (self.rtt * 2.0).clamp(0.05, 1.0); // тайм-аут с запасом
}

А по RTT строим контроль перегрузки, тот самый Good/Bad, что задавал темп рассылки сервера. В плохой режим уходим сразу при высоком RTT, а обратно только после устойчиво хороших условий, причём штрафное время растёт, если перегрузка возвращается слишком быстро:

/// Контроль перегрузки с гистерезисом: в плохой режим уходим сразу, обратно
/// только после устойчиво хороших условий, штраф растёт при быстрых возвратах.
fn update_congestion(&mut self, dt: f64) {
    let conditions_good = self.rtt > 0.0 && self.rtt <= RTT_BAD_THRESHOLD;
    // ... Good -> Bad сразу при плохом RTT, удваивая штраф при частых срывах;
    //     Bad -> Good только когда хорошо держится дольше penalty_time
}

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

Как это вообще тестировать

Чтобы проверить netcode, не нужен плохой Wi-Fi, нужен управляемый плохой канал. Симулятор канала моделирует всё, чем сеть портит жизнь, и делает это детерминированно:

/// Параметры качества канала.
pub struct LinkConfig {
    pub latency: f64,   // базовая задержка
    pub jitter: f64,    // разброс задержки (переупорядочивание)
    pub loss: f32,      // вероятность потери
    pub duplicate: f32, // вероятность дубликата
}

Время виртуальное, генератор случайных чисел детерминированный, поэтому тест с потерями и джиттером воспроизводим до байта. На этом же симуляторе крутится и интерактивное демо, и тот самый виджет из прошлого урока: ползунки канала это и есть LinkConfig.

Golden-трейс: страховка детерминизма

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

/// Прогоняет запись через свежий сервер и возвращает отпечаток мира на каждом
/// такте. Дважды вызванный на одной записи даёт идентичный результат.
pub fn replay(&self) -> Vec<u64> {
    let mut sim = ServerSim::new();
    for _ in 0..self.players { sim.add_player(); }
    let mut digests = Vec::new();
    for frame in &self.frames {
        for (id, input) in frame {
            sim.ingest(*id, ClientMessage::Inputs { inputs: vec![*input] });
        }
        sim.tick();
        digests.push(sim.world().digest());
    }
    digests
}

Это число коммитится как golden-значение. Если кто-нибудь случайно сломает детерминизм (поменяет порядок обхода игроков, протащит скрытую зависимость от часов или случайности), трасса разойдётся и тест это поймает. Это прямой аналог nestest из эмулятора NES: эталонная трасса как страховка от незаметной регрессии. Тем же приёмом проверяется и digest мира, построенный на детерминированном обходе BTreeMap.

Что унести из урока и из блока

Надёжность поверх UDP делается выборочной: важное (рукопожатие, выстрелы) едет с переотправкой, эфемерное (снапшоты, ввод) без, чего TCP с его надёжностью на весь поток не умеет. Номера пакетов это u16 с закольцовыванием, и сравнивать их надо через sequence_greater_than. Подтверждения это ack плюс 32-битное поле, один заголовок подтверждает до 33 пакетов и сам себя чинит при потере acks. Переотправка это не таймер, а следствие: неподтверждённое сообщение лежит в очереди и едет снова, а на приёме дедуплицируется по id. RTT считается из времени до подтверждения и через гистерезис управляет контролем перегрузки. А тестируется всё это на детерминированном симуляторе плохого канала, и golden-трейс ловит любую поломку детерминизма.

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

Домашка