Designing a Social Graph: Storage Models, Traversal Queries, and Mutual Connection Discovery at Scale

Every social product rests on a graph. Users are nodes. Follow relationships, friendships, and blocks are edges. When the graph is small, none of the design decisions feel consequential. At a few thousand users you can JOIN the follows table twice and get mutual friends in under a millisecond. At a few million users those queries turn into table scans that cascade across your read replicas. At hundreds of millions, the graph itself becomes one of the most expensive data structures you operate.

This article is about the graph layer specifically: how you store it, how you query it, how you cache the hot paths, and what happens downstream when graph writes propagate into feeds and notifications. The feed layer is a separate design problem covered elsewhere. This focuses on the relationship data itself.

What the Social Graph Actually Stores

Before picking a storage model, get precise about the data. A social graph holds:

• Edges with direction: user A follows user B is not the same as user B follows user A. Twitter/X, Instagram, and LinkedIn (connections) all have subtly different semantics.
• Edge metadata: when the relationship was created, whether it is pending (friend request sent but not accepted), muted, or a close-friends qualifier.
• Derived counts: follower count, following count, mutual friend count. These are computed from edges but almost always cached separately for read performance.
• Negative edges: blocks and mutes. These are first-class relationships that must propagate into every downstream query.

The distinction between unidirectional and bidirectional edges shapes every design decision that follows.

Unidirectional Edges (Follow Model)

A follows B does not imply B follows A. Two separate rows exist in the edge table. Twitter, Instagram, and Substack use this model. The data model is simple: a single directed edge (follower_id, followee_id). Querying followers and following are symmetric: one index per direction.

Bidirectional Edges (Friend Model)

Both parties must consent. A friend request from A to B creates a pending edge. Acceptance materializes a confirmed relationship. You can store this as two directed rows (canonical) or as a single row with a normalized key (canonical user_id_a < user_id_b by convention). Facebook, LinkedIn connections, and Snapchat friendships use this model.

The two-directed-rows approach simplifies read queries at the cost of write-time coordination. The single-row approach simplifies storage but complicates every query that needs to look up “everyone connected to user A” because the user could appear in either the user_a or user_b column.

Use two directed rows. The storage cost is negligible and the query simplicity is worth it.

Relational Storage: The Adjacency List

A PostgreSQL adjacency list is the right starting point for any social graph under roughly 100M edges. The schema is minimal:

// Schema representation — executed via your migration tool of choice
const schema = `
  CREATE TABLE edges (
    follower_id  BIGINT NOT NULL,
    followee_id  BIGINT NOT NULL,
    created_at   TIMESTAMPTZ NOT NULL DEFAULT now(),
    status       TEXT NOT NULL DEFAULT 'active',  -- active | pending | muted | blocked
    PRIMARY KEY (follower_id, followee_id)
  );

  CREATE INDEX edges_followee_idx ON edges (followee_id, follower_id);
`;

Two indexes: the primary key covers (follower_id, followee_id) for “who does this user follow” queries. The secondary index covers (followee_id, follower_id) for “who follows this user” queries. Both are range scans on a B-tree, which performs well until the index no longer fits in memory.

Follower and following counts should never be computed from the live table on read. Maintain them in a separate counters table and update them transactionally alongside edge inserts and deletes:

async function followUser(
  followerId: bigint,
  followeeId: bigint,
  db: DatabaseClient
): Promise<void> {
  await db.transaction(async (tx) => {
    await tx.query(
      `INSERT INTO edges (follower_id, followee_id)
       VALUES ($1, $2)
       ON CONFLICT DO NOTHING`,
      [followerId, followeeId]
    );

    // Increment counters atomically with the edge insert
    await tx.query(
      `INSERT INTO user_counts (user_id, following_count, follower_count)
       VALUES ($1, 1, 0), ($2, 0, 1)
       ON CONFLICT (user_id) DO UPDATE SET
         following_count = user_counts.following_count + EXCLUDED.following_count,
         follower_count  = user_counts.follower_count  + EXCLUDED.follower_count`,
      [followerId, followeeId]
    );
  });
}

This keeps counts consistent without expensive COUNT(*) queries. The tradeoff is that counter rows become hot under high write throughput. Partition counter updates through a queue if the write rate saturates the row lock.

Mutual Friend Queries in SQL

Finding mutual connections between two users is the canonical hard query on an adjacency list. The naive approach is an intersection:

-- Mutual followers between user A and user B
SELECT e1.followee_id
FROM edges e1
JOIN edges e2 ON e1.followee_id = e2.followee_id
WHERE e1.follower_id = $user_a
  AND e2.follower_id = $user_b
  AND e1.status = 'active'
  AND e2.status = 'active';

This works but scans both users’ following lists in full and then hashes or sorts to find the intersection. At moderate follow counts (a few thousand each) it is fast. At high follow counts it becomes expensive, and at celebrity-level follow counts it is unusable.

Two optimizations matter in practice. First, intersect in the application layer using sets rather than relying on the database join when both users’ following lists are small enough to be cached:

async function getMutualFollows(
  userA: bigint,
  userB: bigint,
  db: DatabaseClient
): Promise<bigint[]> {
  // Fetch both following lists, limit to a reasonable cap for UX purposes
  const [followingA, followingB] = await Promise.all([
    db.query<{ followee_id: bigint }>(
      `SELECT followee_id FROM edges WHERE follower_id = $1 AND status = 'active' LIMIT 5000`,
      [userA]
    ),
    db.query<{ followee_id: bigint }>(
      `SELECT followee_id FROM edges WHERE follower_id = $1 AND status = 'active' LIMIT 5000`,
      [userB]
    ),
  ]);

  const setA = new Set(followingA.map((r) => r.followee_id));
  return followingB
    .map((r) => r.followee_id)
    .filter((id) => setA.has(id));
}

Second, for “people you may know” features that require friend-of-friend traversal, avoid computing it on demand entirely. Pre-compute and cache it. More on that below.

Graph Databases: When to Consider Them

Graph databases (Neo4j, Amazon Neptune, TigerGraph) are optimized for traversal. Their internal adjacency list representation stores edges as direct pointers to neighboring nodes, so a two-hop traversal does not require index lookups per hop the way a relational join does. This property is called index-free adjacency.

The practical advantage shows up at three or more hops. Querying “all users within 3 degrees of separation” on a billion-node graph is infeasible in SQL and tractable in a graph database. The Cypher query for friends-of-friends looks like this:

MATCH (a:User {id: $userId})-[:FOLLOWS*2]->(fof:User)
WHERE NOT (a)-[:FOLLOWS]->(fof)
  AND fof.id <> $userId
RETURN fof.id, count(*) AS mutual_count
ORDER BY mutual_count DESC
LIMIT 100

The *2 notation expresses variable-depth traversal. In relational SQL this would require two explicit self-joins with deduplication logic.

The cost of adopting a graph database is operational: a separate system to operate, replicate, back up, and monitor. Most social products do not need full graph traversal at query time. LinkedIn and Facebook built their own custom graph stores (Tao at Facebook, Espresso at LinkedIn) because neither PostgreSQL nor off-the-shelf graph databases matched their access patterns at scale. For most products, a relational adjacency list with smart caching covers 95% of use cases.

Caching Hot Paths

The graph has a small number of extremely hot query paths:

1. “Is user A following user B?” (rendered on every profile page)
2. “How many followers does user X have?” (rendered on every profile page)
3. “Who are the mutual connections between A and B?” (rendered on connection UIs)
4. “Who should we suggest to user A?” (people you may know)

Each has a different caching strategy.

Edge Existence Checks

Cache individual edge existence in Redis as a bit or string with a short TTL:

async function isFollowing(
  followerId: bigint,
  followeeId: bigint,
  redis: RedisClient,
  db: DatabaseClient
): Promise<boolean> {
  const cacheKey = `edge:${followerId}:${followeeId}`;
  const cached = await redis.get(cacheKey);

  if (cached !== null) return cached === '1';

  const result = await db.query<{ exists: boolean }>(
    `SELECT EXISTS(
       SELECT 1 FROM edges
       WHERE follower_id = $1 AND followee_id = $2 AND status = 'active'
     ) AS exists`,
    [followerId, followeeId]
  );

  const exists = result[0].exists;
  await redis.set(cacheKey, exists ? '1' : '0', { ex: 300 }); // 5-minute TTL
  return exists;
}

On unfollow, invalidate the cache key. Stale reads for 5 minutes are acceptable on most UIs. Adjust TTL based on your consistency requirements.

Follower Count Caching

Read from the counters table, cache in Redis with an invalidation on every follow/unfollow. For very high-follower accounts, accept approximate counts: maintain the counter in Redis directly and periodically reconcile with the source of truth.

async function getFollowerCount(
  userId: bigint,
  redis: RedisClient,
  db: DatabaseClient
): Promise<number> {
  const cacheKey = `follower_count:${userId}`;
  const cached = await redis.get(cacheKey);

  if (cached !== null) return parseInt(cached, 10);

  const result = await db.query<{ follower_count: number }>(
    `SELECT follower_count FROM user_counts WHERE user_id = $1`,
    [userId]
  );

  const count = result[0]?.follower_count ?? 0;
  await redis.set(cacheKey, count.toString(), { ex: 60 });
  return count;
}

People You May Know: Pre-Computed Suggestions

Friend-of-friend recommendations are the most expensive graph query. Computing them at request time is impractical beyond a few thousand users. The production pattern is offline pre-computation on a cadence (hourly or daily depending on graph mutation rate), with results stored per user in Redis or a key-value store.

The computation logic: for each user A, fetch A’s following list, then fetch each followee’s following list, aggregate scores by how many mutual connections exist, filter out users A already follows and A themselves, and rank by mutual count.

interface Suggestion {
  userId: bigint;
  mutualCount: number;
  mutualIds: bigint[];
}

async function computeSuggestions(
  userId: bigint,
  db: DatabaseClient
): Promise<Suggestion[]> {
  // Step 1: get user's following set
  const following = await db.query<{ followee_id: bigint }>(
    `SELECT followee_id FROM edges WHERE follower_id = $1 AND status = 'active'`,
    [userId]
  );
  const followingSet = new Set(following.map((r) => r.followee_id));
  followingSet.add(userId); // exclude self

  // Step 2: get second-degree connections with mutual count
  const fof = await db.query<{ candidate_id: bigint; bridge_id: bigint }>(
    `SELECT e2.followee_id AS candidate_id, e1.followee_id AS bridge_id
     FROM edges e1
     JOIN edges e2 ON e1.followee_id = e2.follower_id
     WHERE e1.follower_id = $1
       AND e1.status = 'active'
       AND e2.status = 'active'
       AND e2.followee_id != ALL($2::bigint[])`,
    [userId, Array.from(followingSet)]
  );

  // Step 3: aggregate by candidate
  const scores = new Map<bigint, { count: number; bridges: bigint[] }>();
  for (const row of fof) {
    const entry = scores.get(row.candidate_id) ?? { count: 0, bridges: [] };
    entry.count += 1;
    entry.bridges.push(row.bridge_id);
    scores.set(row.candidate_id, entry);
  }

  return Array.from(scores.entries())
    .map(([userId, { count, bridges }]) => ({
      userId,
      mutualCount: count,
      mutualIds: bridges.slice(0, 3), // show up to 3 mutual names in UI
    }))
    .sort((a, b) => b.mutualCount - a.mutualCount)
    .slice(0, 50);
}

Run this as a background job per user, write results to Redis with a 24-hour TTL, and serve suggestions from cache. Re-run when a user follows someone new, since that changes the second-degree neighborhood.

Fan-Out Implications for Downstream Systems

The social graph is not an isolated data store. It is the dependency that feeds and notification systems query on every write.

When a user posts, the feed system needs their follower list. When a user comments, the notification system needs to check relationships (is the post author following the commenter? do they have notifications enabled for this person?). Every graph read that happens in a hot write path is a latency risk.

Denormalize Follower Lists for High-Fan-Out Accounts

For accounts with more than a threshold follower count (commonly 10,000 to 1M depending on your scale), maintain a pre-fetched follower snapshot in a distributed store. The feed system reads from this snapshot rather than querying the edges table directly.

const HIGH_FOLLOWER_THRESHOLD = 10_000;

async function getFollowerIdsForFanOut(
  userId: bigint,
  redis: RedisClient,
  db: DatabaseClient
): Promise<bigint[]> {
  const cacheKey = `followers:${userId}`;

  // For high-follower accounts, serve from a cached set
  const cachedCount = await redis.scard(cacheKey);
  if (cachedCount > 0) {
    const members = await redis.smembers(cacheKey);
    return members.map(BigInt);
  }

  const followers = await db.query<{ follower_id: bigint }>(
    `SELECT follower_id FROM edges WHERE followee_id = $1 AND status = 'active'`,
    [userId]
  );

  const ids = followers.map((r) => r.follower_id);

  if (ids.length >= HIGH_FOLLOWER_THRESHOLD) {
    const pipeline = redis.pipeline();
    pipeline.sadd(cacheKey, ...ids.map(String));
    pipeline.expire(cacheKey, 300); // 5-minute TTL
    await pipeline.exec();
  }

  return ids;
}

Invalidate the follower set cache on every follow and unfollow targeting that account. For accounts at the extreme end (millions of followers), accept a bounded staleness window and rely on periodic reconciliation.

Block and Mute Propagation

Blocks must propagate into every downstream system synchronously. A blocked user must not see the blocker’s content in their feed and must not receive notifications from the blocker. This is typically implemented as a bloom filter or a Redis set per user that downstream systems check before including content.

async function isBlocked(
  viewerId: bigint,
  contentOwnerId: bigint,
  redis: RedisClient
): Promise<boolean> {
  // Check both directions: viewer blocked by owner, or viewer blocked owner
  const [blockedByOwner, blockedOwner] = await Promise.all([
    redis.sismember(`blocks:${contentOwnerId}`, viewerId.toString()),
    redis.sismember(`blocks:${viewerId}`, contentOwnerId.toString()),
  ]);
  return blockedByOwner === 1 || blockedOwner === 1;
}

Populate these sets on block creation and invalidate on unblock. A bloom filter can replace the Redis set for very large block lists, accepting a small false-positive rate (showing no content when a block does not exist) in exchange for memory efficiency.

Tradeoffs Table

Dimension	Relational adjacency list	Graph database	Custom in-memory store
Multi-hop traversal	Poor beyond 2 hops	Native, efficient	Excellent (if fits in memory)
Operational complexity	Low	Medium-high	Very high
Mutual friend query	Requires join or app-layer intersection	Native, fast	Native, fast
Consistency model	Strong (ACID)	Varies by vendor	Eventual
Storage efficiency	Good	Higher overhead per edge	Depends on implementation
Scaling approach	Read replicas, sharding	Horizontal sharding	Custom partitioning
Query language	SQL	Cypher/Gremlin	Custom API
Best fit	Most products under 500M edges	Complex traversal requirements	Web-scale with dedicated teams

Production Considerations

Sharding the edge table. A single-node PostgreSQL instance can comfortably hold a few hundred million edges with proper indexing. Beyond that, shard by follower_id using hash sharding. The downside: “who follows user X” queries fan out across all shards. Mitigate by maintaining a separate followee_shard table that maps followee_id to the shards holding their follower rows.

Soft deletes vs hard deletes. When a user unfollows, hard-deleting the edge row is simpler but loses history. Soft deletes (setting status = 'unfollowed') preserve analytics data (how many people unfollowed after a specific event) but inflate the table. Most products use hard deletes for follows and soft deletes (with a TTL cleanup job) for friend requests.

Consistency windows on counts. If you update follower counts in a separate transaction from the edge insert, a crash between the two leaves counts stale. Use transactional outbox pattern: write edge and count delta to the same transaction, then apply the count update asynchronously from the outbox. Reconcile counts nightly against a COUNT(*) aggregate.

Graph mutation rate and cache TTLs. At low user counts, short cache TTLs are fine because the database can handle the miss rate. As user count grows, the graph mutation rate (follows per second) increases, and cache invalidation becomes a thundering herd problem if many caches expire simultaneously. Stagger TTLs with a random jitter of 10-30% of the base TTL to distribute cache misses across time.

Auditing edge changes. Relationship changes (follows, unfollows, blocks) are security-relevant events. Log them to an append-only audit table or stream them to a Kafka topic for downstream compliance and safety systems. Never silently drop an edge mutation.

Testing at graph scale. Generating a realistic social graph for load testing is harder than it looks. Real social graphs follow a power-law degree distribution: most users have few connections, a small number have enormous connection counts. A uniform random graph does not stress the same code paths. Use a preferential attachment algorithm to generate synthetic graphs that match real-world degree distributions before running load tests.

The social graph looks like a solved problem until you start hitting the edges of what a naive relational schema can do. The relational adjacency list gets you further than most teams expect. The key is knowing which queries to push into pre-computation versus which to serve live, and making that decision before the graph is large enough to make the wrong answer painful.