Как устроен Neo4j: property graph, узлы, рёбра и обход без индексов

← назад к разделу

«Друзья друзей моих друзей» в SQL это три соединения таблицы с самой собой, и на четвёртом уровне запрос перестаёт возвращаться. Neo4j хранит данные в виде графа: набор объектов и связей между ними, и переход по связи там стоит одинаково на любом уровне. Это не метафора и не способ нарисовать схему — это буквально то, как данные лежат и как по ним ходят запросы.

Property graph: четыре кирпичика

Модель Neo4j называется property graph («граф со свойствами»), и собирается она из четырёх вещей. Человек, товар, счёт, документ это узел (node), аналог строки таблицы, но без фиксированной схемы. ДРУЖИТ, КУПИЛ, ПЕРЕВЁЛ это ребро (relationship), связь между двумя узлами; у ребра ровно один тип и направление, от одного узла к другому. «Работает в компании с 2019 года в должности инженера»: должность и год живут прямо на ребре, потому что свойства (properties), пары «ключ-значение», есть и у узлов, и у рёбер, а в реляционной базе ради данных на связи пришлось бы заводить отдельную таблицу. И чтобы не искать человека среди всех узлов подряд, узлам дают метки (labels), :Person, :Company: меток у узла может быть несколько, по метке Neo4j понимает, где искать, и к ней чаще всего привязывают индекс. «Чаще всего» потому, что в Neo4j 5 индекс можно завести и на рёбра, и бывает он не только обычным: есть составные, полнотекстовые, точечные (по координатам) и векторные.

Метки бывают только у узлов, тип — только у ребра. Схема при этом не жёсткая: новый вид связи — это рёбра с новым типом, без миграций и перекройки таблиц. Это главная сила модели — лёгкость развития.

Все четыре кирпичика проще увидеть на живом графе, чем перечитать. В учебной песочнице лежит маленький магазин: люди, товары, заказы и знакомства между людьми. Вот узлы с меткой :Person и три их свойства — запустите, а потом замените p.status на p.email:

живой пример

MATCH (p:Person)
RETURN p.firstName, p.lastName, p.status LIMIT 5

А вот ребро целиком, вместе со своим типом: type(r) возвращает тот самый единственный тип, который есть у каждой связи.

живой пример

MATCH (p:Person)-[r:КУПИЛ]->(t:Product)
RETURN p.firstName, type(r), t.title LIMIT 5

Про сами свойства стоит сказать отдельно, потому что здесь ждёт разочарование человека, пришедшего из документных баз. Значение свойства — это скаляр или массив скаляров: число, строка, логическое значение, дата, точка, или массив из них. Вложенных объектов не бывает: {address: {city: "Казань"}} в свойство не положить. Если данные вложенные, они превращаются либо в отдельный узел со связью (правильный ответ в графе — (:Customer)-[:LIVES_AT]->(:Address)), либо в набор плоских свойств (address_city, address_street).

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

Index-free adjacency: почему обход дёшев

Ключевое отличие от реляционной базы — как хранятся связи. В SQL, чтобы пройти от заказа к его позициям, база берёт order_id, идёт в индекс таблицы позиций и ищет там подходящие строки. Поиск по индексу быстрый, но не бесплатный, и он повторяется на каждом шаге связи.

В Neo4j связь — это прямая ссылка: в записи узла лежат ссылки на его рёбра, а в записи ребра — на узлы-концы. Чтобы пройти к соседям, база не ищет ничего в индексе, она идёт по ссылке, как по указателю в структуре данных. Это и есть index-free adjacency («смежность без индексов»): стоимость обхода равна числу пройденных рёбер, а не размеру базы. Друзей друзей находят одинаково быстро и в графе на тысячу узлов, и на миллиард — если у самого человека соседей немного.

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

Цену обхода видно прямо в данных: у узла ровно столько работы, сколько у него рёбер, и размер остального графа на это не влияет.

живой пример

MATCH (p:Person)-[r]->()
RETURN p.firstName, count(r) AS рёбер
ORDER BY рёбер DESC LIMIT 5

Тот же счёт в маленькой программе — списки смежности против отсортированной таблицы связей:

import java.util.*;

public class FriendsOfFriends {
    static int hops, compares;

    static List<String> byLink(Map<String, List<String>> graph, String who) {
        List<String> next = graph.getOrDefault(who, List.of());
        hops += next.size();
        return next;
    }

    static List<String> byIndex(List<String[]> rows, String who) {
        int lo = 0, hi = rows.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            compares++;
            if (rows.get(mid)[0].compareTo(who) < 0) lo = mid + 1; else hi = mid - 1;
        }
        List<String> next = new ArrayList<>();
        while (lo < rows.size() && rows.get(lo)[0].equals(who)) next.add(rows.get(lo++)[1]);
        return next;
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = Map.of("Иван", List.of("Пётр", "Анна"),
                "Пётр", List.of("Оля", "Лев"), "Анна", List.of("Дан"));
        List<String[]> rows = new ArrayList<>();
        graph.forEach((a, bs) -> bs.forEach(b -> rows.add(new String[]{a, b})));
        for (int i = 0; i < 100_000; i++) rows.add(new String[]{"user" + i, "x"});
        rows.sort(Comparator.comparing((String[] r) -> r[0]));

        Set<String> links = new LinkedHashSet<>(), index = new LinkedHashSet<>();
        for (String f : byLink(graph, "Иван")) links.addAll(byLink(graph, f));
        for (String f : byIndex(rows, "Иван")) index.addAll(byIndex(rows, f));

        System.out.println("по ссылкам: " + links + ", переходов " + hops);
        System.out.println("по индексу: " + index + ", сравнений " + compares
                + " на " + rows.size() + " строк");
    }
}

package main

import (
	"fmt"
	"sort"
	"strings"
)

var hops, compares int

func byLink(graph map[string][]string, who string) []string {
	next := graph[who]
	hops += len(next)
	return next
}

func byIndex(rows [][2]string, who string) []string {
	lo, hi := 0, len(rows)-1
	for lo <= hi {
		mid := int(uint(lo+hi) >> 1)
		compares++
		if rows[mid][0] < who {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	var next []string
	for lo < len(rows) && rows[lo][0] == who {
		next = append(next, rows[lo][1])
		lo++
	}
	return next
}

func addAll(set []string, items []string) []string {
	for _, item := range items {
		found := false
		for _, s := range set {
			if s == item {
				found = true
				break
			}
		}
		if !found {
			set = append(set, item)
		}
	}
	return set
}

func main() {
	graph := map[string][]string{"Иван": {"Пётр", "Анна"}, "Пётр": {"Оля", "Лев"}, "Анна": {"Дан"}}
	var rows [][2]string
	for _, a := range []string{"Иван", "Пётр", "Анна"} {
		for _, b := range graph[a] {
			rows = append(rows, [2]string{a, b})
		}
	}
	for i := 0; i < 100_000; i++ {
		rows = append(rows, [2]string{fmt.Sprintf("user%d", i), "x"})
	}
	sort.SliceStable(rows, func(i, j int) bool { return rows[i][0] < rows[j][0] })

	var links, index []string
	for _, f := range byLink(graph, "Иван") {
		links = addAll(links, byLink(graph, f))
	}
	for _, f := range byIndex(rows, "Иван") {
		index = addAll(index, byIndex(rows, f))
	}

	fmt.Printf("по ссылкам: [%s], переходов %d\n", strings.Join(links, ", "), hops)
	fmt.Printf("по индексу: [%s], сравнений %d на %d строк\n", strings.Join(index, ", "), compares, len(rows))
}

let hops = 0, compares = 0;

function byLink(graph, who) {
  const next = graph.get(who) ?? [];
  hops += next.length;
  return next;
}

function byIndex(rows, who) {
  let lo = 0, hi = rows.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    compares++;
    if (rows[mid][0] < who) lo = mid + 1; else hi = mid - 1;
  }
  const next = [];
  while (lo < rows.length && rows[lo][0] === who) next.push(rows[lo++][1]);
  return next;
}

const graph = new Map([['Иван', ['Пётр', 'Анна']], ['Пётр', ['Оля', 'Лев']], ['Анна', ['Дан']]]);
const rows = [];
for (const [a, bs] of graph) for (const b of bs) rows.push([a, b]);
for (let i = 0; i < 100_000; i++) rows.push([`user${i}`, 'x']);
rows.sort((r1, r2) => (r1[0] < r2[0] ? -1 : r1[0] > r2[0] ? 1 : 0));

const links = new Set(), index = new Set();
for (const f of byLink(graph, 'Иван')) for (const n of byLink(graph, f)) links.add(n);
for (const f of byIndex(rows, 'Иван')) for (const n of byIndex(rows, f)) index.add(n);

console.log(`по ссылкам: [${[...links].join(', ')}], переходов ${hops}`);
console.log(`по индексу: [${[...index].join(', ')}], сравнений ${compares} на ${rows.length} строк`);

hops = compares = 0


def by_link(graph: dict[str, list[str]], who: str) -> list[str]:
    global hops
    nxt = graph.get(who, [])
    hops += len(nxt)
    return nxt


def by_index(rows: list[tuple[str, str]], who: str) -> list[str]:
    global compares
    lo, hi = 0, len(rows) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        compares += 1
        if rows[mid][0] < who:
            lo = mid + 1
        else:
            hi = mid - 1
    nxt = []
    while lo < len(rows) and rows[lo][0] == who:
        nxt.append(rows[lo][1])
        lo += 1
    return nxt


graph = {"Иван": ["Пётр", "Анна"], "Пётр": ["Оля", "Лев"], "Анна": ["Дан"]}
rows = [(a, b) for a, bs in graph.items() for b in bs]
rows += [(f"user{i}", "x") for i in range(100_000)]
rows.sort(key=lambda r: r[0])

links: dict[str, None] = {}
index: dict[str, None] = {}
for f in by_link(graph, "Иван"):
    links.update(dict.fromkeys(by_link(graph, f)))
for f in by_index(rows, "Иван"):
    index.update(dict.fromkeys(by_index(rows, f)))

print(f"по ссылкам: [{', '.join(links)}], переходов {hops}")
print(f"по индексу: [{', '.join(index)}], сравнений {compares} на {len(rows)} строк")

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

Сколько это стоит и где кончается дешевизна

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

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

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

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

Чем это отличается от реляционной модели

Сравним на одном вопросе: «есть ли путь от счёта А к счёту Б через цепочку переводов неизвестной длины».

• В SQL это рекурсивный запрос (WITH RECURSIVE) по таблице переводов: JOIN по индексу на каждом шаге, и число шагов в структуре запроса не выражено.
• В Neo4j это один шаблон с переменной длиной пути (-[:ПЕРЕВЁЛ*]->): база идёт по ссылкам от счёта А, пока не упрётся в Б или не кончатся рёбра.

А вот в чём разницы нет: Neo4j — обычная транзакционная база с полноценными ACID-гарантиями, а не «хранилище на итоговой согласованности». Транзакция либо применилась целиком, либо не применилась вовсе — как в PostgreSQL. Цена у этого своя: запись в Neo4j идёт через один узел, и добавлением машин её не разогнать. Масштабируется чтение, запись — нет.

Граф не всегда лучше. Для «выбрать заказы за месяц с суммой больше N» реляционная база быстрее и проще — там нет обхода связей, там фильтр по значениям. Neo4j выигрывает там, где вопрос про связи и их глубину, а не про фильтр по полям.

Где это применяется

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

Где чаще всего ошибаются в модели:

• Путают узел и свойство. Если по значению ищут связи («все, кто в этом городе») — это узел :City, а не строковое свойство city у каждого человека. Свойство читают вместе с узлом, узел — связывает.
• Забывают направление. Оно есть у связи всегда; в запросе её обходят в обе стороны, но при моделировании задают осмысленно: КУПИЛ идёт от человека к товару.
• Ждут, что граф ускорит всё. Фильтры и агрегаты он не ускоряет — там реляционная база быстрее.

Глубже: чем платят за index-free adjacencyрасширенное

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

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

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

Коротко

• Property graph — узлы с метками, рёбра с типом и направлением, свойства и на тех и на других.
• Меток у узла бывает несколько, тип у ребра ровно один; новый вид связи не требует миграции.
• Index-free adjacency: ссылки на рёбра лежат в записи узла, поэтому шаг к соседу — переход по ссылке, а не поиск по индексу.
• Стоимость обхода равна числу пройденных рёбер; в SQL каждый шаг дорожает вместе с таблицей. У узла с десятками тысяч рёбер рёбра разложены по группам (тип и направление), и шаг к соседям чуть дороже.
• Neo4j — транзакционная база с ACID; масштабируется чтение, запись идёт через один узел.
• Индекс нужен для стартового узла обхода, а не чтобы пройти связь.
• Граф выигрывает на связях и их глубине, реляционная база — на фильтрах и агрегатах.
• Свойство — скаляр или массив скаляров; вложенных объектов нет, и вложенность превращается в отдельный узел со связью.
• Дешевизна обхода пропорциональна числу пройденных связей и держится, пока данные в кэше страниц; вход в граф всё равно требует индекса.
• Платит за это запись: связь прошита на обоих концах, массовая загрузка требует отдельного инструмента, а запись масштабируется одной машиной.

Что почитать дальше

• Cypher: язык запросов к графу простыми словами — шаблон связи и путь переменной длины.
• Neo4j: моделирование графа, индексы и эксплуатация — что делать узлом, что свойством, где нужен индекс.
• Графовые данные простыми словами: рекурсивный SQL или графовая СУБД — когда хватает WITH RECURSIVE.
• Графы — список смежности и обходы на обычных коллекциях.