Search Typeahead

A search-as-you-type service. While you type it suggests the most popular queries beginning with your prefix, ranked by popularity; submitting a search records it and shifts the rankings. Suggestions are served from a distributed in-process cache in front of an in-memory trie, with PostgreSQL as the durable source of truth. A recency-aware "trending" mode promotes recently-searched queries, and search-count writes are batched so the database is never written to per keystroke.

Built in Java 21 with Spring Boot (embedded Tomcat) and plain JDBC over HikariCP. The frontend is a single static page served by the same app. The whole stack — app, PostgreSQL, and the dataset loader — runs under Docker Compose.

Features

• Prefix suggestions — top 10 by count, case-insensitive, empty / no-match handled
• Search submission with a stub response, recorded into popularity counts
• Distributed cache over logical nodes, routed by a CRC32 consistent-hash ring
• Trending mode — recency-aware ranking via exponential time decay
• Batched, aggregated writes — submissions are tallied and flushed in bulk
• A live web UI showing cache hit/miss, owning node, latency, and write reduction

Architecture

graph TB
    subgraph Client["FRONTEND (static page)"]
        UI["Search box · Suggestion menu · Trending board · Live stats"]
    end

    subgraph Server["BACKEND (Spring Boot / Tomcat)"]
        direction TB
        H["REST controllers<br/>/suggest · /search · /cache/* · /stats"]
        RING["Consistent-hash ring<br/>(CRC32 into a TreeMap, virtual nodes)"]
        TREND["Trending scorer<br/>(exponential decay, one score/query)"]
        H --> RING
    end

    subgraph CacheLayer["DISTRIBUTED CACHE (logical nodes, in-process)"]
        direction LR
        N0["node0<br/>prefix→top-10<br/>TTL + LRU"]
        N1["node1<br/>prefix→top-10<br/>TTL + LRU"]
        N2["node2<br/>prefix→top-10<br/>TTL + LRU"]
    end

    subgraph Serving["IN-MEMORY INDEX"]
        TRIE["Trie<br/>prefix walk + per-node top-10<br/>(immutable after build, lock-free reads)"]
    end

    subgraph WriteSide["WRITE PATH"]
        BUF["Write buffer<br/>(tally, aggregates repeats)<br/>flush on time OR size"]
    end

    subgraph Truth["SOURCE OF TRUTH"]
        PG[("PostgreSQL<br/>query→count<br/>durable, survives restart")]
    end

    UI -->|"GET /suggest?q=ip (debounced)"| H
    UI -->|"POST /search"| H

    RING -->|"read: pick owner"| N0
    RING --> N1
    RING --> N2

    N0 -.->|"miss"| TRIE
    N1 -.->|"miss"| TRIE
    N2 -.->|"miss"| TRIE

    TREND -.->|"recency feeds rerank"| TRIE

    H -->|"write: record search"| BUF
    H -->|"bump recency"| TREND
    BUF -->|"bulk flush (aggregated)"| PG
    PG -->|"startup: load + build"| TRIE

Loading

Four storage layers, each with one responsibility:

• PostgreSQL — durable source of truth (query, count); survives restarts and receives batched writes.
• Trie — in-memory prefix index built from PostgreSQL at startup, answering prefix queries via a precomputed top-10 at each node. Disposable; rebuilt on boot.
• Distributed cache — finished suggestion lists for hot prefixes, spread across logical nodes and routed by a consistent-hash ring.
• Write buffer — tallies submissions and flushes to PostgreSQL in batches.

Reasoning is in DESIGN.md; measured numbers are in PERFORMANCE.md. The shape of everything follows one fact: reads (every keystroke) dwarf writes (submissions), so reads are made nearly free and writes are deferred and aggregated.

Run with Docker (recommended)

Requirements: Docker and the AOL dataset. Nothing else — the JDK, Maven build, and PostgreSQL all run in containers.

1. Get the dataset

AOL query log (Kaggle: "AOL User Session Collection"):

https://www.kaggle.com/datasets/dineshydv/aol-user-session-collection-500k

Download and unzip it into this directory; you will get tab-separated files named user-ct-test-collection-NN.txt.

The dataset is not committed — it is large and, given the log's history, not ours to redistribute. Ingestion keeps only the query text; every user-identifying column is discarded.

2. Start the stack

docker compose up -d --build

This builds the app image (a multi-stage Maven build) and starts postgres (durable store, host port 5433) and app (the server, port 8080). The app waits for PostgreSQL to be healthy, creates its table if needed, and serves — even on an empty database, so the first boot never fails.

3. Load the dataset

A one-off ingest container (behind a Compose profile, so it does not run on every up) reads the file and bulk-loads (query, count):

AOL_FILE=user-ct-test-collection-02.txt docker compose run --rm ingest
docker compose restart app          # rebuild the trie from the loaded data

Ingestion normalizes queries (lowercase, trim, drop empty/-), aggregates counts, and bulk-loads them; one file yields ~1.24M unique queries. The trie is built once at startup, so the app is restarted to pick up freshly-loaded data.

4. Open the UI

Visit http://localhost:8080/. Type a prefix (goog, map, ebay), navigate with the arrow keys, submit with Enter or the button. The boards report each request's latency, cache hit/miss, owning node, and live write-buffer stats.

Stop with docker compose down (-v also wipes the database volume).

Run locally (without Docker for the app)

Requires JDK 21 and Maven. PostgreSQL is easiest as a container:

docker compose up -d postgres
mvn package
java -jar target/search-typeahead.jar ingest --file=user-ct-test-collection-02.txt
java -jar target/search-typeahead.jar

Connection settings default to jdbc:postgresql://localhost:5433/typeahead with user/password typeahead, overridable via JDBC_URL, DB_USER, DB_PASSWORD. Loading the full dataset into the trie takes a few seconds; give the JVM enough heap (JAVA_OPTS=-Xmx4g is set in the image).

API

Method	Path	Purpose	Notes
GET	/suggest?q=<prefix>	Top 10 prefix matches by count	Add &mode=trending for recency-aware ranking
POST	/search	Record a search, return stub	JSON body {"query":"…"}, returns {"message":"Searched"}
GET	/cache/debug?prefix=<p>	Owning node + hit/miss	Demonstrates consistent hashing
GET	/cache/stats	Per-node hits/misses/size
GET	/stats	Write-buffer stats	searches received, flushes, rows written

Examples

curl "http://localhost:8080/suggest?q=goog"
curl "http://localhost:8080/suggest?q=goog&mode=trending"
curl -X POST http://localhost:8080/search \
  -H "Content-Type: application/json" -d '{"query":"iphone"}'
curl "http://localhost:8080/cache/debug?prefix=goog"

Demonstrations

Consistent hashing

docker compose run --rm app ringtest

Prints each sample prefix's owner with 3 nodes, then adds a 4th and reports how many moved — only the keys in the new node's arcs relocate, the consistent-hashing property (~1/N remapped, not nearly all).

Performance

./scripts/benchmark.sh

Measures p95 latency (cache path vs trie path), cache hit rate, and write reduction through batching. Requires hey (brew install hey). Results and their reading are in PERFORMANCE.md.

Trending rise-and-fall

In the UI, switch to trending mode and watch a low-ranked query climb after a burst of searches, then settle back as its recency score decays. The half-life is a constant in Settings.java — shorten it for a live demo.

Project layout

src/main/java/com/typeahead/
  TypeaheadApplication.java   entrypoint: server / ingest / ringtest dispatch
  Settings.java               tuning constants
  AppConfig.java              Spring beans + startup trie build
  store/                      PostgreSQL access (JDBC + HikariCP)
  index/                      trie with per-node top-K
  cache/                      ring (CRC32 + TreeMap), node (TTL + LRU), facade
  buffer/                     write buffer (batching + aggregation)
  trending/                   recency scorer (exponential decay)
  api/                        REST controllers
  tools/                      ingest loader + ring demo
src/main/resources/
  application.properties
  static/index.html           frontend
scripts/benchmark.sh          performance measurement
Dockerfile                    multi-stage build (Maven -> JRE)
docker-compose.yml            postgres + app + one-off ingest

Notes and trade-offs

• Cache nodes are logical (objects in one JVM), simulating distribution; in production they would be separate processes or Redis, with identical routing.
• Batching means a hard crash loses buffered-but-unflushed searches — acceptable for ranking data; the clean-shutdown path flushes to shrink the window.
• The trie is immutable after the startup build, so reads are lock-free. Live count changes go to PostgreSQL via the buffer; the trie can be rebuilt periodically or tolerate slight staleness, which is fine for ranking.
• See DESIGN.md for the reasoning behind each choice.