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