1
2
3
4
5
6
7
8
9
10
11
12
13

Origin processing breakdown (target: 20ms p99):
 
Query normalization:        1ms   ████
Profile/session fetch:      3ms   ████████████
Prefix index lookup:        5ms   ████████████████████
Candidate scoring:          6ms   ████████████████████████
Sorting/top-K:              2ms   ████████
Post-processing:            2ms   ████████
Serialization:              1ms   ████
                           ────
Total:                     20ms
 
Note: Fetches should be parallelized, not sequential!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class ClientSuggestionCache {
  private cache: Map<string, CachedResult>;
  private maxEntries: number = 100;
  private ttlMs: number = 60000;  // 1 minute
  
  get(prefix: string): Suggestion[] | null {
    const cached = this.cache.get(prefix);
    if (!cached) return null;
    
    if (Date.now() > cached.expiresAt) {
      this.cache.delete(prefix);
      return null;
    }
    
    // Move to front (LRU)
    this.cache.delete(prefix);
    this.cache.set(prefix, cached);
    
    return cached.suggestions;
  }
  
  set(prefix: string, suggestions: Suggestion[]): void {
    // Evict if at capacity
    if (this.cache.size >= this.maxEntries) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    
    this.cache.set(prefix, {
      suggestions,
      expiresAt: Date.now() + this.ttlMs,
    });
  }
  
  // Optimization: Use prefix hierarchy
  getPrefixMatch(query: string): Suggestion[] | null {
    // "machine le" might be cached; filter for "machine lea"
    for (let len = query.length; len > 0; len--) {
      const prefix = query.slice(0, len);
      const cached = this.get(prefix);
      if (cached) {
        // Filter cached results for the full query
        return cached.filter(s => 
          s.text.toLowerCase().startsWith(query.toLowerCase())
        );
      }
    }
    return null;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Edge Cache Configuration:
 
┌─────────────────────────────────────────────────────────────┐
│                     CDN (CloudFront/Fastly)                  │
├─────────────────────────────────────────────────────────────┤
│ Cache Key: prefix + locale + platform                        │
│ TTL: 60 seconds (short for freshness)                        │
│ Stale-While-Revalidate: 120 seconds                          │
│ Cache-Control: public, max-age=60, stale-while-revalidate=120│
│                                                              │
│ Vary: Accept-Encoding, Accept-Language                       │
│                                                              │
│ Not cached: Personalized results (user-specific)             │
│ Cached: Non-personalized, popular prefixes                   │
└─────────────────────────────────────────────────────────────┘
 
Cache Hit Rates by Prefix Length:
- 1-char prefixes: 99% hit rate (26 entries cover all)
- 2-char prefixes: 95% hit rate (common combos)
- 3-char prefixes: 80% hit rate (frequently typed)
- 4+ char prefixes: 40-60% hit rate (long tail)
 
Overall expected hit rate: 70-80%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// Multi-tier application cache
class ApplicationCache {
  // L1: Process-local cache (fastest, smallest)
  private l1Cache: LRUCache<string, CachedSuggestions>;
  
  // L2: Shared cache (Redis)
  private l2Cache: RedisClient;
  
  constructor() {
    this.l1Cache = new LRUCache({
      maxSize: 10000,     // 10K entries
      ttlMs: 30000,       // 30 second TTL
    });
  }
  
  async get(key: string): Promise<Suggestion[] | null> {
    // Try L1 first
    const l1Result = this.l1Cache.get(key);
    if (l1Result) {
      metrics.increment('cache.l1.hit');
      return l1Result;
    }
    
    // Try L2
    const l2Result = await this.l2Cache.get(`sugg:${key}`);
    if (l2Result) {
      metrics.increment('cache.l2.hit');
      // Backfill L1
      const parsed = JSON.parse(l2Result);
      this.l1Cache.set(key, parsed);
      return parsed;
    }
    
    metrics.increment('cache.miss');
    return null;
  }
  
  async set(key: string, value: Suggestion[]): Promise<void> {
    // Write-through to both levels
    this.l1Cache.set(key, value);
    await this.l2Cache.setex(
      `sugg:${key}`,
      60,  // 60 second TTL
      JSON.stringify(value)
    );
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

┌───────────────────────────────────────────────────────────────┐
│                     Global CDN Network                         │
│  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐           │
│  │ Edge NA │  │ Edge EU │  │ Edge AP │  │ Edge SA │           │
│  │ (cache) │  │ (cache) │  │ (cache) │  │ (cache) │           │
│  └────┬────┘  └────┬────┘  └────┬────┘  └────┬────┘           │
│       │            │            │            │                 │
└───────┴────────────┴────────────┴────────────┴─────────────────┘
                               │
                               ▼
              ┌────────────────────────────────┐
              │         Origin Servers          │
              │  (us-east-1 or multi-region)    │
              │                                 │
              │  - Full suggestion index        │
              │  - Ranking logic                │
              │  - Personalization              │
              └────────────────────────────────┘
 
Latency from user:
- Cache hit at edge: 5-20ms (great!)
- Cache miss, origin request: 50-150ms (acceptable for misses)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

┌───────────────────────────────────────────────────────────────┐
│                   Edge Compute Network                         │
│  ┌──────────────┐  ┌──────────────┐  ┌──────────────┐         │
│  │ Edge NA      │  │ Edge EU      │  │ Edge AP      │         │
│  │              │  │              │  │              │         │
│  │ ┌──────────┐ │  │ ┌──────────┐ │  │ ┌──────────┐ │         │
│  │ │ Trie     │ │  │ │ Trie     │ │  │ │ Trie     │ │         │
│  │ │ Replica  │ │  │ │ Replica  │ │  │ │ Replica  │ │         │
│  │ └──────────┘ │  │ └──────────┘ │  │ └──────────┘ │         │
│  │ ┌──────────┐ │  │ ┌──────────┐ │  │ ┌──────────┐ │         │
│  │ │ Ranking  │ │  │ │ Ranking  │ │  │ │ Ranking  │ │         │
│  │ │ Logic    │ │  │ │ Logic    │ │  │ │ Logic    │ │         │
│  │ └──────────┘ │  │ └──────────┘ │  │ └──────────┘ │         │
│  └──────────────┘  └──────────────┘  └──────────────┘         │
│                                                                │
│  All queries answered at edge - no origin round-trip!          │
└───────────────────────────────────────────────────────────────┘
                               △
                               │ Periodic replication
                               │ (every few minutes)
              ┌────────────────────────────────┐
              │         Central Origin          │
              │  - Master suggestion index      │
              │  - Trending updates             │
              │  - User profile store           │
              └────────────────────────────────┘
 
Latency: consistently 5-20ms regardless of origin distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Cloudflare Worker / Fastly Compute@Edge / Lambda@Edge
 
interface EdgeTypeaheadConfig {
  trieData: ArrayBuffer;      // Serialized trie (loaded at startup)
  topKCache: KVNamespace;     // Edge KV for pre-computed results
}
 
export default {
  async fetch(request: Request, env: EdgeTypeaheadConfig): Promise<Response> {
    const url = new URL(request.url);
    const prefix = url.searchParams.get('q') || '';
    
    if (prefix.length < 1) {
      return new Response(JSON.stringify({ suggestions: [] }));
    }
    
    // Check edge cache first
    const cacheKey = `prefix:${prefix.toLowerCase()}`;
    const cached = await env.topKCache.get(cacheKey);
    if (cached) {
      return new Response(cached, {
        headers: { 'Content-Type': 'application/json', 'X-Cache': 'HIT' },
      });
    }
    
    // Query local trie (loaded in memory at worker startup)
    const trie = TrieIndex.fromBuffer(env.trieData);
    const suggestions = trie.search(prefix, 10);
    
    const response = JSON.stringify({ suggestions });
    
    // Cache at edge for next request
    await env.topKCache.put(cacheKey, response, { expirationTtl: 60 });
    
    return new Response(response, {
      headers: { 'Content-Type': 'application/json', 'X-Cache': 'MISS' },
    });
  },
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// Bad: Pointer-chasing through Map
interface BadTrieNode {
  children: Map<string, BadTrieNode>;  // Each lookup → hash + dereference
  isTerminal: boolean;
  word?: string;
  metadata?: NodeMetadata;
}
 
// Good: Array with good locality
interface GoodTrieNode {
  // Children stored as flat array, indexed by char code
  // All child pointers are contiguous in memory
  children: (GoodTrieNode | null)[];  // Size 128 for ASCII
  
  // Hot data first (accessed together)
  isTerminal: boolean;
  childCount: number;  // Avoid traversing array to count
  
  // Cold data after (accessed only on terminal)
  wordIndex: number;   // Index into separate string table
  score: number;
}
 
// Even better: Struct-of-arrays
interface TrieIndex {
  // All node data in contiguous arrays
  childBitmaps: Uint32Array;      // bitmap per node
  childOffsets: Uint32Array;      // offset to children
  isTerminal: Uint8Array;         // 1 bit per node (packed)
  scores: Float32Array;           // score per node
  
  // Separate string storage
  stringTable: Uint8Array;
  stringOffsets: Uint32Array;
}
 
// Accessing fields for node i:
// childBitmap = index.childBitmaps[i]
// score = index.scores[i]
// All cache-friendly sequential access!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// Conceptual: Batch score computation with SIMD
// Real implementation would use WebAssembly SIMD or native code
 
function batchComputeScores_naive(
  candidates: Float32Array,  // Base scores
  boosts: Float32Array,       // Personalization boosts
  count: number
): Float32Array {
  const result = new Float32Array(count);
  for (let i = 0; i < count; i++) {
    result[i] = candidates[i] * boosts[i];
  }
  return result;
}
 
// SIMD version: Process 4/8 elements at once
function batchComputeScores_simd(
  candidates: Float32Array,
  boosts: Float32Array,
  count: number
): Float32Array {
  // Assuming WASM SIMD or native
  // v128.mul processes 4 x f32 in one instruction
  const result = new Float32Array(count);
  
  // Process 4 elements at a time
  const vec_count = Math.floor(count / 4) * 4;
  for (let i = 0; i < vec_count; i += 4) {
    // In WASM: v128.mul(candidates[i:i+4], boosts[i:i+4])
    result[i] = candidates[i] * boosts[i];
    result[i+1] = candidates[i+1] * boosts[i+1];
    result[i+2] = candidates[i+2] * boosts[i+2];
    result[i+3] = candidates[i+3] * boosts[i+3];
  }
  
  // Handle remainder
  for (let i = vec_count; i < count; i++) {
    result[i] = candidates[i] * boosts[i];
  }
  
  return result;
}
 
// Speedup: 2-4x for scoring operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

interface PrecomputedTrieNode {
  // Pre-computed at index build time
  topKSuggestions: number[];    // Indices of top-K descendants
  maxDescendantScore: number;   // For pruning during search
  subtreeSize: number;          // Number of terminal nodes below
  
  // Runtime-mutable
  trendingBoost: number;        // Updated by streaming pipeline
}
 
// At query time:
function getTopK(node: PrecomputedTrieNode, k: number): Suggestion[] {
  if (node.topKSuggestions.length <= k) {
    // Pre-computed result is sufficient
    return node.topKSuggestions.map(i => suggestionTable[i]);
  }
  
  // Need fresh ranking — but this is rare for common prefixes
  return computeTopKDynamic(node, k);
}
 
// Pre-computation trade-offs:
// - Build time: Longer (compute once)
// - Memory: Higher (store pre-computed results)
// - Query time: Much faster (just lookup)
// Worth it for hot paths!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// Bad: Sequential processing
async function handleRequest_bad(query: string, userId: string) {
  // Step 1: 10ms
  const candidates = await getCandidates(query);
  // Step 2: 5ms (waits for step 1)
  const profile = await getUserProfile(userId);
  // Step 3: 3ms (waits for step 2)
  const session = await getSessionState(userId);
  // Step 4: 8ms (waits for all above)
  const ranked = await rankCandidates(candidates, profile, session);
  // Total: 26ms
  return ranked;
}
 
// Good: Parallel where independent
async function handleRequest_good(query: string, userId: string) {
  // Steps 1, 2, 3 are independent - run in parallel
  const [candidates, profile, session] = await Promise.all([
    getCandidates(query),    // 10ms
    getUserProfile(userId),   // 5ms (parallel)
    getSessionState(userId),  // 3ms (parallel)
  ]);
  // Total wait: max(10, 5, 3) = 10ms
  
  // Step 4 depends on all three
  const ranked = await rankCandidates(candidates, profile, session);
  // Total: 10 + 8 = 18ms (vs 26ms sequential)
  
  return ranked;
}
 
// Speedup: 30% just from parallelization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class SpeculativeTypeahead {
  private prefetchCache: Map<string, Promise<Suggestion[]>>;
  
  async getSuggestions(prefix: string): Promise<Suggestion[]> {
    // Check if we already prefetched this
    const prefetched = this.prefetchCache.get(prefix);
    if (prefetched) {
      return prefetched;
    }
    
    // Fetch current prefix
    const result = this.fetchSuggestions(prefix);
    
    // Speculatively prefetch likely next prefixes
    this.speculativePrefetch(prefix);
    
    return result;
  }
  
  private speculativePrefetch(prefix: string): void {
    // Predict next keystrokes based on common patterns
    const likelyNextChars = this.predictNextChars(prefix);
    
    for (const char of likelyNextChars.slice(0, 3)) {
      const nextPrefix = prefix + char;
      if (!this.prefetchCache.has(nextPrefix)) {
        // Start fetch without awaiting
        this.prefetchCache.set(
          nextPrefix,
          this.fetchSuggestions(nextPrefix)
        );
      }
    }
  }
  
  private predictNextChars(prefix: string): string[] {
    // Could use frequency data from logs
    // Simplified: common English letter frequencies after prefix
    const common = 'etaoinsrhldcumwfgypbvkjxqz'.split('');
    return common;
  }
}
 
// Effect: By the time user types next char, result is ready
// Hit rate depends on prediction accuracy (typically 30-50%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class TypeaheadService {
  private updateQueue: AsyncQueue<UpdateEvent>;
  
  async handleQuery(request: QueryRequest): Promise<QueryResponse> {
    // Fast path: just read, never block on writes
    const suggestions = await this.index.search(request.prefix);
    
    // Record query event asynchronously (don't await)
    this.updateQueue.enqueue({
      type: 'query',
      prefix: request.prefix,
      timestamp: Date.now(),
    }).catch(err => console.error('Failed to enqueue:', err));
    
    return { suggestions };
  }
  
  // Background worker processes updates
  async startUpdateProcessor(): Promise<void> {
    while (true) {
      const batch = await this.updateQueue.dequeueBatch(100, 1000);
      
      // Process batch updates
      await this.processUpdateBatch(batch);
      
      // Yield to allow query processing
      await new Promise(r => setTimeout(r, 10));
    }
  }
}
 
// Result: Query latency completely decoupled from update processing

1
2
3
4
5
6
7
8
9
10
11
12

Typical suggestion response (10 suggestions):
 
Uncompressed JSON: ~2000 bytes
gzip compressed:   ~500 bytes (75% reduction)  
brotli compressed: ~400 bytes (80% reduction)
 
Network time @ 10 Mbps:
Uncompressed: 1.6ms
Compressed:   0.4ms
 
Plus: CDN edge caches compressed responses directly
      Fewer bytes = lower network cost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// Express.js example
import compression from 'compression';
 
app.use(compression({
  level: 6,                    // Balance speed vs ratio
  threshold: 100,              // Don't compress tiny responses
  filter: (req, res) => {
    // Always compress typeahead responses
    if (req.path.startsWith('/api/suggest')) {
      return true;
    }
    return compression.filter(req, res);
  },
}));
 
// Response headers for CDN caching compressed responses
res.set({
  'Content-Encoding': 'br',        // Brotli
  'Vary': 'Accept-Encoding',       // Cache by encoding
  'Cache-Control': 'public, max-age=60',
});

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// protobuf schema
// syntax = "proto3";
// 
// message SuggestionRequest {
//   string prefix = 1;
//   string user_id = 2;
//   int32 limit = 3;
// }
// 
// message SuggestionResponse {
//   repeated Suggestion suggestions = 1;
// }
// 
// message Suggestion {
//   string text = 1;
//   float score = 2;
//   string type = 3;
// }
 
// Generated TypeScript client
import { SuggestionRequest, SuggestionResponse } from './proto/suggestions_pb';
 
async function fetchSuggestions(prefix: string): Promise<Suggestion[]> {
  const request = new SuggestionRequest();
  request.setPrefix(prefix);
  request.setLimit(10);
  
  // Binary encoding (much smaller than JSON)
  const bytes = request.serializeBinary();
  
  const response = await fetch('/api/suggest-binary', {
    method: 'POST',
    headers: { 'Content-Type': 'application/protobuf' },
    body: bytes,
  });
  
  const responseBytes = await response.arrayBuffer();
  return SuggestionResponse.deserializeBinary(new Uint8Array(responseBytes));
}
 
// Size comparison:
// JSON: { "prefix": "python", "user_id": "u123", "limit": 10 } = 50 bytes
// Protobuf: same data = ~15 bytes (70% smaller)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// HTTP/2 multiplexing: Many requests over one connection
import http2 from 'http2';
 
class TypeaheadClient {
  private session: http2.ClientHttp2Session;
  
  constructor(private url: string) {
    // Single persistent connection
    this.session = http2.connect(url);
    
    // Handle connection errors
    this.session.on('error', (err) => {
      console.error('HTTP/2 error:', err);
      this.reconnect();
    });
  }
  
  async getSuggestions(prefix: string): Promise<Suggestion[]> {
    return new Promise((resolve, reject) => {
      const req = this.session.request({
        ':method': 'GET',
        ':path': `/api/suggest?q=${encodeURIComponent(prefix)}`,
      });
      
      let data = '';
      req.on('data', (chunk) => data += chunk);
      req.on('end', () => resolve(JSON.parse(data).suggestions));
      req.on('error', reject);
      req.end();
    });
  }
}
 
// Benefits of HTTP/2:
// - Single TCP connection (no connection setup overhead)
// - Multiplexed streams (parallel requests)
// - Header compression (HPACK)
// - Server push (proactive cache warming)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import { trace, context, SpanKind } from '@opentelemetry/api';
 
const tracer = trace.getTracer('typeahead-service');
 
async function handleTypeaheadRequest(request: Request): Promise<Response> {
  return tracer.startActiveSpan('typeahead.request', {
    kind: SpanKind.SERVER,
  }, async (span) => {
    try {
      span.setAttribute('prefix', request.prefix);
      span.setAttribute('userId', request.userId);
      
      // Trace sub-operations
      const candidates = await tracer.startActiveSpan(
        'typeahead.getCandidates',
        async (childSpan) => {
          const result = await getCandidates(request.prefix);
          childSpan.setAttribute('candidateCount', result.length);
          childSpan.end();
          return result;
        }
      );
      
      const ranked = await tracer.startActiveSpan(
        'typeahead.rank',
        async (childSpan) => {
          const result = await rankCandidates(candidates);
          childSpan.end();
          return result;
        }
      );
      
      span.setStatus({ code: SpanStatusCode.OK });
      return new Response(JSON.stringify({ suggestions: ranked }));
    } catch (error) {
      span.setStatus({ code: SpanStatusCode.ERROR, message: error.message });
      span.recordException(error);
      throw error;
    } finally {
      span.end();
    }
  });
}
 
// Trace visualization shows:
// typeahead.request (18ms total)
// ├── typeahead.getCandidates (10ms)
// ├── typeahead.fetchProfile (3ms, parallel)
// └── typeahead.rank (5ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// Run before merge to detect performance regressions
 
interface PerformanceTest {
  name: string;
  warmupRequests: number;
  testRequests: number;
  p99Target: number;  // milliseconds
}
 
const tests: PerformanceTest[] = [
  { name: 'short-prefix', warmupRequests: 100, testRequests: 1000, p99Target: 50 },
  { name: 'long-prefix', warmupRequests: 100, testRequests: 1000, p99Target: 30 },
  { name: 'personalized', warmupRequests: 50, testRequests: 500, p99Target: 60 },
];
 
async function runPerfTests(): Promise<TestResult[]> {
  const results: TestResult[] = [];
  
  for (const test of tests) {
    const latencies: number[] = [];
    
    // Warmup
    for (let i = 0; i < test.warmupRequests; i++) {
      await sendTestRequest(test.name);
    }
    
    // Measure
    for (let i = 0; i < test.testRequests; i++) {
      const start = performance.now();
      await sendTestRequest(test.name);
      latencies.push(performance.now() - start);
    }
    
    // Calculate p99
    latencies.sort((a, b) => a - b);
    const p99 = latencies[Math.floor(latencies.length * 0.99)];
    
    results.push({
      name: test.name,
      p99,
      passed: p99 <= test.p99Target,
      target: test.p99Target,
    });
  }
  
  return results;
}
 
// CI integration: Block merge if p99 exceeds target