Обзор архитектуры

Это веб-версия нашей научной статьи VLDB 2024. Мы также вели блог о её предыстории и пути, и рекомендуем посмотреть презентацию VLDB 2024 от CTO и создателя ClickHouse, Алексея Миловидова:

АННОТАЦИЯ

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

В этой статье представлен обзор ClickHouse, популярной открытой OLAP базы данных, разработанной для высокопроизводительного анализа данных с петабайтными масштабами и высокими скоростями приема. Его уровень хранения сочетает в себе формат данных, основанный на традиционных деревьях слияния с логической структурой (LSM), с новыми методиками непрерывной трансформации (например, агрегация, архивирование) исторических данных на заднем плане. Запросы пишутся на удобном SQL диалекте и обрабатываются высококлассным векторизованным движком выполнения запросов с опциональной компиляцией кода. ClickHouse активно использует техники обрезки, чтобы избежать оценки нерелевантных данных в запросах. Другие системы управления данными могут быть интегрированы на уровне табличной функции, движка таблиц или движка базы данных. Реальные бенчмарки показывают, что ClickHouse является одной из самых быстрых аналитических баз данных на рынке.

1 ВВЕДЕНИЕ

Эта статья описывает ClickHouse, столбцовую OLAP базу данных, разработанную для высокопроизводительных аналитических запросов к таблицам с триллионами строк и сотнями столбцов. ClickHouse был запущен в 2009 году как фильтр и оператор агрегации для данных веб-логов и был открыт в 2016 году. Рисунок 1 иллюстрирует, когда основные функции, описанные в этой статье, были внедрены в ClickHouse.

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

Огромные наборы данных с высокими скоростями приема. Многие приложения, ориентированные на данные, в таких отраслях, как веб-аналитика, финансы и электронная коммерция, характеризуются огромными и постоянно растущими объемами данных. Для обработки больших наборов данных аналитические базы данных должны не только предоставлять эффективные стратегии индексирования и сжатия, но также позволяет распределять данные по нескольким узлам (масштабирование) поскольку отдельные серверы ограничены несколькими десятками терабайт хранилища. Более того, последние данные часто более актуальны для получения оперативной информации, чем исторические данные. В результате аналитические базы данных должны быть в состоянии непрерывно принимать новые данные с consistently high rates или в приливах, а также постоянно "понижать приоритет" (например, агрегация, архивирование) исторические данные без замедления параллельных отчетных запросов.
Множество одновременных запросов с ожиданием низкой задержки. Запросы можно в общем классифицировать как разовые (например, исследовательский анализ данных) или повторяющиеся (например, периодические запросы для панелей мониторинга). Чем более интерактивен случай использования, тем ниже ожидается задержка запросов, что приводит к вызовам в оптимизации и выполнении запросов. Повторяющиеся запросы дополнительно предоставляют возможность адаптировать физическую компоновку базы данных к рабочей нагрузке. В результате базы данных должны предлагать техники обрезки, которые позволяют оптимизировать частые запросы. В зависимости от приоритета запроса базы данных также должны предоставлять равный или приоритетный доступ к общим системным ресурсам, таким как CPU, память, диск и ввод-вывод сети, даже если большое количество запросов выполняется одновременно.
Разнообразные ландшафты хранилищ данных, местоположения и форматы. Чтобы интегрироваться с существующими архитектурами данных, современные аналитические базы данных должны демонстрировать высокую степень открытости для чтения и записи внешних данных в любой системе, местоположении или формате.
Удобный язык запросов с поддержкой анализа производительности. Реальное использование OLAP баз данных ставит дополнительные "мягкие" требования. Например, вместо узкоспециализированного языка программирования пользователи часто предпочитают взаимодействовать с базами данных с помощью выразительного SQL диалекта с вложенными типами данных и широким спектром обычных, агрегатных и оконных функций. Аналитические базы данных также должны предоставлять сложные инструменты для анализа производительности системы или отдельных запросов.
Устойчивость уровня индустрии и возможность универсального развертывания. Поскольку обычное оборудование ненадежно, базы данных должны предоставлять репликацию данных для устойчивости к сбоям узлов. Кроме того, базы данных должны работать на любом оборудовании, начиная от старых ноутбуков и заканчивая мощными серверами. Наконец, чтобы избежать накладных расходов на сбор мусора в программах на основе JVM и обеспечить высокую производительность (например, SIMD) базы данных идеальны для развертывания как нативные бинарные файлы для целевой платформы.

Рисунок 1: Хронология ClickHouse.

2 АРХИТЕКТУРА

Рисунок 2: Архитектура ClickHouse на высоком уровне.

Как показано на Рисунке 2, движок ClickHouse разделен на три основных слоя: слой обработки запросов (описанный в разделе 4), слой хранения (раздел 3) и интеграционный слой (раздел 5). Кроме того, слой доступа управляет пользовательскими сессиями и взаимодействием с приложениями через различные протоколы. Существуют ортогональные компоненты для потоков, кэширования, контроля доступа на основе ролей, резервного копирования и непрерывного мониторинга. ClickHouse построен на C++ как единый статически скомплектованный бинарный файл без зависимостей.

Обработка запросов следует традиционному парадигме парсинга входящих запросов, построения и оптимизации логических и физических планов запросов и выполнения. ClickHouse использует векторизованную модель выполнения, аналогичную MonetDB/X100 [11], в сочетании с оппортунистической компиляцией кода [53]. Запросы могут быть написаны на функциональном SQL диалекте, PRQL [76] или Kusto's KQL [50].

Уровень хранения состоит из различных движков таблиц, которые инкапсулируют формат и местоположение данных таблицы. Движки таблиц делятся на три категории: первая категория - это семейство движков таблиц MergeTree*, которое представляет собой основной формат постоянного хранения в ClickHouse. Основанные на идее деревьев слияния LSM [60], таблицы разделяются на горизонтальные отсортированные части, которые непрерывно объединяются фоновым процессом. Отдельные движки таблиц MergeTree* отличаются по способу объединения строк из их входных частей. Например, строки могут быть агрегированы или заменены, если устарели.

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

Третья категория движков таблиц - это виртуальные движки таблиц для двустороннего обмена данными с внешними системами, такими как реляционные базы данных (например, PostgreSQL, MySQL), системы публикации/подписки (например, Kafka, RabbitMQ [24]), или хранилища ключ/значение (например, Redis). Виртуальные движки также могут взаимодействовать с озерами данных (например, Iceberg, DeltaLake, Hudi [36]) или файлами в объектных хранилищах (например, AWS S3, Google GCP).

ClickHouse поддерживает шардирование и репликацию таблиц по нескольким узлам кластера для масштабируемости и доступности. Шардирование разделяет таблицу на набор шардов таблицы в соответствии с выражением шардирования. Отдельные шарды представляют собой взаимозависимые таблицы и обычно размещаются на разных узлах. Клиенты могут читать и записывать шарды непосредственно, т.е. относиться к ним как к отдельным таблицам, или использовать специальный движок распределенной таблицы, который предоставляет глобальный обзор всех шардов таблиц. Основной целью шардирования является обработка наборов данных, превышающих объем отдельных узлов (обычно, несколько десятков терабайт данных). Другой целью шардирования является распределение нагрузки на чтение и запись для таблицы по нескольким узлам, т.е. балансировка нагрузки. Ортогонально этому, шард может быть реплицирован по нескольким узлам для обеспечения устойчивости к сбоям узлов. Для этой цели каждый движок Merge-Tree* имеет соответствующий движок ReplicatedMergeTree*, который использует схему координации с множеством мастеров на основе консенсуса Raft [59] (реализованную Keeper, заменой Apache Zookeeper, написанной на C++), чтобы гарантировать, что каждый шард всегда имеет настраиваемое количество реплик. Раздел 3.6 подробно обсуждает механизм репликации. В качестве примера, Рисунок 2 показывает таблицу с двумя шардами, каждый из которых реплицирован на два узла.

Наконец, движок базы данных ClickHouse может работать в локальном, облачном, автономном или встроенном режимах. В локальном режиме пользователи настраивают ClickHouse локально как один сервер или многонодный кластер с шардированием и/или репликацией. Клиенты общаются с базой данных через нативные, бинарные протоколы MySQL, PostgreSQL или HTTP REST API. Облачный режим представлен ClickHouse Cloud, полностью управляемым и автоматическим DBaaS предложением. Хотя эта статья сосредоточена на локальном режиме, мы планируем описать архитектуру ClickHouse Cloud в следующей публикации. Автономный режим превращает ClickHouse в утилиту командной строки для анализа и трансформации файлов, что делает его SQL-альтернативой для Unix инструментов, таких как cat и grep. Хотя это не требует предварительной настройки, автономный режим ограничен одним сервером. В последнее время был разработан встроенный режим под названием chDB [15] для интерактивных случаев анализа данных, таких как Jupyter notebooks [37] с Pandas dataframe [61]. Вдохновленный DuckDB [67], chDB встраивает ClickHouse как высокопроизводительный OLAP движок в хост-процесс. По сравнению с другими режимами, это позволяет эффективно передавать исходные и результирующие данные между движком базы данных и приложением без копирования, так как они работают в одном адресном пространстве.

3 УРОВЕНЬ ХРАНЕНИЯ

Этот раздел обсуждает движки таблиц MergeTree* как собственный формат хранения ClickHouse. Мы описываем их представление на диске и обсуждаем три техники обрезки данных в ClickHouse. Далее мы представляем стратегии слияния, которые непрерывно трансформируют данные, не влияя на параллельные вставки. Наконец, мы объясняем, как реализуются обновления и удаления, а также дедупликация данных, репликация данных и соблюдение ACID.

3.1 Формат на диске

Каждая таблица в движке таблиц MergeTree* организована как коллекция неизменяемых частей таблицы. Часть создается всякий раз, когда в таблицу вставляется набор строк. Части являются самодостаточными в том смысле, что они включают все метаданные, необходимые для интерпретации их содержимого без дополнительных запросов к центральному каталогу. Чтобы сохранить низкое количество частей на таблицу, фоновая задача слияния периодически объединяет несколько меньших частей в большую часть, пока не будет достигнут настраиваемый размер части (по умолчанию 150 ГБ). Поскольку части сортируются по первичным ключевым столбцам таблицы (см. Раздел 3.2), для слияния используется эффективная k-ходовая сортировка слияния [40]. Исходные части помечаются как неактивные и, в конечном итоге, удаляются, как только их количество ссылок падает до нуля, т.е. больше нет запросов, которые читают из них.

Строки могут быть вставлены в двух режимах: в режиме синхронной вставки каждое выражение INSERT создает новую часть и добавляет её в таблицу. Чтобы минимизировать накладные расходы на слияния, клиентам базы данных рекомендуется вставлять кортежи оптом, например, по 20 000 строк за раз. Однако задержки, вызванные пакетированием на стороне клиента, часто неприемлемы, если данные должны анализироваться в реальном времени. Например, случаи использования наблюдаемости часто включают тысячи агентов мониторинга, которые непрерывно отправляют небольшие объемы данных событий и метрик. Такие сценарии могут использовать режим асинхронной вставки, в котором ClickHouse буферизует строки из нескольких входящих INSERT в одну и ту же таблицу и создает новую часть только после того, как размер буфера превысит настраиваемый порог или истечет время ожидания.

Рисунок 3: Вставки и слияния для таблиц движка MergeTree*.

Рисунок 3 иллюстрирует четыре синхронные и две асинхронные вставки в таблицу движка MergeTree*. Два слияния сократили количество активных частей с первоначальных пяти до двух.

В отличие от LSM-деревьев [58] и их реализации в различных базах данных [13, 26, 56], ClickHouse рассматривает все части как равные, а не организует их в иерархию. В результате слияния больше не ограничены частями в одном уровне. Поскольку это также отказывается от неявного хронологического порядка частей, требуются альтернативные механизмы для обновлений и удалений, не основанные на милостях (см. Раздел 3.4). ClickHouse записывает вставки непосредственно на диск, в то время как другие LSM-деревья обычно используют ведение журнала (см. Раздел 3.7).

Часть соответствует каталогу на диске, содержащему один файл для каждого столбца. В качестве оптимизации, столбцы маленькой части (меньше 10 МБ по умолчанию) хранятся последовательно в одном файле, чтобы увеличить пространственную локальность для чтения и записи. Строки части дополнительно логически делятся на группы по 8192 записи, называемые гранулами. Гранула представляет собой наименьшую неделимую единицу данных, обрабатываемую операторами сканирования и поиска индексов в ClickHouse. Чтения и записи данных на диске, однако, не выполняются на уровне гранул, а на уровне блоков, которые объединяют несколько соседних гранул в одном столбце. Новые блоки формируются на основе настраиваемого размера в байтах на блок (по умолчанию 1 МБ), т.е. количество гранул в блоке переменное и зависит от типа данных и распределения столбца. Блоки дополнительно сжимаются, чтобы уменьшить их размер и накладные расходы на ввод-вывод. По умолчанию ClickHouse использует LZ4 [75] в качестве алгоритма сжатия общего назначения, но пользователи также могут указывать специализированные кодеки, такие как Gorilla [63] или FPC [12] для данных с плавающей точкой. Алгоритмы сжатия также могут быть связаны. Например, возможно сначала уменьшить логическую избыточность в числовых значениях, используя дельта-кодирование [23], затем выполнить тяжелое сжатие, а затем зашифровать данные с использованием кодека AES. Блоки распаковываются на лету при загрузке с диска в память. Чтобы обеспечить быстрый случайный доступ к отдельным гранулам, несмотря на сжатие, ClickHouse дополнительно хранит для каждого столбца отображение, которое ассоциирует каждый идентификатор гранулы с смещением её содержащего сжатого блока в файле столбца и смещением гранулы в распакованном блоке.

Столбцы также могут быть закодированы в словарном формате [2, 77, 81] или быть нулевыми, используя два специальных типа оберток: LowCardinality(T) заменяет оригинальные значения столбца целыми идентификаторами и таким образом значительно сокращает накладные расходы на хранение для данных с небольшими уникальными значениями. Nullable(T) добавляет внутренний битмап к столбцу T, представляя, являются ли значения столбца NULL или нет.

Наконец, таблицы могут быть разделены на диапазоны, хеши или кругом с использованием произвольных выражений разбиения. Чтобы включить обрезку разбиения, ClickHouse дополнительно хранит минимальные и максимальные значения выражения разбиения для каждого раздела. Пользователи могут дополнительно создавать более сложную статистику по столбцам (например, статистика HyperLogLog [30] или t-дополнение [28]), которые также предоставляют оценки кардинальности.

3.2 Обрезка данных

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

Во-первых, пользователи могут определить индекс первичного ключа для таблицы. Первичные ключевые столбцы определяют порядок сортировки строк внутри каждой части, т.е. индекс локально сгруппирован. ClickHouse дополнительно хранит для каждой части отображение значений столбцов первичного ключа первой строки каждой гранулы на идентификатор гранулы, т.е. индекс разреженный [31]. Получившаяся структура данных обычно достаточно мала, чтобы оставаться полностью в памяти, например, только 1000 записей необходимо для индексирования 8,1 миллиона строк. Основная цель первичного ключа - оценивать предикаты равенства и диапазона для часто фильтруемых столбцов с использованием двоичного поиска вместо последовательных сканирований (Раздел 4.4). Локальная сортировка также может быть использована в процессе слияния частей и оптимизации запросов, например, для агрегации на основе сортировки или чтобы убрать операторы сортировки из физического плана выполнения, когда столбцы первичного ключа формируют префикс сортировочных столбцов.

Рисунок 4 показывает индекс первичного ключа по столбцу EventTime для таблицы со статистикой показов страниц. Гранулы, которые соответствуют диапазону предикатов в запросе, могут быть найдены путем двоичного поиска по индексу первичного ключа вместо последовательного сканирования EventTime.

Рисунок 4: Оценка фильтров с индексом первичного ключа.

Во-вторых, пользователи могут создавать проекции таблиц, т.е. альтернативные версии таблицы, которые содержат те же строки, отсортированные по другому первичному ключу [71]. Проекции позволяют ускорить запросы, которые фильтруют по столбцам, отличным от первичного ключа главной таблицы, за счет увеличения накладных расходов на вставку, слияние и потребление пространства. По умолчанию проекции заполняются лениво, только из частей, недавно вставленных в главную таблицу, но не из существующих частей, если пользователь не материализует проекцию полностью. Оптимизатор запросов выбирает между чтением из главной таблицы и проекции на основе оценок затрат ввода-вывода. Если проекция не существует для части, выполнение запроса возвращается к соответствующей главной части таблицы.

В-третьих, индексы пропуска предоставляют легковесную альтернативу проекциям. Идея индексов пропуска заключается в том, чтобы хранить небольшие объемы метаданных на уровне нескольких последовательных гранул, что позволяет избежать сканирования нерелевантных строк. Индексы пропуска могут быть созданы для произвольных выражений индекса и с использованием настраиваемой постепенности, т.е. количество гранул в блоке индекса пропуска. Доступные типы индексов пропуска включают: 1. Индексы мин-макс [51], хранящие минимальные и максимальные значения выражения индекса для каждого блока индекса. Этот тип индекса хорошо работает для локально сгруппированных данных с малыми абсолютными диапазонами, т.е. слабо отсортированными данными. 2. Индексы набора, хранящие настраиваемое количество уникальных значений блоков индекса. Эти индексы лучше всего использовать с данными с малой локальной кардинальностью, т.е. "собранными вместе" значениями. 3. Индексы фильтров Блума [9], созданные для строк, токенов или значений n-грамм с настраиваемой долей ложных срабатываний. Эти индексы поддерживают текстовый поиск [73], но в отличие от индексов мин-макс и набора, они не могут использоваться для диапазонных или отрицательных предикатов.

3.3 Преобразование данных во время слияния

Случаи бизнес-аналитики и наблюдаемости часто требуют обработки данных, генерируемых на постоянно высоких скоростях или в приливах. Кроме того, недавно сгенерированные данные обычно более актуальны для значимых аналитических инсайтов в реальном времени, чем исторические данные. Такие случаи использования требуют от баз данных поддерживать высокие скорости приема данных, одновременно непрерывно уменьшая объем исторических данных с помощью таких техник, как агрегация или старение данных. ClickHouse позволяет непрерывное инкрементальное преобразование существующих данных с использованием различных стратегий слияния. Преобразование данных во время слияния не компрометирует производительность заявлений INSERT, но оно не может гарантировать, что таблицы никогда не содержат нежелательных (например, устаревших или не агрегированных) значений. Если необходимо, все трансформации во время слияния могут быть применены во время выполнения запроса, указав ключевое слово FINAL в заявлениях SELECT.

Замена слияний сохраняет только наиболее недавно вставленную версию кортежа на основе временной метки создания его содержащей части, более старые версии удаляются. Кортежи считаются эквивалентными, если у них одинаковые значения столбцов первичного ключа. Для явного контроля над тем, какой кортеж сохраняется, также возможно указать специальный столбец версии для сравнения. Замена слияний обычно используется как механизм обновления во время слияния (обычно в случаях использования, где обновления часты), либо как альтернатива дедупликации данных во время вставки (Раздел 3.5).

Агрегационные слияния сворачивают строки с равными значениями столбцов первичного ключа в одну агрегированную строку. Не первичные ключевые столбцы должны находиться в частичном состоянии агрегации, которое содержит сводные значения. Два частичных состояния агрегации, например, сумма и количество для avg(), комбинируются в новое частичное состояние агрегации. Агрегационные слияния обычно используются в материализованных представлениях вместо обычных таблиц. Материализованные представления заполняются на основе трансформационного запроса против исходной таблицы. В отличие от других баз данных, ClickHouse не обновляет материализованные представления периодически с полным содержимым исходной таблицы. Вместо этого материализованные представления обновляются инкрементально с результатом трансформационного запроса, когда новая часть вставляется в исходную таблицу.

Рисунок 5 показывает материализованное представление, определенное для таблицы со статистикой показов страниц. Для новых частей, вставленных в исходную таблицу, трансформационный запрос рассчитывает максимальные и средние задержки, сгруппированные по регионам, и вставляет результат в материализованное представление. Агрегационные функции avg() и max() с расширением -State возвращают частичные состояния агрегации вместо фактических результатов. Агрегационное слияние, определенное для материализованного представления, непрерывно комбинирует частичные состояния агрегации в разных частях. Чтобы получить окончательный результат, пользователи консолидации частичных состояний агрегации в материализованном представлении, используя avg() и max() с -Merge расширением.

Рисунок 5: Агрегационные слияния в материализованных представлениях.

Слияния TTL (времени жизни) обеспечивают старение для исторических данных. В отличие от удаления и агрегационных слияний, слияния TTL обрабатывают только одну часть за раз. Слияния TTL определяются в терминах правил с триггерами и действиями. Триггер - это выражение, вычисляющее временную метку для каждой строки, которая сравнивается с временем, в которое выполняется слияние TTL. Хотя это позволяет пользователям контролировать действия на уровне строки, мы нашли достаточно проверить, удовлетворяют ли все строки данному условию и выполнить действие на всей части. Возможные действия включают 1. перемещение части на другое хранилище (например, более дешевое и медленное), 2. повторное сжатие части (например, с использованием более тяжелого кодека), 3. удаление части, и 4. сводка, т.е. агрегация строк с использованием ключа группировки и агрегатных функций.

В качестве примера рассмотрим определение таблицы логирования в Списке 1. ClickHouse переместит части со значениями временной метки столбца старше одной недели в медленное, но дешевое объектное хранилище S3.

Список 1: Переместить часть в объектное хранилище через неделю.

3.4 Обновления и удаления

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

Мутации переписывают все части таблицы на месте. Чтобы предотвратить временное удвоение размера таблицы (удаление) или столбца (обновление), эта операция не является атомарной, то есть параллельные SELECT могут читать измененные и неизмененные части. Мутации гарантируют, что данные физически изменяются в конце операции. Мутации удаления все еще дороги, так как они переписывают все столбцы во всех частях.

В качестве альтернативы, легковесные удаления просто обновляют внутренний битмап столбца, указывая, удалена ли строка или нет. ClickHouse дополняет SELECT-запросы дополнительным фильтром по битмап-столбцу, чтобы исключить удаленные строки из результата. Удаленные строки физически удаляются только рег

3.6 Репликация Данных

Репликация является необходимым условием для высокой доступности (устойчивости к сбоям узлов), но также используется для балансировки нагрузки и обновлений без простоя [14]. В ClickHouse репликация основана на концепции состояний таблицы, которые состоят из набора частей таблицы (раздел 3.1) и метаданных таблицы, таких как имена и типы столбцов. Узлы обновляют состояние таблицы с помощью трех операций: 1. Вставки добавляют новую часть в состояние, 2. слияния добавляют новую часть и удаляют существующие части из состояния, 3. мутации и DDL-выражения добавляют части, и/или удаляют части, и/или изменяют метаданные таблицы, в зависимости от конкретной операции. Операции выполняются локально на одном узле и записываются как последовательность переходов состояния в глобальном журнале репликации.

Журнал репликации поддерживается ансамблем из typically трех процессов ClickHouse Keeper, которые используют алгоритм согласия Raft [59] для обеспечения распределенного и отказоустойчивого слоя координации для кластера узлов ClickHouse. Все узлы кластера изначально указывают на одно и то же положение в журнале репликации. В то время как узлы выполняют локальные вставки, слияния, мутации и DDL-выражения, журнал репликации воспроизводится асинхронно на всех других узлах. В результате реплицированные таблицы являются только конечными согласованными, т.е. узлы могут временно считывать старые состояния таблицы, пока они сходятся к последнему состоянию. Большинство вышеупомянутых операций могут также выполняться синхронно, пока большинство узлов (например, большинство узлов или все узлы) не примут новое состояние.

В качестве примера, Рисунок 6 показывает изначально пустую реплицированную таблицу в кластере из трех узлов ClickHouse. Узел 1 сначала получает два оператора вставки и записывает их ( 1 2 ) в журнал репликации, хранящийся в ансамбле Keeper. Далее, Узел 2 воспроизводит первую запись журнала, получая её ( 3 ) и загружая новую часть от Узла 1 ( 4 ), в то время как Узел 3 воспроизводит обе записи журнала ( 3 4 5 6 ). Наконец, Узел 3 сливает обе части в новую часть, удаляет входные части и записывает запись слияния в журнал репликации ( 7 ).

Рисунок 6: Репликация в кластере из трех узлов.

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

3.7 Соответствие ACID

Чтобы максимизировать производительность параллельных операций чтения и записи, ClickHouse максимально избегает блокировок. Запросы выполняются против снимка всех частей во всех вовлеченных таблицах, созданного в начале запроса. Это гарантирует, что новые части, вставленные параллельными INSERT-ами или слияниями (раздел 3.1), не участвуют в выполнении. Чтобы предотвратить одновременное изменение или удаление частей (раздел 3.4), счетчик ссылок на обрабатываемые части увеличивается на время выполнения запроса. Формально это соответствует изоляции по снимкам, реализованной с помощью варианта MVCC [6], основанного на версионированных частях. В результате операторы в целом не соответствуют ACID, кроме редкого случая, когда параллельные записи в момент создания снимка влияют только на одну часть.

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

4 УРОВЕНЬ ОБРАБОТКИ ЗАПРОСОВ

Рисунок 7: Параллелизация между единицами SIMD, ядрами и узлами.

Как показано на Рисунке 7, ClickHouse параллелизует запросы на уровне элементов данных, частей данных и шардов таблицы. Несколько элементов данных могут обрабатываться внутри операторов одновременно с использованием инструкций SIMD. На одном узле движок запросов выполняет операторы одновременно в нескольких потоках. ClickHouse использует ту же модель векторизации, что и MonetDB/X100 [11], т.е. операторы производят, передают и потребляют несколько строк (частей данных), а не одиночные строки для минимизации накладных расходов на виртуальные вызовы функций. Если исходная таблица разбита на несовпадающие шардированные таблицы, несколько узлов могут одновременно сканировать шары. В результате все аппаратные ресурсы полностью используются, и обработка запросов может масштабироваться горизонтально путем добавления узлов и вертикально путем добавления ядер.

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

4.1 Параллелизация SIMD

Передача нескольких строк между операторами создает возможность для векторизации. Векторизация основана либо на вручную написанных встроенных функциях [64, 80], либо на автоматической векторизации компилятора [25]. Код, который извлекает выгоду из векторизации, компилируется в различные вычислительные ядра. Например, внутренний "горячий" цикл оператора запроса может быть реализован в терминах невекторизованного ядра, автоматически векторизованного ядра AVX2 и вручную векторизованного ядра AVX-512. Самое быстрое ядро выбирается во время выполнения на основе инструкции cpuid. Этот подход позволяет ClickHouse работать на системах, которые старше 15 лет (требованиями являются минимум SSE 4.2), при этом обеспечивая значительные ускорения на современном оборудовании.

4.2 Многопоточная Параллелизация

Рисунок 8: Физический план оператора с тремя дорожками.

ClickHouse следует традиционному подходу [31] преобразования SQL-запросов в направленный граф физических операторов плана. Вход оператора плана представляется специальными исходными операторами, которые читают данные в нативном или любом из поддерживаемых сторонних форматов (см. раздел 5). Точно так же специальный оператор вывода преобразует результат в желаемый выходной формат. Физический план операторов разворачивается во время компиляции запроса в независимые исполнительные дорожки на основе настраиваемого максимального количества рабочих потоков (по умолчанию - количество ядер) и размера исходной таблицы. Дорожки разлагают обрабатываемые данные операторов параллельно на неперекрывающиеся диапазоны. Чтобы максимизировать возможность параллельной обработки, дорожки объединяются как можно позже.

В качестве примера, рамка для Узла 1 на Рисунке 8 показывает граф операторов типичного OLAP-запроса к таблице со статистикой показов страницы. На первом этапе одновременно фильтруются три несовпадающих диапазона исходной таблицы. Оператор обмена Repartition динамически маршрутизирует части результатов между первым и вторым этапами, чтобы поддерживать равномерную загрузку потоков обработки. После первого этапа дорожки могут стать несбалансированными, если сканируемые диапазоны имеют значительно разные селективности. На втором этапе строки, прошедшие фильтр, группируются по RegionID. Операторы Aggregation поддерживают локальные группы результатов с RegionID в качестве столбца группировки и сумму и подсчет по группе в качестве частичного состояния агрегации для avg(). Локальные результаты агрегации в конечном итоге объединяются оператором GroupStateMerge в глобальный результат агрегации. Этот оператор также является разрывом конвейера, т.е. третий этап может начаться только после полной обработки результата агрегации. На третьем этапе группы результатов сначала разделяются оператором распределения по трем равным по размеру несовпадающим.partition, которые затем сортируются по AvgLatency. Сортировка выполняется в три этапа: сначала операторы ChunkSort сортируют отдельные части каждого раздела. Затем операторы StreamSort поддерживают локально отсортированный результат, который комбинируется с приходящими отсортированными частями с использованием 2-way merge sorting. Наконец, оператор MergeSort объединяет локальные результаты с помощью k-way sorting, чтобы получить окончательный результат.

Операторы являются автоматами состояний и соединены между собой через входные и выходные порты. Три возможных состояния оператора - need-chunk, ready и done. Чтобы перейти от need-chunk к ready, часть помещается в входной порт оператора. Чтобы перейти от ready к done, оператор обрабатывает входную часть и генерирует выходную часть. Чтобы перейти от done к need-chunk, выходная часть удаляется из выходного порта оператора. Первые и третьи переходы состояний в двух связанных операторах могут выполняться только в рамках одного шага. Исходные операторы (выводные операторы) имеют только состояния ready и done (need-chunk и done).

Рабочие потоки непрерывно проходят через физический план операторов и выполняют переходы состояний. Чтобы поддерживать работу кэшей CPU, план содержит подсказки, что один и тот же поток должен обрабатывать последовательные операторы в одной дорожке. Параллельная обработка происходит как горизонтально на несовпадающих входах в пределах стадии (например, на Рисунке 8 операторы Aggregation выполняются одновременно), так и вертикально между этапами, не разделенными разрывами конвейера (например, на Рисунке 8 операторы Filter и Aggregation в одной дорожке могут работать одновременно). Чтобы избежать переподписки и недостаточной подписки, когда начинаются новые запросы или завершаются одновременные запросы, степень параллелизма может меняться во время запроса между одним и максимальным количеством рабочих потоков для запроса, указанным в начале запроса (см. раздел 4.5).

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

Двигатель выполнения запросов ClickHouse и параллелизм на основе кусочков [44] похожи тем, что дорожки обычно выполняются на разных ядрах / сокетах NUMA и что рабочие потоки могут заимствовать задачи из других дорожек. Также нет центрального компонента планировщика; вместо этого рабочие потоки индивидуально выбирают свои задачи, постоянно проходя через план операторов. В отличие от параллелизма на основе кусочков, ClickHouse впечатывает максимальную степень параллелизма в план и использует гораздо большие диапазоны для разделения исходной таблицы по сравнению с обычными размерами кусочков около 100.000 строк. Хотя это может в некоторых случаях вызывать задержки (например, когда время выполнения операторов фильтра в различных дорожках сильно отличается), мы отмечаем, что широкое использование операторов обмена, таких как Repartition, по крайней мере, избегает накопления таких дисбалансов между стадиями.

4.3 Параллелизация Многоузловая

Если исходная таблица запроса разбита на шардированные, оптимизатор запроса на узле, получившем запрос (узле-инициаторе), старается выполнить как можно больше работы на других узлах. Результаты из других узлов могут быть интегрированы в различные точки плана запроса. В зависимости от запроса, удаленные узлы могут либо 1. передавать сырые столбцы исходной таблицы узлу-инициатору, 2. фильтровать исходные столбцы и отправлять оставшиеся строки, 3. выполнять операции фильтрации и агрегации и отправлять локальные группы результатов с частичными состояниями агрегации, или 4. выполнять весь запрос, включая фильтры, агрегацию и сортировку.

Узлы 2 ... N на Рисунке 8 показывают фрагменты плана, выполняемые на других узлах, которые содержат шары таблицы hit. Эти узлы фильтруют и группируют локальные данные и отправляют результат узлу-инициатору. Оператор GroupStateMerge на узле 1 объединяет локальные и удаленные результаты перед окончательной сортировкой групп результатов.

4.4 Глобальная Оптимизация Производительности

Этот раздел представляет избранные ключевые оптимизации производительности, применяемые на различных этапах выполнения запросов.

Оптимизация запросов. Первая группа оптимизаций применяется к семантическому представлению запроса, полученному из AST запроса. Примеры таких оптимизаций включают сложение констант (например, concat(lower('a'),upper('b')) становится 'aB'), извлечение скалярных значений из определенных агрегатных функций (например, sum(a2) становится 2 * sum(a)), устранение общих подвыражений и преобразование дизъюнкций фильтров равенства в списки IN (например, x=c OR x=d становится x IN (c,d)). Оптимизированное семантическое представление запроса впоследствии преобразуется в логический операторный план. Оптимизации выше логического плана включают подъем фильтров, переупорядочивание шагов оценки функций и сортировки, в зависимости от того, что оценивается как более затратное. В конечном итоге логический план запроса преобразуется в физический операторный план. Это преобразование может использовать особенности вовлеченных движков таблиц. Например, в случае движка таблиц MergeTree, если столбцы ORDER BY составляю префикс первичного ключа, данные могут быть прочитаны в порядке диска, и операторы сортировки могут быть удалены из плана. Также, если столбцы группировки в агрегации формируют префикс первичного ключа, ClickHouse может использовать сортированную агрегацию [33], т.е. агрегировать группы одного и того же значения в предварительно отсортированных входах непосредственно. По сравнению с хеш-агрегацией, сортированная агрегация требует значительно меньше памяти, и агрегированное значение можно передать следующему оператору сразу после обработки группы.

Компиляция Запросов. ClickHouse использует компиляцию запросов на базе LLVM для динамического объединения соседних операторов плана [38, 53]. Например, выражение a * b + c + 1 может быть объединено в один оператор вместо трех операторов. Кроме выражений, ClickHouse также использует компиляцию для оценки нескольких агрегатных функций за один раз (т.е. для GROUP BY) и для сортировки с более чем одним ключом сортировки. Компиляция запросов уменьшает количество виртуальных вызовов, сохраняет данные в регистрах или кэшах CPU и помогает предсказателю ветвлений, так как исполняется меньше кода. Кроме того, компиляция во время выполнения позволяет применять богатый набор оптимизаций, таких как логические оптимизации и оптимизации с подглядыванием, реализованные в компиляторах, и дает доступ к самым быстрым доступным на месте инструкциям процессора. Компиляция инициируется только тогда, когда одно и то же регулярное, агрегатное или сортировочное выражение выполняется различными запросами более чем указанное количество раз. Скомпилированные запросные операторы кешируются и могут быть повторно использованы последующими запросами.[7]

Оценка Индекса Первичного Ключа. ClickHouse оценивает условия WHERE с использованием индекса первичного ключа, если подмножество фильтров в конъюнктивной нормальной форме условия составляет префикс столбцов первичного ключа. Индекс первичного ключа анализируется слева направо по лексикографически отсортированным диапазонам значений ключа. Фильтровые условия, соответствующие столбцу первичного ключа, оцениваются с использованием тернарной логики - они могут быть все истинными, все ложными или комбинацией истинных/ложных для значений в диапазоне. В последнем случае диапазон делится на поддиапазоны, которые анализируются рекурсивно. Существуют дополнительные оптимизации для функций в условиях фильтрации. Во-первых, функции имеют свойства, описывающие их монотонность, например, toDayOfMonth(date) является кусочно монотонной в пределах месяца. Свойства монотонности позволяют выводить, если функция выдает отсортированные результаты для отсортированных значений ключа диапазонов. Во-вторых, некоторые функции могут вычислять прообраз данного результата функции. Это используется для замены сравнений констант с вызовами функции по столбцам ключа, сравнивая значение столбца ключа с прообразом. Например, toYear(k) = 2024 может быть заменено на k >= 2024-01-01 && k < 2025-01-01.

Пропуск Данных. ClickHouse пытается избегать чтения данных во время выполнения запроса, используя структуры данных, представленные в разделе 3.2. Кроме того, фильтры по различным столбцам оцениваются последовательно в порядке убывания оценочной селективности на основе эвристики и (по желанию) статистики столбцов. Только части данных, содержащие хотя бы одну совпадающую строку, передаются следующему предикату. Это постепенно уменьшает объем считываемых данных и количество вычислений, которые необходимо выполнить от предиката к предикату. Оптимизация применяется только тогда, когда присутствует хотя бы один высокоселективный предикат; в противном случае задержка запроса ухудшится по сравнению с оценкой всех предикатов параллельно.

Хеш-таблицы. Хеш-таблицы являются основными структурами данных для агрегации и хеш-соединений. Выбор правильного типа хеш-таблицы критически важен для производительности. ClickHouse инстанцирует различные хеш-таблицы (более 30 по состоянию на март 2024 года) из общего шаблона хеш-таблицы с хеш-функцией, аллокатором, типом ячейки и политикой изменения размера в качестве вариативных точек. В зависимости от типа данных столбцов группировки, оценочной кардинальности хеш-таблицы и других факторов, самая быстрая хеш-таблица выбирается для каждого оператора запроса индивидуально. Другие оптимизации, реализованные для хеш-таблиц, включают:

двухуровневую структуру с 256 подсчетами (на основе первого байта хеша) для поддержки огромных наборов ключей,
строковые хеш-таблицы [79] с четырьмя подсчетами и разными хеш-функциями для различных длин строк,
таблицы поиска, которые используют ключ непосредственно как индекс корзины (т.е. без хеширования), когда ключей немного,
значения с внедренными хешами для более быстрой обработки коллизий, когда сравнение дорого (например, строки, AST),
создание хеш-таблиц на основе предсказанных размеров из статистики времени выполнения, чтобы избежать ненужных изменений размеров,
аллокацию нескольких маленьких хеш-таблиц с одинаковыми циклами создания/уничтожения на одном слое памяти,
мгновенное очищение хеш-таблиц для повторного использования с использованием счетчиков версий по карте хеширования и по ячейкам,
использование предвыборки CPU (__builtin_prefetch) для ускорения извлечения значений после хеширования ключа.

Соединения. Поскольку ClickHouse изначально поддерживал соединения только в rudimentary форме, многие сценарии исторически прибегали к денормализованным таблицам. Сегодня база данных предлагает все типы соединений, доступные в SQL (внутренние, левое/правое/полное внешнее, кросс, как-до), а также различные алгоритмы соединения, такие как хеш-соединение (наивное, grace), сортировочно-сливающее соединение и индексовое соединение для движков таблиц с быстрым поиском по ключам (обычно словари).

Поскольку соединения являются одними из наиболее затратных операций базы данных, важно предоставлять параллельные варианты классических алгоритмов соединения, в идеале с настраиваемыми компромиссами пространства/времени. Для хеш-соединений ClickHouse реализует неблокирующий, общий алгоритм разделения из [7]. Например, запрос на Рисунке 9 вычисляет, как пользователи перемещаются между URL-адресами через само-соединение на таблице статистики показов страниц. Этап построения соединения разделяется на три дорожки, охватывающие три несовпадающих диапазона исходной таблицы. Вместо глобальной хеш-таблицы используется разделенная хеш-таблица. (обычно три) рабочих потока определяют целевую партию для каждой входной строки с помощью вычисления модуля хеш-функции. Доступ к разделам хеш-таблицы синхронизируется с помощью оператора Gather exchange. Этап пробности находит целевую партию для своих входных кортежей аналогичным образом. Хотя этот алгоритм вводит два дополнительных вычисления хеша на кортеж, он значительно снижает конкуренцию за блокировку на этапе построения, в зависимости от количества разделов хеш-таблицы.

Рисунок 9: Параллельное хеш-соединение с тремя разделами хеш-таблицы.

4.5 Изоляция Нагрузки

ClickHouse предлагает управление конкурентностью, лимиты использования памяти и планирование ввода-вывода, позволяя пользователям изолировать запросы в классы нагрузки. Устанавливая лимиты на разделяемые ресурсы (ядра CPU, DRAM, ввод-вывод диска и сети) для конкретных классов нагрузки, он гарантирует, что эти запросы не будут влиять на другие критически важные бизнес-запросы.

Управление конкурентностью предотвращает переподписку потоков в сценариях с высоким числом одновременных запросов. Более конкретно, количество рабочих потоков на запрос динамически корректируется на основе установленного соотношения к числу доступных ядер CPU.

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

Наконец, планирование ввода-вывода позволяет пользователям ограничивать локальные и удаленные обращения к дискам для классов нагрузки на основе максимальной пропускной способности, текущих запросов и политики (например, FIFO, SFC [32]).

5 УРОВЕНЬ ИНТЕГРАЦИИ

Приложения для принятия решений в реальном времени часто зависят от эффективного доступа к данным в нескольких местах с низкой задержкой. Существуют два подхода для того, чтобы сделать внешние данные доступными в OLAP базе данных. С помощью доступа к данным на основе пуша сторонний компонент соединяет базу данных с внешними хранилищами данных. Один из примеров таких инструментов - специализированные инструменты извлечения-преобразования-загрузки (ETL), которые отправляют удаленные данные в целевую систему. В модели на основе вытягивания сама база данных подключается к удаленным источникам данных и вытягивает данные для запросов в локальные таблицы или экспортирует данные в удаленные системы. Хотя подходы на основе пуша более универсальны и распространены, они требуют большего архитектурного объема и становятся узким местом масштабируемости. Напротив, удаленная связь непосредственно в базе данных предлагает интересные возможности, такие как соединения между локальными и удаленными данными, при этом сохраняя общую архитектуру простой и уменьшая время для получения инсайтов.

Остальная часть раздела исследует методы интеграции данных на основе вытягивания в ClickHouse, направленные на доступ к данным в удаленных местах. Мы отмечаем, что идея удаленной связи в SQL базах данных не нова. Например, стандарт SQL/MED [35], введенный в 2001 году и реализованный PostgreSQL с 2011 года [65], предлагает внешние обертки данных как единый интерфейс для управления внешними данными. Максимальная совместимость с другими хранилищами данных и форматами хранения является одной из целей дизайна ClickHouse. По состоянию на март 2024 года ClickHouse предлагает, насколько нам известно, наибольшее количество встроенных опций интеграции данных среди всех аналитических баз данных.

Внешняя Связь. ClickHouse предоставляет более 50 интеграционных таблиц функций и движков для связи с внешними системами и хранилищами данных, включая ODBC, MySQL, PostgreSQL, SQLite, Kafka, Hive, MongoDB, Redis, S3/GCP/Azure объектные хранилища и различные озера данных. Мы дополнительно делим их на категории, которые показаны на следующем бонусном рисунке (не часть оригинальной статьи vldb).

Бонусное изображение: Возможности взаимодействия ClickBench.

Временный доступ с помощью интеграционных табличных функций. Табличные функции могут быть вызваны в разделе FROM запросов SELECT для чтения удаленных данных для исследовательских запросов. В качестве альтернативы, их можно использовать для записи данных в удаленные хранилища с помощью операторов INSERT INTO TABLE FUNCTION.

Постоянный доступ. Существует три метода для создания постоянных соединений с удаленными хранилищами данных и системами обработки.

Во-первых, интеграционные табличные движки представляют удаленный источник данных, например, таблицу MySQL, как постоянную локальную таблицу. Пользователи хранят определение таблицы, используя синтаксис CREATE TABLE AS, в сочетании с запросом SELECT и табличной функцией. Можно указать настраиваемую схему, например, чтобы ссылаться только на подмножество удаленных столбцов, или использовать вывод схемы для автоматического определения имен столбцов и соответствующих типов ClickHouse. Мы также различаем пассивное и активное поведение во время выполнения: Пассивные табличные движки перенаправляют запросы в удаленную систему и заполняют локальную прокси-таблицу результатами. В отличие от этого, активные табличные движки периодически извлекают данные из удаленной системы или подписываются на удаленные изменения, например, через логическую репликацию PostgreSQL. В результате локальная таблица содержит полную копию удаленной таблицы.

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

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

Форматы Данных. Для взаимодействия с системами третьих сторон современные аналитические базы данных также должны быть способны обрабатывать данные в любом формате. Кроме своего нативного формата ClickHouse поддерживает более 90 форматов, включая CSV, JSON, Parquet, Avro, ORC, Arrow и Protobuf. Каждый формат может быть форматом ввода (который ClickHouse может читать), форматом вывода (который ClickHouse может экспортировать) или обоими. Некоторые форматы, ориентированные на аналитику, такие как Parquet, также интегрированы с обработкой запросов, т.е. оптимизатор может использовать встроенные статистики, а фильтры оцениваются непосредственно на сжатых данных.

Совместительные интерфейсы. Кроме своего нативного двоичного протокола и HTTP, клиенты могут взаимодействовать с ClickHouse через интерфейсы, совместимые с протоколами MySQL или PostgreSQL. Эта функция совместимости полезна для обеспечения доступа из проприетарных приложений (например, некоторых инструментов бизнес-аналитики), для которых еще не реализовано нативное подключение ClickHouse.

6 ПРОИЗВОДИТЕЛЬНОСТЬ КАК ФУНКЦИЯ

Этот раздел представляет встроенные инструменты для анализа производительности и оценивает производительность, используя реальные и бенчмарковые запросы.

6.1 Встроенные Инструменты Анализа Производительности

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

Метрики сервера и запросов. Статистика на уровне сервера, такая как количество активных частей, пропускная способность сети и коэффициенты попаданий в кэш, дополняются статистикой на уровне запросов, например, количеством прочитанных блоков или статистикой использования индекса. Метрики вычисляются синхронно (по запросу) или асинхронно через настраиваемые интервалы.

Профилировщик выборок. Стек вызовов потоков сервера может быть собран с помощью профилировщика выборок. Результаты могут быть по желанию экспортированы в внешние инструменты, такие как визуализаторы flamegraph.

Интеграция OpenTelemetry. OpenTelemetry является открытым стандартом для трассировки строк данных по множеству систем обработки данных [8]. ClickHouse может генерировать временные интервалы OpenTelemetry с настраиваемой гранулярностью для всех этапов обработки запросов, а также собирать и анализировать временные интервалы OpenTelemetry из других систем.

Объяснение запроса. Как и в других базах данных, запросы SELECT могут предшествовать EXPLAIN для детального анализа AST запроса, логического и физического планов операторов и поведения во время выполнения.

6.2 Бенчмарки

Хотя бенчмарки подвергались критике за то, что они недостаточно реалистичны [10, 52, 66, 74], они все же полезны для выявления сильных и слабых сторон баз данных. В следующем разделе мы обсудим, как бенчмарки используются для оценки производительности ClickHouse.

6.2.1 Денормализованные таблицы

Запросы фильтрации и агрегации по денормализованным таблицам фактов исторически представляют собой основное применение ClickHouse. Мы сообщаем о временах выполнения ClickBench, типовой рабочей нагрузки подобного рода, которая моделирует ad-hoc и периодические запросы отчетности, используемые в анализе кликстрима и трафика. Эталон состоит из 43 запросов к таблице с 100 миллионами анонимизированных посещений страниц, полученных из одной из крупнейших аналитических платформ в интернете. Онлайн панель [17] отображает измерения (времена выполнения при холодном/горячем старте, время импорта данных, размер на диске) для более чем 45 коммерческих и исследовательских баз данных по состоянию на июнь 2024 года. Результаты предоставляются независимыми участниками на основе общедоступного набора данных и запросов [16]. Запросы тестируют последовательные и индексационные пути доступа и регулярно выявляют операции реляционной базы данных, ограниченные производительностью CPU, вводом-выводом или памятью.

Рисунок 10 показывает общие относительные времена выполнения при холодном и горячем старте для последовательного выполнения всех запросов ClickBench в базах данных, часто используемых для аналитики. Измерения были произведены на одноузловом экземпляре AWS EC2 c6a.4xlarge с 16 vCPU, 32 ГБ ОЗУ и 5000 IOPS / 1000 MiB/s на диске. Сравнимые системы использовались для Redshift (ra3.4xlarge, 12 vCPU, 96 ГБ ОЗУ) и Snowfake (размер хранилища S: 2x8 vCPU, 2x16 ГБ ОЗУ). Физический дизайн базы данных настроен только легким образом, например, мы указываем первичные ключи, но не изменяем сжатие отдельных столбцов, не создаем проекции или индексы пропуска. Мы также очищаем кэш страниц Linux перед каждым запуском холодного запроса, но не настраиваем элементы управления базы данных или операционной системы. Для каждого запроса используется наибыстрейшее время выполнения через базы данных в качестве основы. Относительные времена выполнения запросов для других баз данных рассчитываются как ( + 10)/(_ + 10). Общее относительное время выполнения для базы данных — это геометрическое среднее по соотношениям на уровне запроса. Хотя исследовательская база данных Umbra [54] достигает лучшего общего времени выполнения при горячем старте, ClickHouse превышает все другие базы данных производственного класса по горячему и холодному времени выполнения.

Рисунок 10: Относительные времена холодного и горячего старта ClickBench.

Чтобы отслеживать производительность SELECT в более разнообразных рабочих нагрузках с течением времени, мы используем комбинацию из четырех эталонов, которые называются VersionsBench [19]. Этот эталон выполняется раз в месяц, когда публикуется новая версия, чтобы оценить ее производительность [20] и выявить изменения в коде, которые потенциально ухудшили производительность: отдельные эталоны включают: 1. ClickBench (описанный выше), 2. 15 запросов MgBench [21], 3. 13 запросов к денормализованной таблице фактов Star Schema Benchmark [57] с 600 миллионами строк. 4. 4 запроса по NYC Taxi Rides с 3.4 миллиарда строк [70].

Рисунок 11 показывает развитие времен выполнения VersionsBench для 77 версий ClickHouse между мартом 2018 года и мартом 2024 года. Чтобы компенсировать различия в относительном времени выполнения отдельных запросов, мы нормализуем времена выполнения, используя геометрическое среднее с отношением к минимальному времени выполнения запроса по всем версиям в качестве веса. Производительность VersionBench улучшилась в 1.72 × за последние шесть лет. Даты выпусков с долгосрочной поддержкой (LTS) отмечены на оси x. Хотя производительность временно ухудшалась в некоторые периоды, LTS выпуски, как правило, имеют сопоставимую или лучшую производительность по сравнению с предыдущей версией LTS. Существенное улучшение в августе 2022 года было вызвано техникой оценки фильтров по столбцам, описанной в разделе 4.4.

Рисунок 11: Относительные времена выполнения VersionsBench 2018-2024.

6.2.2 Нормализованные таблицы

В классическом хранилище данные часто моделируются с использованием звездных или снежинок образцов. Мы представляем времена выполнения запросов TPC-H (фактор масштабирования 100), но отмечаем, что нормализованные таблицы являются новой областью применения для ClickHouse. Рисунок 12 показывает горячие времена выполнения запросов TPC-H на основе алгоритма параллельного хэш-присоединения, описанного в разделе 4.4. Измерения были произведены на одноузловом экземпляре AWS EC2 c6i.16xlarge с 64 vCPU, 128 ГБ ОЗУ и 5000 IOPS / 1000 MiB/s на диске. Были зафиксированы самые быстрые из пяти запусков. Для справки, мы провели те же измерения в системе Snowfake сопоставимого размера (размер хранилища L, 8x8 vCPU, 8x16 ГБ ОЗУ). Результаты одиннадцати запросов исключены из таблицы: Запросы Q2, Q4, Q13, Q17 и Q20-22 включают коррелированные подзапросы, которые не поддерживаются на момент ClickHouse v24.6. Запросы Q7-Q9 и Q19 зависят от расширенной оптимизации на уровне плана для соединений, таких как перераспределение соединений и сглаживание предикатов соединений (обе отсутствуют на момент ClickHouse v24.6), чтобы достичь жизнеспособного времени выполнения. Автоматическая декорреляция подзапросов и лучшая поддержка оптимизатора для соединений планируется к реализации в 2024 году [18]. Из оставшихся 11 запросов 5 (6) запросов выполнялись быстрее в ClickHouse (Snowfake). Поскольку вышеупомянутые оптимизации известны как критические для производительности [27], мы ожидаем, что они улучшат времена выполнения этих запросов после реализации.

Рисунок 12: Горячие времена выполнения (в секундах) для запросов TPC-H.

Аналитические базы данных были предметом большого академического и коммерческого интереса в последние десятилетия [1]. Ранние системы, такие как Sybase IQ [48], Teradata [72], Vertica [42] и Greenplum [47], отличались дорогими пакетными процессами ETL и ограниченной эластичностью из-за своей локальной природы. В начале 2010-х годов появление облачных хранилищ данных и предложений баз данных как услуги (DBaaS), таких как Snowfake [22], BigQuery [49] и Redshift [4], резко снизило стоимость и сложность аналитики для организаций, одновременно выигрывая от высокой доступности и автоматического масштабирования ресурсов. В более недавнее время аналитические ядра выполнения (например, Photon [5] и Velox [62]) предлагают совместно модифицированную обработку данных для использования в различных аналитических, потоковых и машинно-обучающих приложениях.

Наиболее похожими базами данных на ClickHouse, с точки зрения целей и принципов проектирования, являются Druid [78] и Pinot [34]. Оба системы нацелены на аналитику в реальном времени с высокими скоростями поступления данных. Как и ClickHouse, таблицы разбиваются на горизонтальные части, называемые сегментами. В то время как ClickHouse постоянно объединяет меньшие части и, по желанию, уменьшает объем данных, используя методы, описанные в разделе 3.3, части остаются навсегда неизменными в Druid и Pinot. Кроме того, Druid и Pinot требуют специализированные узлы для создания, изменения и поиска таблиц, тогда как ClickHouse использует монолитный двоичный файл для этих задач.

Snowfake [22] — популярное облачное хранилище данных на основе архитектуры общего диска. Его подход к разделению таблиц на микропартии аналогичен концепции частей в ClickHouse. Snowfake использует гибридные страницы PAX [3] для хранения, тогда как формат хранения ClickHouse строго столбцовый. Snowfake также подчеркивает локальное кэширование и обрезку данных, используя автоматически создаваемые легковесные индексы [31, 51] в качестве источника хорошей производительности. Подобно первичным ключам в ClickHouse, пользователи могут опционально создавать кластерные индексы для совместного размещения данных с одинаковыми значениями.

Photon [5] и Velox [62] являются движками выполнения запросов, предназначенными для использования в качестве компонентов в сложных системах управления данными. Оба системы получают планы запросов в качестве входных данных, которые затем выполняются на локальном узле над файлами Parquet (Photon) или Arrow (Velox) [46]. ClickHouse способен потреблять и генерировать данные в этих универсальных форматах, но предпочитает свой собственный формат файла для хранения. В то время как Velox и Photon не оптимизируют план запроса (Velox выполняет базовые оптимизации выражений), они используют техники адаптивности во время выполнения, такие как динамическое переключение вычислительных ядер в зависимости от характеристик данных. Аналогичным образом, операторы плана в ClickHouse могут создавать другие операторы во время выполнения, в основном для переключения на внешние операторы агрегации или соединения, в зависимости от потребления памяти запроса. В статье о Photon отмечается, что конструкции, генерирующие код [38, 41, 53], сложнее разрабатывать и отлаживать, чем интерпретируемые векторизованные конструкции [11]. Поддержка (экспериментальная) генерации кода в Velox строит и связывает общую библиотеку, произведенную из сгенерированного во время выполнения кода C++, в то время как ClickHouse взаимодействует напрямую с API компиляции LLVM по запросу.

DuckDB [67] также предназначен для встраивания хост-процессом, но дополнительно предоставляет оптимизацию запросов и транзакции. Он был разработан для OLAP запросов, смешанных с случайными операциями OLTP. DuckDB, соответственно, выбрал формат хранения DataBlocks [43], который использует легковесные методы сжатия, такие как словари, сохраняющие порядок, или ссылочные рамки [2], чтобы достичь хорошей производительности в гибридных рабочих нагрузках. В отличие от этого, ClickHouse оптимизирован для сценариев только добавления, т.е. отсутствия или редких обновлений и удалений. Блоки сжимаются с использованием тяжелых методов, таких как LZ4, предполагая, что пользователи широко применяют обрезку данных для ускорения частых запросов, и что затраты на ввод-вывод значительно превышают затраты на декомпрессию для оставшихся запросов. DuckDB также предоставляет сериализуемые транзакции на основе схемы MVCC Hyper [55], в то время как ClickHouse предлагает только изоляцию снимков.

8 ЗАКЛЮЧЕНИЕ И ПЕРСПЕКТИВЫ

Мы представили архитектуру ClickHouse, открытой, высокопроизводительной OLAP базы данных. С оптимизированным для записи слоем хранения и современным векторизованным движком выполнения запросов в основе, ClickHouse обеспечивает аналитику в реальном времени на основе наборов данных объемом пета-байт с высокими скоростями поступления данных. Путем асинхронного слияния и преобразования данных в фоновом режиме, ClickHouse эффективно отделяет обслуживание данных от параллельных вставок. Его слой хранения позволяет сильно обрезать данные с использованием разреженных первичных индексов, индексов пропуска и таблиц проекций. Мы описали реализацию ClickHouse обновлений и удалений, идемпотентных вставок и репликации данных между узлами для обеспечения высокой доступности. Уровень обработки запросов оптимизирует запросы с использованием множества техник и параллелизует выполнение по всем ресурсам сервера и кластера. Интеграционные движки таблиц и функции предоставляют удобный способ взаимодействия с другими системами управления данными и форматами данных без швов. Через эталоны мы демонстрируем, что ClickHouse находится среди самых быстрых аналитических баз данных на рынке, и показали значительные улучшения в производительности типичных запросов в реальных развертываниях ClickHouse на протяжении многих лет.

Все функции и улучшения, запланированные на 2024 год, можно найти на публичной дорожной карте [18]. Запланированные улучшения включают поддержку пользовательских транзакций, PromQL [69] как альтернативного языка запросов, новый тип данных для полуструктурированных данных (например, JSON), лучшие оптимизации на уровне плана для соединений, а также реализацию легковесных обновлений для дополнения легковесных удалений.

БЛАГОДАРНОСТИ

Согласно версии 24.6, SELECT * FROM system.contributors возвращает 1994 человека, которые внесли свой вклад в ClickHouse. Мы хотели бы поблагодарить всю инженерную команду ClickHouse Inc. и удивительное сообщество с открытым исходным кодом ClickHouse за их упорный труд и преданность делу создания этой базы данных вместе.

ССЫЛКИ

[1] Даниэль Абади, Петер Бонч, Ставрос Харизопулос, Стратос Идреиос и Самуэль Мэдден. 2013. Дизайн и реализация современных столбцовых систем баз данных. https://doi.org/10.1561/9781601987556
[2] Даниэль Абади, Самуэль Мэдден и Мигель Феррейра. 2006. Интеграция сжатия и выполнения в столбцовых системах баз данных. В Материалах Международной конференции ACM SIGMOD по управлению данными 2006 года (SIGMOD '06). 671–682. https://doi.org/10.1145/1142473.1142548
[3] Анастасия Айламаки, Дэвид Дж. ДеУитт, Марк Д. Хилл и Мариос Скуонакис. 2001. Взаимосвязь отношений для повышения производительности кэша. В Материалах 27-й Международной конференции по очень большим базам данных (VLDB '01). Morgan Kaufmann Publishers Inc., Сан-Франциско, Калифорния, США, 169–180.
[4] Никос Арменадзоглу, Санудж Басу, Нага Бханури, Менчху Цай, Нареш Чайани, Кирэн Чинта, Венкатраман Говиндараджу, Тодд Дж. Грин, Мониш Гупта, Себастьян Хиллиг, Эрик Хотингер, Ян Лешински, Цзиньтянь Лянг, Майкл МакКриди, Фабиан Нагель, Иппократис Пандис, Панос Паркас, Рахул Патхак, Орестис Полифронью, Фойзур Рахман, Гаурава Саксен, Гокул Сундарараджан, Шрирам Субраманиам и Даг Тери. 2022. Amazon Redshift переосмыслен. В Материалах Международной конференции по управлению данными 2022 года (Филадельфия, Пенсильвания, США) (SIGMOD '22). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 2205–2217. https://doi.org/10.1145/3514221.3526045
[5] Александр Бем, Шаумик Палькар, Уткарш Агарвал, Тимоти Армстронг, Дэвид Кэшман, Анкур Дейн, Тодд Гриенштейн, Шант Ховсепиан, Райан Джонсон, Арвинд Сай Кришнан, Пол Левентис, Ала Лущак, Прашант Менон, Мустафа Моктар, Джин Панг, Самир Паранжпье, Грег Ран, Барт Самвел, Том ван Буссел, Герман ван Ховелл, Мэриан Сюэ, Рейнольд Ксин и Матей Захария. 2022. Photon: быстрый движок запросов для lakehouse-систем (SIGMOD '22). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 2326–2339. https://doi.org/10.1145/3514221. 3526054
[6] Филип А. Бернштейн и Натан Гудман. 1981. Контроль параллелизма в распределенных системах баз данных. ACM Computing Survey 13, 2 (1981), 185–221. https://doi.org/10.1145/356842.356846
[7] Спирос Бланас, Инан Ли и Джигнеш М. Пател. 2011. Проектирование и оценка алгоритмов хеш-присоединения с основной памятью для многопроцессорных ЦП. В Материалах Международной конференции ACM SIGMOD по управлению данными 2011 года (Афины, Греция) (SIGMOD '11). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 37–48. https://doi.org/10.1145/1989323.1989328
[8] Даниэль Гомес Бланко. 2023. Практическое OpenTelemetry. Springer Nature.
[9] Бертон Х. Блум. 1970. Компромиссы пространства/времени в хешировании с допустимыми ошибками. Commun. ACM 13, 7 (1970), 422–426. https://doi.org/10.1145/362686. 362692
[10] Петер Бонч, Томас Нойманн и Орри Эрлинг. 2014. TPC-H проанализирован: скрытые сообщения и извлеченные уроки из влиятельной меры. В Характеризации производительности и бенчмаркинге. 61–76. https://doi.org/10.1007/978-3-319- 04936-6_5
[11] Петер Бонч, Марчин Жуковский и Нiels Нэс. 2005. MonetDB/X100: гиперпакетная выполнение запросов. В CIDR.
[12] Мартин Буртшер и Парудж Ратанаворабан. 2007. Высокая пропускная способность сжатия данных с плавающей запятой двойной точности. В Конференции по сжатию данных (DCC). 293–302. https://doi.org/10.1109/DCC.2007.44
[13] Джеф Карпентер и Эбен Хьюитт. 2016. Cassandra: Определяющее руководство (2-е издание). O'Reilly Media, Inc.
[14] Бернадетт Шаррон-Бост, Фернандо Педоне и Андре Шипер (ред.). 2010. Репликация: теория и практика. Springer-Verlag.
[15] chDB. 2024. chDB - встроенный OLAP SQL движок. Получено 2024-06-20 с https://github.com/chdb-io/chdb
[16] ClickHouse. 2024. ClickBench: бенчмарк для аналитических баз данных. Получено 2024-06-20 с https://github.com/ClickHouse/ClickBench
[17] ClickHouse. 2024. ClickBench: сравнительные измерения. Получено 2024-06-20 с https://benchmark.clickhouse.com
[18] ClickHouse. 2024. Планы ClickHouse 2024 года (GitHub). Получено 2024-06-20 с https://github.com/ClickHouse/ClickHouse/issues/58392
[19] ClickHouse. 2024. Результаты бенчмарка версий ClickHouse. Получено 2024-06-20 с https://github.com/ClickHouse/ClickBench/tree/main/versions
[20] ClickHouse. 2024. Результаты бенчмарка версий ClickHouse. Получено 2024-06-20 с https://benchmark.clickhouse.com/versions/
[21] Эндрю Кротти. 2022. MgBench. Получено 2024-06-20 с https://github.com/ andrewcrotty/mgbench
[22] Бенуа Дажевиль, Тьерри Круан, Марцин Жуковский, Вадим Антонов, Артин Аванес, Джон Бок, Джонатан Клейбау, Даниэль Энговатоф, Мартин Хенчель, Цзяншэн Хуан, Эллисон У. Ли, Ашиш Мотивала, Абдул К. Мунір, Стивен Пелли, Петер Повинец, Грег Ран, Спиридон Триантафиллис и Филипп Унтербруннер. 2016. Снежное облако: эластичное хранилище данных. В Материалах Международной конференции по управлению данными 2016 года (Сан-Франциско, Калифорния, США) (SIGMOD '16). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 215–226. https: //doi.org/10.1145/2882903.2903741
[23] Патрик Дамме, Аннетт Унгетюм, Жулиана Хильдебрандт, Дирк Хабих и Вольфганг Ленер. 2019. От комплексного экспериментального исследования к стратегии выбора на основе затрат для легковесных алгоритмов сжатия целых чисел. ACM Trans. Database Syst. 44, 3, статья 9 (2019), 46 страниц. https://doi.org/10.1145/3323991
[24] Филипп Доббелаэр и Кюмарс Шейх Искойли. 2017. Kafka против RabbitMQ: сравнительное исследование двух отраслевых реализаций Publish/Subscribe: отраслевой доклад (DEBS '17). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 227–238. https://doi.org/10.1145/3093742.3093908
[25] Документация LLVM. 2024. Авто-векторизация в LLVM. Получено 2024-06-20 с https://llvm.org/docs/Vectorizers.html
[26] Сийинг Дунг, Эндрю Крычка, Яньцинь Цзинь и Майкл Стумм. 2021. RocksDB: эволюция приоритетов разработки в хранилище ключ-значение для крупных приложений. ACM Transactions on Storage 17, 4, статья 26 (2021), 32 страницы. https://doi.org/10.1145/3483840
[27] Маркус Дрезелер, Мартин Буаисье, Тильман Рабл и Маттиас Уфаер. 2020. Количественное определение узких мест TPC-H и их оптимизации. Proc. VLDB Endow. 13, 8 (2020), 1206–1220. https://doi.org/10.14778/3389133.3389138
[28] Тед Даннинг. 2021. T-дйжест: эффективные оценки распределений. Software Impacts 7 (2021). https://doi.org/10.1016/j.simpa.2020.100049
[29] Мартин Фауст, Мартин Буаисье, Марвин Келлер, Дэвид Швальб, Хольгер Бишоф, Катрин Эйзенрайх, Франц Фербер и Хассо Платтнер. 2016. Уменьшение отпечатков и обеспечение уникальности с помощью хеш-индексов в SAP HANA. В Приложениях баз данных и экспертных систем. 137–151. https://doi.org/10.1007/978-3-319-44406- 2_11
[30] Филипп Флажоле, Эрик Фюси, Оливьер Гандуэ и Фредерик Меньер. 2007. HyperLogLog: анализ алгоритма оценки кардинальности, близкого к оптимуму. В AofA: Анализ алгоритмов, том DMTCS Proceedings, том AH, Конференция 2007 года по анализу алгоритмов (AofA 07). Дискретная математика и теоретическая информатика, 137–156. https://doi.org/10.46298/dmtcs.3545
[31] Хектор Гарсия-Молина, Джефри Д. Ульман и Дженнифер Уидом. 2009. Системы баз данных - Полная книга (2-е издание).
[32] Паван Гоял, Харрик М. Вин и Хайчен Чен. 1996. Справедливое очередность времени старта: алгоритм планирования для интегрированных сервисов пакетной коммутации. 26, 4 (1996), 157–168. https://doi.org/10.1145/248157.248171
[33] Готц Грефе. 1993. Техники оценки запросов для больших баз данных. ACM Comput. Surv. 25, 2 (1993), 73–169. https://doi.org/10.1145/152610.152611
[34] Жан-Франсуа Им, Кишор Гопалакришна, Суббу Субраманиам, Майанк Шривиастава, Адвайт Тумбде, Сяотянь Цзян, Дженнифер Дай, Сеунгхюн Ли, Неха Павар, Цзялианг Ли и Рави Арингунрам. 2018. Pinot: OLAP в реальном времени для 530 миллионов пользователей. В Материалах Международной конференции по управлению данными 2018 года (Хьюстон, Техас, США) (SIGMOD '18). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 583–594. https://doi.org/10.1145/3183713.3190661
[35] ISO/IEC 9075-9:2001 2001. Информационные технологии — Язык баз данных — SQL — Часть 9: Управление внешними данными (SQL/MED). Стандарт. Международная организация по стандартизации.
[36] Парас Джейн, Питер Крафт, Конор Пауэр, Татагада Дас, Ион Стойка и Матей Захария. 2023. Анализ и сравнение систем хранения Lakehouse. CIDR.
[37] Проект Jupyter. 2024. Jupyter Notebooks. Получено 2024-06-20 с https: //jupyter.org/
[38] Тимо Керстен, Виктор Лейс, Альфонс Кемпер, Томас Нойманн, Эндрю Павло и Петер Бонч. 2018. Все, что вы всегда хотели знать о скомпилированных и векторизованных запросах, но боялись спросить. Proc. VLDB Endow. 11, 13 (сентябрь 2018), 2209–2222. https://doi.org/10.14778/3275366.3284966
[39] Чангкю Ким, Джатин Чхугани, Надатур Сатиш, Эрик Седлар, Энтони Д. Нгуен, Тим Кальдевей, Виктор В. Ли, Скотт А. Брандт и Прадип Дубей. 2010. FAST: быстрая архитектурно-чувствительная поиск в дереве на современных ЦП и ГП. В Материалах Международной конференции ACM SIGMOD по управлению данными 2010 года (Индианаполис, Индиана, США) (SIGMOD '10). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 339–350. https://doi.org/10.1145/1807167.1807206
[40] Дональд Е. Кнут. 1973. Искусство программирования, Том III: Сортировка и поиск. Addison-Wesley.
[41] Андре Кохн, Виктор Лейс и Томас Нойманн. 2018. Адаптивное выполнение скомпилированных запросов. В 2018 году IEEE 34-я Международная конференция по инженерии данных (ICDE). 197–208. https://doi.org/10.1109/ICDE.2018.00027
[42] Эндрю Лэмб, Мэтт Фуллер, Рамакришна Варадараджан, Нга Тран, Бен Вандивер, Лирик Доши и Чак Беар. 2012. База данных аналитики Vertica: C-Store через 7 лет. Proc. VLDB Endow. 5, 12 (авг. 2012), 1790–1801. https://doi.org/10. 14778/2367502.2367518
[43] Харольд Ланг, Тобиас Мюлбауер, Флориан Функе, Петер А. Бонч, Томас Нойманн и Альфонс Кемпер. 2016. Блоки данных: гибрид OLTP и OLAP на сжатом хранилище, использующем как векторизацию, так и компиляцию. В Материалах Международной конференции по управлению данными 2016 года (Сан-Франциско, Калифорния, США) (SIGMOD '16). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 311–326. https://doi.org/10.1145/2882903.2882925
[44] Виктор Лейс, Петер Бонч, Альфонс Кемпер и Томас Нойман. 2014. Модель параллелизма на основе морселов: фреймворк для оценки запросов с учетом NUMA для многопроцессорного времени. В Материалах Международной конференции ACM SIGMOD по управлению данными 2014 года (Сноубёрд, Юта, США) (SIGMOD '14). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 743–754. https://doi.org/10.1145/2588555. 2610507
[45] Виктор Лейс, Альфонс Кемпер и Томас Нойман. 2013. Адаптивное древо радиуса: AРТful индексация для баз данных в основной памяти. В 2013 году IEEE 29-я Международная конференция по инженерии данных (ICDE). 38–49. https://doi.org/10.1109/ICDE. 2013.6544812
[46] Чунвей Лю, Анна Павленко, Маттео Интерланди и Брендон Хейнс. 2023. Глубокое погружение в общие открытые форматы для аналитических СУБД. 16, 11 (июль 2023), 3044–3056. https://doi.org/10.14778/3611479.3611507
[47] Чжэнхуа Лю, Хуан Хуберт Чжан, Ганг Сян, Ганг Гуо, Хаозу Ванг, Цзинбао Чэнь, Ассим Правин, Юй Ян, Сяоминь Гао, Александра Ванг, Вэнь Лин, Ашвин Агравал, Цзюнфэн Ян, Хао У, Сяолианг Ли, Фэн Гуо, Цзянь У, Джесси Чжан и Венкатеш Рагхаван. 2021. Greenplum: гибридная база данных для транзакционных и аналитических нагрузок (SIGMOD '21). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 2530–2542. https: //doi.org/10.1145/3448016.3457562
[48] Роджер Макакол и Блейн Фрэнч. 2004. Sybase IQ Multiplex - Спроектированный для аналитики. В Материалах Тридцатой международной конференции по очень большим базам данных - Том 30 (Торонто, Канада) (VLDB '04). VLDB Endowment, 1227–1230.
[49] Сергей Мельник, Андрей Губарев, Цзинь Цзинь Лонг, Гефри Ромер, Шива Шивакумар, Мэтт Толтон, Тео Василакис, Хосейн Ахмади, Дэн Делори, Слава Мин, Моша Пасумански и Джеф Шут. 2020. Dremel: Десятилетие интерактивного SQL-анализа в масштабах Интернета. Proc. VLDB Endow. 13, 12 (авг. 2020), 3461–3472. https://doi.org/10.14778/3415478.3415568
[50] Microsoft. 2024. Язык запросов Kusto. Получено 2024-06-20 с https: //github.com/microsoft/Kusto-Query-Language
[51] Гвидо Меркотте. 1998. Малые материализованные агрегаты: легкая структура индекса для хранения данных. В Материалах 24-й Международной конференции по очень большим базам данных (VLDB '98). 476–487.
[52] Джалал Мостафа, Сара Вехби, Сурен Чилингарян и Андреас Коппман. 2022. SciTS: бенчмарк для баз данных временных рядов в научных экспериментах и промышленном Интернете вещей. В Материалах 34-й Международной конференции по научному и статистическому управлению данными (SSDBM '22). Статья 12. https: //doi.org/10.1145/3538712.3538723
[53] Томас Нойман. 2011. Эффективная компиляция эффективных планов запросов для современного оборудования. Proc. VLDB Endow. 4, 9 (июнь 2011), 539–550. https://doi.org/10.14778/ 2002938.2002940
[54] Томас Нойман и Майкл Дж. Фрайтаг. 2020. Umbra: система на диске с производительностью в памяти. В 10-й Конференции по инновационным исследованиям в области систем данных, CIDR 2020, Амстердам, Нидерланды, 12-15 января 2020, онлайн-материалы. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p29-neumann cidr20.pdf
[55] Томас Нойман, Тобиас Мюлбауэр и Альфонс Кемпер. 2015. Быстрое сериализуемое многоверсионное управление параллелизмом для систем баз данных в основной памяти. В Материалах Международной конференции ACM SIGMOD по управлению данными 2015 года (Мельбурн, Виктория, Австралия) (SIGMOD '15). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 677–689. https://doi.org/10.1145/2723372. 2749436
[56] LevelDB на GitHub. 2024. LevelDB. Получено 2024-06-20 с https://github. com/google/leveldb
[57] Патрик О'Нил, Элизабет О'Нил, Сюэдонг Чен и Стивен Ревилак. 2009. Бенчмарк схемы звезд и компактирование индексирования фактов. В Оценке производительности и бенчмаркинге. Springer Berlin Heidelberg, 237–252. https: //doi.org/10.1007/978-3-642-10424-4_17
[58] Патрик Е. О'Нил, Эдвард Ю. С. Ченг, Дитер Гавлик и Элизабет Дж. О'Нил. 1996. Структура слияния журналов (LSM-дерево). Acta Informatica 33 (1996), 351–385. https://doi.org/10.1007/s002360050048
[59] Диего Онгаро и Джон Оустерхоут. 2014. В поисках понятного алгоритма консенсуса. В Материалах Конференции USENIX 2014 года (USENIX ATC'14). 305–320. https://doi.org/doi/10. 5555/2643634.2643666
[60] Патрик О'Нил, Эдвард Ченг, Дитер Гавлик и Элизабет О'Нил. 1996. Структура слияния журналов (LSM-дерево). Acta Inf. 33, 4 (1996), 351–385. https: //doi.org/10.1007/s002360050048
[61] Pandas. 2024. Pandas Dataframes. Получено 2024-06-20 с https://pandas. pydata.org/
[62] Педро Педрейра, Орри Эрлинг, Маша Басманова, Кевин Уилфонг, Лаит Сакка, Кришна Пай, Вэй Хэ и Бисвапеш Чатопадхйай. 2022. Velox: единый исполнительный движок Meta. Proc. VLDB Endow. 15, 12 (авг. 2022), 3372–3384. https: //doi.org/10.14778/3554821.3554829
[63] Туомас Пелконен, Скотт Франклин, Джастин Теллер, Пол Кавалларо, Ци Хуанг, Джастин Меза и Каутик Вирарагаван. 2015. Gorilla: быстрая, масштабируемая в памяти база данных временных рядов. Proceedings of the VLDB Endowment 8, 12 (2015), 1816–1827. https://doi.org/10.14778/2824032.2824078
[64] Орестис Полифронью, Аруна Рагхаван и Кеннет А. Росс. 2015. Переосмысление SIMD векторизации для баз данных в основной памяти. В Материалах Международной конференции ACM SIGMOD по управлению данными 2015 года (SIGMOD '15). 1493–1508. https://doi.org/10.1145/2723372.2747645
[65] PostgreSQL. 2024. PostgreSQL - Обертки для внешних данных. Получено 2024-06-20 с https://wiki.postgresql.org/wiki/Foreign_data_wrappers
[66] Марк Раасвельдт, Педро Холанда, Тим Губнер и Ханнес Мюлеизен. 2018. Справедливое тестирование бенчмарков считается сложным: общие ошибки в тестировании производительности баз данных. В Материалах Семинара по тестированию систем баз данных (Хьюстон, Техас, США) (DBTest'18). Статья 2, 6 страниц. https://doi.org/10.1145/3209950.3209955
[67] Марк Раасвельдт и Ханнес Мюлеизен. 2019. DuckDB: Встраиваемая аналитическая база данных (SIGMOD '19). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 1981–1984. https://doi.org/10.1145/3299869.3320212
[68] Jun Rao и Kenneth A. Ross. 1999. Кэш-сознательное индексирование для поддержки решений в основной памяти. В Материалах 25-й Международной конференции по очень большим базам данных (VLDB '99). Сан-Франциско, Калифорния, США, 78–89.
[69] Навин С. Сабарвал и Пийуш Кант Панде. 2020. Работа с языком запросов Prometheus (PromQL). В Мониторинг микросервисов и контейнеризованных приложений. https://doi.org/10.1007/978-1-4842-6216-0_5
[70] Тодд В. Шнейдер. 2022. Данные такси и прокатных автомобилей Нью-Йорка. Получено 2024-06-20 с https://github.com/toddwschneider/nyc-taxi-data
[71] Майк Стоунбрейкер, Даниэль Д. Абади, Адам Бэткин, Сюэдонг Чен, Митч Чернияк, Мигель Феррейра, Эдмон Лау, Амресон Лин, Сэм Мэдден, Элизабет О'Нил, Пэт О'Нил, Алекс Расин, Нга Тран и Стэн Здоник. 2005. C-Store: столбцовая СУБД. В Материалах 31-й Международной конференции по очень большим базам данных (VLDB '05). 553–564.
[72] Teradata. 2024. База данных Teradata. Получено 2024-06-20 с https://www. teradata.com/resources/datasheets/teradata-database
[73] Фредерик Трансир. 2010. Алгоритмы и структуры данных для движков текстового поиска в памяти. Диссертация доктора философии. https://doi.org/10.5445/IR/1000015824
[74] Адриан Вогельзгезанг, Майкл Хауеншильд, Ян Финсис, Альфонс Кемпер, Виктор Лейс, Тобиас Мюльбауэр, Томас Нойман и Мануэль Тен. 2018. Осознайте: как бенчмарки не могут адекватно представлять реальный мир. В Материалах Семинара по тестированию систем баз данных (Хьюстон, Техас, США) (DBTest'18). Статья 1, 6 страниц. https://doi.org/10.1145/3209950.3209952
[75] Веб-сайт LZ4. 2024. LZ4. Получено 2024-06-20 с https://lz4.org/
[76] Веб-сайт PRQL. 2024. PRQL. Получено 2024-06-20 с https://prql-lang.org [77] Тилл Вестманн, Дональд Коссман, Свен Хелмер и Гвидо Меркотте. 2000. Реализация и производительность сжатых баз данных. SIGMOD Rec.
29, 3 (сентябрь 2000), 55–67. https://doi.org/10.1145/362084.362137 [78] Фанцзинь Янг, Эрик Тсехтер, Ксавье Лео, Нельсон Рэй, Гьян Мерлино и Дип Гангули. 2014. Druid: хранилище данных в реальном времени. В Материалах Международной конференции ACM SIGMOD по управлению данными 2014 года (Сноубёрд, Юта, США) (SIGMOD '14). Ассоциация вычислительных машин, Нью-Йорк, Нью-Йорк, США, 157–168. https://doi.org/10.1145/2588555.2595631
[79] Тяньци Чжен, Чжибинь Чжан и Сюэци Ченг. 2020. SAHA: адаптивная хеш-таблица строк для аналитических баз данных. Прикладные науки 10, 6 (2020). https: //doi.org/10.3390/app10061915
[80] Цзинжэнь Чжоу и Кеннет А. Росс. 2002. Реализация операций баз данных с использованием инструкций SIMD. В Материалах Международной конференции ACM SIGMOD по управлению данными 2002 года (SIGMOD '02). 145–156. https://doi.org/10. 1145/564691.564709
[81] Марчин Жуковский, Сандор Хеман, Нiels Нэс и Петер Бонч. 2006. Суперскалярное сжатие кэша в RAM-ЦП. В Материалах 22-й Международной конференции по инженерии данных (ICDE '06). 59. https://doi.org/10.1109/ICDE. 2006.150

АННОТАЦИЯ​

1 ВВЕДЕНИЕ​

2 АРХИТЕКТУРА​

3 УРОВЕНЬ ХРАНЕНИЯ​

3.1 Формат на диске​

3.2 Обрезка данных​

3.3 Преобразование данных во время слияния​

3.4 Обновления и удаления​

3.6 Репликация Данных​

3.7 Соответствие ACID​

4 УРОВЕНЬ ОБРАБОТКИ ЗАПРОСОВ​

4.1 Параллелизация SIMD​

4.2 Многопоточная Параллелизация​

4.3 Параллелизация Многоузловая​

4.4 Глобальная Оптимизация Производительности​

4.5 Изоляция Нагрузки​

5 УРОВЕНЬ ИНТЕГРАЦИИ​

6 ПРОИЗВОДИТЕЛЬНОСТЬ КАК ФУНКЦИЯ​

6.1 Встроенные Инструменты Анализа Производительности​

6.2 Бенчмарки​

6.2.1 Денормализованные таблицы​

6.2.2 Нормализованные таблицы​

7 СВЯЗАННЫЕ РАБОТЫ​

8 ЗАКЛЮЧЕНИЕ И ПЕРСПЕКТИВЫ​

БЛАГОДАРНОСТИ​

ССЫЛКИ​