Моя команда использует ClickHouse как хранилище для 100 млрд записей с трафиком по 300 млн в сутки и поиском по таблице. Я расскажу об устройстве движка таблиц MergeTree. Рассказ буду вести, показывая физические данные, а не абстрактные схемы.

MergeTree — это сердце ClickHouse, остальные движки скорее вспомогательные. Название отсылает к LSM-дереву, которое давно используется в других СУБД.

Последовательный доступ решает, даже для SSD

ClickHouse задумывался для аналитики, под большую пропускную способность записи и чтения. Чтобы получить максимальную пропускную способность записи можно просто писать в конец файла, без поддержания всяких индексов и произвольных seek’ов, но как без них обеспечить скорость чтения? Ведь поиск по произвольным данным без индекса быстрым быть не может. Получается, нужно либо упорядочивать в момент вставки, либо фуллсканить в момент чтения. Оба варианта гробят пропускную способность. ClickHouse решил упорядочивать посередине: в фоне.

Так и появился компромисс в виде MergeTree: пишем на диск небольшие куски отсортированных данных, которые ClickHouse сливает в фоне для поддержания упорядоченности.

Концептуальная идея, надеюсь, ясна, приступим к рассмотрению работы MergeTree под микроскопом.

Лабораторная работа

Достанем из-под парты ClickHouse версии 20.8.9.6 и создадим таблицу с небольшим числом колонок. В качестве первичного ключа выберем user_id. ClickHouse создал папку /var/lib/clickhouse/data/default/clicks.

Про index_granularity — чуть позже.

create table clicks
(
    date      DateTime,
    user_id   Int64,
    banner_id String
) engine = MergeTree() order by user_id settings index_granularity = 2;

Вставим 10 строчек:

+-------------------+-------+---------+
|date               |user_id|banner_id|
+-------------------+-------+---------+
|2021-01-01 15:43:58|157    |lqe(|    |
|2021-01-01 15:45:38|289    |freed    |
|2021-01-01 15:47:18|421    |08&N0    |
|2021-01-01 15:48:58|553    |n5UD$    |
|2021-01-01 15:50:38|685    |1?!Up    |
|2021-01-01 15:52:18|817    |caHy6    |
|2021-01-01 15:53:58|949    |maXZD    |
|2021-01-01 15:55:38|1081   |Fx:BO    |
|2021-01-01 15:57:18|1213   |\v8j+    |
|2021-01-01 15:58:58|1345   |szEG)    |
+-------------------+-------+---------+

На диске появился один кусок данных (data part) all_1_1_0. Посмотрим, из чего он состоит:

all — название партиции. Поскольку выражения партиционирования в CREATE TABLE мы не задали, вся таблица будет в одной партиции.
1_1 — это срез блоков, который хранится в парте.
0 — это уровень в дереве слияний. Нулевой уровень у первых «протопартов», если два парта слить, то их уровень увеличится на 1.

all_1_1_0/
├── banner_id.bin
├── banner_id.mrk2
├── checksums.txt
├── columns.txt
├── count.txt
├── date.bin
├── date.mrk2
├── primary.idx
├── user_id.bin
└── user_id.mrk2

Появился первичный индекс primary.idx и по два файла на каждую колонку: mrk2 и bin.

columns.txt — информация о колонках.
count.txt — число строк в куске.

Первичный индекс primary.idx, он же разрежённый

В primary.idx лежат засечки: отсортированные значения выражения первичного ключа, заданного в CREATE TABLE, для каждой index_granularity строки: для строки 0, index_granularity, index_granularity*2 и т.д. Размер гранулы index_granularity — это степень разреженности индекса primary.idx. Для каждого запроса ClickHouse читает с диска целое количество гранул. Если задать большой размер гранулы, будет прочитано много лишних строк, если маленький — увеличится размер первичного индекса, который хранится в оперативке для быстродействия.

Последняя засечка (здесь 1345) нужна, чтобы знать, на чём заканчивается таблица.
od -i просто отображает байты как целые положительные четырёхбайтные числа.

od -i all_1_1_0/primary.idx
0000000               157               0             421               0
0000020               685               0             949               0
0000040              1213               0            1345               0
0000060

Файлы данных .bin

Файлы bin содержат значения колонок, отсортированные по выражению первичного ключа, в нашем случае — user_id. Данные хранятся в сжатом виде, единица сжатия — блок. N-ое значение принадлежит к N-ой строке.

banner_id.bin:

cat  all_1_1_0/banner_id.bin | clickhouse-compressor -d | od -a
0000000  enq   l   q   e   (   | enq   f   r   e   e   d enq   0   8   &
0000020    N   0 enq   n   5   U   D   $ enq   1   ?   !   U   p enq   c
0000040    a   H   y   6 enq   m   a   X   Z   D enq   F   x   :   B   O
0000060  enq   \   v   8   j   + enq   s   z   E   G   )

user_id.bin:

cat  all_1_1_0/user_id.bin | clickhouse-compressor -d | od -i
0000000               157               0             289               0
0000020               421               0             553               0
0000040               685               0             817               0
0000060               949               0            1081               0
0000100              1213               0            1345               0

Ну и date.bin, в виде epoch-time:

cat  all_1_1_0/date.bin | clickhouse-compressor -d | od -i
0000000        1609515838      1609515938      1609516038      1609516138
0000020        1609516238      1609516338      1609516438      1609516538
0000040        1609516638      1609516738
0000050
#от пятница,  1 января 2021 г. 15:43:58 (UTC) 
#до пятница,  1 января 2021 г. 15:58:58 (UTC)

Стоп, а почему данные отсортированы? Ведь мы вставляли строки в произвольном порядке? Дело в том, что ClickHouse сортирует вставляемые строки в оперативке с использованием красно-чёрного дерева, и время от времени сбрасывает его на диск в виде immutable дата-парта.

Есть DELETE и UPDATE, но эти команды не для рутинного использования, они работают в фоне, и не меняют старые парты, а создают новые.

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

Файлы засечек .mrk2

Для каждой засечки из primary.idx mrk2 знает, где именно в bin-файле начинаются значения соответствующей колонки.

Засечка в mrk2 состоит из 3 положительных 8-битных чисел, всего 24 байта: смещение блока в bin-файле, смещение в разжатом блоке и количество строк в грануле. Третье число пока не важно.

Читаем третью засечку:

#читаем 24 байта как числа long начиная с 48 байт смещения
od -l -j 48 -N 24 all_1_1_0/user_id.mrk2
0000060                                 0                              32
0000100                                 2
0000110

Пройдём по этому указателю, пропустив 32 байта в нулевом блоке:

cat  all_1_1_0/user_id.bin | clickhouse-compressor -d |od -j 32 -i -N 4
0000040               685
0000044

Видим значение первичного ключа из четвёртой строки. Это и есть начало третьей засечки в primary.idx!

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

Поиск по MergeTree

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

Видно, что 982 лежит между гранулами 949 и 1213, поэтому можно прочесть только одну гранулу:

--включаем логи в clickhouse-client
set send_logs_level = 'trace';

SELECT *
FROM clicks
WHERE user_id = 982

Selected 1 parts by date, 1 parts by key, 1 marks by primary key, 1 marks to read from 1 ranges
Reading approx. 2 rows with 1 streams

А вот если сделать поиск по колонке вне первичного ключа, придётся делать фуллскан:

SELECT *
FROM clicks
WHERE banner_id = 'genbykj[';

Selected 1 parts by date, 1 parts by key, 5 marks by primary key, 5 marks to read from 1 ranges
Reading approx. 10 rows with 1 streams

Это делает ClickHouse СУБД плохо справляющейся с точечными запросами, ведь приходится читать много лишних строк. Если размер гранулы по умолчанию 8192, а в результате только одна строка, то эффективность чтения 1/8192 = 0.0001.

Партиции

Теперь разберемся, что такое партиции. Добавим выражение партиционирования в CREATE TABLE, обрезая дату до дня:

create table clicks
(
    date      DateTime,
    user_id   Int64,
    banner_id String
) engine = MergeTree() order by user_id partition by toYYYYMMDD(date);
+-------------------+-------+---------+
|date               |user_id|banner_id|
+-------------------+-------+---------+
|2021-01-16 13:34:29|157    ||^/g~    |
|2021-01-16 18:51:09|289    |/y;ny    |
|2021-01-17 00:07:49|421    |@7bbc    |
|2021-01-17 05:24:29|553    |.[e/{    |
|2021-01-17 10:41:09|685    |0Wj)m    |
|2021-01-17 15:57:49|817    |W6@Oo    |
|2021-01-17 21:14:29|949    |tvQZ&    |
|2021-01-18 02:31:09|1081   |ZPeCE    |
|2021-01-18 07:47:49|1213   |H|$PI    |
|2021-01-18 13:04:29|1345   |a'0^J    |
+-------------------+-------+---------+

После вставки 10 строк, на диске появились три парта вместо одного: на 16, 17, 18 января 2021 года:

clicks
├── 20210116_1_1_0
├── 20210117_2_2_0
├── 20210118_3_3_0

Внутри парты такие же, как и без партиционирования, но добавился файл, хранящий партицию, к которой относится парт:

cat clicks/20210118_3_3_0/partition.dat | od -i
0000000    20210118
0000004

И minmax индекс по дате, в котором хранятся минимальное и максимальное значение даты в парте:

od -i 20210116_1_1_0/minmax_date.idx
0000000  1610804069  1610823069
0000010
date --utc -d @1610804069
Sat Jan 16 13:34:29 UTC 2021
date --utc -d @1610823069
Sat Jan 16 18:51:09 UTC 2021

Теперь посмотрим, как партиции помогают в поиске:

--запрос по выражению, участвующего в партиционировании
SELECT *
FROM clicks
WHERE (date >= toUnixTimestamp('2021-01-17 00:00:00', 'UTC')) AND (date < toUnixTimestamp('2021-01-17 16:00:00', 'UTC'))
--зная границы дат каждого парта, легко узнать, какие парты читать не нужно
MinMax index condition: (column 0 in [1610841600, +inf)), (column 0 in (-inf, 1610899199]), and
Not using primary index on part 20210117_2_2_0
Selected 1 parts by date, 1 parts by key, 1 marks by primary key, 1 marks to read from 1 ranges
Reading approx. 8192 rows with 1 streams
┌────────────────date─┬─user_id─┬─banner_id─┐
│ 2021-01-17 03:07:49 │     421 │ @7bbc     │
│ 2021-01-17 08:24:29 │     553 │ .[e/{     │
│ 2021-01-17 13:41:09 │     685 │ 0Wj)m     │
│ 2021-01-17 18:57:49 │     817 │ W6@Oo     │
└─────────────────────┴─────────┴───────────┘
Read 4 rows, 104.00 B in 0.002051518 sec., 1949 rows/sec., 49.51 KiB/sec.

--запрос без участия партиций
SELECT *
FROM clicks
WHERE banner_id = 'genbykj['
--приходится читать все парты, в три параллельных потока
Not using primary index on part 20210117_2_2_0
Not using primary index on part 20210116_1_1_0
Not using primary index on part 20210118_3_3_0
Selected 3 parts by date, 3 parts by key, 3 marks by primary key, 3 marks to read from 3 ranges
Reading approx. 24576 rows with 3 streams
Read 10 rows, 140.00 B in 0.001798808 sec., 5559 rows/sec., 76.01 KiB/sec.

Дата-парты также удобно смотреть через системную таблицу:

SELECT name, rows, min_time, max_time
FROM system.parts
WHERE table = 'clicks'

┌─name───────────┬─rows─┬────────────min_time─┬────────────max_time─┐
│ 20210116_1_1_0 │    2 │ 2021-01-16 16:34:29 │ 2021-01-16 21:51:09 │
│ 20210117_2_2_0 │    4 │ 2021-01-17 03:07:49 │ 2021-01-17 18:57:49 │
│ 20210118_3_3_0 │    4 │ 2021-01-18 00:14:29 │ 2021-01-18 16:04:29 │
└────────────────┴──────┴─────────────────────┴─────────────────────┘

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

Слияние дата-партов

Для того, чтобы количество партов не разрасталось, ClickHouse производит фоновое слияние кусков. При слиянии также срабатывает логика в Replacing, Summing, Collapsing и других вариациях движка MergeTree. При слиянии двух отсортированных партов появляется один отсортированный.

--остановим процесс слияния и вставим строк
system stop merges clicks;
insert into clicks(date, user_id, banner_id) 
select now() , number * 132 + 157, randomPrintableASCII(5)
from system.numbers limit 50;
Ok.
--появился 1 парт
+--------------+------+
|name          |active|
+--------------+------+
|20210116_1_1_0|1     |
+--------------+------+

--вставим ещё строк
insert into clicks(date, user_id, banner_id)  
select now() , number * 132 + 157, randomPrintableASCII(5) 
from system.numbers limit 50;

--уже 2 парта
+--------------+------+
|name          |active|
+--------------+------+
|20210116_1_1_0|1     |
|20210116_2_2_0|1     |
+--------------+------+

--возобновим процесс слияния
system start merges clicks;
-- и попросим ClickHouse запустить слияние
optimize table clicks final;

--через некоторое время видим, что два парта слились в один 20210116_1_2_1, у которого увеличился уровень. 
--Неактивные парты будут удалены со временем.
+--------------+------+----+
|name          |active|rows|
+--------------+------+----+
|20210116_1_1_0|0     |50  |
|20210116_1_2_1|1     |100 |
|20210116_2_2_0|0     |50  |
+--------------+------+----+

Выводы

Я осветил базовые конструкции, как видим, никакой магии нет. Идея MergeTree стара и проста как сам LSM. Всем рекомендую пользоваться!

ClickHouse: как устроен MergeTree