Bw-tree

Bw-tree — это структура данных, относящаяся к классу сбалансированных деревьев поиска, разработанная для работы в многопоточных средах и оптимизированная для использования в современных кэш-иерархиях процессоров. В отличие от традиционных деревьев (например, B-tree), Bw-tree не изменяет узлы на месте, а использует технику обновлений на основе дельта-записей (delta records) и принципы копирования при записи (copy-on-write), что обеспечивает высокую конкурентность и производительность при низких накладных расходах на синхронизацию.

История

Bw-tree была впервые предложена в 2011 году исследователями из Microsoft Research Джастином Левинсоном, Дэвидом Лометом и другими. Разработка была направлена на создание индексной структуры, эффективно работающей на многоядерных процессорах с неоднородным доступом к памяти (NUMA) и системами флэш-памяти (SSD). Первое описание было опубликовано в работе «The Bw-Tree: A B-tree for New Hardware Platforms» в 2013 году. В отличие от многих предшествующих структур, Bw-tree не требует блокировок и не использует латч (lock), что уменьшает конкуренцию между потоками.

Технические предпосылки. В 2010-х годах рост числа ядер в процессорах и распространение SSD с быстрым последовательным доступом, но ограниченными операциями записи, потребовали пересмотра традиционных подходов к индексации. Bw-tree стала одной из первых реализаций, адаптированных к этим условиям.

Принцип работы и архитектура

Bw-tree представляет собой дерево, состоящее из узлов, которые хранят пары ключ-значение. Основные принципы, отличающие её от B-tree, включают:

• Отсутствие структурных модификаций на месте (no in-place updates). Вместо изменения содержимого узла создаётся новый физический узел, содержащий дельта-запись (delta record), которая описывает изменение (вставку, удаление, перемещение). Это позволяет избежать блокировок при записи.
• Дельта-обновления. Каждый узел является неизменяемым (immutable) после создания. Изменения применяются путём добавления цепочек дельта-записей — небольших записей, содержащих только разницу с предыдущей версией. При накоплении достаточного количества дельт или при обходе дерева выполняется слияние (применение) этих записей в один новый полный узел.
• Логарифмическое слияние (log-structured merge). Bw-tree использует стратегию фоновой консолидации для поддержания сбалансированности. Периодически (или по требованию) дельта-записи применяются и узлы перестраиваются, что напоминает работу LSM-деревьев, но с сохранением «формы» B-дерева.
• Атомарные обновления с помощью CAS (Compare-and-Swap). Для указателей на корневые узлы и на цепочки дельт используются атомарные операции, предоставляемые процессорами, что исключает необходимость в блокировках.

Структура узлов

Каждый физический узел Bw-tree состоит из двух частей:

1. Базовый узел (base node) — неизменяемая копия полного набора пар ключ-значение.
2. Цепочка дельта-записей (delta chain) — последовательность записей, каждая из которых содержит тип операции (вставка, удаление, разделение, слияние) и данные изменения. Цепочка строится от последнего изменения к началу: новая дельта добавляется в начало.

Процесс работы

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

Разделение (split) или слияние (merge) узлов, характерные для B-tree, также реализуются с помощью дельта-записей, но без блокировок. Например, при разделении создаётся новый узел, содержащий половину ключей, а в родительский узел добавляется дельта, отражающая это изменение.

Преимущества и недостатки

Преимущества Bw-tree:

• Высокая конкурентность. Отсутствие блокировок и минимальное использование атомарных операций позволяют эффективно работать на многопоточной системе с сотнями ядер.
• Кэш-эффективность. Частая запись дельт (очень маленьких по размеру) снижает давление на кэш. Базовые узлы консолидируются реже, что уменьшает количество кэш-промахов.
• Адаптация к флэш-памяти. Операции замены узлов на месте традиционно требуют перезаписи больших блоков, что снижает производительность SSD. Bw-tree уменьшает количество таких операций за счёт фонового слияния и неизменяемости основных узлов.
• Низкое соперничество (contention). Потоки конкурируют только за атомарный указатель, а не за содержимое узла.

Недостатки и ограничения:

• Сложность реализации. Управление цепочкой дельт, периодическая консолидация и поддержание ссылочной целостности требуют тщательного проектирования. Ошибки могут привести к утечкам памяти или неверным результатам поиска.
• Дополнительные накладные расходы. Хранение дельта-записей и фоновое слияние потребляют оперативную память и процессорное время. В некоторых сценариях Bw-tree может быть менее эффективна, чем традиционное B-дерево с блокировками.
• Зависимость от аппаратного обеспечения. Методы CAS и неделимых операций могут различаться на разных платформах; эффективность Bw-tree сильно зависит от архитектуры процессора.

Сравнение с другими структурами

Применение

Bw-tree нашла применение в системах управления базами данных (СУБД) и других компонентах, где требуется высокая производительность индексирования в многопоточных средах:

• Система LLAMA (2013) — гибридный слой хранения, реализованный на основе Bw-tree и предназначенный для работы с энергонезависимой памятью. Лежит в основе многих современных research-проектов.
• Проект OpenBw-tree (2016) — открытая реализация на языке C++, используется в академических исследованиях и для тестирования производительности.
• Встраивание в коммерческие СУБД. Некоторые современные решения, ориентированные на in-memory обработку (например, SAP HANA в определённых версиях), используют элементы архитектуры, напоминающие Bw-tree, для индексации.
• Использование в системах баз данных для IoT и реального времени — где ценятся низкие задержки и многопоточность.

Интересные факты

• Название расшифровывается как «Blink-tree with write-optimization» или «B-tree with delta records», но в оригинальной работе использовался акроним от «B-tree without locks» или «B-tree for white box».
• В Bw-tree не существует отдельной операции закрепления (latch) при чтении — для поиска достаточно атомарно получить указатель на корень, а затем пройти по цепочке, используя локальную копию. Это упрощает алгоритмы и повышает производительность.
• Несмотря на название, Bw-tree не является B-деревом в классическом понимании, так как внутренние узлы могут содержать неполные дельта-записи, а физическая структура напоминает гибрид между B-деревом и LSM-деревом.

Критика

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

Источники

• Levinson, J., Lomet, D., et al. «The Bw-Tree: A B-tree for New Hardware Platforms», Microsoft Research, 2013.
• Lomet, D., et al. «LLAMA: A Cache/Storage Subsystem for Modern Hardware», 2013.
• «OpenBw-tree: A multi-versioned Bw-tree implementation», GitHub, 2016.
• «Bw-tree: A Design for High-Performance Indexing on Modern Hardware», технический доклад, 2012.
• «Comparison of B-trees and LSM-trees for In-Memory Databases», ACM, 2014.