Social graph follows and FlockDB
Ada follows Bo. Opening Ada's following list asks for edges leaving Ada; publishing Bo's post asks for edges entering Bo. The relationship is the same, but the two reads need different access paths.
Most follow-graph work is shallow: test one relationship, list neighbors, page through followers, or count them. Start with those operations. A graph-shaped data model does not automatically require arbitrary graph traversal.
Store the direction, then the relationship rule
The previous model uses (follower, followee) as a unique pair. A mutual friendship would need a different acceptance rule or two confirmed directions. A reverse lookup for Ada following Bo is not a second friendship and does not mean Bo follows Ada.
A broader relations(source, type, target, state, position) model can support follows, blocks or mutes when their storage needs are shared. Include the type in relationship identity. Keep each type's permissions and state transitions explicit: a pending follow request and an active block are not interchangeable just because both connect accounts.
A sort position supports ordered listing. State can distinguish active, removed or archived edges. Extra metadata belongs to the relationship it describes; it should not turn every pair into an unvalidated bag of unrelated values.
Why the reverse lookup changes after sharding
On one database, a forward index on (follower, followee) and a reverse index on (followee, follower) can serve both reads. The database maintains the indexes when a row changes.
Now partition the rows by follower. Ada's outgoing list stays on Ada's partition. Bo's followers can be spread across all the other users' partitions. A local index on followee helps inside each partition, but does not tell the router which partitions contain Bo's incoming edges.
A separately placed reverse list solves that routing problem. The forward entry is grouped by Ada, and its reverse entry is grouped by Bo.
contains Bo] R --> B[Follower list
contains Ada]
If Bo also follows Ada, that is a second logical relationship with its own forward and reverse entries: four entries for two follows. The cost is two logical entries per relationship before indexes and replication, plus the work of keeping them consistent. It is not a universal two-times storage estimate.
What FlockDB chose
Twitter's 2010 FlockDB design used MySQL-backed adjacency lists, indexed and partitioned in both directions. It targeted large neighbor lists, ordered pagination and set operations rather than multi-hop graph walks. Its position field supported ordered reads; removed and archived states let it retain edges without exposing them as active follows.
That design also accepted retried and out-of-order writes using operation ordering. It did not make an arbitrary pair of remote database writes into a single SQLite transaction. The archived repository is no longer maintained; this is a historical design to understand, not a current package recommendation.
The useful distinction survives the implementation: listing direct followers is different work from finding paths, communities or recommendations across many hops. Choose an online adjacency service and an offline graph-analysis pipeline according to the queries each must answer.
Keep the two representations consistent
Our social example, with its shared helpers, deliberately stores two tables in one SQLite database. One transaction writes the forward row, reverse row and operation receipt. An exception between the row writes rolls everything back. This exposes the maintenance obligation without pretending to implement distributed FlockDB.
The six-account graph starts with Ada and Dee following Bo and Cy, plus Eli and Fay following Cy. The replay interrupts Eli's new follow of Bo, retries it, and then unfollows. A delayed retry of the old follow returns its historical receipt without restoring the edge.
python3 m22-social.py graphAda follows: Bo,Cy
Cy followers: Ada,Dee,Eli,Fay
interrupted Eli->Bo: forward=False reverse=False
retry committed: {"accepted_state":true,"duplicate":true}
delayed old follow: current=False
absent unfollow: {"accepted_state":false,"duplicate":false}
changed operation: 409
committed forward/reverse pairs: 6 6The successful retry is repeated before printing, hence duplicate:true. Reusing its operation identity with different input returns conflict. The receipt describes an accepted operation; the current adjacency list describes the relationship now. The final check compares complete forward and reverse pair sets, not just equal counts.
Across independent stores, choose a consistency and recovery contract. A reverse projection updated asynchronously needs retained changes, duplicate handling, an applied position and repair. If it drives delivery, lag can omit recipients. A cached follower count cannot reconstruct who is missing.
Page by a stable boundary
Offset pagination repeatedly skips earlier rows. An indexed cursor can seek to the last returned ordering key instead. Include a tie-breaker: several follows can share one timestamp.
For a relational extension with non-null created_at and a unique (followee, follower) pair, use an index beginning with (followee, created_at DESC, follower DESC). After returning the row at (100, 'Eli'), the next-page query is:
SELECT follower, created_at
FROM follows_by_time
WHERE followee = :author
AND (created_at, follower) < (:last_time, :last_id)
ORDER BY created_at DESC, follower DESC
LIMIT :page_size;This is a proposed time-ordered table, separate from the example's alphabetically sorted lists. If Cy's followers sort as Fay@100, Eli@100, Dee@99, Ada@99, a two-row first page ends at (100, 'Eli'); the next page returns Dee and Ada. A one-row page ending at (100, 'Fay') still reaches Eli because the ID breaks the timestamp tie.
Keyset pagination avoids deep offset scans when an appropriate index is used. It does not freeze a changing graph. If an edge is removed or its sort position changes between requests, define whether the caller accepts a live list or needs a versioned snapshot. The cursor must also belong to the requested account and relationship type.
Handle a very large follower list deliberately
A single popular account can dominate one reverse partition. Isolating it protects other accounts, but does not divide its own workload. Bucketing that list spreads storage and writes; reads now need to merge ordered bucket pages and carry enough cursor state to resume them.
Cache frequently read first pages when their freshness policy permits it. Separate an approximate public count from exact edge membership, and batch recipient enumeration for downstream delivery. Preserve current access rules when a cached list is used for a protected action.
Once outgoing and incoming relationships have clear meanings, the feed-generation comparison can decide whether to write feed references when a post appears or collect posts when a reader opens the page.
Managing the Follower Graph
The "social graph" is the mapping of relationships between users. In systems like Twitter or Instagram, this is a directed graph (User A follows User B, but B might not follow A). Managing this graph efficiently is crucial because every feed generation relies on knowing who a user follows.
The Twitter Approach: FlockDB
Twitter famously built FlockDB to handle their social graph. Rather than a complex traversal-focused graph database (like Neo4j), FlockDB is essentially a highly optimized, distributed adjacency list stored on MySQL shards managed by Twitter's Gizzard sharding framework.
Adjacency Lists in SQL
The core concept is storing directed edges in simple tables. An edge table has three main columns: source_id, destination_id, and state (active, blocked, etc.).
To find who User 1 follows: SELECT destination_id FROM edges WHERE source_id = 1.
To find User 1's followers: SELECT source_id FROM edges WHERE destination_id = 1.
Sharding the Graph
Because the graph is too large for one machine, it must be sharded. FlockDB maintained indexed adjacency lists in both directions. A forward representation grouped by source_id serves outgoing edges, while a reverse representation grouped by destination serves incoming edges; keeping both paths consistent requires ordered, retry-safe updates and repair. Because the forward copy is sharded by source and the backward copy by destination, both "Who do I follow?" and "Who follows me?" are single-shard lookups. A design that stores each edge only once, sharded by source_id, would make "Who follows me?" a scatter-gather query, which is exactly why FlockDB keeps the second, destination-sharded copy.
Worked example: how big is the graph?
Assume 400 million users following an average of 200 accounts: 80 billion logical edges. Storing both directions gives 160 billion rows. With two 8-byte IDs plus an 8-byte position or timestamp and a state byte, a row is about 25 bytes raw, so roughly 4 TB of raw data; index and storage-engine overhead typically multiply that by 2 to 3, landing around 10 TB before replication. With three replicas that is about 30 TB, easily spread over a few hundred MySQL shards.
Operations and their cost
| Operation | Served by | Cost | Notes |
|---|---|---|---|
| Who does A follow? (page of 100) | Forward list, shard of A | One indexed range read | Used by pull-based feeds |
| Who follows B? (page of 100) | Reverse list, shard of B | One indexed range read | Used by push fan-out; huge for celebrities |
| Does A follow B? | Forward list, shard of A | Point lookup | Used for button state and privacy checks |
| Follower count of B | Denormalized counter | Point lookup | Counting 100M rows per request is not acceptable |
| Mutual follows of A and B | Intersect two forward lists | Two reads plus merge | Cap list sizes or precompute for large accounts |
Write path for a follow
Each edge row carries a state (active, removed, blocked) and a position. An unfollow is a state change with a newer position, so a delayed retry of the original follow cannot resurrect the edge: the store keeps whichever write has the higher position. A background repair job compares forward and reverse lists and fixes drift.
How real systems do it
- FlockDB (Twitter) stored edges as (source, destination, position, state) in MySQL via the Gizzard sharding framework, keeping forward and backward copies so both directions were cheap, and supported set operations like intersection for "who follows both".
- TAO (Facebook) stores associations with an inverse association type; the two directions live on different shards and are written separately, with the inverse write repaired if it fails.
- LinkedIn built dedicated in-memory graph services (most recently LIquid) because degree-of-connection queries need two and three hop answers quickly.