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

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

Аннотация

В последнее время аналитические системы являются очень востребован­ ными и используются повсеместно. Самой важной частью таких систем явля­ ется аналитическая база данных, в которую записываются все события. Ана­ литическая база данных позволяет интерактивно выполнять запросы на этих данных. Распространенный паттерн использования заключается в агрегирова­ нии всех данных для подсчета статистики, группируя данные по стране, городу, или идентификатору пользователя. Для такой агрегации обычно нужно итери­ роваться по всем сохраненным данным, что неприемлемо для больших систем, которые записывают новые события в базу со скоростью десятков тысяч собы­ тий в секунду. Если агрегация данных для больших таблиц это частая операция, которая должна учитывать самые последние данные, то инкрементальная агре­ гация это хороший способ выполнять эту агрегацию быстрее и эффективнее. Антифрод системы могут использовать инкрементальную агрегацию для по­ строения различных статистик на поступающих событиях, и использовать их для нахождения мошеннических активностей. В данной работе рассматривает­ ся реализация инкрементальной агрегации в памяти в 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 coun­rry, 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. Anti­fraud 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 in­memory aggregation in ClickHouse, an open­source 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 Введение 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

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 Оптимизация запросов по ключу . .

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

[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 opensource 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 RealTime 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).