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

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

Аннотация

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