オートコンプリート付き商品検索システムの設計

1. 概要

検索ボックスに「ao th」と入力すると、ユーザーは「áo thun nam」「áo thun cotton」を100ms以下で見たいと思います。この記事では完全なケーススタディを紹介します：要件、データモデル、API、書き込みおよび読み込みフロー、そしてホットキー、一貫性、トラフィック急増などの課題です。

読み終わったら、Spring Boot、Redis、Kafkaを使ってオートコンプリートサービスを構築できます。また、各設計上の決定がなぜ選択されたかについても理解できるでしょう。

2. 要件

2.1. 機能要件

• ユーザーは最低2文字入力します。システムは最大10個の提案を人気度の順で返します。
• アクセント記号の有無に関わらず、マッチします：「ao thun」は「Áo thun」にマッチします。
• 提案は2つのソースから取得されます：ユーザーが検索したキーワード、および商品名、ブランド、カテゴリーです。
• 管理者は敏感なキーワードをブロックできます。ブロックされたキーワードは提案から消えなければなりません。

2.2. スケールと制約

• 約200万個の提案フレーズと500万個の商品があります。
• 通常トラフィックは5,000リクエスト/秒です。フラッシュセール時は30,000リクエスト/秒になります。
• サーバー側のp99レイテンシーは50ms以下です。
• 許容される鮮度は1～2分です。これは最終的な一貫性：ホットなキーワードが直ちに表示されない可能性があり、それは許容可能です。

最後の制約は非常に重要です。これにより、書き込みフロー（スコア更新）を読み込みフロー（提案を返す）から完全に分離できます。

3. 全体アーキテクチャ

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)──┘

主なアイデアは各prefixに対してあらかじめtop-Kを計算することです。「ao」「ao t」「ao th」などの各prefixに対して、Redis sorted setを1つ持ちます。このsetは最高スコアの最大50個の項目のみを保持します。読み込み時には、ZREVRANGEコマンド1つで済み、計算量はO(log N + K)です。スキャンや計算は不要です。

メモリ推定：200万フレーズ、prefix制限は20文字。重複するprefixをマージすると約1,000万個のキーになります。各キーは約40バイトの50個の要素を保持し、オーバーヘッドを含めて合計約20GB。この数字は3シャードのレプリカ付きRedis Clusterで対応可能です。

4. データモデル

ソースデータはPostgreSQLに保存されます。Redisは読み取り専用インデックスであり、いつでも再構築できます。

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側には3種類のキーがあります：

ac:score            ZSET  member=display_text, score=グローバルスコア合計
ac:p:{prefix}       ZSET  member=display_text, score=スコア合計（最大50個の要素）
ac:blocked          SET   ブロックされた display_text

5. ベトナム語の正規化とprefix生成

ここが最も間違いやすい部分です。アクセント記号を削除し、小文字に変換し、空白を統合し、Normalizerが分解できない文字「đ」を特別に処理する必要があります。

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 」と「ao」は trim 後に同じになる
        }
        return result;
    }
}

Form.NFDは「á」を「a」と結合記号に分解します。その後、正規表現\p{M}が記号部分を削除します。関数prefixesは空白で終わるprefixをスキップします。理由：ユーザーのクエリはすでにtrim()されているため、キーac:p:ao は決して読まれません。

主要な動作のテスト：

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");
    }
}

入力「ao thun」、minLen = 2、maxLen = 5の場合、長さ2～5の部分文字列は「ao」、「ao 」、「ao t」、「ao th」です。要素「ao 」は空白で終わるため、除外されます。

注意： この方法は語句の最初からのマッチングのみです。「thun」から「áo thun」を提案するには、各単語の開始位置から追加のprefixを生成する必要があります：「thun nam」、「nam」など。その代わり、メモリは約3～4倍増加します。有効にする前にテストしてください。

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）はlimitを1～10の範囲に制限するため、クライアントは10,000個の要素を要求できません。リクエスト例：

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

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

クライアント側は約150msのdebounceを行い、ユーザーが入力を続けると古いリクエストをキャンセルする必要があります。これだけでリクエスト量を60～70%削減できます。

7. 読み込みフロー

必要な依存関係を追加します：

<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>

読み込みサービスは2階層のキャッシュを使用します：JVM内のCaffeineと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);
    }
}

注目すべき点：

• CaffeineのCache.get(key, loader)はキーごとにatomicな操作です。1,000個のthreadが同時に prefix「ao」をキャッシュが空の状態で要求する場合、1つのthreadだけがRedisを呼び出します。他のthreadは結果を待ちます。これはrequest coalescingテクニックで、cache stampedeに対する対策です。
• 20文字を超えるクエリは最初の20文字のキーを使用します。その後、filter(startsWith)ステップで正確にフィルタリングします。
• フィルタリングステップは正規化済みのqueryを使用し、keyは使用しません。これにより、結果は常にユーザーが入力した文字列と正確にマッチします。

8. 書き込みフロー：スコア集約とインデックス更新

ユーザーが検索するたびに、Search Serviceはsearch-eventsトピックにイベントを送信します。各イベントが20個のZADDコマンドを引き起こすと、Redisはすぐに過負荷になります。そのため、メモリ内でスコアを集約します。

@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は多くのthreadが同時にインクリメントしても、AtomicLongよりも競合が少なくなります。30秒ごとに、各フレーズは1回だけの書き込みを生成します、その期間に10,000回検索されても。必ず@EnableSchedulingを設定クラスに追加してください。

注意： 小さな隙間があります。イベントがremoveとsum()の間に到着する可能性があり、新しいLongAdderに落ち込み、次のフラッシュで処理されます。インスタンスがフラッシュ前に死ぬと、最大30秒のスコアが失われます。提案ランキング問題ではこの誤差は受け入れられます。金銭的な問題ではそうではありません。

Indexerはグローバルスコアを更新し、その後、スコア合計を各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;
        });
    }
}

各行の処理：

• ZINCRBY ac:scoreはスコアをatomicに加算し、新しい合計を返します。アプリケーション側で読み取り-修正-書き込みのステップはありません。
• ZADD ... GTは新しいスコアが現在のスコアより大きい場合のみ書き込みます。2つのインスタンスが同じフレーズをフラッシュすると、遅いインスタンスは古い合計を後に持ってきます。その古い合計は新しい合計を上書きできません。スコアは増加するだけなので、GTはロックなしで競合を解決するのに十分です。
• ZREMRANGEBYRANK key 0 -51はランクの低い要素を削除し、最高スコアの50個の要素を保持します。ブロックされたキーワードと長いクエリをフィルタリングするためのスペースを残すため、10個ではなく50個を保持します。
• Pipelineは1回のラウンドトリップで約40個のコマンドを送信します。各コマンドが1つのキーのみをタッチするため、PipelineはRedis Clusterで機能します。

注意： これらのコマンドをRedis Cluster上の複数キーのLua scriptに統合しないでください。キーac:p:*は異なるスロットに分散し、scriptはCROSSSLOTエラーを報告します。hash tagを使用して同じスロットに強制できますが、その場合すべてのロードが1つのshardに集中します。

Catalog Serviceはproduct-eventsトピックを通じて同様に処理します。新しい商品が作成されると、商品名は小さい初期スコアで追加されます。同じ商品のイベントが常に正しい順序で到着するようにするため、KafkaのキーとしてproductIdを使用してください。

9. 難しい点と対策

9.1. ホットキーとトラフィック急増

フラッシュセール「iPhone」が開始すると、何万人ものユーザーが同時に「ip」と入力します。キーac:p:ipはホットキーになり、1つのRedis shardがすべてを処理します。システムは層ごとに対策します：

1. クライアント側： debounce、最小2文字の長さ、古いリクエストのキャンセル。
2. Caffeine： 各インスタンスで30秒キャッシュします。短いprefixが大部分のトラフィックを占めるため、ヒット率は通常90%以上です。20個のインスタンスがある場合、Redisは1つのprefixに対して30秒ごとに最大約20個のリクエストを受け取ります。
3. Coalescing： セクション7で説明したように、同じキーの複数リクエストはRedisへの呼び出しを1回だけ生成します。
4. Redisレプリカ： レプリカからの読み取りを有効にする（LettuceでReadFrom.REPLICA_PREFERRED）して読み込み負荷を分散します。
5. Degrade： Redisがタイムアウトして30msを超えた場合、空のリストまたはあらかじめキャッシュされたグローバルホットフレーズのトップを返します。検索ボックスがページ全体をハング させないようにしてください。

9.2. キーワードブロック時の一貫性

ブロックされたキーワードは、キャッシュのTTLである30秒ではなく、数秒以内に消える必要があります。2ステップの方法で実現します：

• 管理者がキーワードをブロックします。システムはDB にblocked = trueを書き込み、ac:blockedに追加し、keyword-blockedイベントを発行します。
• 各インスタンスはこのイベントをリッスンします。インスタンスはメモリ内のSet<String>ブロックリストを更新し、local.invalidateAll()を呼び出します。読み込み時のfilterステップがブロックリストに属する要素を除外します。
• バックグラウンドジョブは、そのprefixに対してZREMを実行し、ac:scoreから削除してガベージコレクションを行います。

読み込み時のフィルタは即座に正確性を確保します。クリーンアップジョブはメモリを節約するためだけです。

9.3. インデックスの再構築

Redisがデータを失った、または正規化ルールを変更した場合、suggestionテーブルから再構築し、新しい名前空間に書き込みます、例えばac:v2:p:*。その後、読み込み設定をv2に変更しv1を削除します。これはインデックスのblue-green デプロイメント：ユーザーが不完全なインデックスを見ることはありません。

定期的に、ac:scoreをカラムsuggestion.scoreに同期する必要があります。このカラムは必要な場合に再構築するためのソースです。

10. この方法を使うべきではない場合

• ファジー検索が必要： ユーザーが「ao thn」と誤入力しても「áo thun」が表示されることを望みます。Prefix別top-Kではできません。ElasticsearchまたはOpenSearchでcompletion suggesterまたはsearch_as_you_typeを使用してください。
• パーソナライズされた提案： 各ユーザーが異なるリストを持っています。prefixごとのキーはグローバルなため、後ろにユーザーごとのre-rankingレイヤーを追加する必要があります。
• 小さなカタログ（数万の商品、数百リクエスト/秒）：normalized列に対してLIKE 'ao th%'を実行するPostgreSQLクエリとtext_pattern_opsインデックスで十分です。この問題のためにKafkaとRedis Clusterを構築しないでください。

11. 結論

数十万のリクエスト/秒に耐えられるオートコンプリートシステムの設計を見てきました。重要なポイントは4つの決定にあります：

• 各prefixのtop-Kをあらかじめ計算して、読み込みフローがZREVRANGEコマンド1つだけになるようにします。
• Kafkaを通じて書き込みフローを分離し、バッチでスコアを集約して、Redisが書き込みコマンドの洪水を受けないようにします。
• ZINCRBYとZADD GTを使用してロックなしで競合を処理します。
• Caffeineとrequest coalescingを使用してホットキーをブロックします。

ランキングスコアの最終的な一貫性を受け入れ、ブロックリストのように即座に正確である必要があるものは厳密に制御することは、ほとんどのECサイトにとって合理的なバランスです。この基盤から、製品が実際に必要な場合はファジー検索またはパーソナライズを追加できます。