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 состоит из двух частей:
- Базовый узел (base node) — неизменяемая копия полного набора пар ключ-значение.
- Цепочка дельта-записей (delta chain) — последовательность записей, каждая из которых содержит тип операции (вставка, удаление, разделение, слияние) и данные изменения. Цепочка строится от последнего изменения к началу: новая дельта добавляется в начало.
¶Процесс работы
При выполнении операций вставки или удаления потоки конкурируют не за изменение узла, а за добавление новой дельта-записи в начало цепочки. Операция CAS применяется к указателю на голову цепочки, что позволяет выполнять изменения без взаимной блокировки. Если CAS обнаруживает, что цепочка уже была изменена другим потоком, поток повторяет попытку с новым указателем.
Разделение (split) или слияние (merge) узлов, характерные для B-tree, также реализуются с помощью дельта-записей, но без блокировок. Например, при разделении создаётся новый узел, содержащий половину ключей, а в родительский узел добавляется дельта, отражающая это изменение.
¶Преимущества и недостатки
Преимущества Bw-tree:
- Высокая конкурентность. Отсутствие блокировок и минимальное использование атомарных операций позволяют эффективно работать на многопоточной системе с сотнями ядер.
- Кэш-эффективность. Частая запись дельт (очень маленьких по размеру) снижает давление на кэш. Базовые узлы консолидируются реже, что уменьшает количество кэш-промахов.
- Адаптация к флэш-памяти. Операции замены узлов на месте традиционно требуют перезаписи больших блоков, что снижает производительность SSD. Bw-tree уменьшает количество таких операций за счёт фонового слияния и неизменяемости основных узлов.
- Низкое соперничество (contention). Потоки конкурируют только за атомарный указатель, а не за содержимое узла.
Недостатки и ограничения:
- Сложность реализации. Управление цепочкой дельт, периодическая консолидация и поддержание ссылочной целостности требуют тщательного проектирования. Ошибки могут привести к утечкам памяти или неверным результатам поиска.
- Дополнительные накладные расходы. Хранение дельта-записей и фоновое слияние потребляют оперативную память и процессорное время. В некоторых сценариях Bw-tree может быть менее эффективна, чем традиционное B-дерево с блокировками.
- Зависимость от аппаратного обеспечения. Методы CAS и неделимых операций могут различаться на разных платформах; эффективность Bw-tree сильно зависит от архитектуры процессора.
¶Сравнение с другими структурами
| Характеристика | Bw-tree | B-tree | LSM-дерево |
|---|---|---|---|
| Конкурентность | Высокая (без блокировок) | Средняя (блокировки) | Высокая (компактизация) |
| Скорость вставки (в среднем) | Высокая | Умеренная | Высокая |
| Скорость поиска (в среднем) | Высокая | Высокая | Умеренная (много уровней) |
| Управление памятью | Разделение на дельты и базовые узлы | Прямое изменение | Компактизация и слияние |
| Адаптация к SSD | Да | Частично | Да |
¶Применение
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.