Multi-Stage Lock-Free Message Router

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

Архитектура

Система состоит из трех типов компонентов, соединенных в pipeline:

Producers → Stage1 Router → Processors → Stage2 Router → Strategies

Компоненты

• Producers (4-8 потоков): Генерируют сообщения с высокой скоростью
• Stage1 Router: Маршрутизирует сообщения к процессорам на основе типа сообщения
• Processors (4-8 потоков): Обрабатывают сообщения с имитацией работы
• Stage2 Router: Маршрутизирует обработанные сообщения к стратегиям
• Strategies (2-4 потока): Финальные потребители, проверяющие порядок сообщений

Ключевые особенности

• ✅ Lock-Free дизайн: Использует только атомарные операции, без мьютексов
• ✅ Гарантия порядка: Сообщения от одного производителя одного типа доставляются в порядке
• ✅ Нулевая потеря сообщений: Все сообщения доставляются до получателя
• ✅ Высокая пропускная способность: 10+ миллионов сообщений в секунду
• ✅ Низкая задержка: p99 < 5 микросекунд end-to-end

Требования

Для сборки из исходников

• Ubuntu 22.04+ (или совместимый Linux дистрибутив)
• CMake 3.20+
• Clang 19+
• Git

Для Docker

• Docker 20+
• Docker Compose 2+

Быстрый старт с Docker

Сборка образа

docker-compose build

Запуск тестов

Запуск одного сценария

docker-compose run router-test configs/baseline.json

Запуск всех сценариев

chmod +x scripts/docker_run_all.sh
./scripts/docker_run_all.sh

Запуск бенчмарков

# Все бенчмарки
docker-compose run all-benchmarks

# Отдельные бенчмарки
docker-compose run queue-benchmark
docker-compose run routing-benchmark
docker-compose run memory-benchmark
docker-compose run scaling-benchmark

Просмотр результатов

# Результаты тестов
cat results/baseline_result.txt

# Результаты бенчмарков
ls results/benchmarks/

Сборка из исходников

Установка зависимостей

sudo apt-get update
sudo apt-get install -y build-essential cmake git clang-19 \
    libc++-19-dev libc++abi-19-dev

Сборка проекта

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release \
      -DCMAKE_CXX_COMPILER=clang++-19 \
      -DBUILD_BENCHMARKS=ON ..
make -j$(nproc)

Запуск

# Запуск теста
./router_test ../configs/baseline.json

# Запуск бенчмарка
./queue_benchmark

Тестовые сценарии

1. Baseline (10 секунд)

• 4 производителя × 1M сообщений/сек
• Равномерное распределение по 4 типам сообщений
• Цель: Базовая проверка корректности и производительности

2. Hot Message Type (15 секунд)

• 70% сообщений типа-0 (создание горячей точки)
• 10% для остальных типов
• Цель: Проверка обработки несбалансированной нагрузки

3. Burst Traffic (20 секунд)

• Переменная нагрузка с пиками
• Цель: Проверка обработки всплесков трафика

4. Imbalanced Processing (15 секунд)

• Разное время обработки по типам (50ns - 2000ns)
• Цель: Проверка, что медленный процессор не блокирует остальные

5. Ordering Stress Test (10 секунд)

• Все производители отправляют только тип-0
• Все сообщения идут через один процессор к одной стратегии
• 8M сообщений/сек
• Цель: Проверка сохранения порядка при экстремальной конкуренции

6. Strategy Bottleneck (20 секунд)

• Strategy-0 обрабатывает медленно (1000ns)
• Остальные стратегии быстро (50ns)
• Цель: Проверка обработки backpressure

Структура проекта

.
├── CMakeLists.txt           # Конфигурация сборки
├── Dockerfile               # Multi-stage Docker образ
├── docker-compose.yml       # Оркестрация Docker контейнеров
├── README.md                # Этот файл
│
├── include/                 # Заголовочные файлы
│   ├── spsc_queue.hpp       # Lock-free SPSC очередь
│   ├── mpsc_queue.hpp       # Lock-free MPSC очередь
│   ├── message.hpp          # Структура сообщения
│   ├── config.hpp           # Конфигурация системы
│   ├── statistics.hpp       # Сбор статистики
│   ├── timer.hpp            # Высокоточный таймер
│   ├── producer.hpp         # Производитель сообщений
│   ├── processor.hpp        # Обработчик сообщений
│   ├── strategy.hpp         # Финальный потребитель
│   └── router.hpp           # Роутеры Stage1/Stage2
│
├── src/                     # Исходный код
│   ├── main.cpp             # Главное приложение
│   ├── core/                # Основные компоненты
│   │   ├── message.cpp
│   │   ├── config.cpp
│   │   └── statistics.cpp
│   ├── components/          # Компоненты системы
│   │   ├── producer.cpp
│   │   ├── processor.cpp
│   │   ├── strategy.cpp
│   │   └── router.cpp
│   └── utils/
│       └── timer.cpp
│
├── benchmarks/              # Бенчмарки (Google Benchmark)
│   ├── queue_benchmark.cpp      # Производительность очередей
│   ├── routing_benchmark.cpp    # Накладные расходы маршрутизации
│   ├── memory_benchmark.cpp     # Использование памяти
│   └── scaling_benchmark.cpp    # Масштабирование
│
├── configs/                 # Конфигурационные файлы
│   ├── baseline.json
│   ├── hot_type.json
│   ├── burst_pattern.json
│   ├── imbalanced_processing.json
│   ├── ordering_stress.json
│   └── strategy_bottleneck.json
│
├── scripts/                 # Вспомогательные скрипты
│   ├── run_all_tests.sh
│   └── docker_run_all.sh
│
└── results/                 # Результаты тестов (создается автоматически)
    └── benchmarks/

Lock-Free дизайн

SPSC Queue (Single Producer Single Consumer)

• Кольцевой буфер с атомарными индексами
• Cache-line aligned для избежания false sharing
• Использует memory_order_acquire/release семантику

Маршрутизация

• Busy-waiting для минимальной задержки
• Round-robin балансировка при множественных процессорах
• Прямая маршрутизация без дополнительных копирований

Memory Management

• Все очереди предаллоцированы (размер = 65536)
• Нет динамических выделений на горячем пути
• Сообщения передаются по значению (trivially copyable)

Мониторинг и статистика

Система выводит статистику в реальном времени:

[1.00s] Произведено: 4.00M | Обработано: 3.98M | Доставлено: 3.95M | Потеряно: 0
        Stage1 Queues: [256, 312, 298, 189] | Stage2 Queues: [512, 234, 445]
        Задержки(μs) - Stage1: 0.34 | Processing: 0.18 | Stage2: 0.41 | Total: 1.23

Финальный отчет включает:

• Общее количество сообщений
• Пропускную способность
• Перцентили задержек (p50, p90, p99, p99.9, max)
• Проверку порядка для каждого производителя
• Результат теста (PASSED/FAILED)

Оптимизации

1. Busy-waiting: Минимизирует задержку, но нагружает CPU
2. Cache-line alignment: Избегает false sharing между потоками
3. Compile-time optimization: -O3 -march=native для максимальной производительности
4. Atomic operations: Только relaxed/acquire/release memory order где возможно
5. Zero-copy: Сообщения передаются без лишних копирований

Известные ограничения

• Размеры очередей фиксированы на этапе компиляции
• Busy-waiting приводит к 100% использованию CPU
• Требуется современный процессор с поддержкой атомарных операций
• Ограничение на количество производителей/процессоров (до 16)

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

Целевые метрики

• Пропускная способность: 10+ миллионов сообщений/сек
• Задержка (p99): < 5 микросекунд
• Потеря сообщений: 0
• Нарушения порядка: 0

Факторы производительности

• Количество ядер CPU
• Частота процессора
• Размер кэша L1/L2/L3
• Memory bandwidth
• Настройки CPU governor

Troubleshooting

Низкая производительность

• Проверьте CPU governor: cat /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
• Установите performance mode: sudo cpupower frequency-set -g performance
• Отключите CPU frequency scaling в BIOS

Нарушения порядка

• Проверьте размеры очередей (могут быть слишком маленькими)
• Увеличьте QUEUE_SIZE в исходном коде
• Уменьшите скорость генерации сообщений

Потеря сообщений

• Обычно связано с переполнением очередей
• Увеличьте размеры очередей или уменьшите нагрузку

Лицензия

Этот проект создан в образовательных целях.

О проекте

Проект разработан в рамках изучения высокопроизводительных систем обработки сообщений и lock-free программирования. Реализация демонстрирует применение современных техник concurrent programming для построения систем с ультра-низкими задержками, применяемых в HFT (High-Frequency Trading) и других критичных по времени областях.