Проектируем игровой протокол: varint, биты и дельты

В прошлом уроке мы получили голый UDP: датаграммы с границами, но без гарантий. Теперь решаем, что именно по нему гонять. Игровой трафик это жёсткий бюджет: датаграмма должна влезать в один сетевой кадр, а сервер шлёт снапшот мира десятки раз в секунду каждому игроку. Если писать числа как есть, бюджет лопнет. Поэтому сегодня проектируем бинарный протокол, который экономит каждый байт: varint для маленьких чисел, zigzag для знаковых, битовая упаковка под флаги, плюс приёмы уровня сообщений (магия и версия, теги, полный снапшот против дельты). Это прямое продолжение кодирования битиков из RU3, только теперь биты едут по сети.

Бюджет пакета это закон

Сначала про ограничение, из которого растёт весь дизайн. Сетевой кадр без фрагментации это около 1500 байт, и за вычетом IP и UDP заголовков на полезную нагрузку остаётся примерно 1200.

/// Безопасный потолок полезной нагрузки одной UDP-датаграммы. Консервативное
/// значение под типичный MTU 1500 минус IP/UDP заголовки и запас на туннели.
pub const MAX_PAYLOAD: usize = 1200;

MTU это не рекомендация, а закон: вылезешь за него, и IP-уровень разрежет датаграмму на фрагменты, а потеря одного фрагмента губит весь пакет. Значит, в 1200 байт надо уместить состояние стольких игроков, сколько игрок видит. При наивной упаковке (каждое число это 4 байта) это десяток-другой игроков, и всё. При умной упаковке счёт идёт на сотни. Поэтому числа на провод мы пишем компактно.

Varint: маленькое занимает мало

Большинство чисел в трафике маленькие: номер ввода, id игрока, длина списка. Тратить на них по 4 или 8 байт расточительно. Varint кодирует число переменной длиной: семь бит полезной нагрузки на байт, старший бит это флаг продолжения. Числа от 0 до 127 занимают один байт, и только большие значения растут.

/// Кодирует беззнаковое u64 как LEB128 varint, дописывая байты в out.
///
/// Семь бит полезной нагрузки на байт, старший бит это «есть продолжение».
pub fn write_varint_u64(out: &mut Vec<u8>, mut value: u64) {
    loop {
        let mut byte = (value & 0x7F) as u8;
        value >>= 7;
        if value != 0 {
            byte |= 0x80; // будет ещё байт
        }
        out.push(byte);
        if value == 0 {
            break;
        }
    }
}

Чтение зеркально, и тут впервые видно, что декодер из сети обязан защищаться. Ввод может быть любым, поэтому отсекаем и обрыв буфера, и слишком длинную последовательность:

/// Ошибка декодирования varint из недоверенного буфера.
pub enum VarintError {
    /// Буфер кончился, а старший бит последнего байта всё ещё просил продолжение.
    Truncated,
    /// Больше 10 байт: для u64 это заведомо мусор или попытка переполнения.
    Overlong,
}

/// Читает LEB128 varint из начала buf. Возвращает значение и длину или ошибку.
pub fn read_varint_u64(buf: &[u8]) -> Result<Varint, VarintError> {
    let mut value: u64 = 0;
    let mut shift = 0u32;
    for (i, &byte) in buf.iter().enumerate() {
        if i >= 10 {
            return Err(VarintError::Overlong); // u64 это максимум 10 байт varint
        }
        value |= ((byte & 0x7F) as u64) << shift;
        if byte & 0x80 == 0 {
            return Ok(Varint { value, bytes: i + 1 });
        }
        shift += 7;
    }
    Err(VarintError::Truncated)
}

Граница i >= 10 это не эстетика: десять байт по семь бит это 70 бит, больше чем влезает в u64. Без этой проверки злонамеренный поток байт со взведённым старшим битом крутил бы цикл и переполнял сдвиг. Это та же мысль про недоверенный ввод, что и MAX_FRAME из прошлого урока.

Zigzag: отрицательные тоже короткие

У varint есть слабое место: отрицательные числа. В дополнительном коде -1 это 0xFFFFFFFFFFFFFFFF, и varint от него занимает все десять байт, хотя по модулю число крошечное. Лечит это zigzag: он перекладывает знаковое число в беззнаковое так, что близкие к нулю значения (и положительные, и отрицательные) остаются короткими.

/// zigzag-кодирование знакового числа в беззнаковое.
pub fn zigzag_encode(value: i64) -> u64 {
    ((value << 1) ^ (value >> 63)) as u64
}

/// Обратное zigzag-декодирование.
pub fn zigzag_decode(value: u64) -> i64 {
    ((value >> 1) as i64) ^ -((value & 1) as i64)
}

Отображение простое: 0 -> 0, -1 -> 1, 1 -> 2, -2 -> 3. Чётные это положительные, нечётные это отрицательные, и обе ветки растут от нуля. Дальше знаковое число гонится обычным varint, и -1 снова занимает один байт.

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

Биты: флаги по биту, а не по байту

Varint экономит на числах, но между байтами есть ещё резерв. Пять кнопок ввода это пять bool, и записать их пятью байтами было бы мотовством: это пять бит. Для упаковки под-байтовых полей заведём накопитель битов, который сбрасывает байт в выход, как только наберётся восемь:

/// Пишет биты в поток старшими битами вперёд (MSB-first).
pub struct BitWriter {
    out: Vec<u8>,
    acc: u8,
    nbits: u8, // сколько бит уже лежит в acc, 0..8
}

impl BitWriter {
    /// Записывает младшие count бит значения value (count в 0..=32).
    pub fn write(&mut self, value: u32, count: u8) {
        for i in (0..count).rev() {
            let bit = ((value >> i) & 1) as u8;
            self.acc = (self.acc << 1) | bit;
            self.nbits += 1;
            if self.nbits == 8 {
                self.out.push(self.acc);
                self.acc = 0;
                self.nbits = 0;
            }
        }
    }

    pub fn write_bool(&mut self, bit: bool) {
        self.write(bit as u32, 1);
    }

    /// Дописывает нулями до границы байта и отдаёт буфер.
    pub fn finish(mut self) -> Vec<u8> {
        if self.nbits > 0 {
            self.acc <<= 8 - self.nbits;
            self.out.push(self.acc);
        }
        self.out
    }
}

BitReader читает в том же порядке (старший бит вперёд), и нехватку бит он возвращает как None, а не паникует, всё та же граница доверия. Вместе varint, zigzag и битовая упаковка дают радикальную экономию. Вот как пакуется один игрок в снапшоте:

/// Пишет игрока бит в бит: id 16, позиция 2 по 16 (квантована), прицел 8,
/// здоровье 7, счёт 16, флаг жив 1. Итого 80 бит вместо 13 байт.
fn write_player_bits(bw: &mut BitWriter, p: &PlayerState) {
    bw.write(p.id as u32, 16);
    bw.write(quantize_pos(p.x) as u32, 16);
    bw.write(quantize_pos(p.y) as u32, 16);
    bw.write(p.aim as u32, 8);
    bw.write(p.health.min(127) as u32, 7);   // здоровья максимум 100, хватает 7 бит
    bw.write(p.score as u32, 16);
    bw.write_bool(p.alive);                   // один бит вместо целого байта
}

Здоровье никогда не больше 100, значит хватает семи бит, а не восьми. Координата f32 это четыре байта, но точность до доли пикселя на проводе не нужна, поэтому позиция квантуется в u16: вдвое короче, а потеря точности на глаз незаметна.

Магия, версия и теги

Это про числа внутри сообщения. Теперь про сами сообщения. Каждый пакет начинается с магического числа и версии:

/// Магическое число протокола. Первые байты любого нашего пакета.
pub const PROTOCOL_ID: u32 = 0x42_53_4E_47; // "BSNG" (BatSchool NetGame)

/// Версия формата. Несовпадение это ошибка протокола.
pub const VERSION: u8 = 1;

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

pub enum ClientMessage {
    Hello { version: u8 },
    Inputs { inputs: Vec<Input> },
    AckSnapshot { tick: u32 },
}

impl ClientMessage {
    const TAG_HELLO: u8 = 1;
    const TAG_INPUTS: u8 = 2;
    const TAG_ACK: u8 = 3;
}

При разборе match по тегу исчерпывающий, а неизвестный тег это типизированная ошибка, а не паника. Это прямой перенос идеи «невозможные состояния невыразимы» из урока про перечисления на провод: enum моделирует множество сообщений, тег это его сериализованный дискриминант.

Полный снапшот против дельты

Последнее крупное решение дизайна. Сервер мог бы каждый такт слать полный снапшот мира. Он самодостаточен, но дорог. Дельта-снапшот шлёт только то, что поменялось с известного базового такта, и он в разы меньше. Цена: получателю нужен тот базовый снапшот, иначе дельту не применить.

/// Строит дельту между базовым и текущим снапшотами.
pub fn diff(base: &Snapshot, current: &Snapshot) -> Self {
    let changed = current
        .players
        .iter()
        .filter(|p| base_map.get(&p.id).map(|b| *b != *p).unwrap_or(true))
        .copied()
        .collect();          // только реально изменившиеся игроки
    let removed = base_map
        .keys()
        .filter(|id| !cur_map.contains_key(id))
        .copied()
        .collect();          // исчезнувшие: умерли или ушли из зоны видимости
    DeltaSnapshot { tick: current.tick, base_tick: base.tick, changed, removed, /* ... */ }
}

/// Применяет дельту к базовому снапшоту. None, если базовый такт не совпал:
/// клиент потерял опору и должен дождаться следующего полного снапшота.
pub fn apply(&self, base: &Snapshot) -> Option<Snapshot> {
    if base.tick != self.base_tick {
        return None;
    }
    // ... берём base, выкидываем removed, накатываем changed
}

Стратегия самовосстанавливающаяся: сервер шлёт полный снапшот как опору, дальше дельты, а при потере синхронизации снова полный. apply возвращает Option, и None это честное «базы нет, жди опору», а не молчаливая порча состояния. Как клиент собирает поток «полный плюс дельты» обратно в снапшоты, разберём в уроке про netcode.

Практика

Соберём ядро протокола руками: varint и кадрирование пакета на его основе. Это тот самый кирпич, на котором стоит всё остальное.

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

Игровой протокол живёт в бюджете пакета: датаграмма должна влезать в MTU (около 1200 байт полезных), иначе фрагментация, иначе потеря всего пакета. Отсюда компактная упаковка: varint кодирует число длиной по его величине (маленькое это один байт), zigzag делает короткими и отрицательные, битовая упаковка кладёт флаги по биту, а квантование меняет лишнюю точность координат на половину размера. На уровне сообщений магия и версия отсекают чужой и несовместимый трафик, тег это сериализованный дискриминант enum с исчерпывающим разбором, а дельта против полного снапшота меняет трафик на зависимость от базы, и Option в apply честно сигналит о потере опоры. Сквозная нить: всё, что читается из сети, проверяется (обрыв, переполнение varint, чужой тег), потому что ввод недоверенный.

Дальше превратим эти приёмы в аккуратный слой сериализации: трейты Encode и Decode, фиксированный порядок байт и курсор чтения, который валидирует каждый доступ к недоверенному буферу.

Домашка