[2009 WSDM] Défis de la construction de systèmes de recherche d’information à grande échelle

Principales dimensions et compromis d’un système de recherche d’information

• Lors de la conception d’un système, il faut équilibrer avec soin les compromis d’ingénierie entre les éléments suivants.
  • Nombre de documents indexés
  • Nombre de requêtes traitées par seconde (QPS)
  • Fraîcheur de l’index / vitesse de mise à jour
  • Latence des requêtes
  • Quantité d’informations stockées pour chaque document
  • Complexité / coût du calcul de score et des algorithmes de recherche
• La difficulté d’ingénierie tend à être proportionnelle au produit de ces paramètres.
• Tous ces éléments influencent les performances globales et le rapport performance/coût (performance par dollar).

Évolution de l’échelle du système (1999 vs 2009)

• Au cours des 10 dernières années, l’échelle du système et les exigences de performance ont radicalement changé.
  • # documents : ~70 millions → plusieurs milliards (~x100)
  • Nombre de requêtes traitées par jour : (~x1000)
  • Informations d’index par document : (~x3)
  • Latence de mise à jour : plusieurs mois → quelques minutes (~divisée par 10000)
  • Latence moyenne des requêtes : <1 seconde → <0,2 seconde (~divisée par 5)
  • Ressources système : plus de machines * machines plus rapides (~x1000)
• Comme ces paramètres évoluent continuellement, parfois de plusieurs ordres de grandeur, la conception du système doit elle aussi évoluer en permanence.
  • Une architecture adaptée à un instant donné (X) peut devenir très mauvaise à une échelle 10x ou 100x supérieure. (Il faut donc concevoir avec une croissance d’environ 10x en tête, tout en prévoyant une réécriture avant d’atteindre 100x.)
  • Il y a eu 7 refontes majeures au cours des 10 dernières années.

Architecture initiale du système (1997-1999)

• Phase projet de recherche (1997) :
  • Le serveur web frontend reçoit les requêtes et distribue le traitement vers les serveurs d’index et les serveurs de documents
  • Serveurs d’index : sharding par ID de document (docid)
  • Serveurs de documents : sharding par ID de document (docid)
• Principes de base :
  • Les documents reçoivent des ID entiers (docids) (les documents importants / de haute qualité reçoivent de petits ID)
  • Serveurs d’index : (requête) → renvoient une liste triée de (score, docid, ...). Sharding par docid, réplication (replication) pour augmenter la capacité. Coût en O(#requêtes * #documents dans l’index).
  • Serveurs de documents : (docid, requête) → génèrent (titre, extrait). Mappage docid → document complet sur disque. Sharding par docid. Coût en O(#requêtes).
• Système de serving (1999) :
  • Ajout de serveurs de cache et intégration du système publicitaire à la structure du projet de recherche
  • Exploitation de réplicas (Replicas) pour les shards de serveurs d’index et de documents
  • Caching : mise en cache à la fois des résultats d’index et des extraits de documents. Taux de hit du cache de 30 à 60 %. Contribution majeure à l’amélioration des performances et à la réduction de la latence des requêtes. (Attention toutefois aux pics importants de latence lors des mises à jour d’index / flush de cache.)

Stratégies de partitionnement de l’index

• Par document (By doc) : chaque shard contient l’index d’une partie des documents (choix de Google)
  • Avantages : traitement indépendant des requêtes par shard, conservation plus simple d’informations supplémentaires par document, moins de trafic réseau (requêtes/réponses)
  • Inconvénients : tous les shards doivent traiter la requête, pour une requête de K mots il faut O(K*N) seeks disque sur N shards
• Par mot (By word) : chaque shard contient l’index d’une partie des mots sur l’ensemble des documents
  • Avantages : une requête de K mots n’implique qu’au plus K shards, O(K) seeks disque
  • Inconvénients : bande passante réseau beaucoup plus élevée nécessaire (il faut regrouper en un point les informations par mot des documents correspondants), plus difficile de conserver des informations par document

Crawling et indexation initiaux (1998-1999)

• Crawling :
  • Système simple de crawling par batch : liste d’URL de départ → crawl des pages → extraction des liens et ajout à la file → arrêt une fois suffisamment de pages collectées
  • Points à considérer : éviter de surcharger un site donné, déterminer la priorité des pages non crawlées (ex. PageRank), gérer efficacement la file d’URL non crawlées, gérer les pannes machines
• Indexation :
  • Système simple d’indexation par batch, fondé sur de simples outils Unix
  • Problèmes : absence de checkpointing rendant les pannes machines très pénibles, absence de checksum sur les données source provoquant des erreurs de bits matérielles (aggravées par l’absence d’ECC/parité sur les premières machines, problème du « mostly sorted »), expérience d’« mémoire hostile et programmation hostile »
  • Solution : développement d’une abstraction de fichier permettant de stocker de petits checksums d’enregistrement et d’ignorer les enregistrements corrompus / de se resynchroniser

Méthodes de mise à jour de l’index (1998-1999)

• Périodicité : environ une fois par mois
• Processus :
  1. Attendre les heures de faible trafic
  2. Basculer une partie des réplicas hors ligne
  3. Copier le nouvel index vers les réplicas hors ligne
  4. Démarrer un nouveau frontend pointant vers l’index mis à jour et lui faire traiter une partie du trafic
• Stratégie d’utilisation des disques des serveurs d’index :
  • La partie externe du disque (outer part) offre une bande passante plus élevée
  1. (Pendant que l’ancien index continue d’être servi) copier le nouvel index dans la moitié interne (inner half) du disque
  2. Redémarrer pour utiliser le nouvel index
  3. Supprimer l’ancien index
  4. Recopier le nouvel index vers la moitié externe plus rapide (faster half)
  5. Supprimer la première copie du nouvel index placée dans la zone interne
  6. Utiliser l’espace interne libéré pour construire des structures de données d’amélioration des performances (ex. Pair cache — pré-calcul des intersections de listes de postings pour les paires de termes de requête fréquemment associées)

Réponse à la croissance et mise à l’échelle (1999-2001)

• Forte augmentation de la taille de l’index et du trafic en '99, '00 et '01 (~50 millions → plus d’1 milliard de pages, croissance mensuelle du trafic de 20 % + doublement du trafic du jour au lendemain avec le partenariat Yahoo, etc.)
• Les performances des serveurs d’index sont devenues cruciales : ajout continu de machines + besoin d’améliorations logicielles de 10 à 30 % par mois
• Mode de montée en charge : ajout de davantage de shards (Shards) et de réplicas (Replicas)
• Enseignements :
  • Le temps de réponse d’un shard dépend du nombre de seeks disque et du volume de données à lire
  • Pistes d’amélioration des performances : meilleur ordonnancement disque, encodage d’index amélioré

Évolution des techniques d’encodage d’index

• Encodage initial ('97) : format byte-aligned très simple (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). Un hit correspond à une position + des attributs (taille de police, titre, etc.). Ajout d’une table de saut pour les grandes listes de postings. Décodage peu coûteux mais faible taux de compression, nécessitant une forte bande passante disque.
• Diverses techniques d’encodage :
  • Niveau bit : Unary, Gamma, Rice_k (cas particulier du code de Golomb), Huffman-Int
  • Byte-aligned : varint (7 bits par octet + bit de continuation)
• Format d’index basé sur des blocs : réduction à la fois de l’espace et de l’usage CPU (~30 % de taille en moins), décodage plus rapide. Utilisation de blocs de longueur variable. En-tête (delta, longueur, etc.) + deltas d’ID de document (Rice_k) + nombre de hits (Gamma) + attributs des hits (Huffman run-length) + positions des hits (Huffman-Int).
• Nouveau format d’index (après 2004) : utilisation d’un espace de positions plat unique. Structures auxiliaires pour suivre les frontières des documents. Les listes de postings sont des listes de positions encodées en delta. Compacité et très grande vitesse de décodage sont toutes deux essentielles.

Système d’index en mémoire (début 2001)

• Contexte : l’extension du sharding + l’augmentation des réplicas ont permis d’obtenir assez de mémoire totale pour conserver une copie complète de l’index en mémoire
• Architecture : frontend → load balancer (bal) → shards (plusieurs réplicas de serveurs d’index en mémoire par shard)
• Avantages : forte augmentation du throughput, forte baisse de la latence (notamment pour les requêtes complexes qui demandaient auparavant des E/S disque de l’ordre du Go — ex. « circle of life »)
• Problèmes :
  • Variance : passage de quelques dizaines à plusieurs milliers de machines → comportement plus difficile à prédire (ex. tâches cron aléatoires posant problème)
  • Disponibilité : nombre de réplicas des données d’index de chaque document égal à 1 ou faible → « requête de la mort » (arrêt simultané de tous les backends), problèmes de disponibilité des données d’index en cas de panne machine (surtout pour les documents importants qui doivent être répliqués)

Conception et technologies des systèmes ultérieurs (après 2004)

• Matériel : datacenters de plus grande taille, racks conçus en interne, cartes mères de classe PC, matériel de stockage et de réseau à bas coût, Linux + logiciels développés en interne
• Conception du serving (édition 2004) : structure hiérarchique
  • Serveurs Root → serveurs Parent → serveurs Leaf (chargement d’un Repository Shard depuis GFS via File Loader)
  • Intégration de serveurs de cache

Encodage Group Varint

• Idée : résoudre les inefficacités du décodage varint (nombreuses branches / opérations de décalage / masques). Regrouper 4 entiers et les encoder sur 5 à 17 octets.
• Méthode :
  • Regrouper les 4 tags de 2 bits indiquant la longueur en octets de chaque valeur (1 à 4 octets) pour former un octet de préfixe (prefix)
  • Stocker ensuite les octets de données réels après cet octet de préfixe
• Décodage : lecture de l’octet de préfixe, utilisation comme index pour consulter une table pré-calculée de 256 entrées → récupération des offsets et des informations de masque afin de décoder les 4 valeurs en une seule fois
• Performances : beaucoup plus rapide que les méthodes précédentes (Group Varint : ~400M/s, 7-bit Varint : ~180M/s, 30-bit Varint w/ 2-bit len : ~240M/s)

Recherche universelle (2007)

• Système qui affiche non seulement des résultats de recherche web, mais intègre aussi divers types d’informations (images, informations locales, actualités, vidéos, blogs, livres, etc.).
• Un nœud super root envoie les requêtes à plusieurs systèmes de recherche spécialisés (moteurs de recherche verticaux) et agrège les résultats.

Défis du crawling et de l’indexation à faible latence

• Répercuter les mises à jour en quelques minutes est un défi très difficile.
• Heuristiques de crawling : quelles pages faut-il crawler ?
• Système de crawling : il faut crawler les pages rapidement.
• Système d’indexation : dépend de données globales comme le PageRank ou l’anchor text → nécessite des approximations online en temps réel.
• Système de serving : doit être prêt à accepter des mises à jour pendant le traitement des requêtes (ce qui exige des structures de données très différentes de celles d’un système de mise à jour par batch).

Importance de l’expérimentation et de l’infrastructure

• Facilité d’expérimentation : extrêmement importante (cycles d’expérimentation rapides → plus d’expériences → plus d’améliorations).
• Types d’expériences :
  • Expériences faciles : ajustement des pondérations sur des données existantes, etc.
  • Expériences difficiles : besoin de nouvelles données absentes de l’index de production. (La génération / l’intégration de nouvelles données et leur utilisation expérimentale doivent être faciles.)
• Infrastructure clé :
  • GFS : système de fichiers distribué à grande échelle
  • MapReduce : écriture / exécution simple de traitements de données massifs. (Accélère la génération des données de l’index de production et permet de lancer rapidement des expériences temporaires.)
  • BigTable : système de stockage semi-structuré (semi-structured). (Accès online et efficace aux informations par document, mises à jour asynchrones des informations documentaires par plusieurs processus — crucial pour passer de mises à jour à l’échelle de l’heure à des mises à jour à l’échelle de la minute.)

Cycle d’expérimentation et mise en production

1. Conception de l’idée et expérimentation offline :
   • Génération de données avec MapReduce, BigTable, etc.
   • Exécution d’expériences offline et vérification de l’effet (jeu de requêtes d’évaluation humaine, jeu de requêtes aléatoires, etc.).
   • À ce stade, la latence / le throughput du prototype n’ont pas d’importance.
   • Amélioration itérative sur la base des résultats expérimentaux.
2. Expérimentation live :
   • Si les résultats offline sont bons, mener une expérimentation live sur une petite fraction (tiny sliver) du trafic utilisateur réel (généralement un échantillon aléatoire, parfois une classe de requêtes spécifique).
   • À ce stade, la latence est plus importante que le throughput ! Le framework d’expérimentation doit se comporter au plus près de la latence de l’environnement de production.
3. Réglage des performances et lancement :
   • Si les résultats live sont bons, régler les performances / réimplémenter afin que l’exécution soit possible sous charge complète (ex. pré-calculer les données au lieu de calculer à l’exécution, utiliser une approximation moins coûteuse si elle est « suffisamment bonne »).
   • Importance du processus de rollout : il faut en permanence arbitrer entre qualité et coût, et équilibrer rapidité de lancement avec faible latence / stabilité du site (bonne collaboration nécessaire entre l’équipe qualité de recherche et l’équipe en charge des performances / de la stabilité).

Orientations futures et défis

• Recherche d’information multilingue (Cross-Language IR) : traduire tous les documents du monde dans toutes les langues → explosion de la taille de l’index et coût de calcul élevé. (Amélioration continue de la qualité de traduction, besoin de systèmes massifs capables de traiter des modèles de langue plus grands et plus complexes.)
• Listes de contrôle d’accès (ACLs) dans les systèmes de recherche d’information : environnement mêlant documents privés / semi-privés / largement partagés / publics. (Besoin de systèmes capables de traiter efficacement des ACL de tailles très variées — la solution optimale n’est pas la même pour un document partagé avec 10 personnes et pour un document partagé avec le monde entier, et les schémas de partage peuvent évoluer dans le temps.)
• Construction automatique de systèmes d’IR efficaces : aujourd’hui, plusieurs systèmes sont utilisés selon les objectifs (mises à jour ultra-rapides, corpus gigantesques, etc.). (Peut-on concevoir un système unique capable de construire automatiquement un système de recherche efficace adapté aux exigences à partir de paramètres d’entrée ?)
• Extraction d’information à partir de données semi-structurées : très peu de données portent des labels sémantiques explicites. Les tables, formulaires et autres données semi-structurées sont abondants. (Besoin d’algorithmes / techniques améliorés pour extraire de l’information structurée à partir de sources non structurées / semi-structurées — malgré le bruit, en exploitant la redondance, et en sachant relier / combiner / agréger les informations issues de multiples sources.)

Conclusion

• Concevoir et construire des systèmes de recherche d’information à grande échelle est une tâche à la fois difficile et passionnante.
• Les nouvelles technologies de recherche exigent souvent de nouvelles conceptions système.