System Design Cases
Social Graph (LinkedIn / Facebook TAO)
Social Graph (LinkedIn / Facebook TAO) — 1B users, 200B+ edges. Sharded MySQL adjacency (objects+assoc tables, sharded by id1) behind a stateless TAO-style cache tier (Memcached, 99% hit). Two ADRs: graph DB vs sharded SQL adjacency, and cache strategy for hot edges (celebrities). 5 scenarios: add friend (bidirectional write + invalidate), friends-of-friends 2-hop (scatter-gather), mutual friends (sorted-list intersection), PYMK (2-hop + ML rerank via PyTorch BigGraph), hot celebrity read (pre-sharded follower list with leases).
Социальный граф
Кейс разделяет каноническое состояние отношений, асинхронные 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: скрыть данные/кандидата, а не показать потенциально запрещённую связь.
Сценарии
Один canonical commit и две идемпотентные adjacency-проекции.
Ограниченный двухшаговый поиск с batch reads и budget.
Пересечение двух bounded adjacency pages после privacy-проверки.
Offline candidates и embeddings плюс свежие online-фильтры.
Bucketed high-degree storage и keyset pagination.
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Первичные источники
- 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