Моя команда использует 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. Всем рекомендую пользоваться!
Автор: yonesko
