Почему ClickHouse такой быстрый?

Помимо способа организации данных, на производительность базы данных влияет множество других факторов. Далее мы подробнее объясним, что делает ClickHouse таким быстрым, особенно по сравнению с другими столбцовыми базами данных. С архитектурной точки зрения базы данных состоят (как минимум) из уровня хранения и уровня обработки запросов. Уровень хранения отвечает за сохранение, загрузку и поддержку данных таблиц, а уровень обработки запросов выполняет пользовательские запросы. По сравнению с другими базами данных ClickHouse предлагает нововведения на обоих уровнях, которые обеспечивают чрезвычайно быструю вставку и выполнение запросов SELECT. В ClickHouse каждая таблица состоит из нескольких «частей таблицы». Часть создаётся каждый раз, когда пользователь вставляет данные в таблицу (оператор INSERT). Запрос всегда выполняется по всем частям таблицы, существующим на момент его запуска. Чтобы не допустить накопления слишком большого числа частей, ClickHouse в фоновом режиме выполняет операцию слияния, которая непрерывно объединяет несколько меньших частей в одну более крупную. У этого подхода есть несколько преимуществ: всю обработку данных можно перенести в фоновые слияния частей, сохранив запись данных лёгкой и высокоэффективной. Отдельные вставки являются «локальными» в том смысле, что им не нужно обновлять глобальные, то есть общие для всей таблицы, структуры данных. В результате нескольким одновременным вставкам не требуется ни взаимная синхронизация, ни синхронизация с существующими данными таблицы, поэтому вставки можно выполнять почти со скоростью дискового ввода-вывода. 🤿 Подробнее об этом см. в разделе On-Disk Format в веб-версии нашей статьи VLDB 2024. Вставки полностью изолированы от запросов SELECT, а слияние вставленных частей данных происходит в фоновом режиме и не влияет на одновременные запросы. 🤿 Подробности см. в разделе Storage Layer в веб-версии нашей статьи для VLDB 2024. В отличие от других баз данных, в ClickHouse запись данных остаётся простой и эффективной, поскольку все дополнительные преобразования данных выполняются во время фонового процесса слияния. Например:

• Replacing merges сохраняют только самую свежую версию строки во входных частях и отбрасывают все остальные версии. Replacing merges можно рассматривать как операцию очистки при слиянии.
• Aggregating merges объединяют промежуточные состояния агрегации во входной части в новое состояние агрегации. Хотя это может звучать сложно, на практике это просто реализует инкрементальную агрегацию.
• TTL (time-to-live) merges сжимают, перемещают или удаляют строки на основе определённых правил, завязанных на времени.

Смысл этих преобразований в том, чтобы перенести работу (вычисления) с момента выполнения пользовательских запросов на время слияния. Это важно по двум причинам: С одной стороны, пользовательские запросы могут выполняться значительно быстрее — иногда в 1000 раз и более, — если используют «преобразованные» данные, например предварительно агрегированные. С другой стороны, большая часть времени выполнения слияний уходит на загрузку входных частей и сохранение выходной части. Дополнительные затраты на преобразование данных во время слияния обычно не слишком сильно влияют на время выполнения слияний. Вся эта магия полностью прозрачна и не влияет на результаты запросов (кроме их производительности). 🤿 Подробнее об этом — в разделе Merge-time Data Transformation в web version нашей статьи для VLDB 2024. На практике многие запросы повторяются, то есть выполняются без изменений или лишь с небольшими изменениями (например, с другими значениями параметров) через регулярные промежутки времени. Повторное выполнение одинаковых или похожих запросов позволяет добавлять индексы или реорганизовывать данные так, чтобы часто используемые запросы могли обращаться к ним быстрее. Этот подход также известен как «отсечение данных», и ClickHouse предоставляет для этого три метода:

1. Индексы первичного ключа, которые определяют порядок сортировки данных таблицы. Правильно выбранный первичный ключ позволяет применять фильтры (например, предложение WHERE в приведённом выше запросе) с помощью быстрого двоичного поиска вместо полного сканирования столбцов. Говоря более технически, время выполнения сканирования становится логарифмическим, а не линейным относительно объёма данных.
2. Проекции таблиц — альтернативные внутренние версии таблицы, хранящие те же данные, но отсортированные по другому первичному ключу. Проекции могут быть полезны, когда часто используется несколько условий фильтрации.
3. Индексы пропуска данных, которые сохраняют для столбцов дополнительную статистику, например минимальное и максимальное значение столбца, набор уникальных значений и т. д. Индексы пропуска данных дополняют первичные ключи и проекции таблиц и, в зависимости от распределения данных в столбце, могут значительно ускорить применение фильтров.

Все три метода направлены на то, чтобы пропускать как можно больше строк при полном чтении столбцов, потому что самый быстрый способ прочитать данные — вообще их не читать. 🤿 Подробнее об этом — в разделе Отсечение данных в веб-версии нашей статьи VLDB 2024. Кроме того, на уровне хранения ClickHouse сырые табличные данные также могут дополнительно сжиматься с помощью различных кодеков. Столбцовые хранилища особенно хорошо подходят для такого сжатия, поскольку значения одного типа и с одинаковым распределением данных хранятся рядом. Пользователи могут указать, что столбцы нужно сжимать с помощью различных универсальных алгоритмов сжатия (например, ZSTD) или специализированных кодеков, например Gorilla и FPC для значений с плавающей точкой, Delta и GCD для целочисленных значений, или даже AES в качестве шифрующего кодека. Сжатие данных не только уменьшает объем хранилища, занимаемый таблицами базы данных, но и во многих случаях повышает производительность запросов, поскольку локальные диски и сетевой ввод-вывод часто ограничены низкой пропускной способностью. 🤿 Подробнее об этом — в разделе On-Disk Format в веб-версии нашей статьи для VLDB 2024. Наконец, ClickHouse использует векторизованный уровень обработки запросов, который максимально распараллеливает выполнение запросов, чтобы задействовать все ресурсы и обеспечить максимальную скорость и эффективность. «Векторизация» означает, что операторы плана запроса передают промежуточные результирующие строки батчами, а не по одной строке. Это позволяет эффективнее использовать кэши процессора и применять SIMD-инструкции для одновременной обработки нескольких значений. Более того, многие операторы существуют в нескольких версиях - по одной для каждого поколения наборов SIMD-инструкций. ClickHouse автоматически выбирает самую новую и быструю версию в зависимости от возможностей оборудования, на котором он работает. Современные системы имеют десятки процессорных ядер. Чтобы задействовать все ядра, ClickHouse разбивает план запроса на несколько параллельных потоков, обычно по одному на ядро. Каждый поток обрабатывает непересекающийся диапазон данных таблицы. Благодаря этому производительность базы данных масштабируется «вертикально» вместе с количеством доступных ядер. Если одного узла уже недостаточно для хранения данных таблицы, можно добавить новые узлы и сформировать кластер. Таблицы можно разделить на сегменты («sharded») и распределить по узлам. ClickHouse будет выполнять запросы на всех узлах, где хранятся данные таблицы, и тем самым масштабироваться «горизонтально» вместе с количеством доступных узлов. 🤿 Подробнее об этом читайте в разделе Query Processing Layer в веб-версии нашей статьи VLDB 2024.

“ClickHouse — это просто безумная система: у вас тут 20 версий хеш-таблицы. У вас есть все эти невероятные штуки, тогда как в большинстве систем будет одна хеш-таблица … у ClickHouse такая впечатляющая производительность именно потому, что в нём есть все эти специализированные компоненты” Andy Pavlo, профессор баз данных в CMU

ClickHouse выделяет именно скрупулёзное внимание к низкоуровневой оптимизации. Создать базу данных, которая просто работает, — это одно, но спроектировать её так, чтобы она обеспечивала высокую скорость для самых разных типов запросов, структур данных, распределений данных и конфигураций индексов, — вот где проявляется мастерство “безумной системы”. Хеш-таблицы. Возьмём в качестве примера хеш-таблицу. Хеш-таблицы — это ключевые структуры данных, лежащие в основе JOIN и агрегаций. С точки зрения программиста здесь нужно учитывать следующие проектные решения:

• Какую хеш-функцию выбрать,
• Как разрешать коллизии: открытая адресация или цепочки,
• Структура памяти: один массив для ключей и значений или отдельные массивы?
• Коэффициент заполнения: когда и как менять размер? Как перемещать значения при изменении размера?
• Удаление: должна ли хеш-таблица поддерживать вытеснение записей?

Обычная хеш-таблица из сторонней библиотеки функционально работала бы, но быстрой она бы не была. Высокая производительность требует тщательного бенчмаркинга и экспериментов. В реализации хеш-таблиц в ClickHouse выбирается один из 30+ заранее скомпилированных вариантов хеш-таблиц в зависимости от особенностей запроса и данных. Алгоритмы. То же самое касается и алгоритмов. Например, при сортировке можно учитывать следующее:

• Что будет сортироваться: числа, Tuple, строки или структуры?
• Находятся ли данные в оперативной памяти?
• Требуется ли стабильная сортировка?
• Нужно ли сортировать все данные или достаточно частичной сортировки?

Алгоритмы, учитывающие характеристики данных, часто работают лучше своих универсальных аналогов. Если эти характеристики заранее неизвестны, система может попробовать разные реализации и выбрать ту, которая лучше всего работает во время выполнения. В качестве примера см. статью о том, как в ClickHouse реализована распаковка LZ4. 🤿 Подробный разбор см. в разделе Holistic Performance Optimization в web version нашей статьи VLDB 2024. В августе 2024 года наша первая научная статья была принята и опубликована на конференции VLDB. VLDB — международная конференция по очень большим базам данных, которую широко считают одной из ведущих конференций в области управления данными. Среди сотен поданных работ доля принятых на VLDB обычно составляет около 20%. Вы можете прочитать PDF-версию статьи или её веб-версию, где кратко описаны наиболее интересные архитектурные и системные особенности ClickHouse, благодаря которым он работает так быстро. Alexey Milovidov, наш CTO и создатель ClickHouse, представил статью (слайды здесь), после чего состоялась сессия вопросов и ответов (время на неё закончилось очень быстро!). Запись выступления можно посмотреть здесь: