Recommender

Architektur

Server

Server Dienste werden in Form eines Clusters zur Verfügung gestellt. Auf Server, der als Cluster-Member vorgesehen ist, laufen ein oder mehrere Instanzen der Applikation in einem Applikationsserver, die Kommunikation zwischen den Member-Knoten erfolgt mit Messaging. Eine Instanz der Applikation wird im weitern als Member-Knoten bezeichnet.

Jeder Member-Knoten ist hinsichtlich Konfiguration ident. Der einzige Unterschied ist die ID des Member-Knotens, die aus Hostname und einer Zufallszahl, für den Fall dass mehrere Instanzen auf einem physischen Server laufen, generiert wird.

Auf genau einem der Member-Knoten läuft eine Koordinator Komponente (Singleton).

Jeder Member-Knoten aktualisiert in regelmässigen Abständen die Statusmap

Applikationsserver

Als Applikationsserver kommt JBoss AS7 in der aktuellen Version zum Einsatz.

JBoss' integrierte Cluster-Fähigkeit wird nicht verwendet. Ein Grund hierfür ist, dass derzeit noch keine Dokumentation für die aktuelle Version vorliegt. Ausserdem ist die Applikation dadruch nicht an JBoss als Applikationsserver gebunden, es ist lediglich ein Messaging Provider erforderlich.

Als Messaging System kommt HornetQ zum Einsatz. HornetQ lässt sich nahtlos in JBoss integrieren, bzw. ist bereits in manchen Versionen integriert. HornetQ Server werden im Cluster Modus betrieben, somit wird einerseits Ausfallsicherheit, andererseits Skalierbarkeit gewährleistet.

Datenbank

Als Datenbank kommt neo4j in der Enterprise Edition zum Einsatz. Diese Version ermöglicht es, neo4j Instanzen als Cluster zu betreiben. Neo4j benötigt dafür laufende Zookeeper Instanzen. Lesevorgänge können auf allen Instanzen ausgeführt werden. Bei Schreivorgängen werden Daten zuerst auf einem Master gespeichert. Sobald auf einer Slave Instanz ein Schreibvorgang stattfindet, werden die Daten mit dem Master abgeglichen. Das Konsistenzmodell ist also in diesem Fall Eventually Consistent.

Sharding

Eine Datenbank in neo4j kann 32 Milliarden Nodes, 32 Milliarden Relations und 64 Milliarden Properties umfassen.

Das bedeutet für den Fall dass jedes Item allen anderen Item in einer Beziehung steht eine maximale Obergrenze von ca. 250.000 Items.

Partitionierung der Daten (Sharding) wäre daher erforderlich, wird aber von den meisten Graphdatenbanken, so auch von neo4j, nicht unterstützt.

Ein weiterer Aspekt ist Performance: Neo4j versucht Graphen soweit wie möglich im Cache zu halten. Lesevorgänge von Daten die sich im Cache befinden sind extrem schnell. Sobald eine Datenbank zu gross wird, können sie nicht mehr zur Gänze im Cache gehalten werden, worunter die Lese-Performance leidet. Jim Webber schlägt als Lösung hier das Pattern Cache Sharding vor. Statt Sharding wird hier ein Consistent Routing implementiert - Zugriffe auf gleiche Datensätze werden immer auf dieselbe Serverinstanz geroutet. Jim Webber schlägt vor Abgrenzungen domän-spezifisch zu implementieren.

Um beide Aspekte zu berücksichtigen, werden Daten pro Mandaten (=Domäne) in unterschiedlichen Datenbanken gespeichert, bzw. Daten von wenigen Mandaten in einer Datenbank zusammengefasst. Datenzugriffe werden pro Mandaten an immer dieselben zugeordneten Member-Knoten geroutet. Dies zu gewährleiten ist Aufgabe des Koordinators.

Nachteil dieser Lösung ist dass es nicht mehr ohne weiteres möglich ist, Domän-Übergreifende Beziehungen festzustellen.

Client

Clients dienen dazu, mit dem Recommender System zu interagieren.

Wie Clients mit dem jeweiligen Zielsystemen zusammenspielen bleibt der Implementierung des Clients überlassen.

Auch der Umgang mit anonymen Usern obliegt dem Client, so kann beispielsweise einen anonymen User pro Session ein eigener User kreiert werden.

Clients interagieren mit dem Server über ein Restful Webservice. In weiterer Zukunft wird es auch möglich sein einen Client als native Java-Applikation zu implementieren, die über eine Proxy-Klasse mit dem Recommender System kommuniziert.

Aktionen

Folgende Aktionen können von Clients ausgeführt werden:

• Rate: Ein Rating eines Users für ein Item wird übermittelt
• User hinzufügen: Ein neuer User wird angelegt
• User-Merkmal hinzufügen: Eine Merkmal, z.B. ein Schlagwort oder eine Eigenschaft, wie Alter, Gender, etc. wird hinzugefügt.
• Item hinzufügen: Ein neues Item wird angelegt
• Item-Merkmal hinzufügen: Ein Merkmal, z.B. ein Schlagwort oder ein Wortvektor wird hinzugefügt
• Recommendations für User abfragen: Das Recommender System liefert dem Client eine Liste mit Namen oder IDs von Items

Design

Datenbanken und Datenstruktur

Datenbanken der Mandaten

User, Items und deren Beziehungen werden pro Mandaten in jeweils einer Datenbank gespeichert. Für Mandaten mit kleineren Datenmengen werden die Daten mehrerer Mandaten in einer Datenbank zusammengefasst.

Diese Datenbank enthält folgende Knoten-Arten:

• Mandant: Repräsentiert einen Mandanten, hat Kanten zu Item und User-Knoten

• Item:
  • similiar_to Kanten zu anderen Items (diese Kanten sind als ungerichtete Kanten zu verstehen)
  • Profil-Kanten zu verscheidenen Profile-Knoten, wie Wordverktor-Knoten oder Keyword-Knoten

• User:
  • similiar_to Kanten zu anderen User-Knoten (diese Kanten sind als ungerichtete Kanten zu verstehen)
  • rate Kanten zu Items. Diese Kanten besitzen eine weight Property, die den Wert des Ratings in Prozent enthält.
  • predict Kanten zu Items. Diese Kanten haben mehrere Properties:
    • weight: Ermittelter Rating Wert des Users für dieses Item
    • conf_vers: Versionsnummer der verwendeten Konfiguration (siehe Konfigurations Datenbank)
    • Methoden: Verwendete Methode mit zugehörigen Vorhersagewerten

Konfigurations Datenbank

In der Konfigurationsdatenbank befindet sich:

• Datenbanken: Welche Datenbanken gibt es, und welchen Mandanten sind sie zugeordnet
  • Properties: Name der Datenbank und Dateiname
• Mandanten: Name des Mandanten, Authentifizierungsdaten, etc.
• Methoden: Verfügbare Methoden (e.g. Item-Based CF) zum Ermitteln von Predictions
  • Properties: Name der Methode
• Profile: Profile umfassen eine Reihe verschiedener Methoden, und wie jede Methode für eine Prediction zu gewichten ist. Ein Profil kann von beliebig vielen Configurations verschiedener Mandanten verwendet werden.
• Configuration: Entspricht einer Version eines Profiles, inklusive der Möglichkeit Default-Gewichtungen zu überschreiben. Unterhält eine Beziehung zu genau einem Profil. Ist genau einem Mandanten zugeordnet. Jeder Mandant kann allerdings mit mehreren Configuration Knoten verbunden sein, wobei genau eine Configuration aktiv sein muss. Die aktive Configuration wird mittels active Property der Mandant->Configuration Kante gekennzeichnet. Properties:
  • Versionsnummer: Diese Versionsnummer wird als Property der predict Kante übernommen. Damit kann festgestellt werden ob Berechnungen auf der momentan aktive Konfiguration beruhen oder alle Predictions erneut ermittelt werden müssen.
  • Accuracy: Ermittelte Gesamt-Accuracy (Mean Absolute Error Abweichung von Ratings zu Predictions)
• Properties der Kante Configuration->Profile:
  • Weight: Tatsächlich bei der Ermittlung der Predictions vewendetes Gewicht.
  • Accuracy: Ermittelte Accuracy (Mean Absolute Error Abweichung von Ratings zu Predictions) der betreffenden Methode

Dependency-Map

Zwischen Methoden können Abhängigkeiten bestehen. So ist die Methode Content Boosted CF von der Methode Content Based Filtering abhängig, diese muss also zuerst beendet werden bevor Content Boosted CF' gestartet werden darf. Diese Abhängigkeiten sind als depends_on Kanten zwischen Method Knoten modelliert.

Status-Map

Status-Map

Jeder Member-Knoten ist in der Statusmap vertreten. Jeder Knoten aktualisiert in regelmässigen Abständen die Heartbeat Property seines entsprechenden Nodes in der Statusmap. Dieser Schreibvorgang bewirkt eine synchronisation mit dem Master, wodurch die Statusmap unmittelbar nach jedem Schreibvorgang konsistent ist.

Je nach Rolle erfolgt zusätzlich zum Update der Statusmap ein zusätzlicher Schritt:

• der Koordinator prüft ob eine Heartbeat Property eines Kontens nicht aktualisiert wurde. In diesem Fall gilt der Knoten als ausgefallen, und wird aus der Statusmap entfernt. Zugeordnete Mandanten und Jobs werden neu verteilt.
• jeder Knoten prüft ob der Koordinator dessen Heartbeat Property aktualisiert hat. Ist dies nicht der Fall, gilt der Koordinator als ausgefallen, und der Knoten startet eine Election.

In der Status-Map sind auch alle aktive Mandaten-Knoten enthalten. Mittels Consistent-Hashing Algorithmus sind Mandanten ein oder mehreren Member-Knoten zugeordnet. Diese Zuordnung steuert das Message Routing. Betreffende Member-Knoten erhalten Rating-Requests und Jobs, die den jeweiligen Mandaten betreffen. Diese Jobs, sowie allfällige Abhängigkeiten zu anderen Jobs sind ebenfalls in der Status-Map enthalten.

Kommunikation

Client kommunizieren mit dem Server über ein Restful Webservice.

Der Vorgang, am Beispiel Rate-Request läuft wie folgt ab: Der Client übermittelt ein Rating an einen der Server des Clusters. Der Antwortende Member-Knoten generiert eine Nachricht und sendet diese an eine konfigurierte Queue, die Kommunikation zwischen Cleint und Server wird daraufhin beendet.

Messaging

Kommunikation findet grösstenteils über Messaging statt. Vorteile sind:

• Einfachere Kommunikaton: Jeder Member-Knoten ist hinsichtlich Konfiguration ident. Anstatt wissen zu müssen wie andere Knoten kontaktiert werden müssen, beschränkt sich bei Messaging das erforderliche Wissen drauf, an welche Queues oder Topics versendet werden muss.
• Skalierbarkeit: Es ist nicht erforderlich dass jeder Member-Knoten an jeden anderen Member-Knoten Nachrichten versenden kann. Es muss auch nicht jedem Member-Knoten bekannt sein welche anderen Knoten verfügbar sind.
• Entkoppelung von Cleint und Server, und Entkoppelung der Member-Knoten, asynchroner Nachrichtenaustausch
• Einfachere Parallelverarbeitung: Pro Knoten sind mehrere Instanzen vorhanden, die Nachrichten erhalten und gegebenenfalls parallel verarbeiten können

Es gibt ausser dem Koordinator zwei Arten von Message Consumer:

• Empfänger von Rate-Jobs: Der entsprechde User und Item Node wird in der entsprechenden Datenbank gesucht, Rating Kante zwischen User und Item gesetzt und gewichtet, und daraufhin eine Nachricht an die Scheduler Queue, deren Emfpänger der Koordinator ist, gesendtet.
• Emfänger der Job Queue: In der Status Map wird der entsprechende Job anhand der sich in der Nachricht befindlichen Job-ID nachgeschlagen. Daraufhin wird der Job an eine Instanz der jeweilgen Methodenverabeitung delegiert, und daraufhin der Job in der Status Map gelöscht. In der Status Map könne auch Abhängigkeiten notiert sein, beispielsweise kann ein Job erst nach Beendigung eines anderen Jobs gestartert werden. In diesem Fall wird nach einiger Zeit erneut geprüft ob der Job gestartet werden kann. Ist dies nicht der Fall wird die Nachricht zurückgewiesen, was entweder zu eine neuerlichen Zustellversuch führt, oder die Nachricht wird als nicht zustellbar betrachtet und demgemäss an die Queue für nicht zustellbare Nachrichten zugestellt.

Queues und Topics

Rate-Requests

An Queue werden von Clients gemeldete Ratings übermittelt. Relevante Informationen sind hier: Mandant, User, Item, Rating als Prozentwert (bei Ratingmöglichkeit von 1 bis 7 und Wahl 3 würde dies 42.86% entsprechen). Consumer der Queue ist der Koordinator.

Rate-Jobs

An diese Queue werden vom Koordinator Nachrichten der Rate-Request Queue gesendet, ergänzt mit Filter Information, die einem de-facto Routing dienen (siehe oben).

Scheduler-Queue

An diese Queue werden Nachrichten gesendet die entweder infolge eines bereits durchgeführten Ratings erstellt werden, oder Nachrichten infolge Anlage eines neuen Users oder Items, oder Nachrichten infolge Änderung von Eigenschaften von Item oder User Knoten. Erstellt werden Rating Nachrichten von Workern die erfolgreich ein Rating eingetragen habe, und von den via Webservice kontaktierten Services nach der Durchführung der entsprechenden Aktion.

Job-Queue

An diese Queue sendet der Koordinator Nachrichten mit Job IDs. Nachrichten sind mit Filter Informationen versehen, daher erhalten Consumer nur Nachrichten anhand enstprechnder Message Selektoren. Consumer schlagen Jobs in der Status-Map nach, und verarbeiten diese.

Dead Letter Queue

An diese Queue stellt der Messaging Provider nicht zustellbare Nachrichten zu. Consumer dieser Queue ist der Koordinator, der enstprechend der Nachricht weitere Aktionen setzt, so werden beispielsweise Nachrichten mit Job IDs erneut an die Job Queue gesendet.

Koordinator

Der Koordinator startet folgende Dienste:

• Rating Scheduler
• Job Scheduler

Wenn ein Koordinator feststellt dass er nicht länger Koordinator ist, beendet er diese Dienste.

Die Aufgabe beider Schedulern ist das Verteilen, bzw. das Routen von Nachrichten, die Aufgaben für andere Member Nodes beinhalten.

Anhand der Statusmap werden mittels Consistent Hashing Algorithmus jedem Member-Knoten zu betreuende Mandaten zugeteilt. Hintergrund dieser Zuteilung ist die fehlende Sharding Möglichkeit (siehe #Routing) bei gängigen Graphdatenbanken.

Member-Knoten erhalten mittels gesetzem Message Selektor ausschliesslich für sie bestimmte Nachrichten. Es ist Aufgabe des Koordinators, die entsprechende Header Property bei Nachrichten entsprechend zu setzen, wobei die Status-Map vor dem Setzen der Property konsultiert wird, um ausgefallene Member-Knoten, neue hinzugekommene Member-Knoten, neue Mandanten, etc. berücksichten zu können.

Für nicht zustellbare Nachrichten, falls beispielsweise ein Member-Knoten ausgefallen ist nachdem der Koordinator eine Nachricht für diesen erstellt hat, ist eine eigene Queue vorgesehen. Der Koordinator verteilt Nachrichten aus dieser Queue erneut.

Rating Scheduler

Der Koordinator liest in einer Endlosschleife Nachrichten aus der Rate-Requests Queue (und der Queue für nicht zustellbare Nachrichten). Folgend den Informationen aus der Statusmap wird die Rating Nachricht mit einem entsprechendem Filter Information versehen und an die Rate-Jobs Queue zugestellt.

Job Scheduler

Der Koordinator liest in einer Endlosschleife Nachrichten aus der Scheduler-Queue und generiert entsprechden Jobs. Beispielsweise werden mehrere Rating-Nachrichten eines Mandaten aus der Scheduler-Queue zusammengefasst und entsprechende Jobs generiert.

Aufgrund der Information der Dependency-Map werden aus Ratings, und den für den entsprechnden Mandanten konfigurierten Methoden, mehrere Jobs erzeugt. Diese Jobs können untereinander Abhängigkeiten besitzen. Jobs und deren Abhängigkeiten werden in die Status-Map eingetragen. Danach wird eine Nachricht erzeugt, in der neben der Job-ID auch ein entsprechender Message Selektor gesetzt ist und diese an die Job-Queue gesendet.

Election

Eine Election findet statt, sobald ein Member-Knoten feststellt dass der Koordinator ausgefallen ist.

Dies erfolgt indem jeder Member-Konten prüft ob er derjenige mit der niedrigsten ID ist, in diesem Fall wird dieser Knoten neuer Koordinator.

Falls weitere Member-Konten mit niedrigeren IDs vorhanden sind wird geprüft ob einer dieser Knoten verfügbar ist. In diesem Fall muss keine weitere Aktion erfolgen. Sind alle Konten mit niedrigeren IDs ausgefallen, erklärt sich betreffender Member-Knoten als neuer Koordinator.

Ein neuer Koordinator setzt eine Kante vom Koordinator-Node zum entsprechenden Member-Knoten.