В 2004 году я слишком много играл в RuneScape на модеме 56k, который разрывал соединение, когда мама поднимала трубку. 3D-мир, на сервере которого могло быть до тысячи игроков и десятки на экране одновременно... И всё это в браузере со скоростью 5 килобайт в секунду. Каким-то образом всё это работало. Давайте пошагово разберёмся, как же именно.

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

Методология

Подробности, приведённые в этом посте, взяты из декомпилированного клиента RuneScape 2 от 2004 года. Фрагменты кода — это приблизительная трансляция этого декомпилированного кода, местами подчищенная для удобочитаемости, но с сохранением логики.

Базовые принципы различаются между разными версиями, но большинство из них остаётся неизменным от самой RuneScape Classic (2001 год) до современной RuneScape 3 и, разумеется, до Old School RuneScape.

Если вы играли в RuneScape в начале 2000-х и у вас всё ещё есть жёсткие диски из той эпохи, то советую заглянуть в RuneScape Archive Project. Его авторы проделали отличную работу по каталогизации исторических версий RuneScape, которые в противном случае были бы утеряны, и им важен каждый вклад.

Ограничения

Давайте рассмотрим некоторые ограничения, с которыми приходилось в то время считаться компании-разработчику Jagex.

Ширина канала. Модем 56k синхронизируется со скоростью 56 килобит/с на скачивание и ещё меньше на загрузку минус оверхеды протоколов и шум линии. Будем считать, что это 5 КБ/с на скачивание и намного меньше на загрузку. К 2000 году домашний широкополосный доступ уже был в Британии, но в большинстве домов он появился только в конце 2000-х, то есть многие игроки сидели на коммутируемом соединении.
Java-апплет в браузере в 2004 году. Java-апплеты работали в защищённой песочнице, что означало отсутствие сырых нативных сокетов и UDP. Каждый байт передавался по единичному TCP-соединению по порядку и с оверхедом на каждый сегмент.
Серверный цикл 600 мс. Игровые серверы RuneScape делали шаги по дискретным циклам, примерно равным 600 миллисекундам. На каждом цикле сервер должен был разобраться, что видит каждый игрок, и отправить эту информацию до наступления следующего цикла.

Краткое описание слоя шифрования

После завершения handshake логина и перед отправкой игровых пакетов настраивается небольшой слой шифрования. Он нужен не для экономии байт; это единственное шифрование в стеке (если не считать RSA-шифрования при handshake); он нужен потому, что от защищаемого им опкодa зависит всё то, о чём мы будем говорить ниже.

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

Оба потока порождаются из общего ключа, состоящего из четырёх целых чисел. Два из них клиент генерирует сам; два других поступают от сервера в рамках handshake. Затем поток от сервера к клиенту использует то же самое порождающее значение с прибавленным к каждому слову 50 — этого достаточно для того, чтобы два направления не использовали один ключевой поток:

this.outboundCipher = new ISAAC(seed);

for (int index = 0; index < 4; index++) {
    seed[index] += 50;
}

this.inboundCipher = new ISAAC(seed);

Шифрование на выходе выполняется в одну строку:

public void putOpcode(int opcode) {
    this.putByte(opcode + this.outboundCipher.value());
}

На входе данные отзеркаливаются:

this.currentOpcode = (this.currentOpcode - this.inboundCipher.value()) & 0xFF;

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

Отправка запроса на перемещение

Мы рассмотрим, что происходит, когда игрок нажимает на тайл на один квадрат к северу, и что передаётся на сервер.

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

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

Позиция начала занимает 4 байта (два short), каждая последующая дельта точки пути занимает 2 байта, а последний байт определяет, удерживается ли клавиша Ctrl. То есть длина тела равна 4 + 2 * (pathLength - 1) + 1.

this.outboundStream.putOpcode(ClientToServerOpcodes.WALK_TILE);
this.outboundStream.putByte(4 + 2 * (pathLength - 1) + 1);

Пакет содержит абсолютную позицию первой точки пути маршрута (x и z передаются как двухбайтные short), за которой идёт дельта каждой точки пути относительно первой: по одному байту со знаком на каждую ось, что удобно попадает в байтовый диапазон от -128 до 127, поскольку одно нажатие мыши не может находиться дальше этого расстояния.

Решение отправлять здесь только дельту в виде 2 байт на шаг, а не абсолютных координат в виде 4 байт на шаг — это первый пример бережного обращения Jagex с сетевыми данными. В абсолютных величинах это позволяет экономить всего несколько байт на один пакет перемещения, но каждая дополнительная точка пути занимает 2 байта вместо 4 байт — экономия в 50% на каждую точку.

int firstX = pathX[0];
int firstZ = pathZ[0];

this.outboundStream.putShort(this.playerPositionX + firstX);
this.outboundStream.putShort(this.playerPositionZ + firstZ);

for (int i = 1; i < pathLength; i++) {
    this.outboundStream.putByte(this.pathX[i] - firstX);
    this.outboundStream.putByte(this.pathZ[i] - firstZ);
}

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

Например, в рассматриваемой нами версии этот пакет записан как (x, z, ...path), в других версиях, например 317, как (x, ...path, z), а в ещё одних — как (...path, x, z).

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

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

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

Последняя часть пакета — это байт, обозначающий, удерживается ли клавиша Ctrl. В ранних версиях игры это использовалось для применения «режима бега», в последующих версиях инвертировало текущий режим перемещения (персонаж бежал к точке, если «режим бега» был отключен, или шёл, если он включен):

this.outboundStream.putByte(this.keyStatus[Keys.CTRL] == 1 ? 1 : 0);

Итак, мы видим, что наш один шаг на север занимает семь байт, включая опкод и маркер длины:

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

4 + 2 * (pathLength - 1) + 1 = 4 + 2 * 0 + 1 = 5

После выполнения показанных выше фрагментов кода пакет попадает в исходящий поток клиента. Поток передаётся в сеть примерно каждые 20 мс.

Сервер получает запрос

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

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

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

int opcode = player.inboundStream.takeOpcode();

if (opcode == ClientToServerOpcodes.WALK_TILE) {
    int length = player.inboundStream.takeByte();

    int deltaCount = (length - 4 - 1) / 2;

    int[] firstWaypoint = new int[2];
    firstWaypoint[0] = player.inboundStream.takeShort();
    firstWaypoint[1] = player.inboundStream.takeShort();

    int[][] waypointDeltas = new int[deltaCount][2];
    for (int i = 0; i < deltaCount; i++) {
        waypointDeltas[i][0] = player.inboundStream.takeByte();
        waypointDeltas[i][1] = player.inboundStream.takeByte();
    }

    boolean holdingCtrl = player.inboundStream.takeByte() == 1;

    player.processWalkTile(firstWaypoint, waypointDeltas, holdingCtrl);
}

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

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

if (opcode == ClientToServerOpcodes.USE_ITEM_ON_ITEM) {
    int sourceItemId = player.inboundStream.takeShort();
    int sourceInterfaceId = player.inboundStream.takeShort();
    int sourceInterfaceSlot = player.inboundStream.takeShort();

    int targetItemId = player.inboundStream.takeShort();
    int targetInterfaceId = player.inboundStream.takeShort();
    int targetInterfaceSlot = player.inboundStream.takeShort();

    player.processUseItemOnItem(/* ... */);
}

Этот пакет имеет фиксированную длину 12 байт (6 short). Сервер знает о фиксированной длине, поэтому в этом пакете не нужно передавать маркер длины.

Цикл сервера

Цикл сервера RuneScape состоит из множества этапов, а интересующие нас части происходят в следующем порядке:

Чтение входящих пакетов
Обработка игроков (действия в очереди, триггеры, движение и так далее)
Создание обновлений игроков (подробнее об этом в следующем разделе)
Отправка исходящих пакетов

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

В целом порядок чёток: чтение, потом действие, потом запись.

Обновления игроков

Перед тем, как разбираться с пакетом, стоит объяснить, на чём строится протокол: клиент хранит своё зеркало каждого игрока, которого он может видеть. Это отслеживаемый список ближайших игроков с их последним известным местоположением, внешним видом, анимацией и состоянием чата, плюс собственное локальное состояние игрока. Задача пакета обновления игрока заключается в синхронизации этого зеркала с достоверной версией состояния сервера, и это почти всегда означает, что обновление — это дельта относительно того, что игрок уже знает. Именно поэтому состояние «изменений нет» настолько экономно: у клиента уже есть все данные, а сервер лишь подтверждает, что они по-прежнему валидны.

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

private void readPlayerUpdates(Packet packet) {
    packet.accessMode(PacketAccess.BITS);

    this.readLocalPlayer(packet);

    // другие игроки, уже отслеживаемые клиентом
    this.readOtherPlayers(packet);

    // игроки, только появившиеся в области видимости, которых клиент должен начать отслеживать
    this.readNewPlayers(packet);

    packet.accessMode(PacketAccess.BYTES);

    // подробные изменения, связанные с игроками
    this.readPlayerDetails(packet);
}

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

Этап 1: локальный игрок

Логика чтения локального игрока проста, поэтому позволю вам самим её прочитать, а проанализировать её можно позже:

private void readLocalPlayer(Packet packet) {
    int updated = packet.takeBits(1);

    // нет локального движения или не изменились локальные подробности
    if (updated == 0) {
        return;
    }
    
    int movementType = packet.takeBits(2);

    // тип 1: ходьба
    if (movementType == 1) {
        int direction = packet.takeBits(3);

        this.localPlayer.step(direction, false);

        int detailUpdated = packet.takeBits(1);
        if (detailUpdated == 1) {
            this.trackPlayerDetails(this.localPlayer.id);
        }
    }
    // тип 0: движения нет, но далее следует обновление подробностей
    // тип 2: бег - два направления подряд
    // тип 3: телепорт
}

Обратите внимание на первую конструкцию if. Если в этом цикле локальный игрок не двигался, и ничего связанное с ним не менялось, то всё его присутствие в пакете обновления составляет один бит. Даже не байт, а бит. Самое частое состояние любого игрока в любом цикле — «нет изменений» — оказывается самой малозатратной передачей.

Если локальный игрок всё-таки сдвинулся, это 1 бит, ещё два бита описывают тип, три бита — направление, а ещё один бит определяет, будут ли ещё следовать подробности. Информация «я сделал шаг» занимает семь бит, даже не один байт. Если исключить первый флаг «требуется обновление» и тип движения, это умещается в четыре бита.

Другие типы тоже экономны. Если исключить трёхбитные заголовки:

тип 0 (движения нет, но далее следуют подробности): отсутствие полезной нагрузки. Нулевой бит.
тип 2 (бет): два 3-битных направления и бит флага «дополнительные подробности». Семь бит.
тип 3 (телепорт): плоскость высоты (2 бита), координаты x и z (по 7 бит каждая), бит флага «дополнительные подробности» и бит прыжка (используется, чтобы сообщить клиенту, должен ли он попытаться анимировать это движение). Чуть затратнее, но всё равно всего восемнадцать бит, немного больше двух полных байт.

Этап 2: отслеживаемые игроки

Здесь принцип такой же, только применяется он к набору уже отслеживаемых игроков.

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

private void readOtherPlayers(Packet packet) {
    int count = packet.takeBits(8);

    for (int i = 0; i < count; i++) {
        int updated = packet.takeBits(1);

        if (updated == 0) {
            continue;
        }

        // чтение типа движения и тому подобного, как выше
    }
}

После 8-битного значения количества игроков идёт по одному биту на каждого известного игрока, сообщающему, происходит ли с ним что-то. Если локальный игрок стоит в толпе из сорока игроков, ни один из которых не двигается, то для подтверждения того, что вся сцена статична, достаточно 48 бит (6 байт). Любой игрок, сделавший шаг, стоит те же семь бит, что и локальный игрок на этапе 1.

В этом и заключается главная хитрость. Значение по умолчанию («ничего не изменилось») — это один бит, максимально экономное описание. Реальные биты тратятся только на то, что на самом деле переместилось. У сервера и клиента имеется одинаковое понимание протокола, внедрённое в них на этапе компиляции, в том числе и то, что подразумевается под состоянием по умолчанию, а что считается изменением. Ни тому, ни другому никогда не нужно детализировать отсутствие изменений; отсутствие подробностей, скрывающееся за нулевым битом, и есть сообщение.

Этап 3: появление новых игроков в области видимости

Когда кто-то входит в область видимости игрока (или появляется иным образом: выполняет логин, телепортируется и так далее) впервые, сервер должен представить его: кто это и где находится относительно игрока:

private void readNewPlayers(Packet packet) {
    // место для 11-битного id игрока
    while (packet.bitsRemaining > 10) {
        int playerId = packet.takeBits(11);

        // ограничитель: больше игроков нет
        if (playerId == 2047) {
            break;
        }

        Player otherPlayer;
        // ... распределяем или ищем игрока ...

        int updated = packet.takeBits(1);
        if (updated == 1) {
            this.trackPlayerDetails(playerId);
        }

        int teleported = packet.takeBits(1);

        int deltaX = packet.takeBits(5);
        if (deltaX >= 16) { deltaX -= 32; } // знаковое 5-битное значение: от -16 до +15

        int deltaZ = packet.takeBits(5);
        if (deltaZ >= 16) { deltaZ -= 32; }

        otherPlayer.move(localPlayer.x + deltaX, localPlayer.z + deltaZ, teleported == 1);
    }
}

11-битный id игрока (2047 зарезервирован как останавливающее значение, поэтому списку не нужен заголовок длины), по одному биту, обозначающему, будет ли дальше идти обновление «дополнительные подробности», один бит, определяющий, телепортировался ли игрок, а затем 10 бит позиции. Позиция — это одна из тех деталей, которые в этом блоке нравятся мне больше всего.

Относительные координаты

Абсолютные координаты игрока — это пара значений с диапазоном значений до тысяч — карта RuneScape очень большая (тысячи тайлов по каждой из осей). Это два 16-битных числа (итого 32 бита) для размещения игрока в любой точке карты.

Однако логике обновления игрока не нужна глобальная позиция. Ей нужно лишь знать, где он находится относительно локального игрока, потому что это всё, что он видит. Другой игрок, находящийся на расстоянии отрисовки, может быть максимум в 15 тайлах от локального. 15 удобно умещаются в знаковое 5-битное число (от -16 до +15). То есть местоположение только что появившегося в области видимости игрока стоит десять бит, по пять на ось, вместо тридцати двух. Пространство координат центрируется по локальному игроку и усекается по границам видимости. Кодирование имеет размер ровно под видимую область и не битом больше. Та же логика встречается в ветвлении телепортации этапа 1, где координаты выражаются в виде двух 7-битных значений (чего достаточно для адресации загруженной площади со стороной 104 тайла), а не в координатах всего мира.

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

Битовый курсор

В начале этого раздела я говорил, что этапы с первого по третий считывают отдельные биты, а этап 4 считывает полные байты. Все эти операции чтения «нескольких бит за раз» обеспечиваются одним маленьким методом. Биты заполняют каждый байт сверху вниз — первый бит находится в позиции 7, последний — в позиции 0:

public int takeBits(int count) {
    int value = 0;
    for (int n = 0; n < count; n++) {
        int bytePos = this.bitPosition / 8;
        int bitInByte = 7 - (this.bitPosition % 8);

        int bitValue = (this.buffer[bytePos] >> bitInByte) & 1;
        value = (value << 1) | bitValue;

        this.bitPosition++;
    }
    return value;
}

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

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

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

Этап 4: изменение подробностей игрока

Четвёртый этап отвечает за детализированные обновления игроков, обычно связанные с их внешним видом. Он обрабатывает только игроков, для которых установлен флаг «далее следует обновление подробностей».

Вот полный список флагов обновления:

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

Два последних флага в списке всегда (насколько я могу судить) представлены битами в старшем байте типа обновления. Обычно они бывают более редкими обновлениями, и мне кажется, что такая структура выбрана намеренно для экономии: передачи второго байта типа обновления требуют только редкие события.

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

Выполняются итерации для всех игроков в массиве «дополнительные подробности» и считывается флаг «тип обновления»:

private void readPlayerDetails(Packet packet) {
    for (int i = 0; i < moreDetailPlayerCount; i++) {
        int updateType = packet.takeByte();

        if ((updateType & 0b1000_0000) != 0) {
            updateType |= packet.takeByte() << 8;
        }
        
        // ...
    }
}

Здесь можно заметить ещё один трюк для эффективного использования байтов. Девять флагов из списка не уместились бы в один байт, если каждый флаг будет отдельным битом, поэтому полный тип обновления требовал бы адресации двух байтов. Вместо того, чтобы считывать по два байта на игрока (при помощи takeShort), семь байт упаковываются в первый байт с одним битом-маркером — старшим битом. Когда этот бит маркера установлен, второй байт считывается, смещённый влево на один байт и скомбинированный с первым, образуя 16-битное значение (в котором значимы 10 бит: 9 флагов плюс маркер).

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

После получения полного типа обновления в нём происходит поиск наличия отдельных флагов для применения конкретных подробностей. Часть из них показана в этом коде:

if ((updateType & 0b0000_0100) != 0) {
    // игрок смотрит на сущность (npc или другого игрока)
    player.targetEntityId = packet.takeShort();
}

if ((updateType & 0b0010_0000) != 0) {
    // игрок смотрит на тайл
    player.targetTileX = packet.takeShort();
    player.targetTileZ = packet.takeShort();
}

if ((updateType & 0b0000_0010) != 0) {
    // игрок выполняет анимацию
    player.animationId = packet.takeShort();
    player.animationDelay = packet.takeByte();
}

// ... другие флаги ...

// проверяем младший бит старшего байта
if ((updateType & (0b0000_0001 << 8)) != 0) {
    // у игрока воспроизводится графический эффект
    player.graphicalEffectId = packet.takeShort();
    player.graphicalEffectHeight = packet.takeShort();
    player.graphicalEffectDelay = packet.takeShort();
}

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

Обновление внешнего вида

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

имя
боевой уровень
информацию о частях тела, включая экипированные предметы и трансмогрификации NPC
цвет частей тела
анимации стояния/ходьбы
пол
иконки головы (иконки молитвы, череп player killer)

В целом раздел внешнего вида занимает от 44 до 80 байт на каждого игрока.

Почему не используется побитная упаковка?

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

На этапах 1, 2 и 3 так многократно и происходит. Состояние по умолчанию («нет изменений») — это один бит, и в каждом цикле он повторяется для каждого видимого игрока, поэтому при десятках сущностей экономия накапливается. Этапу 4 это не присуще. У него нет какого-то крошечного значения по умолчанию: у игрока или вообще нет обновления (что уже обработано однобитной загрузкой), или есть, самое маленькое поле которого, «смотрит на сущность», уже представляет собой двухбайтный short. Значение short не позволяет ничего сэкономить, заняты оба его байта, поэтому побитовая упаковка ничего бы не сэкономила, но всё равно бы требовала затрат на работу с курсором. Множитель тоже пропадает: на этапе 4 всегда содержится только несколько игроков, состояние которых поменялось в этом цикле, а не вся толпа, поэтому даже если и есть биты для экономии, их почти не на что умножить. Единственное место, где трюк себя оправдывает — это сам байт типа обновления: благодаря биту маркера второй байт можно использовать только по необходимости; происходит битовая упаковка в байт, как раз там, где есть место.

Вторая причина заключается в способе составления сервером этой части пакета: на самом деле, это тот же принцип, но со стороны сервера. Многие поля на этапе 4 не вычисляются заново на каждом цикле: мне кажется, буфер внешнего вида создаётся только при изменении у отдельного игрока и хранится в виде буфера байтов, который сервер разрезает на исходящие пакеты для всех наблюдателей, кому они нужны. Клиент точно кэширует его таким образом, повторно используя его, когда отслеживаемый игрок покидает видимую область и возвращается в неё; было бы странно, если бы сервер не повторял такого поведения. Такое разрезание экономно, потому что выровненный по байтам блоб данных не зависит от позиции: где бы он ни оказался в пакете конкретного наблюдателя, он представляет одну и ту же последовательность байт, то есть для его вставки достаточно обычного копирования из массива. Если упаковать его побитово, то его смещение будет зависеть от того, что было записано до него, а эта информация варьируется для каждого наблюдателя и цикла, поэтому для одного и того же кэшированного блоба потребуется свежий сдвиг и маска для каждого наблюдателя и цикла, а значит, смысл кэша пропадает.

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

Байты по проводам

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

После добавления байта опкода и маркера длины (два байта вместо однобайтного маркера, использованного для пакета движения — длина блока обновления игрока может быть больше 255) мы получаем примерно девять байт, полностью отвечающих на вопрос «какие действия только что выполнили все рядом со мной?» в цикле, где один человек сделал один шаг в толпе из двадцати одного. Ваш передаваемый на сервер пакет движения занимал семь байт; обновление вернуло вам примерно девять. Шестнадцать байт на путь от сервера и обратно для одного шага; при этом сервер отправляет один и тот же девятибайтный ответ всем другим игрокам, которые вас видят. При скорости 5 КБ/с у нас остаётся достаточно места для отправки сотен таких пакетов в секунду; в этом и заключается смысл — бои, расположение игроков и чат должны умещаться в один и тот же конвейер.

Для понимания масштабов: текст этого поста на английском занимает примерно 32 КБ, то есть более чем в три тысячи раз больше, чем эти девятибайтные обновления сцены. Статья об экономности протокола намного больше, чем те данные, которые он отправляет.

Вот как выглядит весь путь:

Главный урок

Клиент и сервер RuneScape общаются не при помощи двух обменивающихся сообщениями систем. Они работают совместно как одна система, разделённая в TCP-соединении. Все возможности экономии этого протокола связаны с тем, что обе стороны имеют общие знания о том, что не передаётся:

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

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

Можно читать эту статью как исследование реликта той эпохи, когда широкополосный доступ ещё был недоступен или дорог. Но граница никогда не пролегала между старым и новым; она зависит от предназначения системы и от того, что её на самом деле ограничивает. Современный веб-сервис намеренно разрабатывается противоположным образом: cо слабым связыванием, самодокументируемый, версионный, подробный — то же обновление сцены в виде JSON через HTTP занимало бы сотни байт и одни заголовки превышали девять байт. Эта роскошь — не пустая трата, с её помощью мы покупаем возможность изменения одной стороны без повторного развёртывания другой, работы со множеством различных клиентов и отладки при помощи чтения передаваемых данных. Эти параметры следует выбирать по умолчанию, если главными ограничениями становятся команды и скорость внедрения изменений, а не байты.

Легко забыть о том, что большая доля ПО, которое пишут сегодня, по-прежнему находится по ту же сторону границы, что и RuneScape. При проектировании сетевого шутера, файтинга, фида финансовых данных следует использовать тот же подход с тесным сопряжением клиента и сервера, побитовой упаковкой и встроенной схемой данных. Разделённый стиль — это не фича современной архитектуры, а необходимость для обеспечения возможности независимой развёртывания. Выбор зависит от того, какое ограничение важнее всего.

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

Благодарности

Выражаю благодарность компании Jagex за создание игры, которая не только прошла испытание временем, но и интересна для разбора и анализа даже спустя двадцать лет.

Спасибо множеству участников сообществ сохранения игр и реверс-инжиниринга, с которыми я работал последние пятнадцать лет и от которых получил имеющиеся у меня теперь знания.

Имена переменных и структуры взяты из декомпилированного и подчищенного клиента RuneScape; архитектура полностью разработана Jagex.

Как RuneScape в 2004 году удавалось работать на 56k-соединении