System Design: Product Search with Autocomplete

1. Overview

Type “ao th” into the search box and the user expects to see “áo thun nam”, “áo thun cotton” instantly, within less than 100ms. This article walks through a complete case study: requirements, data model, API, write and read flows, then tackles challenges like hot keys, consistency, and traffic spikes.

After reading, you’ll be able to build an autocomplete service using Spring Boot, Redis, and Kafka. You’ll also understand why each design decision was made.

2. Requirements

2.1. Functional Requirements

• User types at least 2 characters. System returns up to 10 suggestions, ranked by popularity.
• Typing with or without diacritics matches: “ao thun” must match “Áo thun”.
• Suggestions come from two sources: search queries users enter and product names, brands, categories.
• Admins can block sensitive keywords. Blocked terms must disappear from suggestions.

2.2. Scale and Constraints

• Around 2 million suggestion phrases and 5 million products.
• Normal traffic: 5,000 req/s. During flash sales: 30,000 req/s.
• Server-side p99 latency under 50ms.
• Acceptable freshness is 1–2 minutes. This is eventual consistency: a newly hot keyword may not appear immediately, and that’s okay.

This last constraint is crucial. It lets us completely decouple the write path (updating scores) from the read path (serving suggestions).

3. Overall Architecture

Client ──(debounce 150ms)──> API Gateway ──> Autocomplete Service ──> Caffeine (local)
                                                     │                      │ miss
                                                     │                      v
                                                     │               Redis: ac:p:{prefix}
Search Service ──(search-events)──> Kafka ──> Aggregator ──(flush 30s)──> Redis
Catalog Service ──(product-events)──┘

The core idea is precomputing top-K for each prefix. Each prefix like “ao”, “ao t”, “ao th” has its own Redis sorted set. Each set holds at most 50 phrases with the highest scores. When reading, you only need one ZREVRANGE command with O(log N + K) complexity. No full scans, no computation needed.

Memory estimate: 2 million phrases, prefix limit 20 characters. After deduplicating prefixes, we have around 10 million keys. Each key holds 50 elements at around 40 bytes each, totaling about 20GB with overhead. This fits comfortably in a 3-shard Redis Cluster with replicas.

4. Data Model

Raw data lives in PostgreSQL. Redis is just a read-serving index and can be rebuilt anytime.

CREATE TABLE suggestion (
    id            BIGSERIAL PRIMARY KEY,
    display_text  VARCHAR(200) NOT NULL,          -- "Áo thun nam cotton"
    normalized    VARCHAR(200) NOT NULL UNIQUE,   -- "ao thun nam cotton"
    source        VARCHAR(20)  NOT NULL,          -- QUERY | PRODUCT | BRAND
    score         BIGINT       NOT NULL DEFAULT 0,
    blocked       BOOLEAN      NOT NULL DEFAULT FALSE,
    updated_at    TIMESTAMPTZ  NOT NULL DEFAULT now()
);

CREATE INDEX idx_suggestion_score ON suggestion (score DESC) WHERE blocked = FALSE;

Redis has three key types:

ac:score            ZSET  member=display_text, score=global score total
ac:p:{prefix}       ZSET  member=display_text, score=score total (max 50 elements)
ac:blocked          SET   blocked display_text values

5. Vietnamese Normalization and Prefix Generation

This is the easiest part to get wrong. You must remove diacritics, convert to lowercase, collapse whitespace, and handle “đ” separately because Normalizer doesn’t decompose it.

public final class TextNormalizer {

    private static final Pattern MARKS = Pattern.compile("\\p{M}+");
    private static final Pattern SPACES = Pattern.compile("\\s+");

    private TextNormalizer() {}

    public static String normalize(String input) {
        if (input == null) return "";
        String s = Normalizer.normalize(input, Normalizer.Form.NFD);
        s = MARKS.matcher(s).replaceAll("")
                 .replace('đ', 'd').replace('Đ', 'D')
                 .toLowerCase(Locale.ROOT);
        return SPACES.matcher(s).replaceAll(" ").trim();
    }

    public static List<String> prefixes(String normalized, int minLen, int maxLen) {
        List<String> result = new ArrayList<>();
        int end = Math.min(normalized.length(), maxLen);
        for (int i = minLen; i <= end; i++) {
            String p = normalized.substring(0, i);
            if (!p.endsWith(" ")) result.add(p); // "ao " is the same as "ao" after trim
        }
        return result;
    }
}

Form.NFD decomposes “á” into “a” and a combining mark. The regex \p{M} then removes the mark portion. The prefixes function skips prefixes that end with whitespace. Reason: user queries are already trim()’d, so the key ac:p:ao will never be read.

Test for core behavior:

class TextNormalizerTest {

    @Test
    void shouldRemoveVietnameseDiacritics() {
        assertThat(TextNormalizer.normalize("  Áo Thun ĐỎ   nam "))
            .isEqualTo("ao thun do nam");
    }

    @Test
    void shouldGeneratePrefixesWithoutTrailingSpace() {
        assertThat(TextNormalizer.prefixes("ao thun", 2, 5))
            .containsExactly("ao", "ao t", "ao th");
    }
}

With input "ao thun", minLen = 2 and maxLen = 5, substrings of length 2 to 5 are "ao", "ao ", "ao t", "ao th". The element "ao " is excluded because it ends with whitespace.

Note: This approach only matches from the beginning of a phrase. To also have “thun” suggest “áo thun”, generate prefixes starting from each word: “thun nam”, “nam”… In exchange, memory usage increases by 3–4x. Measure before enabling.

6. API

@RestController
@RequestMapping("/api/v1/autocomplete")
public class AutocompleteController {

    private final AutocompleteService service;

    public AutocompleteController(AutocompleteService service) {
        this.service = service;
    }

    public record SuggestResponse(String query, List<String> suggestions) {}

    @GetMapping
    public SuggestResponse suggest(@RequestParam("q") String q,
                                   @RequestParam(defaultValue = "10") int limit) {
        int safeLimit = Math.clamp(limit, 1, 10);
        return new SuggestResponse(q, service.suggest(q, safeLimit));
    }
}

Math.clamp (Java 21) bounds limit to 1–10, so clients can’t request 10,000 items. A sample request:

GET /api/v1/autocomplete?q=ao%20th&limit=3

{"query":"ao th","suggestions":["Áo thun nam","Áo thun cotton","Áo thun oversize"]}

The client should debounce by ~150ms and cancel old requests as the user continues typing. This alone reduces request volume by 60–70%.

7. Read Path

Add required dependencies:

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
<dependency>
    <groupId>org.springframework.kafka</groupId>
    <artifactId>spring-kafka</artifactId>
</dependency>
<dependency>
    <groupId>com.github.ben-manes.caffeine</groupId>
    <artifactId>caffeine</artifactId>
</dependency>

The read service uses two cache layers: Caffeine in the JVM and Redis.

@Service
public class AutocompleteService {

    static final int MAX_PREFIX = 20;
    private final StringRedisTemplate redis;
    private final Cache<String, List<String>> local = Caffeine.newBuilder()
            .maximumSize(200_000)
            .expireAfterWrite(Duration.ofSeconds(30))
            .build();

    public AutocompleteService(StringRedisTemplate redis) {
        this.redis = redis;
    }

    public List<String> suggest(String rawQuery, int limit) {
        String query = TextNormalizer.normalize(rawQuery);
        if (query.length() < 2) return List.of();
        String key = query.length() > MAX_PREFIX ? query.substring(0, MAX_PREFIX) : query;

        return local.get(key, this::loadFromRedis).stream()
                .filter(s -> TextNormalizer.normalize(s).startsWith(query))
                .limit(limit)
                .toList();
    }

    private List<String> loadFromRedis(String prefix) {
        Set<String> top = redis.opsForZSet().reverseRange("ac:p:" + prefix, 0, 49);
        return top == null ? List.of() : List.copyOf(top);
    }
}

Key points:

• Caffeine’s Cache.get(key, loader) is atomic per key. If 1,000 threads query prefix “ao” when cache is empty, only one thread calls Redis. The other threads wait for the result. This is request coalescing, which prevents cache stampede.
• Queries longer than 20 characters use the key of the first 20 characters. The filter(startsWith) step then filters precisely.
• The filter step uses the query that’s been normalized, not key. This ensures results always match exactly what the user typed.

8. Write Path: Score Aggregation and Index Update

Each time a user searches, Search Service fires an event to the search-events topic. If each event spawns twenty ZADD commands, Redis overloads immediately. So we batch and aggregate scores in memory first.

@Component
public class SearchEventAggregator {

    private final ConcurrentHashMap<String, LongAdder> pending = new ConcurrentHashMap<>();
    private final AutocompleteIndexer indexer;

    public SearchEventAggregator(AutocompleteIndexer indexer) {
        this.indexer = indexer;
    }

    @KafkaListener(topics = "search-events", groupId = "autocomplete-aggregator")
    public void onSearch(String displayQuery) {
        pending.computeIfAbsent(displayQuery.trim(), k -> new LongAdder()).increment();
    }

    @Scheduled(fixedDelay = 30_000)
    public void flush() {
        for (String phrase : List.copyOf(pending.keySet())) {
            LongAdder adder = pending.remove(phrase);
            if (adder != null) indexer.addScore(phrase, adder.sum());
        }
    }
}

LongAdder handles many threads incrementing concurrently with less contention than AtomicLong. Every 30 seconds, each phrase generates only one write, even if it was searched 10,000 times. Remember to add @EnableScheduling to your config class.

Note: There’s a small gap. An event can arrive right between remove and sum(), fall into a new LongAdder, and be flushed next time. If an instance dies before flushing, you lose at most 30 seconds of scores. For ranking suggestions, this error margin is acceptable. For money, it’s not.

The indexer updates the global score, then pushes the new total to each prefix:

@Component
public class AutocompleteIndexer {

    static final int KEEP_PER_PREFIX = 50;
    private final StringRedisTemplate redis;

    public AutocompleteIndexer(StringRedisTemplate redis) {
        this.redis = redis;
    }

    public void addScore(String phrase, long delta) {
        Double total = redis.opsForZSet().incrementScore("ac:score", phrase, delta);
        if (total == null) return;
        byte[] member = phrase.getBytes(StandardCharsets.UTF_8);
        List<String> prefixes = TextNormalizer.prefixes(
                TextNormalizer.normalize(phrase), 2, AutocompleteService.MAX_PREFIX);

        redis.executePipelined((RedisCallback<Object>) conn -> {
            for (String p : prefixes) {
                byte[] key = ("ac:p:" + p).getBytes(StandardCharsets.UTF_8);
                conn.zSetCommands().zAdd(key, total, member, RedisZSetCommands.ZAddArgs.empty().gt());
                conn.zSetCommands().zRemRange(key, 0, -(KEEP_PER_PREFIX + 1));
            }
            return null;
        });
    }
}

What each line does:

• ZINCRBY ac:score atomically adds the score and returns the new total. No read-modify-write on the app side.
• ZADD ... GT only writes if the new score is greater than the current one. Suppose two instances flush the same phrase; the slower one carries an old total. That old total won’t overwrite the new one. Since scores only increase, GT is sufficient to resolve conflicts without locking.
• ZREMRANGEBYRANK key 0 -51 removes low-rank elements, keeping the top 50 by score. We keep 50 instead of 10 to have room for filtering blocked terms and longer queries.
• The pipeline sends about 40 commands in one round-trip. Pipelining works well on Redis Cluster because each command touches only one key.

Note: Don’t combine these commands into a multi-key Lua script on Redis Cluster. The keys ac:p:* are in different slots, and the script will error with CROSSSLOT. You can use hash tags to force them into one slot, but then all load concentrates on one shard.

Catalog Service handles similarly via the product-events topic. When a new product is created, its name is added with a low initial score. Use productId as the Kafka key so events for the same product always arrive in order.

9. Challenges and Solutions

9.1. Hot Keys and Traffic Spikes

When a flash sale for “iPhone” starts, tens of thousands type “ip” at once. The key ac:p:ip becomes a hot key and one Redis shard bears all the load. The system addresses this layer by layer:

1. Client: debounce, minimum length 2 characters, cancel old requests.
2. Caffeine: cache for 30 seconds in each instance. Short prefixes dominate traffic, so hit rates are usually above 90%. With 20 instances, Redis receives at most ~20 requests per 30 seconds per prefix.
3. Coalescing: as mentioned in section 7, multiple requests for the same key create only one Redis call.
4. Redis replica: enable reading from replicas (ReadFrom.REPLICA_PREFERRED in Lettuce) to distribute read load.
5. Degrade: if Redis times out beyond 30ms, return an empty list or top global hot phrases cached locally. Don’t let the search box hang the entire page.

9.2. Consistency When Blocking Keywords

Blocked terms must disappear within seconds, not 30 seconds per cache TTL. The approach has two steps:

• Admin blocks a keyword. System writes blocked = true to DB, adds to ac:blocked, and emits a keyword-blocked event.
• Each instance listens for this event. It updates an in-memory Set<String> blocklist, then calls local.invalidateAll(). The filter step during reads excludes blocked items.
• A background job runs ZREM on that term’s prefixes and removes it from ac:score for cleanup.

The read-time filter ensures correctness immediately. The cleanup job just saves memory.

9.3. Rebuilding the Index

Redis loses data, or you change normalization rules? Then you rebuild from the suggestion table and write to a new namespace, like ac:v2:p:*. Then switch the read config to v2 and delete v1. This is blue-green for indexes: users never see a partially built index.

Periodically, sync ac:score back to the suggestion.score column. This column is the source for rebuilds.

10. When NOT to Use This Approach

• Fuzzy search needed: user types “ao thn” and still wants “áo thun” to appear. Top-K by prefix can’t do this. Use Elasticsearch/OpenSearch with completion suggester or search_as_you_type.
• Personalized suggestions: each user sees a different list. Keys by prefix are global, so you need an extra re-ranking layer per user after.
• Small catalog (tens of thousands of products, hundreds of req/s): a PostgreSQL query with LIKE 'ao th%' on the normalized column indexed with text_pattern_ops is enough. Don’t build Kafka and Redis Cluster for this.

11. Conclusion

You’ve just designed an autocomplete system that handles tens of thousands of requests per second. The key decisions are:

• Precompute top-K for each prefix, so the read path is just one ZREVRANGE command.
• Decouple writes via Kafka and batch aggregate scores, so Redis isn’t flooded with writes.
• Use ZINCRBY and ZADD GT to handle conflicts without locks.
• Block hot keys with Caffeine plus request coalescing.

Accept eventual consistency for ranking scores, but enforce strict consistency for parts that must be right immediately, like blocklists. This is a reasonable trade-off for most e-commerce platforms. From this foundation, you can add fuzzy search or personalization when products really need it.