Design X (Twitter): timelines and search

A service like X takes 500 million posts a day and runs four features on that one stream. Home timelines reuse the hybrid fan-outhybrid fan-out: A feed design that pushes the posts of ordinary authors into their followers' inboxes and pulls the posts of the largest accounts when a feed loads, then merges the two by time. More in “Fan-out: push, pull and hybrid timelines” of a news feed: a new post’s id is pushed into the inbox of every active follower, except when the author has a very large following; those posts are pulled and merged in when a timeline is read. Search must find a post seconds after it is written: an indexer reads the same log of new posts, appends each one to an in-memory index segment for the current hour, and readers see it after the next refreshrefresh (search index): The step that makes newly indexed and changed documents visible to search. Elasticsearch refreshes every second by default, so a write becomes searchable at the next refresh, not when it is saved. More in “Inverted indexes, analysers and BM25 ranking”. Replies hang under the post they answer, as a tree whose posts share one conversation id, read a few levels and a page at a time, and trends count terms in sliding windows. This case study sizes each part and follows every path end to end.

Requirements: four features on one stream

Agree on the scope first, because each feature has its own read path:

Functionally, people post, reply, follow, read timelines, search, open conversations and see trends. The non-functional requirements are numbers: a timeline page within 200 ms and a search within 100 ms at the 99th percentile; a new post in followers’ timelines within 5 seconds and in search within 10; and deletes, blocks and protected accounts enforced on every read. Elsewhere availability wins over strict consistency: a timeline a few seconds old is acceptable, an empty one is not.

The estimate: 5,787 posts a second, 1.1 million inbox writes

Two rows shape the design. Fan-out makes 190 inbox writes for every post, so the pull threshold is the main lever on the write path. And a week of posts fits in the memory of a few dozen servers, so search serves recent posts from memory.

API and data model: posts carry their thread’s id

• POST /v1/posts with the text, media ids and an optional reply_to returns the post with its id and conversation id.
• GET /v1/timelines/home?cursor=… returns a page of posts and the next cursor.
• GET /v1/search?q=%23final&order=latest&cursor=… returns matching posts; order=top ranks them.
• GET /v1/conversations/{id}?cursor=… returns a page of a reply tree; GET /v1/trends?region=… returns trends.

Every post carries the id of the post that started its thread. X’s API exposes the same idea: all replies in a thread share a conversation_id, which equals the first post’s own id (X API documentation). Post ids are time-ordered, so a slice of time is a range of ids.

One log feeds four consumers, each at its own offset

The write path. The post service stores the post and appends an event to a partitioned log. Four consumers read that log, each at its own position: a consumer’s position in a partition is a single offsetoffset: The position of a record in a log or a partition: 0 for the first record, then 1, 2 and so on. A reader group's committed offset is the next record it has not processed. More in “Queues, logs and pub-sub: three different tools”, which it can also move back to read again (Kafka documentation). Fan-out workers push the id into active followers’ inboxes unless the author is above the pull threshold. Indexers add the post to the newest search segment. The conversation service files a reply under its parent, and trend counters count its terms. Follow one reply through the log:

The read paths. A home-timeline read takes the reader’s inbox, merges the recent posts of the pulled accounts they follow, fetches the posts in one batch, drops what the reader may not see, and ranks the page. A search goes to every index partition of the newest hours, and a broker merges their best matches. A conversation read takes one page of replies under a parent, a few levels deep. Twitter’s engineers described this search shape for their Earlybird servers: posts arrive from an ingestion pipeline, only the newest of a handful of segments is written, and posts were typically searchable 10 seconds after creation, with queries answered in about 50 ms (Earlybird paper).

The model below sends 12,135 posts through a log into a segmented index and measures how long each waited to become searchable.

# A real-time search index in miniature. Posts reach the indexer through a log, are appended to the active time
# segment, and become searchable at the next refresh. Part 1 measures the visibility delay, from posting to
# searchable, for three refresh intervals. Part 2 runs a newest-first search over the time segments.
# Seeded, so every run prints the same.
import random

RATE = 300  # posts a second
SECONDS = 40
SEGMENT_POSTS = 3_000  # the active segment closes after this many posts
WORDS = ["the", "match", "goal", "rain", "train", "late", "today", "city", "power", "cut", "news", "live",
         "score", "final", "metro", "traffic", "budget", "vote", "film", "song"]
WEIGHTS = [1 / (rank + 1) for rank in range(len(WORDS))]  # a few words are common, most are rare
TAGS = ["#final", "#rain", "#budget", "#metro"]


def make_posts(seed=7):
    """(post id, created at, reaches the indexer at, words), in the order the indexer receives them."""
    rng = random.Random(seed)
    posts, t, post_id = [], 0.0, 100_000
    while True:
        t += rng.expovariate(RATE)
        if t >= SECONDS:
            break
        # Most posts spend 50-400 ms in the log; 1 in 100 waits behind a slow batch for 1.5-3 s.
        lag = rng.uniform(0.05, 0.4) if rng.random() >= 0.01 else rng.uniform(1.5, 3.0)
        words = rng.choices(WORDS, weights=WEIGHTS, k=rng.randint(5, 12))
        if rng.random() < 0.08:
            words.append(rng.choice(TAGS))
        if rng.random() < 0.002:
            words.append("eclipse")  # a rare word
        posts.append((post_id, t, t + lag, words))
        post_id += 1
    return sorted(posts, key=lambda p: p[2])


class Segment:
    """One time partition: append-only postings, and a count of the documents that readers may see."""

    def __init__(self):
        self.docs, self.postings, self.visible = [], {}, 0

    def add(self, post_id, words):
        doc = len(self.docs)
        self.docs.append(post_id)
        for w in set(words):
            self.postings.setdefault(w, []).append(doc)

    def refresh(self):
        self.visible = len(self.docs)  # one number moves: everything appended so far becomes searchable


def build(posts, refresh_every):
    """Index the posts in arrival order; return the segments and when each post became searchable."""
    segments, visible_at = [Segment()], {}
    pending, i, tick = [], 0, refresh_every
    while i < len(posts) or pending:
        while i < len(posts) and posts[i][2] <= tick:
            post_id, _, _, words = posts[i]
            if len(segments[-1].docs) == SEGMENT_POSTS:
                segments[-1].refresh()
                segments.append(Segment())  # roll over: the old segment is read-only from now on
            segments[-1].add(post_id, words)
            pending.append(post_id)
            i += 1
        segments[-1].refresh()
        for post_id in pending:
            visible_at[post_id] = tick
        pending, tick = [], tick + refresh_every
    return segments, visible_at


def pct(sorted_values, p):
    return sorted_values[min(len(sorted_values) - 1, int(p / 100 * len(sorted_values)))]


def newest(segments, term, k):
    """The k newest searchable posts with the term, newest first; and how much of the index was read."""
    hits, touched, visited = [], 0, 0
    for seg in reversed(segments):
        visited += 1
        for doc in reversed(seg.postings.get(term, [])):
            if doc >= seg.visible:
                continue  # appended after the last refresh: not searchable yet
            touched += 1
            hits.append(seg.docs[doc])
            if len(hits) == k:
                return hits, touched, visited
    return hits, touched, visited


posts = make_posts()
created = {p[0]: p[1] for p in posts}
print(f"posts: {len(posts):,} in {SECONDS} s ({RATE} a second), {SEGMENT_POSTS:,} to a segment")
print()
print("refresh every   delay p50   p99      max      refreshes a minute")
for every in (0.1, 1.0, 5.0):
    segments, visible_at = build(posts, every)
    delays = sorted(visible_at[pid] - created[pid] for pid in visible_at)
    print(f"{every:>8.1f} s     {pct(delays, 50):>6.2f} s  {pct(delays, 99):>5.2f} s  {delays[-1]:>5.2f} s"
          f"  {60 / every:>8,.0f}")

segments, _ = build(posts, 1.0)
print()
print(f"segments after {SECONDS} s: {len(segments)}, the newest still being written")
for term, k in (("#final", 20), ("eclipse", 20)):
    hits, touched, visited = newest(segments, term, k)
    total = sum(len(s.postings.get(term, [])) for s in segments)
    print(f"newest {k} with {term}: {len(hits)} found, {touched} of {total} postings read, "
          f"{visited} of {len(segments)} segments visited")
    print(f"  first ids: {hits[:4]}")

posts: 12,135 in 40 s (300 a second), 3,000 to a segment

refresh every   delay p50   p99      max      refreshes a minute
     0.1 s       0.28 s   1.66 s   3.04 s       600
     1.0 s       0.74 s   2.03 s   3.87 s        60
     5.0 s       2.79 s   5.24 s   7.87 s        12

segments after 40 s: 5, the newest still being written
newest 20 with #final: 20 found, 20 of 246 postings read, 2 of 5 segments visited
  first ids: [112093, 112027, 112077, 112040]
newest 20 with eclipse: 19 found, 19 of 19 postings read, 5 of 5 segments visited
  first ids: [111250, 111147, 110724, 109876]

With a refresh every second, half the posts were searchable within 0.74 s and 99 % within 2.03 s. Refreshing ten times as often cut those to 0.28 s and 1.66 s, yet the slowest post still waited 3.04 s: posts held up in the log set the tail. A refresh every 5 seconds pushed the median to 2.79 s. The search shows why the index is cut by time: the 20 newest posts with #final came from the two newest segments after reading 20 of 246 postings, while a rare word was looked for in all five. Ids a fraction of a second apart can reach the indexer out of order, so the service sorts each page by id.

Practise: the newest posts in segments

The exercise asks for that Latest search; its sample tests run in the page:

def newest(segments, term, k, deleted=frozenset()):
    """The ids of the k newest searchable posts that contain term, newest first."""
    # Replace this line with your code.
    return []

from newest import newest


def segment(ids, postings, visible=None):
    return {"ids": ids, "postings": postings, "visible": len(ids) if visible is None else visible}


class NeverRead(dict):
    """A postings map that fails the test when it is read."""

    def get(self, *args):
        raise AssertionError("an older segment was read although newer segments held enough posts")

    def __getitem__(self, key):
        raise AssertionError("an older segment was read although newer segments held enough posts")


def test_newest_first_across_segments():
    """the newest segment comes first, and each list is read from its end"""
    old = segment([101, 102, 103], {"#final": [0, 2]})
    new = segment([104, 105, 106], {"#final": [1, 2]})
    assert newest([old, new], "#final", 3) == [106, 105, 103]


def test_stops_when_it_has_k():
    """an older segment is not read when the newest one holds k posts"""
    old = segment([101, 102], NeverRead())
    new = segment([103, 104, 105], {"rain": [0, 1, 2]})
    assert newest([old, new], "rain", 2) == [105, 104]


def test_posts_after_the_refresh_are_not_searchable():
    """positions from "visible" on wait for the next refresh"""
    new = segment([201, 202, 203, 204], {"metro": [1, 2, 3]}, visible=2)
    assert newest([new], "metro", 5) == [202]


def test_deleted_posts_never_appear():
    """a deleted post is skipped, and the search keeps looking"""
    old = segment([301, 302], {"vote": [0, 1]})
    new = segment([303, 304], {"vote": [0, 1]})
    assert newest([old, new], "vote", 2, deleted={304, 303}) == [302, 301]


def test_fewer_than_k_and_no_match():
    """all matches when there are fewer than k; nothing for an unknown term or k = 0"""
    old = segment([401, 402], {"film": [1]})
    new = segment([403], {"film": [0]})
    assert newest([old, new], "film", 10) == [403, 402]
    assert newest([old, new], "eclipse", 10) == []
    assert newest([old, new], "film", 0) == []

The deep dives this design must answer

• The pull threshold: pushing costs writes, pulling costs a merge on every read.
• Merge latency: every pulled timeline fetched in parallel is one more chance of a slow fetch.
• The index: one writer appends to the newest segment while many readers search it.
• Latest and Top: a newest-first search stops after k results; a ranked one needs bounds to skip segments.
• Deletes and protected posts: both must vanish from search and timelines at once.
• Partitions and tiers: recent hours sit in memory across partitions; older ones move to cheaper storage.
• Conversations: a tree of thousands of replies is read a page at a time.
• Trends: counted in windows, with coordinated campaigns filtered out.

Choosing the pull threshold from the long tail, with numbers Pro: opens with a Pro, Premium or Ultimate pass

Real-time search: segments, ranking, partitions and tiers Pro: opens with a Pro, Premium or Ultimate pass

Conversations, trends, failure drills and the level rubric Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• One log of posts feeds four consumers: fan-out, search indexing, conversations and trends.
• Search freshness is a budget: time in the log, indexing and the refresh interval add up.
• Cut the search index by time, so that a newest-first search reads only the newest segments.