Эта статья выбрана из серии статей «Практика инфраструктуры Byte Beat».

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

RocksDB — один из наиболее широко используемых механизмов хранения в мире.Большое количество продуктов баз данных в ByteDance (например, базы данных, NewSQL и т. д.) построены на RocksDB.Больше возможностей для бизнеса.

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

1. Предпосылки

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

В этой статье сначала делается попытка разобраться и представить наши пять улучшений в RocksDB (разработанных на основе внутреннего механизма хранения TerarkDB), в надежде принести некоторую справочную ценность сообществу, и мы приглашаем технических экспертов, которые заинтересованы в механизмах хранения, присоединиться к нам. ● Создайте более сильную базовую поддержку для ByteDance.

2. Недостатки RocksDB

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

3. Наши улучшения

3.1 LazyBuffer

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

Однако PinnableSlice не может иметь значения в некоторых сценариях, таких как операция пользователя, которую необходимо коснуться.Когда много нежелательных значений(Например, существует много версий Value или большое количество надгробий), PinnableSlice по-прежнему будет генерировать операции ввода-вывода для этих бесполезных Values, и этой части накладных расходов можно полностью избежать.

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

Lazy Buffer — это усовершенствование PinnableSlice, которое еще больше сокращает ненужные операции ввода-вывода за счет сокращения копирования данных, что очень полезно для таких сценариев, как большое количество сканирований и SeekRandom.

3.2 Lazy Compaction

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

Leveled Compaction
- Все уровни объединены сверху вниз по стандарту
- Усиление чтения и записи более серьезно, но усиление пространства низкое
- В этом документе (Towards Accurate and Fast Evaluation of Multi-Stage Log-Structured Designs) подробно описано
Tiered Compaction
- т. е. универсальное уплотнение в RocksDB
- Усиление пространства и усиление чтения — это серьезно, но усиление записи минимально.
- В этом документе (Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging) подробно описано
Tiered+Leveled Compaction
- т. е. сжатие уровней в RocksDB
- Это гибридная стратегия уплотнения, усиление пространства ниже, чем многоуровневое уплотнение, и усиление записи также ниже, чем уровневое.
Leveled-N Compaction
- Более низкое усиление записи и более высокое усиление чтения, чем при уровневом уплотнении
- Объединить N - 1 слой в N-й слой за раз

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

Прежде всего, нам нужно понять, что если мы можем позволить SST не поддерживать строгий порядок, то мы можем собрать больше статистической информации, а затем фактически выполнить внешнюю сортировку (уплотнение), но недостатком является то, что это увеличит определенный Степень усиления чтения.Задержка чтения будет иметь влияние, поэтому есть ли способ сделать увеличение усиления чтения управляемым или даже почти не увеличить усиление чтения?

Мы попытались построить новую структуру данных SST (Adaptive Map, aMap для краткости).В отличие от структуры по умолчанию RocksDB, aMap представляет собой логическую виртуальную SST, как показано на следующем рисунке:

Рисунок: Структурная схема aMap

На рисунке SST 1, SST 2 и SST 3 — это три физических файла SST. Когда их нужно объединить, мы сначала создаем виртуальную маску, чтобы представить логически объединенный SST верхнему уровню (логически Большой SST), а запись и маркировка покрытия, Key Space и другой статистики.

Его основные функции:

С точки зрения стратегии большого уплотнения, он наследует уплотнение уровней RocksDB (также может поддерживаться универсальное уплотнение, в зависимости от потребностей сцены, по умолчанию используется уплотнение уровней).
Когда требуется уплотнение, сначала будет построена адаптивная карта, а несколько SST-кандидатов будут сформированы в новый логический SST (как показано на рисунке выше).
На адаптивной карте несколько разных перекрывающихся сегментов, R1, R2, R3, R4, R5, будут разделены, и перекрытие этих перекрывающихся сегментов будет отслеживаться и записываться.
Фоновый поток GC будет предпочтительно выбирать те слои с лучшим перекрытием для GC, что означает, что мы можем сделать GC более эффективным, то есть усиление записи будет намного ниже, чем в случае по умолчанию.

По сравнению с оригинальной RocksDB усиление чтения-записи имеет преимущества в теоретическом анализе:

Накладные расходы ввода-вывода	Оригинал RocksDB	После улучшения	инструкция
читать увеличение	O(log N)	O(1)	N - общий объем данных
написать зум	O(log N)	O(log log N)	N - общий объем данных
вычислительная стоимость	Оригинал RocksDB	После улучшения
чтение потребления	O(p)	O(p)	P — уровень ложных срабатываний BloomFilter.
напишите расход	O(log N)	O(log log N)	N - общий объем данных

Таблица: Сравнение анализа сложности (увеличение чтения и усиление записи)

3.3 КВ разделение

в диссертации*WiscKey: Separating Keys from Values in SSD-conscious Storage*Представлен дизайн SST с разделением KV. Его основной метод заключается в создании файла журнала значений и непрерывном добавлении к нему данных Value. В то же время в исходном SST значение записывает только фактическое местоположение данных.

Рисунок: Основной принцип разделения KV

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

В сообществе RocksDB есть функция BlobDB, разделенная KV, но в настоящее время эта функция не идеальна, и предстоит еще много работы, поэтому я не буду проводить здесь сравнение. Другой TitanDB — это относительно полный движок разделения KV (построенный в виде плагина RocksDB), и мы делаем простое сравнение между ними здесь:

	WiscKey	TitanDB	TerarkDB (наши улучшения)
Расставание при каких обстоятельствах	всегда	превышает порог	превышает порог
Метод сохранения стоимости	VLOG	Специально разработанные файлы больших двоичных объектов	Собственный SST-файл
Получить процесс	1) Ключ → Позиция VLOG2) Позиция VLOG → Значение	1) Ключ → Номер файла + дескриптор 2) Номер файла → Большой двоичный объект 3) Большой двоичный объект + дескриптор → Значение	1) Ключ → Номер файла2) Номер файла → SST3) SST + Ключ → Значение
Стоимость сканирования	Медленнее, чем LevelDB поддерживает Prefetch	Медленнее, чем RocksDB, использование ввода-вывода относительно низкое, предварительная выборка еще не поддерживается.	Медленнее, чем RocksDB, использование ввода-вывода относительно низкое, предварительная выборка еще не поддерживается.
процесс GC	1) Проверить в обратном порядке и вытолкнуть KV в начало VLOG 2) Переписать действительные данные в конец VLOG и повторно вставить LSM-дерево	1) В соответствии с прослушивателем событий выберите большой двоичный объект с наибольшим количеством мусора, чтобы инициировать GC, проверьте обратно KV в большом двоичном объекте. 2) Создайте новый большой двоичный объект и перезапишите затронутые данные в дерево LSM.	1) Согласно прослушивателю событий, выберите SST с наибольшим количеством мусора, чтобы инициировать сборку мусора, и проверьте KV в SST.2) Создайте новый SST.
эффективность ГХ	Прокрутка VLOG для достижения GC прокрутки одного полного цикла GC очень длинная, горячие данные не являются дружественными	Всегда инициируйте GC для большого двоичного объекта с наибольшим количеством мусора, удобного для горячих данных, и переписывайте дерево LSM.	Всегда инициируйте GC для SST с наибольшим количеством мусора, дружелюбным к горячим данным и не перезаписывайте дерево LSM.

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

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

3.4 Поддержка нескольких индексов

Формат SST для нативной RocksDB примерно такой, как показано ниже:

[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]          (see section: "filter" Meta Block)
[meta block 2: index block]
[meta block 3: compression dictionary block]  (see section: "compression dictionary" Meta Block)
[meta block 4: range deletion block]      (see section: "range deletion" Meta Block)
[meta block 5: stats block]          (see section: "properties" Meta Block)
...
[meta block K: future extended block]  (we may add more meta blocks in the future)
[metaindex block]
[Footer]                (fixed size; starts at file_size - sizeof(Footer))

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

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

Дополнительные уже поддерживаемые алгоритмы индексации:

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

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

3.5 Экстремальное сжатие

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

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

Рисунок: Обзор алгоритма глобального сжатия

Общий процесс таков:

Сначала отсканируйте и попробуйте данные, чтобы создать словарь данных.
- Таким образом, по умолчанию Compaction SST необходимо изменить, чтобы обеспечить возможность сканирования дважды.
Согласно словарю данных, на исходных данных выполняется сжатие скользящего окна.
Наконец, выполняется необязательный раунд энтропийного сжатия (Entropy Compression).
- Основная индустрия энтропийного сжатия включает в себя ANS и Хаффмана высокого порядка и т. Д., Которые можно выбрать в соответствии с фактическим обнаружением распределения данных.
В процессе сжатия информация о смещении каждых исходных данных будет сохранена для формирования таблицы смещений.

Рис.: Создайте и сохраните таблицу смещений

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

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

3.6 Поддержка нового оборудования

Мы также адаптировали и оптимизировали популярное новое аппаратное обеспечение (такое как энергонезависимая память, FPGA, QAT и т. д.), например, когда устройство оснащено аппаратным обеспечением QAT, мы решили отказаться от части ЦП, когда нагрузка ЦП хоста высока. .Сжать разгрузку в QAT для сжатия.Например, мы помещаем часть данных в постоянную память, чтобы добиться реального доступа к данным на уровне записи (мы не используем общую структуру индекса на уровне блоков, а напрямую индексируем по записи) и так на.

Здесь мы используем сжатие QAT в качестве примера для иллюстрации:

Мы знаем, что с широкой популярностью твердотельных накопителей PCIe NVMe пропускная способность и IOPS дисков значительно улучшились.
Увеличение пропускной способности диска, в свою очередь, смещает системное узкое место на ЦП.
- Работа, которую должен выполнять ЦП, включает сортировку данных (SST должен поддерживать порядок), проверку CRC, сжатие данных, сравнение запросов и т. д.
Наш первоначальный текущий план состоит в том, чтобы разгрузить сжатие данных и проверку CRC на специализированное оборудование QAT для ускорения.
- В настоящее время аппаратное обеспечение QAT относительно экономично, и даже некоторые материнские платы поставляются с собственными
Алгоритмы сжатия, которые может поддерживать сама QAT, ограничены, в основном это deflate zlib.
Когда мы удаляем сжатие данных и проверку CRC, мы можем выделить больше ЦП для SST GC и сжатия, а также максимально быстро настроить форму SST.

В настоящее время использование QAT все еще находится в стадии тестирования и официально не запущено.Следующим шагом является проведение углубленных исследований по применению FPGA.

4. Сравнительный тест

Мы использовали стендовый инструмент RocksDB, чтобы провести несколько простых тестов и сравнить отличия и различия между RocksDB, TitanDB и TerarkDB.Следует отметить, что этот инструмент использует случайно сгенерированные данные, что не очень дружелюбно к алгоритму сжатия TerarkDB.Так что разница в степени сжатия не большая.

В этом улучшении мы фокусируемся на производительности разделения KV, поэтому мы оцениваем только большее значение, чтобы подтвердить эффект улучшения:

тестовая среда:
- Исходный размер тестового набора данных составляет 256 ГБ со 128 ГБ памяти.
- CPU : 48 Core
- RAM : 128 GB
- Disk : Intel NVMe 3.4T
- Тестовая программа db_bench
- Linux version 4.14
- GCC Version 6.3.0
Содержание теста:
1. fillrandom: многопоточная случайная запись, есть повторяющиеся ключи
2. readseq: Многопоточное последовательное сканирование
3. readrandom: многопоточное случайное получение
4. seekrandom: многопоточный случайный поиск

Value size = 4KB

Value size = 32KB

5. Последующие действия

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

Для достижения этих целей нам еще многое предстоит сделать в будущем, в том числе разгрузить ЦП одного движка в кластер для распределенного уплотнения, внедрить технологии, связанные с SPDK, для повышения эффективности ввода-вывода, а также внедрить AI Tuning для большей гибкости. Ввод/вывод для различных стратегий нагрузки, введение нового оборудования (например, энергонезависимой памяти и ПЛИС) и многое другое.

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

6. Ссылки

WiscKey: Separating Keys from Values in SSD-conscious Storage
Bitcask A Log-Structured Hash Table for Fast Key/Value Data
LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data
Towards Accurate and Fast Evaluation of Multi-Stage Log-Structured Designs

поделиться больше

Глубокое понимание перегрузки TLB и оптимизации, вызванной jemalloc в ядре Linux.

ByteDance самостоятельно разработала графовую базу данных триллионов уровней и практику графовых вычислений

Практика ByteDance HDFS уровня EB

Команда инфраструктуры ByteDance

Команда инфраструктуры ByteDance — важная команда, которая поддерживает бесперебойную работу множества пользовательских продуктов ByteDance, включая Douyin, Today's Toutiao, Xigua Video и Volcano Small Video, Стабильная разработка обеспечивает гарантии и импульс.

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

В культурном плане команда активно использует открытый исходный код и инновационные аппаратные и программные архитектуры. Мы давно набираем студентов по направлению инфраструктура, подробнее см.job.bytedance.com, заинтересованные могут обращаться по электронной почте guoxinyu.0372@bytedance.com .

Добро пожаловать в техническую команду ByteDance