[2009 WSDM] Herausforderungen beim Aufbau großskaliger Informationssuchsysteme

Wichtige Dimensionen und Trade-offs von Informationssuchsystemen

• Beim Systemdesign müssen Engineering-Trade-offs zwischen den folgenden Faktoren ausgewogen berücksichtigt werden.
  • Anzahl der indizierten Dokumente
  • Anzahl der pro Sekunde verarbeiteten Queries (QPS)
  • Aktualität des Indexes / Update-Geschwindigkeit
  • Query-Latenz
  • Umfang der pro Dokument gespeicherten Informationen
  • Komplexität/Kosten der Score-Berechnung bzw. Suchalgorithmen
• Der Engineering-Aufwand neigt dazu, proportional zum Produkt dieser Parameter zu sein.
• All diese Faktoren beeinflussen die Gesamtleistung und die Leistung pro Kosten (Leistung pro Dollar).

Veränderungen der Systemgröße (1999 vs. 2009)

• In den vergangenen 10 Jahren haben sich Systemgröße und Performance-Anforderungen dramatisch verändert.
  • # Dokumente: ~70 Millionen → mehrere Milliarden (~100-faches Wachstum)
  • täglich verarbeitete Queries: (~1000-faches Wachstum)
  • Indexinformationen pro Dokument: (~3-faches Wachstum)
  • Update-Latenz: mehrere Monate → wenige Minuten (~10000-fache Reduktion)
  • durchschnittliche Query-Latenz: <1 Sekunde → <0,2 Sekunden (~5-fache Reduktion)
  • Systemressourcen: mehr Maschinen * schnellere Maschinen (~1000-faches Wachstum)
• Diese Parameter ändern sich kontinuierlich, manchmal um mehrere Größenordnungen, daher muss sich auch das Systemdesign ständig weiterentwickeln.
  • Ein Design, das zu einem bestimmten Zeitpunkt (X) passend war, kann bei einer 10- oder 100-fachen Größenordnung völlig falsch sein. (Daher sollte man für etwa 10-faches Wachstum entwerfen, aber vor 100-fachem Wachstum eine Neuschreibung einplanen.)
  • In den letzten 10 Jahren gab es 7 größere Überarbeitungen.

Frühe Systemarchitektur (1997–1999)

• Phase als Forschungsprojekt (1997):
  • Frontend-Webserver nehmen Queries entgegen und verteilen Verarbeitungsanfragen an Indexserver und Dokumentserver
  • Indexserver: Sharding nach Dokument-ID (docid)
  • Dokumentserver: Sharding nach Dokument-ID (docid)
• Grundprinzipien:
  • Dokumenten werden ganzzahlige IDs (docids) zugewiesen (wichtige/hochwertige Dokumente erhalten kleine IDs)
  • Indexserver: (Query) → Rückgabe einer sortierten Liste aus (Score, docid, ...). Sharding nach docid, Replikation zur Kapazitätserweiterung. Kosten O(#Queries * #Dokumente im Index).
  • Dokumentserver: (docid, Query) → Erzeugung von (Titel, Snippet). Abbildung docid → vollständiges Dokument auf der Festplatte. Sharding nach docid. Kosten O(#Queries).
• Serving-System (1999):
  • Ergänzung der Forschungsprojekt-Struktur um Cacheserver und Anbindung an das Werbesystem
  • Betrieb von Replikaten der Index-/Dokumentserver-Shards
  • Caching: Sowohl Indexergebnisse als auch Dokument-Snippets werden gecacht. Cache-Hit-Rate 30–60 %. Großer Beitrag zu Performance-Steigerung und geringerer Query-Latenz. (Allerdings ist Vorsicht geboten, da bei Index-Updates/Cache-Flushing große Latenzspitzen auftreten können.)

Strategien zur Index-Partitionierung

• Nach Dokumenten (By doc): Jeder Shard enthält den Index eines Teils der Dokumente (von Google gewählt)
  • Vorteile: Unabhängige Query-Verarbeitung pro Shard, zusätzliche dokumentbezogene Informationen leicht beizubehalten, wenig Netzwerktraffic (Requests/Responses)
  • Nachteile: Alle Shards müssen jede Query verarbeiten; bei einer Query mit K Wörtern sind O(K*N) Disk-Seeks über N Shards nötig
• Nach Wörtern (By word): Jeder Shard enthält den Index eines Teils der Wörter über alle Dokumente hinweg
  • Vorteile: Eine Query mit K Wörtern wird von höchstens K Shards verarbeitet, O(K) Disk-Seeks
  • Nachteile: Deutlich höhere benötigte Netzwerkbandbreite (wortbezogene Informationen passender Dokumente müssen an einer Stelle zusammengeführt werden), dokumentbezogene Informationen sind schwerer zu verwalten

Frühes Crawling und Indexing (1998–1999)

• Crawling:
  • Einfaches Batch-Crawling-System: Liste von Start-URLs → Seiten crawlen → Links extrahieren und zur Queue hinzufügen → stoppen, wenn genügend Seiten gesammelt wurden
  • Zu berücksichtigende Punkte: Überlastung bestimmter Sites vermeiden, Priorisierung noch nicht gecrawlter Seiten bestimmen (z. B. PageRank), Queue ungecrawlter URLs effizient verwalten, Maschinenausfälle behandeln
• Indexing:
  • Einfaches Batch-Indexing-System auf Basis einfacher Unix-Tools
  • Probleme: Kein Checkpointing, daher schmerzhaft bei Maschinenausfällen; keine Prüfsummen für Rohdaten, was zu Problemen durch Hardware-Bitfehler führte (verschärft durch frühe Maschinen ohne ECC/Parity, „mostly sorted“-Probleme); Erfahrungen mit „hostilem Speicher und feindlicher Programmierung“
  • Lösung: Entwicklung einer Dateiabstraktion, die Prüfsummen kleiner Records speichert und es erlaubt, beschädigte Records zu überspringen bzw. wieder zu synchronisieren

Verfahren für Index-Updates (1998–1999)

• Zyklus: etwa einmal pro Monat
• Ablauf:
  1. Warten bis zu einer Zeit mit wenig Traffic
  2. Einige Replikate offline nehmen
  3. Den neuen Index auf die Offline-Replikate kopieren
  4. Ein neues Frontend starten, das auf den aktualisierten Index zeigt, und einen Teil des Traffics übernehmen lassen
• Strategie zur Festplattennutzung auf Indexservern:
  • Der äußere Bereich der Festplatte (outer part) bietet höhere Bandbreite
  1. (Während der bestehende Index weiter ausgeliefert wird) den neuen Index in die innere Hälfte der Festplatte (inner half) kopieren
  2. Neu starten, sodass der neue Index verwendet wird
  3. Den alten Index löschen
  4. Den neuen Index erneut in die schnellere äußere Hälfte (faster half) kopieren
  5. Die erste Kopie des neuen Indexes in der inneren Hälfte löschen
  6. Den frei gewordenen inneren Speicherplatz für performanceverbessernde Datenstrukturen nutzen (z. B. Pair cache – vorab berechnete Schnittmengen von Posting-Listen für häufig gemeinsam auftretende Query-Term-Paare)

Umgang mit Wachstum und Skalierung (1999–2001)

• In den Jahren '99, '00 und '01 nahmen Indexgröße und Traffic stark zu (~50 Millionen → über 1 Milliarde Seiten, 20 % Traffic-Wachstum pro Monat sowie z. B. eine Verdopplung des Traffics über Nacht durch die Yahoo-Partnerschaft)
• Die Performance der Indexserver wurde hochkritisch: kontinuierliche Erweiterung um mehr Maschinen + monatlich 10–30 % softwarebasierte Performance-Verbesserungen erforderlich
• Skalierungsansatz: Hinzufügen von mehr Shards und Replikaten
• Erkenntnisse:
  • Die Antwortzeit eines Shards hängt von der Anzahl der Disk-Seeks und der zu lesenden Datenmenge ab
  • Mögliche Ansatzpunkte für Performance-Verbesserungen: besseres Disk-Scheduling, verbesserte Index-Encoding-Verfahren

Weiterentwicklung der Index-Encoding-Techniken

• Frühes Encoding ('97): Sehr einfaches byteausgerichtetes Format (WORD → [docid+nhits:32b, hit:16b, hit:16b...]). Ein Hit besteht aus Position + Attributen (Schriftgröße, Titel usw.). Für große Posting-Listen wurden Skip-Tabellen ergänzt. Das Decoding ist günstig, die Kompression jedoch schwach, sodass viel Festplattenbandbreite benötigt wird.
• Verschiedene Encoding-Verfahren:
  • Bitlevel: Unary, Gamma, Rice_k (Spezialfall eines Golomb-Codes), Huffman-Int
  • Byte-ausgerichtet: varint (7 Bit pro Byte + Fortsetzungsbit)
• Blockbasiertes Indexformat: Sowohl Platzbedarf als auch CPU-Nutzung sinken (~30 % kleinere Größe), Decoding wird schneller. Verwendet variabel lange Blöcke. Header (Delta, Länge usw.) + Dokument-ID-Deltas (Rice_k) + Hit-Anzahlen (Gamma) + Hit-Attribute (Run-Length Huffman) + Hit-Positionen (Huffman-Int).
• Neues Indexformat (ab 2004): Verwendung eines einzigen flachen Positionsraums. Dokumentgrenzen werden über Hilfsdatenstrukturen nachverfolgt. Posting-Listen sind delta-kodierte Positionslisten. Sowohl Kompaktheit als auch sehr hohe Decoding-Geschwindigkeit sind wichtig.

In-Memory-Indexsystem (Anfang 2001)

• Hintergrund: Durch Sharding im größeren Umfang + mehr Replikate war insgesamt genügend Speicher vorhanden, um vollständige Indexkopien im RAM zu halten
• Architektur: Frontend → Load Balancer (bal) → Shard (mehrere Replikate von In-Memory-Indexservern pro Shard)
• Vorteile: Deutlich höherer Throughput, deutlich geringere Latenz (insbesondere bei komplexen Queries, die zuvor Festplatten-I/O im GB-Bereich benötigten – z. B. „circle of life“)
• Probleme:
  • Varianz (Variance): Statt Dutzenden nun Tausende Maschinen → schwerer vorhersehbares Verhalten (z. B. Probleme durch zufällige cron-Jobs)
  • Verfügbarkeit (Availability): Pro Dokument liegt nur ein oder wenige Replikate der Indexdaten vor → „Queries des Todes“ (gleichzeitiger Ausfall aller Backends), Probleme mit der Verfügbarkeit von Indexdaten bei Maschinenausfällen (insbesondere wichtige Dokumente müssen repliziert werden)

Spätere Systemdesigns und Technologien (ab 2004)

• Hardware: Größere Rechenzentren, selbst entworfene Racks, Motherboards auf PC-Niveau, kostengünstige Storage- und Networking-Hardware, Linux + selbst entwickelte Software
• Serving-Design (Edition 2004): Hierarchische Struktur
  • Root-Server → Parent-Server → Leaf-Server (laden Repository-Shards aus dem GFS über den File Loader)
  • Anbindung an Cacheserver

Group-Varint-Encoding

• Idee: Behebung der Ineffizienz beim Varint-Decoding (viele Branches/Shift/Mask-Operationen). Vier Integer-Werte werden als Gruppe in 5–17 Bytes kodiert.
• Verfahren:
  • Vier 2-Bit-Tags, die die Byte-Länge (1–4 Bytes) jedes Werts angeben, werden zu einem 1-Byte-Präfix (prefix) zusammengefasst.
  • Hinter dem Präfix-Byte werden die eigentlichen Datenbytes gespeichert.
• Decoding: Das Präfix-Byte wird gelesen und als Index für eine vorberechnete Tabelle mit 256 Einträgen verwendet → Offset- und Mask-Informationen werden geholt und die 4 Werte auf einmal dekodiert.
• Performance: Deutlich schneller als frühere Verfahren (Group Varint: ~400M/s, 7-bit Varint: ~180M/s, 30-bit Varint w/ 2-bit len: ~240M/s)

Universal Search (2007)

• Ein System, das nicht nur Websuchergebnisse, sondern auch verschiedene andere Informationstypen (Bilder, lokale Informationen, Nachrichten, Videos, Blogs, Bücher usw.) integriert und gemeinsam anzeigt.
• Ein Super-Root-Knoten sendet Queries an mehrere spezialisierte Suchsysteme (vertikale Suchmaschinen) und aggregiert die Ergebnisse.

Herausforderungen bei Crawling und Indexing mit niedriger Latenz

• Updates innerhalb weniger Minuten zu reflektieren, ist äußerst schwierig.
• Crawling-Heuristiken: Welche Seiten sollen gecrawlt werden?
• Crawling-System: Seiten müssen schnell gecrawlt werden.
• Indexing-System: Abhängigkeit von globalen Daten wie PageRank und Anchor-Text → Online-Approximation in Echtzeit erforderlich.
• Serving-System: Muss darauf vorbereitet sein, während der Query-Verarbeitung Updates anzunehmen (erfordert völlig andere Datenstrukturen als ein Batch-Update-System).

Bedeutung von Experimenten und Infrastruktur

• Einfaches Experimentieren: sehr wichtig (schnelle Experimentzyklen → mehr Experimente → mehr Verbesserungen).
• Arten von Experimenten:
  • Einfache Experimente: z. B. Anpassung der Gewichtung bestehender Daten.
  • Schwierige Experimente: erfordern neue Daten, die im Produktionsindex nicht vorhanden sind. (Die Erzeugung/Integration neuer Daten und ihre Verwendung in Experimenten müssen einfach sein.)
• Kerninfrastruktur:
  • GFS: verteiltes Dateisystem im großen Maßstab
  • MapReduce: erleichtert das Schreiben/Ausführen großskaliger Datenverarbeitungsjobs. (Beschleunigt die Erzeugung von Daten für den Produktionsindex, ermöglicht schnelle temporäre Experimente.)
  • BigTable: Storage-System für semi-strukturierte Daten. (Ermöglicht online effizienten Zugriff auf dokumentbezogene Informationen; mehrere Prozesse können Dokumentinformationen asynchron aktualisieren – wichtig für Updates im Minuten- statt Stundenbereich.)

Experimentzyklen und Rollout

1. Ideenfindung und Offline-Experimente:
   • Datenerzeugung mit MapReduce, BigTable usw.
   • Durchführung von Offline-Experimenten und Validierung der Wirkung (menschlich bewertete Query-Sets, zufällige Query-Sets usw.)
   • In dieser Phase sind Latenz und Throughput des Prototyps nicht wichtig.
   • Iterative Verbesserung auf Basis der Experimentergebnisse.
2. Live-Experimente:
   • Wenn die Ergebnisse der Offline-Experimente gut sind, werden Live-Experimente auf einem kleinen Teil (tiny sliver) des realen User-Traffics durchgeführt (meist zufällige Samples, manchmal bestimmte Query-Klassen).
   • In dieser Phase ist Latenz wichtiger als Throughput! Das Experiment-Framework muss sich hinsichtlich der Latenz ähnlich zur Produktionsumgebung verhalten.
3. Performance-Tuning und Release:
   • Wenn die Ergebnisse der Live-Experimente gut sind, erfolgt Performance-Tuning bzw. eine Re-Implementierung, damit das Ganze unter voller Last läuft (z. B. Vorkalkulation von Daten statt Berechnung zur Laufzeit, Nutzung günstigerer Approximationen, wenn sie „gut genug“ sind).
   • Der Rollout-Prozess ist wichtig: Trade-off zwischen Qualität und Kosten muss fortlaufend berücksichtigt werden; Balance zwischen schneller Einführung sowie niedriger Latenz/Website-Stabilität (erfordert gute Zusammenarbeit zwischen Suchqualitätsteams und Teams für Performance/Stabilität).

Zukünftige Richtungen und Herausforderungen

• Mehrsprachige Informationssuche (Cross-Language IR): Alle Dokumente der Welt in alle Sprachen übersetzen → stark wachsender Index, hohe Rechenkosten. (Kontinuierliche Verbesserung der Übersetzungsqualität, Bedarf an großskaligen Systemen zur Verarbeitung größerer und komplexerer Sprachmodelle.)
• Access Control Lists (ACLs) in Informationssuchsystemen: Gemischte Umgebungen aus privaten, halbprivaten, breit geteilten und öffentlichen Dokumenten. (Es wird ein System benötigt, das ACLs sehr unterschiedlicher Größe effizient verarbeitet – die optimale Lösung für mit 10 Personen geteilte Dokumente ist eine andere als für weltweit geteilte Dokumente; Teilungsmuster können sich über die Zeit ändern.)
• Automatischer Aufbau effizienter IR-Systeme: Derzeit werden mehrere Systeme für verschiedene Zwecke verwendet (für ultraschnelle Updates, für extrem große Dokumentmengen usw.). (Möglichkeit eines einheitlichen Systems, das bei Eingabe von Parametern automatisch ein effizientes Suchsystem passend zu den Anforderungen aufbaut?)
• Informationsextraktion aus semi-strukturierten Daten: Es gibt nur sehr wenige Daten mit klaren semantischen Labels. Dagegen sind Tabellen, Formulare und andere semi-strukturierte Daten reichlich vorhanden. (Es werden bessere Algorithmen/Techniken benötigt, um strukturierte Informationen aus unstrukturierten/semi-strukturierten Quellen zu extrahieren – trotz starkem Rauschen, aber unter Nutzung von Redundanz sowie der Fähigkeit, Informationen aus mehreren Quellen zu verknüpfen, zu kombinieren und zu aggregieren.)

Fazit

• Das Design und der Aufbau großskaliger Informationssuchsysteme sind anspruchsvolle und spannende Aufgaben.
• Neue Suchtechnologien erfordern oft auch neue Systemdesigns.