Внешние структуры: B-дерево, LSM-дерево и цена записи

Если ты знаешь, почему B-дерево дорого на вставках, как устроено LSM-дерево и чем уплотнение по уровням отличается от уплотнения по ярусам, листай до «Теперь сам».

Как думаешь, что дешевле

Сервис пишет метрики: миллион вставок, ключи случайные. Вариант А - B-дерево, верхние уровни в памяти, лист читается и пишется с диска. Вариант Б - LSM-дерево, где каждая запись в итоге переписывается на диске около десяти раз. Какой вариант делает меньше обращений к диску на одну вставку?

Ответ - LSM, примерно в десять раз. Десять перезаписей - это проходы по большим отсортированным прогонам, где блок вмещает сто элементов, а B-дерево платит целым блоком за каждый элемент.

На что это похоже

Бухгалтер с картотекой. Можно вставлять каждый новый документ сразу на своё место в шкафу: подойти, найти ящик, вставить - на каждый документ поход к шкафу. А можно складывать новые документы в лоток на столе, вечером сортировать лоток и вливать его в шкаф одним проходом, раз в неделю сливая недельные стопки в архив. Каждый документ перекладывается несколько раз, но всегда пачками.

Неудобство одно: чтобы найти документ, теперь надо проверить лоток, вечерние стопки и шкаф.

Механизм: прогоны, уровни и ярусы

B-дерево на вставках. Путь от корня к листу - ⌈log_B N⌉ узлов. Верхние уровни помещаются в памяти, но лист и уровни под ним - нет: вставка случайного ключа - чтение блока листа и запись блока, два обращения на элемент.

LSM-дерево. Вставки копятся в памяти (memtable) размером M. Когда она заполнена, её содержимое пишется на диск одним отсортированным прогоном - проход. Прогоны объединяются слиянием в фоне, по правилу уплотнения:

• по уровням (leveled): на уровне i = 1, 2, … один прогон вместимостью M · Tⁱ; пришедшее сливается с ним, а переполненный уровень целиком уходит на следующий. Чтение проверяет по одному прогону на уровне, но элемент переписывается около T раз на каждом уровне;
• по ярусам (tiered, size-tiered): на ярусе копятся прогоны; набралось T - сливаются в один на следующем. Элемент пишется по разу на ярус, но прогонов на ярусе до T, и чтение проверяет все.

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

Правило

B-дерево: поиск log_B N, но вставка случайного ключа - два случайных обращения. LSM-дерево копит вставки в памяти, сбрасывает отсортированными прогонами и сливает их в фоне: элемент переписывается несколько раз, но блоками, и вставка стоит долю обращения. Уплотнение по уровням - мало прогонов, много перезаписей; по ярусам - мало перезаписей, много прогонов. Фильтры Блума избавляют чтение от лишних прогонов.

Разбор: B-дерево против LSM на миллионе вставок

Миллион ключей, блок на 100 элементов, память на 10 000. Для B-дерева считаем обращения на вставку, для LSM - сколько раз переписывается элемент при уплотнении по уровням и сколько это блочных обращений на вставку.

import math

def b_derevo(N, B, M):
    # вставка: путь от корня к листу; верхние уровни в памяти, лист и
    # уровни под ним - чтение блока и запись блока
    vysota = math.ceil(math.log(N) / math.log(B))
    v_pamyati = 0
    uzlov = 1
    while uzlov * B <= M and v_pamyati < vysota:
        v_pamyati = v_pamyati + 1
        uzlov = uzlov * B
    # прочитать уровни вне памяти и записать изменённый лист
    return (vysota - v_pamyati) + 1

def lsm(N, B, M, T):
    # вставки копятся в памяти (M элементов) и сбрасываются прогоном;
    # уровень номер i + 1 вмещает M * T^(i+1), переполненный - в
    # следующий целиком. Считаем, сколько раз пишется элемент.
    urovni = []
    zapisano = 0
    for sbros in range(N // M):
        nesu = M
        i = 0
        while True:
            if i == len(urovni):
                urovni.append(0)
            urovni[i] = urovni[i] + nesu
            zapisano = zapisano + urovni[i]
            if urovni[i] <= M * T ** (i + 1):
                break
            nesu = urovni[i]
            urovni[i] = 0
            i = i + 1
    # слияние читает столько, сколько пишет, кроме самих сбросов
    return [zapisano / N, (2 * zapisano - N) / N / B]

N = 10 ** 6
B = 100
M = 10 ** 4
print("B-дерево: блочных обращений на вставку", b_derevo(N, B, M))
for T in [4, 10]:
    r = lsm(N, B, M, T)
    print("LSM, T =", T, ": элемент пишется", round(r[0], 1), "раза,",
          "обращений на вставку", round(r[1], 3))

B-дерево: блочных обращений на вставку 2
LSM, T = 4 : элемент пишется 8.5 раза, обращений на вставку 0.16
LSM, T = 10 : элемент пишется 10.9 раза, обращений на вставку 0.208

B-дерево - два обращения на вставку: верхние два уровня в памяти, лист читается и пишется. LSM при T = 10 переписывает элемент 10,9 раза - но блоками по сто элементов; вместе с чтениями при слиянии выходит 0,208 обращения на вставку, примерно в десять раз меньше. Причём эти обращения последовательные - диск и SSD делают их в разы быстрее случайных. Поэтому базы для интенсивной записи - RocksDB, Cassandra, ScyllaDB, ClickHouse с MergeTree - построены на прогонах и слиянии.

Разбор: уровни или ярусы

Та же нагрузка, 78 сбросов памяти. Сравниваем две политики уплотнения: сколько раз пишется элемент и сколько прогонов придётся проверять при чтении в конце.

def po_urovnyam(N, M, T):
    # на каждом уровне один прогон; приходящее сливается с ним
    urovni = []
    zapisano = 0
    for sbros in range(N // M):
        nesu = M
        i = 0
        while True:
            if i == len(urovni):
                urovni.append(0)
            urovni[i] = urovni[i] + nesu
            zapisano = zapisano + urovni[i]
            if urovni[i] <= M * T ** (i + 1):
                break
            nesu = urovni[i]
            urovni[i] = 0
            i = i + 1
    progonov = 0
    for u in urovni:
        if u > 0:
            progonov = progonov + 1
    return [round(zapisano / N, 1), progonov]

def po_yarusam(N, M, T):
    # на ярусе копятся прогоны; набралось T - один прогон на следующем
    yarusy = []
    zapisano = 0
    for sbros in range(N // M):
        nesu = M
        i = 0
        while True:
            if i == len(yarusy):
                yarusy.append([])
            yarusy[i].append(nesu)
            zapisano = zapisano + nesu
            if len(yarusy[i]) < T:
                break
            nesu = sum(yarusy[i])
            yarusy[i] = []
            i = i + 1
    progonov = 0
    for y in yarusy:
        progonov = progonov + len(y)
    return [round(zapisano / N, 1), progonov]

N = 780000
M = 10 ** 4
print("T  по уровням: [пишется раз, прогонов]  по ярусам: [то же]")
for T in [4, 10]:
    print(T, po_urovnyam(N, M, T), po_yarusam(N, M, T))

T  по уровням: [пишется раз, прогонов]  по ярусам: [то же]
4 [6.8, 3] [3.6, 6]
10 [9.9, 2] [1.9, 15]

T = 10: по уровням элемент пишется 9,9 раза, а прогонов всего 2 - чтение дешёвое. По ярусам - 1,9 раза, в пять раз меньше записи, но прогонов 15, и без фильтров Блума чтение заглянуло бы в каждый. Это и есть компромисс LSM: нельзя одновременно минимизировать запись, чтение и место на диске. RocksDB по умолчанию уплотняет по уровням с множителем 10, Cassandra исторически - по ярусам: она рассчитана на запись.

Что ломается без этого

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

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

Отставшее уплотнение. Запись идёт быстрее, чем фон успевает сливать: прогонов становится всё больше, чтение замедляется, место на диске растёт. LSM-базы тормозят запись, когда уплотнение не успевает, - иначе они бы задохнулись.

Зачем это в работе

Выбор хранилища под нагрузку - это выбор между этими двумя деревьями. Много чтений и обновлений по ключу - B-дерево (PostgreSQL, MySQL InnoDB). Поток записей, метрики, логи, события - LSM (RocksDB под Kafka Streams и многими базами, Cassandra, ClickHouse). Настройка уплотнения - первое, что крутят, когда LSM-база упирается в диск.

Теперь сам

1. Высота B-дерева - 4, в памяти помещаются два верхних уровня. Сколько обращений стоит вставка случайного ключа?
2. Элемент в LSM переписывается 12 раз, блок вмещает 64 элемента. Сколько записей блоков приходится на вставку, и сколько обращений вместе с чтениями при слиянии?
3. Почему уплотнение по ярусам пишет меньше, чем по уровням?