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

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

АННОТАЦИЯ

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

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

1 ВВЕДЕНИЕ

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

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

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

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

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). Виртуальные движки также могут взаимодействовать с Data Lakes (например, Iceberg, DeltaLake, Hudi [36]) или файлами в объектном хранилище (например, AWS S3, Google GCP).

ClickHouse поддерживает шардирование и репликацию таблиц по нескольким узлам кластера для масштабируемости и доступности. Шардирование разбивает таблицу на набор шардов таблицы в соответствии с выражением шардирования. Отдельные шары являются взаимозависимыми таблицами и обычно находятся на различных узлах. Клиенты могут читать и писать шард, непосредственно обращаясь с ними, то есть рассматривать их как отдельные таблицы, или использовать специальный движок таблицы Distributed, который предоставляет глобальный обзор всех шардов таблицы. Основная цель шардирования - обрабатывать наборы данных, которые превышают возможности отдельных узлов (обычно несколько десятков терабайт данных). Другим использованием шардирования является распределение нагрузки на чтение и запись по таблице между несколькими узлами, то есть распределение нагрузки. Параллельно с этим, шарды могут быть реплицированы на нескольких узлах для обеспечения устойчивости к сбоям узлов. Для этой цели каждый движок таблиц MergeTree* имеет соответствующий движок 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 DataFrames [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] или быть допускающими значение 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]. Проекции позволяют ускорять запросы, которые фильтруют по колонкам, отличным от первичного ключа главной таблицы, при этом увеличивая накладные расходы на вставки, слияния и потребление памяти. По умолчанию проекции заполняются лениво только из частей, недавно вставленных в главную таблицу, но не из существующих частей, если пользователь не материализует проекцию в полном объеме. Оптимизатор запросов выбирает между чтением из главной таблицы или проекции на основе оцененных затрат ввода-вывода. Если проекции для части не существует, выполнение запроса откатится к соответствующей главной части таблицы.

В-третьих, индексы пропуска предоставляют легковесную альтернативу проекциям. Идея индексов пропуска заключается в том, чтобы хранить небольшое количество метаданных на уровне нескольких последовательных гранул, что позволяет избежать сканирования нерелевантных строк. Индексы пропуска могут быть созданы для произвольных выражений индексации и с настраиваемой гранулярностью, т.е. количеством гранул в блоке индекса пропуска. Доступные типы индексов пропуска включают: 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) обеспечивают постарение исторических данных. В отличие от удаления и агрегации, слияния с учетом времени жизни обрабатывают только одну часть за раз. Слияния с учетом времени жизни определяются в терминах правил с триггерами и действиями. Триггер - это выражение, вычисляющее временную метку для каждой строки, которая сравнивается со временем, когда выполняется слияние с учетом времени жизни. Хотя это позволяет пользователям контролировать действия на уровне строк, мы нашли достаточным проверить, удовлетворяют ли все строки заданному условию, и выполнять действие на всей части. Возможные действия включают в себя 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: Репликация в кластере из трех узлов.

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

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. Операторы Aggregating поддерживают локальные группы результатов с 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).

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

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

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

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

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

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

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

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

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

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

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

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

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 и различные Data Lakes. Мы делим их на категории, показанные на следующем бонусном рисунке (не входящем в оригинальную статью VLDB).

Бонусный рисунок: Возможности взаимосвязи ClickBench.

Временный доступ с помощью интеграции табличных функций. Табличные функции могут вызываться в блоке FROM SQL-запросов для чтения удаленных данных в рамках исследовательских запросов. Кроме того, они могут использоваться для записи данных в удаленные хранилища с помощью операторов 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,typical нагрузку такого рода, которая имитирует ad-hoc и периодические запросы отчетности, используемые в анализе кликов и трафика. Бенчмарк состоит из 43 запросов к таблице с 100 миллионами анонимизированных обращений к страницам, взятым с одной из крупнейших аналитических платформ в Интернете. Онлайн панель управления [17] показывает измерения (время выполнения холодного/горячего, время импорта данных, размер на диске) для более чем 45 коммерческих и исследовательских баз данных по состоянию на июнь 2024 года. Результаты помещаются независимыми участниками на основе общедоступного набора данных и запросов [16]. Запросы тестируют последовательные и индексные пути доступа и регулярно проявляют релевантные операторы, ограниченные ЦП, вводом-выводом или памятью.

Рисунок 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 ГБ ОЗУ). Физический дизайн базы данных подстраивается только незначительно, например, мы указываем первичные ключи, но не изменяем сжатие отдельных колонок, не создаем проекции и не используем skipping indexes. Мы также очищаем кеш страниц 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.

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, полагая, что пользователи делают широкий использование обрезки данных для ускорения частых запросов и что затраты I/O преобладают над затратами на декомпрессию для остальных запросов. DuckDB также предоставляет сериализуемые транзакции на основе схемы MVCC Hyper [55], тогда как ClickHouse предлагает только изоляцию по снимкам.

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

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

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

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

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

ССЫЛКИ

• [1] Дэниел Абади, Петер Бонcz, Ставрос Харизопулос, Стратос Идряос и Самуэль Мэдден. 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, Сан-Франциско, Калифорния, США, 169–180.
• [4] Никос Арменатцоглу, Санудж Басу, Нага Бханури, Менгчу Цай, Нуреш Чайани, Кирсан Чинта, Венкатраман Говиндараджу, Тодд Дж. Грин, Мониш Гупта, Себастьян Хиллиг, Эрик Хотингер, Ян Лешинский, Цзиньтянь Лян, Майкл МакКриди, Фабиан Нагель, Иппократис Пандис, Папос Пархас, Рахул Патхак, Орестис Полиохрониу, Фойзур Рахман, Гаурава Саксенa, Гокул Саундарвараджан, Сирим Субраманиан и Дуг Терри. 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://benchmark.clickhouse.com/versions/
• [20] ClickHouse. 2024. Бенчмарк версий ClickHouse. Извлечено 2024-06-20 с https://github.com/ClickHouse/ClickBench/tree/main/versions
• [21] Эндрю Кротти. 2022. MgBench. Извлечено 2024-06-20 с https://github.com/ andrewcrotty/mgbench
• [22] Бенуа Дажевиль, Тьерри Круанес, Марцин Зуковски, Владимир Антонов, Артин Авенес, Джон Бокк, Джонатан Клейбо, Даниэль Энговаттов, Мартин Хентшель, Цзяньшэн Хуан, Эллисон В. Ли, Ашиш Мотива́ла, Абдул К. Муннир, Стивен Пелли, Петер Повинец, Грег Ран, Спиридон Триантафиллис и Филипп Унтербруннер. 2016. Эластичный склад данных Snowfake. В материалах международной конференции 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] Мартин Фауст, Мартин Буа зиер, Марвин Келлер, Дэвид Швальб, Хольгер Бишоф, Katrin Eisenreich, Франц Фэрбер и Хассо Платтнер. 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 году на 34-й международной конференции IEEE по обработке данных (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. Адаптивное древовидное индексирование: ARTful индексация для баз данных в основной памяти. В 2013 году на 29-й международной конференции IEEE по обработке данных (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] Майкрософт. 2024. Язык запросов Kusto. Извлечено 2024-06-20 с https: //github.com/microsoft/Kusto-Query-Language
• [51] Гвидо Меркотте. 1998. Малые материализованные агрегаты: легковесная структура индекса для складов данных. В материалах 24-й международной конференции по очень большим базам данных (VLDB '98). 476–487.
• [52] Джалал Мостафa, Сара Вехби, Сурен Чилингарян и Андреас Копманн. 2022. SciTS: Бенчмарк для баз данных временных рядов в научных экспериментах и промышленных IoT. В материалах 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] Патрик Е. О'Нил, Эдвард Y. C. Чен, Дитер Гавлик и Элизабет Дж. О'Нил. 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: быстрое, масштабируемое, встроенное хранилище временных рядов. Материалы 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] Цзюнь Рао и Кеннет А. Росс. 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] Тилл Вестманн, Дональд Коссмaнн, Свен Хельмер и Гвидо Меркотте. 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