Инкрементальная агрегация данных в памяти

1 Введение


В последнее время аналитические системы являются очень востребован ными и используются повсеместно. Чаще всего самой важной частью таких систем является аналитическая база данных, в которую записываются все собы тия самых разных видов, происходящих в системе. Аналитическая база данных позволяет интерактивно выполнять запросы на этих данных, то есть выдавать результат, содержащий информацию о всех поступивших на текущий момент данных. Такой подход к аналитическим задачам называется интерактивной ана литической обработкой [1], и часто подразумевает, что записанные данные не модифицируются. В этой работе рассматривается агрегация данных, которая является важной частью аналитической обработки.


1.1 Актуальность

Распространенный паттерн использования аналитической системы заключается в агрегировании всех данных для подсчета статистики, группируя дан ные по стране, городу, или одному IPадресу. Для этого обычно выполняется GROUP BY запрос на языке SQL, доступный в большинстве реляционных баз данных. Он позволяет группировать строки согласно некоторому выражению, и считать любые поддерживаемые статистики на этих данных.

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

Хороший пример, в котором требуется частая агрегация на свежих данных это системы антифрода и борьбы с мошенничеством. Такие системы агреги руют все поступающие события чтобы построить разные статистики, и с помощью этих статистик ищут активности, которые являются мошенническими с большой вероятностью [2]. Примером такой статистики является число уни кальных IPадресов для одного пользователя. Если один пользователь соверша ет много запросов с разных адресов, это говорит о том, что это скорее всего не настоящий пользователь, а робот, который генерирует мошенническую актив ность.

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


1.2 Краткое описание работы

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


1.3 Цели и задачи

Целью работы является добавление поддержки в ClickHouse возможности инкрементальной агрегации в памяти.

Перед нами были поставлены следующие задачи:


• Исследовать существующие подходы к агрегации в ClickHouse и других системах

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

• Реализовать поддержку использования этого движка вместе с материали зованными представлениями

• Протестировать новый функционал в разных сценариях использования


• Добавить в движок поддержку быстрого чтения по ключу


• Оценить производительность нового решения, измерив время обработки запросов и используемые ресурсы

• Сравнить производительность нового и существующих подходов для ре шения задачи определения подозрительной активности

• Подготовить пользовательскую документацию



1.4 Полученные результаты

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

Также были получены следующие результаты:


• Реализована поддержка использования материализованных представле ний вместе с новым движком

• Написаны работающие тесты функциональности инкрементальной агре гации

• Проведены тесты производительности, показывающие эффективность но вого способа агрегации по сравнению с существующими

• Подготовлен и выложен на GitHub исходный код, реализующий все опи санные результаты


1.5 Структура работы

В главе 2 описываются важные используемые в ClickHouse термины и по нятия.

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

В главе 4 производится подробный разбор существующих механизмов для агрегации в ClickHouse.

В главе 5 описывается работа, проделанная для создания нового табличного движка.

В главе 6 описывается методика тестирования новой функциональности.

В главе 7 описываются эксперименты для оценки производительности но

вых и существующих решений.

В главе 8 описывается процесс разработки и пользовательская документа

ция.

В заключительной главе 9 подводятся выводы и описываются направления возможной дальнейшей работы.


2 Описание предметной области


2.1 Про ClickHouse

ClickHouse [3] это популярная система управления базами данных для ин терактивной аналитической обработки. Это проект с открытым исходным ко дом, который изначально разрабатывался внутри компании Яндекс более 10 лет назад. Весь код написан на С++ современного стандарта, а разработка ведется в публичном GitHub репозитории [4]. ClickHouse это колоночная SQL база дан ных, которая проектировалась чтобы выполнять запросы максимально быстро.

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


2.2 Используемые термины

• Колонки (англ. «Columns») — контейнеры, в которых непосредственно хранятся данные. Могут иметь разные типы, и обычно представляют из себя непрерывные участки в памяти.

• Поле (англ. «Field») — одно значение в колонке. Операции над одиночны ми полями обычно неэффективны, и заменяются операциями над целыми колонками.

• Блок (англ. «Block») — контейнер, который представляет подмножество из строк в таблице. Содержит в себе информацию про колонки, их типы, имена и позиции.

• Потоки блоков (англ. «Block Streams») — специальные интерфейсы, ко торые позволяют читать и записывать блоки, а также проводить с ними преобразования.

• Таблица (англ. «Table») — специальная структура, которая отвечает за за пись, чтение, хранение данных в базе данных.

• Движок (англ. «Storage») — реализация таблицы или класса таблиц. Ре ализация интерфейса движка IStorage обычно содержит функции read, write и другие, которые непосредственно обрабатывают операции с таб лицей на этом движке.

• Интерпретатор (англ. «Interpreter») — специальная структура, которая от вечает за построение плана и конвейера для выполнения запросов.

• Обычная функция (англ. «Function») — простая операция над данными, похожая на математическую, которая по одному значению сопоставляет другое.

• Агрегатная функция (англ. «Aggregate Function») — функция с состояни ем. Накапливает переданные значения в некотором внутреннем состоя нии, и возвращает результат, полученный из этого состояния.

• Агрегатор (англ. «Aggregator») — специальная структура, которая исполь зуется для агрегации данных в ClickHouse.

• Абстрактное синтаксическое дерево (англ. «AST») — специальная струк тура, в которой хранится запрос, прочитанный из строки. Состоит из кор невого и дочерних узлов, образуя таким образом дерево. ASTPtr это ука затель на узел дерева.

• Пайплайн (англ. «Pipeline») — конвейер для обработки данных.

• Чанк (англ. «Chunk») — контейнер, который хранит колонки с данными и количество строк, одинаковое для всех колонок.

• Одноуровневая агрегация (англ. «singlelevel aggregation») — агрегация с использованием одной хештаблицы.

• Двухуровневая агрегация (англ. «twolevel aggregation») — агрегация с использованием нескольких хештаблиц. Ключи между этими хештаблицами разделены на бакеты, и каждому бакету соответствует своя хештаблица.

• Воркер (англ. «Worker») — исполнитель кода. Как правило используется в задачах с несколькими параллельными воркерами.

Содержание



1 Введение 6
1.1 Актуальность............................. 6
1.2 Краткоеописаниеработы...................... 7
1.3 Целиизадачи ............................ 7
1.4 Полученныерезультаты....................... 8
1.5 Структураработы .......................... 9


2 Описание предметной области 9
2.1 Про ClickHouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Используемыетермины....................... 10
2.3 Формальная постановка задачи . . . . . . . . . . . . . . . . . . . 12


3 Обзор существующих решений 13
3.1 Материализованные представления . . . . . . . . . . . . . . . . 13
3.2 Возможности ClickHouse . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 Агрегация .......................... 14
3.2.2 Материализованные представления . . . . . . . . . . . . 15
3.2.3 LIVEпредставления .................... 16
3.2.4 Табличный движок AggregatingMergeTree . . . . . . . . 16
3.3 Другиебазыданных......................... 19
3.3.1 Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.2 Vertica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.3 Materialize . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4 Выводы................................ 21


4 Агрегация в ClickHouse 21
4.1 Обработказапроса.......................... 21
4.2 Функция executeAggregation . . . . . . . . . . . . . . . . . . . . 23




1

4.3 Структура AggregatingTransform . . . . . . . . . . . . . . . . . . 24
4.4 Структура Aggregator . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5 Движок AggregatingMergeTree . . . . . . . . . . . . . . . . . . . 28
4.6 Выводы................................ 29
5 Создание движка AggregatingMemory 29
5.1 Интерфейс табличного движка . . . . . . . . . . . . . . . . . . . 29
5.2 Движок Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3 Реализация AggregatingMemory . . . . . . . . . . . . . . . . . . 32
5.3.1 Созданиетаблицы...................... 32
5.3.2 Инициализациядвижка . . . . . . . . . . . . . . . . . . . 33
5.3.3 Записьвтаблицу ...................... 34
5.3.4 Чтениеизтаблицы ..................... 35
5.4 Особый случай при создании таблицы . . . . . . . . . . . . . . . 36
5.5 Особый случай при записи в таблицу . . . . . . . . . . . . . . . 36
5.6 Модификация Aggregator . . . . . . . . . . . . . . . . . . . . . . 37
5.7 Поддержка материализованных представлений . . . . . . . . . . 37
5.8 Оптимизация запросов по ключу . .

Добрый день! Уважаемые студенты, Вашему вниманию представляется дипломная работа на тему: «Инкрементальная агрегация данных в памяти»

Аннотация



В последнее время аналитические системы являются очень востребован ными и используются повсеместно. Самой важной частью таких систем явля ется аналитическая база данных, в которую записываются все события. Ана литическая база данных позволяет интерактивно выполнять запросы на этих данных. Распространенный паттерн использования заключается в агрегирова нии всех данных для подсчета статистики, группируя данные по стране, городу, или идентификатору пользователя. Для такой агрегации обычно нужно итери роваться по всем сохраненным данным, что неприемлемо для больших систем, которые записывают новые события в базу со скоростью десятков тысяч собы тий в секунду. Если агрегация данных для больших таблиц это частая операция, которая должна учитывать самые последние данные, то инкрементальная агре гация это хороший способ выполнять эту агрегацию быстрее и эффективнее. Антифрод системы могут использовать инкрементальную агрегацию для по строения различных статистик на поступающих событиях, и использовать их для нахождения мошеннических активностей. В данной работе рассматривает ся реализация инкрементальной агрегации в памяти в ClickHouse, аналитиче ской системе управления базами данных с открытым исходным кодом. Несмот ря на то, что в ClickHouse уже есть поддержка инкрементальной агрегации, она использует жесткий диск. Мы реализуем альтернативный способ, который ра ботает быстрее, и может выдерживать более высокие нагрузки. ClickHouse уже содержит различные структуры для эффективной агрегации, что позволит ис пользовать их в нашей реализации.





Abstract



Analytical systems are in great demand and are used everywhere. The most im portant part of such systems is the analytical database, which stores all the events. The analytic database allows online analytical processing of these data. A common usage pattern is to aggregate all the data to compute statistics, grouping data by counrry, city, or user id. This aggregation is usually requires iterating over all persisted data, which is unacceptable for large systems, which accept new events at a rate of ten of thousands of events per second. If aggregating data for large tables is a frequent operation that must take the latest data into account, then incremental aggregation is a great way to perform this aggregation faster and more efficiently. Antifraud systems can use incremental aggregation to build various statistics over incoming events and use them to find fraudulent activities. This work describes the implementation of in cremental inmemory aggregation in ClickHouse, an opensource analytical database management system. Despite ClickHouse already has support for incremental aggre gation, it uses a hard drive. We are implementing an alternative method that is faster and can sustain higher query rates. ClickHouse already contains structures for effi cient aggregation, allowing us to reuse them in our implementation.





Ключевые слова



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

Список литературы


[1] Chaudhuri Surajit, Dayal Umeshwar. An overview of data warehousing and OLAP technology // ACM Sigmod record. –– 1997. –– Vol. 26, no. 1. –– P. 65– 74.

[2] Миловидов Алексей. X5 Retail Hero, Как перестать бояться и начать разрабатывать специализированные структуры данных. –– https: //youtu.be/sJe35GLxzls (дата обращения: 24.02.2021).

[3] ClickHouse ­ fast open­source OLAP DBMS. –– https://clickhouse. tech/ (дата обращения: 13.05.2021).

[4] ClickHouse/ClickHouse: ClickHouse® is a free analytics DBMS for big data. –– https://github.com/ClickHouse/ClickHouse (дата обращения: 13.05.2021).

[5] Chirkova Rada, Yang Jun. Materialized views // Databases. –– 2011. –– Vol. 4, no. 4. –– P. 295–405.

[6] GROUP BY | ClickHouse Documentation. –– https://clickhouse. tech/docs/en/sql-reference/statements/select/group-by/ (дата обращения: 13.05.2021).

[7] VIEW | ClickHouse Documentation. –– https://clickhouse.tech/ docs/en/sql-reference/statements/create/view/ (дата обращения: 13.05.2021).

[8] AggregatingMergeTree | ClickHouse Documentation. –– https: //clickhouse.tech/docs/en/engines/table-engines/mergetree-family/aggregatingmergetree/ (дата обращения: 13.05.2021).


[9] MergeTree | ClickHouse Documentation. –– https://clickhouse.tech/ docs/en/engines/table-engines/mergetree-family/mergetree/

(дата обращения: 13.05.2021).


[10] CREATE MATERIALIZED VIEW LOG. –– https://docs. oracle.com/en/database/oracle/oracle-database/21/sqlrf/ CREATE-MATERIALIZED-VIEW-LOG.html (дата обращения: 15.05.2021).

[11] Live Aggregate Projections. –– https://www.vertica.com/docs/9. 2.x/HTML/Content/Authoring/AnalyzingData/AggregatedData/ LiveAggregateProjections.htm (дата обращения: 15.05.2021).

[12] Event Streaming Database for Real­Time Applications | Materialize. –– https: //materialize.com/ (дата обращения: 13.05.2021).

[13] Introduction | ClickHouse Documentation. –– https://clickhouse.tech/ docs/en/engines/table-engines/ (дата обращения: 13.05.2021).

[14] Memory | ClickHouse Documentation. –– https://clickhouse.tech/

docs/en/engines/table-engines/special/memory/#memory (дата обращения: 13.05.2021).

[15] TABLE | ClickHouse Documentation. –– https://clickhouse.tech/ docs/en/sql-reference/statements/create/table/ (дата обращения: 13.05.2021).

[16] Testing | ClickHouse Documentation. –– https://clickhouse.tech/docs/ en/development/tests/ (дата обращения: 13.05.2021).

[17] Yandex.Metrica Data | ClickHouse Documentation. –– https://clickhouse. tech/docs/en/getting-started/example-datasets/metrica/ (дата обращения: 13.05.2021).