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

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

АННОТАЦИЯ

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

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

1 ВВЕДЕНИЕ

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

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

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

2. Множество одновременных запросов с ожиданием низких задержек. Запросы обычно можно разделить на временные (например, исследовательский анализ данных) или повторяющиеся (например, периодические запросы для панелей мониторинга). Чем более интерактивен сценарий использования, тем ниже ожидаются задержки запросов, что создает сложности в оптимизации и выполнении запросов. Повторяющиеся запросы дополнительно предоставляют возможность адаптировать физическую структуру базы данных к рабочей нагрузке. В результате базы данных должны предлагать методы обрезки, позволяющие оптимизировать частые запросы. В зависимости от приоритета запроса базы данных должны далее предоставлять равный или приоритетный доступ к общим системным ресурсам, таким как CPU, память, диск и ввод-вывод по сети, даже если работает большое количество запросов одновременно.

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

4. Удобный язык запросов с поддержкой производительности. Реальное использование OLAP баз данных предъявляет дополнительные «мягкие» требования. Например, вместо нишевого языка программирования пользователи часто предпочитают взаимодействовать с базами данных на выразительном SQL-диалекте с вложенными типами данных и широким диапазоном регулярных, агрегатных и оконных функций. Аналитические базы данных также должны предоставлять продвинутое инструментальное обеспечение для анализа производительности системы или отдельных запросов.

5. Устойчивость на уровне отрасли и универсальное развертывание. Поскольку обычное оборудование ненадежно, базы данных должны предоставлять репликацию данных для устойчивости к сбоям узлов. Кроме того, базы данных должны работать на любом оборудовании, от старых ноутбуков до мощных серверов. Наконец, чтобы избежать накладных расходов на сбор мусора в программах на основе JVM и обеспечить производительность «близко к металлу» (например, SIMD), базы данных идеальнее всего развертываются как нативные двоичные файлы для целевой платформы.

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

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

Рисунок 2: Общая архитектура движка базы данных ClickHouse.

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

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

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

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

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

ClickHouse поддерживает шардирование и репликацию таблиц через несколько узлов кластера для масштабирования и доступности. Шардирование делит таблицу на набор частей таблицы в соответствии с выражением шардирования. Отдельные шард являются независимыми таблицами и обычно расположены на разных узлах. Клиенты могут непосредственно читать и записывать шард, т.е. рассматривать их как отдельные таблицы, или использовать специальный движок таблицы Distributed, который предоставляет глобальный обзор всех частей таблиц. Основная цель шардирования — обрабатывать наборы данных, превышающие емкость отдельных узлов (обычно несколько десятков терабайт данных). Другой вариант использования шардирования — распределить нагрузку на чтение и запись таблицы между несколькими узлами, т.е. осуществлять балансировку нагрузки. Параллельно этому шарды могут быть реплицированы через несколько узлов для устойчивости к сбоям узлов. Для этой цели у каждого движка таблицы 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 [37] с DataFrames от Pandas [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 МБ), т.е. количество гранул в блоке является переменным и зависит от типа данных колонки и распределения. Блоки также сжимаются, чтобы уменьшить их размер и затраты на I/O. По умолчанию ClickHouse использует LZ4 [75] как универсальный алгоритм сжатия, но пользователи также могут указать специализированные кодеки, такие как Gorilla [63] или FPC [12] для данных с плавающей запятой. Алгоритмы сжатия также могут комбинироваться. Например, можно сначала уменьшить логическую избыточность в числовых значениях с использованием кодирования дельты [23], затем выполнить тяжелое сжатие и, наконец, зашифровать данные с использованием кодека AES. Блоки распаковываются на лету, когда они загружаются с диска в память. Чтобы обеспечить быстрый случайный доступ к отдельным гранулам, несмотря на сжатие, ClickHouse дополнительно хранит для каждой колонки отображение, которое связывает каждый идентификатор гранулы с смещением её содержащего сжатого блока в файле колонки и смещением гранулы в несжатом блоке.

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

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

3.2 Удаление Данных

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

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

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

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

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

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

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 на основе битмап-контракта, чтобы исключить удаленные строки из результата. Удаленные строки физически удаляются только при регулярных слияниях в неопределенное время в будущем. В зависимости от количества колонок легковесные удаления могут быть намного быстрее, чем мутации, за счет более медленных SELECT.

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

3.5 Идемпотентные Вставки

Одна из проблем, которая часто возникает на практике, — это то, как клиенты должны обрабатывать тайм-ауты соединения после отправки данных на сервер для вставки в таблицу. В этой ситуации клиентам трудно различать, были ли данные успешно вставлены или нет. Проблема традиционно решается повторной отправкой данных от клиента к серверу и использованием первичных ключей или уникальных ограничений для отклонения дублирующихся вставок. Базы данных быстро выполняют необходимые точечные проверки, используя структуры индексов, основанные на двоичных деревьях [39, 68], деревьях радиусов [45] или хеш-таблицах [29]. Поскольку эти структуры данных индексируют каждый кортеж, их пространственные и обновляемые накладные расходы становятся непомерными для больших наборов данных и высоких темпов приема.

ClickHouse предоставляет более легковесную альтернативу, основываясь на том, что каждая вставка в конечном итоге создает часть. Более конкретно, сервер поддерживает хеши N последней вставленной части (например, N=100) и игнорирует повторные вставки частей с известным хешем. Хеши для нереплицированных и реплицированных таблиц хранятся локально соответственно в Keeper. В результате вставки становятся идемпотентными, т.е. клиенты могут просто повторно отправить ту же партию строк после тайм-аута и предположить, что сервер позаботится о дедупликации. Для большего контроля над процессом дедупликации клиенты могут дополнительно предоставить токен вставки, который выступает в качестве хеша части. Хотя дедупликация на основе хеша влечет за собой накладные расходы, связанные с хешированием новых строк, стоимость хранения и сравнения хешей незначительна.

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

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

Журнал репликации поддерживается ансамблем из обычно трех процессов 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-запроса к таблице со статистикой просмотров страниц. На первом этапе три неперекрывающихся диапазона исходной таблицы фильтруются одновременно. Оператор обмена перераспределения динамически направляет части результатов между первым и вторым этапами, чтобы поддерживать равномерную загрузку потоков обработки. Дорожки могут стать неравномерными после первого этапа, если отсканированные диапазоны имеют существенно разные селективности. На втором этапе строки, которые выжили после фильтрации, группируются по RegionID. Операторы агрегации поддерживают локальные группы результатов с RegionID в качестве колонки группировки и суммами и счетчиками на группу в качестве частичного состояния агрегации для avg(). Локальные результаты агрегации в конечном итоге объединяются оператором GroupStateMerge в глобальный результат агрегации. Этот оператор также является нарушителем конвейера, т.е. третий этап может начаться только тогда, когда результат агрегации был полностью вычислен. На третьем этапе группы результатов сначала делятся оператором Distribute на три равные большие неперекрывающиеся партиции, которые затем сортируются по AvgLatency. Сортировка выполняется в три этапа: Во-первых, операторы ChunkSort сортируют отдельные части каждой партиции. Во-вторых, операторы StreamSort поддерживают локальный отсортированный результат, который комбинируется с входящими отсортированными частями с использованием 2-ходовой слияния. Наконец, оператор MergeSort объединяет локальные результаты, используя k-ходовое сортировку, чтобы получить окончательный результат.

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

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

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

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

4.3 Параллелизация на нескольких узлах

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

Узлы 2 ... N на Рисунке 8 показывают фрагменты плана, выполняемые на других узлах, содержащих шард таблицы. Эти узлы фильтруют и группируют локальные данные и отправляют результат инициирующему узлу. Оператор 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 и помогает предсказателю ветвлений, так как кода для выполнения требуется меньше. Кроме того, компиляция во время выполнения позволяет реализовать широкий набор оптимизаций, таких как логические оптимизации и оптимизации "взгляда в щель", реализованные в компиляторах, и предоставляет доступ к самым быстрым доступным локально инструкциям 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. Этап поиска находит целевую партицию для своих входных кортежей аналогично. Хотя этот алгоритм вводит два дополнительных вычисления хеша на кортеж, он значительно уменьшает конкуренцию за блокировки на этапе сборки в зависимости от количества разделов хеш-таблицы.

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

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

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

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

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

Наконец, планирование ввода-вывода позволяет пользователям ограничивать локальный и удаленный доступ к дискам для классов нагрузки на основе максимальной пропускной способности, входящих запросов и политики (например, 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 wire-протоколами. Эта функция совместимости полезна для обеспечения доступа от собственных приложений (например, некоторых инструментов бизнес-аналитики), где вендоры еще не реализовали нативное подключение к ClickHouse.

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

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

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

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

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

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

Интеграция с 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, I/O или памятью.

Рисунок 10 показывает общее относительное холодное и горячее время выполнения для последовательного выполнения всех запросов ClickBench в базах данных, которые часто используются для аналитики. Измерения проводились на одной узловой инстанции AWS EC2 c6a.4xlarge с 16 vCPUs, 32 ГБ ОЗУ и диском на 5000 IOPS / 1000 МиБ/с. Сравнимые системы использовались для Redshift (ra3.4xlarge, 12 vCPUs, 96 ГБ ОЗУ) и Snowfake (размер склада S: 2x8 vCPUs, 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 vCPUs, 128 ГБ ОЗУ и диском на 5000 IOPS / 1000 МиБ/с. Зафиксировано самое быстрое из пяти запусков. Для справки мы провели те же измерения в системе Snowfake сопоставимого размера (размер склада L, 8x8 vCPUs, 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.

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

Аналитические базы данных вызывали большой академический и коммерческий интерес в последние десятилетия [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. Интеграция сжатия и выполнения в столбцовых системах баз данных. В материалах 2006 года ACM SIGMOD Международной Конференции по Управлению Данными (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. Дизайн и оценка алгоритмов хеш-соединения в основной памяти для многоядерных ЦП. В материалах 2011 года ACM SIGMOD Международной Конференции по Управлению Данными (Афины, Греция) (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] Петер Бонц, Марцин Жуковский и Нильс Несс. 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] Бенуа Дажевиль, Тьерри Крюанес, Марцин Жуковский, Вадим Антонов, Артин Авенес, Джон Бок, Джонатан Клейбауг, Даниил Энговатав, Мартин Хентшель, Цзяньшэн Хуанг, Элисон В. Ли, Ашиш Мотивал, Абдул Q. Мюнир, Стивен Пелли, Петер Повинец, Грег Ран, Спиридон Триантафиллис и Филипп Унтербруннер. 2016. Snowfake Elastic Data Warehouse. В материалах 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: Сравнительное Исследование Двух Промышленных Референсных Реализаций Публикации/Подписки: Промышленная Статья (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-digest: эффективные оценки распределений. 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 vol. 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 Ноутбуки. Получено 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: Быстрая архитектурно-чувствительная проверка деревьев на современных ЦП и ГП. В материалах 2010 года ACM SIGMOD Международной конференции по Управлению Данными (Индианаполис, штат Индиана, США) (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. Параллелизм на уровне долей:_framework для оценки запросов, учитывающий архитектуру NUMA для многопроцессорных систем. В материалах 2014 года ACM SIGMOD Международной конференции по Управлению Данными (Сноубird, Юта, США) (SIGMOD '14). Ассоциация вычислительной техники, Нью-Йорк, Нью-Йорк, США, 743–754. https://doi.org/10.1145/2588555. 2610507
• [45] Виктор Лейс, Альфонс Кемпер и Томас Нойман. 2013. Адаптивное радикс-дерево: искусная индексация для баз данных в основной памяти. В 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/ 2002938.2002940
• [54] Томас Нойман, Тобиас Мюльбауэр и Альфонс Кемпер. 2020. Umbra: Система на диске с производительностью в памяти. В 10-й Конференции по Инновационным Исследованиям Систем Данных, CIDR 2020, Амстердам, Нидерланды, 12-15 января 2020 года, Онлайн Материалы. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p29-neumanncidr20.pdf
• [55] Томас Нойман, Тобиас Мюльбауэр и Альфонс Кемпер. 2015. Быстрый сериализуемый контроль многоверсионного параллелизма для систем баз данных в основной памяти. В материалах 2015 года ACM SIGMOD Международной конференции по Управлению Данными (Мельбурн, Виктория, Австралия) (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. В поисках понятного алгоритма консенсуса. В материалах 2014 года USENIX Конференции по Техническим Исследованиям USENIX (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: Быстрая, Масштабируемая, В Памяти База Данных Временных Рядов. Материалы VLDB Endowment 8, 12 (2015), 1816–1827. https://doi.org/10.14778/2824032.2824078
• [64] Орестис Полихрониу, Арун Рагхаван и Кеннет А. Росс. 2015. Переосмысление SIMD-векторизации для баз данных в основной памяти. В материалах 2015 года ACM SIGMOD Международной конференции по Управлению Данными (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] Джун Рао и Кеннет А. Росс. 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: Магазин Аналитических Данных В Реальном Времени. В материалах 2014 года ACM SIGMOD Международной конференции по Управлению Данными (Сноубирд, Юта, США) (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. В материалах 2002 года ACM SIGMOD Международной конференции по Управлению Данными (SIGMOD '02). 145–156. https://doi.org/10. 1145/564691.564709
• [81] Марцин Жуковский, Сандор Хеман, Нильс Несс и Петер Бонц. 2006. Сжатие Кэша RAM-ЦП Суперскалярным. В материалах 22-й Международной конференции по Инженерии Данных (ICDE '06). 59. https://doi.org/10.1109/ICDE. 2006.150