La latence médiane d’un index HNSW est rarement le problème. Ce sont les percentiles hauts qui font échouer un SLA, et leurs causes diffèrent de celles qui pilotent la médiane.
Le paramètre qui gouverne le compromis
À la requête, HNSW descend les couches du graphe puis explore la couche de base en maintenant une file dynamique de taille efSearch contenant les meilleurs voisins rencontrés. Ce paramètre est le levier principal : l’augmenter élargit l’exploration, améliore le rappel et allonge la recherche de façon à peu près proportionnelle. Le rendement est décroissant — le rappel plafonne bien avant que le coût ne cesse de croître.
Deux paramètres de construction interviennent en amont. M fixe le nombre de voisins conservés par nœud, et efConstruction la qualité du graphe bâti à l’insertion. Un graphe construit avec un efConstruction trop faible produit des voisinages médiocres, qu’il faudra compenser à la requête par un efSearch plus élevé. Autrement dit, on paie à chaque requête ce qu’on a économisé une fois à la construction.
Pourquoi la queue diverge
La médiane reflète une requête typique sur un graphe bien connecté. Les percentiles hauts agrègent des situations différentes.
Le filtrage par métadonnées est la première cause. Quand un prédicat est très sélectif, le parcours du graphe rencontre majoritairement des nœuds rejetés et doit poursuivre l’exploration bien au-delà de efSearch pour réunir k résultats valides. Le coût explose exactement sur les requêtes les plus restrictives. Deux atténuations : maintenir des index séparés par partition quand l’attribut est de faible cardinalité et stable — par exemple le tenant — et basculer vers un parcours exhaustif du sous-ensemble quand le prédicat descend sous un seuil de sélectivité, un balayage linéaire sur quelques milliers de vecteurs étant plus rapide qu’un parcours de graphe contrarié.
Les défauts de page viennent ensuite. Tant que l’index tient en mémoire, chaque saut du graphe est un accès mémoire. Dès qu’il déborde, les sauts deviennent des lectures disque aux adresses peu prévisibles, et le parcours en cumule des dizaines. Une occupation proche de la limite ne dégrade pas la médiane de façon visible mais épaissit nettement la queue.
Les pauses du ramasse-miettes et les réplicas en retard complètent le tableau, avec un effet plus marqué quand un même nœud sert les requêtes et absorbe les écritures.
Le coût des écritures
HNSW accepte les insertions incrémentales, mais l’ajout d’un nœud modifie les listes de voisins existantes et prend un verrou. Sous forte charge d’écriture, ces verrous se voient directement sur les latences de lecture. Les suppressions sont pires : elles sont généralement logiques, le nœud restant dans le graphe comme point de passage marqué supprimé. Le graphe se remplit alors de nœuds qui coûtent à traverser sans jamais figurer dans les résultats.
La réponse est une reconstruction périodique. On rebâtit l’index hors ligne à partir des vecteurs vivants, on le valide sur un jeu d’évaluation figé, puis on bascule le trafic. Séparer les réplicas de lecture du nœud qui absorbe les écritures évite par ailleurs que les pics d’ingestion ne se propagent aux requêtes.
Une démarche de mesure
Mesurez la latence côté serveur et côté client : l’écart révèle la file d’attente et la sérialisation, souvent non négligeable quand la réponse embarque les vecteurs. Segmentez les percentiles par sélectivité de filtre plutôt que de les agréger, sans quoi la cause principale reste invisible. Enfin, tracez systématiquement rappel et latence ensemble : un p99 réduit de moitié en abaissant efSearch n’est pas un gain si le rappel a chuté avec lui.