Xu dedicated ch. 11 to this topic. Kleppman also discusses it in his first chapter (on pps. 34-5).
The trick here is to recognize that there is a many-to-many problem: you need all your followers to receive your posts, and your followers follow many people. They both refer to this process as fan-out. There are two broad approaches:
- Fan-out on read: Publish all posts to a global data store; query by neighbors.
- Fan-out on write: Maintain a per-user cache of followed content.
The first approach involves an O(1) write, but reads can be very demanding. The second switches this around. Per Kleppman, Twitter used the first approach originally, then switched to the second. However, when a celebrity has millions of followers, every post gets sent to millions of timelines. So they switched to a hybrid approach. (This can be seen as a partition skew problem.)
A graph database is used to keep track of which users should receive the message. Xu also proposes using a resilient cache (such as Redis) to materialize counts of likes, followers, etc.
Of course, with so many different representations of the data, coordination becomes a major concern. Xu puts a message queue before the fan-out, but puts fetching the list of friends before it:
flowchart TD A[Tweet] --> B[Follower graph] B --> C[Per-follower cache] A --> D[Message bus] D --> E[Global store]
But I think you really need a persistent event log that acts as the source of truth:
flowchart TD A[Tweet] --> X[Event log] X --> B[Follower graph] B --> C[Per-follower cache] X --> E[Global store]