FR
FrançaisEspañolDeutschPortuguêsEnglishTiếng Việt한국어日本語简体中文
Accueil / Architecture et conception / Cas concrets

Conception d'un système d'autocomplétion de recherche

Cris The Dev · 12/10/2026 · 11 min de lecture · 84

1. Vue d’ensemble

Vous tapez « ao th » dans la barre de recherche, et vous voulez voir aussitôt « áo thun nam », « áo thun cotton » en moins de 100 ms. Cet article vous guide à travers une étude de cas complète : exigences, modèle de données, API, flux d’écriture et de lecture, puis les défis comme les clés chaudes, la cohérence et les pics de charge.

À la fin, vous pourrez bâtir un service d’autocomplétion avec Spring Boot, Redis et Kafka. Vous comprendrez aussi pourquoi chaque choix de conception a été fait.

2. Exigences

2.1. Exigences fonctionnelles

  • L’utilisateur tape au minimum 2 caractères. Le système retourne au maximum 10 suggestions, classées par popularité.
  • La saisie accentuée ou non accentuée doit correspondre : « ao thun » doit correspondre à « Áo thun ».
  • Les suggestions proviennent de deux sources : les requêtes utilisateur et les noms de produits, marques, catégories.
  • L’administrateur peut bloquer les termes sensibles. Un terme bloqué doit disparaître des suggestions.

2.2. Échelle et contraintes

  • Environ 2 millions de cumulatifs et 5 millions de produits.
  • Trafic normal : 5 000 requêtes/seconde. Pendant une vente flash : 30 000 requêtes/seconde.
  • Latence p99 côté serveur inférieure à 50 ms.
  • Fraîcheur acceptable : 1–2 minutes. C’est une cohérence à terme : un terme venant de devenir tendance peut ne pas apparaître immédiatement, et c’est acceptable.

Cette dernière contrainte est cruciale. Elle permet de découpler complètement le flux d’écriture (mise à jour des scores) du flux de lecture (retour des suggestions).

3. Architecture générale

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

L’idée maîtresse est de pré-calculer le top-K pour chaque préfixe. Chaque préfixe comme « ao », « ao t », « ao th » a son propre sorted set Redis. Ce set ne garde que 50 cumulatifs avec les scores les plus élevés. À la lecture, vous n’avez besoin que d’une seule commande ZREVRANGE avec une complexité O(log N + K). Pas de scan, pas de calcul.

Estimation mémoire : 2 millions de cumulatifs, limite de préfixe 20 caractères. Après fusion des préfixes identiques, nous avons environ 10 millions de clés. Chaque clé contient 50 éléments d’environ 40 octets, pour un total d’environ 20 Go incluant l’overhead. Cela tient dans un Redis Cluster à 3 shards avec replicas.

4. Modèle de données

Les données brutes sont dans PostgreSQL. Redis n’est qu’un index pour servir les lectures et peut être reconstruit à tout moment.

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;

Côté Redis, trois types de clés :

ac:score            ZSET  member=display_text, score=score global cumulatif
ac:p:{prefix}       ZSET  member=display_text, score=score cumulatif (max 50 éléments)
ac:blocked          SET   display_text bloqués

5. Normalisation vietnamienne et génération de préfixes

C’est la partie la plus facile de se tromper. Vous devez ôter les accents, passer en minuscules, fusionner les espaces, et traiter le caractère « đ » séparément car Normalizer ne le divise pas.

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 " fusionné avec "ao" après trim
        }
        return result;
    }
}

Form.NFD divise « á » en « a » et une marque de combinaison. La regex \p{M} efface ensuite la partie marque. La fonction prefixes ignore les préfixes se terminant par un espace. Raison : la requête utilisateur a déjà été trim(), donc la clé ac:p:ao ne sera jamais lue.

Test du comportement principal :

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

Avec input "ao thun", minLen = 2 et maxLen = 5, les substrings de longueur 2 à 5 sont "ao", "ao ", "ao t", "ao th". L’élément "ao " est exclu car il se termine par un espace.

Note : Cette approche ne correspond qu’à partir du début du terme. Pour que « thun » suggère aussi « áo thun », vous devez générer des préfixes depuis chaque position de début : « thun nam », « nam »… En retour, la mémoire augmente d’environ 3–4 fois. Mesurez avant d’activer.

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) limite limit dans la plage 1–10, donc le client ne peut pas demander 10 000 éléments. Une requête d’exemple :

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

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

Côté client, vous devriez debounce autour de 150 ms et annuler les anciennes requêtes quand l’utilisateur tape plus. Rien que cela réduit de 60–70 % le volume de requêtes.

7. Flux de lecture

Ajoutez les dépendances nécessaires :

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

Le service de lecture utilise deux niveaux de cache : Caffeine dans la JVM et 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);
    }
}

Points à noter :

  • Cache.get(key, loader) de Caffeine est atomique par clé. Si 1 000 threads demandent le préfixe « ao » au moment où le cache est vide, seul un thread appelle Redis. Les autres threads attendent le résultat. C’est la technique de coalescence de requêtes, qui prévient le cache stampede.
  • Une requête plus longue que 20 caractères utilisera la clé des 20 premiers caractères. L’étape filter(startsWith) ensuite filtre avec précision.
  • Le filtre utilise query normalisé, pas key. De cette façon, le résultat correspond toujours exactement à la chaîne tapée par l’utilisateur.

8. Flux d’écriture : agrégation des scores et mise à jour de l’index

Chaque fois qu’un utilisateur effectue une recherche, le Search Service envoie un événement vers le topic search-events. Si chaque événement déclenchait une vingtaine de commandes ZADD, Redis serait surchargé immédiatement. C’est pourquoi nous agrégeons les scores en mémoire d’abord.

@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 supporte bien plusieurs threads incrémentant le compteur simultanément avec moins de contention qu’AtomicLong. Tous les 30 secondes, chaque terme génère une seule écriture, même s’il a été recherché 10 000 fois dans cet intervalle. N’oubliez pas d’ajouter @EnableScheduling à votre classe de configuration.

Note : Il y a une petite faille. Un événement peut arriver juste au moment du remove et du sum(), tombant dans une nouvelle LongAdder qui sera vidée au prochain cycle. Si l’instance meurt avant le flush, vous perdez au maximum 30 secondes de scores. Pour un problème de classement de suggestions, c’est acceptable. Pour un problème monétaire, non.

L’indexer met à jour le score global, puis pousse le score cumulatif dans chaque préfixe :

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

Chaque ligne fait quoi :

  • ZINCRBY ac:score ajoute atomiquement le score et retourne la nouvelle somme. Pas de lecture–modification–écriture côté application.
  • ZADD ... GT écrit seulement si le nouveau score est supérieur au score existant. Supposons que deux instances vident le même terme, l’instance plus lente apporte la somme ancienne ensuite. Cette ancienne somme ne remplacera pas la nouvelle somme. Puisque le score ne fait que croître, GT suffit pour résoudre la contention sans verrous.
  • ZREMRANGEBYRANK key 0 -51 supprime les éléments de faible rang, en gardant 50 éléments de score élevé. Nous en gardons 50 au lieu de 10 pour laisser de la place aux filtres de termes bloqués et aux requêtes longues.
  • Le pipeline envoie environ 40 commandes en un seul aller-retour. Le pipeline fonctionne bien sur Redis Cluster car chaque commande ne touche qu’une seule clé.

Note : Ne regroupez pas ces commandes dans un script Lua multi-clés sur Redis Cluster. Les clés ac:p:* se trouvent dans plusieurs slots et le script rapportera une erreur CROSSSLOT. Vous pouvez les forcer dans le même slot avec une hash tag, mais alors la charge entière s’accumule sur un seul shard.

Le Catalog Service fonctionne de manière similaire via le topic product-events. Quand un nouveau produit est créé, son nom est ajouté avec un score d’initialisation bas. Utilisez l’productId comme clé Kafka pour que les événements du même produit arrivent toujours dans le bon ordre.

9. Défis et solutions

9.1. Clés chaudes et pics de charge

Quand une vente flash « iPhone » commence, des dizaines de milliers de personnes tapent « ip » en même temps. La clé ac:p:ip devient chaude et un seul shard Redis porte toute la charge. Le système résout le problème couche par couche :

  1. Client : debounce, longueur minimale 2 caractères, annulation des anciennes requêtes.
  2. Caffeine : cache 30 secondes dans chaque instance. Les préfixes courts représentent la majorité du trafic, donc le taux de hit dépasse généralement 90 %. Avec 20 instances, Redis reçoit au maximum environ 20 requêtes toutes les 30 secondes pour un seul préfixe.
  3. Coalescence : comme expliqué à la section 7, plusieurs requêtes avec la même clé ne font qu’un seul appel Redis.
  4. Replica Redis : activez la lecture depuis les replicas (ReadFrom.REPLICA_PREFERRED dans Lettuce) pour partager la charge de lecture.
  5. Dégradation : si Redis timeout dépasse 30 ms, retournez une liste vide ou les meilleurs cumulatifs globaux pré-cachés. N’abandonnez pas la page entière parce que le champ de recherche se fige.

9.2. Cohérence lors du blocage de termes

Un terme bloqué doit disparaître en quelques secondes, pas en 30 secondes selon la TTL du cache. La solution comprend deux étapes :

  • L’administrateur bloque un terme. Le système écrit blocked = true dans la DB, l’ajoute à ac:blocked et émet un événement keyword-blocked.
  • Chaque instance écoute cet événement. L’instance met à jour un Set<String> blocklist en mémoire, puis appelle local.invalidateAll(). L’étape filter pendant la lecture exclut tous les éléments de la blocklist.
  • Un job en arrière-plan exécute ZREM sur les préfixes de ce terme et le supprime d’ac:score pour nettoyer la garbage.

Le filtre pendant la lecture garantit la précision immédiate. Le job de nettoyage ne sert que à économiser la mémoire.

9.3. Reconstruction de l’index

Redis perd ses données, ou vous changez les règles de normalisation ? Vous reconstruisez alors à partir de la table suggestion et écrivez dans un nouvel espace de noms, par exemple ac:v2:p:*. Puis vous basculez la lecture sur v2 et supprimez v1. C’est une stratégie blue-green pour l’index : l’utilisateur ne voit jamais l’index à moitié.

Périodiquement, vous devriez aussi synchroniser ac:score vers la colonne suggestion.score. Cette colonne est la source pour reconstruire au besoin.

10. Quand NE PAS utiliser cette approche

  • Besoin de recherche approximative : l’utilisateur tape « ao thn » et veut quand même « áo thun ». Top-K par préfixe ne le fait pas. Utilisez Elasticsearch/OpenSearch avec completion suggester ou search_as_you_type.
  • Suggestions personnalisées : chaque personne a une liste différente. Les clés par préfixe sont globales, donc vous devez ajouter un re-ranking par utilisateur après.
  • Petit catalogue (quelques dizaines de milliers de produits, quelques centaines de requêtes/seconde) : une requête PostgreSQL avec LIKE 'ao th%' sur la colonne normalized avec un index text_pattern_ops suffit. Ne construisez pas Kafka et Redis Cluster pour ce problème.

11. Conclusion

Vous venez de découvrir comment concevoir un système d’autocomplétion capable de gérer des dizaines de milliers de requêtes par seconde. Les quatre décisions critiques sont :

  • Pré-calculer le top-K pour chaque préfixe, pour que le flux de lecture ne soit qu’une seule commande ZREVRANGE.
  • Séparer l’écriture via Kafka et aggréger les scores par batch, pour que Redis ne reçoive pas une pluie de commandes d’écriture.
  • Utiliser ZINCRBY et ZADD GT pour résoudre la contention sans verrous.
  • Bloquer les clés chaudes avec Caffeine plus coalescence de requêtes.

Accepter une cohérence à terme pour le score de classement, mais garder un contrôle strict sur ce qui doit être exact, comme la blocklist, est un bon équilibre pour la plupart des marketplaces. À partir de cette fondation, vous pouvez ajouter la recherche approximative ou la personnalisation quand votre produit en a vraiment besoin.

system-designrediskafkaspring-bootautocomplete
Appli de l’auteurDeclutterClear similar photos, big videos and inbox clutteriOS · Android

Sur le même sujet