CatGraph
Jens Ohlig
10. Februar 2014
Im Maschinenraum der Softwareentwicklung von Wikimedia Deutschland entstehen nicht nur riesige Projekte wie Wikidata, sondern auch eine Menge kleinere Werkzeuge und Programme, die oft zu Unrecht unter dem Radar fliegen. In loser Folge wollen wir diese Projekte vorstellen.
Für den Anfang haben wir uns Johannes Kroll und das Projekt CatGraph vorgenommen. Johannes arbeitet seit Juni 2012 bei uns als Software-Entwickler und hat uns etwas dazu erzählt.
CatGraph, das Interview
Hallo Johannes! Du arbeitest für Wikimedia Deutschland an CatGraph, einem graphdatenbankbasierten Werkzeug für die Wikipedia. Wie begann das Projekt?
Ursprünglich hat Daniel Kinzler bemerkt, dass es viele Dinge im Wikiversum gibt, die mit Graphen zusammenhängen oder mit Graphdatenbanken eigentlich besser funktionieren würden. Vor allem wollten wir die Kategoriestruktur in der Wikipedia durchsuchen, auch rekursiv. Das funktioniert mit einer händischen Umsetzung in MySQL/MariaDB nicht wirklich gut, aber viele Tools machen das trotzdem so. Daniel hat dann damit angefangen, ein Werkzeug zu spezifizieren, nämlich eine Graphdatenbank, die speziell für die Kategoriestruktur der Wikipedia zugeschnitten ist. Dazu gab es dann eine Ausschreibung. Mehrere Leute haben sich beworben und ihre Implementierungsvorschläge eingeschickt, letztendlich wurde mein Projektangebot ausgewählt. Ich habe das dann geschrieben und seitdem ist es in Weiterentwicklung hier bei uns im Haus, auch im Rahmen des RENDER-Projektes, und wird seitdem auch von mir erweitert.
Kategorien in der Wikpedia kennen vermutlich viele Menschen, Artikel haben vielleicht Kategorien wie „Bauwerk in Leipzig“ oder „Epoche (Literatur)“. Warum reicht dafür eine normale Datenbank mit Tabellen nicht aus, wo Schlüssel und Werte in Zeilen abgespeichert werden? Warum brauchen wir da Graphen? Und was sind eigentlich Graphen in der Informatik?
Baumstruktur
Graphdatenbanken sind besonders gut dafür geeignet, rekursive Suchen auf einer verästelten, baumartigen Struktur auszuführen. Man kann sich so einen Graph, wie wir ihn verwenden, ganz gut als Baum vorstellen: Es gibt einen Stamm, von dem gehen Äste ab, die sich wieder verzweigen und immer dünner werden und irgendwann sind da Blätter dran, ganz am Ende. Diese Blätter sind die Artikel. Die Äste und ihre immer dünner werdenen Verzweigungen sind die Kategorien und Unterkategorien. (Das ist eine informelle Erklärung. Für eine genauere Unterscheidung der Begriffe Baum und (un)gerichteter Graph in der Informatik kann man z. B. hier oder hier nachlesen.)
Wenn ich in so einer baumartigen Struktur suchen möchte, ist das mit einer herkömmlichen SQL-Datenbank nicht nur für die Programmiererin oder den Programmierer sehr umständlich, es verbraucht auch sehr viel Rechenzeit und kann den Server stark blockieren, wenn es in alle Verzweigungstiefen hinabgeht. Wenn ich alle Artikel finden will, die vielleicht unter Biologie kategorisiert sind und in allen Unterkategorien wie Molekularbiologie, geht das in einer Graphdatenbank ziemlich gut, denn hier werden die Kategorie-Bäume als eigene Datenstruktur abgelegt und sind abrufbar, ohne dass ich alle Tabellen durchlaufen muss und mir den Baum selbst zusammenklauben muss.
Darüberhinaus kann ich auch Inkonsistenzen finden: Wenn eine Kategorie Unterkategorien enthält und eine dieser Unterkategorien enthält ihre eigene Oberkategorie, dann ist das eigentlich wie eine Endlosschleife oder ein Knoten im Graph, der in der Theorie nicht vorkommen sollte — aber in der Praxis gibt es sowas dann eben doch. Mit SQL dauert so eine Suche nach Inkonsistenzen sehr lange und ist sehr schwierig, mit einer Graphdatenbank geht das aber relativ schnell, oft mit einem einzigen Zugriff.
Architektur von CatGraph
Es gibt auch spezialisierte Software für Graphdatenbanken, in dem Bereich wird aktiv geforscht, weil es sich eben für viele Anwendungen anbietet. Aber auf fertige Lösungen wie Neo4j hast du gar nicht zurückgegriffen, sondern für die Wikipedia selbst etwas entwickelt…
Es sollte halt schon etwas sein, was genau auf die Kategorien der Wikipedia zugeschnitten ist, so habe ich das dann auch implementiert und für die Wikipedia funktioniert es ziemlich gut. Abfragen in CatGraph sind vernünftig schnell. Die Implementierung erlaubt uns, die Daten regelmäßig zu aktualisieren, ohne allzu große Belastung für die Server. Einige Optimierungen sorgen dafür, dass der Speicherverbrauch nicht mehr wächst als nötig. Natürlich ist das Projekt freie Software. Bei CatGraph kommt außerdem noch dazu, dass es ein zentraler Service ist. Wir starten (unter dem Namen GraphCore) verschiedene Prozesse, die jeweils einen Graphen enthalten, also eine komplette Wikipedia-Kategoriestruktur. Diese Prozesse können dann mit GraphServ sprechen. Mit diesem Serverprozess können sich dann Autorinnen und Autoren von Tools von außen verbinden. Hier wird dann auch die Last auf verschiedene Prozesse verteilt und auch eine Zugangskontrolle vorgenommen, damit zum Beispiel nicht jeder den Graph einfach löschen kann. Das ganze läuft auch verteilt auf verschiedenen virtuellen Maschinen und ich kann anfragen, auf welchen Server ich mich verbinden muss, wenn ich etwa auf die Datenbank der deutschsprachigen Wikipedia zugreifen will. Das alles läuft in einem eigenen Projekt in unserer Cloud-Infrastruktur Wikimedia Labs, mit der ich recht zufrieden bin. Der Support dort ist ziemlich gut, im IRC sind meistens hilfreiche Menschen zu finden und wenn ich mal mehr Platz brauche, kann ich mir einfach eine neue virtuelle Maschine erstellen.
CatGraph ist als Backend für Tool-Autorinnen und -Autoren gedacht, um bessere Tools zu schreiben oder einfacher mit Graphenstrukturen in der Wikipedia arbeiten zu können. Für die Programmiersprachen PHP und Python hat Daniel Bibliotheken entwickelt, die die Nutzung von CatGraph enorm vereinfachen. Die meisten Menschen werden aber vermutlich über Tools mit CatGraph in Berührung kommen, die die Graphdatenbank benutzen. Der Artikellistengenerator ist im RENDER-Projekt entwickelt worden und ist eine Webanwendung, mit der ich in der Wikipedia nach Kategoriestrukturen suchen und innerhalb der Strukturen dann filtern kann. CatCycle ist eine andere Webanwendung, die zyklisch verknüpfte Kategorien aufspürt.
Gerade der Artikellistengenerator könnte durchaus noch mehr von denen benutzt werden, die sich als Poweruser verstehen, aber nicht unbedingt Entwicklerinnen und Entwickler sind. Gedacht ist er für diejenigen in der Wikipedia, die sich in einem Bereich auskennen und zum Beispiel sehr kleine oder sehr große Artikel einer Kategorie finden wollen, die kleinen Artikel will ich vielleicht erweitern, die sehr großen eventuell aufteilen. Oder ich suche nach Artikeln in einer Kategorie, die keine Bilder haben — die Möglichkeiten sind ganz vielfältig. Das Tool kann auch leicht um neue Filter erweitert werden.
Zukunft und Aussichten
Wo es natürlich auch eine Menge Graphen gibt, das ist Wikidata. Es gibt bereits Visualisierungen über Stammbäume zum Beispiel. Viel von dem, was in Wikidata vorhanden ist, bietet sich an, als Graphenstruktur abzubilden, zu speichern und zu durchsuchen. Soll deine Software über Kategorien hinauswachsen und wäre es dann überhaupt noch CatGraph oder wäre es dann was anderes?
Tatsächlich bin ich gerade dabei, einige Eigenschaften oder Properties von Wikidata zu importieren. Das wird einer der nächsten Schritte sein. Ich warte noch auf ein paar Anpassungen bei Wikidata, aber dann sollte es zum Beispiel möglich sein, die Taxonomie im Tier- und Pflanzenreich als Graph durchsuchbar abzuspeichern. Stammbäume von Personen oder geographische Inklusion wären andere Anwendungen. Nach und nach werden wir diese Strukturen als Erweiterung einbauen und dann stehen sie auch als zusätzliche Möglichkeit für Datenbankabfragen in Wikidata zur Verfügung.
Allgemein fände ich es schön, wenn CatGraph etwas bekannter wäre und häufiger benutzt würde. Über Feedback aus der Community würde ich mich freuen, zum Beispiel Anregungen und Ideen für Einsatzbereiche und wo wir es verbessern könnten. Es wäre gut, wenn einfach mehr Leute davon erfahren, dass wir hier eine Graphdatenbank haben, die ständig mit aktuellen Daten aus der Wikipedia versorgt wird und die für alle verfügbar ist.
