Как тик работает параллельно

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

Системы с разными данными выполняются одновременно

mcrs построен на Bevy ECS (entity component system). В ECS поведение - это набор функций, которые называют системами, и каждая система выполняет одно преобразование над всеми сущностями, у которых есть нужные ей данные. Bevy запускает две системы одновременно, если их доступ к данным не пересекается, поэтому блокировки писать не нужно. Конфликты находит планировщик Bevy, когда строит граф расписания. Компилятор их не проверяет.

Порядок между группами систем задают наборы систем (system sets), то есть именованные группы. Кроме того, проект проверяет расписание на неоднозначность, об этом написано в разделе 13 заметки о шардировании. Тик разбит на несколько фаз с небольшим числом точек синхронизации.¹

Сущности читают замороженный снапшот и пишут в свою строку

У одной системы сущностей все равно может быть очень много, поэтому работа делится и внутри нее. Для сущностей mcrs использует модель из раздела 3 заметки docs/physics-architecture.md:

1. В начале тика движок замораживает снапшот состояния, которое видят другие сущности: блоки в том виде, какими они были в конце прошлого тика, сетку тел и таблицу позиций.
2. Пространство режется на тайлы из колонок. Каждый тайл - задача над строками сущностей, которые в нем находятся.
3. Каждая сущность читает только снапшот и пишет только в свою строку. Эффекты на другие сущности, например толчок или подбор предмета, собираются и применяются позже в фиксированном порядке.

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

Результат одинаков при любом числе потоков

Собранные эффекты сливаются по стабильному ключу, поэтому результат не зависит от машины. Ключ - сохраняемый UUID сущности, а не сетевой id. По этому же ключу решается, кто выигрывает при равенстве между сущностями.

В проекте детерминизм разделен на три уровня:²

Уровень	Гарантия	Где действует
Точный	Результат совпадает с эталоном	Генерация мира, арифметика движения игрока, все, что выбирается случайно по seed, сохраненному в мире
Не зависящий от планировщика	Одинаковые входные данные дают одинаковый тик при любом порядке потоков	Все остальное
Свободный	Допустим любой порядок	Сущности и системы, которые не пишут в общие данные

Сейчас это подтверждают две проверки. Первая - тест tick_determinism.rs. Он прогоняет мир из двух ячеек 60 тиков: один раз со всеми мирами inline в одном потоке, другой раз с потоками. После каждого тика тест хеширует все состояние симуляции и падает на первом тике, где хеши различаются.

Тест: потоки и один поток должны дать одинаковый мир

#[test]
fn the_world_a_tick_produces_does_not_depend_on_the_threads() {
    let inline = run(Placement::Inline);
    let threads = run(Placement::Thread);
    assert_eq!(
        first_divergence(&inline, &threads),
        None,
        "the threads diverge from Inline at the tick shown (the last entry holds the blocks)"
    );
}

crates/mcrs_minecraft_server/tests/it/tick_determinism.rs:274-283

Запустите проверку хеша сами

Вторая проверка - пример в крейте физики. Он строит тестовую сцену из 50 000 ходоков и 50 000 предметов на 32 x 32 тайлах и печатает хеш сцены после N тиков:

cargo run --release -p mcrs_minecraft_engine_physics --example state_hash -- <threads> <ticks>

Запустите его с 1 потоком, потом с 8 потоками, и хеш в конце строки совпадет. Пример печатает и архитектуру, так что можно сравнить две машины. Код короткий:

state_hash: одна сцена, любое число потоков

fn main() {
    let mut arguments = std::env::args().skip(1);
    let threads: usize = arguments.next().unwrap().parse().unwrap();
    let ticks: u32 = arguments.next().unwrap().parse().unwrap();
    let pool = TaskPoolBuilder::new().num_threads(threads).build();
    let mut scene = TestScene::<()>::new(16, 50_000, 50_000, 11);
    let tiles_per_task = (32 * 32_usize).div_ceil(threads * 4);
    let mut writes = EntityWrites::default();
    for _ in 0..ticks {
        scene.step(&pool, tiles_per_task, &mut writes);
    }

crates/mcrs_minecraft_engine_physics/examples/state_hash.rs:14-24

Пример проверяет дизайн и о скорости ничего не говорит. Ему нужен тулчейн nightly, и в руководство по установке он не входит, а само руководство пока WIP.

Что параллельно сегодня, а что остается целью

Область	Состояние
Проход по сущностям над тайлами с замороженным снапшотом, хеш одинаков при любом числе потоков	есть в коде, покрыто примером и тестами выше
Ячейки одного мира тикают одновременно с обменом halo	есть в коде, покрыто tick_determinism.rs
Освещение и генерация мира в своих потоках, результат применяется на границе тика	есть в коде
Симуляция блоков: отложенные тики, обновления блоков, шарды	частично: ядра есть, шарды со слиянием и разделением - В работе#160
Редстоун	не начат: В работе#190
Одно измерение на многих машинах	цель: В работе#181

WIP

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

То, что не меняется, ничего не стоит

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

Пока не измерены две вещи: стоимость тика простаивающего сервера и память на секцию.⁵⁶ Чисел бенчмарков по мобам проект на этой странице не публикует. Что есть в PERF.md, с машиной и сценарием рядом с каждым числом, показано на странице Производительность и как мы ее измеряем.

Дальше: Ячейки и путь к многим узлам.

Footnotes

1. Частично#364 Решение о том, что тик идет фазами с небольшим числом точек синхронизации. ↩

2. Работает#367 Решение, которое вводит три уровня детерминизма. ↩

3. В работе#190 Отслеживает редстоун-схемы, которые ведут себя как в ванили. ↩

4. Частично#365 Решение о том, что работа пропорциональна изменениям. ↩

5. В работе#320 Отслеживает измерение тика простаивающего сервера. ↩

6. В работе#324 Отслеживает фиксацию размеров компонентов и подсчет памяти секций. ↩