Das Job-Netzwerk LinkedIn hat seine neue Suche vorgestellt. Diese ermöglicht ein besseres Ranking, schnellere Updates und bessere Möglichkeiten der Interpretation von Suchanfragen.
Schnellere Updates, bessere Skailerbarkeit, mehr Funktionen - die neue Suche von LinkedIn verspricht einiges.
Die alte Suche des Job-Netzwerks mit seinen mittlerweile mehr als 300 Millionen Mitgliedern war auf Basis der Open-Source-Software Apache Lucene implementiert. Das System wurde nach und nach um weitere Komponenten erweitert. Die Erweiterungen fanden aber stets reaktiv und in kleinen Bereichen statt. Deshalb war es schwierig, umfassende und ganzheitliche Lösungen zu bauen.
Vor allem aber die Skalierung war ein Problem: Die Zahl der zu verarbeitenden Daten wuchs besonders nach der Einführung des Economic Graph als Abbildung der Wirtschaft mit Verbindungen zwischen Personen, Jobs, Fähigkeiten, Unternehmen und Wissen sehr stark an. Der Economic Graph ist vergleichbar mit dem Social Graph bei Facebook, der Nutzer und Eigenschaften als Entitäten und Verbindungen zwischen ihnen abbildet.
Probleme der alten Suche
Die wichtigsten Bestandteile der alten Suche waren:
- Inverted Index: Ein Mapping von Suchbegriffen auf Entitäten, welche die Suchbegriffe enthalten
- Forward Index: Mapping von Entitäten auf Metadaten der Entitäten
Die Listen im Inverted Index heißen Posting Lists. Bei einer Suche werden die eingegebenen Suchphrasen mit den Posting Lists für diese Suchphrasen abgeglichen, um die Entitäten zu finden, die der Suchanfrage entsprechen. Die Relevanz ergibt sich aus Details der Posting List und aus Informationen aus dem Forward Index, also den Metadaten.
Aufgrund der Größe der Indizes mussten diese auf mehrere Teile heruntergebrochen werden, - Shards genannt - die auf verschiedene Rechner verteilt wurden. Dazu wurde eine Komponente namens Sensei entwickelt und als Open Source zur Verfügung gestellt, die sich um die Verteilung auf die verschiedenen Shards kümmert. Ähnliche Ansätze verfolgen beispielsweise Elastic Search oder Apache Solr.
Ein weiteres Problem war, dass Änderungen im Index erst nach einem Commit sichtbar waren - ein sehr rechenintensiver Vorgang. Dem begegnete man bei LinkedIn mit einer Komponente namens Zoie. Diese hält eine Kopie aller nicht committeten Änderungen im Speicher. Diese Daten können dann abgerufen werden, solange der Index nicht aktualisiert wurde.
Weitere Probleme mit der Nutzung des alten Systems waren:
- Geringe Flexibilität beim Ranking: Das Einbinden manueller Scores oder auch von Werten auf Basis von Maschinenlernen ist schwierig.
- Lucene unterstützt nicht alle Suchanforderungen wie beispielsweise Offline-Relevanz, Umschreiben von Suchanfragen, Reranking oder Experimentieren
- Zu viele kleine Open-Soruce-Komponenten: Die Verteilung der einzelnen Komponenten machte es schwierig, den Überblick auf das Gesamtsystem zu behalten
Neue Suche: Galene nutzt weiterhin Lucene
Die neue Suche-Infrastruktur bei LinkedIn besitzt den Namen Galene. Der Begriff "Galene" stammt aus dem Griechischen und bezeichnet die von von Unruhe befreite, erfüllte Seele.
Als Indexierungsschicht für Galene kommt weiterhin Lucene zum Einsatz. Alle weiteren genannten Komponenten des Altsystems jedoch wurden abgelöst. Die folgende Grafik zeigt den grundlegenden Aufbau von Galene:
Bild (C) LinkedIn
Es handelt sich dabei um eine klassische Suche-Architektur mit der Verteilung auf Frontend und Backend, wobei die Backend-Komponenten wiederum auf mehrere Einheiten aufgeteilt sind.
Der Federator und der Broker haben die Aufgabe, Suchanfragen und Metadaten entgegenzunehmen und diese dann auf verschiedene Dienste zu verteilen. Im Gegenzug werden dann die verschiedenen Antworten angenommen und zu einem einheitlichen Suchergebnis kombiniert, welches dann dem Anfragenden zurückgeliefert wird. Der Broker nimmt noch verschiedene Umformungen der Suchanfragen vor, bevor er diese an die Searcher weitergibt.
Der Prozess der Zusammenführung mehrere Suchergebnisse durch den Federator kann recht komplexe Relevanzierungsalgorithmen enthalten. Broker und Federator sind im Prinzip Instanzen ein und derselben Software. Was sie unterscheidet, sind die verschiedenen Plugins, die jeweils installiert sind.
Interessant ist die Rolle der Rewriter: Sie reichern Suchanfragen um verschiedene Metadaten an, bis letztendlich die fertige Suchanfrage entsteht.
Bild (C) LinkedIn
Der Searcher nimmt die fertigen Queries entgegen und liefert die Ergebnisse mit dem höchsten Score für die jeweilige Suchanfrage zurück an den Broker.
Statisches Ranking
Ein Merkmal von Galene ist das Berechnen so genannter statischer Rankings. Das bedeutet, dass jeder Entität eine bestimmte Bedeutung zugesprochen wird - unabhängig von bestimmten Suchanfragen. Dieser Prozess findet offline im Zuge des Indexbaus statt. Auf diese Weise können Entitäten nach Wichtigkeit sortiert werden. Das statische Ranking hat insofern ein wenig Ähnlichkeit mit Googles PageRank-Algorithmus. Auch hier wird bestimmten Knoten im Netz eine unabhängig von Suchanfragen bestehende Bedeutung zugesprochen.
Mit Hilfe des statischen Rankings kann der Prozess der Informationsrückgewinnung (Information Retrieval) für eine Suchanfrage dann abgebrochen werden, wenn eine ausreichende Zahl von Entitäten mit einer bestimmten Wichtigkeit gefunden wurde. Man spricht hier von Early Termination (früher Abbruch).
Live Updates
Um häufige und inkrementelle Updates zu ermöglichen, ist der neue Index bei Galene auf drei verschiedene Segmente unterteilt: den Base Index, den Live Update Buffer und den Snapshot Index.
- Base Index: Dieser Index wird offline und relativ selten auf Hadoop neu gebaut - beispielsweise im Wochenrhythmus. Er wird nie geändert, sondern er wird verworfen, wenn eine neue Version gebaut wurde.
- Live Update Buffer: Dieser Index wird im Speicher gehalten. Alle Live-Updates werden auf dieses Segment des Index angewandt. Das bedeutet, dass sich der Live Update Buffer inkrementell ändert.
- Snapshot Index: Während der Live Update Buffer im Speicher gehalten wird, wird er regelmäßig - etwa alle paar Stunden - auf Platte geschrieben und bildet dann jeweils eine neue, persistente Version des Snapshot Index. Nach jedem solchen Vorgang wird der Live Update Buffer zurückgesetzt.
Bild (C) LinkedIn
Lifecycle-Management des Index
Aufgrund der komplexen Vorgänge beim Indexieren finden diese Prozesse auf gesonderten Rechnern statt, damit die Rechner, die für die Auslieferung von Suchergebnissen zuständig sind, nicht zusätzlich belastet werden. Um Daten an die benötigten Stellen zu transportieren und sie verfügbar zu machen, wird ein System namens Replica Groups eingesetzt: Rechner können sich einer Replica Group anschließen und erhalten dort alle Daten dieser Gruppe. Sie können selbst auch dieser Gruppe Daten hinzufügen, die dann an alle Rechner in dieser Replica Group verteilt werden. Diese Vorgänge werden beispielsweise genutzt, um Daten von den Hadoop Distributed File Systems (HDFS) an die Federatoren und Broker weiterzugeben.
Ausblick
Geplant ist, das System weiter zu verbessern und auch mit zusätzlichen Funktionen auszustatten. Vor allem aber soll die Suche als Service zur Verfügung stehen, um weitere Suchangebote wie eine Jobsuhe oder eine Personensuche anbieten zu können.
{extravote 1}
