Персистентные структуры

Отмена в текстовом редакторе, история коммитов в git, снимок базы данных, с которым работает долгий отчёт, пока в базу пишут новое, — везде нужна не одна текущая версия данных, а все сразу. Копировать данные целиком на каждое изменение дорого: архив погоды Алматы — 31 046 дней, и если каждый новый день — новая версия, копии заняли бы почти полмиллиарда чисел. Персистентная структура хранит все версии и тратит на каждое изменение несколько новых узлов. Ниже — дерево сумм над восемью днями июльских дождей. Поправьте любой день.

Каждая поправка добавила четыре узла — путь от корня к поправленному дню — и ни одного узла не изменила. Остальные узлы новая версия берёт у старой: их цвет показывает, какая версия их создала. Выберите старую версию — она видна целиком и такой, какой была. Восемь версий дерева из пятнадцати узлов заняли бы копиями 120 узлов, а здесь их 43; на длинных массивах разница — в тысячи раз.

Идея

Узлы никогда не меняются после создания. Чтобы изменить элемент, новая версия создаёт копии узлов на пути от корня к нему, с новыми значениями, а у каждой копии одна ссылка ведёт в новую копию ниже, другая — в нетронутый узел прежней версии. Версия — это её корень: всё, до чего от него можно дойти, и есть её содержимое. Приём называют копированием пути.

Для массива из 31 046 дней дерево отрезков имеет высоту 15, и каждая версия обходится в 16 узлов вместо 62 тысяч.

Какой бывает персистентность

• Частичная. Читать можно любую версию, менять — только последнюю. Версии выстраиваются в линию: история правок, архив, журнал.
• Полная. Менять можно и старую версию — получится новая ветка. Версии образуют дерево, как ветки в git. Копирование пути даёт полную персистентность даром: изменение любой версии — это копия пути от её корня.
• Слияние версий. Две версии объединяются в одну, как слияние веток. Для деревьев по неявному ключу это склейка двух деревьев — так работает декартово дерево с копированием пути.

Копирование пути — не единственный способ. Джеймс Дрисколл, Нил Сарнак, Дэниел Слитор и Роберт Тарьян в 1986 году описали «толстые узлы», которые хранят историю своих полей с отметками версий, и копирование узлов, которое сочетает оба подхода. Для связных структур с небольшим числом входящих ссылок оно делает частично персистентной почти любую структуру за O(1) дополнительной памяти на изменение в амортизированном смысле.

Медиана любого периода

Самое неожиданное применение — версии, которые никто не правил. Построим дерево отрезков не по дням, а по значениям температуры: лист — одна температура, узел — сколько дней попало в его диапазон температур. Будем добавлять дни по порядку, и версия i будет знать первые i дней.

Значит, у любого периода есть своё «виртуальное» дерево — разность двух версий, — и по нему можно спускаться как по обычному: k-я по возрастанию температура периода лежит в левом ребёнке, если там не меньше k дней, иначе — в правом, и k уменьшается на число дней слева. Медиана — k, равное половине длины. Выберите любой период.

Гистограмма периода — тоже разность версий: каждый столбик спрашивает число дней в своём диапазоне температур у двух версий. А спуск за медианой проходит девять уровней дерева: в архиве 505 разных температур. Тот же спуск работает и для нескольких периодов сразу — например, для всех летних месяцев десятилетия: на каждом уровне складываются разности по всем парам версий.

Где легко ошибиться

• Изменить общий узел. Главное правило — узел после создания не меняется. Если в коде изменения есть строка вида node.sum += x по узлу, который мог достаться от старой версии, старая версия тоже изменится, и ошибка проявится нескоро и далеко от места. Безопаснее всего, когда менять узел просто нечем: поля задаются один раз при создании.
• Отложенные операции. В обычном дереве отрезков прибавление к отрезку откладывают в узле и проталкивают в детей при спуске. В персистентном проталкивание меняет детей — общие узлы. Поэтому при проталкивании детей копируют, или отложенную добавку не проталкивают вовсе, а суммируют по пути спуска: она навсегда остаётся в узле, где её записали.
• Память, которую никто не освобождает. Если старые версии больше не нужны, их узлы надо уметь выбросить, а узел может принадлежать сразу многим версиям. В языках со сборщиком мусора это делает он: недостижимые из живых корней узлы исчезнут сами. Без сборщика нужны счётчики ссылок или арена, которую выбрасывают целиком.
• Сжатие значений. Дерево по значениям строят по номерам значений, а не по самим значениям: 505 разных температур дают девять уровней, а диапазон в миллиард — тридцать.

Код

Листинг строит по архиву все 31 047 версий дерева значений, считает узлы и находит медиану дня по десятилетиям — за всё десятилетие и только по летним месяцам, через пары версий для каждого лета. Каждую медиану он сверяет с сортировкой.

31046 days, 505 different temperatures, a tree of values with 9 levels
versions 31047, nodes 309982: 10 new per version (a whole copy would be 1009)
years         median day   median summer day
1941-1950          +10.8               +22.5
1951-1960           +8.2               +19.6
1961-1970           +8.5               +19.8
1971-1980           +9.1               +19.9
1981-1990           +8.2               +20.2
1991-2000           +8.7               +19.9
2001-2010           +9.5               +20.1
2011-2020          +10.6               +21.4
2021-2025          +11.7               +24.3

Все версии заняли 310 тысяч узлов. Копия на каждую версию — 31 миллион. Медиана летнего дня за 2021–2025 годы на 4,4° выше, чем за 1991–2000. К сороковым стоит относиться осторожнее: реанализ первых десятилетий опирается на гораздо меньшее число наблюдений и надёжен меньше.

Сколько это стоит

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

Где работает

• git. Коммит хранит дерево каталогов, а каталог ссылается на файлы и подкаталоги по их хешам. Если подкаталог не менялся, новое дерево ссылается на тот же объект, что и старое: коммит создаёт новые объекты только на пути от корня к изменённым файлам. Это копирование пути, где ссылками служат хеши, как в дереве Меркла.
• Функциональные языки. В Clojure векторы и словари неизменяемые: изменение возвращает новую версию, которая делит со старой всё, кроме пути. Деревья там широкие, по 32 ребёнка в узле, поэтому вектор из миллиона элементов — четыре уровня, и изменение копирует четыре узла. Словари построены на хеш-деревьях Фила Багвелла 2001 года.
• Базы и файловые системы. Копирующие B-деревья пишут изменённые страницы на новое место, а не поверх старых: так устроены LMDB и Btrfs. Читатель, начавший работу, видит свою версию дерева целиком, пока писатель создаёт следующую, — и никто никого не ждёт.
• Геометрия. Нил Сарнак и Роберт Тарьян в 1986 году решили этим задачу о точке на карте: проведём вертикальную прямую через каждую вершину карты, в каждой полосе отрезки упорядочены снизу вверх, и соседние полосы отличаются несколькими отрезками. Персистентное дерево поиска хранит все полосы как версии в линейной памяти, а точку находят двумя двоичными поисками — по полосам и внутри версии.

История

Слово «персистентность» для структур данных и первую систематическую теорию дали Дрисколл, Сарнак, Слитор и Тарьян: доклад 1986 года «Как сделать структуры данных персистентными», журнальная статья вышла в 1989-м. Почти одновременно Сарнак и Тарьян показали, что персистентное дерево решает старую задачу геометрии о точке на карте. Функциональное программирование пришло к тем же структурам с другой стороны: там данные неизменяемы по самому устройству языка, и книга Криса Окасаки «Чисто функциональные структуры данных» 1998 года собрала, как сделать их при этом быстрыми. Персистентное дерево отрезков по значениям — олимпиадный фольклор, знакомый всем, кто решал задачу о k-й статистике на отрезке.

Задачи

В задаче — архив погоды Алматы и десятки тысяч вопросов о k-й по возрастанию температуре периода: медианах месяцев, самых холодных днях лета.