Перевод из книги «Designing Data-Intensive Applications, 2nd Edition» подготовлен автором сайта

Table of Contents

Глава 4. Хранение и извлечение данных

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

Ричард Фейнман, семинар Idiosyncratic Thinking (1985)

На самом базовом уровне база данных должна уметь делать две вещи: когда вы ей даёте данные — она должна их сохранить, а когда вы попросите их позже — она должна их вам вернуть.

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

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

В частности, есть большая разница между движками, оптимизированными под транзакционные нагрузки (OLTP), и теми, что оптимизированы под аналитику (OLAP). Эта глава начнётся с рассмотрения двух семейств движков для OLTP: лог-структурированных движков, которые пишут неизменяемые файловые сегменты, и движков на основе B-деревьев, которые обновляют данные на месте. Эти структуры используются как для key-value хранения, так и для вторичных индексов.

Позже, в разделе «Хранение данных для аналитики», мы рассмотрим семейство движков, оптимизированных для аналитики, а в разделе «Многомерные и полнотекстовые индексы» — кратко заглянем в индексы для более сложных запросов, например полнотекстового поиска.

Хранение и индексация для OLTP

Представим себе самую простую базу данных в мире, реализованную в виде двух функций на Bash:

#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

#!/bin/bash

db_set () {

echo "$1,$2" >> database

}

db_get () {

grep "^$1," database | sed -e "s/^$1,//" | tail -n 1

}

Эти две функции реализуют key-value storage. Можно вызвать db_set key value, и это сохранит ключ и значение в базе. Ключ и значение могут быть (почти) любыми — например, значением может быть JSON-документ. Затем можно вызвать db_get key, чтобы получить последнее значение, связанное с данным ключом.

И это работает:

$ db_set 12 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

$ db_set 12 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42

{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

Формат хранения очень простой: текстовый файл, где каждая строка содержит пару ключ-значение, разделённую запятой (примерно как CSV, если не учитывать экранирование). Каждый вызов db_set просто дописывает строку в конец файла. Если вы обновляете один и тот же ключ несколько раз, старые значения не перезаписываются — чтобы найти последнее значение, нужно взять последнюю строку с этим ключом в файле (поэтому в db_get используется tail -n 1):

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}
$ cat database
12,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'

$ db_get 42

{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database

12,{"name":"London","attractions":["Big Ben","London Eye"]}

42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

42,{"name":"San Francisco","attractions":["Exploratorium"]}

Функция db_set на самом деле работает довольно быстро для такой простой реализации, потому что дописывание в конец файла — операция обычно очень эффективная. Подобно этому, многие базы данных внутри используют лог — файл с данными только для добавления. В реальных базах приходится решать больше проблем (например, обработка конкурентных записей, освобождение дискового пространства, чтобы лог не рос бесконечно, и восстановление после краша при частично записанных данных), но базовый принцип тот же. Логи невероятно полезны, и мы будем сталкиваться с ними ещё не раз в этой книге.

Примечание

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

С другой стороны, db_get имеет ужасную производительность, если в базе много записей. Каждый раз при поиске ключа db_get должен просканировать весь файл базы от начала до конца, находя все вхождения ключа. В терминах алгоритмов, стоимость поиска — O(n): если удвоить количество записей n в базе, поиск займёт в два раза больше времени. Это плохо.

Чтобы эффективно находить значение по конкретному ключу, нужна другая структура данных — индекс. В этой главе мы рассмотрим разные структуры индексов и сравним их; общая идея в том, чтобы структурировать данные особым образом (например, отсортировать по ключу), что позволяет быстрее находить нужное. Если нужно искать одни и те же данные разными способами, могут потребоваться несколько индексов по разным частям данных.

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

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

Лог-структурированное хранение

Начнём с предположения, что вы хотите продолжать хранить данные в append-only файле, который пишет db_set, но ускорить чтение. Один из способов — хранить в памяти hash map, где каждому ключу сопоставлен байтовый offset в файле, по которому лежит последнее значение для этого ключа, как показано на рисунке 4-1.

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

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

Такой подход намного быстрее, но у него всё же есть несколько проблем:

Никогда не освобождается место на диске, занимаемое старыми лог-записями, которые были перезаписаны; если продолжать писать в базу, место на диске может закончиться.
Хэш-таблица не сохраняется, поэтому её приходится перестраивать при перезапуске базы — например, сканированием всего лог-файла, чтобы найти последнее смещение для каждого ключа. Это делает перезапуск очень медленным, если данных много.
Хэш-таблица должна помещаться в память. Теоретически можно было бы хранить её на диске, но, к сожалению, сделать дисковую хэш-таблицу производительной очень трудно. Она требует большого количества случайных операций ввода-вывода, дорого обходится при увеличении размера и сталкивается с коллизиями хэшей, для которых нужна сложная логика.
Диапазонные запросы неэффективны. Например, нельзя просто просканировать все ключи между 10000 и 19999 — придётся искать каждый ключ отдельно в хэш-таблице.

Формат файла SSTable

На практике хэш-таблицы для индексов баз данных используются не очень часто; вместо этого гораздо чаще данные хранятся в структуре, отсортированной по ключу. Пример такой структуры — Sorted String Table, или сокращённо SSTable, как показано на рисунке 4-2. Этот формат файла также хранит пары ключ-значение, но гарантирует, что они отсортированы по ключу, и каждый ключ встречается в файле только один раз.

Рисунок 4-2. SSTable с разреженным индексом, позволяющим запросам сразу переходить к нужному блоку

Теперь нет необходимости держать все ключи в памяти: пары ключ-значение внутри SSTable можно сгруппировать в блоки размером в несколько килобайт, а затем сохранить в индексе только первый ключ каждого блока. Такой индекс, который хранит лишь часть ключей, называется разреженным. Этот индекс хранится в отдельной части SSTable, например, с использованием неизменяемого B-дерева, префиксного дерева (trie) или другой структуры данных, позволяющей быстро искать ключ.

Например, на рисунке 4-2 первый ключ одного блока — handbag, а первого ключа следующего блока — handsome. Теперь допустим, вы ищете ключ handiwork, которого нет в разреженном индексе. Благодаря сортировке вы знаете, что handiwork должен находиться между handbag и handsome. Это значит, что можно перейти к смещению для handbag и просканировать файл оттуда, пока не будет найден handiwork (или до конца блока, если ключа нет в файле). Блок в несколько килобайт можно просканировать очень быстро.

Кроме того, каждый блок записей может быть сжат (что показано затемнённой областью на рисунке 4-2). Помимо экономии места на диске, сжатие также уменьшает использование пропускной способности ввода-вывода, ценой небольшой дополнительной загрузки CPU.

Построение и слияние SSTable

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

Эта проблема решается лог-структурированным подходом — гибридом между логом только для добавления и отсортированным файлом:

Когда приходит запись, она добавляется в упорядоченную in-memory структуру данных, такую как красно-чёрное дерево, skip list или trie. В этих структурах можно вставлять ключи в любом порядке, эффективно их искать и извлекать обратно в отсортированном порядке. Эта структура в памяти называется memtable.
Когда memtable вырастает больше некоторого порога — обычно несколько мегабайт — её сбрасывают на диск в отсортированном виде как файл SSTable. Такой новый SSTable называется самым свежим сегментом базы данных и хранится как отдельный файл рядом со старыми сегментами. У каждого сегмента свой собственный индекс содержимого. Пока новый сегмент пишется на диск, база может продолжать работать с новым экземпляром memtable, а память старого memtable освобождается после завершения записи SSTable.
Чтобы прочитать значение для ключа, сначала ищут ключ в memtable и в самом новом сегменте на диске. Если его там нет — ищут в следующем, более старом сегменте, и так далее, пока либо ключ не будет найден, либо не будет достигнут самый старый сегмент. Если ключ не встречается ни в одном сегменте, его нет в базе.
Время от времени в фоне запускается процесс слияния и уплотнения сегментов, чтобы объединять файлы сегментов и удалять перезаписанные или удалённые значения.

Слияние сегментов работает аналогично алгоритму mergesort. Этот процесс показан на рисунке 4-3: начинаем чтение входных файлов параллельно, смотрим на первый ключ в каждом файле, копируем в выходной файл наименьший ключ (согласно порядку сортировки) и повторяем. Если один и тот же ключ встречается в нескольких входных файлах, сохраняется только самое свежее значение. В результате получается новый объединённый сегментный файл, также отсортированный по ключу, с одним значением на ключ. При этом используется минимальное количество памяти, так как мы можем итерироваться по SSTable построчно, по одному ключу за раз.

Рисунок 4-3. Слияние нескольких сегментов SSTable с сохранением только самого свежего значения для каждого ключа

Чтобы гарантировать, что данные в memtable не будут потеряны при сбое базы, сторедж-энджин ведёт отдельный лог на диске, куда каждая запись немедленно дописывается. Этот лог не отсортирован по ключу, но это и не нужно, так как его единственная цель — восстановить memtable после сбоя. Каждый раз, когда memtable был сброшен в SSTable, соответствующая часть лога может быть удалена.

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

Алгоритм, описанный здесь, по сути используется в RocksDB, Cassandra, Scylla и HBase, все они были вдохновлены статьёй Google о Bigtable (в которой были введены термины SSTable и memtable).

Впервые этот алгоритм был опубликован в 1996 году под названием Log-Structured Merge-Tree или LSM-Tree, опираясь на более ранние работы о лог-структурированных файловых системах. Поэтому движки хранения, основанные на принципе слияния и уплотнения отсортированных файлов, часто называют LSM storage engines.

В LSM-движках сегментный файл пишется за один проход (либо при записи memtable, либо при слиянии существующих сегментов), и после этого он неизменяемый. Слияние и уплотнение сегментов могут выполняться в фоне, и пока это происходит, можно продолжать обслуживать чтения, используя старые сегментные файлы. Когда процесс слияния завершён, запросы на чтение переключаются на новый объединённый сегмент, а старые сегментные файлы могут быть удалены.

Сегментные файлы не обязательно хранить на локальном диске: они также хорошо подходят для записи в объектное хранилище. Например, такой подход используют SlateDB и Delta Lake.

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

Фильтры Блума

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

Рисунок 4-4 показывает пример фильтра Блума, содержащего два ключа и 16 бит (на самом деле он содержал бы больше ключей и больше бит). Для каждого ключа в SSTable мы вычисляем хэш-функцию, которая выдаёт набор чисел, интерпретируемых как индексы в массиве битов. Биты по этим индексам устанавливаются в 1, остальные остаются равными 0. Например, ключ handbag хэшируется в числа (2, 9, 4), поэтому мы устанавливаем 2-й, 9-й и 4-й биты в 1. Получившаяся битовая карта сохраняется как часть SSTable вместе с разреженным индексом ключей. Это занимает немного дополнительного места, но фильтр Блума обычно очень мал по сравнению с остальной частью SSTable.

Рисунок 4-4. Фильтр Блума обеспечивает быстрый вероятностный способ проверить, существует ли конкретный ключ в конкретной SSTable

Когда мы хотим узнать, содержится ли ключ в SSTable, мы вычисляем тот же хэш этого ключа, что и раньше, и проверяем биты по соответствующим индексам. Например, на рисунке 4-4 мы ищем ключ handheld, который хэшируется в (6, 11, 2). Один из этих битов равен 1 (а именно бит номер 2), а два других равны 0. Эти проверки можно выполнять чрезвычайно быстро с использованием побитовых операций, которые поддерживаются всеми CPU.

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

Вероятность ложноположительных результатов зависит от количества ключей, количества бит, установленных на каждый ключ, и общего количества бит в фильтре Блума. Для подбора параметров под ваше приложение можно использовать онлайн-калькулятор. В качестве правила большого пальца: необходимо выделять 10 бит пространства фильтра Блума на каждый ключ в SSTable, чтобы вероятность ложноположительного результата составляла 1%; при этом вероятность уменьшается в 10 раз за каждые дополнительные 5 бит на ключ.

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

Если фильтр Блума говорит, что ключ отсутствует, мы можем безопасно пропустить эту SSTable, так как можем быть уверены, что она не содержит ключ.

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

Стратегии уплотнения (Compaction strategies)

Важная деталь заключается в том, как LSM-хранилище выбирает момент для выполнения уплотнения и какие SSTable включать в compaction. Многие системы на основе LSM позволяют настраивать стратегию уплотнения, и некоторые из распространённых вариантов такие:

Уплотнение по размеру (size-tiered compaction).
Более новые и меньшие SSTable последовательно сливаются в более старые и большие SSTable. SSTable, содержащие старые данные, могут становиться очень большими, и их слияние требует большого объёма временного дискового пространства. Преимущество этой стратегии в том, что она может выдерживать очень высокую скорость записи.
Уплотнение по уровням (leveled compaction).
Диапазон ключей делится на меньшие SSTable, а старые данные перемещаются в отдельные «уровни», что позволяет выполнять уплотнение более постепенно и использовать меньше места на диске, чем при стратегии size-tiered. Эта стратегия эффективнее для чтения, чем уплотнение по размеру, потому что движку хранения нужно читать меньше SSTable, чтобы проверить, содержат ли они ключ.

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

Хотя существует много нюансов, базовая идея LSM-деревьев — хранить каскад SSTable, которые сливаются в фоне — проста и эффективна. Мы подробнее рассмотрим их характеристики производительности в разделе «Сравнение B-деревьев и LSM-деревьев».

Встроенные движки хранения

Многие базы данных работают как сервис, принимающий запросы по сети, но существуют и встроенные базы данных, которые не предоставляют сетевой API. Вместо этого это библиотеки, работающие в том же процессе, что и ваш код приложения, обычно читающие и пишущие файлы на локальном диске, и вы взаимодействуете с ними через обычные вызовы функций. Примеры встроенных движков хранения: RocksDB, SQLite, LMDB, DuckDB и KùzuDB.

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

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

B-деревья

Лог-структурированный подход популярен, но это не единственная форма key-value хранения. Наиболее широко используемая структура для чтения и записи записей базы данных по ключу — это B-дерево.

Впервые представленное в 1970 году и названное «повсеместным» менее чем через 10 лет, B-дерево отлично выдержало испытание временем. Оно остаётся стандартной реализацией индекса почти во всех реляционных базах данных, и многие нереляционные базы используют их тоже.

Как и SSTable, B-деревья хранят пары ключ-значение, отсортированные по ключу, что позволяет эффективно выполнять поиск по ключу и диапазонные запросы. Но на этом сходство заканчивается: B-деревья имеют совершенно иную философию проектирования.

Ранее рассмотренные лог-структурированные индексы разбивают базу данных на сегменты переменного размера, обычно несколько мегабайт или больше, которые записываются один раз и затем становятся неизменяемыми. Напротив, B-деревья разбивают базу на блоки или страницы фиксированного размера и могут перезаписывать страницу «на месте». Страница традиционно имеет размер 4 КиБ, но PostgreSQL сейчас использует 8 КиБ, а MySQL по умолчанию — 16 КиБ.

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

Рисунок 4-5. Поиск ключа 251 с использованием индекса B-дерева. От корневой страницы мы сначала переходим по ссылке на страницу для ключей 200–300, затем на страницу для ключей 250–270

Одна страница назначается корнем B-дерева; каждый раз, когда вы хотите найти ключ в индексе, вы начинаете отсюда. Страница содержит несколько ключей и ссылки на дочерние страницы. Каждый дочерний элемент отвечает за непрерывный диапазон ключей, а ключи между ссылками указывают, где проходят границы между этими диапазонами. (Эта структура иногда называется B+ деревом, но нам не нужно отличать её от других вариантов B-дерева.)

В примере на рисунке 4-5 мы ищем ключ 251, поэтому знаем, что нужно следовать по ссылке на страницу между границами 200 и 300. Это приводит нас на похожую страницу, которая дальше разбивает диапазон 200–300 на поддиапазоны. В итоге мы доходим до страницы, содержащей отдельные ключи (листовой страницы), которая либо содержит значение для каждого ключа inline, либо содержит ссылки на страницы, где можно найти значения.

Количество ссылок на дочерние страницы в одной странице B-дерева называется фактором ветвления. Например, на рисунке 4-5 фактор ветвления равен шести. На практике он зависит от объёма места, необходимого для хранения ссылок на страницы и границ диапазонов, но обычно составляет несколько сотен.

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

Рисунок 4-6. Рост B-дерева путём разделения страницы по граничному ключу 337. Родительская страница обновляется так, чтобы ссылаться на оба дочерних элемента

В примере на рисунке 4-6 мы хотим вставить ключ 334, но страница для диапазона 333–345 уже заполнена. Поэтому мы делим её на страницу для диапазона 333–337 (включая новый ключ) и страницу для диапазона 337–344. Мы также должны обновить родительскую страницу, чтобы она содержала ссылки на оба дочерних элемента, с граничным значением 337 между ними. Если в родительской странице недостаточно места для новой ссылки, её тоже придётся разделить, и разделения могут продолжаться вплоть до корня дерева. Когда корень делится, мы создаём над ним новый корень. Удаление ключей (которое может требовать слияния узлов) более сложно.

Этот алгоритм гарантирует, что дерево остаётся сбалансированным: B-дерево с n ключами всегда имеет глубину O(log n). Большинство баз данных можно уместить в B-дерево глубиной три или четыре уровня, так что не приходится проходить много ссылок, чтобы найти нужную страницу. (Четырёхуровневое дерево из страниц по 4 КиБ с фактором ветвления 500 может хранить до 250 ТБ.)

Надёжность B-деревьев

Базовая операция записи в B-дереве заключается в перезаписи страницы на диске новыми данными. Предполагается, что перезапись не изменяет расположение страницы; т.е. все ссылки на эту страницу остаются корректными после её перезаписи. Это резко контрастирует с индексами на основе журнала, такими как LSM-деревья, которые только добавляют данные в файлы (и в конечном счёте удаляют устаревшие файлы), но никогда не изменяют файлы на месте.
Перезапись нескольких страниц одновременно, как при разделении страницы, — это опасная операция: если база данных аварийно завершится после того, как только часть страниц была записана, в итоге получится повреждённое дерево (например, может появиться «осиротевшая» страница, которая не является дочерней ни для одного родителя).
Чтобы сделать базу данных устойчивой к сбоям, в реализации B-деревьев обычно добавляется дополнительная структура данных на диске: журнал предзаписи (WAL, Write-Ahead Log). Это файл только для добавления, в который каждая модификация B-дерева должна быть записана перед тем, как её можно будет применить к страницам самого дерева. Когда база данных запускается после сбоя, этот журнал используется для восстановления B-дерева в согласованное состояние. В файловых системах эквивалентный механизм называется журналированием.
Для повышения производительности реализации B-деревьев, как правило, не записывают сразу каждую изменённую страницу на диск, а сначала некоторое время буферизуют страницы B-дерева в памяти. Тогда журнал предзаписи также гарантирует, что данные не будут потеряны в случае сбоя: пока данные были записаны в WAL и сброшены на диск с помощью системного вызова fsync(), данные будут надёжными, так как база данных сможет восстановить их после сбоя.

Варианты B-деревьев

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

Вместо перезаписи страниц и поддержки WAL для восстановления после сбоев некоторые базы данных (например, LMDB) используют схему «copy-on-write». Изменённая страница записывается в другое место, и создаётся новая версия родительских страниц дерева, указывающая на новое местоположение. Такой подход также полезен для управления параллелизмом, как мы увидим в разделе «Изоляция снимков и повторяемое чтение».
Можно экономить место на страницах, не сохраняя полный ключ, а сокращая его. Особенно на внутренних страницах дерева ключи должны содержать только достаточно информации, чтобы служить границами между диапазонами ключей. Упаковка большего количества ключей в страницу позволяет дереву иметь больший коэффициент ветвления и, следовательно, меньше уровней.
Чтобы ускорить сканирование диапазона ключей в отсортированном порядке, некоторые реализации B-деревьев пытаются расположить дерево так, чтобы страницы-листья находились на диске в последовательном порядке, уменьшая количество обращений к диску. Однако поддерживать этот порядок по мере роста дерева трудно.
В дерево добавляются дополнительные указатели. Например, каждая страница-лист может иметь ссылки на свои соседние страницы слева и справа, что позволяет сканировать ключи по порядку без возврата к родительским страницам.

Сравнение B-деревьев и LSM-деревьев

Как правило, LSM-деревья лучше подходят для приложений с интенсивной записью, тогда как B-деревья быстрее при чтении. Однако результаты тестов часто зависят от деталей нагрузки. Чтобы провести корректное сравнение, необходимо тестировать системы именно с вашей нагрузкой. Более того, это не строгое «или/или» между LSM и B-деревьями: движки хранения иногда сочетают характеристики обоих подходов, например, имеют несколько B-деревьев и объединяют их в стиле LSM. В этом разделе мы кратко обсудим несколько вещей, которые стоит учитывать при измерении производительности движка хранения.

Производительность чтения

В B-дереве поиск ключа включает чтение одной страницы на каждом уровне B-дерева. Так как количество уровней обычно невелико, это означает, что чтение из B-дерева обычно быстрое и имеет предсказуемую производительность. В LSM-движке чтения часто должны проверять несколько разных SSTable на разных стадиях уплотнения, но фильтры Блума помогают сократить количество фактических операций ввода-вывода. Оба подхода могут работать хорошо, и то, какой быстрее, зависит от деталей движка хранения и нагрузки.
Диапазонные запросы просты и быстры в B-деревьях, так как они используют отсортированную структуру дерева. В LSM-хранилищах диапазонные запросы также могут использовать сортировку в SSTable, но им нужно сканировать все сегменты параллельно и объединять результаты. Фильтры Блума не помогают при диапазонных запросах (так как пришлось бы вычислять хеш для каждого возможного ключа внутри диапазона, что непрактично), поэтому диапазонные запросы обходятся дороже, чем точечные запросы в подходе LSM.
Высокая пропускная способность записей может вызвать всплески задержек в движке хранения на основе журнала, если memtable заполняется. Это происходит, если данные не могут достаточно быстро записываться на диск, возможно, потому что процесс уплотнения не успевает за входящими записями. Многие движки хранения, включая RocksDB, используют механизм обратного давления в этой ситуации: они приостанавливают все чтения и записи до тех пор, пока memtable не будет выгружена на диск.
Что касается пропускной способности чтения, современные SSD (и особенно NVMe) могут выполнять множество независимых запросов на чтение параллельно. И LSM-деревья, и B-деревья способны обеспечивать высокую пропускную способность чтения, но движки хранения должны быть тщательно спроектированы, чтобы использовать это параллельное выполнение.

Последовательные и случайные записи

В B-дереве, если приложение записывает ключи, разбросанные по всему пространству ключей, то и операции на диске также оказываются случайно разбросанными, так как страницы, которые нужно перезаписать движку хранения, могут находиться где угодно на диске. С другой стороны, движок хранения на основе журнала записывает целые файлы сегментов за раз (либо выгружая memtable, либо при уплотнении существующих сегментов), которые намного больше страницы в B-дереве.
Шаблон множества мелких, разбросанных записей (как в B-деревьях) называется случайными записями, в то время как шаблон меньшего количества крупных записей (как в LSM-деревьях) называется последовательными записями. Диски в целом имеют более высокую пропускную способность для последовательных записей, чем для случайных, что означает, что движок хранения на основе журнала обычно способен выдерживать более высокую нагрузку на запись на том же оборудовании, чем B-дерево. Эта разница особенно велика на жёстких дисках (HDD); на твердотельных накопителях (SSD), которые используются в большинстве баз данных сегодня, разница меньше, но всё же заметна (см. «Последовательные и случайные записи на SSD»).

ПОСЛЕДОВАТЕЛЬНЫЕ И СЛУЧАЙНЫЕ ЗАПИСИ НА SSD

На жёстких дисках (HDD) последовательные записи намного быстрее случайных: случайная запись должна механически переместить головку диска в новое положение и подождать, пока нужная часть пластины пройдёт под головкой диска, что занимает несколько миллисекунд — вечность по меркам вычислительных масштабов времени. Однако SSD (твердотельные накопители), включая NVMe (Non-Volatile Memory Express, т.е. флеш-память, подключённая к шине PCI Express), теперь обогнали HDD для многих сценариев использования, и они не подвержены таким механическим ограничениям.
Тем не менее, SSD также имеют большую пропускную способность для последовательных записей, чем для случайных. Причина в том, что флеш-память можно читать или записывать по одной странице (обычно 4 КиБ) за раз, но стирать можно только блоками (обычно 512 КиБ) за раз. Некоторые страницы в блоке могут содержать актуальные данные, а другие — данные, которые больше не нужны. Перед тем как стереть блок, контроллер должен сначала переместить страницы с актуальными данными в другие блоки; этот процесс называется сборкой мусора (GC, Garbage Collection).
Последовательная нагрузка записи записывает большие куски данных за раз, поэтому велика вероятность, что весь блок в 512 КиБ принадлежит одному файлу; когда этот файл позже удаляется, весь блок можно стереть без выполнения GC. С другой стороны, при случайной нагрузке записи более вероятно, что блок содержит смесь страниц с актуальными и неактуальными данными, поэтому GC приходится выполнять больше работы, прежде чем блок можно стереть.
Пропускная способность записи, потребляемая GC, недоступна для приложения. Более того, дополнительные записи, выполняемые GC, способствуют износу флеш-памяти; поэтому случайные записи изнашивают накопитель быстрее, чем последовательные.

Усиление записи (Write amplification)

В любом типе движка хранения один запрос на запись от приложения превращается во множество операций ввода-вывода на нижележащем диске. В LSM-деревьях значение сначала записывается в журнал для обеспечения надежности, затем снова, когда memtable сбрасывается на диск, и снова каждый раз, когда пара ключ-значение участвует в процессах уплотнения. (Если значения значительно больше ключей, эти накладные расходы можно сократить, сохраняя значения отдельно от ключей и выполняя уплотнение только над SSTable, содержащими ключи и ссылки на значения.)

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

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

Усиление записи является проблемой как в LSM-деревьях, так и в B-деревьях. Какой вариант лучше — зависит от различных факторов, таких как длина ключей и значений, а также частота перезаписи существующих ключей по сравнению с добавлением новых. Для типичных нагрузок LSM-деревья, как правило, имеют меньшее усиление записи, потому что им не нужно переписывать целые страницы, и они могут сжимать блоки SSTable. Это еще один фактор, делающий движки хранения на основе LSM хорошо подходящими для нагрузок с интенсивной записью.

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

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

Использование дискового пространства (Disk space usage)

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

Фрагментация является меньшей проблемой в LSM-деревьях, поскольку процесс уплотнения периодически переписывает файлы данных, и SSTable не имеют страниц с неиспользованным пространством. Более того, блоки пар ключ-значение в SSTable лучше поддаются сжатию, и поэтому часто создают меньшие по размеру файлы на диске, чем B-деревья. Ключи и значения, которые были перезаписаны, продолжают занимать место, пока не будут удалены уплотнением (compaction), но эти накладные расходы достаточно низкие при использовании уровневого уплотнения. Уплотнение по уровням использует больше дискового пространства, особенно временно во время самого уплотнения.

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

С другой стороны, неизменяемая природа файлов сегментов SSTable полезна, если необходимо сделать снимок базы данных в определенный момент времени (например, для резервного копирования или создания копии базы данных для тестирования): можно сбросить memtable и зафиксировать, какие файлы сегментов существовали в тот момент времени. Пока файлы, входящие в снимок, не удаляются, их не нужно фактически копировать. В B-дереве, страницы которого перезаписываются, сделать такой снимок эффективно гораздо сложнее.

Множественные и вторичные индексы (Multi-Column and Secondary Indexes)

До этого мы рассматривали только индексы по ключу-значению, которые похожи на индекс по первичному ключу в реляционной модели. Первичный ключ однозначно идентифицирует одну строку в реляционной таблице, один документ в документной базе данных или одну вершину в графовой базе данных. Другие записи в базе могут ссылаться на эту строку/документ/вершину по её первичному ключу (или ID), и индекс используется для разрешения таких ссылок.

Также очень часто используются вторичные индексы. В реляционных базах данных можно создать несколько вторичных индексов на одной и той же таблице с помощью команды CREATE INDEX, что позволяет выполнять поиск по столбцам, отличным от первичного ключа. Например, на Рисунке 3-1 в Главе 3 у вас, скорее всего, будет вторичный индекс по столбцам user_id, чтобы можно было находить все строки, принадлежащие одному пользователю, в каждой из таблиц.

Вторичный индекс легко построить из индекса по ключу-значению. Основное отличие состоит в том, что во вторичном индексе индексируемые значения не обязательно уникальны; то есть под одной индексной записью может находиться множество строк (документов, вершин). Это можно решить двумя способами: либо сделать каждое значение в индексе списком идентификаторов совпадающих строк (как список вхождений в полнотекстовом индексе), либо сделать каждую запись уникальной, добавив к ней идентификатор строки. Для реализации индекса могут использоваться как движки хранения с обновлением на месте (например, B-деревья), так и журнально-структурированное хранение.

Хранение значений внутри индекса (Storing values within the index)

Ключ в индексе — это то, по чему выполняется поиск в запросах, но значение может быть одним из нескольких вариантов:

Если фактические данные (строка, документ, вершина) хранятся непосредственно внутри структуры индекса, это называется кластерным индексом. Например, в движке хранения InnoDB в MySQL первичный ключ таблицы всегда является кластерным индексом, а в SQL Server можно указать один кластерный индекс для каждой таблицы.
Альтернативно, значением может быть ссылка на фактические данные: либо первичный ключ соответствующей строки (InnoDB делает так для вторичных индексов), либо прямое указание на расположение на диске. В последнем случае место, где хранятся строки, называется heap file (кучей), и оно хранит данные без какого-либо определенного порядка (оно может быть только-добавляемым, либо может отслеживать удаленные строки, чтобы позже перезаписывать их новыми данными). Например, Postgres использует подход с heap file.
Промежуточный вариант между двумя подходами — это покрывающий индекс (covering index) или индекс с включенными столбцами, который хранит некоторые столбцы таблицы внутри индекса, в дополнение к хранению полной строки в куче или в кластерном индексе по первичному ключу. Это позволяет некоторым запросам выполняться только с использованием индекса, без необходимости обращаться к первичному ключу или искать в куче (в таком случае говорят, что индекс «покрывает» запрос). Это может сделать некоторые запросы быстрее, но дублирование данных означает, что индекс занимает больше места на диске и замедляет операции записи.

Обсужденные до сих пор индексы сопоставляют только один ключ со значением. Если необходимо выполнять запрос по нескольким столбцам таблицы (или нескольким полям документа) одновременно.

При обновлении значения без изменения ключа подход с heap file позволяет перезаписывать запись на месте, при условии, что новое значение не больше старого. Ситуация усложняется, если новое значение больше, так как его, вероятно, придется переместить в новое место в куче, где есть достаточно пространства. В таком случае либо все индексы должны быть обновлены, чтобы указывать на новое место записи в куче, либо в старом месте оставляется пересылающий указатель (forwarding pointer).

Хранение всего в памяти (Keeping everything in memory)

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

По мере того как RAM дешевеет, аргумент о стоимости за гигабайт теряет силу. Многие наборы данных просто не такие большие, поэтому вполне реально держать их полностью в памяти, возможно, распределив между несколькими машинами. Это привело к разработке in-memory баз данных.

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

Когда база данных в памяти перезапускается, ей нужно заново загрузить свое состояние — либо с диска, либо по сети от реплики (если только не используется специальное оборудование). Несмотря на запись на диск, это по-прежнему база данных в памяти, потому что диск используется только как журнал в режиме append-only для надежности, а чтение всегда выполняется из памяти. Запись на диск также имеет эксплуатационные преимущества: файлы на диске легко резервировать, просматривать и анализировать внешними утилитами.

Продукты такие как VoltDB, SingleStore и Oracle TimesTen — это базы данных в памяти с реляционной моделью, и их производители утверждают, что они могут предложить значительный прирост производительности за счет устранения всех накладных расходов, связанных с управлением структурами данных на диске. RAMCloud — это открытая in-memory база данных ключ-значение с надежностью (использует журнальную структуру как для данных в памяти, так и для данных на диске). Redis и Couchbase обеспечивают слабую надежность, записывая данные на диск асинхронно.

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

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

Хранение данных для аналитики (Data Storage for Analytics)

Модель данных хранилища данных чаще всего является реляционной, потому что SQL, как правило, хорошо подходит для аналитических запросов. Существует множество графических инструментов анализа данных, которые генерируют SQL-запросы, визуализируют результаты и позволяют аналитикам исследовать данные (через такие операции, как детализация (drill-down) и разбиение/комбинирование (slicing and dicing)).

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

Некоторые базы данных, такие как Microsoft SQL Server, SAP HANA и SingleStore, поддерживают как транзакционную обработку, так и хранилище данных в одном продукте. Однако эти базы данных для гибридной транзакционной и аналитической обработки (HTAP, Hybrid Transactional and Analytical Processing), упомянутые в разделе «Хранилища данных», всё чаще становятся двумя отдельными движками хранения и запросов, которые, тем не менее, доступны через общий SQL-интерфейс.

Облачные хранилища данных (Cloud Data Warehouses)

Поставщики хранилищ данных, такие как Teradata, Vertica и SAP HANA, продают как локальные хранилища по коммерческим лицензиям, так и облачные решения. Но поскольку многие их клиенты переходят в облако, новые облачные хранилища данных, такие как Google Cloud BigQuery, Amazon Redshift и Snowflake, также получили широкое распространение. В отличие от традиционных хранилищ данных, облачные хранилища используют масштабируемую облачную инфраструктуру, такую как объектное хранилище и безсерверные вычислительные платформы.

Облачные хранилища данных, как правило, лучше интегрируются с другими облачными сервисами и более эластичны. Например, многие облачные хранилища поддерживают автоматическую загрузку логов и предлагают простую интеграцию с фреймворками обработки данных, такими как Google Cloud Dataflow или Amazon Web Services Kinesis. Эти хранилища также более эластичны, потому что они разделяют вычисления для запросов и слой хранения. Данные сохраняются в объектном хранилище, а не на локальных дисках, что позволяет легко независимо масштабировать емкость хранения и вычислительные ресурсы для запросов, как мы уже видели в разделе «Архитектура облачных систем» (Cloud-Native System Architecture).

Открытые хранилища данных, такие как Apache Hive, Trino и Apache Spark, также развивались вместе с облаком. По мере того как хранение данных для аналитики переместилось в озёра данных (data lakes) на объектных хранилищах, открытые хранилища начали разделяться на отдельные компоненты. Следующие части, которые ранее были интегрированы в единую систему, такую как Apache Hive, теперь часто реализуются как отдельные компоненты:

Движок запросов (Query engine)

Движки запросов, такие как Trino, Apache DataFusion и Presto, разбирают SQL-запросы, оптимизируют их в планы выполнения и исполняют их над данными. Выполнение обычно требует параллельных распределённых задач обработки данных. Некоторые движки запросов предоставляют встроенное выполнение задач, в то время как другие используют сторонние фреймворки выполнения, такие как Apache Spark или Apache Flink.

Формат хранения (Storage format)

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

Формат таблицы (Table format)

Файлы, записанные в Apache Parquet и аналогичных форматах хранения, обычно являются неизменяемыми после записи. Для поддержки вставок и удалений строк используется формат таблицы, такой как Apache Iceberg или формат Delta от Databricks. Форматы таблиц определяют файловый формат, который указывает, какие файлы составляют таблицу, вместе со схемой таблицы. Такие форматы также предлагают расширенные возможности, такие как time travel (возможность выполнять запросы к таблице в состоянии на предыдущий момент времени), сбор мусора и даже транзакции.

Каталог данных (Data catalog)

Так же, как формат таблицы определяет, какие файлы составляют таблицу, каталог данных определяет, какие таблицы составляют базу данных. Каталоги используются для создания, переименования и удаления таблиц. В отличие от форматов хранения и таблиц, каталоги данных, такие как Polaris от Snowflake и Unity Catalog от Databricks, обычно работают как отдельный сервис, к которому можно обращаться через REST-интерфейс. Apache Iceberg также предлагает каталог, который может работать внутри клиента или как отдельный процесс. Движки запросов используют информацию каталога при чтении и записи таблиц. Традиционно каталоги и движки запросов были интегрированы, но их разделение позволило системам обнаружения данных и управления данными (обсуждается в разделе «Системы данных, закон и общество» — Data Systems, Law, and Society) также получать доступ к метаданным каталогов.

Хранение, ориентированное на колонки (Column-Oriented Storage)

Как обсуждалось в разделе «Звёзды и снежинки: схемы для аналитики» (Stars and Snowflakes: Schemas for Analytics), хранилища данных по соглашению часто используют реляционную схему с большой фактографической таблицей, содержащей внешние ключи, ссылающиеся на таблицы измерений. Если в ваших фактографических таблицах находятся триллионы строк и петабайты данных, то их эффективное хранение и запросы становятся сложной задачей. Таблицы измерений обычно значительно меньше (миллионы строк), поэтому в этом разделе мы сосредоточимся на хранении фактов.

Хотя фактографические таблицы часто содержат более 100 колонок, типичный запрос к хранилищу данных обращается лишь к 4–5 из них за раз («SELECT *»-запросы редко нужны для аналитики). Рассмотрим запрос в примере 4-1: он обращается к большому числу строк (каждое событие покупки фруктов или сладостей в течение календарного 2024 года), но ему нужно получить доступ лишь к трём колонкам таблицы fact_sales: date_key, product_sk и quantity. Все остальные колонки запрос игнорирует.

Пример 4-1. Анализ того, склонны ли люди покупать больше свежих фруктов или сладостей в зависимости от дня недели

SELECT
dim_date.weekday, dim_product.category,
SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
JOIN dim_date    ON fact_sales.date_key   = dim_date.date_key
JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
dim_date.year = 2024 AND
dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
dim_date.weekday, dim_product.category;

SELECT

dim_date.weekday, dim_product.category,

SUM(fact_sales.quantity) AS quantity_sold

FROM fact_sales

JOIN dim_date ON fact_sales.date_key = dim_date.date_key

JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk

WHERE

dim_date.year = 2024 AND

dim_product.category IN ('Fresh fruit', 'Candy')

GROUP BY

dim_date.weekday, dim_product.category;

Как можно выполнить этот запрос эффективно?

В большинстве OLTP-баз данных хранение организовано построчно: все значения из одной строки таблицы хранятся рядом друг с другом. Документо-ориентированные базы данных похожи: весь документ обычно хранится как одна непрерывная последовательность байт. Это можно увидеть в примере CSV на рисунке 4-1.

Чтобы обработать запрос, подобный примеру 4-1, у вас могут быть индексы на fact_sales.date_key и/или fact_sales.product_sk, которые указывают движку хранения, где найти все продажи за определённую дату или для определённого продукта. Но затем построчный движок хранения всё равно должен загрузить все эти строки (каждая из которых состоит из более чем 100 атрибутов) с диска в память, разобрать их и отфильтровать те, что не соответствуют условиям. Это может занять много времени.

Идея хранения, ориентированного на колонки (или колоночного хранения), проста: не хранить все значения одной строки вместе, а хранить все значения каждой колонки вместе. Если каждая колонка хранится отдельно, то запросу нужно читать и разбирать только те колонки, которые используются в этом запросе, что может существенно сэкономить ресурсы. Принцип показан на рисунке 4-7 с использованием расширенной версии фактографической таблицы из рисунка 3-5.

Примечание
Колоночное хранение проще всего понять в реляционной модели данных, но оно в равной мере применимо и к нереляционным данным. Например, Parquet — это формат колоночного хранения, который поддерживает документо-ориентированную модель данных, основанную на Google Dremel, с использованием техники, известной как shredding или striping.

Рисунок 4-7. Хранение реляционных данных по колонкам, а не по строкам

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

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

Колоночное хранение используется почти во всех аналитических базах данных сегодня — от масштабных облачных хранилищ данных, таких как Snowflake, до односерверных встраиваемых баз данных, таких как DuckDB, и систем аналитики продуктов, таких как Pinot и Druid. Оно используется в форматах хранения, таких как Parquet, ORC, Lance и Nimble, а также во внутрипамятных аналитических форматах, таких как Apache Arrow и Pandas/NumPy. Некоторые базы данных временных рядов, такие как InfluxDB IOx и TimescaleDB, также основаны на колоночном хранении.

Сжатие колонок (Column Compression)

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

Взгляните на последовательности значений для каждой колонки на рисунке 4-7: они часто выглядят довольно повторяющимися, что является хорошим признаком для сжатия. В зависимости от данных в колонке можно использовать разные методы сжатия. Один из методов, который особенно эффективен в хранилищах данных, — это битовая (bitmap) кодировка, показанная на рисунке 4-8.

Рисунок 4-8. Сжатое, индексированное битовыми картами хранение одной колонки

Часто количество уникальных значений в колонке невелико по сравнению с количеством строк (например, у ритейлера могут быть миллиарды транзакций продаж, но только 100 000 уникальных продуктов). Мы можем взять колонку с n уникальными значениями и превратить её в n отдельных битовых карт: одну битовую карту для каждого уникального значения, с одним битом для каждой строки. Бит равен 1, если строка имеет это значение, и 0 — если нет.

Один из вариантов — хранить эти битовые карты, используя один бит на строку. Однако такие карты, как правило, содержат много нулей (мы говорим, что они разреженные). В таком случае битовые карты можно дополнительно кодировать с помощью run-length encoding: подсчитывать количество последовательных нулей или единиц и хранить это число, как показано в нижней части рисунка 4-8. Такие техники, как roaring bitmaps, переключаются между двумя представлениями битовых карт, используя то, которое является наиболее компактным. Это может сделать кодировку колонки исключительно эффективной.

Битовые индексы, подобные этим, очень хорошо подходят для типов запросов, которые часто встречаются в хранилище данных. Например:

WHERE product_sk IN (31, 68, 69)

1	WHERE product_sk IN (31, 68, 69)

Загрузить три битовые карты для product_sk = 31, product_sk = 68 и product_sk = 69, и вычислить побитовое ИЛИ (OR) трёх карт, что можно сделать очень эффективно.

WHERE product_sk = 30 AND store_sk = 3

1	WHERE product_sk = 30 AND store_sk = 3

Загрузить битовые карты для product_sk = 30 и store_sk = 3, и вычислить побитовое И (AND). Это работает потому, что колонки содержат строки в одном и том же порядке, поэтому k-й бит в битовой карте одной колонки соответствует той же строке, что и k-й бит в битовой карте другой колонки.

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

Примечание

Не путайте колоночные базы данных с широкими колонками (также известными как column-family), в которых строка может содержать тысячи колонок, и нет необходимости, чтобы у всех строк были одинаковые колонки. Несмотря на сходство в названии, базы данных с широкими колонками ориентированы на строки, поскольку они хранят все значения строки вместе. Примеры модели с широкими колонками — Google Bigtable, Apache Accumulo и HBase.

Порядок сортировки в колоночном хранении (Sort Order in Column Storage)

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

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

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

Вторая колонка может определять порядок сортировки строк, имеющих одинаковое значение в первой колонке. Например, если date_key является первым ключом сортировки в рисунке 4-7, разумно выбрать product_sk в качестве второго ключа сортировки, чтобы все продажи одного продукта за один день хранились вместе. Это поможет запросам, которые должны группировать или фильтровать продажи по продукту в пределах определённого диапазона дат.

Ещё одно преимущество упорядочивания заключается в том, что оно может помочь со сжатием колонок. Если у первичного ключа сортировки немного уникальных значений, то после сортировки образуются длинные последовательности, где одно и то же значение повторяется много раз подряд. Простое run-length encoding, которое мы использовали для битовых карт на рисунке 4-8, может сжать такую колонку до нескольких килобайт — даже если таблица содержит миллиарды строк.

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

Запись в колоночное хранилище (Writing to Column-Oriented Storage)

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

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

Для выполнения записей пакетами часто используется журналируемый (log-structured) подход. Все записи сначала попадают в ориентированное на строки, отсортированное, хранимое в памяти хранилище. Когда накапливается достаточно записей, они сливаются с колоночными закодированными файлами на диске и записываются в новые файлы пакетно. Так как старые файлы остаются неизменяемыми, а новые записываются целиком, объектное хранилище хорошо подходит для их хранения.

Запросам необходимо учитывать как данные колонок на диске, так и недавние записи в памяти и объединять их. Движок выполнения запросов скрывает это различие от пользователя. С точки зрения аналитика, данные, изменённые с помощью вставок, обновлений или удалений, немедленно отражаются в последующих запросах. Так работают Snowflake, Vertica, Apache Pinot, Apache Druid и многие другие.

Выполнение запросов: компиляция и векторизация (Query Execution: Compilation and Vectorization)

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

Внутри каждого оператора движку запросов необходимо выполнять различные действия со значениями в колонке, например находить все строки, где значение входит в определённый набор значений (возможно, как часть join), или проверять, больше ли значение 15. Также нужно просматривать несколько колонок для одной и той же строки, например чтобы найти все транзакции продаж, где продукт — это бананы, а магазин — это определённый интересующий магазин.

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

Компиляция запросов (Query compilation)

Движок запросов берёт SQL-запрос и генерирует код для его выполнения. Код перебирает строки одну за другой, смотрит на значения в интересующих колонках, выполняет необходимые сравнения или вычисления и копирует нужные значения в выходной буфер, если условия удовлетворены. Движок запросов компилирует сгенерированный код в машинный код (часто с использованием существующего компилятора, такого как LLVM), а затем запускает его на колоночных закодированных данных, загруженных в память. Такой подход к генерации кода похож на just-in-time (JIT) компиляцию, используемую в JVM и аналогичных средах выполнения.

Векторизованная обработка (Vectorized processing)

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

Например, мы можем передать колонку product_sk и ID продукта «бананы» оператору равенства и получить в ответ битовую карту (по одному биту на каждое значение входной колонки, где 1 означает «это банан»); затем мы можем передать колонку store_sk и ID интересующего магазина тому же оператору равенства и получить другую битовую карту; а затем передать обе карты оператору «побитовое И (AND)», как показано на рисунке 4-9. Результатом будет битовая карта, содержащая 1 для всех продаж бананов в данном магазине.

Рисунок 4-9. Побитовое И двух битовых карт подходит для векторизации

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

предпочтение последовательного доступа к памяти перед случайным доступом для снижения числа промахов в кэше;
выполнение большей части работы во внутренних циклах (с малым числом инструкций и без вызовов функций), чтобы загрузить конвейер обработки инструкций CPU и избежать ошибок предсказания переходов;
использование параллелизма, такого как многопоточность и инструкции single-instruction-multi-data (SIMD);
работа напрямую с сжатыми данными без их декодирования в отдельное представление в памяти, что экономит затраты на выделение памяти и копирование.

Материализованные представления и кубы данных (Materialized Views and Data Cubes)

Мы уже встречались с материализованными представлениями в разделе “Materializing and Updating Timelines”: в реляционной модели данных это объект, похожий на таблицу, содержимое которого является результатом некоторого запроса. Разница в том, что материализованное представление — это фактическая копия результатов запроса, записанная на диск, тогда как виртуальное представление — это всего лишь ярлык для упрощённой записи запросов. Когда вы читаете из виртуального представления, SQL-движок на лету разворачивает его в исходный запрос представления и затем обрабатывает уже развёрнутый запрос.

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

Материализованные агрегаты — это разновидность материализованных представлений, которая может быть полезна в хранилищах данных. Как мы обсуждали ранее, запросы в хранилище данных часто включают агрегатные функции, такие как COUNT, SUM, AVG, MIN или MAX в SQL. Если одни и те же агрегаты используются многими разными запросами, может быть расточительно каждый раз пересчитывать их на сырых данных. Почему бы не закэшировать некоторые из наиболее часто используемых подсчётов или сумм? Куб данных (data cube) или OLAP-куб делает именно это, создавая сетку агрегатов, сгруппированных по различным измерениям. На рисунке 4-10 показан пример.

Рисунок 4-10. Два измерения куба данных, агрегирование данных суммированием

Представим, что каждый факт имеет внешние ключи только к двум таблицам измерений — на рисунке 4-10 это date_key и product_sk. Тогда можно нарисовать двумерную таблицу: по одной оси — даты, по другой — продукты. Каждая ячейка содержит агрегат (например, SUM) атрибута (например, net_price) всех фактов с данной комбинацией дата–продукт. Затем можно применить тот же агрегат по каждой строке или столбцу и получить сводку, уменьшенную на одно измерение (например, продажи по продукту без учёта даты или продажи по дате без учёта продукта).

В общем случае факты часто имеют больше двух измерений. На рисунке 3-5 пять измерений: дата, продукт, магазин, акция и клиент. Намного труднее представить, как выглядел бы пятиразмерный гиперкуб, но принцип остаётся тем же: каждая ячейка содержит продажи для конкретной комбинации дата–продукт–магазин–акция–клиент. Эти значения затем можно многократно агрегировать вдоль каждого из измерений.

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

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

Многомерные и полнотекстовые индексы (Multidimensional and Full-Text Indexes)

B-деревья и LSM-деревья позволяют выполнять диапазонные запросы по одному атрибуту: например, если ключом является имя пользователя, можно использовать их как индекс для эффективного поиска всех имён, начинающихся с буквы «L». Но иногда поиска только по одному атрибуту недостаточно.

Наиболее распространённый тип многоколонного индекса называется конкатенированным индексом (concatenated index). Он просто объединяет несколько полей в один ключ, последовательно добавляя одну колонку к другой (определение индекса задаёт, в каком порядке объединяются поля). Это похоже на старомодную бумажную телефонную книгу, которая обеспечивает индекс по (фамилия, имя) к номеру телефона. Благодаря порядку сортировки индекс можно использовать, чтобы найти всех людей с определённой фамилией или всех людей с определённой комбинацией фамилия–имя. Однако индекс бесполезен, если нужно найти всех людей с определённым именем.

С другой стороны, многомерные индексы позволяют выполнять запросы сразу по нескольким колонкам. Один из наиболее важных случаев применения — геопространственные данные. Например, сайт поиска ресторанов может иметь базу данных с широтой и долготой каждого ресторана. Когда пользователь смотрит рестораны на карте, сайт должен найти все рестораны внутри прямоугольной области карты, которую пользователь в данный момент просматривает. Для этого нужен двумерный диапазонный запрос, например:

SELECT * 
FROM restaurants
WHERE latitude  > 51.4946 
AND latitude  < 51.5079
AND longitude > -0.1162 
AND longitude < -0.1004;

SELECT *

FROM restaurants

WHERE latitude > 51.4946

AND latitude < 51.5079

AND longitude > -0.1162

AND longitude < -0.1004;

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

Один из вариантов — преобразовать двумерное местоположение в одно число с помощью заполняющей пространство кривой (space-filling curve), а затем использовать обычный индекс B-дерева. Чаще применяются специализированные пространственные индексы, такие как R-деревья или Bkd-деревья; они делят пространство так, что близкие точки данных группируются в одном поддереве. Например, PostGIS реализует геопространственные индексы как R-деревья, используя механизм обобщённых деревьев поиска (Generalized Search Tree) PostgreSQL. Также можно использовать регулярно расположенные сетки из треугольников, квадратов или шестиугольников.

Многомерные индексы применяются не только для географических координат. Например, на сайте электронной коммерции можно использовать трёхмерный индекс по измерениям (red, green, blue), чтобы искать товары в определённом диапазоне цветов. Или в базе данных метеорологических наблюдений можно иметь двумерный индекс по (дата, температура), чтобы эффективно находить все наблюдения за 2013 год, когда температура была между 25 и 30 ℃. С одномерным индексом пришлось бы либо просматривать все записи за 2013 год (независимо от температуры) и затем фильтровать их по температуре, либо наоборот. 2D-индекс может сузить поиск сразу и по дате, и по температуре.

Полнотекстовый поиск

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

Тем не менее, в своей основе, полнотекстовый поиск можно рассматривать как еще один вид многомерного запроса: в данном случае каждое слово, которое может встретиться в тексте (термин), является измерением. Документ, содержащий термин x, имеет значение 1 в измерении x, а документ, не содержащий x, имеет значение 0. Поиск документов, упоминающих “red apples” (“красные яблоки”), означает запрос, который ищет 1 в измерении red и одновременно 1 в измерении apples. Таким образом, количество измерений может быть очень большим.

Структура данных, которую многие поисковые системы используют для ответа на такие запросы, называется инвертированным индексом. Это структура «ключ-значение», где ключ — это термин, а значение — список идентификаторов всех документов, содержащих данный термин (список вхождений). Если идентификаторы документов являются последовательными числами, список вхождений также может быть представлен как разреженное битовое поле, как на рисунке 4-8: n-й бит в битовом поле для термина x равен 1, если документ с идентификатором n содержит термин x.

Поиск всех документов, содержащих оба термина x и y, теперь аналогичен векторизованному запросу в хранилище данных, который ищет строки, удовлетворяющие двум условиям (рисунок 4-9): загружаются два битовых поля для терминов x и y и вычисляется их побитовое И. Даже если битовые поля закодированы методом run-length, это можно сделать очень эффективно.

Например, Lucene, механизм полнотекстового индексирования, используемый в Elasticsearch и Solr, работает именно так. Он хранит отображение от термина к списку вхождений в отсортированных файлах наподобие SSTable, которые объединяются в фоне, используя тот же подход с журналируемой структурой, который мы рассматривали ранее в этой главе. Тип индекса GIN в PostgreSQL также использует списки вхождений для поддержки полнотекстового поиска и индексирования внутри JSON-документов.

Вместо разбиения текста на слова, альтернативой является нахождение всех подстрок длиной n, которые называются n-граммами. Например, триграммы (n = 3) строки «hello» это «hel», «ell» и «llo». Если построить инвертированный индекс всех триграмм, можно искать документы по произвольным подстрокам длиной как минимум три символа. Триграммные индексы даже позволяют использовать регулярные выражения в поисковых запросах; минус в том, что они получаются довольно большими.

Чтобы справляться с опечатками в документах или запросах, Lucene может искать слова в пределах определенного расстояния редактирования (расстояние редактирования 1 означает, что одна буква была добавлена, удалена или заменена). Он делает это, сохраняя множество терминов как конечный автомат по символам в ключах, аналогичный префиксному дереву (trie), и преобразуя его в автомат Левенштейна, который поддерживает эффективный поиск слов в пределах заданного расстояния редактирования.

Векторные представления (Vector Embeddings)

Семантический поиск выходит за пределы синонимов и опечаток, пытаясь понять концепции документа и намерения пользователя. Например, если на ваших страницах помощи есть страница с заголовком “cancelling your subscription” (“отмена подписки”), пользователи должны иметь возможность найти эту страницу по запросам “how to close my account” (“как закрыть мой аккаунт”) или “terminate contract” (“расторгнуть контракт”), которые близки по смыслу, даже если используют совершенно разные слова.

Чтобы понять семантику документа — его значение — индексы семантического поиска используют модели встраивания (embedding models), которые переводят документ в вектор вещественных значений с плавающей точкой, называемый векторным представлением (vector embedding). Вектор представляет точку в многомерном пространстве, и каждое вещественное значение представляет положение документа вдоль оси одного измерения. Модели встраивания генерируют векторы, которые располагаются близко друг к другу (в этом многомерном пространстве), если входные документы семантически похожи.

Примечание

Мы уже встречали термин векторизованная обработка в разделе “Query Execution: Compilation and Vectorization”. Векторы в семантическом поиске имеют другое значение. В векторизованной обработке вектор относится к пакету битов, который можно обработать с помощью специально оптимизированного кода. В моделях встраивания векторы — это список чисел с плавающей точкой, представляющих местоположение в многомерном пространстве.

Например, трехмерное векторное представление для страницы Википедии об аграрном хозяйстве может быть [0.1, 0.22, 0.11]. Страница Википедии об овощах будет находиться довольно близко, возможно с представлением [0.13, 0.19, 0.24]. Страница о звездных схемах может иметь представление [0.82, 0.39, -0.74], находясь сравнительно далеко. Мы можем видеть, что первые два вектора ближе друг к другу, чем третий.

Модели встраивания используют гораздо более длинные векторы (часто более 1000 чисел), но принципы остаются теми же. Мы не пытаемся понять, что означают отдельные числа; они просто способ для моделей указывать положение в абстрактном многомерном пространстве. Поисковые системы используют функции расстояния, такие как косинусное сходство или евклидово расстояние, чтобы измерять расстояние между векторами. Косинусное сходство измеряет косинус угла между двумя векторами, чтобы определить, насколько они близки, тогда как евклидово расстояние измеряет прямое расстояние между двумя точками в пространстве.

Многие ранние модели встраивания, такие как Word2Vec, BERT и GPT, работали с текстовыми данными. Такие модели обычно реализуются как нейронные сети. Исследователи затем создали модели встраивания для видео, аудио и изображений. Более недавно архитектура моделей стала мультимодальной: одна модель может генерировать векторы для нескольких типов данных, например текста и изображений.

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

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

Плоские индексы (Flat indexes)
Векторы сохраняются в индексе как есть. Запрос должен прочитать каждый вектор и измерить его расстояние до вектора запроса. Плоские индексы точны, но измерение расстояния между запросом и каждым вектором медленно.

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

Иерархический навигируемый малый мир (HNSW)
HNSW-индексы поддерживают несколько уровней векторного пространства, как показано на Рисунке 4-11. Каждый уровень представлен в виде графа, где узлы представляют векторы, а рёбра — близость к соседним векторам. Запрос начинается с поиска ближайшего вектора на самом верхнем уровне, где узлов немного. Затем запрос перемещается к тому же узлу на нижнем уровне и следует по рёбрам этого уровня, который связан плотнее, в поисках вектора, который ближе к запросу. Процесс продолжается до тех пор, пока не будет достигнут последний уровень. Как и IVF-индексы, HNSW-индексы являются приближенными.

Рисунок 4-11. Поиск записи в базе данных, которая ближе всего к заданному вектору-запросу в HNSW-индексе

Многие популярные векторные базы данных реализуют IVF- и HNSW-индексы. Библиотека Faiss от Facebook имеет множество вариаций каждого, а PostgreSQL pgvector также поддерживает оба. Полные детали алгоритмов IVF и HNSW выходят за рамки этой книги, но их статьи являются отличным источником.

Резюме

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

Раздел «Аналитические и операционные системы» ввёл различие между обработкой транзакций (OLTP) и аналитикой (OLAP). В этой главе мы увидели, что движки хранения, оптимизированные для OLTP, сильно отличаются от оптимизированных для аналитики:

OLTP-системы оптимизированы для большого числа запросов, каждый из которых читает и записывает небольшое количество записей и требует быстрых ответов. Записи обычно обращаются по первичному ключу или вторичному индексу, и эти индексы, как правило, являются упорядоченными отображениями от ключа к записи, которые также поддерживают диапазонные запросы.
Хранилища данных и подобные аналитические системы оптимизированы для сложных запросов на чтение, которые сканируют большое количество записей. Обычно они используют колонко-ориентированную схему хранения с сжатием, минимизирующим количество данных, которые нужно прочитать с диска, а также just-in-time компиляцию запросов или векторизацию, чтобы минимизировать затраты процессорного времени на обработку данных.

С OLTP-стороны мы рассмотрели движки хранения из двух основных школ мысли:

Журнально-структурированный подход, который позволяет только добавлять данные в файлы и удалять устаревшие файлы, но никогда не обновляет уже записанный файл. К этой группе относятся SSTables, LSM-деревья, RocksDB, Cassandra, HBase, Scylla, Lucene и другие. В целом, журнально-структурированные движки хранения, как правило, обеспечивают высокую пропускную способность на запись.
Подход с обновлением на месте, который рассматривает диск как набор фиксированных по размеру страниц, которые можно перезаписывать. B-деревья, крупнейший пример этой философии, используются во всех основных реляционных OLTP-базах данных, а также во многих нереляционных. Как правило, B-деревья лучше подходят для чтения, обеспечивая более высокую пропускную способность на чтение и меньшее время отклика, чем журнально-структурированное хранение.

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

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

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

Глава 4. Хранение и извлечение

Глава 4. Хранение и извлечение данных

Хранение и индексация для OLTP

Лог-структурированное хранение

Формат файла SSTable

Построение и слияние SSTable

Фильтры Блума

Стратегии уплотнения (Compaction strategies)

Встроенные движки хранения

B-деревья

Надёжность B-деревьев

Варианты B-деревьев

Сравнение B-деревьев и LSM-деревьев

Производительность чтения

Последовательные и случайные записи

Усиление записи (Write amplification)

Использование дискового пространства (Disk space usage)

Множественные и вторичные индексы (Multi-Column and Secondary Indexes)

Хранение значений внутри индекса (Storing values within the index)

Хранение всего в памяти (Keeping everything in memory)

Хранение данных для аналитики (Data Storage for Analytics)

Облачные хранилища данных (Cloud Data Warehouses)

Хранение, ориентированное на колонки (Column-Oriented Storage)

Сжатие колонок (Column Compression)

Порядок сортировки в колоночном хранении (Sort Order in Column Storage)

Запись в колоночное хранилище (Writing to Column-Oriented Storage)

Выполнение запросов: компиляция и векторизация (Query Execution: Compilation and Vectorization)

Материализованные представления и кубы данных (Materialized Views and Data Cubes)

Многомерные и полнотекстовые индексы (Multidimensional and Full-Text Indexes)

Полнотекстовый поиск

Векторные представления (Vector Embeddings)

Резюме

Python — Многозадачность, конкурентность и асинхронность

PySpark Interview — Вопросы и ответы

Системный дизайн. Интервью по System Design

Apache Kafka Tutorial 101: Архитектура, Consumer, Producer, Topic