Несмотря на то, что реализации B-деревьев, как правило, более «зрелые», чем реализации LSM-деревьев, LSM-деревья также интересны своими характеристиками производительности. LSM-деревья, как правило, быстрее работают с операцией записи, в то время как B-деревья считаются более быстрыми для чтения. Чтение, как правило, медленнее на LSM-деревьях, потому что им приходится проверять несколько различных структур данных и SSTables на разных стадиях уплотнения.

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

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

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

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

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

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

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

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

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

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

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

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

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

Также очень часто встречаются вторичные индексы. В реляционных базах данных вы можете создать несколько вторичных индексов в одной таблице с помощью команды CREATE INDEX, и они часто имеют решающее значение для эффективного выполнения объединения. Например, на рисунке 2-1 главы 2, скорее всего, будет нужен вторичный индекс в столбцах user_id, чтобы вы могли найти все строки, принадлежащие одному и тому же пользователю, в каждой из таблиц. Вторичный индекс можно легко построить из индекса «ключ-значение». Основное отличие заключается в том, что во вторичном индексе индексируемые значения не обязательно уникальны; то есть под одной и той же записью индекса может быть много строк (документов, вершин). Этого можно избежать двумя способами: либо сделав каждое значение в индексе списком совпадающих идентификаторов строк (например, список сообщений в полнотекстовом индексе), либо сделав каждую запись уникальной, добавив к ней идентификатор строки. В любом случае, как B-деревья, так и лог-структурированные индексы могут использоваться в качестве вторичных индексов.

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

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

В некоторых ситуациях дополнительный переход от индекса к файлу кучи является слишком большой платой за производительность при чтении, поэтому возможно лучше будет хранить индексированную строку непосредственно в индексе. Это называется кластеризованный индекс (clustered index). Например, в подсистеме хранения InnoDB MySQL первичным ключом таблицы всегда является кластеризованный индекс, а вторичные индексы ссылаются на первичный ключ (а не на местоположение файла кучи). В SQL Server вы можете указать один кластеризованный индекс для каждой таблицы.

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

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

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

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

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

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

Одним из вариантов является преобразование двумерного местоположения в одно число с помощью кривой заполнения пространства, а затем использование обычного индекса B-дерева. Чаще всего используются специализированные пространственные индексы, такие как R-деревья. Например, PostGIS реализует геопространственные индексы в виде R-деревьев, используя средство индексирования PostgreSQL Generalized Search Tree. У нас нет времени, чтобы подробно описать R-деревья, но литературы по ним достаточно.

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

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

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

Как упоминалось в разделе «Создание LSM-дерева из SSTables», Lucene использует структуру, похожую на SSTable, для своего словаря терминов. Эта структура требует небольшого резидентного индекса, который сообщает запросам, при каком смещении в отсортированном файле им нужно искать ключ. В LevelDB этот резидентный индекс представляет собой разреженную коллекцию некоторых ключей, но в Lucene резидентный индекс — это конечный автомат над символами в ключах, похожий на префиксное дерево. Этот автомат может быть преобразован в автомат Левенштейна, который поддерживает эффективный поиск слов в пределах заданного редакционного расстояния.

Другие методы нечеткого поиска идут в направлении классификации документов и машинного обучения. См. учебники по поиску информации для получения более подробной информации.

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

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

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

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

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

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

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

Недавние исследования показывают, что архитектура резидентных баз данных может быть расширена, чтобы обрабатывать наборы данных, превышающих объем доступной памяти, без возвращения к излишествам архитектуры, ориентированной на диск. Так называемый подход анти-кэширования (anti-caching) работает за счет вытеснения последних использованных данных из памяти на диск, когда памяти недостаточно, и загрузки их обратно в память при повторном обращении к ним в будущем. Это похоже на то, что операционные системы делают с виртуальной памятью и файлами подкачки, но база данных может управлять памятью более эффективно, чем ОС, поскольку она может работать на уровне отдельных записей, а не целых страниц памяти. Однако такой подход все равно требует, чтобы индексы полностью помещались в памяти (как в примере Bitcask в начале главы).

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