Модель внешней памяти: считаем блоки, а не операции

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

Как думаешь, сколько обращений

В файле на диске миллион чисел, блок - 512 чисел. Двоичный поиск по отсортированному файлу делает 20 сравнений. Сколько блоков он прочитает? А B-дерево с узлом в один блок?

Ответь себе до чтения. «20 блоков - по блоку на сравнение» почти верно: последние сравнения попадают в уже прочитанный блок, и в худшем из наших запросов выходит 12. B-дереву хватит трёх.

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

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

Модель внешней памяти считает именно походы в подвал: что ты делаешь с полкой наверху - бесплатно.

Механизм: M, B и цена в блоках

Параметры модели: N - размер задачи, M - сколько элементов помещается в быструю память, B - сколько элементов в блоке. Обращение к элементу, чьего блока нет в быстрой памяти, - промах: читается весь блок, а если места нет, какой-то блок вытесняется (обычно давно не использовавшийся - правило LRU).

Базовые цены:

• проход по N элементам подряд - N / B обращений: каждый блок читается один раз;
• случайный доступ к N элементам - почти N обращений, если N много больше M: блок почти никогда не оказывается в памяти;
• поиск: двоичный - около log₂(N / B) блоков (пока отрезок длиннее блока, каждое сравнение - новый блок); B-дерево с ветвлением B - ⌈log_B N⌉, по блоку на уровень. Устройство B-дерева разобрано в главе о B-деревьях; здесь важно, почему оно выигрывает: основание логарифма B вместо двух.

Та же модель описывает пару «кеш процессора - оперативная память»: B - строка кеша (64 байта), M - размер кеша. Цены другие - 100 наносекунд вместо 100 микросекунд у SSD и миллисекунд у жёсткого диска, - но принцип тот же.

Правило

В модели внешней памяти цена - число переносов блоков размера B между медленной памятью и быстрой размера M. Проход по N элементам стоит N / B, случайный доступ - около N. Поиск двоичным поиском - около log₂(N / B) блоков, B-деревом - ⌈log_B N⌉. Алгоритм хорош на диске, если трогает элементы в том порядке, в каком они лежат по блокам.

Разбор: три способа прочитать один массив

Модель с LRU-кешем: 1024 элемента, блок 16, быстрая память на 128 элементов - восемь блоков. Делаем по 1024 обращения трижды: подряд, случайно (с повторами: случайный номер каждый раз) и с шагом B - сначала нулевые элементы всех блоков, потом первые и так далее.

import random

def promahi(adresa, B, M):
    # кеш из M // B блоков по B элементов, вытесняется давно не нужный
    kesh = []
    promahov = 0
    for a in adresa:
        blok = a // B
        if blok in kesh:
            kesh.remove(blok)
        else:
            promahov = promahov + 1
            if len(kesh) == M // B:
                kesh.pop(0)
        kesh.append(blok)
    return promahov

N = 1024
B = 16
M = 128
podryad = list(range(N))
random.seed(1)
sluchajno = []
for k in range(N):
    sluchajno.append(random.randint(0, N - 1))
shagom = []
for start in range(B):
    for a in range(start, N, B):
        shagom.append(a)
print("N =", N, "B =", B, "M =", M, "- нижняя граница N / B =", N // B)
print("подряд:", promahi(podryad, B, M))
print("случайно:", promahi(sluchajno, B, M))
print("с шагом B:", promahi(shagom, B, M))

N = 1024 B = 16 M = 128 - нижняя граница N / B = 64
подряд: 64
случайно: 899
с шагом B: 1024

Подряд - 64 промаха, ровно N / B. Случайно - 899: почти каждое обращение мимо, ведь в памяти восемь блоков из 64. С шагом B - 1024, промах на каждое обращение: элементы те же, что подряд, но каждый следующий из другого блока, и к тому времени, как программа вернётся к блоку за следующим элементом, его уже вытеснили. Число операций во всех трёх случаях одно и то же - разница в шестнадцать раз только из-за порядка.

Разбор: двоичный поиск против B-дерева

Блок - 512 элементов, примерно 4 КБ ключей. Считаем, сколько разных блоков читает двоичный поиск при пустом кеше, и сравниваем с высотой B-дерева с ветвлением 512.

import math

def poisk_dvoichnyj(N, B, x):
    # двоичный поиск в отсортированном массиве на диске: какие блоки он
    # читает при холодном кеше
    lo = 0
    hi = N
    bloki = {}
    while hi - lo > 1:
        mid = (lo + hi) // 2
        bloki[mid // B] = True
        if mid <= x:
            lo = mid
        else:
            hi = mid
    return len(bloki)

B = 512
print("N         двоичный поиск   B-дерево: ceil(log_B N)")
for N in [10 ** 4, 10 ** 6, 10 ** 8]:
    hudshee = 0
    for x in [0, N // 3, N // 2 + 7, N - 1]:
        hudshee = max(hudshee, poisk_dvoichnyj(N, B, x))
    print(N, hudshee, math.ceil(math.log(N) / math.log(B)))

N         двоичный поиск   B-дерево: ceil(log_B N)
10000 5 2
1000000 12 3
100000000 18 3

На миллионе элементов двоичный поиск читает 12 блоков, B-дерево - 3. На ста миллионах - 18 против 3. Двоичный поиск делит пополам, а блок вмещает 512 вариантов: каждое обращение B-дерева сужает поиск в 512 раз, а двоичного - всего в два. Поэтому индексы баз данных - B-деревья, а не отсортированные массивы, хотя сравнений в B-дереве даже больше.

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

Обход по столбцам массива, лежащего по строкам. В C и numpy (по умолчанию) двумерный массив лежит по строкам одним куском, в Java каждая строка - отдельный массив; в обоих случаях соседи по строке соседствуют в памяти, а соседи по столбцу - нет. Цикл «по столбцам снаружи, по строкам внутри» трогает каждый следующий элемент в другой строке кеша - промах на каждое обращение, как «с шагом B» в разборе.

Связный список на миллионы узлов. Узлы разбросаны по памяти, каждый переход - промах. Массив той же длины проходится в десятки раз быстрее, хотя асимптотика обоих - O(n).

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

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

Индексы PostgreSQL и MySQL - B-деревья со страницей 8 и 16 КБ. Столбцовые форматы (Parquet, ClickHouse) хранят столбец подряд именно затем, чтобы запрос по одному столбцу читал его проходом. Обработка логов grep и awk быстра, потому что это проход; та же обработка через базу с индексом по каждой строке - случайный доступ, и она медленнее, хотя «умнее».

Теперь сам

1. N = 10⁹, B = 1000. Сколько блочных обращений стоит проход? А случайное чтение всех элементов?
2. Высота B-дерева с ветвлением 256 на миллиарде ключей?
3. В разборе «с шагом B» дал 1024 промаха. При каком размере быстрой памяти он дал бы столько же, сколько проход подряд?