Design public post search

01Problem and scope

A public-post search service retrieves matching posts without scanning every stored body. An inverted index maps each normalized term to the document IDs containing it; these lists are called postings. For a bounded example, T101 contains “solar battery”, T102 “solar roof”, and T103 “new solar battery”. The index contains solar → [T101,T102,T103] and battery → [T101,T103]. An AND query intersects the lists; an OR query unions them. At large scale, the same operations run across partitioned indexes before ranking and visibility checks.

Tokenization splits text into searchable terms. Normalization must use compatible rules during ingestion and querying; otherwise an apparently matching post can become unreachable. Partitioning and replicas preserve these semantics while distributing index storage and query work.

Scope the service to public keyword search with newest and relevance ordering, then define popularity ordering explicitly. Allow a few seconds between durable post creation and search visibility, while current deletion and access checks govern returned content. Creating the social network, private-message search, advertising auctions and language-model answers are outside this search design.

This hypothetical interview design uses explicit workload assumptions, not claims about a company’s internal architecture. The central engineering problem is to maintain a searchable derived index while posts change, then combine candidates from many index partitions into a stable, correctly filtered result.

02Functional requirements

Matching decides which posts satisfy the query; ranking decides their order. A lexical relevance score uses the words in the query and post. BM25 is one such score, combining term occurrences, term rarity and post length; the worked example later shows why its order can differ from newest-first or most-liked order.

1. Match public text: Support explicit AND/OR, such as solar AND battery, with clear syntax errors rather than silently changing Boolean meaning.
2. Choose ordering: Support latest, relevance and most-liked as distinct stable sorts. Start relevance with a comparable lexical score such as BM25, using an explicit corpus-statistics policy.
3. Page a bounded query: Return a bounded result page and continue the same query without duplicates caused by new posts. An expired snapshot requires a restart.
4. Return permitted fields: Include post ID, author/name, text, creation time and permitted engagement fields.
5. Reflect changes: Edited terms become searchable within the freshness interval. Deletion or restriction makes a post ineligible at the final visibility check.
6. Report incomplete coverage: A missing shard produces an explicit incomplete response, not a claim that the visible results are exhaustive.

Search scope and retention tiers

Assume seconds of indexing delay and subsecond normal search for the exercise. Decide whether two years are interactive and older history uses a slower tier; do not promise five-year search while building only two years. Private search and semantic embeddings are extensions. Social-distance personalization is also later work because it changes ranking data and pagination.

Text semantics and freshness

An analyzer is the configured sequence of tokenization and normalization steps used to turn text into indexed terms. Stop words are common terms that an analyzer may omit. Keeping the analyzer version explicit makes it possible to tell whether ingestion and a query interpreted the same text in the same way.

A durable post can still await index refresh; Elastic's refresh explanation makes that distinction explicit. Stop-word removal saves space but changes phrase/exact-term behavior, so agree on it before discarding words.

03Non-functional requirements

1. Latency: Search p95 below 300 ms and p99 below 800 ms for bounded interactive queries.
2. Availability: 99.9% search availability.
3. Index freshness: New or edited public posts become searchable within five seconds p99 under normal workload. Source writes follow their durable replication contract; index lag does not lose the source post.
4. Query bounds: At most 100 results/page; cap term count, wildcard complexity and historical span.
5. Retention tiers: Default to the recent two-year interactive index; search older retained source data through a slower archival tier.
6. Pagination lifetime: Bound a stable page sequence to, for example, two minutes so snapshots cannot consume resources indefinitely.
7. Authorization: Current deletion/visibility overrides old search snapshots. Pagination stability never grants permission to return removed content.

Index and response invariants

Engagement changes asynchronously, so globally instantaneous relevance is not promised. Final filters may shorten a page; never fill it with unverified cached text. If visibility authority is unavailable, omit uncertain items or fail according to product policy rather than expose them optimistically.

04Capacity estimates

Workload assumptions and arithmetic

Use these hypothetical workload assumptions: 400M posts/day at 300 bytes and 500M searches/day.

Worked estimates

Capacity implications and limits

A vocabulary of 500K terms at five bytes per term is only 2.5 MB. Compression helps; positions, scores, deletion data, and replicas add overhead. Five bytes can represent the exercise’s 730B five-year IDs; a real allocation format needs future headroom.

Assume a fivefold peak: about 23,150 post writes/s and 28,935 searches/s. If a recent query fans out to 40 partitions, that is approximately 1.16 million shard queries/s before retries. Each shard returning 100 candidates of 32 bytes sends 3.2 KB; forty shards return 128 KB/query, or about 3.7 GB/s at peak just for candidate merging. These assumptions make fanout and candidate count first-class design decisions.

At 15 terms/post, the average ingest generates around 69,450 posting additions/s, before edits and term positions. Batch writes reduce fixed per-operation overhead, but larger batches increase freshness latency and replay work. Time-based routing can skip old partitions for a last-day query; replicas distribute query CPU but add index bytes and update traffic. Estimate body retrieval separately: a 20-result page at 300 bytes/post is only 6 KB of raw text, so posting traversal and fanout may dominate over response payload.

05APIs and contracts

Request and response example

The system has two input flows: a caller asks for matching results, while the source post service reports content changes to the indexer. The search response identifies its coverage and paging context; PostChanged identifies a source change that must be applied even if it arrives late or repeats.

GET /search?q=solar%20AND%20battery&sort=latest&limit=20
→ {results:[...], nextCursor:"opaque", partial:false,
   searchedThrough:"timestamp", snapshotExpiresAt:"..."}

PostChanged {postId:T103, version:12, operation:delete,
             sourcePartition:4, offset:8172}

A point-in-time search snapshot retains one visible index state for a sequence of pages. Search-after pagination resumes after the last result's sort values within that state. Together they prevent newly indexed posts from shifting earlier page boundaries; current permission checks remain separate.

An opaque cursor binds the normalized query hash, filters, sort definition, point-in-time snapshot and last sort tuple. Sign or validate it server-side; callers cannot inject arbitrary shard positions. Reusing a cursor with a different query returns an error. A maximum page size and expiry prevent unbounded retained search contexts. The developer credential controls quota and visibility scope.

The ingestion event has a stable source partition/offset and monotonically increasing per-post version. Create, edit and delete are explicit operations. A version-12 tombstone is not equivalent to simply removing an index row and forgetting its version, because a late version-11 update could then resurrect it. Indexers acknowledge source progress only after the relevant durable index/version state is recoverable.

Search timeout behavior is part of the interface: either a strict mode fails when a shard misses its deadline or a partial mode marks incompleteness and missing scope. Retry guidance must not automatically multiply every shard request. Clients should not infer an exact global result count from a partial or approximate search response.

06Data model and access patterns

A posting entry connects a searchable term to a source post; it is not another authoritative copy of the post body. The query uses postings to find candidate IDs, then loads permitted source content. The cursor records where that query stopped within its chosen snapshot and ordering.

Authenticate developer credentials for quota enforcement, cap query complexity, and return author/name/text/time/engagement fields. Store posts by ID and maintain a durable change log through reliable change capture. A create emits version 1; an edit emits version 2; a delete emits a tombstone. Indexers apply versions idempotently, meaning replay has the same effect as one application.

The post store owns current content/version/visibility. An immutable change log records how to rebuild the index. Within a time/document index partition, maintain term dictionaries, compressed postings, optional positions and per-document current version/deletion state. Positions support phrase queries but increase bytes; omit that feature only after agreeing on the contract. A partition manifest records the ownership version (routing epoch), snapshot identity and replay watermark—the last source-log position whose changes the snapshot includes.

Choose deterministic ownership: creation-time bucket plus hash(postId) within the bucket. An edit stays with the post's original partition; otherwise every edit could become a cross-partition move. Engagement features such as like count can live in a separately versioned feature store so each like need not rewrite lexical postings. A post-body cache is keyed by post/version; a query cache is keyed by normalized query, filters, sort and the permitted freshness horizon.

Deletion/permission checks use current authoritative state or a specifically safe derived revocation mechanism. An ordinary short cache time to live (TTL) is not proof that a deleted post is no longer exposed. The final step loads post bodies from candidate IDs, often called hydration, and can batch the visibility checks rather than making one network call per result.

An allow decision binds the viewer, post ID, immutable content version and current policy revision. Hydration fetches that exact authorized version. If either version differs from the decision, repeat authorization against the returned version within the deadline or omit the result. A cached public v1 allow decision cannot authorize an edited private v2 body. The permission-read boundary still allows a response authorized before a subsequent revocation to finish under the stated in-flight policy.

07Basic working design

Local durable postings index

Start with one search process, one durable post table and a local inverted index. Creating T103 persists the post plus a pending index event transactionally. A background indexer reads it, tokenizes “new solar battery” with analyzer A1, adds T103 to each term's postings and records applied version one. After index refresh, queries can see it. The API's create acknowledgment does not falsely claim search visibility before that refresh.

Boolean search and visibility checks

The caller's AND query reads the solar and battery lists, intersects IDs and sorts matches by (createdAt,id) descending. It loads the winning post from the source table, checks public visibility and returns the text. OR instead unions IDs and removes duplicates. Sorting by a deterministic tie-breaker makes equal timestamps unambiguous.

Search-engine baseline and limits

This baseline can use a mature single-node search engine rather than implementing index file formats during an interview. What matters is explaining the data path and failure contract. A crash after the post commit but before indexing leaves a durable event to replay. A crash after indexing but before checkpointing replays the same version harmlessly. A periodic scan for source/index version differences is a repair path, not the primary ingest strategy.

08Find the baseline flaws

09Improve the design, step by step

Partitioning decides which index entries live together. Term ownership keeps a term's posting list together, making a single-term lookup local but separating the terms needed for a multi-term intersection. Document ownership keeps all terms from a post together; time/document ownership additionally groups posts by creation time so recent queries can skip older groups. The table compares the resulting query and update costs.

Choose time/document partitioning for this exercise. With a comparable final score, each partition’s top k contains sufficient candidates for global top k; later personalization, permission filtering, or deduplication may require more. Likes/comments can feed popularity; term matching feeds relevance; social distance personalizes. Store frequently changing ranking features separately when rewriting postings would be wasteful. Consistent hashing alone cannot divide one hot term’s traffic.

1. Change 1 — time/document partitions. Trigger: the local index exceeds measured posting traversal and merge capacity. Each post's complete lexical state stays in one partition; recent-time filters prune old buckets. The improvement is parallel ingest and bounded historical scope. Costs include sending each query to multiple shards, merging their replies (scatter/gather), and waiting for the slowest required shards; a wrong routing manifest misses documents. Term partitioning is attractive for narrow single-term workloads, but hot terms and cross-owner intersections make it a weaker default here.

2. Change 2 — query replicas and bounded candidate merging. Trigger: read CPU saturates while ingest remains healthy. Replicas serve independent queries; each contacted shard returns its local top candidates using a comparable sort/score. This increases query capacity but consumes storage and replication bandwidth. Replica freshness can differ, so choose replicas compatible with the snapshot and deadline. Bigger machines may be simpler before replica coordination is worthwhile.

3. Change 3 — durable ingestion and versioned rebuilds. Trigger: replay and index-file failures produce missing or resurrected records. Indexers consume the source log, apply version guards and write recoverable checkpoints; rebuilders create a new generation from a snapshot plus subsequent events. This repairs derived state without blocking all queries. It costs duplicate storage during rebuild and requires validation before alias/routing cutover. A full source scan remains a slow fallback when no valid manifest exists.

4. Change 4 — bounded caches and feature separation. Trigger: repeated queries/body reads and frequent engagement updates dominate work. Cache hot bodies with a bounded least-recently-used (LRU) eviction policy and short-lived eligible query candidates; keep dynamic rank features separate. The savings are measured by hit rate and avoided posting work. Staleness and visibility leakage are new risks, so hydration rechecks current eligibility. Skip query caching when personalization or freshness makes reuse negligible.

10Detailed architecture

Source-to-index write path

The write direction starts at the post authority, which commits content and change events. Indexers consume the change log and update primary index shards and replicas. Their checkpoints and manifests record what has been indexed and where each partition belongs. Object snapshots and source events enable recovery. A deleted post remains represented by a sufficient version/tombstone history so old updates cannot recreate it during the replay horizon.

Query-to-result read path

The read direction starts at an authenticated search edge, then a query coordinator. It parses and normalizes the query, consults the time/partition manifest and snapshot context, selects replicas, requests local candidates, and merges them. A feature service can supply popularity or other agreed ranking inputs. The hydration/visibility service fetches current post bodies and permissions before any result reaches the caller. It can use a body cache only under the current version/access rules.

Authority and query boundaries

These boundaries explain why the graph needs more than “Client → search → database.” Indexing is asynchronous; acknowledgment of the source write and index freshness are separate. Candidate selection and authorization are separate. Storage snapshots and replica health are separate recovery mechanisms. The design can return a useful partial page during an index shard outage, but cannot convert a failed visibility check into permission to return stale text.

BM25: a concrete lexical relevance score

BM25 is one defensible starting scorer. It combines term frequency (occurrences in this post), inverse document frequency (rarer corpus terms receive more weight), and length normalization (the same matches in a longer post can contribute less). Repeated occurrences have diminishing returns, controlled by k1; b controls length normalization. This ranks matches; it does not change the AND/OR matching rule. Lucene BM25.

In the formula below, t is a query term, tf is its occurrence count in the post, and IDF(t) is its rarity weight across the corpus. length and averageLength are the post's token count and the corpus average under the same analyzer.

For one conventional scaling, sum IDF(t) × tf × (k1+1) / [tf + k1 × (1−b+b×length/averageLength)] over query terms. Assume k1=1.2, b=0.75, corpus average length 2.5 tokens, and illustrative IDF=1 for both query terms. Each occurs once:

Both match, but T101 ranks first under these assumptions. A latest-first sort could prefer the newer T103. The formula and assumptions are explicit so the example can be recomputed; exact library scores may use a different constant scaling. Tune parameters against judged queries rather than treating these values as a product requirement. BM25 derivation and parameters.

Comparable scores across shards

For newest sort, (createdAt,id) is directly comparable across shards. For relevance, define score comparability, analyzer versions and any shared term statistics; a collection of unrelated local scores cannot be blindly merged and called global relevance.

Popularity features before candidate selection

To return the most-liked matches, each shard must consider likes while choosing candidates. Sorting only twenty lexical winners by likes can miss a more popular match that never entered that shortlist. For that exact sort, each document shard uses a co-located, versioned popularity feature snapshot while selecting its local top k; the coordinator resolves the feature generation before issuing shard queries. The cursor pins that generation along with the index snapshot. A separate feature store can distribute these snapshots without rebuilding term postings, but it needs an actual integration with shard scoring. If only post-retrieval reranking is available, advertise a bounded-candidate approximation and evaluate recall instead.

Concrete pagination behavior

For an Elasticsearch implementation, point-in-time plus search_after supplies stable index pagination. Default shard-local relevance statistics need not give the same scores as statistics over the whole corpus; a distributed statistics collection phase can improve comparability at extra query cost. Neither feature automatically freezes an external popularity service. The application must retain its chosen feature generation for the page session or explicitly expire the cursor.

11Write path and acknowledgement

The source post remains authoritative; the search index applies versioned changes asynchronously. The example follows post T103 through versions 10, 11 and a deletion at 12, using source offsets 8170–8172.

1. The post service authenticates author u7 and commits T103 version 10 plus change event offset 8170. The response promises durable post storage, with search visibility allowed to lag.
2. The indexer resolves T103's creation-time/document partition and analyzer generation. It reads the current applied version and rejects an older event.
3. For an edit to version 11, it replaces the document's searchable representation under the index engine's concurrency protocol. New index files, called segments, become query-visible at refresh; old representations are hidden by the current version/deletion state until compaction reclaims bytes.
4. The indexer persists a recovery position only when its applied changes can be reconstructed. If its checkpoint trails the source log, replay repeats operations safely. If it leads durable index state, updates can be lost; do not permit that ordering.
5. A delete at version 12 records a tombstone/current-version guard and removes the post from future candidate eligibility. The authoritative post service makes current visibility deny immediately according to its write contract; hydration filters older snapshots.
6. A late version-11 event is skipped because 11 is not newer than 12. The tombstone/version fence is retained through the maximum event replay and rebuild horizon, then reclaimed only under a coordinated watermark policy.

Batching reduces ingestion overhead, but acknowledgment of an entire source batch cannot leap past a failed middle event without a recorded recovery path. Events that repeatedly fail processing are isolated with their IDs for investigation, and the system records their missing updates rather than treating the affected source range as fully indexed.

12Read and delivery path

Query processing must preserve the requested Boolean semantics, a stable page boundary and current authorization. The example query q208 requests one newest result for solar AND battery within snapshot s16.

Use the same normalized query and snapshot for every continuation page.

1. The coordinator parses AND and normalizes both terms.
2. Relevant partitions intersect local postings.
3. The merge step orders T103 before T101 using (createdAt,id).
4. The authority checks current visibility/deletion and binds an allow decision to T103's exact content version and policy revision. Hydration fetches that immutable version; a mismatch requires fresh authorization or omission, not substitution of a newer body. If it differs from the indexed content version, re-evaluate the Boolean query against the exact returned text using the pinned analyzer and omit nonmatches. An edited body must not be returned solely because an older body contained both terms; complete recall and ranking can still lag until reindexing.
5. The caller receives T103 plus a cursor anchored to s16 and its last sort values.

When page two arrives, a new T104 must not randomly shift the page boundary. A point-in-time snapshot plus search-after values stabilizes ordering. Elasticsearch pagination. If T101 was deleted meanwhile, current deletion protection overrides returning it; fetch more eligible candidates or return a shorter page.

The coordinator sends a deadline to each shard and reserves time for merge and hydration. With a 300 ms p95 budget, an illustrative allocation is 20 ms edge/parse, 160 ms shard work, 40 ms merge/features and 80 ms hydration/network. These are planning values to measure, not universal timings. A shard cannot consume the full end-to-end budget and leave nothing for permissions.

Snapshot IDs expire and pin resources. Limit concurrent contexts per user and close them when paging finishes. A delete after snapshot creation can shorten a later page; that is a deliberate correctness exception to an otherwise stable historical view.

13Correctness deep dive

Per-post version monotonicity

The hard guarantee is not “events are ordered”; failures and multiple consumers can deliver old work. Each post therefore carries a source-assigned version. The index writer serializes updates for a document, or uses an engine-provided atomic version predicate, so comparison and application cannot race.

apply(event, generation):
  atomic per-document update:
    old = currentVersion[generation, event.postId]
    if event.version <= old: return ALREADY_APPLIED
    if event.operation == DELETE:
      retain tombstone(event.postId, event.version)
      hide document from new searches
    else:
      replace indexed document with analyzed event content
    currentVersion = event.version
  persist recoverable index position before advancing checkpoint

Delete replay after a crash

Rebuild from a snapshot and log watermark

Retain tombstones through the replay horizon

Do not discard delete-version metadata while older events can still replay. If a storage engine retains tombstones for less time than our recovery horizon, maintain an external version ledger or rebuild from a source snapshot that excludes older history. The final hydration check is a second protection, not permission to leave the index permanently incorrect.

14Failure and recovery

15Operations, security, and cost

Cache, health and abuse controls

Cache hot post bodies with a bounded LRU policy and short-lived query results when freshness permits. Health checks remove dead replicas; round robin by itself neither detects failures nor accounts for long queues. Query deadlines, bounded fanout, and load-aware routing protect tail latency. If one partition times out, mark a partial result explicitly rather than claiming an exhaustive answer.

Index and query signals

Monitor indexing lag, search p99, shard timeout rate, postings scanned, cache hit rate, deletion propagation, and rebuild duration. Apply visibility checks after cached candidate selection and reject resource-exhausting queries.

Measure commit-to-search freshness

Tie the five-second freshness objective to source commit time → searchable generation time, and track deletion eligibility separately. Compare query latency by fanout, terms, posting length and page depth; a global average hides one hot word. Use replay tests that apply delete v12 before edit v11 and verify both index candidates and final output.

Shard fanout cost

At the illustrative peak, forty-way fanout creates about 1.16M shard queries/s. Reducing common recent queries to ten relevant partitions cuts that component fourfold; the improvement may exceed a small cache hit-rate increase. Two-year postings of 21.9 TB become 43.8 TB with one replica before positions, segment slack and snapshots. A full parallel rebuild can temporarily add another primary-sized generation, so reserve capacity before an analyzer migration.

Analyzer rollout and recovery drills

Deploy a new analyzer into a new generation and compare a fixed evaluation set: exact term matches, AND/OR behavior, deletion suppression, pagination and relevance judgments. A faster analyzer that drops an important token changes the product. Canary read routing, retain the previous generation through a rollback window, and ensure rollback cannot restore deleted content because current visibility remains enforced.

16Decision ledger and limitations

The index is a specialized materialized view, not the sole durable copy of a post. That choice makes recovery possible but creates ingestion lag and operational work. Query replicas improve throughput without guaranteeing that every replica is equally fresh. A newest-first query is simpler to merge than a personalized relevance model; discuss the additional candidate recall and score comparability requirements before adding personalization.

The remaining bottlenecks are hot posting lists, broad historical fanout and final access checks. Caching helps repeated eligible work; it does not make every ad hoc query inexpensive. Request bounds and explicit partial-result semantics are product decisions as much as implementation details.

17Interview closing

“I start with public keyword search and a few seconds of freshness delay. Posts are durable in the source store, and a change log drives a derived inverted index. I partition by time and document so each post's terms update together and recent searches skip history. Query coordinators fan out to eligible replicas, merge comparable local candidates, then hydrate and check current visibility before returning text. A point-in-time context and search-after tuple stabilize pagination.

“The critical correctness rule is monotonic per-post version application: a delayed edit cannot overwrite a newer deletion. Rebuilds use a snapshot watermark plus replay and publish a validated generation. The costs are waiting for slow shards when merging results, index lag, extra visibility reads and duplicate storage during rebuild. I would next measure posting scans and p99 fanout latency for common and pathological queries.”

If the interviewer adds private posts, move access filtering into retrieval where possible to avoid poor candidate recall, while retaining final authorization. If they add semantic search, build a separate embedding/index lifecycle with model versions and evaluate hybrid candidate recall; adding a vector database icon alone does not define relevance, privacy or freshness.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.