Benutzer:Johannes Kroll (WMDE)/CatGraph

(English version here.)

CatGraph (nicht zu verwechseln mit Catgraph. Wir müssen uns dringend einen besseren Namen ausdenken! ;)) ist eine im Auftrag von Wikimedia Deutschland entwickelte Graphdatenbank. Sie ermöglicht Entwicklern von Tools und anderer Software schnellen Zugriff auf die Wikipedia-Kategoriestruktur, zum Beispiel:

Finden aller Seiten in einer Kategorie mit einer beliebigen Suchtiefe innerhalb der Unterkategorien.
Finden von "Root Nodes", also Kategorien die in keiner Kategorie enthalten sind; in dewiki z. B. !Hauptkategorie.
Finden von Zyklen innerhalb der Kategoriestruktur, also Kategorien, die eine ihrer Oberkategorien enthalten (beta).
Verknüpfung von Suchergebnissen durch Bildung der Schnittmenge ("In A und in B") oder Differenz ("In A, aber nicht in B").

Der vollständige Kategoriegraph einer Wikipedia-Sprachversion wird im RAM gehalten. Die bereitgehaltenen Daten bestehen ausschließlich aus page_ids, die dann als Parameter für SQL-Abfragen benutzt werden können.

Beispiel-Abfrage

Folgende Abfrage liefert eine Liste die Schnittmenge der Seiten aus enwiki, die in den Kategorien Biology und People enthalten sind.

Es wird jeweils mit Suchtiefe 6 gesucht, das bedeutet, es werden die Unterkategorien und deren Unterkategorien, ... bis zur 6. Unterkategorie durchsucht. Der so ermittelte Subgraph 'Biology' enthält (während ich das schreibe) 381187 Seiten, der Subgraph 'People' 1852741 Seiten. Die Schnittmenge, also die Seiten, die in beiden Subgraphen enthalten sind, besteht aus 86042 Seiten.

$ time curl "http://sylvester.wmflabs.org:8090/enwiki/traverse-successors+692675+6+&&+traverse-successors+691008+6" >/dev/null
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100  705k    0  705k    0     0  67236      0 --:--:--  0:00:10 --:--:--  170k

real   0m10.759s
user   0m0.012s
sys    0m0.020s

Momentan laufende Instanzen

Eine Liste der momentan auf Wikimedia Labs laufenden Wiki-Graphen gibt es hier. Der Name der Graphen entspricht der Wiki-Instanz, z. B. dewiki für die deutsche Wikipedia. Die Endung steht für den Namensraum, z. B. beinhaltet "enwiki_ns14" den Kategorie-Namensraum der englischen Wikipedia. Graphen ohne eine solche Endung enthalten alle Namensräume.

Zur Zeit werden die Instanzen per cron-job in regelmäßigen Abständen vollständig aktualisiert. Den Zeitstempel des letzten Updates sieht man z. B. hier. Ein Skript, das die laufenden Änderungen sofort überträgt, ist in Arbeit.

Es ist geplant, nach und nach alle Wikipedia-Sprachversionen zu importieren.

Tools, die Catgraph nutzen

Der Render-Artikellistengenerator benutzt CatGraph für die Suche im Kategoriegraph.
CatCycle findet Zyklen in der Kategoriestruktur, also Kategorien, die eine ihrer Oberkategorien enthalten. Außerdem können Root Nodes und der kürzeste Pfad zwischen Kategorien angezeigt werden.
Merlissimo hat begonnen, an einer CatGraph-Schnittstelle für Merlbot zu arbeiten.

Ressourcen für Entwickler

gpClient: Bibliotheken zur Kommunikation mit CatGraph in PHP & Python.
Diesen Code könnte man benutzen, um in Python auf einfache Weise CatGraph-Abfragen als Textstrings auszuführen.
Dieses einfache Skript zeigt die Nutzung von gpClient mit PHP (Listing).

Kernkomponenten

Die Kernkomponenten sind in C++ implementiert. Einige Optimierungen wurden vorgenommen, um die Performance zu verbessern. Durch einen maßgeschneiderten mmap-basierten block-allocator sind Speicher-Allokationen schnell und der Speicherverbrauch nahe dem theoretischen Minimum.

In Graphcore ist die Graphdatenbank implementiert. Ein Graphcore-Prozess enthält jeweils eine Wikipedia-Sprachinstanz oder ein Subset der jeweiligen Namensräume. Die Knoten werden als vorzeichenlose Ganzzahlen dargestellt, die sich auf das page_id-Datenbankfeld beziehen. Graphcore kommuniziert mit einer einfachen zeilenbasierten Kommandosprache über stdin/stdout.

Graphserv kümmert sich um TCP-Verbindungen und den Datenfluss zwischen Clients und Graphcore-Instanzen (multiplexing). Außerdem wird eine einfache Zugangskontrolle mit Lese-, Schreib- und Administrationsrechten und Benutzername/Passwort-Authentifizierung zur Verfügung gestellt.