Design Google Search

9 collapsed lines
1
interface Document {
2
  doc_id: string
3
  url: string
4
  content: string
5
  quality_score: number
6
}
7

8
interface Posting {
9
  doc_id: number
10
  frequency: number
11
  positions: number[]
12
}
13

14
// Map phase: emit (term, posting) pairs
15
function mapDocument(doc: Document): Map<string, Posting> {
16
  const terms = new Map<string, Posting>()
17
  const tokens = tokenize(doc.content)
18

19
  for (let pos = 0; pos < tokens.length; pos++) {
20
    const term = normalize(tokens[pos]) // lowercase, stem
21

22
    if (!terms.has(term)) {
23
      terms.set(term, {
24
        doc_id: hashDocId(doc.doc_id),
25
        frequency: 0,
26
        positions: [],
27
      })
28
    }
29

30
    const posting = terms.get(term)!
31
    posting.frequency++
32
    posting.positions.push(pos)
33
  }
34

35
  return terms
36
}
37

38
// Reduce phase: merge postings for same term
39
function reducePostings(term: string, postings: Posting[]): PostingList {
40
  // Sort by quality-weighted doc_id for early termination optimization
41
  postings.sort((a, b) => b.quality_score - a.quality_score)
42

43
  return {
44
    term,
45
    doc_count: postings.length,
46
    postings: deltaEncode(postings),
47
  }
48
}
49

50
function deltaEncode(postings: Posting[]): Buffer {
51
  const buffer = new CompressedBuffer()
52
  let prevDocId = 0
53

10 collapsed lines
54
  for (const posting of postings) {
55
    // Store delta instead of absolute doc_id
56
    buffer.writeVarint(posting.doc_id - prevDocId)
57
    buffer.writeVarint(posting.frequency)
58
    buffer.writePositions(posting.positions)
59
    prevDocId = posting.doc_id
60
  }
61

62
  return buffer.toBuffer()
63
}

7 collapsed lines
1
interface SpellResult {
2
  original: string
3
  corrected: string
4
  confidence: number
5
  alternatives: string[]
6
}
7

8
async function correctSpelling(query: string): Promise<SpellResult> {
9
  // 1. Check if query is a known valid phrase
10
  if (await isKnownPhrase(query)) {
11
    return { original: query, corrected: query, confidence: 1.0, alternatives: [] }
12
  }
13

14
  // 2. Run neural spell correction model
15
  const modelOutput = await spellModel.predict(query)
16

17
  // 3. Consider context: surrounding words affect correction
18
  // "python" after "monty" → don't correct to "python programming"
19
  const contextualCorrection = applyContextRules(query, modelOutput)
20

21
  // 4. Check correction against query logs (popular queries)
22
  const popularMatch = await findPopularMatch(contextualCorrection)
23

24
  return {
25
    original: query,
26
    corrected: popularMatch || contextualCorrection,
27
    confidence: modelOutput.confidence,
28
    alternatives: modelOutput.alternatives.slice(0, 3),
29
  }
30
}

11 collapsed lines
1
interface PageGraph {
2
  pages: Map<string, string[]> // page → outlinks
3
  inlinks: Map<string, string[]> // page → pages linking to it
4
}
5

6
const DAMPING_FACTOR = 0.85
7
const CONVERGENCE_THRESHOLD = 0.0001
8
const MAX_ITERATIONS = 100
9

10
function computePageRank(graph: PageGraph): Map<string, number> {
11
  const numPages = graph.pages.size
12
  const initialRank = 1.0 / numPages
13

14
  // Initialize all pages with equal rank
15
  let ranks = new Map<string, number>()
16
  for (const page of graph.pages.keys()) {
17
    ranks.set(page, initialRank)
18
  }
19

20
  // Iterate until convergence
21
  for (let iter = 0; iter < MAX_ITERATIONS; iter++) {
22
    const newRanks = new Map<string, number>()
23
    let maxDelta = 0
24

25
    for (const page of graph.pages.keys()) {
26
      // Sum of (rank / outlink_count) for all pages linking to this page
27
      let inlinkSum = 0
28
      const inlinks = graph.inlinks.get(page) || []
29

30
      for (const inlink of inlinks) {
31
        const inlinkRank = ranks.get(inlink) || 0
32
        const outlinks = graph.pages.get(inlink) || []
33
        if (outlinks.length > 0) {
34
          inlinkSum += inlinkRank / outlinks.length
35
        }
36
      }
37

38
      // PageRank formula: PR(A) = (1-d)/N + d * sum(PR(Ti)/C(Ti))
39
      const newRank = (1 - DAMPING_FACTOR) / numPages + DAMPING_FACTOR * inlinkSum
40
      newRanks.set(page, newRank)
41

42
      maxDelta = Math.max(maxDelta, Math.abs(newRank - (ranks.get(page) || 0)))
43
    }
44

45
    ranks = newRanks
46

47
    if (maxDelta < CONVERGENCE_THRESHOLD) {
48
      break // Converged
5 collapsed lines
49
    }
50
  }
51

52
  return ranks
53
}

14 collapsed lines
1
interface ShardResult {
2
  shard_id: number
3
  results: ScoredDocument[]
4
  latency_ms: number
5
}
6

7
interface QueryPlan {
8
  query: ParsedQuery
9
  shards: ShardConnection[]
10
  timeout_ms: number
11
  top_k_per_shard: number
12
}
13

14
async function executeQuery(plan: QueryPlan): Promise<SearchResult[]> {
15
  const { query, shards, timeout_ms, top_k_per_shard } = plan
16

17
  // Fan out to all shards in parallel
18
  const shardPromises = shards.map((shard) =>
19
    queryShard(shard, query, top_k_per_shard).catch((err) => ({
20
      shard_id: shard.id,
21
      results: [],
22
      latency_ms: timeout_ms,
23
      error: err,
24
    })),
25
  )
26

27
  // Wait for all shards with timeout
28
  const shardResults = await Promise.race([Promise.all(shardPromises), sleep(timeout_ms).then(() => "timeout")])
29

30
  if (shardResults === "timeout") {
31
    // Return partial results from completed shards
32
    return aggregatePartialResults(shardPromises)
33
  }
34

35
  // Merge results from all shards
36
  return mergeAndRank(shardResults as ShardResult[], query)
37
}
38

39
function mergeAndRank(shardResults: ShardResult[], query: ParsedQuery): SearchResult[] {
40
  // Collect all candidates
41
  const candidates: ScoredDocument[] = []
42
  for (const result of shardResults) {
43
    candidates.push(...result.results)
44
  }
45

46
  // Global ranking across all shards
47
  // Shard-local scores are comparable because same scoring function
48
  candidates.sort((a, b) => b.score - a.score)
49

50
  // Apply final ranking (BERT, personalization)
51
  const reranked = applyFinalRanking(candidates.slice(0, 1000), query)
52

53
  return reranked.slice(0, query.num_results)
54
}
55

56
async function queryShard(shard: ShardConnection, query: ParsedQuery, topK: number): Promise<ShardResult> {
57
  const start = Date.now()
58

59
  // 1. Retrieve posting lists for query terms
60
  const postingLists = await shard.getPostingLists(query.terms)
61

62
  // 2. Intersect posting lists (for AND queries)
63
  const candidates = intersectPostingLists(postingLists)
64

65
  // 3. Score candidates using local signals
66
  const scored = candidates.map((doc) => ({
67
    doc,
68
    score: computeLocalScore(doc, query),
11 collapsed lines
69
  }))
70

71
  // 4. Return top-K
72
  scored.sort((a, b) => b.score - a.score)
73

74
  return {
75
    shard_id: shard.id,
76
    results: scored.slice(0, topK),
77
    latency_ms: Date.now() - start,
78
  }
79
}

11 collapsed lines
1
interface CrawlJob {
2
  url: string
3
  domain: string
4
  priority: number
5
  lastCrawl: Date | null
6
  estimatedChangeRate: number
7
}
8

9
interface DomainState {
10
  lastRequestTime: Date
11
  crawlDelay: number // From robots.txt or adaptive
12
  concurrentRequests: number
13
  maxConcurrent: number
14
}
15

16
class CrawlScheduler {
17
  private domainStates: Map<string, DomainState> = new Map()
18
  private frontier: PriorityQueue<CrawlJob>
19

20
  async scheduleNext(): Promise<CrawlJob | null> {
21
    while (!this.frontier.isEmpty()) {
22
      const job = this.frontier.peek()
23

24
      // Check politeness constraints
25
      const domainState = this.getDomainState(job.domain)
26

27
      if (!this.canCrawlNow(domainState)) {
28
        // Can't crawl this domain yet, try next
29
        this.frontier.pop()
30
        this.frontier.push(job) // Re-add with delay
31
        continue
32
      }
33

34
      // Acquire crawl slot for this domain
35
      if (domainState.concurrentRequests >= domainState.maxConcurrent) {
36
        continue
37
      }
38

39
      domainState.concurrentRequests++
40
      domainState.lastRequestTime = new Date()
41

42
      return this.frontier.pop()
43
    }
44

45
    return null
46
  }
47

48
  private canCrawlNow(state: DomainState): boolean {
49
    const elapsed = Date.now() - state.lastRequestTime.getTime()
50
    return elapsed >= state.crawlDelay * 1000
51
  }
52

53
  // Adaptive crawl delay based on server response
54
  updateCrawlDelay(domain: string, responseTimeMs: number, statusCode: number): void {
55
    const state = this.getDomainState(domain)
56

57
    if (statusCode === 429 || statusCode === 503) {
58
      // Server is overloaded, back off exponentially
10 collapsed lines
59
      state.crawlDelay = Math.min(state.crawlDelay * 2, 60)
60
    } else if (responseTimeMs > 2000) {
61
      // Slow response, increase delay
62
      state.crawlDelay = Math.min(state.crawlDelay * 1.5, 30)
63
    } else if (responseTimeMs < 200 && state.crawlDelay > 1) {
64
      // Fast response, can crawl more aggressively
65
      state.crawlDelay = Math.max(state.crawlDelay * 0.9, 1)
66
    }
67
  }
68
}

9 collapsed lines
1
interface SearchResultsPage {
2
  query: string
3
  results: SearchResult[]
4
  knowledgePanel?: KnowledgePanel
5
  relatedSearches: string[]
6
}
7

8
// Server-side render critical content
9
function renderSERP(data: SearchResultsPage): string {
10
  // 1. Inline critical CSS for above-the-fold content
11
  const criticalCSS = extractCriticalCSS()
12

13
  // 2. Render first 3 results server-side (no JS needed)
14
  const initialResults = data.results.slice(0, 3).map(renderResult).join("")
15

16
  // 3. Defer non-critical content
17
  const deferredContent = `
18
    <script>
19
      // Hydrate remaining results after initial paint
20
      window.__SERP_DATA__ = ${JSON.stringify(data)};
21
    </script>
22
  `
23

24
  return `
25
    <html>
26
    <head>
27
      <style>${criticalCSS}</style>
28
    </head>
29
    <body>
30
      <div id="results">${initialResults}</div>
31
      <div id="deferred"></div>
32
      ${deferredContent}
33
      <script src="/serp.js" defer></script>
34
    </body>
35
    </html>
36
  `
37
}

7 collapsed lines
1
class AutocompleteController {
2
  private debounceMs = 100
3
  private minChars = 2
4
  private cache: Map<string, string[]> = new Map()
5

6
  async handleInput(query: string): Promise<string[]> {
7
    if (query.length < this.minChars) {
8
      return []
9
    }
10

11
    // Check cache first
12
    const cached = this.cache.get(query)
13
    if (cached) {
14
      return cached
15
    }
16

17
    // Debounce rapid keystrokes
18
    await this.debounce()
19

20
    // Fetch suggestions
21
    const suggestions = await this.fetchSuggestions(query)
22

23
    // Cache for repeat queries
24
    this.cache.set(query, suggestions)
25

26
    // Prefetch likely next queries
27
    this.prefetchNextCharacter(query)
28

29
    return suggestions
30
  }
31

32
  private prefetchNextCharacter(query: string): void {
33
    // Prefetch common next characters
34
    const commonNextChars = ["a", "e", "i", "o", "s", "t", " "]
35
    for (const char of commonNextChars) {
36
      const nextQuery = query + char
37
      if (!this.cache.has(nextQuery)) {
38
        // Low-priority background fetch
39
        requestIdleCallback(() => this.fetchSuggestions(nextQuery))
40
      }
41
    }
42
  }
43
}

1
function computeNewsScore(doc: NewsDocument, query: Query): number {
2
  const baseRelevance = computeTextRelevance(doc, query)
3
  const authorityScore = doc.sourceAuthority // CNN > random blog
4
  const freshnessScore = computeFreshnessDecay(doc.publishedAt)
5

6
  // Freshness dominates for news queries
7
  return baseRelevance * 0.3 + authorityScore * 0.2 + freshnessScore * 0.5
8
}
9

10
function computeFreshnessDecay(publishedAt: Date): number {
11
  const ageHours = (Date.now() - publishedAt.getTime()) / (1000 * 60 * 60)
12

13
  // Exponential decay: half-life of ~6 hours for breaking news
14
  return Math.exp(-ageHours / 8)
15
}

1
interface ImageDocument {
2
  imageUrl: string
3
  pageUrl: string
4
  altText: string
5
  surroundingText: string
6
  visualFeatures: number[] // CNN embeddings
7
  safeSearchScore: number
8
}
9

10
function rankImageResult(image: ImageDocument, query: Query): number {
11
  // Text signals from alt text and page context
12
  const textScore = computeTextRelevance(image.altText + " " + image.surroundingText, query)
13

14
  // Visual similarity to query (if query has image)
15
  const visualScore = query.hasImage ? cosineSimilarity(image.visualFeatures, query.imageFeatures) : 0
16

17
  // Page authority
18
  const pageScore = getPageRank(image.pageUrl)
19

20
  return textScore * 0.4 + visualScore * 0.3 + pageScore * 0.3
21
}