Служба спасения студентов
Служба спасения для студентов (18+)

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

Стоимость
2500 руб.
Содержание
Теория
Объем
56 лист.
Год написания

Описание работы

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

 
Содержание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.3LIVEпредставления ....................16

3.2.4Табличный движок AggregatingMergeTree  . . . . . . . .16
3.3Другиебазыданных.........................19

3.3.1Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

3.3.2Vertica   . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

3.3.3Materialize  . . . . . . . . . . . . . . . . . . . . . . . . . .20
3.4Выводы................................21
4   Агрегация в ClickHouse21
4.1Обработказапроса..........................21
4.2Функция executeAggregation  . . . . . . . . . . . . . . . . . . . .23
 
1
 

4.3Структура AggregatingTransform  . . . . . . . . . . . . . . . . . .24

4.4Структура Aggregator  . . . . . . . . . . . . . . . . . . . . . . . .25

4.5Движок AggregatingMergeTree  . . . . . . . . . . . . . . . . . . .28

4.6Выводы................................29
5Создание движка AggregatingMemory29

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

5.9Выводы................................40
6Тестирование41

6.1Базовыетесты ............................42

6.2Материализованные представления  . . . . . . . . . . . . . . . .43

6.3Дополнительныетесты .......................43

6.4Выводы................................44
7Оценка производительности45

7.1Инструменты для тестирования производительности  . . . . . .45

7.2Нашаметодика............................46

7.3Движок AggregatingMemory   . . . . . . . . . . . . . . . . . . . .48

7.4Обычнаяагрегация .........................49
 
2


7.5Движок AggregatingMergeTree  . . . . . . . . . . . . . . . . . . .49

7.6Materialize  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50

7.7Результатыэкспериментов  . . . . . . . . . . . . . . . . . . . . .51

7.8Выводы................................51
8Разработка и использование52

8.1Разработка ..............................52

8.2Документация в ClickHouse . . . . . . . . . . . . . . . . . . . . .52

8.3Документированиедвижка.....................52

8.4Выводы................................52
9Заключение53


Аннотация

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


В последнее время аналитические системы являются очень востребован ными и используются повсеместно. Чаще всего самой важной частью таких систем является аналитическая база данных, в которую записываются все собы тия самых разных видов, происходящих в системе. Аналитическая база данных позволяет интерактивно выполнять запросы на этих данных, то есть выдавать результат, содержащий информацию о всех поступивших на текущий момент данных. Такой подход к аналитическим задачам называется интерактивной ана литической обработкой [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]    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).

 

Сколько стоит помощь с учебной работой?