Search Typeahead

A search typeahead (autocomplete) system built with Python + FastAPI. As the user types a prefix, the backend returns the top-ranked completions in two modes: basic (ranked by all-time popularity) and trending (ranked by a recency-weighted score). The system uses a prefix Trie for O(prefix) reads, a simulated distributed cache fronted by a consistent-hash ring with virtual nodes, and a batch writer with a write-ahead log (WAL) that aggregates search events and durably persists them to SQLite (WAL mode). The frontend is vanilla HTML/CSS/JS served from static/.

---

§1 Quick start

No Docker required. Run the following in order from the project root:

pip install -r requirements.txt
python data/generate_dataset.py        # creates data/queries.tsv (>=120k rows)
python -m app.ingest                    # loads the TSV into SQLite
uvicorn app.main:app --port 8000        # serves the app at http://localhost:8000
pytest -q                               # run the test suite
python scripts/bench.py                 # p95 latency + cache hit rate (server must be running)
python scripts/consistent_hash_demo.py  # key distribution + node-removal demo

A Makefile provides convenience targets: make setup, make dataset, make ingest, make run, make test, make bench, make demo.

Windows users: if make is not installed, run the equivalent python / uvicorn / pytest commands directly as shown above. The Makefile targets are thin wrappers around exactly these commands.

Open http://localhost:8000 in a browser to use the typeahead UI.

Run with Docker (optional)

The whole app runs in one container — no local Python needed. On first start it generates the 120k dataset and ingests it automatically, then serves on :8000.

docker compose up --build        # then open http://localhost:8000
# or, without compose:
docker build -t typeahead .
docker run -p 8000:8000 -v typeahead-data:/app/data typeahead

The named volume typeahead-data persists the SQLite DB + WAL, so recorded search counts survive docker compose down / up. (docker compose down -v wipes the data and forces a fresh dataset rebuild on the next start.)

---

§2 Architecture

The browser UI calls the FastAPI backend. Reads (GET /suggest) use a cache-aside strategy: the service computes a cache key from (prefix, mode), routes it through the consistent-hash ring to the owning cache node, and returns the cached suggestions on a hit. On a miss it falls through to the Trie, ranks the candidates, stores the result in the cache with a TTL, and returns it.

Writes (POST /search) record recency for the query and hand the event to the BatchWriter, which appends to a durable WAL and aggregates repeats in an in-memory buffer. A background thread flushes the buffer to SQLite every 2s (or when it reaches 500 entries). On flush, the service updates the Trie counts and invalidates the cache keys for affected prefixes so stale suggestions are not served.

flowchart TD
    UI["Browser UI (static/)"]
    API["FastAPI (app/main.py)"]
    SVC["Service orchestrator (app/service.py)"]

    UI -->|GET /suggest, POST /search| API
    API --> SVC

    subgraph ReadPath["Read path (cache-aside)"]
        RING["Consistent-hash ring (vnodes)"]
        NODES["Cache nodes (CacheCluster)"]
        TRIE["Prefix Trie (top-k per node)"]
        RANK["Ranking (basic / trending)"]
        SVC -->|key = prefix+mode| RING --> NODES
        NODES -->|miss| TRIE --> RANK
        RANK -->|set w/ TTL| NODES
        NODES -->|hit| SVC
    end

    subgraph WritePath["Write path"]
        BW["BatchWriter (WAL + buffer)"]
        WAL[("WAL file (durable)")]
        DB[("SQLite (WAL mode)")]
        SVC -->|record recency + record event| BW
        BW -->|append| WAL
        BW -->|flush every 2s / 500| DB
    end

    BW -.->|on flush| TRIE
    BW -.->|invalidate affected prefix keys| NODES

Loading

For a full deep-dive see docs/ARCHITECTURE.md.

---

§3 API documentation

Endpoint	Method	Params	Description
/suggest	GET	q (prefix, required), mode = basic|trending (default basic)	Top-10 completions for the prefix
/search	POST	JSON body {"query": "..."}	Records a search event (async batched)
/trending	GET	limit (int, default config)	Top trending queries with scores
/cache/debug	GET	prefix, mode	Cache routing/status for a key
/stats	GET	—	Latency, cache, DB, and batch metrics
/	GET	—	Serves the typeahead UI

Examples

GET /suggest?q=lap&mode=basic

{
  "prefix": "lap",
  "mode": "basic",
  "suggestions": ["laptop", "laptop stand", "laptop bag", "lapland"]
}

POST /search
Content-Type: application/json

{"query": "laptop stand"}

{"message": "Searched"}

GET /trending?limit=3

{
  "trending": [
    {"query": "laptop", "count": 48210, "score": 6.83},
    {"query": "headphones", "count": 31002, "score": 6.41},
    {"query": "monitor", "count": 22118, "score": 5.97}
  ]
}

GET /cache/debug?prefix=lap&mode=trending

{
  "prefix": "lap",
  "cache_key": "trending:lap",
  "owner_node": "node-2",
  "status": "hit"
}

GET /stats

{
  "latency_ms": {"p50": 1.2, "p95": 4.8, "p99": 9.1},
  "cache_hit_rate": 0.93,
  "db_reads": 1204,
  "db_writes": 56,
  "cache_node_sizes": {"node-0": 410, "node-1": 388, "node-2": 402},
  "batch": {"buffered": 12, "flushes": 56, "wal_replayed": 0}
}

---

§4 Dataset

• Format: tab-separated values (TSV), one row per query: query<TAB>count.
• Size: at least 120,000 rows.
• Distribution: counts follow a Zipf distribution, so a handful of head queries dominate while a long tail receives few hits — realistic for a search workload and useful for exercising both ranking and caching.
• Generate: python data/generate_dataset.py writes data/queries.tsv.
• Load: python -m app.ingest reads the TSV and upserts the rows into the SQLite queries table.

---

§5 Design choices & trade-offs (brief)

• Trie for reads: prefix lookups are O(len(prefix) + k) instead of a full-table LIKE 'prefix%' scan. Each trie node caches its top CANDIDATE_K completions by count, so a suggestion request walks the prefix once and returns the precomputed candidates.
• Consistent hashing + virtual nodes: cache keys map to nodes via an MD5 hash ring. Virtual nodes (VNODES_PER_NODE=150) smooth out key distribution, and adding/removing a node remaps only ~1/N of keys.
• Batch writes + WAL durability: search events are aggregated in memory and flushed in batches, drastically reducing per-request SQLite writes; the WAL guarantees no acknowledged search is lost across a crash.
• Trending half-life decay: recent activity decays exponentially (RECENCY_HALF_LIFE=1800s) and counts are log-damped, so a brief spike fades and never permanently dominates rankings.
• Cache TTL + invalidation: cached suggestions expire on a TTL and are explicitly invalidated for affected prefixes whenever a batch flush changes the underlying counts.

See docs/ARCHITECTURE.md for full reasoning.

---

§6 Rubric coverage

Rubric item	Where it is implemented
Basic suggestions (60)	app/trie.py (prefix lookup + per-node top-k), app/ranking.py (basic = sort by all-time count), read path in app/service.py, GET /suggest?mode=basic. Caching via app/consistent_hash.py + app/cache.py. Dataset via data/generate_dataset.py + app/ingest.py + app/store.py.
Trending (20)	app/ranking.py trending score W_COUNT*log10(count+1) + W_RECENT*decayed_recent with exponential half-life decay; recency recorded on the write path in app/service.py; GET /suggest?mode=trending and GET /trending. Cache invalidated on flush via _post_flush.
Batch writes (20)	app/batch_writer.py: in-memory buffer + WAL, flush every BATCH_FLUSH_INTERVAL (2s) or at BATCH_MAX_SIZE (500), WAL rotation (*.flushing), and recover() on startup. Wired through POST /search and _post_flush in app/service.py.

---

§7 Viva prep

1. Why a trie, not SQL LIKE? A trie gives O(len(prefix)+k) lookups with precomputed top-k per node; LIKE 'p%' scans/sorts rows on every keystroke.
2. Why virtual nodes? Without them, few physical nodes hash unevenly; 150 vnodes per node smooth distribution and shrink the data moved on membership change.
3. Why does consistent hashing move only ~1/N keys? Only the arc of the ring previously owned by the removed/added node is reassigned, not the whole keyspace.
4. What happens if you crash before a batch flush? The WAL already has every acknowledged event durably on disk; recover() replays the surviving WAL on startup, so nothing acknowledged is lost.
5. Why batch writes at all? They collapse many repeated searches into a few aggregated upserts, cutting SQLite write volume and lock contention.
6. How does trending avoid permanently over-ranking a brief spike? Recent contribution decays with a half-life (1800s) and counts are log-damped, so the spike's boost fades over time rather than sticking.
7. How is the cache kept consistent when rankings change? On each flush, affected prefix cache keys are invalidated (and entries also expire by TTL), so the next read recomputes from fresh data.
8. Why SQLite in WAL mode? WAL allows concurrent readers during writes and gives better write throughput than the default rollback journal — sufficient for a single-node assignment.
9. What is the cache key and how is it routed? mode:prefix; it is MD5-hashed onto the ring and routed to the owning logical node via a bisect lookup.
10. What would you change at real scale? Swap the in-process cache for a real Redis cluster, shard the trie, move the write buffer to Kafka, and use approximate counters for the long tail.