Conception d'un système de typeahead : comment fonctionne l'autocomplétion de recherche à grande échelle

Tapez « how to » dans un champ de recherche, et des suggestions apparaissent avant que vous ayez fini le mot suivant. Cette fonctionnalité répond à une requête à presque chaque frappe, pour chaque utilisateur, et elle doit sembler instantanée : des recherches sur les temps de réponse remontant à plusieurs décennies placent la limite du « le système réagit instantanément » à environ 0,1 seconde. Rien dans l'autocomplétion n'est difficile en soi. Le défi consiste à faire des choses simples dans un budget de latence serré, à un débit de requêtes très élevé, tout en gardant les suggestions fraîches et exemptes de ce que vous ne voulez jamais afficher.

Cet article conçoit un service de typeahead : exigences et capacité, index de préfixes top-k, service et sharding, pipeline de construction hors ligne, requêtes tendance, cache, personnalisation et filtrage, avec un diagramme des deux moitiés.

Exigences

Fonctionnelles :

• Renvoyer les 5 à 10 meilleures complétions d'un préfixe, classées surtout par popularité.
• Refléter les nouvelles tendances en quelques minutes, pas en quelques jours.
• Ne jamais afficher de suggestions contraires à vos règles.

Non fonctionnelles :

• Environ 100 ms de bout en bout, ce qui laisse au backend un budget de quelques dizaines de millisecondes une fois le réseau déduit.
• Haute disponibilité : si les suggestions échouent, la recherche fonctionne toujours, alors dégradez en douceur.
• Peu coûteux : cela s'exécute à chaque frappe.

Capacité

Supposons 50 millions d'utilisateurs quotidiens qui font chacun 10 recherches par jour, avec environ 6 requêtes de suggestion par recherche une fois que le client cesse d'en envoyer une par caractère :

Deux observations façonnent la conception. Les préfixes courts sont extrêmement répétitifs : tous ceux qui tapent « w » posent la même question. Et la réponse à un préfixe change lentement, si bien qu'elle peut être calculée à l'avance.

Le client fait la moitié du travail

• Debounce. Attendez 100 à 200 ms après la dernière frappe avant d'envoyer une requête, pour que les tapeurs rapides ne déclenchent pas une requête par caractère.
• Annulez les requêtes périmées. Quand un nouveau préfixe part, abandonnez le précédent et ignorez les réponses tardives d'un préfixe plus ancien.
• Mettez en cache localement. Si « how t » a renvoyé dix résultats qui commencent tous par « how to », le client peut les filtrer pour « how to » sans requête.
• Repliez-vous en silence. Si l'appel de suggestion échoue ou traîne, n'affichez rien ; la recherche doit continuer à fonctionner.

L'index de préfixes top-k

La structure classique est un trie, où chaque nœud est un préfixe et ses enfants le prolongent d'un caractère. Parcourir le trie et fouiller tout le sous-arbre à la recherche des requêtes les plus populaires au moment de la requête est trop lent pour les préfixes populaires. Précalculez plutôt la réponse : stockez à chaque nœud de préfixe les k meilleures complétions, déjà classées. Une recherche devient une simple lecture.

Beaucoup d'implémentations se passent complètement du trie à pointeurs et stockent une table plate du préfixe vers sa liste top-k, plafonnée à une longueur de préfixe maximale, car les préfixes très longs sont rares et peuvent basculer sur un chemin plus lent. En construire une à partir de comptages agrégés tient en quelques lignes :

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

Le résultat est en lecture seule et se charge en mémoire sur chaque nœud de service. Si vous exploitez déjà Elasticsearch, son completion suggester fournit la même idée sous forme de fonctionnalité : la documentation décrit des structures de données qui permettent des recherches rapides mais coûtent cher à construire et sont stockées en mémoire, exactement le compromis que fait cette conception.

Service et sharding

Le service de suggestion normalise le préfixe (minuscules, suppression des espaces, normalisation Unicode), lit la liste top-k dans l'index, y fusionne les résultats tendance et personnels, filtre et répond. Tout ce qu'il lit est en mémoire.

Quand l'index dépasse la capacité d'une machine, partitionnez-le. Partitionner par première lettre semble naturel, mais c'est très déséquilibré : bien plus de requêtes commencent par « s » que par « x ». Hachez plutôt le préfixe, ou découpez selon des plages de trafic mesuré, et répliquez chaque shard pour qu'une panne de nœud ne fasse que réduire la capacité. Comme l'index est reconstruit hors ligne, les répliques n'ont jamais à s'accorder sur des écritures : chacune charge le même snapshot.

Le pipeline de construction hors ligne

1. Collecter. Les frontaux de recherche journalisent chaque requête terminée dans un flux comme Kafka.
2. Agréger. Une tâche batch compte les requêtes sur une fenêtre, par exemple les 30 derniers jours, en pondérant davantage les jours récents, et écarte les requêtes rares sous un seuil pour protéger la vie privée et éliminer le bruit.
3. Filtrer. Appliquez listes de blocage et classifieurs de règles avant que quoi que ce soit ne devienne une suggestion.
4. Construire. Calculez l'index de préfixes comme ci-dessus et écrivez-le sous forme de snapshot versionné dans un stockage objet.
5. Déployer. Les nœuds de service chargent le nouveau snapshot à côté de l'ancien, basculent de façon atomique et gardent la version précédente pour un retour arrière rapide.

Des reconstructions horaires ou quotidiennes gardent l'index principal assez frais pour la plupart des requêtes.

Les requêtes tendance

Une actualité de dernière minute produit une nouvelle requête populaire en quelques minutes, bien avant la prochaine construction batch. Ajoutez une petite couche temps réel : un processeur de flux compte les requêtes sur des fenêtres glissantes, repère celles qui montent bien plus vite que leur niveau de base et les écrit, indexées par préfixe, dans un stockage rapide comme Redis. Le service de suggestion les fusionne avec les résultats batch. Gardez cette couche petite et filtrez-la sévèrement ; c'est là qu'une attaque coordonnée tenterait d'implanter des suggestions.

Du cache à chaque couche

Les préfixes courts sont les plus chauds et les plus faciles à mettre en cache, parce qu'ils sont identiques pour tout le monde. Les résultats personnalisés ne peuvent pas être mis en cache sur le CDN, l'une des raisons de garder une personnalisation légère.

Personnalisation, fautes de frappe et filtrage

• L'historique personnel. Mêler les requêtes récentes d'un utilisateur aux suggestions globales aide beaucoup et coûte peu si ces requêtes récentes vivent sur l'appareil ou dans un petit stockage par utilisateur.
• Les fautes de frappe. Une correspondance approximative à une modification près du préfixe sauve « pyhton ». Elle coûte plus cher : beaucoup de systèmes essaient d'abord les préfixes exacts et ne basculent sur l'approximation que si les résultats sont maigres.
• Le filtrage s'applique deux fois : hors ligne, avant qu'une requête n'entre dans l'index, et en ligne, contre une liste de blocage rapide qu'on peut mettre à jour en quelques minutes sans reconstruction.

Le diagramme du typeahead

Comment le lire :

• Le cadre en ligne est le chemin de chaque frappe : navigateur, cache CDN, passerelle API et service de suggestion.
• Le service de suggestion lit deux shards de préfixes en mémoire et le stockage de tendances Redis, puis fusionne et filtre les résultats.
• Le cadre hors ligne est le chemin de construction : journaux de requêtes depuis Kafka, tâche d'agrégation et snapshots d'index versionnés dans le stockage objet.
• L'arête en pointillé du stockage objet vers les shards est le chargement du snapshot, le seul lien entre les deux moitiés.
• Le bloc Markdown présente le budget de latence et les chiffres de capacité.

Dessiner clairement les systèmes à forte lecture

• Séparez en ligne et hors ligne. Les deux moitiés ont des budgets de latence, des modes de panne et des responsables différents, et le diagramme doit le montrer d'un coup d'œil.
• Montrez chaque couche de cache, avec son expiration. Dans un système à forte lecture, les caches constituent l'essentiel de l'architecture.
• Dessinez le lien unique entre les moitiés : ici, un snapshot versionné. Il explique comment les mises à jour atteignent les utilisateurs et comment fonctionne le retour arrière.
• Annotez le budget de latence sur le chemin en ligne.

Pour l'approche générale, voyez l'exemple de diagramme de conception de système. Le diagramme des stratégies de cache approfondit les couches de cache, et l'agrégation des journaux suit les modèles du diagramme d'architecture de pipeline de données.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez deux nœuds Cadre du pack Base : Online, per keystroke, et Offline, hourly build.
3. Dans le cadre en ligne, ajoutez un nœud Appareil du pack Réseau pour le navigateur, un CDN et une Passerelle API du pack Cloud, un nœud Instance de calcul pour le service de suggestion, deux nœuds Redis du pack Données pour les shards de préfixes et un autre nœud Redis pour les requêtes tendance.
4. Dans le cadre hors ligne, ajoutez un nœud Kafka du pack Données pour les journaux de requêtes, un nœud Instance de calcul du pack Cloud pour la tâche d'agrégation et un Magasin d'objets du pack Données pour les snapshots d'index.
5. Dessinez le chemin des requêtes de gauche à droite, le chemin de construction en dessous, et une arête en pointillé des snapshots vers les shards.
6. Ajoutez un bloc Markdown du pack Base avec le budget de latence et la capacité.

L'exemple utilise 13 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Quelle structure de données utilise-t-on pour l'autocomplétion ? Un trie, ou une table plate du préfixe vers les résultats, avec les k meilleures complétions précalculées pour chaque préfixe. Le précalcul transforme chaque recherche en une seule lecture en mémoire.

À quelle vitesse l'autocomplétion doit-elle répondre ? Environ 100 ms entre la frappe et les suggestions donnent une impression d'instantané. Une fois le réseau déduit, il reste au backend quelques dizaines de millisecondes, d'où un index en mémoire.

Comment les suggestions restent-elles à jour ? Un pipeline batch reconstruit l'index à partir des journaux de requêtes toutes les heures ou tous les jours, et une couche temps réel ajoute en quelques minutes les requêtes en forte hausse.

Faut-il envoyer une requête d'autocomplétion à chaque frappe ? Non. Appliquez un debounce de 100 à 200 ms côté client, annulez les requêtes périmées et réutilisez les résultats en cache pour les préfixes plus longs. Cela réduit nettement le volume de requêtes.

Comment écarter les suggestions offensantes ? Filtrez hors ligne avant que les requêtes n'entrent dans l'index, appliquez des seuils minimaux de popularité et vérifiez les résultats en ligne contre une liste de blocage que vous pouvez mettre à jour rapidement.

Commencez gratuitement — un siège, sans carte bancaire.