Социальный граф

Кейс разделяет каноническое состояние отношений, асинхронные adjacency-проекции, кэш чтения и offline-кандидатов для рекомендаций. Это важно: одна «дружба» не должна атомарно записываться в два разных шарда без распределённой транзакции.

Модель отношений

Для симметричной дружбы канонический ключ — упорядоченная пара min(user_a,user_b), max(user_a,user_b). Транзакция сохраняет одно состояние пары, версию, request id и outbox row. Так принятие или блокировка имеют один источник истины.

Projection Worker идемпотентно строит две направленные записи adjacency: A → B и B → A. Эти записи могут находиться на разных шардах и обновляются асинхронно. Поэтому ответ «accepted» означает durable canonical commit, а не мгновенную готовность всех проекций. Read-your-write достигается overlay недавней канонической мутации или ожиданием нужной projection version.

Направление репликации

Read replica подключается к source и получает binlog, поэтому физические рёбра направлены replica → primary. Анимация primary → replica идёт по тому же ребру в обратном направлении. Реплика может отставать; критический block-check не должен полагаться только на неё.

Масштаб чтения и кэш

Если учебное допущение равно 100 млн graph reads/с, то даже 99% hit rate оставляет 1 млн cache misses/с. Это полноценная нагрузка на storage, а не «почти ноль». Нужны:

• request coalescing или lease для одинаковых cache fills;
• versioned keys и контролируемая invalidation;
• отрицательный кэш с коротким TTL только там, где он не ослабляет privacy;
• лимиты fan-out, page size, CPU и deadline.

TAO — read-optimized graph abstraction поверх sharded MySQL и cache. Публикация TAO прямо описывает приоритет availability и per-machine efficiency над строгой consistency; поэтому сильные инварианты дружбы и блокировки здесь вынесены в Canonical Pair Store.

Высокая степень вершины

Шардирование только по celebrity id создаёт один горячий раздел. High-degree adjacency разбивается на детерминированные buckets, например hash(other_user_id) mod N. Страница собирается из ограниченного числа bucket heads.

OFFSET для десятков миллионов рёбер заставляет пропускать всё больше строк и нестабилен при конкурентных вставках. Используется keyset cursor по created_at + edge_id; cursor также несёт projection version, чтобы клиент понимал консистентность страниц.

Друзья друзей и рекомендации

Точный online-обход не должен взрывать fan-out. Сценарий Friends-of-Friends получает ограниченную первую страницу, затем один batched second-hop read и строгий budget.

PYMK загружает offline-кандидатов и признаки, после чего online удаляет уже существующие отношения, себя и заблокированные пары. Graph embeddings помогают ранжированию, но работа Facebook PBG описывает offline distributed training; её нельзя трактовать как готовый online serving path.

Privacy и block

Block фиксируется в canonical store до подтверждения. Relationship Service синхронно устанавливает tombstone/invalidation для online paths, а durable projector обновляет adjacency. Privacy Gate проверяет authoritative pair state для чувствительных запросов. Если этот check недоступен, ответ fail closed: скрыть данные/кандидата, а не показать потенциально запрещённую связь.

Сценарии

▶Walkthrough: add-friend (not found)

Один canonical commit и две идемпотентные adjacency-проекции.

▶Walkthrough: fof-2hop (not found)

Ограниченный двухшаговый поиск с batch reads и budget.

▶Walkthrough: mutual-friends (not found)

Пересечение двух bounded adjacency pages после privacy-проверки.

▶Walkthrough: pymk (not found)

Offline candidates и embeddings плюс свежие online-фильтры.

▶Walkthrough: hot-celebrity (not found)

Bucketed high-degree storage и keyset pagination.

▶Walkthrough: block (not found)

Authoritative block, синхронная invalidation и fail-closed чтение.

Наблюдаемость

• projection lag и доля read-your-write overlays;
• cache hit rate вместе с абсолютным miss QPS;
• lease/coalescing effectiveness и stampede rate;
• p95/p99 latency по размеру degree;
• число privacy fail-closed, stale replica reads и blocked-candidate removals;
• skew по shard и bucket.

Связанные материалы

[CONCEPT]neo4j-graph-db [CONCEPT]sharding-strategies [CONCEPT]caching-patterns [CONCEPT]multi-region [CONCEPT]consistency-models [CASE]recommendation-system [CASE]news-feed

Event sourcing

Transactional outbox

Первичные источники

• Facebook TAO paper: https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf
• Facebook Memcache paper: https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf
• MySQL replication implementation: https://dev.mysql.com/doc/refman/8.4/en/replication-implementation.html
• PyTorch-BigGraph paper: https://arxiv.org/abs/1903.12287