Как оценивать системы распределённой координации? -- Обзор и анализ

Основная информация

• ID статьи: 2403.09445
• Название: How to Evaluate Distributed Coordination Systems? -- A Survey and Analysis
• Авторы: Bekir Turkkan (IBM Research), Elvis Rodrigues (University at Buffalo), Tevfik Kosar (University at Buffalo), Aleksey Charapko (University of New Hampshire), Ailidani Ailijiang (Microsoft), Murat Demirbas (MongoDB)
• Категория: cs.DC (Распределённые вычисления)
• Дата публикации: Препринт arXiv, последнее обновление 27 октября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2403.09445

Аннотация

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

Исследовательский контекст и мотивация

1. Основная проблема

Системы распределённой координации (включая алгоритмы консенсуса, сервисы координации и распределённые приложения) не имеют стандартизированных инструментов оценки, что приводит к:

• Неполной оценке: разработчики либо используют тесты NoSQL (например, YCSB), но игнорируют согласованность, распределённость и отказоустойчивость
• Плохой сравнимости: различные системы используют пользовательские микротесты с разными метриками и методами, что делает справедливое сравнение невозможным
• Фрагментации оценки: отсутствует единая структура для комплексной оценки производительности, масштабируемости, доступности и согласованности

2. Значимость проблемы

• Практические потребности: облачные вычисления и приложения больших данных (поисковые системы, социальные сети, потоковая передача видео, IoT) зависят от распределённой координации
• Технологическая эволюция: от Paxos к Raft и далее к оптимизированным для WAN вариантам, таким как WPaxos и SwiftPaxos
• Широкое применение: критические системы Google Spanner, Apache Kafka, Twitter Manhattan и другие зависят от сервисов координации
• Сложность оценки: системы распределённой координации требуют одновременного рассмотрения производительности, согласованности, отказоустойчивости и географического распределения

3. Ограничения существующих подходов

Недостатки существующих инструментов тестирования:

• YCSB: однопроцессный клиент, не поддерживает перекрытие доступа к данным, локальность доступа и другие критические параметры
• TPC-C: в основном предназначен для обработки транзакций, не подходит для специфических требований сервисов координации
• Jepsen: требует глубокого понимания внутреннего устройства инструмента, не является чёрным ящиком, сложен в применении
• Отсутствие поддержки WAN: большинство инструментов не поддерживают оценку географически распределённых сценариев

4. Исследовательская мотивация

Данная работа проводит систематическое исследование практик оценки 30+ систем распределённой координации с целью:

• Выявить общие черты и различия в текущих практиках оценки
• Определить основные требования к оценке систем распределённой координации
• Проанализировать недостатки существующих инструментов тестирования
• Предоставить рекомендации для разработки стандартизированных инструментов тестирования в будущем

Основные вклады

1. Систематическое исследование: анализ практик оценки 30+ систем распределённой координации (включая 13 алгоритмов консенсуса, 10 сервисов координации, 7 распределённых приложений)
2. Топологическая классификация: выявление и определение 6 типов экспериментальной топологии (плоская, звёздообразная, многозвёздообразная, иерархическая, сетевая, центральный журнал), обеспечивающих основу для понимания архитектуры системы
3. Система метрик и параметров:
   • Систематизация 4 основных метрик оценки: производительность, масштабируемость, доступность, согласованность
   • Выявление критических параметров рабочей нагрузки: соотношение чтения/записи, перекрытие доступа к данным, локальность доступа, количество и размер объектов
4. Требования к тестированию: определение 7 основных требований к инструментам тестирования систем распределённой координации:
   • Гибкость и сложность
   • Поддержка WAN-систем
   • Масштабируемость самого инструмента тестирования
   • Простота применения
   • Возможность чёрного ящика
   • Возможность проверки согласованности
   • Возможность внедрения сбоев
5. Анализ пробелов: систематический анализ возможностей и недостатков 10+ существующих инструментов тестирования (YCSB, TPC-C, Jepsen, Elle и др.)
6. Практические рекомендации: предоставление исследователям и инженерам лучших практик и соображений при оценке систем распределённой координации

Подробное описание методологии

Определение задачи

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

• Входные данные: статьи и материалы оценки 30+ систем распределённой координации
• Обработка: извлечение информации о топологии оценки, метриках, параметрах, инструментах
• Выходные данные: систематизированное резюме практик оценки, анализ требований и сравнение возможностей инструментов

Методология исследования

1. Критерии выбора систем

Авторы выбрали три класса систем на основе релевантности, актуальности и влияния:

Класс I: Алгоритмы консенсуса (13)

• Варианты Paxos: Mencius, FPaxos, Multi-Paxos, Hybrid-Paxos, E-Paxos, M2 Paxos, WPaxos, SwiftPaxos, Omni-Paxos
• Другие протоколы: Raft, Bizur, ZAB, Hydra

Класс II: Сервисы координации (10)

• ZooKeeper, Tango, Calvin, WanKeeper, ZooNet, Boki, FlexLog, SplitFT, Fabric, Narwhal

Класс III: Распределённые приложения (7)

• Spanner, DistributedLog, PNUTS, COPS, CockroachDB, OceanBase, ScalarDB

2. Структура топологической классификации

Авторы определили 6 типов топологии на основе способа создания кворума и способа обработки запросов:

3. Извлечение и анализ данных

Из статей каждой системы извлекались:

• Экспериментальная установка: количество регионов, серверов, клиентов, платформа тестирования, инструменты тестирования
• Метрики оценки: пропускная способность, задержка, масштабируемость, доступность, согласованность
• Параметры рабочей нагрузки: соотношение чтения/записи, количество/размер объектов, перекрытие доступа к данным, локальность доступа

Экспериментальная установка (результаты исследования)

Распределение экспериментальных топологий

Авторы проанализировали экспериментальные установки 30 систем и выявили основные результаты:

Географическое распределение:

• Развёртывание в одном регионе: большинство систем (например, Raft, Multi-Paxos, ZooKeeper)
• Развёртывание в нескольких регионах: системы, оптимизированные для WAN (например, WPaxos с 5 регионами и 15 серверами, SwiftPaxos с 13 регионами)
• Реальные облачные окружения: Amazon EC2, Google Compute Engine, Alibaba ECS
• Контролируемые окружения: Emulab, DETER (с контролируемой сетевой задержкой)

Масштаб кластера:

• Малый масштаб: 3-13 серверов (большинство алгоритмов консенсуса)
• Средний масштаб: 15-100 серверов (сервисы координации)
• Большой масштаб: OceanBase достигает 1557 серверов, 360 000 клиентов/серверов

Конфигурация клиентов:

• Один клиент: Bizur, Omni-Paxos
• Многопоточные клиенты: Multi-Paxos (1-20 потоков)
• Распределённые клиенты: E-Paxos (50 клиентов), PNUTS (300 клиентов)

Использование метрик оценки

Согласно таблице 2 статистики:

Ключевые выводы:

• Оценка производительности практически универсальна, но оценка согласованности серьёзно недостаточна
• Тестирование разделения сети встречается намного реже, чем тестирование сбоев узлов
• Оценка масштабируемости обычно сосредоточена только на количестве серверов, игнорируя расширение по регионам

Результаты экспериментов (результаты исследования)

Основной вывод 1: Несогласованное использование параметров рабочей нагрузки

Согласно анализу таблицы 3:

Соотношение чтения/записи

• 100% операций записи: Multi-Paxos, E-Paxos, Hybrid-Paxos (фокус на конфликтующих командах)
• Изменение от 0 до 100%: ZooKeeper, WanKeeper (демонстрация различных сценариев)
• Фиксированное соотношение: COPS (50% записи), PNUTS (10% записи)
• Не указано: Raft, FPaxos и несколько других систем

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

Перекрытие доступа к данным

• 100% перекрытие: Mencius, E-Paxos, Hybrid-Paxos (наихудший случай)
• Изменение от 0 до 100%: WanKeeper, Boki, FlexLog
• Не оценивается: большинство систем с единственным лидером (так как влияние на производительность минимально)

Ключевое понимание: производительность систем с несколькими лидерами сильно зависит от перекрытия доступа, но оценка часто игнорируется

Локальность доступа

• Оценённые системы: M2 Paxos (0-100%), WPaxos (70-90%), COPS (0-100%)
• Не оценивается: большинство систем
• Значимость: огромное влияние на системы, использующие механизмы владения

Количество объектов

• Указанные системы: Mencius (16-1024), M2 Paxos (1-1000), Omni-Paxos (500-50K)
• Большинство не указано: ограничивает понимание степени конфликтов

Размер объектов

• Малые объекты: 6B-1KB (CPU-интенсивная рабочая нагрузка)
• Большие объекты: 1KB-8KB (сетевая интенсивная рабочая нагрузка)
• Диапазон изменения: Mencius (6B-4KB), SplitFT (128B-8KB)

Основной вывод 2: Разнообразные методы оценки масштабируемости

Масштабируемость рабочей нагрузки:

• Hybrid-Paxos, E-Paxos: увеличение количества одновременных клиентов
• WPaxos: регулировка ограничения пропускной способности клиентов
• Большинство систем: тестирование до точки насыщения

Масштабируемость системы:

• Горизонтальное расширение: ZooKeeper (3-13 реплик), Calvin (4-100 реплик)
• Расширение по регионам: E-Paxos и Mencius (3-7 регионов)
• Вертикальное расширение: M2 Paxos (изменение производительности CPU)

Проблема: отсутствие единого метода тестирования масштабируемости затрудняет сравнение различных систем

Основной вывод 3: Серьёзная недостаточность оценки согласованности

Текущие практики:

• Инструменты тестирования: Bizur использует Serialla, Multi-Paxos использует проверку контрольной суммы
• Тестирование Jepsen: ZooKeeper, CockroachDB (проверка линеаризуемости)
• Тестирование Elle: ScalarDB (проверка строгой сериализуемости)
• Измерение устаревания: ZooNet, PNUTS, BG (но не может доказать строгую согласованность)

Основные проблемы:

• Большинство систем заявляют о "строгой согласованности", но определение неясно
• Отсутствует систематизированный метод проверки согласованности
• Измерение устаревания недостаточно для проверки линеаризуемости или сериализуемости

Основной вывод 4: Оценка доступности сосредоточена на сбоях при крахе

Согласно таблице 4:

Типы сбоев:

• Крах узла: наиболее распространён (14/30 систем)
• Разделение сети: менее распространено (5/30 систем)
• Другие сбои: дрейф часов, повреждение памяти и т.д. практически не тестируются

Количество сбоев:

• Сбой одного узла: большинство систем
• Сбой нескольких узлов: ZooKeeper (2 follower), Omni-Paxos (1-2 узла)

Методы тестирования:

• Измерение деградации пропускной способности во время сбоя
• Spanner: крах целого региона, но группа Paxos остаётся доступной
• Hybrid-Paxos: увеличение количества реплик для тестирования повышения доступности

Связанные работы

Тестирование распределённых систем

Тесты баз данных NoSQL:

• YCSB (2010): наиболее популярный тест NoSQL, но не поддерживает распределённых клиентов и WAN-сценариев
• YCSB+T (2014): добавляет поддержку транзакций, но остаётся однопроцессным
• YCSB++ (2011): поддерживает распределённых клиентов, но зависит от синхронизации ZooKeeper, не подходит для WAN

Тесты, специфичные для приложений:

• BG (2013): рабочая нагрузка социальной сети, но использует блокировки для избежания конфликтов
• TPC-C (1992): стандарт обработки транзакций, но не предназначен для сервисов координации
• HiBench (2010): тест Hadoop, не подходит для систем координации

Тесты больших данных:

• BigDataBench (2014): охватывает различные рабочие нагрузки больших данных
• Но все они не подходят для оценки специфических требований сервисов координации (согласованность, отказоустойчивость, географическое распределение)

Инструменты тестирования согласованности

Jepsen (2013-настоящее время):

• Мощная структура для тестирования согласованности
• Может обнаруживать нарушения линеаризуемости
• Но требует глубокого понимания инструмента, не является чёрным ящиком

Elle (2020):

• Основана на Jepsen, более эффективное обнаружение уровней изоляции
• Построение графа зависимостей транзакций для выявления нарушающих циклов
• Всё ещё требует настройки рабочей нагрузки

Другие инструменты тестирования:

• Serialla: используется Bizur для тестирования строгой сериализуемости
• UPB (2013): тест доступности, основанный на YCSB

Исследования распределённых систем

Оценка облачных сервисов:

• Оценка эластичности, вычислительные возможности, анализ рентабельности
• Но не предназначены для сервисов координации

Файловые системы и хранилища данных:

• Тестирование распределённых файловых систем
• Оценка производительности запросов хранилищ данных
• Отличаются от требований систем координации

Обзоры сервисов координации:

• Сравнение алгоритмов (варианты Paxos)
• Анализ характеристик сервисов
• Уникальность данной работы: первый систематический анализ практик оценки и требований к инструментам тестирования

Выводы и обсуждение

Основные выводы

1. Фрагментация практик оценки: из 30 систем только 7 используют стандартные тесты (YCSB, TPC-C, Jepsen), большинство используют пользовательские микротесты
2. Неравномерное покрытие метриками:
   • Оценка производительности универсальна (93% систем)
   • Оценка согласованности недостаточна (27% систем)
   • Тестирование разделения сети редко (17% систем)
3. Несогласованное использование параметров:
   • Критические параметры (локальность доступа, перекрытие доступа к данным) часто игнорируются
   • Отсутствует стандартизация конфигурации параметров
   • Затруднено справедливое сравнение различных систем
4. Недостаточность существующих инструментов:
   • YCSB: не поддерживает распределённых клиентов, WAN-сценариев, локальности доступа
   • TPC-C: не предназначен для сервисов координации
   • Jepsen: не является чёрным ящиком, сложен в применении
   • Ни один инструмент не удовлетворяет всем требованиям
5. 7 основных требований к инструментам тестирования:
   • Гибкость и сложность (поддержка многомерной оптимизации параметров)
   • Поддержка WAN-систем (географическое распределение, неравномерная задержка)
   • Масштабируемость (распределённое создание нагрузки)
   • Простота применения (чёрный ящик, независимость от языка)
   • Тестирование производительности (пропускная способность, задержка, хвостовая задержка)
   • Проверка согласованности (линеаризуемость, сериализуемость)
   • Внедрение сбоев (крах, разделение, дрейф часов)

Ограничения

1. Охват выборки: хотя охватывает 30 систем, может пропустить некоторые новые системы или координационные сервисы специального назначения
2. Актуальность: распределённые системы быстро развиваются, постоянно появляются новые практики оценки и инструменты
3. Глубина анализа: анализ практик оценки каждой системы основан на открытых статьях, может не охватывать все детали реализации
4. Реализация инструментов: работа выявляет требования, но не реализует полный инструмент тестирования
5. Модели согласованности: различные системы определяют "строгую согласованность" по-разному, затруднено установление единого стандарта оценки

Направления будущих исследований

1. Разработка стандартизированного инструмента тестирования:
   • Поддержка распределённых клиентов и WAN-сценариев
   • Гибкая конфигурация параметров
   • Интеграция возможностей проверки согласованности
   • Поддержка различных типов внедрения сбоев
2. Установление стандартов оценки:
   • Определение минимального набора необходимых метрик оценки
   • Стандартизация конфигурации параметров рабочей нагрузки
   • Разработка протокола проверки согласованности
3. Расширение области исследования:
   • Включение новых протоколов координации (например, на основе DAG)
   • Анализ практик оценки алгоритмов консенсуса блокчейна
   • Исследование требований координации в сценариях граничных вычислений
4. Эмпирические исследования:
   • Переоценка существующих систем с использованием стандартных инструментов
   • Количественное определение влияния различных параметров на производительность
   • Проверка заявленных гарантий согласованности
5. Автоматизация тестирования:
   • Разработка автоматизированных инструментов проверки согласованности
   • Интеграция с непрерывной интеграцией/непрерывным развёртыванием (CI/CD)
   • Поддержка регрессионного тестирования

Глубокая оценка

Преимущества

1. Систематичность и полнота

• Широта: охватывает 30 систем, охватывающих 20 лет истории исследований (Paxos 1998 - новейшие системы 2024)
• Глубина: детальный анализ экспериментальной установки, топологии, метрик, параметров
• Ясная классификация: трёхуровневая классификация (алгоритм-сервис-приложение) + 6 типов топологии

2. Высокая практическая ценность

• Рекомендации: предоставляет разработчикам лучшие практики оценки
• Ясные требования: 7 требований к инструментам тестирования имеют практическую применимость
• Ориентация на проблемы: чётко указывает конкретные недостатки существующих инструментов

3. Богатые данные

• 3 комплексные таблицы: таблица 1 (экспериментальная установка), таблица 2 (использование метрик), таблица 3 (параметры рабочей нагрузки)
• Количественный анализ: охват метрик, частота использования параметров
• Визуализация: чёткие диаграммы 6 типов топологии

4. Объективность и нейтральность

• Не отдаёт предпочтение конкретным системам или инструментам тестирования
• Справедливый анализ преимуществ и недостатков каждого инструмента
• Оценка основана на фактах, а не на субъективных суждениях

5. Академическая строгость

• Ссылки на 85 источников
• Ясная методология (критерии выбора, структура анализа)
• Выводы подкреплены достаточными данными

Недостатки

1. Отсутствие количественного сравнения

• Не предоставляет данные о различиях в производительности между методами оценки
• Отсутствует количественное определение влияния выбора параметров на результаты
• Нет статистического анализа (корреляция, проверка значимости)

2. Недостаточная проверка реализации

• Не разработан инструмент тестирования, удовлетворяющий требованиям
• Отсутствует экспериментальная проверка осуществимости предложенных требований
• Нет оценки прототипной системы

3. Поверхностный анализ оценки согласованности

• Недостаточно глубокое обсуждение различий между моделями согласованности
• Отсутствует конкретная методология проверки согласованности
• Нет анализа сложности тестирования согласованности

4. Ограниченный анализ WAN-сценариев

• Хотя подчёркивается важность WAN, конкретный анализ недостаточен
• Не подробно обсуждаются влияния различных моделей географического распределения
• Отсутствует обсуждение специальных вызовов развёртывания между облаками и континентами

5. Недостаточное покрытие новых тенденций

• Алгоритмы консенсуса блокчейна не рассмотрены
• Требования координации в сценариях граничных вычислений не обсуждаются
• Оценка систем машинного обучения с координацией не затронута

6. Недостаточные рекомендации по воспроизводимости

• Отсутствуют подробные рекомендации по воспроизведению экспериментов
• Нет открытых наборов данных или скриптов оценки
• Не обсуждается обеспечение воспроизводимости оценки

Влияние

1. Академический вклад

• Заполнение пробела: первый систематический анализ практик оценки систем распределённой координации
• Теоретическая ценность: установление структуры оценки и системы требований
• Потенциал цитирования: может стать справочным материалом для методологии оценки в этой области

2. Практическая ценность

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

3. Ограничения

• Отсутствие реализации: не предоставляет готовый инструмент для непосредственного использования
• Недостаточная проверка: осуществимость требований не подтверждена эмпирически
• Необходимость обновления: быстро развивающаяся область требует постоянного обновления

4. Область применения

• Прямое применение: исследователи и инженеры систем распределённой координации
• Косвенное применение: разработчики распределённых баз данных, блокчейна, облачных систем
• Образовательная ценность: может использоваться как справочный материал в курсах распределённых систем

Применимые сценарии

1. Исследовательские сценарии

• Разработка новых протоколов: использование контрольного списка требований при проектировании плана оценки
• Сравнение систем: выбор подходящих метрик и параметров для справедливого сравнения
• Написание статей: ссылка на стандартные практики оценки повышает достоверность

2. Инженерные сценарии

• Выбор системы: понимание результатов оценки различных систем и их ограничений
• Оптимизация производительности: выявление критических параметров, влияющих на производительность
• Тестирование отказоустойчивости: проектирование комплексного плана тестирования доступности

3. Образовательные сценарии

• Преподавание курсов: введение методологии оценки распределённых систем
• Практические проекты: руководство для студентов при проектировании экспериментов и планов оценки
• Обзор литературы: понимание современного состояния исследований в этой области

4. Сценарии стандартизации

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

Избранные ссылки

Классические алгоритмы консенсуса

1. Lamport, L. (1998). The part-time parliament. ACM TOCS - оригинальная статья Paxos
2. Ongaro, D. & Ousterhout, J. (2014). In search of an understandable consensus algorithm. USENIX ATC - алгоритм Raft

Сервисы координации

3. Hunt, P. et al. (2010). ZooKeeper: Wait-free coordination for internet-scale systems. USENIX ATC
4. Balakrishnan, M. et al. (2013). Tango: Distributed data structures over a shared log. SOSP

Инструменты тестирования

5. Cooper, B.F. et al. (2010). Benchmarking cloud serving systems with YCSB. SoCC
6. Kingsbury, K. (2024). Jepsen tests - структура тестирования согласованности
7. Kingsbury, K. & Alvaro, P. (2020). Elle: Inferring Isolation Anomalies from Experimental Observations

Оптимизация WAN

8. Ailijiang, A. et al. (2017). Multileader WAN Paxos: Ruling the archipelago with fast consensus - WPaxos
9. Mao, Y. et al. (2008). Mencius: Building efficient replicated state machines for WANs. OSDI

Распределённые приложения

10. Corbett, J.C. et al. (2013). Spanner: Google's globally distributed database. ACM TOCS

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