Backend systems / system design
Search Typeahead System
Autocomplete with Trie indexing, caching, persistence, and performance instrumentation.
Backend implementation, indexing, caching, and measurement
Python · FastAPI · SQLAlchemy · PostgreSQL / SQLite · Redis · Pytest
Open-source engineering project
OVERVIEW
A FastAPI autocomplete backend with a short read path: normalize a prefix, check the cache, then retrieve pre-ranked suggestions from an in-memory Trie. Search logs and offline refresh jobs update the durable catalog and rebuild the index.
Architecture
- 01PREFIX REQUEST
FastAPI validates and normalizes the query.
- 02CACHE CHECK
Redis or local TTL cache returns a hit.
- 03TRIE ON MISS
Pre-ranked suggestions feed the response and cache.
- 04OFFLINE REFRESH
SQL catalog → index rebuild → cache invalidation.
BOUNDARYSearch events are persisted separately. Batch aggregation and ORCAS imports refresh the SQL catalog; the Trie is process-local.
The suggestion service keeps prefix reads in memory. SQLAlchemy stores suggestions and search events in SQLite by default, with PostgreSQL and Redis configured in Docker Compose. Ranking combines search, click, conversion, recency, and business-boost inputs.
Trending suggestions aggregate recent logs. Admin updates, batch aggregation, and the ORCAS query-click importer recalculate scores, rebuild the Trie, and clear cached suggestions.
Key decisions & trade-offs
Each Trie node stores a bounded list of top suggestions. Prefix traversal is O(m) for a prefix of length m, plus the cost of returning results. This shifts ranking work toward writes and rebuilds in exchange for memory at each node.
A cache abstraction supports local TTL storage or Redis. Failed cache reads fall back to the Trie. Full index rebuilds are simple to inspect, but there is no coordinated refresh across service replicas.
Verification / results
Committed Pytest suites cover prefix indexing, ranking, cache expiry, API behavior, and ORCAS import. GitHub Actions runs pytest on pushes and pull requests.
The benchmark harness sends concurrent HTTP requests to /suggest and reports success/failure counts, throughput, average latency, p50, p95, p99, and cache-hit ratio. A committed localhost sample exists; it is a small local run, not a production latency guarantee.
Limitations
The in-memory index is replicated per process; rebuilds are not atomic index swaps. Fuzzy fallback scans indexed suggestions, admin access uses a static token, and production rate limiting is a documented placeholder. No production traffic or distributed-scale claim is made.