Графовые и key-value БД: Неo4j, Dgraph, etcd, RocksDB, LMDB

На первый взгляд соединять в одной статье графовые и key-value базы — насилие над классификацией. Одни хранят самую богатую модель данных из существующих, другие — самую бедную. Но именно поэтому они и стоят рядом: это два конца одной оси.

Key-value — это дно абстракции. Упорядоченное или неупорядоченное отображение байтов в байты, без схемы, без запросов, без планировщика. Настолько мало, что почти любая другая база данных внутри себя содержит именно такой движок: InnoDB под MySQL, RocksDB под TiKV, Yugabyte, Kafka Streams и Ceph, Badger под Dgraph, Pebble под CockroachDB, LMDB под OpenLDAP и Monero. Когда вы работаете с key-value напрямую, вы работаете со слоем хранения без СУБД поверх него, и вся работа планировщика ложится на вас.

Граф — это верх абстракции по связности. Там, где реляционная модель кодирует связь как совпадение значений (внешний ключ, который надо найти), графовая модель кодирует её как физический указатель, по которому надо перейти. Разница в стоимости обхода — на порядки, но только для определённого класса запросов и ценой всего остального.

Обе категории объединяет одно свойство, которое стоит осознать до выбора: вы отказываетесь от универсальности в обмен на конкретную операцию. У key-value эта операция — «дай значение по ключу за микросекунды с предсказуемой стоимостью». У графа — «пройди k рёбер от вершины, не заплатив за размер базы». Всё, что вне этих операций, вы делаете вручную и дороже, чем в PostgreSQL.

Предыдущие статьи трека дали контекст: таксономию NoSQL и CAP, Redis как in-memory key-value и LSM-деревья в контексте wide-column. Здесь мы спускаемся ниже — к движкам, из которых всё это собрано, — и поднимаемся выше, к модели, где связь важнее сущности.

Часть I. Key-value: движки, а не базы

Что такое key-value на самом деле

Минимальный контракт key-value-движка — четыре операции: Put(k, v), Get(k), Delete(k) и, если хранилище упорядоченное, Scan(from, to). Последняя операция разделяет мир надвое.

• Неупорядоченные (хеш-таблица на диске, Memcached, чистый Bitcask) дают O(1) доступ, но не умеют «дай всё с префиксом user:42:». Диапазонных запросов нет вообще.
• Упорядоченные (RocksDB, LMDB, LevelDB, BoltDB) держат ключи в лексикографическом порядке байтов и позволяют итерироваться. Это фундаментальнее, чем кажется: упорядоченный key-value — достаточная основа, чтобы построить поверх него реляционную БД. Именно так работают TiKV, YugabyteDB и CockroachDB — они кодируют строки таблиц в ключи вида /tenant/table/index/pk/column, и вторичный индекс становится просто другим диапазоном ключей.

Из этого следует главный приём проектирования на key-value: весь ваш дизайн — это дизайн схемы ключа. Порядок компонентов в ключе определяет, какие запросы возможны, ровно как порядок колонок в составном B-tree-индексе (см. индексы и планы).

# Кодирование составного ключа для упорядоченного key-value.
# Ключевое требование: лексикографический порядок байтов должен совпадать
# с логическим порядком значений. Для этого числа кодируем big-endian.

import struct

def encode_key(user_id: int, ts_ms: int, event_id: int) -> bytes:
    # b'E' — префикс пространства имён (аналог имени таблицы)
    # >Q — беззнаковое 64-битное big-endian: порядок байтов = порядок чисел
    return b"E" + struct.pack(">QQQ", user_id, ts_ms, event_id)

def range_for_user_window(user_id: int, t_from: int, t_to: int):
    # Диапазонный скан = один непрерывный проход по отсортированным ключам.
    # Стоимость: O(log N) на позиционирование + O(m) на m результатов.
    return (encode_key(user_id, t_from, 0),
            encode_key(user_id, t_to, 2**64 - 1))

# Ловушка №1: little-endian сломает порядок (255 окажется «больше» 256).
# Ловушка №2: строки переменной длины нельзя просто конкатенировать —
# ключи ("ab", "c") и ("a", "bc") дадут одинаковые байты. Нужно
# экранирование нулевого байта или префикс длины.

RocksDB: LSM-движок, который лежит под половиной индустрии

RocksDB — форк LevelDB, сделанный в Facebook в 2012 году под флеш-накопители и многоядерные машины. Модель — LSM-дерево: запись идёт в WAL и в memtable (обычно skip-list в памяти), memtable по заполнению становится иммутабельным и сбрасывается на диск как SST-файл, а фоновая компакция сливает файлы уровнями.

Три числа, которыми описывается любой движок хранения, и которые всегда в конфликте (RUM conjecture, Athanassoulis et al., EDBT 2016):

Практический вывод: leveled-компакция экономит место и чтение ценой записи, universal — наоборот. Если у вас тяжёлая запись и есть свободный диск — universal; если чтения и место дороже — leveled (дефолт).

// Минимально осмысленная продакшн-конфигурация RocksDB.
// Комментарии — про то, что каждая опция реально стоит.
rocksdb::Options opts;
opts.create_if_missing = true;

// Память под memtable: больше буфер — реже flush, меньше L0-файлов,
// но дольше восстановление после краха и больше пик по RAM.
opts.write_buffer_size = 256ull << 20;          // 256 МБ
opts.max_write_buffer_number = 4;               // до 4 буферов в памяти
opts.min_write_buffer_number_to_merge = 2;      // сливать по 2 при flush

// Параллелизм фона. Если компакция не успевает — будет write stall,
// и латентность записи улетит с 0.1 мс до секунд. Это причина №1
// инцидентов с RocksDB.
opts.max_background_jobs = 8;
opts.bytes_per_sync = 1ull << 20;               // подсказка ОС: не копить грязные страницы

// Компакция и размеры уровней
opts.compaction_style = rocksdb::kCompactionStyleLevel;
opts.level0_file_num_compaction_trigger = 4;
opts.level0_slowdown_writes_trigger = 20;       // мягкое торможение
opts.level0_stop_writes_trigger = 36;           // полная остановка записи
opts.max_bytes_for_level_base = 1ull << 30;     // L1 = 1 ГБ, дальше ×10

rocksdb::BlockBasedTableOptions tbl;
// Block cache — главный рычаг латентности чтения. Обычно 1/3 RAM машины.
tbl.block_cache = rocksdb::NewLRUCache(8ull << 30);
// Bloom-фильтр: 10 бит на ключ ≈ 1% ложноположительных.
// Без него точечное чтение обходит ВСЕ уровни.
tbl.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10, false));
// Индексы и фильтры в кэше, но с приоритетом — иначе они вытесняются данными
tbl.cache_index_and_filter_blocks = true;
tbl.pin_l0_filter_and_index_blocks_in_cache = true;
opts.table_factory.reset(rocksdb::NewBlockBasedTableFactory(tbl));

// Column family — отдельное логическое пространство с собственным
// набором SST-файлов, но общим WAL. Аналог «таблицы».

Что реально ломается в проде с RocksDB:

1. Write stall. level0_stop_writes_trigger достигнут — и приложение просто перестаёт писать. Диагностика: rocksdb.is-write-stopped, rocksdb.actual-delayed-write-rate и логи LOG-файла. Лечение — больше фоновых потоков, быстрее диск, больше write_buffer_size или переход на universal-компакцию.
2. Tombstone-накопление. Массовое удаление создаёт маркеры удаления, которые живут до полной компакции. Скан по диапазону, где было удалено миллион ключей, честно прочитает миллион tombstone. Это та же проблема, что и в Cassandra. Спасает DeleteRange вместо цикла Delete.
3. Слишком много column families. Каждая — свой набор memtable и flush; сотня CF на одной машине означает постоянный фоновый шторм.
4. Get на несуществующий ключ дороже, чем на существующий, если Bloom-фильтры выгружены из кэша. Проверяйте rocksdb.bloom.filter.useful.

LMDB: противоположная философия

LMDB (Lightning Memory-Mapped Database, Говард Чу, проект OpenLDAP) — это ~10 тысяч строк C и полный отказ от всего, что делает RocksDB сложным. Никакого пула буферов, никаких фоновых потоков, никакой компакции, никакого WAL. Файл целиком отображается в память через mmap, а дерево — copy-on-write B+tree: изменение листа копирует его и весь путь до корня, коммит атомарно переключает мета-страницу.

Следствия этой конструкции радикальны:

• Чтение — это разыменование указателя. mdb_get возвращает указатель внутрь mmap; ни копирования, ни аллокации, ни системного вызова (после первого page fault). Отсюда цифры вроде 10–20 млн чтений в секунду на многоядерной машине с прогретым кэшем — читатели линейно масштабируются по ядрам, потому что вообще не берут блокировок.
• Писатель ровно один. Не «один на таблицу» — один на всю среду (environment), защищённый мьютексом. Параллельной записи нет по построению.
• Восстановления после краха не существует, потому что нечего восстанавливать: файл всегда консистентен на одной из двух мета-страниц.
• Размер задаётся заранее через mdb_env_set_mapsize. Превысили — MDB_MAP_FULL. Это не «база выросла», это «приложение упало».

/* LMDB: полный цикл. Обратите внимание на то, чего здесь НЕТ:
   настроек кэша, потоков, компакции, конфига вообще. */
MDB_env *env;
mdb_env_create(&env);
/* mapsize — верхняя граница файла. Ставьте с запасом ×5–10:
   виртуальная память дешёвая, а увеличение требует закрытия среды. */
mdb_env_set_mapsize(env, 64ULL * 1024 * 1024 * 1024);   /* 64 ГБ */
mdb_env_set_maxdbs(env, 8);                              /* именованных БД */
mdb_env_set_maxreaders(env, 512);                        /* слотов в lock-таблице */
mdb_env_open(env, "/var/lib/app/db", MDB_NOTLS, 0664);

MDB_txn *txn; MDB_dbi dbi;
mdb_txn_begin(env, NULL, 0, &txn);          /* NULL = не вложенная, 0 = на запись */
mdb_dbi_open(txn, "events", MDB_CREATE, &dbi);

MDB_val k = { .mv_size = 4, .mv_data = "u:42" };
MDB_val v = { .mv_size = 5, .mv_data = "hello" };
mdb_put(txn, dbi, &k, &v, 0);
mdb_txn_commit(txn);                        /* здесь один fsync мета-страницы */

/* Чтение: zero-copy. Указатель v.mv_data валиден, пока жива транзакция.
   Скопировать данные до mdb_txn_abort — иначе use-after-free. */
MDB_txn *rtxn;
mdb_txn_begin(env, NULL, MDB_RDONLY, &rtxn);
if (mdb_get(rtxn, dbi, &k, &v) == MDB_SUCCESS) { /* v.mv_data — прямо в mmap */ }
mdb_txn_abort(rtxn);   /* read-only транзакцию завершаем ВСЕГДА и БЫСТРО */

Главная продакшн-ловушка LMDB — долгоживущая read-only транзакция. Пока она открыта, ни одна освобождённая страница не может быть переиспользована: снимок должен оставаться валидным. Забытый курсор в фоновом потоке — и файл растёт на гигабайты в час при неизменном объёме данных. Симптом: mdb_stat показывает мало страниц с данными и огромный размер файла. Второе — MDB_NOSYNC и MDB_WRITEMAP: они дают кратный прирост записи, но возвращают вас в мир, где крах ОС означает потерю или порчу данных.

Сравнение встраиваемых движков

Порядки цифр (NVMe, значение 1 КБ, датасет больше RAM — из бенчмарков RocksDB и LMDB microbench); это ориентиры, а не обещания — измеряйте на своей нагрузке:

Ключевой вывод: выбор между LSM и COW B+tree — это выбор между пропускной способностью записи и простотой эксплуатации. RocksDB даст вам больше, но потребует инженера, который понимает компакцию. LMDB не потребует ничего — и не даст параллельной записи.

etcd: key-value, который на самом деле про консенсус

etcd — это не хранилище данных, это хранилище решений. Каждая запись проходит через Raft: лидер реплицирует запись в журнал, ждёт подтверждения кворума, только потом применяет к состоянию. Значит, стоимость записи — это fsync на лидере + сетевой обход до кворума + fsync на репликах, то есть единицы миллисекунд в одном ДЦ и десятки между регионами. Никакой тюнинг это не изменит: это цена линеаризуемости.

Модель данных etcd — плоское упорядоченное key-value с глобальным монотонным счётчиком ревизий. Это принципиально: у каждого ключа есть create_revision, mod_revision и version, и любой клиент может подписаться на изменения начиная с конкретной ревизии. Именно на этом построен весь механизм watch в Kubernetes — контроллер переподключается и продолжает с той ревизии, на которой остановился, без потери событий.

# Compare-And-Swap: единственный корректный способ конкурентного обновления.
# Транзакция etcd — это If/Then/Else над ревизиями и значениями.
etcdctl txn <<'EOF'
mod("service/leader") = "7"

put service/leader "node-a"

get service/leader
EOF

# Аренда (lease) — TTL, привязанный к сессии. Ключ живёт, пока клиент
# шлёт keepalive. Основа распределённых блокировок и service discovery.
LEASE=$(etcdctl lease grant 15 | awk '{print $2}')
etcdctl put --lease=$LEASE service/instances/node-a '{"addr":"10.0.0.7:8080"}'
etcdctl lease keep-alive $LEASE &     # обновление каждые ~5 с

# Наблюдение за префиксом с конкретной ревизии — без потери событий
etcdctl watch --prefix service/instances/ --rev=128

# ОБЯЗАТЕЛЬНАЯ эксплуатация: компакция истории + дефрагментация.
# Без этого база растёт монотонно и упирается в квоту.
etcdctl compact $(etcdctl endpoint status -w json | jq -r '.[0].Status.header.revision')
etcdctl defrag --cluster        # блокирует узел на время работы — по одному!

Жизненный цикл аренды — источник половины инцидентов в системах, построенных на etcd:

Жёсткие ограничения etcd, которые нельзя обойти конфигом:

Отсюда правило: etcd — для метаданных, а не для данных. Хранить в нём пользовательские сессии, счётчики или события — классическая ошибка, которая заканчивается деградацией всего кластера Kubernetes, если etcd общий.

Часть II. Графовые базы данных

Задача, ради которой существует граф

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

Проблема в стоимости. Каждый «прыжок» по связи в реляционной модели — это поиск: обращение к B-tree-индексу за O(log N), где N — размер всей таблицы связей. Планировщик может выбрать hash join и прочитать таблицу целиком. Глубина обхода умножает эту стоимость и, что хуже, множит промежуточную кардинальность: 200 друзей × 200 друзей = 40 000 строк на втором уровне, 8 миллионов на третьем.

Графовая СУБД делает переход по ребру разыменованием указателя. В классическом формате хранения Neo4j запись вершины — 15 байт фиксированной длины, запись ребра — 34 байта, так что физический адрес вычисляется арифметикой: id × размер_записи. Ребро хранит ссылки на предыдущее и следующее ребро для каждого из двух своих концов — то есть все рёбра вершины образуют двусвязный список. Это и называется index-free adjacency: индекс нужен только на входе в граф, чтобы найти стартовую вершину.

Асимптотика:

• Реляционный обход: O(k · log N) при N — размер таблицы связей, k — число посещённых рёбер. Плюс риск материализации промежуточных результатов.
• Графовый обход: O(сумма степеней посещённых вершин). Не зависит от размера базы. Обход в графе на миллиард рёбер стоит столько же, сколько в графе на миллион, если локальная плотность та же.

Это единственное настоящее преимущество графовых БД, и оно реально. Всё остальное — язык запросов, удобство моделирования — приятно, но воспроизводимо в PostgreSQL.

Модель: property graph против триплетов

Property graph (Neo4j, Memgraph, Neptune, JanusGraph): вершины с метками и свойствами, направленные типизированные рёбра со своими свойствами. Свойство на ребре — ключевое отличие от реляционной модели, где для этого нужна отдельная таблица-связка.

RDF / триплеты (Virtuoso, GraphDB, Apache Jena, Amazon Neptune в режиме SPARQL): всё — тройка субъект – предикат – объект, каждый узел имеет глобальный URI. Свойств у рёбер нет; чтобы их выразить, приходится реифицировать (превращать сам факт в узел). Зато модель самоописывающаяся, федерируемая между организациями и снабжена онтологиями (OWL, RDFS) с логическим выводом.

Практический критерий: RDF — когда данные интегрируются между организациями и важна семантика словарей (биомедицина, госданные, публикации). Property graph — во всех остальных случаях, потому что моделировать в нём проще, а инструментов больше.

Neo4j: устройство, Cypher и планы

Cypher — язык, где паттерн рисуется ASCII-графикой: (a)-[:KNOWS]->(b). С 2024 года у семейства появился стандарт ISO: GQL (ISO/IEC 39075:2024) — первый новый стандартный язык запросов после SQL, и Cypher — его непосредственный предок.

// Схема: ограничения создают индексы и гарантируют уникальность
CREATE CONSTRAINT person_email IF NOT EXISTS
FOR (p:Person) REQUIRE p.email IS UNIQUE;

CREATE INDEX company_industry IF NOT EXISTS
FOR (c:Company) ON (c.industry);

// Индекс по свойству РЕБРА (Neo4j 5+) — часто забывают, что он существует
CREATE INDEX knows_since IF NOT EXISTS
FOR ()-[k:KNOWS]-() ON (k.since);

// Загрузка данных: MERGE идемпотентен, но требует индекса,
// иначе каждый MERGE — полное сканирование по метке.
MERGE (p:Person {email: 'anna@example.com'})
  ON CREATE SET p.name = 'Аня', p.created = datetime()
  ON MATCH  SET p.lastSeen = datetime();

// Тот самый запрос «друзья друзей, работавшие в моих компаниях»
MATCH (me:Person {email: $email})-[:KNOWS]->(:Person)-[:KNOWS]->(fof:Person)
WHERE me <> fof
  AND NOT (me)-[:KNOWS]->(fof)          // отрицание паттерна — дёшево
MATCH (me)-[w1:WORKS_AT]->(c:Company)<-[w2:WORKS_AT]-(fof)
WHERE w1.from < w2.to AND w2.from < w1.to   // пересечение периодов
RETURN fof.name AS candidate,
       collect(DISTINCT c.name) AS sharedCompanies,
       count(DISTINCT c) AS strength
ORDER BY strength DESC
LIMIT 20;

Планы Neo4j читаются через EXPLAIN (оценка) и PROFILE (фактическое исполнение с числом обращений к хранилищу — db hits). Это прямой аналог EXPLAIN ANALYZE в PostgreSQL, и работать с ним нужно так же (см. индексы и планы выполнения).

PROFILE MATCH (me:Person {email:'anna@example.com'})-[:KNOWS*2]->(fof) RETURN count(fof)

+-----------------------+----------------+------+---------+----------------------------+
| Operator              | Estimated Rows | Rows | DB Hits | Details                    |
+-----------------------+----------------+------+---------+----------------------------+
| +ProduceResults       |              1 |    1 |       0 |                            |
| +EagerAggregation     |              1 |    1 |       0 | count(fof)                 |
| +VarLengthExpand(All) |          31250 | 4187 |    8562 | (me)-[:KNOWS*2..2]->(fof)  |
| +NodeIndexSeek        |              1 |    1 |       2 | :Person(email) = $autostr  |
+-----------------------+----------------+------+---------+----------------------------+

Total database accesses: 8564, total allocated memory: 312

Как это читать:

• NodeIndexSeek в самом низу — это хорошо. Если там NodeByLabelScan или, хуже, AllNodesScan — у вас нет индекса на точке входа, и запрос читает всю базу.
• DB Hits — настоящая единица стоимости. 8564 обращения — это дёшево. Если видите миллионы при десятках возвращённых строк, где-то раздувается промежуточная кардинальность.
• Разрыв Estimated Rows и Rows (31250 против 4187) — ошибка статистики. Neo4j оценивает по средней степени вершин; на скошенных распределениях он ошибается систематически.
• Eager-операторы — красный флаг: они материализуют весь промежуточный результат в памяти. Частая причина — MATCH после CREATE/SET в одном запросе.

Правила производительности Cypher, которые дают наибольший эффект:

1. Ограничьте типы и направление рёбер. -[:KNOWS]-> вместо --. Ненаправленный обход без типа расширяет по всем рёбрам сразу.
2. Ограничьте глубину явно. [:KNOWS*1..3] вместо [:KNOWS*]. Неограниченный обход на связном графе посещает всё.
3. Начинайте с самой селективной точки. Планировщик пытается сам, но подсказки (USING INDEX) иногда необходимы.
4. Для кратчайших путей — shortestPath(), а не паттерн переменной длины: это двунаправленный BFS, а не полный перебор.
5. Батчируйте запись. Транзакция на 1 млн CREATE съест кучу памяти; используйте CALL { ... } IN TRANSACTIONS OF 10000 ROWS.

Эксплуатация Neo4j. Две области памяти, и путать их нельзя:

# neo4j.conf — типичная машина на 64 ГБ RAM

# Page cache: сюда должен помещаться граф целиком, иначе обход
# превращается в случайное чтение с диска и теряет своё преимущество.
# Это главный параметр производительности графовой БД.
server.memory.pagecache.size=32g

# Heap JVM: под промежуточные результаты запросов и транзакции.
# Больше 31 ГБ ставить нельзя — теряются compressed OOPs.
server.memory.heap.initial_size=16g
server.memory.heap.max_size=16g

# Защита от запроса, который решил обойти весь граф
db.transaction.timeout=120s
dbms.memory.transaction.total.max=8g
dbms.memory.transaction.max=2g

# Логирование медленных запросов — включать сразу, а не после инцидента
db.logs.query.enabled=INFO
db.logs.query.threshold=500ms

Оценка размера графа: примерно 15 байт × вершины + 34 байта × рёбра + свойства. Граф на 1 млрд рёбер — это порядка 34 ГБ только под рёбра, плюс свойства и индексы; реалистично закладывать 60–100 ГБ page cache. Если граф не помещается в page cache, преимущество index-free adjacency испаряется: указатель ведёт на страницу, которой нет в памяти, и вы платите случайным чтением с диска за каждое ребро.

Кластеризация и лицензии. Community-редакция — GPLv3, один инстанс, без кластеризации, без RBAC, без онлайн-бэкапа. Всё это — Enterprise, коммерческая лицензия с ценой, обсуждаемой индивидуально (порядок — десятки тысяч долларов в год за кластер; AuraDB как управляемый сервис тарифицируется по объёму памяти). Это самый частый сюрприз при выборе Neo4j: прототип на Community взлетает, а продакшн-требования (HA, бэкап без остановки, разграничение доступа) упираются в счёт.

Dgraph и распределённые графы

Neo4j — по существу однохостовая система с репликацией (в Enterprise-кластере запись идёт через Raft-лидера, чтения масштабируются репликами). Dgraph строился как распределённый с самого начала: написан на Go, поверх собственного LSM-движка Badger, шардируется по предикатам (по типу ребра), каждая группа — своя Raft-группа.

# Dgraph DQL: запрос обхода с фильтрами и агрегацией
{
  var(func: eq(email, "anna@example.com")) {
    friends as knows @filter(NOT eq(email, "anna@example.com")) {
      fof as knows
    }
  }
  result(func: uid(fof), first: 20) {
    uid
    name
    worksAt @filter(uid_in(company, val(sharedCompanies))) {
      name
    }
  }
}

Шардирование по предикату — сильное и одновременно опасное решение. Сильное: запрос «все рёбра типа knows» локализуется в одной группе. Опасное: предикат нельзя разбить между группами, поэтому один популярный тип ребра (follows в соцсети) становится горячим шардом целиком, и вертикальный рост — единственный выход.

Честно про зрелость: Jepsen-анализ Dgraph 1.0.2 (2018) и повторный анализ версии 1.1.1 (2020) обнаружили потерю данных, нарушения снапшот-изоляции и проблемы восстановления после разделения сети. Часть исправлена, но уровень доверия к распределённым графовым БД объективно ниже, чем к распределённым SQL-системам — им уделяют меньше внимания исследователи и меньше эксплуатируют под нагрузкой. Если распределённость критична, посмотрите на NewSQL и на моделирование графа поверх него.

Ландшафт графовых систем

Честное сравнение: а нужен ли вам вообще граф?

PostgreSQL умеет рекурсивные обходы через WITH RECURSIVE. Сравним на одной задаче — обход на 3 уровня в графе на 10 млн вершин и 100 млн рёбер.

-- PostgreSQL: обход в ширину на 3 уровня с отсечением циклов
WITH RECURSIVE traversal AS (
    SELECT p.id, 0 AS depth, ARRAY[p.id] AS path
    FROM person p
    WHERE p.email = 'anna@example.com'

    UNION ALL

    SELECT k.b_id, t.depth + 1, t.path || k.b_id
    FROM traversal t
    JOIN knows k ON k.a_id = t.id
    WHERE t.depth < 3
      AND NOT k.b_id = ANY(t.path)      -- защита от циклов, O(длина пути)
)
SELECT DISTINCT id FROM traversal WHERE depth = 3;

-- Обязательный индекс: без него каждый уровень — Seq Scan по knows
CREATE INDEX ON knows (a_id) INCLUDE (b_id);   -- покрывающий: Index Only Scan

-- EXPLAIN (ANALYZE, BUFFERS), сокращённо:
 CTE Scan on traversal  (actual rows=1284301 loops=1)
   ->  Recursive Union  (actual time=0.089..4812.331 rows=1284301)
         ->  Index Scan using person_email_key  (actual rows=1 loops=1)
         ->  Nested Loop  (actual rows=428100 loops=3)
               ->  WorkTable Scan on traversal  (actual rows=42810 loops=3)
               ->  Index Only Scan using knows_a_id_idx  (actual rows=10 loops=128430)
                     Heap Fetches: 0
                     Buffers: shared hit=384291 read=112884
 Planning Time: 0.612 ms
 Execution Time: 5218.774 ms

Что здесь видно и что из этого следует:

Практическое правило, которое сэкономит вам систему:

• Обходы до 2 уровней, граф — часть более крупной модели → оставайтесь в PostgreSQL. Facebook держит один из крупнейших социальных графов планеты на MySQL с кэширующим слоем TAO (статья, ATC 2013) — это прямое эмпирическое опровержение тезиса «соцсеть требует графовой БД».
• Нужны обходы переменной глубины, кратчайшие пути, обнаружение сообществ, PageRank, поиск паттернов мошенничества, рекомендации по связям → графовая БД оправдана.
• Граф — второстепенный аспект, но обходы нужны → Apache AGE или pgRouting в том же PostgreSQL: без второй системы в эксплуатации.

Отдельный сценарий: граф как аналитический артефакт, а не операционное хранилище. Если обходы нужны раз в сутки для расчёта фич, дешевле выгрузить рёбра в файл и посчитать библиотекой (NetworkX для миллионов рёбер, igraph/graph-tool/Spark GraphX для сотен миллионов), чем держать графовую СУБД в проде.

Продакшн-проблемы графовых БД

1. Суперузлы (dense nodes). Вершина со степенью в миллионы — популярный хештег, страна, служебный аккаунт. Любой обход, задевающий её, разворачивается в миллионы рёбер. Neo4j смягчает это relationship group-записями (при превышении порога, по умолчанию 50 рёбер, связи группируются по типу и направлению), но это лишь смягчение. Приёмы борьбы:

// ПЛОХО: обход через суперузел «Страна» соединяет всех со всеми
MATCH (a:Person)-[:LIVES_IN]->(:Country)<-[:LIVES_IN]-(b:Person) RETURN a, b

// ЛУЧШЕ: разбить суперузел на «сателлиты» по региону
// (:Person)-[:LIVES_IN]->(:Region)-[:PART_OF]->(:Country)

// ИЛИ: не превращать атрибут в вершину. Страна — свойство, а не узел,
// если по ней не нужен обход.
MATCH (a:Person {country: 'RU'}), (b:Person {country: 'RU'}) ...

Главный урок моделирования графов: вершиной должно быть то, через что вы обходите; всё остальное — свойство. Превращение каждого атрибута в вершину («потому что это же граф») — самая частая ошибка новичков и прямой путь к суперузлам.

2. Взрыв промежуточной кардинальности. Cypher-запрос без LIMIT и без ограничения глубины на связном графе выполнится за время, пропорциональное размеру графа. Обязательны db.transaction.timeout и лимит памяти на транзакцию.

3. Кэш планов и параметры. Литералы в запросе (WHERE p.email = 'anna@example.com') порождают новый план на каждое значение и вымывают кэш. Всегда параметры: $email. Это ровно та же проблема, что и с prepared statements в SQL.

4. Массовая загрузка. Транзакционная запись в граф медленная: neo4j-admin database import для первичной загрузки (миллионы записей в секунду, но только в пустую базу) против LOAD CSV с батчами (десятки тысяч в секунду) — разница на два порядка. Планируйте первичную загрузку заранее.

5. Отсутствие агрегатной аналитики. «Сколько заказов по месяцам за год» в графовой БД будет медленнее, чем в любой реляционной, и катастрофически медленнее, чем в ClickHouse. Граф не для этого.

Стоимость владения: честный счёт

Самая недооценённая строка — первая. Взять RocksDB, потому что «нужно просто key-value», означает взять на себя всё, что СУБД делает бесплатно: согласованные бэкапы, восстановление на момент времени, репликацию, эволюцию схемы, наблюдаемость. Если ваша нагрузка укладывается в PostgreSQL или SQLite — берите их.

Когда НЕ брать эти системы

Не берите встраиваемый key-value, если:

• нужен доступ из нескольких процессов или машин — это уже сетевая БД, и вы будете писать её сами;
• нужны запросы не по ключу — вы построите вторичные индексы вручную и получите проблемы согласованности;
• нет ресурса на тюнинг компакции (RocksDB) — write stall придёт в самый неподходящий момент;
• объём данных заранее неизвестен и может вырасти в 100 раз (LMDB и mapsize).

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

Не берите графовую БД, если:

• обходы не глубже двух уровней — рекурсивный CTE справится;
• основная нагрузка — агрегации и отчёты;
• граф не помещается в память одного узла и вы не готовы к рискам распределённых графовых систем;
• в команде нет никого, кто будет читать PROFILE и объяснять, почему запрос за 300 мс стал запросом за 40 секунд;
• вы выбираете её «потому что данные связанные». Все данные связанные — вопрос в том, ходите ли вы по этим связям вглубь.

Мини-итог

• Key-value — это слой хранения, а не база данных. Взяв его напрямую, вы берёте на себя роль СУБД: схему, индексы, бэкапы, репликацию. Иногда это правильно, но решение должно быть осознанным.
• RocksDB против LMDB — это LSM против copy-on-write B+tree, то есть высокая пропускная способность записи и обязательный тюнинг против простоты, zero-copy чтений и единственного писателя. Ни один не «лучше»: они оптимизируют разные вершины треугольника чтение–запись–место.
• etcd — хранилище решений, а не данных. Линеаризуемость через Raft стоит fsync плюс кворум на каждую запись; отсюда все ограничения — 8 ГБ, 1.5 МБ на запрос, тысячи записей в секунду. Компакция и дефрагментация — обязательный регламент, а не опция.
• Index-free adjacency — единственное настоящее преимущество графовых БД: переход по ребру стоит O(1) и не зависит от размера базы. Оно работает, только пока граф помещается в page cache, и ломается о суперузлы.
• Порог целесообразности графа — глубина обхода. До двух уровней PostgreSQL с покрывающим индексом конкурентоспособен. От трёх и глубже, а также для путей переменной длины, разрыв становится качественным.
• Вершиной делайте то, через что обходите. Всё остальное — свойство. Это правило предотвращает большую часть проблем моделирования и производительности.
• Проверяйте лицензии до пилота: Neo4j Community — GPLv3 без кластера и онлайн-бэкапа, ArangoDB и Memgraph — BUSL. Архитектурное решение, принятое на бесплатной редакции, легко становится счётом на пятизначную сумму.

Источники

• Siying Dong et al., «RocksDB: Evolution of Development Priorities in Key-Value Stores Serving Large-Scale Applications», ACM ToS 2021 — как менялись приоритеты движка под реальной нагрузкой Facebook.
• RocksDB Wiki — особенно разделы Tuning Guide, Write Stalls и Compaction.
• Howard Chu, «LMDB: The Lightning Memory-mapped Database» и техническая документация LMDB.
• Lu, Pillai, Arpaci-Dusseau, «WiscKey: Separating Keys from Values in SSD-conscious Storage», FAST 2016 — основа BadgerDB.
• Athanassoulis et al., «Designing Access Methods: The RUM Conjecture», EDBT 2016.
• Ongaro, Ousterhout, «In Search of an Understandable Consensus Algorithm (Raft)», USENIX ATC 2014.
• etcd Documentation — разделы Performance, Maintenance и API guarantees.
• Kyle Kingsbury, «Jepsen: etcd 3.4.3», «Jepsen: Dgraph 1.1.1» — экспериментальная проверка заявленных гарантий.
• Ian Robinson, Jim Webber, Emil Eifrem, «Graph Databases», 2nd ed. — глава 6 про физическое устройство хранения Neo4j.
• Neo4j Cypher Manual и Operations Manual — конфигурация памяти, планы, кластеризация.
• ISO/IEC 39075:2024 Information technology — Database languages — GQL — первый стандарт графового языка запросов.
• Bronson et al., «TAO: Facebook’s Distributed Data Store for the Social Graph», USENIX ATC 2013 — крупнейший соцграф на MySQL.
• Apache AGE и PostgreSQL: WITH Queries (Recursive) — граф без второй СУБД.
• Martin Kleppmann, «Designing Data-Intensive Applications», глава 2 (графовые модели данных) и глава 3 (LSM против B-tree).

Что дальше

Мы прошли крайности: движки, у которых нет ничего, кроме ключа и значения, и модель, где связь важнее сущности. Осталась категория, которая пытается не выбирать между полноценным SQL с ACID и горизонтальным масштабированием, — и строит распределённые транзакции поверх тех самых упорядоченных key-value-движков, что мы разбирали в первой части: NewSQL и распределённые БД: CockroachDB, YugabyteDB, TiDB, Spanner.