Персистентные и конкурентные структуры данных

Все предыдущие тринадцать статей трека жили в одном очень удобном мире. В этом мире есть ровно одна копия структуры, ровно один исполнитель, который её трогает, и время течёт последовательно: операция началась, операция закончилась, состояние поменялось. Именно на этих допущениях держатся все привычные оценки — «вставка в хеш-таблицу за O(1)», «поворот в AVL за O(1)», «push в динамический массив амортизированно за O(1)».

Реальность ломает оба допущения, и ломает независимо:

• Ломается единственность состояния. Нужен undo. Нужны снапшоты для бэкапа. Нужно показать пользователю согласованное представление данных, пока другие их правят. Нужно ответить на запрос «а что лежало в этом дереве на момент версии 1734?». Состояние перестаёт быть точкой и становится историей.
• Ломается единственность исполнителя. Двадцать четыре ядра одновременно лезут в одну и ту же таблицу. Мьютекс вокруг неё превращает 24 ядра в одно плюс накладные расходы. Время перестаёт быть линейным порядком и становится частичным.

Удивительно, но эти две проблемы решаются в значительной степени одним и тем же приёмом — и в этом главная идея статьи. Если структура неизменяемая, то старая версия автоматически остаётся валидной (персистентность), и её автоматически безопасно читать без единой блокировки, пока кто-то строит новую (конкурентность). Иммутабельность — это мост между двумя половинами статьи, и я построю его явно.

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

Часть I. Персистентность

Что вообще значит «персистентная структура»

Терминологическая ловушка номер один: в этом контексте «персистентная» не значит «сохраняется на диск». Это чистая структура в памяти. Персистентность здесь — про версии.

Структура называется эфемерной (ephemeral), если операция изменения уничтожает предыдущее состояние: после t.insert(5) старого t больше нет. Обычное дерево, обычный список, обычная хеш-таблица — все эфемерные.

Структура называется персистентной, если старые версии остаются доступными. Классификация из работы Дрисколла, Сарнака, Слейтора и Тарьяна 1986 года («Making Data Structures Persistent» — dl.acm.org/doi/10.1145/28395.28424) различает три уровня:

Отдельно стоит функциональная структура — та, что персистентна «по построению», потому что просто не имеет операций мутации. Все структуры из книги Окасаки («Purely Functional Data Structures», amazon.com) такие.

Наивное решение и почему оно провальное

Самый честный способ сделать что угодно персистентным — копировать структуру целиком на каждое изменение. Это работает и даёт полную персистентность бесплатно. Проблема арифметическая: n вставок в дерево из n элементов стоят Θ(n²) времени и Θ(n²) памяти. Для n = 10⁶ это терабайты. Наивный вариант неприменим, но он задаёт правильный ориентир — нам нужна иллюзия полной копии по цене O(изменённого).

Path copying: главный приём

Ключевое наблюдение про деревья: вставка меняет только узлы на пути от корня к точке вставки. Все остальные поддеревья остаются буквально теми же самыми объектами в памяти. Значит, копировать нужно только путь — O(log n) узлов, — а всё остальное разделить (share) между старой и новой версией.

Каждая версия — это просто свой корень. Держите массив корней — получите доступ к любой версии за O(1), а поиск в версии k — обычный спуск от roots[k].

from dataclasses import dataclass
from typing import Any, Optional

@dataclass(frozen=True)          # frozen=True — узлы неизменяемы, это критично
class Node:
    key: Any
    left: Optional["Node"] = None
    right: Optional["Node"] = None

def insert(node: Optional[Node], key) -> Node:
    """Возвращает НОВЫЙ корень. Старое дерево не тронуто.
    Время O(h), новых узлов O(h), общих узлов O(n - h)."""
    if node is None:
        return Node(key)
    if key < node.key:
        # копируем текущий узел, подменяя только левого ребёнка;
        # node.right переиспользуется как есть — вот оно, разделение
        return Node(node.key, insert(node.left, key), node.right)
    if key > node.key:
        return Node(node.key, node.left, insert(node.right, key))
    return node                  # ключ уже есть — версия не изменилась, возвращаем тот же объект

def contains(node: Optional[Node], key) -> bool:
    while node is not None:
        if key == node.key:
            return True
        node = node.left if key < node.key else node.right
    return False

# История версий
versions = [None]
for k in [50, 30, 70, 20, 40, 60, 80]:
    versions.append(insert(versions[-1], k))

v_old = versions[4]              # дерево из 3 элементов
v_new = insert(versions[-1], 65)
assert contains(v_new, 65) and not contains(versions[-1], 65)   # старая версия цела

Стоимость. Одно обновление: O(log n) времени, O(log n) новой памяти при условии, что дерево сбалансировано. m обновлений: O(m log n) суммарной памяти вместо O(m·n) у наивного копирования. Для m = n = 10⁶ это разница между ~20 МБ узлов и ~10¹² узлов.

Балансировка обязательна. Наивное персистентное BST деградирует так же, как эфемерное: на отсортированной вставке путь становится длиной n, и каждая версия копирует n узлов — мы вернулись к Θ(n²). Поэтому персистентность практически всегда строят поверх структуры с гарантированной высотой. Здесь есть тонкость: AVL и красно-чёрные деревья с их поворотами прекрасно совместимы с path copying (поворот трогает O(1) узлов на пути, который мы и так копируем), а вот структуры с амортизированными оценками ломаются.

Splay-дерево нельзя сделать персистентным «просто так». Его O(log n) — амортизированная оценка, которая опирается на то, что дорогая операция «оплачивается» накопленным потенциалом. Персистентность позволяет многократно повторить одну и ту же дорогую операцию над одной и той же версией, каждый раз заново тратя потенциал, который был накоплен единожды. Амортизационный анализ рушится. То же касается амортизированного удвоения в динамическом массиве. Подробнее про механику потенциала — в статье про асимптотику и амортизацию.

Fat nodes и node copying: как получить O(1) накладных расходов

Path copying концептуально прост, но платит O(log n) памяти за каждое изменение поля. DSST предложили два более тонких метода.

Fat nodes. Узел не копируется — вместо этого в нём хранится список версионированных значений каждого поля: left = [(v1 → A), (v7 → B), (v12 → C)]. Обновление — O(1) памяти (добавили запись). Чтение поля в версии k — бинарный поиск по списку, O(log m), где m — число изменений. Итог: идеальная память, но лишний логарифм на каждый шаг спуска, что на практике убийственно.

Node copying (метод DSST). Гибрид: в каждом узле резервируется e дополнительных слотов под версионированные изменения. Пока слоты есть — пишем в них за O(1). Когда слоты кончились — копируем узел целиком и рекурсивно обновляем указатель у родителя (что может вызвать каскад). Амортизационный анализ показывает: при e ≥ p (где p — число указателей на узел) получается O(1) амортизированной памяти и O(1) замедления чтения для частичной персистентности. Это теоретический оптимум, но константы и сложность реализации таковы, что в прикладном коде почти всегда выигрывает честный path copying.

Персистентное дерево отрезков: убийственное приложение

Самое красивое практическое применение path copying — не undo, а запросы к истории. Классическая задача: дан массив, отвечать на запросы «k-я порядковая статистика на отрезке [l, r]» без изменений массива.

Идея: строим n + 1 версий дерева отрезков над пространством значений. Версия i содержит счётчики всех элементов a[0..i-1]. Тогда «сколько элементов из a[l..r] попадает в диапазон значений X» = версия[r+1](X) − версия[l](X) — деревья вычитаются поузельно, потому что они над одним и тем же разбиением. Спускаясь по двум корням одновременно, находим k-ю статистику за один проход.

import bisect

class PNode:
    __slots__ = ("cnt", "left", "right")
    def __init__(self, cnt=0, left=None, right=None):
        self.cnt, self.left, self.right = cnt, left, right

EMPTY = PNode()
EMPTY.left = EMPTY.right = EMPTY          # «пустое» дерево замыкается само на себя

def add(node, lo, hi, pos):
    """Персистентное +1 в позицию pos. O(log n) времени и НОВОЙ памяти."""
    if lo == hi:
        return PNode(node.cnt + 1)
    mid = (lo + hi) // 2
    if pos <= mid:
        return PNode(node.cnt + 1, add(node.left, lo, mid, pos), node.right)
    return PNode(node.cnt + 1, node.left, add(node.right, mid + 1, hi, pos))

def kth(u, v, lo, hi, k):
    """k-я по величине (1-индексация) среди элементов, попавших между версиями u и v."""
    if lo == hi:
        return lo
    mid = (lo + hi) // 2
    left_cnt = v.left.cnt - u.left.cnt    # вычитание версий — вся магия здесь
    if k <= left_cnt:
        return kth(u.left, v.left, lo, mid, k)
    return kth(u.right, v.right, mid + 1, hi, k - left_cnt)

def build(a):
    vals = sorted(set(a))                 # сжатие координат
    roots = [EMPTY]
    for x in a:
        roots.append(add(roots[-1], 0, len(vals) - 1, bisect.bisect_left(vals, x)))
    return roots, vals

def query_kth(roots, vals, l, r, k):      # k-я минимальная на a[l..r] включительно
    return vals[kth(roots[l], roots[r + 1], 0, len(vals) - 1, k)]

a = [7, 2, 9, 4, 5, 1, 8]
roots, vals = build(a)
assert query_kth(roots, vals, 1, 4, 2) == 4      # a[1..4] = [2,9,4,5] → отсортировано 2,4,5,9
assert query_kth(roots, vals, 0, 6, 1) == 1      # минимум всего массива
assert query_kth(roots, vals, 3, 3, 1) == 4      # отрезок из одного элемента

Обратите внимание, что исходный массив никто не менял и не сортировал — вся структура строится один раз, а дальше отвечает на произвольные запросы к произвольным отрезкам. Эфемерное дерево отрезков так не умеет: оно знает только своё текущее состояние.

Сложность: построение O(n log n) времени и памяти, запрос O(log n). Тот же приём даёт персистентный DSU (без сжатия путей, только union by rank — снова из-за амортизации!), персистентный trie для «XOR-максимума в префиксе» и «откат» состояния в offline-алгоритмах.

Bit-partitioned vector: персистентный массив, который реально быстр

Массив с path copying — это O(log n) на чтение вместо O(1), и в наивной бинарной версии глубина 20 при миллионе элементов означает 20 промахов кэша. Рич Хикки в Clojure популяризовал решение Фила Багвелла: дерево с ветвлением 32 (bit-partitioned trie, из статьи «Ideal Hash Trees», lampwww.epfl.ch/papers/idealhashtrees.pdf).

Индекс разбивается на группы по 5 бит, каждая группа — уровень. При 32-арном ветвлении глубина для 10⁹ элементов равна 6. Формально сложность всё ещё O(log₃₂ n), но это «O(1) с очень большой константой отсечки»: любой реалистичный массив укладывается в 6–7 уровней.

SHIFT = 5                       # 32-арное ветвление
MASK  = (1 << SHIFT) - 1

def lookup(root, shift, i):
    """Спуск по 5 бит индекса за уровень. Никаких сравнений — только сдвиги и индексация."""
    node = root
    while shift > 0:
        node = node[(i >> shift) & MASK]
        shift -= SHIFT
    return node[i & MASK]       # листовой массив из 32 элементов — одна кэш-линия × 4

def assoc(node, shift, i, value):
    """Персистентная замена элемента: копируется по одному узлу на уровень (≤ 7 узлов)."""
    new = list(node)            # копия массива из 32 ссылок
    if shift == 0:
        new[i & MASK] = value
    else:
        idx = (i >> shift) & MASK
        new[idx] = assoc(node[idx], shift - SHIFT, i, value)
    return new

Замена одного элемента копирует ≤ 7 узлов по 32 ссылки — около 1.8 КБ вместо копирования всего массива. Хвостовые оптимизации (tail chunk) делают conj в конец амортизированно O(1). На той же основе построен HAMT (Hash Array Mapped Trie) — персистентная хеш-таблица, где вместо индекса по дереву спускается хеш ключа, а разреженные узлы сжимаются битовой маской. HAMT — это то, что стоит за clojure.lang.PersistentHashMap, scala.collection.immutable.HashMap, immutable.js и Map в Elixir/Erlang (см. трек Elixir).

Transients / уникальное владение. Если версия точно никому не видна (строится в цикле), копирование — чистая потеря. Clojure даёт transient/persistent!, Rust — Arc::make_mut (мутирует на месте, если счётчик ссылок == 1), Swift — isKnownUniquelyReferenced. Приём один и тот же: copy-on-write только при реальном разделении.

Где персистентность стоит в проде

• Git. Объектная модель — буквально персистентное дерево с path copying: коммит меняет один файл, копируются только tree-объекты по пути к нему, остальные blob’ы и tree’ы разделяются по хешу. История — DAG, то есть слитная персистентность. git-scm.com/book/en/v2/Git-Internals-Git-Objects
• Copy-on-write файловые системы: Btrfs, ZFS, APFS. Тот же path copying, но узлы — это страницы на диске, а «версия» — суперблок. Снапшот стоит O(1): сохранить указатель на корень.
• MVCC в СУБД. PostgreSQL хранит несколько версий кортежа с xmin/xmax — это fat nodes на уровне строк. LMDB — B+-дерево с чистым CoW, отсюда его знаменитое «читатели никогда не блокируются и никогда не блокируют». lmdb.readthedocs.io
• Frontend. React сравнивает состояния по ссылке: если объект не изменился физически, поддерево не перерисовывается. Иммутабельность превращает глубокое сравнение в ===.
• Undo/redo в редакторах и CAD: версия документа = корень дерева, undo = сдвиг индекса.

Часть II. Конкурентность

Почему нельзя просто обернуть всё мьютексом

Можно. Часто нужно. И это правильный первый шаг — «coarse-grained lock» проще, надёжнее и на низкой нагрузке быстрее хитрых алгоритмов. Проблемы начинаются, когда:

1. Нет масштабирования. Критическая секция сериализует ядра. По закону Амдала при 5% последовательного кода потолок ускорения — 20×, сколько ядер ни добавь.
2. Конвоирование (lock convoy). Поток, взявший лок, вытесняется планировщиком; все остальные ждут его кванта времени. Латентность хвоста взрывается.
3. Инверсия приоритетов и отсутствие гарантий прогресса: если владелец лока упал или ушёл в своп, структура заблокирована навсегда.

Отсюда иерархия гарантий прогресса — она важнее слова «lock-free» в маркетинге:

Практический смысл: lock-free ≠ быстрее. Lock-free гарантирует, что система не встанет из-за неудачно вытесненного потока, но при высокой конкуренции CAS-цикл может крутиться вхолостую и проигрывать мьютексу. Wait-free почти всегда медленнее в среднем — его берут там, где важен худший случай (реальное время, обработка прерываний).

Атомарный примитив: CAS

Вся lock-free-алгоритмика стоит на одной инструкции — compare-and-swap:

CAS(addr, expected, new) -> bool:
    атомарно:
        if *addr == expected:
            *addr = new
            return true
        return false

На x86 это lock cmpxchg, на ARM — пара ldrex/strex (LL/SC). Херлихи показал («Wait-Free Synchronization», 1991, cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf), что у CAS бесконечное число консенсуса: из него можно построить wait-free-реализацию любого объекта для любого числа потоков. Из атомарных чтения/записи — нельзя даже для двух. Именно поэтому CAS есть в каждом процессоре.

Канонический шаблон — read-modify-CAS-retry:

for {
    old := ptr.Load()
    new := computeNewValue(old)   // чистая функция, без побочных эффектов!
    if ptr.CompareAndSwap(old, new) {
        break
    }
    // кто-то опередил — начинаем заново с новым old
}

Два правила, которые нарушают чаще всего: computeNewValue обязана быть чистой (её результат выбрасывается при неудачном CAS), и между Load и CAS нельзя делать ничего необратимого — ни записи в общую память, ни отправки в сеть.

Стек Трайбера и проблема ABA

Простейшая lock-free-структура — стек на односвязном списке (Treiber, 1986). Вершина — атомарный указатель, push и pop — CAS по ней. Опирается на связные списки и стеки.

package lockfree

import "sync/atomic"

type node[T any] struct {
    value T
    next  *node[T]
}

// Stack — lock-free стек Трайбера.
type Stack[T any] struct {
    top atomic.Pointer[node[T]]
}

func (s *Stack[T]) Push(v T) {
    n := &node[T]{value: v}
    for {
        old := s.top.Load()
        n.next = old                       // готовим новый узел, он ещё никому не виден
        if s.top.CompareAndSwap(old, n) {  // публикуем одной атомарной записью
            return
        }
    }
}

func (s *Stack[T]) Pop() (T, bool) {
    for {
        old := s.top.Load()
        if old == nil {
            var zero T
            return zero, false
        }
        if s.top.CompareAndSwap(old, old.next) {
            return old.value, true
        }
    }
}

Код короткий и обманчиво простой. В языке со сборщиком мусора он корректен. В C++ или Rust с ручным освобождением он содержит две смертельные ошибки.

Ошибка первая — ABA. Поток читает top == A, засыпает. Другой поток снимает A, снимает B, кладёт A обратно (тот же адрес — аллокатор переиспользовал память). Первый просыпается, делает CAS(top, A, A.next) — CAS успешен, потому что адрес совпал, — и записывает в вершину B, который уже удалён и освобождён. Стек разрушен.

Лечится версионным тегом: указатель хранится вместе со счётчиком (double-width CAS, cmpxchg16b), либо счётчик прячут в неиспользуемые старшие 16 бит указателя (pointer tagging). CAS сравнивает пару (указатель, версия), и «тот же адрес, но другая версия» больше не проходит.

Ошибка вторая — освобождение памяти. Даже без ABA нельзя вызвать free(old) после успешного pop: другой поток прямо сейчас может держать указатель на этот узел и вот-вот разыменует old.next. Это фундаментальная проблема lock-free — она сложнее самого алгоритма.

Безопасное освобождение: hazard pointers, epochs, RCU

Три инженерных ответа на вопрос «когда узел действительно никому не нужен»:

RCU — самая успешная из трёх: это несущая конструкция ядра Linux (kernel.org/doc/html/latest/RCU/whatisRCU.html), где чтение защищённой структуры не стоит ни одной атомарной операции. В userspace есть liburcu, в Rust — crossbeam-epoch, в C++ — folly::hazptr и стандартизованные std::hazard_pointer (C++26).

Очередь Майкла — Скотта

Классическая lock-free FIFO-очередь (Michael & Scott, PODC 1996, dl.acm.org/doi/10.1145/248052.248106) — основа java.util.concurrent.ConcurrentLinkedQueue. Два трюка:

1. Фиктивный узел (dummy) в голове — чтобы head и tail никогда не были nil и enqueue/dequeue не конфликтовали за один и тот же указатель на пустой очереди.
2. Помощь (helping) — enqueue делается в два CAS: сначала tail.next, потом tail. Между ними очередь в «промежуточном» состоянии. Любой поток, увидевший tail.next != nil, обязан сначала дотолкнуть чужой tail, и только потом делать своё дело. Это и даёт lock-freedom: застрявший поток не блокирует остальных, они завершают его работу за него.

enqueue(q, v):
    n = new Node(v, next=nil)
    loop:
        t    = q.tail
        next = t.next
        if t != q.tail: continue          # снимок устарел
        if next != nil:                   # чужая незавершённая операция —
            CAS(q.tail, t, next)          # помогаем и пробуем снова
            continue
        if CAS(t.next, nil, n):           # шаг 1: подцепили узел
            CAS(q.tail, t, n)             # шаг 2: сдвинули хвост (может провалиться — не страшно)
            return

Обратите внимание: последний CAS разрешено провалить — если он не удался, значит кто-то уже помог. Это типичная для lock-free мысль: «не гарантирую, что сделаю я; гарантирую, что будет сделано».

Конкурентные словари и упорядоченные множества

Хеш-таблицы

Развитие подходов хорошо видно на истории java.util.concurrent:

Главная сложность конкурентной хеш-таблицы — не вставка, а рехеширование. Разом перестроить таблицу нельзя: это остановит всех. Решения — split-ordered lists (Shalev & Shavit, «Split-Ordered Lists: Lock-Free Extensible Hash Tables», people.csail.mit.edu/shanir/publications/Split-Ordered_Lists.pdf), где корзины не переносятся вообще, а лишь «расщепляются» в одном общем отсортированном по reversed-хешу списке, — либо кооперативный инкрементальный ресайз, как в Java 8.

sync.Map в Go — ещё один узкоспециализированный ответ: два уровня, атомарная read-only копия + мутируемая dirty-карта под мьютексом. Он выигрывает только в двух сценариях (ключи пишутся один раз и много читаются; разные горутины работают с непересекающимися ключами) — в остальных обычная map под RWMutex быстрее. См. pkg.go.dev/sync#Map и трек Go.

Почему конкурентные множества — это скип-листы, а не деревья

Сбалансированное дерево при вставке делает поворот, который меняет несколько узлов и корень атомарно. Сделать это lock-free крайне тяжело: нужен многословный CAS, которого в железе нет. Поэтому в конкурентном мире побеждает скип-лист:

• вставка — это локальная операция: CAS на next в каждом из O(log n) уровней;
• никаких глобальных перестроений, балансировка вероятностная, а не структурная;
• уровни независимы, так что «частично вставленный» элемент — корректное состояние.

Отсюда java.util.concurrent.ConcurrentSkipListMap, memtable в LevelDB и RocksDB (конкурентный skiplist), индексы в Redis (ZSET). Если вам нужен упорядоченный конкурентный контейнер — по умолчанию это скип-лист.

Мост: иммутабельность как самый простой конкурентный алгоритм

Вот главный практический вывод статьи. Если структура персистентная, то конкурентная версия строится тривиально:

• читатели берут текущий корень одной атомарной загрузкой и дальше работают с ним как с частной константой — ноль блокировок, ноль CAS, ноль барьеров на чтении;
• писатель строит новую версию (path copying, O(log n)) и подменяет корень одним CAS;
• старая версия остаётся валидной ровно столько, сколько её кто-то держит, — реклэйм памяти делает GC (или refcount).

// COWMap — карта, оптимизированная под «много читателей, редкие записи».
// Чтение полностью бесплатно: атомарная загрузка указателя и обычный доступ к map.
type COWMap[K comparable, V any] struct {
    mu sync.Mutex                  // сериализует ТОЛЬКО писателей
    m  atomic.Pointer[map[K]V]
}

func NewCOWMap[K comparable, V any]() *COWMap[K, V] {
    c := &COWMap[K, V]{}
    empty := make(map[K]V)
    c.m.Store(&empty)
    return c
}

func (c *COWMap[K, V]) Get(k K) (V, bool) {
    m := *c.m.Load()               // O(1), без синхронизации: карта неизменяема
    v, ok := m[k]
    return v, ok
}

func (c *COWMap[K, V]) Set(k K, v V) {
    c.mu.Lock()                    // писатели не должны терять записи друг друга
    defer c.mu.Unlock()
    old := *c.m.Load()
    next := make(map[K]V, len(old)+1)
    for kk, vv := range old {      // O(n) — вот и вся плата
        next[kk] = vv
    }
    next[k] = v
    c.m.Store(&next)               // публикация одной атомарной записью
}

Здесь запись — O(n), и это осознанный размен: при соотношении 10000 чтений на 1 запись такая карта разносит любой мьютекс. Именно так устроены CopyOnWriteArrayList в Java, таблицы маршрутизации в сетевом софте, конфигурация и feature-флаги в сервисах, снапшоты метрик. А если O(n) на запись слишком дорого — замените обычную map на HAMT из части I, и запись станет O(log₃₂ n) при том же бесплатном чтении. Персистентность и конкурентность сходятся в одной точке.

Эту же идею на уровне языка реализует STM (software transactional memory): Clojure ref/dosync и Haskell STM дают композируемые транзакции над иммутабельными значениями — см. Composable Memory Transactions Харриса и Пейтона Джонса.

Железо: то, что не видно в псевдокоде

Модель памяти. Компилятор и процессор переупорядочивают доступы к памяти. Без явных барьеров «сначала заполнил узел, потом опубликовал указатель» может выполниться наоборот, и другой поток увидит мусор. Отсюда release на публикации и acquire на чтении (C++ std::memory_order, Java volatile/VarHandle, Go — вся синхронизация описана в The Go Memory Model). Правило для прикладного кода: если вы пишете atomics с relaxed-порядком, вы должны уметь доказать корректность формально.

Ложное разделение (false sharing). Единица когерентности — кэш-линия в 64 байта. Два счётчика, лежащие рядом, конфликтуют, даже будучи логически независимыми.

Это часто 10–50× замедления на ровном месте. Лечение — паддинг: @Contended в Java, #[repr(align(64))] в Rust, cpu.CacheLinePad в Go, alignas(64) в C++. Замер разницы — классика блога Preshing (preshing.com).

LMAX Disruptor — образцовый пример проектирования «под железо»: кольцевой буфер фиксированного размера, предраспределённые объекты (ноль аллокаций → ноль GC-пауз), паддинг курсоров, единственный CAS на публикацию, механическое сочувствие вместо теоретической красоты. Результат — миллионы сообщений в секунду с латентностью в наносекунды. lmax-exchange.github.io/disruptor

Корректность: линеаризуемость

Как вообще сформулировать «конкурентная структура работает правильно»? Стандарт — линеаризуемость (Herlihy & Wing, 1990): каждая операция выглядит так, будто произошла мгновенно в некоторый момент между её вызовом и возвратом, и полученная последовательная история корректна. Практическое следствие: у каждой операции надо уметь назвать точку линеаризации — обычно это тот самый успешный CAS. Если вы не можете указать пальцем на строчку, где операция «случилась», алгоритм скорее всего некорректен.

И следствие ещё важнее: size() у конкурентной коллекции не линеаризуем без глобальной блокировки, поэтому в ConcurrentHashMap он приблизительный. Не стройте на нём логику.

Типичные ошибки

В персистентных структурах:

1. Мутировать «неизменяемый» узел. Одна забытая запись в поле — и вы испортили все версии сразу, включая те, что уже отдали наружу. Замораживайте узлы средствами языка (frozen=True, final, отсутствие mut), а не дисциплиной.
2. Path copying поверх амортизированной структуры (splay, динамический массив, DSU со сжатием путей) — асимптотика рушится, см. врезку выше.
3. Забыть, что версии держат память. Массив из миллиона корней — это миллион живых поддеревьев; ничего не соберётся. Персистентность требует явной политики удержания версий.
4. Ожидать структурного разделения от deepcopy. Копия, сделанная «в лоб», разделения не даёт — нужна структура, спроектированная под него.

В конкурентных структурах:

1. Композиция атомарных операций не атомарна. if !m.Has(k) { m.Set(k, v) } — гонка, даже если обе операции по отдельности потокобезопасны. Нужен SetIfAbsent/LoadOrStore.
2. Побочные эффекты внутри CAS-цикла. Тело ретрая выполняется многократно.
3. Игнорирование реклэйма памяти в языках без GC — самый частый способ получить use-after-free, который воспроизводится раз в неделю на проде.
4. Ложное разделение и отсутствие backoff в CAS-цикле: под нагрузкой ядра выжигают шину когерентности вхолостую.
5. «Сделаем lock-free, будет быстрее». Сначала измерьте. Мьютекс с хорошей локальностью данных очень часто быстрее lock-free-структуры с плохой.
6. Оптимистичное чтение без валидации. Прочитали два поля по отдельности — получили состояние, которого никогда не существовало (seqlock решает это счётчиком версии).

Мини-итог

• Персистентность — это про версии, а не про диск. Базовый приём — path copying: копируем только путь O(log n), остальное разделяем. Версия = корень.
• Персистентность несовместима с амортизированными структурами и требует балансировки; практический оптимум для массивов и словарей — bit-partitioned trie / HAMT с ветвлением 32.
• Персистентное дерево отрезков превращает «запросы к истории» в стандартный приём: O(log n) на запрос, O(n log n) памяти.
• Конкурентность строится на CAS; ценность lock-free — в гарантиях прогресса, а не в скорости. Иерархия: blocking ⊂ obstruction-free ⊂ lock-free ⊂ wait-free.
• Самое трудное в lock-free — не алгоритм, а освобождение памяти: hazard pointers, EBR, RCU.
• Для упорядоченных конкурентных множеств выбирают скип-лист, для словарей — шардирование или CAS по корзине; size() при этом перестаёт быть точным.
• Мост между частями: иммутабельная структура + атомарная подмена корня = самая простая и часто самая быстрая конкурентная структура при read-mostly нагрузке.
• И главное правило инженерной честности: мьютекс — правильный ответ по умолчанию; всё остальное включается после бенчмарка, который показал, что он не подходит.

Источники

• J. Driscoll, N. Sarnak, D. Sleator, R. Tarjan. Making Data Structures Persistent, 1986 — dl.acm.org/doi/10.1145/28395.28424
• C. Okasaki. Purely Functional Data Structures, Cambridge University Press — cambridge.org
• P. Bagwell. Ideal Hash Trees, 2001 — lampwww.epfl.ch/papers/idealhashtrees.pdf
• M. Herlihy, N. Shavit. The Art of Multiprocessor Programming — базовый учебник по теме: elsevier.com
• M. Herlihy, J. Wing. Linearizability: A Correctness Condition for Concurrent Objects, 1990 — dl.acm.org/doi/10.1145/78969.78972
• M. Michael, M. Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms, 1996 — dl.acm.org/doi/10.1145/248052.248106
• M. Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, 2004 — dl.acm.org/doi/10.1109/TPDS.2004.8
• O. Shalev, N. Shavit. Split-Ordered Lists: Lock-Free Extensible Hash Tables — people.csail.mit.edu/shanir/publications/Split-Ordered_Lists.pdf
• Linux RCU — kernel.org/doc/html/latest/RCU/whatisRCU.html
• The Go Memory Model — go.dev/ref/mem; JSR-133 (Java Memory Model) — cs.umd.edu/~pugh/java/memoryModel/
• LMAX Disruptor — lmax-exchange.github.io/disruptor
• Preshing on Programming — практическое введение в lock-free и модели памяти: preshing.com
• Git Internals — git-scm.com/book/en/v2/Git-Internals-Git-Objects

Что дальше

Это последняя статья трека «Структуры данных». Мы прошли путь от модели стоимости и массивов через хеш-таблицы, сбалансированные деревья, кучи, графы и вероятностные структуры до версий и параллелизма. Общая карта — в обзоре трека.

Куда двигаться дальше:

• Алгоритмы — естественное продолжение: структуры данных существуют ради алгоритмов, которые на них работают. Сортировки, поиск, графовые алгоритмы, динамическое программирование, жадные стратегии.
• Go — язык, в котором конкурентность из этой статьи становится повседневной практикой: горутины, каналы, sync/atomic, race detector.
• Elixir — противоположный подход к тем же задачам: полная иммутабельность, персистентные структуры по умолчанию, акторы вместо разделяемой памяти. Отличный способ прочувствовать часть I на практике.
• TypeScript и C# — если ближе прикладная разработка с иммутабельными коллекциями и async.
• Data Engineering — там MVCC, снапшоты и LSM-деревья из этой статьи работают в промышленном масштабе.

Общая карта всех треков портала и рекомендованный порядок изучения — в дорожной карте.