Wie Inventur im Baumarkt...

Das MapReduce Verfahren und die Umsetzung in Apache Hadoop

Warum speichern wir unsere Daten eigentlich nicht mehr auf den guten alten 5 ¼ Disketten? Sie wären sicher vor Zugriffen von außen und vor Netzwerkausfällen. Eine feine Sache also. Die Antwort ist recht einfach und eigentlich jedem klar, der irgendwann eine dieser dünnen schwarzen rechteckigen Scheiben in der Hand hatte. Die Speicherkapazität einer Diskette ist so gering, dass man allein für den Hausgebrauch wohl ein kleines Zimmer bräuchte, in dem man elektronisch gespeicherte Dokumente, Präsentationen und Urlaubsfotos auf hunderten solcher Datenträger aufbewahren würde. Wollte man noch zusätzlich Videodateien archivieren, müsste bald auch die Garage als „Speicher“ herhalten.

In Büros dagegen würde man sich genötigt sehen, das Gebäude zu unterkellern. Abgesehen von der unhandlichen Datenhaltung kämen noch die erschwerten Datenzugriffe hinzu. Mit der Suche nach einem Kundendatensatz aus dem vorigen Geschäftsjahr könnte man einen halben Arbeitstag verbringen, bis man in den langen Regalen im Kellerarchiv auf den richtigen Karton mit der darin enthaltenen gesuchten Diskette stoßen würde.

Noch aufwändiger würde es bei etwas professionelleren Datensammlern wie z.B. sozialen Netzwerken. Quartalsmäßig müssten neue Lagerstätten von der Größe eines 60.000 Zuschauer fassenden Fußballstadions errichtet werden. Von überall auf der Welt würden Disketten mit Daten eingesendet werden, die den richtigen Benutzer zugeordnet und so gelagert werden müssten, dass man sie schnell wieder finden kann. Hunderte, vielleicht sogar tausende Archivare wären damit beschäftigt den Betrieb zumindest notdürftig aufrecht zu erhalten.

Kurzum, egal ob im Privatgebrauch, in der Geschäftswelt oder in der Welt des Web 2.0, in allen Bereichen wäre es impraktikabel, mit Wechseldatenträgern im herkömmlichen Sinn zu arbeiten und daher begann man – als die Datenmengen anstiegen - diese zunehmend auf anderem Weg zu archivieren.

Neue Wege zur Datenspeicherung

Im privaten Bereich werden die Bedürfnisse weitgehend durch Festplatten mit Kapazitäten im Gigabyte bis Terrabyte-Bereich und kleinere NAS Systeme gedeckt. In der Geschäftswelt greift man auf relationale Datenbanksysteme zurück, die die Datensätze in virtuellen Regalen, den über Schlüssel verknüpften Tabellen, lagern. Die Datenbankserver stehen dazu gerne tatsächlich im Keller der Geschäftsräume, aber der Gang dorthin bleibt dem Abrufenden erspart, reichen doch einige Mausklicks oder SQL Befehle, um die Daten direkt auf den Bildschirm geliefert zu bekommen.

Schwierig bleibt es aber bei den Web 2.0 Anwendungen, nämlich genau dann, wenn viele Klienten aus vielen verschiedenen Orten gleichzeitig auf Daten zugreifen wollen. Zwar gibt es bei relationalen Datenbanksystemen keine Archivare, die durch Kellerarchive huschen müssen, aber die Anlieferung von vielen Punkten der Welt an eine zentrale Datenhaltung, die Suche darin und die Auslieferung stellen nach wie vor ein Problem dar, welches aufgrund der anwachsenden Datenbergs und der zunehmenden Entfernungen – durch relationale Datenbanksysteme nicht mehr gelöst werden kann.

Das CAP Theorem

Die relationalen Datenbanksysteme sind für den Zweck, den Datenhaltungssysteme im Web 2.0 erfüllen müssen also ungeeignet. Die Analyse, ob sich ein bestimmtes System zur Haltung bestimmter Daten zu einem bestimmten Zweck eignet beruht auf dem CAP-Theorem.

Dieses besagt, dass in einem (verteilten) Datenbanksystem nur zwei der drei Eigenschaften

  • Konsistenz (Consistency)
  • Verfügbarkeit (Availability)
  • Partitionstoleranz (Partition tolerance)

gleichzeitig gegeben sein können.

Konsistent ist ein Datenhaltungs-System demnach, wenn alle seine Knoten zu jedem Zeitpunkt die gleichen Daten sehen. Es erfüllt die Eigenschaft „Verfügbarkeit“, wenn all Anfragen auf das System stets beantwortet werden. Und es ist Partitionstolerant, wenn auch bei Ausfall oder Datenverlust einiger Knoten das System noch funktionstüchtig bleibt.

Es ist nicht möglich, alle drei Eigenschaften gleichzeitig vorzufinden, da bei Ausfall eines Knotens entweder dieser aus dem System ausgegliedert werden müsste – damit wäre dessen Datenhaltung nicht mehr Konsistent zu der Datenhaltung der anderen Knoten – oder die Anfragen ans System dürften für den Zeitraum des Ausfalls nicht mehr verarbeitet werden. Damit wäre die Konsistenz gewahrt, aber die Verfügbarkeit eingeschränkt. Oder man verzichtet, wie beim Einsatz der relationalen Datenbanksysteme im Allgemeinen, darauf, mehrere Datenhaltungsknoten einzusetzen und gibt damit die Partitionstoleranz auf. Eine Entscheidung, die nicht einfach ist und zweckgebunden getroffen werden muss.

Man kann sich das CAP-Theorem aber auch positiv zu Nutze machen, indem man sich fragt: Welche zwei Eigenschaften sind denn für mein System überhaupt sinnvoll und notwendig. Bei den RDBMS geht man davon aus, dass die Eigenschaften C (Consistency) und A (Availability) erfüllt sein sollen.

Bei extrem konsistenzkritischen Anwendungen, wie beispielsweise Finanztransaktionen, setzt man auf Systeme, die die Eigenschaften C und P (Partition tolerance) erfüllen. Damit ist sichergestellt, dass keine Transaktionen durchgeführt werden können, so lange Teile des Systems nicht verfügbar sind.

Die Frage, die man sich bei den enormen Datensammlungen im Bereich des Web 2.0 stellt ist: Lohnt es sich überhaupt, alle Daten in allen Knoten gleichermaßen sichtbar zu machen? Lohnt es sich, den Datenverkehr extrem aufzublähen und Daten rund um die Welt zu schicken, nur um beispielsweise die Urlaubsfotos eines Europäers, die in Australien gemacht wurden auch auf einem Datenbank-Knoten in Nordamerika vorzuhalten? Oder anders gefragt: Hat dieses Vorgehen eine höhere Priorität als die ständige Verfügbarkeit des Gesamtsystems? Man entschied sich dafür, dass im Zweifelsfall lieber auf ein paar Urlaubsfotos verzichtet werden soll, als dass allen Benutzern das Gesamtsystem vorenthalten wird. Man entschied sich für ein AP-System.

Neue Datenhaltung, neue Probleme

So gut diese Entscheidung unter den Gesichtspunkten der Verfügbarkeit und des reduzierten Datenverkehrs auch sein mag, es bleibt die Frage, wie nun trotzdem die Daten, die auf einem Knoten am einen Ende der Welt lagern bei einer Suche am anderen Ende der Welt auch gefunden werden können? Die Lösung gleicht einer Inventur in einer Baumarkt-Kette. Viele Gehilfen zählen vor Ort in jeder Filiale alle Schrauben eines bestimmten Typs. Die Ergebnisse werden notiert und am Ende in der Zentrale aufsummiert.

Münzt man diese Vorgehensweise auf Datenbanksysteme spricht man vom MapReduce Verfahren.

Hierbei sucht jeder Teilknoten während der Map-Phase in seinem Datenpool nach Ergebnissen zu einer zentral gestellten Anfrage und liefert die Ergebnisse zum Master-Knoten. Dieser sammelt alle zu dieser Anfrage eingegangenen Ergebnisse, entfernt während der Reduce-Phase mögliche Duplikate, summiert die Ergebnisse auf, und liefert sie zum Anfragesteller aus.

Werden nun beispielsweise Urlaubsfotos gesucht, die rund um die Welt entstanden und abgelegt worden sind, so werden sie zwar nur auf dem jeweiligen Knoten gespeichert, dann aber innerhalb des Knotens gesucht, gefunden und an den Abfrageknoten gesendet.

1.png

Apache Hadoop

So funktionieren die verteilten NoSQL-Datenbanksysteme jedenfalls im Groben. Implementierungen dafür gibt es einige. Eine Java basierte Umsetzung ist das Framework Hadoop, welches als Open Source Lösung unter der Apache Lizenz verfügbar ist

Es besteht aus der MapReduce Engine und dem Hadoop Disributed File System (HDFS), das sich durch hohe Verfügbarkeit, Speicherung und Verwaltung sehr großer Datenmengen, hohe Skalierbarkeit und einfache Erweiterbarkeit der Speichergröße auszeichnet.

Das HDFS kann geclustert werden, wobei jeder Cluster aus einem Knoten besteht auf dem Metadaten zu allen Daten gespeichert werden (Name Node) und vielen Knoten, auf denen die eigentlichen Daten verteilt werden (Data Nodes). Um zusätzlich zur Verteilung auf nahe Knoten auch noch eine Sicherheit vor Datenverlust zu haben, werden die Daten nicht nur verteilt, sondern bei der Verteilung auch repliziert, sodass sie mehrfach (standardmäßig drei Mal) auf verschiedenen Knoten vorhanden sind. Die Data Nodes können untereinander kommunizieren, um eventuelle Knoten-Ausfälle zu kompensieren und die Daten entsprechend umzulagern. Dadurch wird der Einsatz eines RAID Systems überflüssig.

2.png
 

Der Anfragensteller (Job Tracker) der MapReduce Engine und der Name Node bilden zusammen einen Knoten im Cluster, den Master Node. Jeder Data Node dagegen bildet zusammen mit einer selbstständigen Sucheinheit der MapReduce Engine (einem Task Tracker) einen Slave Node, wobei der Job Tracker auch die Arbeit der Reduce-Phase an die Slave Knoten verteilt und zwar so, dass möglichst wenig Datenverkehr entsteht.

So kann Hadoop mit Datenmengen bis hin zu Exabytes (1.000.000 Terabytes) umgehen, während relationale Datenbanksysteme bereits bei Mengen im mittleren Terabyte Bereich an ihre Grenzen stoßen. Das macht Hadoop für die Big Players der Internetbranche interessant. In den großen Suchmaschinen, den erfolgreichsten geschäfts- und sozialen Netzwerken, bekannten Microblogging-Diensten und Newsportalen, wird es zur Datenhaltung seit Jahren erfolgreich eingesetzt.

Wachsende Popularität

Dabei gibt es nicht DEN einen Grund, der Hadoop so gefragt macht, sondern viele kleine Vorteile. Die einfache, lineare Skalierbarkeit und die niedrigen Anforderungen, die an einen Datenknoten gestellt werden, sind die wohl herausstechenden. Es ist ausreichend, dass eine Java Runtime Environement auf einem System installiert ist, das als Datenknoten genutzt werden soll, mehr Leistungsanforderungen werden für die grundsätzliche Funktionalität nicht gestellt. Prinzipiell käme also nahezu jeder halbwegs moderne Home PC dafür in Frage

Mit dem immer vielseitigeren Angebot an Cloud-Datenhaltung, der notwendigen verteilten Verarbeitung dieser Daten mit ansteigenden Datenmengen und immer dezentralerem Arbeiten werden MapReduce Verfahren und verteilte File Systeme für immer mehr Unternehmen interessant. Bei der Suche nach ausgereiften Implementierungen ist es Wert, Hadoop näher zu betrachten.

Es sei denn, man versteht unter verteilter Datenhaltung doch noch das Einlagern von Disketten in Hallen, so groß wie Fußballstadien…