Typeahead : Autocomplete Service in Go

A standalone prefix-search/autocomplete service in Go. It supports prefix suggestions ranked by selection frequency, memory capacity limiting (LRU eviction), crash recovery (JSON Snapshotting + Write-Ahead Log), and optional fuzzy matching (edit distance 1).

---

Features

1. Trie Structure: Character-level search tree utilizing Go rune types for UTF-8 support. Terminating nodes store selection frequency weights.
2. Concurrency: Synchronized using a sync.RWMutex which allows multiple concurrent reads (/suggest) while serializing write updates (/insert, /select).
3. API Layer: HTTP REST endpoints for query suggestions, word insertions, and selection updates.
4. Persistence: Write-Ahead Log (WAL) for append-only logs of each write, combined with periodic snapshots (JSON files written atomically via temp-file-and-rename).
5. Memory Limiting: Fixed word count limit (max-words). When the limit is reached, the Least Recently Used (LRU) word is evicted, and unused nodes are pruned from the tree.
6. Fuzzy Matching: Optional typo-tolerance matching prefixes with up to edit distance 1 (handling substitutions, insertions, deletions, and transpositions).

---

System Architecture & Data Flow

1. Read and Write Paths

The service separates read and write flows. Reads acquire shared locks, while writes acquire exclusive locks, append to the WAL, and check memory bounds.

flowchart TD
    Client[Client Request] --> REST[REST API / HTTP Server]
    
    subgraph Read Path
        REST -->|GET /suggest| ReadLock[Acquire RLock]
        ReadLock --> TrieSearch[Traverse Prefix Path]
        TrieSearch --> DFS[Subtree DFS / Fuzzy Traverse]
        DFS --> Sort[Sort by Frequency]
        Sort --> ReleaseRLock[Release RLock]
        ReleaseRLock --> ClientResponse[JSON Response]
    end

    subgraph Write Path
        REST -->|POST /insert or /select| WriteLock[Acquire Lock]
        WriteLock --> WAL[Append to WAL File & Sync]
        WAL --> TrieUpdate[Modify Node Frequency]
        TrieUpdate --> LRU[Update LRU Cache List]
        LRU --> LimitCheck{Size > max-words?}
        LimitCheck -->|Yes| Evict[Evict Oldest Word & Prune Node]
        LimitCheck -->|No| ReleaseLock[Release Lock]
        Evict --> ReleaseLock
        ReleaseLock --> WriteResponse[Success Response]
    end

Loading

2. Startup Recovery Flow

On startup, the persistence manager checks for existing snapshots and WAL logs to reconstruct the Trie in the correct LRU order.

flowchart TD
    Start[Service Start] --> LoadSnap{Snapshot Exists?}
    LoadSnap -->|Yes| ReadSnap[Read JSON Snapshot]
    ReadSnap --> PopTrie[Populate Trie & LRU List]
    PopTrie --> ReadWAL{WAL Exists?}
    LoadSnap -->|No| ReadWAL
    
    ReadWAL -->|Yes| ReplayWAL[Replay WAL operations sequentially]
    ReplayWAL --> TriggerSnap[Trigger fresh Snapshot & Truncate WAL]
    TriggerSnap --> Ready[Ready to Accept Requests]
    ReadWAL -->|No| Ready

Loading

---

Design Comparisons

1. Trie vs. Sorted Array + Binary Search

• Reads: Both look up prefix matches quickly ($O(L + S)$ for Trie, $O(L \cdot \log N + K)$ for binary search).
• Writes & Updates: Inserting new words or updating selection frequencies in a sorted array is an $O(N)$ operation because it requires shifting subsequent elements in memory. A Trie performs inserts and frequency updates in $O(L)$ time (where $L$ is the word length), which does not scale with vocabulary size $N$.
• Eviction: Evicting words from a sorted array requires shifting elements ($O(N)$), while Trie eviction and path pruning run in $O(L)$ time.

2. Trie vs. Hash-Based Prefix Index (Prefix-to-Words Map)

• Memory Usage: A hash-based prefix index maps every possible prefix string to a list of suggestions. If a word has length $L$, it is duplicated and referenced in $L$ separate lists, causing high memory usage. A Trie shares common prefix nodes, storing characters and words once.
• Updates: When a word's weight changes or a word is evicted, a hash-based index must search and modify lists for all of its prefix keys. A Trie only modifies the single terminating leaf node.

---

Project Structure

typeahead/
├── cmd/
│   └── server/
│       └── main.go             # Flags parsing, server bootstrap, and graceful shutdown
├── pkg/
│   ├── trie/
│   │   ├── trie.go             # Core Trie struct, RWMutex synchronizer, and eviction
│   │   └── fuzzy.go            # Edit distance 1 search algorithm
│   ├── persistence/
│   │   ├── wal.go              # Write-Ahead Log appender
│   │   ├── snapshot.go         # JSON snapshot serializer
│   │   └── manager.go          # Snapshot & WAL state coordinator
│   ├── api/
│   │   ├── rest_server.go      # HTTP REST handlers
│   │   └── protobuf/           # gRPC Schema definition
│   │       └── typeahead.proto
├── benchmark/
│   └── loadtest/
│       └── main.go             # HTTP concurrent load testing tool

---

API Endpoints

1. Get Suggestions

• Endpoint: GET /suggest
• Query Parameters:
  • prefix (string, required): Prefix to match.
  • limit (int, optional, default=10): Maximum suggestions to return.
  • fuzzy (bool, optional, default=false): Enable edit distance 1 match.
• Response: 200 OK

{
  "prefix": "ap",
  "suggestions": [
    { "word": "apricot", "frequency": 3 },
    { "word": "apple", "frequency": 2 },
    { "word": "app", "frequency": 1 }
  ]
}

2. Insert Word

• Endpoint: POST /insert
• Body: {"word": "banana"}
• Response: 200 OK

{
  "success": true,
  "message": "Word inserted successfully"
}

3. Select Word

• Endpoint: POST /select
• Body: {"word": "apple"}
• Response: 200 OK

{
  "success": true,
  "message": "Word selection recorded"
}

---

How to Run

Run the Server

go run cmd/server/main.go --port=8080 --max-words=10000

Available flags:

• --port: Port to listen on (default: 8080).
• --max-words: Maximum words capacity (default: 10000).
• --snapshot-path: Path to snapshot file (default: ./data/snapshot.json).
• --wal-path: Path to WAL file (default: ./data/wal.log).
• --snapshot-writes-threshold: Writes before snapshot trigger (default: 1000).
• --snapshot-interval-seconds: Background snapshot timer in seconds (default: 30).

Run Tests

go test ./... -v

---

Benchmarks & Performance Results

These metrics were collected on an Intel Core Ultra 5 125H processor.

1. Go Unit Benchmarks

Measuring algorithm operations in memory:

go test -bench=".*" ./pkg/trie/... -benchmem

• Insertions: ~6,200,000 ops/sec (Average latency: 169.4 ns/op)
• Suggestions (Prefix Search): ~2,450,000 ops/sec (Average latency: 463.0 ns/op)
• Fuzzy Suggestions (Edit Distance 1): ~10,000 ops/sec (Average latency: 0.11 ms/op)

2. HTTP Load Testing Results

Using benchmark/loadtest/main.go with 10 concurrent workers, 3 seconds duration, and a 90% read / 10% write distribution:

Total Requests:  7728
Successful:      7728 (100.00%)
Failed/Error:    0
Throughput:      2566.16 req/sec
Total Time:      3.01s

Latency Percentiles:
  p50 (Median):  1.615 ms
  p95:           9.259 ms
  p99:           21.622 ms
  Average:       2.683 ms