Размещено на http://allbest.ru

Оглавление

Основные определения

Введение

Глава 1. Анализ предметной области колоночных СУБД и релевантных методов сжатия информации

1.1 Колоночные СУБД

1.1.1 ClickHouse

1.1.2 Vertica

1.1.3 Apache Hive

1.1.4 Greenplum

1.1.5 MySQL

1.1.6 Apache Impala

1.1.7 Druid

1.1.8 Pinot

1.1.9 Apache Kudu

1.1.10 InfluxDB

1.1.11 Gorilla, Beringei

1.2Методы сжатия без потери информации

1.2.1 Семейство алгоритмов Лемпеля-Зива

1.2.2 bzip2

1.2.3Фильтры, улучшающие сжатие

Выводы по 1 главе

Глава 2. Техническое задание

2.1 Независимые расширяемые методы сжатия

2.2 Комбинированные методы сжатия

2.3 Структура блока данных

2.4 Расширение DDL

Глава 3. Описание решения

3.1 Кодек как независимая сущность

3.1.1 Интерфейс

3.1.2 Реализованные кодеки

3.2 Фабрика кодеков

3.3 Последовательность кодеков

3.4 Расширение структуры блока

3.4.1 Continuation bit

3.4.2 Новая структура блока

3.5 Расширение DDL: ключевое слово CODEC

Выводы по 3 главе

Заключение

Источники



Основные определения

База данных -- представленная в объективной форме совокупность самостоятельных материалов, систематизированных таким образом, чтобы эти материалы могли быть найдены и обработаны ЭВМ.

СУБД - database management system, система управления базами данных.

Колоночная СУБД - column oriented database (database management system), СУБД, данные в которой хранятся независимо для каждой колонки.

Фильтр - метод преобразования данных.

Алгоритм сжатия данных - алгоритм преобразования данных, позволяющий уменьшить размер входных данных, lossless - без потерь информации, lossy - с вероятными потерями информации.

Фабрика - синглтон, содержащий регистр классов, объединённых некоторым свойством, например, DataTypeFactory - фабрика типов данных, позволяет по строковому названию типа данных получить экземпляр объекта этого класса.

DDL - Data Definition Language, язык описания данных, семейство компьютерных языков, используемых для описания структуры базы данных.

Кодек - метод преобразования данных, объединяющий понятия «методы сжатия» и «фильтры».

OLAP - Online analytical processing, интерактивная аналитическая обработка данных.



Введение

СУБД ClickHouse была создана в результате исследований по улучшению сервиса Яндекс.Метрика, поэтому к этой системе выдвигались требования по быстродействию, удобству и умению обрабатывать большие объёмы данных (OLAP и sub-second query). Исходя из этих требований, была выбрана архитектура колоночной СУБД. За счёт построения разреженных индексов и хранения колонок таблиц независимо друг от друга удалось добиться большой пропускной способности системы.

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

Но не каждый алгоритм сжатия данных подходит для ClickHouse. Основные характеристики алгоритма, на которые обращается внимание: коэффициент сжатия на однотипных данных (особенность колоночных СУБД, следующая из определения), скорость компрессии, скорость декомпрессии, потребление памяти во время сжатия. Последний параметр важен в условиях работы с оперативной памятью, так как она ограничена, при этом малые дополнительные данные могут быть эффективнее за счёт кэшей процессора. Коэффициент сжатия непосредственно влияет на скорость работы запросов в системе, так как при большем значении данного параметра уменьшается количество взаимодействий с диском при чтении данных, что экономит ресурсы. Скорость сжатия данных критична в момент записи обработанных данных, которые надо выгрузить из памяти, например, для сохранения результатов вычислений или вытеснении из кэша. Скорость декомпрессии оказывает влияние на скорость чтения данных с диска и произведения манипуляций с ними.

Таким образом, в рамках данной работы ставились следующие задачи:

1. Изучить ClickHouse.

2. Изучить текущее решение для работы со сжатием данных.

3. Исследовать присутствующие на рынке конкурирующие СУБД, учесть опыт работы со сжатием данных.

4. Разработать новую расширяемую систему управления сжатием данных в СУБД ClickHouse с учетом требований сообщества.

5. Разработать интерфейс для управления сжатием.

6. Провести всесторонние тесты производительности предложенного решения.

Работа построена следующим образом: в первой главе проводится исследование рынка колоночных СУБД, в частности рассматриваются подходы к компрессии данных, а также приводится сравнение их производительности с ClickHouse в схожих условиях; во второй главе фиксируется техническое задание и требования к разрабатываемому модулю; в третьей главе подробно расписывается предложенное решение, с учетом стиля и структуры исходного кода проекта; в четвертой главе приводятся тесты производительности системы.



Глава 1. Анализ предметной области колоночных СУБД и релевантных методов сжатия информации

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

1.1 Колоночные СУБД

На рынке колоночных СУБД [1] представлено множество решений [2], различающиеся по назначению, открытости исходного кода, языку и времени разработки. В данной главе рассматриваются основные популярные колоночные СУБД и приводятся сравнения производительности решений с ClickHouse. Кроме того, подробно рассматривается аспект компрессии данных конкурентов.

1.1.1 ClickHouse

Система разработана компанией Yandex [3] и выведена в open source на платформе GitHub. Основным преимуществом и целевыми показателями разработки являются быстрые аналитические запросы к большим объёмам данных: OLAP, sub-second query. Система на момент написания работы не обладала возможностью мутаций данных (методы UPDATE, DELETE), но такой функционал находился в разработке.

Сжатие данных производится для всех таблиц и колонок одинаково с помощью настроек, указанных в файле config.xml, который предоставляется при запуске сервера системы. Таким образом, изменение настроек сжатия применяется сразу ко всем таблицам, а также требует перезагрузки сервера. Кроме того, доступно 4 варианта алгоритмов сжатия:

· None - отсутствие какого-либо алгоритма сжатия;

· LZ4 - алгоритм семейства LZ, развитие LZ77, характерен быстрой скоростью компрессии и декомпрессии;

· LZ4HC - модификация алгоритма LZ4;

· ZSTD - алгоритм семейства LZ, вариация LZ77, использующая в качестве методов энтропийного кодирования асимметричные системы счисления (tANS) и кодирование Хаффмана.

Алгоритм сжатия применяется непосредственно перед записью данных на диск. Соответственно декомпрессия происходит во время чтения данных. Это связано со «слоистой» архитектурой системы, где каждое преобразование данных представляет из себя отдельный «поток» (stream).

1.1.2 Vertica

Коммерческое решение, разработанное на основе проекта C-Store [4].

Тесты производительности [5,6] показывают, что система в среднем в 3.76 раз (2.53 для непрогретого кэша, 5.58 для прогретого) медленнее в случае одного сервера и 4.96 в случае кластера из 3 узлов, чем ClickHouse, на выгрузке данных Яндекс.Метрики размером 1 млрд записей, однако обходит ClickHouse по некоторым запросам в условиях непрогретого. Причем, при увеличении количества записей преимущество Vertica сокращается почти для всех запросов, кроме комплексного запроса на суммирование с арифметическими операциями по полю, не входящему в первичный ключ.

Сжатие данных в системе представлено двумя частями: кодированием (encoding) и сжатием (compression).

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

Сжатие используется непосредственно для записи данных на диск. В качестве алгоритма сжатия система использует упаковку целых чисел для не кодированных значений и LZO для несжатых данных.

Алгоритмы кодирования и сжатия [7]:

· Автоматически - в зависимости от типа колонки, используется LZO или Delta кодирование;

· BLOCK_DICT - уникальные значения в каждом блоке колонки записываются в словарь отдельно, а в блоке пишется индекс слова в словаре;

· BLOCKDICT_COMP - тип кодировки похож на BLOCK_DICT, за исключением того, что словарные индексы кодируются энтропией, затрачивается больше CPU, но для колонок с малой энтропией значений может привести к значительному снижению размера данных на диске;

· BZIP_COMP - для сжатия блока используется алгоритм кодирования bzip2, лучшее качество кодирования, чем gzip и LZO, но затрачивает больше CPU;

· COMMONDELTA_COMP - похоже на BLOCK_DICT, только в словарь записываются дельта-значения;

· DELTARANGE_COMP - каждое значение хранится как изменение от предыдущего (дельта);

· DELTAVAL - каждое значение хранится, как изменение относительно наименьшего значения в блоке;

· GCDDELTA - значение дельты от самого маленького элемента блока делится на наибольший общий делитель всех значений в блоке;

· GZIP_COMP - блок кодируется с использованием алгоритма gzip;

· RLE - кодирует последовательности одинаковых значений парой значения и количества элементов.



1.1.3Apache Hive

Разрабатывается на языке Java в связке с проектом Apache Hadoop как data warehouse с поддержкой SQL подобного синтаксиса [8].

По результатам тестов [7], по всем запросам эта система проигрывает ClickHouse на данных Яндекс.Метрики размером 100 миллионов записей: первое выполнение запроса в среднем медленнее в 101.3 раза, повторное в 279.26, в среднем 168.19 раз хуже ClickHouse. Это обосновывается архитектурным строением Hadoop.

Возможно использование следующих кодеков для кодирования и сжатия данных [9]:

· 4mc - библиотека, использующая специальный формат блоков данных, но внутри использующая LZ4 алгоритм;

· GZip - используется алгоритм Deflate;

· LZO - алгоритм LZO из семейства LZ, разработанный для максимально быстрой распаковки в середине 1990-х годов, возможно многопоточное исполнение;

· LZ4 - быстрая модификация LZ77;

· Snappy - алгоритм на основе идей LZ77, опубликованный в свободный доступ в 2011 году, показывает хорошие показатели скорости сжатия и декомпрессии;

· bzip2 - формат и утилита, алгоритмически является комбинацией BWT, MTF и кодирования Хаффмана.

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

1.1.4 Greenplum

Система является open source, используется для анализа и хранения больших данных. Массово-параллельная архитектура системы позиционируется как одно из основных достоинств, на ряду с поддержкой SQL подобного синтаксиса и готовностью хранилища к петабайтам данных [10]. база информация диск запись кодек алгоритм

Проигрывает ClickHouse по всем запросам, в зависимости от объёма данных и размера кластера (для одного сервера: 100 млн записей - в среднем проигрыш в 13.92 раза, 1 млрд записей - 10.51 раза; для кластера из двух машин: 100 млн записей - средний проигрыш в 9.4 раза, 1 млрд записей - 6.84 раза) в разной степени (от x5 до x11).

Особенности архитектуры Greenplum позволяют одной таблице для каждой партиции (partition) в автоматическом режиме выбирать метод хранения (колоночный или построчный), а также метод кодирования (например, zlib, column oriented RLE). Методы сжатия могут применятся на уровне строк (row level) и столбцов (column level) [11]. Есть возможность указать специфический метод кодирования отдельного столбца и отдельный метод кодирования всей таблицы. Для указания специфического кодирования используется расширение DDL ключевым словом «ENCODING» с параметрами compresstype, compresslevel и block, означающих тип и уровень кодирования и размер блока данных соответственно.

Варианты алгоритмов кодирования [12]:

· ZLib - алгоритм Deflate;

· QuickLZ - алгоритм сжатия, модификация алгоритмов семейства LZ, обладает высокой скоростью кодирования и декодирования, но проигрывает LZ4 (подробности в секции 1.2);

· RLE_TYPE - замена последовательности одинаковых элементов парой элемент-количество;

· None - не кодировать данные.



1.1.5 MySQL

MySQL является реляционной базой данных. При использовании ответвления MariaDB [13] есть возможность использовать специальный тип хранилища ColumnStore [14] для записи данных в колоночном формате.

Так как данный формат не является основным для системы, а создан для удобства, то и скорость обработки запросов в нём не достигает рекордных показателей: в сравнении с ClickHouse данное решение уже на 10 млн записей Яндекс.Метрики проигрывает в среднем в 22.83 раза для InfiniDB вариации, и до 314.21 раз при использовании MyISAM в качестве движка [17].

С ростом объёма данных разница для InfiniDB почти не меняется (в среднем в 21.8 раз хуже для 100 млн записей), а для MyISAM растёт (в среднем хуже в 532.74 раза) [6].

Существует глобальный параметр сжатия inifinidb_compression_type, который регулирует политику сжатия данных [16] (InfiniDB фигурирует в названии параметра в силу того, что ColumnStore основан на ответвлении разработки InfiniDB).

Изначально значение равно 2, что означает компрессия включена и соответствует методу snappy, доступно также значение 0, которое означает, что сжатие выключено. Других методов сжатия нет [15].

1.1.6 Apache Impala

СУБД с открытым исходным кодом для управления данными на основе Apache Hadoop. Поддерживает тот же синтаксис и метаданные, что и Apache Hive. Использует свой планировщик и исполнитель запросов [18].

Прямого сравнения Impala и ClickHouse провести не удалось, однако существуют сравнения Apache Impala и Apache Hive [19], в которых показано, что производительность этих систем сравнима в рамках LLAP запросов.

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

Рис. 1.1. Количество выполненных запросов Hive, Impala, источник: [19]

Для сжатия данных [20] доступна настройка COMPRESSION_CODEC [21], принимающая значения SNAPPY, GZIP, NONE. Для установки параметра используется инструкция SET в интерактивном режиме.

1.1.7 Druid

База данных с открытым исходным кодом, спроектированная для быстрого выполнения запросов и ориентированная на OLAP запросы применительно к real-time и историческим данным, не поддерживает SQL [22].

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

Найти и провести тесты непосредственного сравнения Druid и ClickHouse не удалось в силу различия систем на уровне организации данных и подходу к формулированию запросов, однако, существует сравнение Druid с MySQL [23], аналогичное тому, которое приведено выше для MySQL и ClickHouse.

Рис. 1.2. Среднее время исполнения запросов на 1 ГБ данных, Druid, MySQL, источник: [23

Наглядно видно превосходство Druid над MySQL. Также в статье приводятся данные о замерах времени для этих запросов:

Таблица 1.1. Время обработки запросов Druid, MySQL, источник: [23]

Запрос	Druid	MySQL
count_star_interval	0.1112114	1.77
sum_all	0.6074772	2.4
sum_all_filter	0.5058156	2.415
sum_all_year	0.6100049	3.440
sum_price	0.1655666	2.070
top_100_commitdate	0.4150540	3.880
Среднее значение	0.4025216	2.662



Среднее превосходство Druid над MySQL по данным из статьи составляет 6.61 раза. Согласно источникам [24, 25, 26], данные в Druid хранятся в специальной структуре данных - сегмент (Segment). Внутри одного сегмента возможна компрессия данных с помощью алгоритмов LZ4, LZF и Bitmap.

1.1.8 Pinot

Схожая с Druid разработка на Java: real-time OLAP система, поддерживающая индексацию, агрегацию метаданных на уровне хранилища, отсутствует возможность мутации данных, поддерживает SQL-подобный синтаксис запросов, без операции JOIN и с использованием слова TOP для ограничения размера выдачи [27].

Сервис может интегрироваться с Kafka, Hadoop, однако, создатели советуют не использовать его как замену базы данных. Замеров производительности не предоставляется в силу их чувствительности, так как основной пользователь и разработчик - LinkedIn [28].

Существует возможность кодирования блоков данных перед записью на диск с помощью алгоритма Fixed Bit Encoding (используется минимально необходимое количество бит для значений поля вместо полноразмерных типов) и RLE, планируется поддержка алгоритмов Snappy, LZO, LZ4 и ZLib.

1.1.9 Apache Kudu

Колоночная СУБД на основе Apache Hadoop платформы, возможно использование с MapReduce, Spark. В преимуществах системы упоминаются OLAP запросы, поддержка временных данных [29].

Система интегрируется с Apache Impala и использует преимущества HDFS и Apache Parquet, но в дополнении ко всему позволяет мутировать данные.



Рис. 1.3. Сравнение Kudu и Parquet в тесте TPC-H. Источник: https://www.slideshare.net/cloudera/kudu-new-hadoop-storage-for-fast-analytics-on-fast-data/40

Существует сравнение Kudu и Impala/Parquet, где показано, что Kudu показывает себя лучше на 31% на данных, которые умещаются в оперативную память, и проигрывает при частых обращениях к жёсткому диску. Каждая колонка в Kudu может быть создана с указанием кодирования данных, например, целые числа могут кодироваться алгоритмами bitshuffle, RLE, числа с плавающей точкой только bitshuffle, строки могут кодироваться через prefix или словарь. Помимо кодирования отдельных значений, Kudu поддерживает сжатие колонок алгоритмами LZ4, Snappy и ZLib.

1.1.10 InfluxDB

Open source СУБД, написанная на Go, для работы с временными рядами и данными, существует с 2013 года, является частью архитектуры решения InfluxData по аналитике [30]. Поддерживает SQL синтаксис запросов.

Для уменьшения занимаемого объёма памяти используются различные алгоритмы: simple8b, Snappy, RLE, delta, в зависимости от выбранного движка и типа данных [31].

В силу специфики этой СУБД (временные ряды), сравнение производительности не приводится, так как прямого сравнения с ClickHouse не проводилось, а из конкурентов в данной работе только Beringei (2016).

1.1.11 Gorilla, Beringei

Разработанная Facebook in-memory база данных, специализирующаяся на хранении временных данных (time series) [32]. Рассматривается в данном обзоре, так как ClickHouse также может использоваться для хранения временных данных, кроме того, Gorilla использует продвинутые методики сжатия временных данных. Существует open source реализация - Beringei [33]. Для хранения временных рядов используется кодирование алгоритмами Delta, Delta-of-Delta и основанное на операции XOR сжатие возрастающих чисел с плавающей точкой, что позволяет системе сжимать данные до 12 раз, используя 1,37 байта на значение [32, 34].

Замеры скорости не приводятся в силу специфики Gorilla, Beringei (TSDB).

1.2 Методы сжатия без потери информации

Не все методы компрессии информации подходят для СУБД, претендующих на генерацию аналитических отчетов в реальном времени. В первую очередь, методы сжатия не должны терять информацию во время компрессии (lossless), а также быстрыми в смысле пропускной способности сжатия и декомпрессии (например, сравнивая по значению МБ/сек). Эффективность сжатия отходит в таких системах на второй план, но зачастую даётся выбор пользователю, готов ли он ждать дольше, но использовать меньшее хранилище, либо наоборот готов пожертвовать пространством жёсткого диска в угоду другим параметрам системы.



Рис. 1.4. Распределение методов кодирования на графике скорость компрессии, коэффициент компрессии, источник: [49]

1.2.1 Семейство алгоритмов Лемпеля-Зива

Семейство алгоритмов сжатия LZ*. Основываются на опубликованных алгоритмах LZ77 и LZ78 в статьях Авраама Лемпеля и Яакова Зива в 1977 и 1978 годах. Алгоритмы являются словарными методами сжатия.

LZ77, LZ78. Алгоритм LZ77 [35] использует внутри себя «скользящее окно», в то время как LZ78 неявно использует словарный подход. Это, в некотором смысле, эквивалентные подходы.

Более подробно: в алгоритмах используются принцип скользящего окна и механизм кодирования совпадений. Первый заключается в том, что у алгоритма есть некоторый буфер, в котором хранятся ранее встретившиеся значения, на ссылки в котором заменяются повторные вхождения строк. Механизм кодирования совпадений различается для LZ77 и LZ78. LZ77 использует только скользящее окно (понятия длина совпадения и смещение), в то время как LZ78 использует словарь встретившихся фраз (поиск максимальной подстроки в элементах словаря и замещение наименее используемого). В результате последовательного построения и изменения буфера, он представляет собой обобщённую форму RLE.

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

LZW. Метод является расширением LZ78 (предложен Терри Велчем в 1984 году [41]) с помощью префиксного дерева, которое замещает словарь в версии LZ78, за счёт чего возможен рост размера словаря.

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

LZO. Алгоритм является развитием LZ77, стараясь обеспечить максимальную скорость распаковки (предложен Маркусом Оберхеймером в середине 1990-х).

Поддерживает многопоточное исполнение, требует малое количество дополнительной памяти [37].

Deflate. Алгоритм является развитием LZ77, использующим для энтропийного кодирования коды Хаффмана на высоких уровнях сжатия. Сначала происходит сжатие с помощью LZ77, в результате чего вхождение символов заменяется ссылками в словаре/окне, после чего символы в окне кодируются кодами Хаффмана по частоте вхождения [36]. Используется во многих стандартах, форматах и утилитах, например, Zip, GZip, PDF, PNG.

LZ4 - модификация алгоритма LZ77 2011 года, реализованная Яном Коллетом, которая жертвует степенью сжатия в угоду скорости, не используя энтропийное кодирование, в результате чего получается один из лучших показателей скорости сжатия и декомпрессии, в разы быстрее, чем, например, GZip [39].

Особенность алгоритма в поиске первого совпадения в небольшом плавающем окне (sliding window) и специфика его кодирования, за счёт чего достигается большая скорость.

LZ4HC - LZ4 в версии High-Compression, то есть увеличенная степень сжатия. Данный алгоритм отличается от LZ4 тем, что ищет все вхождения текущей (в момент обработки участка на этапе компрессии) подстроки в словарь для более качественного кодирования.

QuickLZ. Улучшенная реализация варианта FastLZ. Уступает по показателям скорости более нового LZ4 [39, 42].

ZSTD. ZStandart - библиотека, написанная Яном Коллетом в 2015 году, использующая Finite State Entropy (tANS) совместно с кодом Хаффмана в алгоритмах LZ семейства, в результате чего получается ускорить стандартные имплементации с улучшением показателя сжатия [40].

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

Brotli. Алгоритм, изначально созданный для сжатия WOFF2 файлов, использующий в основе LZ77 алгоритм в связке с кодированием Хаффмана и моделированием контекста второго порядка [43].

Показывает хорошую степень сжатия. На малых объёмах данных способен показывать очень высокую скорость и степень сжатия выше, чем ZSTD [49]. С изменением настроек возможно достижение скорости, схожей с zlib на больших объёмах данных. Не используется в базах данных в силу особенностей и плюсов, проявляющихся в основном на малых объёмах данных.

Snappy. Алгоритм, разработанный в компании Google, нацеленный на скорость компрессии, нежели на качество. Используются идеи LZ77 [44]. Используется во многих библиотеках и системах.

1.2.2 bzip2

Утилита, использующая преобразование Барроуза-Уилера, Move-To-Front кодирование и код Хаффмана [38].

Реализованный в 1996 году алгоритм, используется во многих системах, поставляется как утилита. Может уступать методу LZMA [48], но показывает хорошую скорость в сравнении с наилучшими алгоритмами сжатия времён разработки (PPM) [38].

1.2.3 Фильтры, улучшающие сжатие

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

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

Рис.1.5. D elta кодирование.

Delta, Delta-Delta. Зачастую в ClickHouse хранятся временные последовательности, данные, которые получены в результате некоторых замеров, периодичных действий.

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

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

Можно заметить, что такое преобразование, в некотором смысле, эквивалентно взятию первой производной, в связи с чем, было проверена и доказана эффективность Delta of Delta кодирования, эквивалентного взятию второй производной [32, 45].

Shuffle, Transpose. Второе преобразование берёт своё начало из базовых соображений алгебры и представлений чисел в памяти. Например, в сортированном блоке данных лежат числа, входящие в окрестность некоторого числа, таким образом, они имеют одинаковый префикс в двоичном представлении.

Записав построчно числа в матрицу n x n, где n - размер числа в байтах, можно провести преобразования этой матрицы - транспонирование, после чего запись матрицы в памяти будет иметь префикс из последовательности одинаковых символов. Такое преобразование называется по-разному в различных системах: shuffle или transpose. Это лишь один пример алгебраического подхода к записи чисел, возможны несложные манипуляции с последовательностями байт памяти, помогающие улучшить качество сжатия [46].

Рис. 1.6. RLE и Dictionary кодирование.

Huffman Code, Finite State Entropy, Dictionary, Run length encoding. Многие методы кодирования данных полагаются на комбинацию базовых структур, например, LZ77 в комбинации с кодом Хаффмана и префиксным деревом, учет энтропии значений с помощью конечного автомата, запись всех уникальных значений столбца в словарь и использование индексов в словаре. Всё это может быть использовано как фильтры при реализации методов сжатия СУБД [35, 36, 37, 39, 40, 7].

Выводы по 1 главе

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

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



Глава 2. Техническое задание

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

2.1 Независимые расширяемые методы сжатия

Историческое решение по сжатию данных в ClickHouse регулируется специальным блоком конфигурации файла config.xml, указывающим метод сжатия и условия его использования (размер блока, размер колонки, параметры алгоритма). Методы сжатия применяются к блоку данных в CompressedReadBuffer / CompressedWriteBuffer классах.

Класс CompressedReadBufferBase производит считывание заголовка блока данных с диска и проверяет валидность - метод кодирования, в случае корректности - считывает блок данных до конца и вызывает функцию декомпрессии на данных, соответствующую указанному методу кодирования. Для выбора алгоритма декомпрессии используется switch-case конструкция, что очень скудно расширяется.

Класс CompressedWriteBuffer, помимо потока данных, получает метод кодирования и его настройки, после чего записывает заголовок блока, сжимает данные указанным методом и записывает их в блок. Здесь также используется switch-case конструкция для выбора функции шифрования, в которую напрямую передаётся указатель на буффер вывода, в результате чего достигается очень высокая скорость записи кодированных данных. Это архитектурное решение также плохо поддаётся расширению.

Требуется выделить методы сжатия в отдельный класс объектов с унифицированным интерфейсом. В данный момент используются методы LZ4, LZ4HC, ZSTD, none.

2.2 Комбинированные методы сжатия

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

2.3 Структура блока данных

Если предыдущие пункты задания относятся к алгоритмической и архитектурной структуре проекта, то блок данных является низкоуровневым представлением данных. Структура блоков данных должна остаться обратно совместимой. Сейчас блок включает заголовок и тело. Заголовок состоит из 16 байт контрольной суммы (checksum), одного байта, кодирующего метод сжатия, 4 байт размера до кодирования и 4 байт размера после кодирования. Необходимо предусмотреть возможность записи в заголовок нескольких кодирующих методы сжатия байт, а также аргументы конкретных методов кодирования. Например, можно использовать один бит как флаг наличия последующего метода кодирования. Для кодирования аргументов метода можно завести новые методы кодирования, которые постепенно заменят старые, не требующие сохранения аргументов в блоке данных. Такое решение позволит сохранить обратную совместимость блоков и расширяемость для использования новых возможностей.

2.4 Расширение DDL

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

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

Предлагается добавить возможность указывать ключевое слово CODEC с опционально конфигурируемыми аргументами при создании таблицы данных в описании колонки. Пример использования:

CREATE TABLE test (col1 UInt8 CODEC(Delta, LZ4(1))) Engine = Log.

В данном запросе создаётся таблица test с колонкой col1 целочисленного типа, кодируемая кодеком Delta и алгоритмом сжатия LZ4 с аргументом 1.



Глава 3. Описание решения

В данной главе описывается предлагаемое решение, соответствующее техническому заданию, указанному в Главе 2. Для унификации кодовой базы и лёгкости поддержки кода, что важно для open source проекта, решение во многом опирается на уже применяемые подходы в проекте. Например, фабрика кодеков аналогична фабрике типов данных, базовый класс-интерфейс описывает границы применимости внутренних методов, регулирует необходимость их реализации.

3.1 Кодек как независимая сущность

Для соответствия пункту 2.1 был реализован класс-интерфейс ICompressionCodec. Данный класс используется для наследования от него всех имплементаций кодеков и предоставляет базовый интерфейс. Использование класса-интерфейса позволяет в дальнейшем пользоваться полиморфизмом C++, применимо к методам сжатия.

Каждый кодек обладает собственным строковым названием и кодирующим байтом, использующимся в низкоуровневом представлении блоков данных в заголовочной секции. Эти идентифицирующие признаки используются для регистрации объектов в фабрике кодеков. Помимо общего набора параметров, отдельные кодеки могут обладать уникальным набором аргументов, например, кодек Delta должен знать размер единицы данных, а LZ4 уровень сжатия.

3.1.1 Интерфейс

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

ICompressionCodec интерфейс включает следующие методы:

getName() - получение строкового представления текущего инстанса класса, включает в себя дополнительные аргументы, если они есть, например, LZ4(1);

getFamilyName() - получение строкового представления названия класса, то есть семейства кодеков, например, LZ4;

size_t writeHeader(char* dest) - данный метод записывает в секцию заголовка кодирующий байт и необходимые аргументы, соответствующие инстансу класса;

size_t parseHeader(const char* header) - данный метод разбирает секцию заголовка, содержащую дополнительные аргументы кодека;

size_t getMaxCompressedSize(size_t uncompressed_size) - получить максимально возможный размер результирующего (после сжатия) объекта по размеру до сжатия, например, для подготовки массива для результата сжатия;

size_t compress(const char* source, char* dest, int inputSize, int maxOutputSize) - произвести сжатие объекта, расположенного в массиве source размером inputSize, и записать результат в массив dest с ограничением по размеру maxOutputSize, функция возвращает количество записанных байт - размер сжатого объекта;

size_t decompress(const char* source, char* dest, size_t inputSize. size_t maxOutputSize) - произвести декомпрессию объекта, расположенного в массиве source размером inputSize, и записать результат в массив dest, ограниченный размером maxOutputSize, функция возвращает количество записанный байт - размер декодированного объекта, в случае возникновения ошибки вызывается Exception;

void setDataType(DataTypePtr dataType) - данный метод позволяет проставить в объект класса тип каждого элемента в колонке, откуда в дальнейшем можно получить размер элемента и операции над ним.

Кроме указанных методов, объекты ICompressionCodec обладают публичным полем bytecode - один байт, который кодирует кодек в заголовочной секции, size_t datasize - размер одного элемента в блоке данных. Помимо указанных методов, наследуемые классы могут объявлять необходимые конструкторы, принимающие дополнительные аргументы. В таком случае, кодеки называются параметризируемыми, иначе кодеки называются простыми.

3.1.2 Реализованные кодеки

На данный момент реализованы необходимые для обратной совместимости кодеки LZ4, LZ4HC, ZSTD, помимо которых добавлены кодеки Delta и Shuffle (Transpose).

LZ4, LZ4HC. Данный кодек инкапсулирует взаимодействие с библиотекой lz4. Классы различаются только дополнительным полем is_hc, так как метод декодирования не отличается. Реализует дополнительный конструктор, принимающий на вход число - параметр алгоритма.

Методы compress и decompress проксируют параметры в методы библиотеки lz4.

ZSTD. Кодек инкапсулирует взаимодействие с библиотекой zstd, проксируя методы compress и decompress. Также реализует дополнительный конструктор, принимающий на вход уровень сжатия (сохраняется в дополнительное поле класса uint8_t compression_level).

Delta. Метод кодирования (фильтр) Delta использует размер элемента данных при итерации по массиву source, заменяя все объекты разницей с предыдущим. Реализация написана самостоятельно, так как метод достаточно простой и не требует выделенной библиотеки, кроме того, библиотеки (C-Blosc, PowTurbo) с реализованным методом дельта-кодирования распространяются под лицензией GPL, что не совпадает с лицензией ClickHouse. Среди особенностей реализации стоит выделить то, что класс полагается на данные о типе и ведёт себя разным образом для разных типов данных (целочисленные, с плавающей точкой), эту информацию он кодирует в заголовке.

Shuffle, Transpose. Метод кодирования, фильтр, также использует размер одного элемента при кодировании для построения матрицы элементов, после чего производится преобразование (транспонирование полученной матрицы).

3.2 Фабрика кодеков

По аналогии с DataTypeFactory, создана CompressionCodecFactory, позволяющая по названию или кодирующему байту кодека получить инстанс его класса. По названию кодек получается при обработке запроса на создание таблицы, подробности см. в секции 3.5. По кодирующему байту кодек создаётся при чтении блоков данных с диска, подробнее см. в секции 3.4. Для регистрации кодеков в классе описывается метод регистрации конкретного кодека, который уже объявляется в файле, описывающем кодек. Внутри фабрики существует два словаря (объекты типа map): первый регистрирует кодеки по строковому наименованию, второй по кодирующему байту. Для простых кодеков сразу создаётся объект класса. Для параметризируемых кодеков функция-creator ожидает передачу параметров.

Получение объектов происходит с помощью перегруженной функции get, принимающей на вход строку или кодирующий байт. Функция возвращает другую функцию, которая уже генерирует объекты нужного класса, на вход ожидая опциональные параметры класса кодека. Более подробное взаимодействие кодеков, фабрики и последовательности кодеков описано в секции 3.3.

3.3 Последовательность кодеков

Для поддержки последовательности кодеков, был разработан специальный объект CompressionPipeline, реализующий такой же интерфейс, как любой другой кодек, ICompressionCodec, Особенность данного объекта в том, что внутри он инкапсулирует вызовы compress и decompress для всей последовательности кодеков, которую получает на вход.

Конструктор объекта принимает на вход строку, секцию заголовка блока или ASTPtr - ссылку на узел ключевого слова CODEC в абстрактном синтаксическом дереве.

К строковому представлению, например, «CODEC(LZ4, Delta)», в конструкторе применяется разбор синтаксического дерева данного сообщения, в результате чего передаётся вызов конструктору по ASTPtr.

В конструкторе, принимающем на вход ASTPtr, проводятся следующие манипуляции: вытаскивается последовательность необходимых кодеков (vector<ASTPtr>), например, указатели на узлы LZ4 и Delta, после чего для каждого узла получается название и список аргументов.

После выявления простой или параметризованный кодек необходим, происходит обращение к CompressionCodecFactory, по результатам взаимодействия с которой и получается необходимый кодек. Далее, все кодеки складывается в вектор кодеков vector<ICompressionCodec> и записывается в объект класса CompressionPipeline.

Конструктор по заголовку блока данных итерируется по байтам заголовка, зануляя зарезервированные биты, тем самым получая кодирующий байт. Получая кодирующие байты, создаётся объект кодека и вызывается его функция parseHeader для разбора дополнительных параметров (подробнее в секции 3.4), производится обращение к фабрике и получение кодека. Все кодеки также складываются в вектор. Метод writeHeader класса последовательности кодеков обращается последовательно к каждому из кодеков, лежащих во внутреннем векторе кодеков, после чего получается заголовок для последовательности. Класс реализует дополнительный метод parseSize(const char* header) для считывания последовательности размеров преобразований, подробнее далее.



Схема 3.1. Архитектура модуля кодеков компрессии

Метод compress создаёт локальный массив для записи результата преобразований кодеков и последовательно вызывает все кодеки из внутреннего вектора, чередуя массивы выхода (локальный и предоставленный dest).

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

Метод decompress работает аналогично методу compress, за тем лишь исключением, что итерируется по вектору кодеков в обратном порядке и использует вектор промежуточных размеров алгоритмов компрессии.

3.4 Расширение структуры блока

Блок состоит из двух частей: заголовка (header) и тела (data).

Заголовок включает в себя контрольную сумму, один байт, кодирующий метод сжатия, размер до сжатия и после.

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

3.4.1 Continuation bit

0x01 - добавляется к кодирующему кодек байту, что означает выставление в положительное значение флага о наличии последующих кодеков. Используется для реализации CompressionPipeline, позволяя кодировать в бинарный формат более одного кодека.

3.4.2 Новая структура блока

Реализованный блок содержит помимо контрольной суммы фиксированного размера и блоков с размерами до и после преобразования меняющийся блок, кодирующий кодеки.

Размер заголовка теперь не статичен, но так как считывание происходит последовательно и обязательно считывает весь заголовок, указатель остаётся перед началом содержательного блока данных, что никак не влияет на работоспособность остальной системы.

Кодирование параметров кодека происходит автоматически самим кодеком в методе writeHeader, а чтение параметров происходит в методе parseHeader кодека, которое вызывается из конструктора CompressionPipeline.

Дополнительные аргументы считываются из заголовка, размер аргументов вычисляется методом кодека автоматически.

3.5 Расширение DDL: ключевое слово CODEC

Расширение языка описания данных заключается в редактировании парсера абстрактного синтаксического дерева.

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

Например: Column_name UInt64 CODEC(Delta, Shuffle, LZ4(4))

После разбора AST, указатель на узел кодека попадает в описание ASTColumnDeclaration.

Далее, на этапе создания колонки вызывается CompressionPipeline, который конструирует для столбца необходимый поток кодеков. Результирующий объект попадает в описание колонок ColumnsDescription в объект типа map<string, ColumnCodecs>.

Используется данный объект в блоке CompressedReadBuffer/CompressedWriteBuffer, куда он передаётся из движка таблицы, например TinyLog или MergeTree.

Выводы по 3 главе

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

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

Обратная совместимость сохранилась и новые версии системы способны работать со старыми данными. Возможности старым системам работать с новым форматом не предусматривается.



Заключение

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

Среди примеров таких методов кодирования, помимо уже присутствующих в ClickHouse кодеков LZ4 и ZSTD: Delta и Delta-Delta кодирование для временных последовательностей, Run-Length Encoding, Block-Dict, код Хаффмана. Применимость этих кодеков в рамках ClickHouse оправдана характером данных основных пользователей системы - аналитики Яндекс.Метрики. Помимо аналитики рынка решений, было зафиксировано техническое задание, опирающееся как на реализации конкурентов, так и на здравый смысл и требования качества системы.

Было разработано решение, соответствующее требованиям и не уступающее предлагаемым другими системами подходам, но и в некотором роде комбинирующее и обобщающее их подход. На примере адаптации уже присутствовавших кодеков (LZ4, ZSTD) и введении новых (Delta) была показана расширяемость и гибкость предложенного решения.

Дальнейшим развитием системы может стать более глубокая интеграция и тестирование архитектуры кодеков: подбор кодеков по умолчанию для определённых типов данных на основе балансирования нагрузки на процессор и объёма данных на жёстком диске. По примеру конкурентных решений возможно создание аналитической утилиты для автоматизации выбора кодеков для уже существующих наборов данных.



Источники

1. S. Harizopoulos, D. Abadi. P. Boncz. Column-Oriented Database Systems [Электронный ресурс]. - Режим доступа : http://www.cs.yale.edu/homes/dna/talks/Column_Store_Tutorial_VLDB09.pdf, свободный. - Загл. с экрана.

2. List of column-oriented DBMSes [Электронный ресурс]. - Режим доступа : https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes, свободный. - Загл. с экрана.

3. ClickHouse - open source distributed column-oriented DBMS [Электронный ресурс]. - Режим доступа : https://clickhouse.yandex/, свободный. - Загл. с экрана.

4. Vertica: Big Data Analytics on Premise, in the Cloud, or on Hadoop [Электронный ресурс]. - Режим доступа : https://www.vertica.com/, свободный. - Загл. с экрана.

5. Performance comparison of analytical DBMS, 1bn [Электронный ресурс]. - Режим доступа: https://clickhouse.yandex/benchmark.html#[1000000000,[%22ClickHouse%22,%22Vertica%22,%22Vertica%20(x3)%22,%22Greenplum(x2)%22,%22Greenplum%22],[%220%22,%221%22]], свободный. - Загл. с экрана.