Search Autocomplete Service

Project roadmap

1. 01

   Design the service

   ~2h

   Write DESIGN.md: the terms table in PostgreSQL (term, weight, updated at, deleted flag), the API GET /suggest?q=&limit= (at most 10), how the prefix is normalized (lowercase, trimmed, accents removed), how ranking works (weight, then alphabetical), and how updates reach the index (polling for changed rows every few seconds). Note the latency goal, for example under 5 ms at the 99th percentile. Done when: DESIGN.md covers the data, API, ranking and update flow.

2. 02

   Build the trie with top suggestions

   ~3h

   Implement a trie where every node stores its top 10 terms by weight, updated while inserting, so a lookup only walks down the prefix and returns that node's list without searching the subtree. Handle normalization, and prefixes with no matches. Write unit tests, including comparing results with a brute-force search over a list. Done when: the trie returns the same results as the brute-force search for thousands of random prefixes.

3. 03

   Load from PostgreSQL and serve

   ~2h

   Load all terms from PostgreSQL at startup (use Flyway for the schema and a seed of about 100,000 terms, for example product names with random weights) and build the trie. Add the suggest endpoint, validating the prefix length (1 to 50 characters) and the limit. Return 503 until the first build finishes, using a readiness health check. Done when: the endpoint returns ranked suggestions after startup.

4. 04

   Apply updates without pausing reads

   ~3h

   Every few seconds, fetch terms changed since the last check. Build a new trie in the background (or apply the changes to a copy), then publish it by replacing an AtomicReference, so requests always read a complete trie and never wait for a lock. Remember the latest updated-at value seen to avoid missing or repeating changes. Done when: changing a term's weight in the database changes suggestions within seconds, with no errors during the swap.

5. 05

   Record searches as popularity

   ~2h

   Add POST /searches { term } that counts searches in memory and writes the increases to PostgreSQL in batches every few seconds, instead of one update per search. Limit how fast one client can post searches. Make sure a crash loses at most the last few seconds of counts. Done when: popular searches rise in the suggestions over time, and the database receives few, batched writes.

6. 06

   Add metrics and limits

   ~1.5h

   Expose metrics with Micrometer through Actuator: suggestion latency (with percentiles), index size, time of the last successful refresh and refresh duration. Log a warning when the index hasn't refreshed for too long. Add a simple rate limit per client IP on the suggest endpoint. Done when: the metrics endpoint shows latency percentiles and the refresh time.

7. 07

   Test and measure

   ~2.5h

   Write integration tests with Testcontainers PostgreSQL: suggestions after startup, an update showing up after a refresh, deleted terms disappearing, and a restart rebuilding the same index. Write a small load test (for example with Gatling or a Java HttpClient loop against your own local server) and record the latency percentiles in README.md. Done when: the tests pass, and the measured latency meets the goal.

Resources

• ArticleTrie (Wikipedia)
• DocsSpring Boot reference documentation
• DocsAtomicReference (Java API)
• DocsMicrometer documentation
• DocsTestcontainers for Java