Big Data auf einem Mac mini

Neue Software macht es möglich, Aufgaben auf kleinen Computern zu erledigen, für die früher ganze Rechencluster notwendig waren.

Informatiker an der Carnegie Mellon University (CMU) haben neue Algorithmen zur Graphenberechnung entwickelt. Mit ihnen lassen sich Arbeiten auf einzelnen PCs ausführen, für die früher zahlreiche Server benötigt wurden.

Die Technik könnte Entwicklern helfen, die an zahlreichen modernen Problemen der Informatik arbeiten – von der Schaffung neuartiger Internet-Suchmaschinen bis zur Erstellung von Software, mit der Millionen von Verbindungen in einem sozialen Netzwerk analysiert werden können. Bei der dazu notwendigen "Graph Computation" müssen gigantische Datenmengen verarbeitet werden. Deshalb nutzt man dazu normalerweise ganze Rechencluster, die man beispielsweise bei Cloud-Computing-Anbietern wie Amazon anmieten kann.

Das CMU-Verfahren namens GraphChi will dies nun auch auf lokaler Ebene erlauben und nutzt dabei die zunehmend größer werdenden Festplatten, die in modernen Rechnern stecken. Ein Graph würde normalerweise zur Analyse im flüchtigen Speicher eines Clusters gelagert. Bei GraphChi wird diese Aufgabe vom RAM auf den Magnetspeicher verlagert.

"PCs haben nicht genügend RAM, um einen kompletten Web-Graphen im Speicher zu halten, aber sie haben Festplatten, auf die viele Daten passen", sagt Carlos Guestrin, Co-Direktor des SelectLab an der CMU, wo GraphChi entwickelt wurde. Das Problem: Festplatten sind im Vergleich zu RAM beim Lesen und Schreiben von Daten deutlich langsamer, was die Berechnungen normalerweise ausbremst. Aus diesem Grund entwickelte Guestrins wissenschaftlicher Mitarbeiter Aapo Kyrola eine effizientere Methode für den Festplattenzugriff, bei der sich der Lesekopf weniger zufällig über den Magnetspeicher bewegen muss.

Laut Guestrin kann ein einzelner Mac mini mit GraphChi den gesamten sozialen Graphen von Twitter aus dem Jahr 2010 berechnen. Dieser enthält immerhin 40 Millionen Nutzer und 1,2 Milliarden Verbindungen. Die dafür gestoppte Zeit: 59 Minuten. "Frühere zu diesem Problem publizierte Ergebnisse sprechen von 400 Minuten mit einem Cluster von rund 1000 Rechnern", berichtet der Informatiker stolz.

Mit einer beschleunigten Vernetzung und immer größeren Datensätzen werde die Graphenberechnung in zahlreichen Bereichen wichtig, meint David A. Bader, IT-Experte am Georgia Institute of Technology. "Egal ob wir wissen wollen, wie das menschliche Gehirn funktioniert oder ob wir versuchen, Tausende von Patientenakten zu analysieren – immer geht es darum."

Zudem treibt die Technik neuartige Web-Produkte. "Die Suche nach Dokumenten im Netz, die Platzierung von Anzeigen, das Berechnen von Routen, das Buchen von Flügen oder die Internet-Sicherheit bedingen alle Graph Computation", sagt MIT-Forscher Jeremy Kepner. "Wenn Internet-Entwickler diese Analysen auf ihren Desktop-Rechnern vornehmen können, beschleunigt das die Produktentwicklung und wird zum Innovationstreiber."

Guestrin zufolge kann GraphChi außerdem mit sogenannten Streaming-Graphs umgehen, bei denen große Netzwerke genauer modelliert werden, weil sie laufend erfassen, wie sich Beziehungen mit der Zeit verändern. Bader und andere Forscher am Georgia Institute of Technology haben bereits ein Framework namens Stinger für diese Verfahren entwickeln, doch ist es für Supercomputer gedacht, die mit riesigen Datenmengen hantieren.

"Der Umfang dieser Probleme wird natürlich wachsen", sagt Guestrin. Er glaube aber, dass GraphChi in der Lage ist, zahlreiche Graph-Computation-Probleme effektiv zu bearbeiten, ohne dass man auf Cloud-Systeme oder Supercomputer ausweichen muss. "Ein Forscher in der Bioinformatik könnte große Berechnungen auf seinem PC durchführen, ein Entwickler, der an Rechenzentrumsalgorithmen werkelt, diese auf dem Laptop testen, bevor sie online gehen."

Das Thema "Big Data" sei zwar in aller Munde, aber so riesig seien die Datensätze, relativ gesehen, mittlerweile nicht mehr. "Werkzeuge wie GraphChi werden es vielen Firmen erlauben, all ihre Bedürfnisse mit einzelnen Maschinen zu decken." Das sei kosteneffizient und bringe Innovationen voran. (bsc)