TypeAheadX

PROTOTYPE

Distributed autocomplete: consistent hashing over three Redis nodes, a decaying trending score, and a write buffer that absorbs viral spikes.

Course project · Jun 2026 · 15 commits over two days

Source on GitHub ↗

THE PROBLEM

Autocomplete is read-heavy but latency-sensitive: one search generates a query per keystroke, hot prefixes create Zipfian skew, and a single Redis instance becomes a bottleneck.

HOW IT WORKS

FastAPI serves suggestions from PostgreSQL behind a Redis cache-aside layer; a 128-bit MD5 consistent-hash ring (500 virtual nodes) spreads prefixes across three Redis nodes.
An async write buffer batches click events before they hit the database, and a decaying trending score keeps popular queries fresh without a write on every keystroke.
A Next.js frontend calls the API directly; there is no separate gateway.

ENGINEERING EVIDENCE

The consistent-hash ring balances keys evenly (about 33.6/34.8/31.6% of 10,000 keys across three nodes), reproduced offline over five seeds. consistent_hash_ring.py ↗
Rebalancing from 3 to 4 nodes moved about 26.4% of keys under consistent hashing versus about 74.8% under modulo hashing, reproduced three times against the repo's own benchmark script. rebalance_experiment.py ↗
500 virtual nodes per node was chosen over 150 and 1000, on the stated trade-off of most of the balancing benefit at half the memory and CPU cost.

Virtual nodes per Redis node set to 500 after trying 150 and 1000ADOPTED
Final ownership with 500: 33.86% / 34.58% / 31.57% (ring_analysis.py re-run, matching README).
Why one Redis node took about 60% of hits although keys were split evenlyADOPTED
The ring balances keys but not traffic.
Redis cache-aside cut database reads but did not change latency in a local testADOPTED
Recorded: p50 about 7.5 ms without the cache and about 7.1 ms with it; p95 about 10.0 ms and about 12.2 ms; database reads 1000 per 1k requests (one per request, by construction) versus 13; hit rate 98.7%.
Modulo vs consistent hashing when a 4th node is added: re-run of rebalance_experiment.pyADOPTED
The repo reports 74.88% (modulo) and 26.44% (ring) in README.md and Project_Report.md.

WHAT ISN'T DONE

Balanced keys did not mean balanced traffic: with a Zipfian workload, one node still took about 60% of live requests, because the three most popular queries all hashed to it. The fix (an L1 cache or hot-key replication) is proposed but not built.
The README's "sub-millisecond autocomplete experience" is not supported by any measured end-to-end number; a 100,000-request run recorded a 420 ms warm-cache p50.
The phase-3 cache benchmark is a single unpaired run with only 12 distinct keys, so the recorded latency difference (about 7.5 ms without Redis, 7.1 ms with it) is noise, not a result.
This was a course project built over two days; no CI, and the hot-shard and rebalance findings were reproduced with scripts that are not committed to the repository.

NEXT STEPS

Each one comes from a gap listed above. It says what fixing the gap would take; it is not a promise.

Build the proposed hot-key fix (an L1 cache or hot-key replication) and re-measure the 60% hot-node share.
Re-run the cache-latency comparison as a real paired benchmark with more than 12 distinct keys.
Commit the reproduction scripts used for the hot-shard and rebalance findings.

STACK

Python
FastAPI
PostgreSQL
Redis
Next.js
React
TypeScript