Оценка подхода lock-free списков

Привет от команды Greengage DB Core!

Позвольте начать с краткой исторической справки: Greengage DB был запущен в 2024 году как open-source форк Greenplum — Massively Parallel Processing (MPP) аналитической системы управления базами данных, основанной на PostgreSQL. Мы начали этот проект, чтобы поддержать open-source сообщество Greenplum, который неожиданно стал проприетарным продуктом в мае 2024 года. Мы гарантируем дальнейшее развитие Greengage DB, следуя принципам открытости и прозрачности.

Так как Greengage DB основан на PostgreSQL, он унаследовал некоторые его известные особенности и проблемы. Одна из таких проблем, особенно актуальная в распределенных средах — это проблема "брошенных файлов" (orphaned files).

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

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

Если кратко, основная идея нашего подхода такова:

Таким образом, одной из ключевых частей этой новой функциональности является эффективная и надежная передача информации о relfilenodes от множества backend-процессов к центральному процессу checkpointer. Так как все они — независимые процессы Linux, любые общие данные, такие как списки relfilenode, должны храниться в shared memory. Естественно, эти общие данные требуют надежной защиты от одновременного доступа для обеспечения целостности и согласованности.

Прямолинейный и распространенный подход к защите общих данных — это реализация классического механизма блокировок, например, с использованием мьютекса или спинлока для каждого отдельного списка. Однако важнейшей характеристикой любой высокопроизводительной OLAP СУБД является способность быстро обрабатывать огромные объемы данных. Введение частых блокировок, особенно в системе с множеством параллельных backend-процессов, может привести к значительной конкуренции, что вызывает ухудшение производительности из-за последовательной обработки и снижения параллелизма.

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

Ответ — "да", это возможно, но у такого lock-free подхода будут определенные конструктивные ограничения:

Lock-free подход вдохновлен статьей A Pragmatic Implementation of Non-Blocking Linked Lists. Из нее мы взяли идею логического удаления узла с помощью Compare-and-Swap. Мы переосмыслили подход и упростили его для модели с одним процессом записи (оригинал описывает алгоритм для нескольких) и сосредоточились на управлении удаленными узлами.

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

Процедура тестирования была спроектирована с учетом следующих ключевых требований:

С учетом этих соображений была разработана следующая синтетическая схема тестирования:

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

Следовательно, истинной целью и точкой интереса было провести сравнительный анализ, а именно: сравнить ключевые параметры lock-free реализации списка с традиционным списком на блокировках. Это сравнение проводилось на одном и том же кластере Greengage и идентичном аппаратном обеспечении, что позволило изолированно выполнить замеры производительности нашего lock-free решения по сравнению с его аналогом на блокировках. Такой подход позволяет сделать осмысленные выводы об относительной эффективности нашего решения.

Мы провели тесты производительности с разным количеством вставляемых и удаляемых элементов: 100, 1000, 5000 и 10000 записей. Для статистической надежности каждая конфигурация тестов была повторена 10 раз. Усредненные значения производительности этих запусков представлены на следующих графиках.

Как видно из приведенных графиков, с увеличением количества параллельных сессий (и, следовательно, одновременно запущенных backend-процессов) время выполнения реализации lock-free списка растет значительно более плавно по сравнению со списками, построенными на per-backend блокировках. Это указывает на лучшую масштабируемость при взаимных блокировках.

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

Описанный lock-free подход доказал свою эффективность, показав обнадеживающие результаты производительности при высоких нагрузках. Однако, учитывая, что ожидаемая нагрузка для нашей целевой функциональности невелика (как правило, хранение десятков или сотен relfilenodes, но обычно не более), мы приняли стратегическое решение по реализации этого функционала. Мы решили использовать традиционные списки с блокировками, так как они показывают сопоставимую производительность при малом количестве элементов. Этот выбор существенно повышает удобство сопровождения и снижает риск случайных поломок или неожиданных регрессий при будущих изменениях, благодаря простоте, присущей традиционному подходу.

Тем не менее, сама lock-free методология доказала свои отличные характеристики производительности, особенно при высокой конкуренции за ресурсы и больших объемах данных. Следовательно, этот подход остается сильным кандидатом для использования в будущих новых функциональных возможностях Greengage DB, где необходимо эффективно и параллельно передавать или обмениваться значительными объемами данных между различными процессами внутри сегмента, обеспечивая надежную масштабируемость и минимальные накладные расходы.

Источник: Оценка подхода lock-free списков