October 12, 2015 / by Torsten Bøgh Köster / CTO / @tboeghk
Wie wir es lieben lernten, die Exaktheit der Geschwindigkeit zu opfern
“Wenn Du kein Big Data machen musst, lass es bleiben!” - schon ein paarmal auf Konferenzen gehört, inzwischen eine Aussage, die man nur allzu gut nachvollziehen kann. Vor allem, wenn man sich an ausufernden Ressourcenanforderungen, langen Laufzeiten und angestaubten Batchprozessen von “Big Data” eine blutige Nase geholt hat. Wie aber sieht es im “Grenzgebiet” von “Big Data” aus: Wenn zu viele Daten für die klassische Verarbeitung vorliegen, aber nahezu Echtzeitanforderungen an Prozesse bestehen? Hier helfen probabilistische Verarbeitungsansätze Probleme klein zu rechnen.
“Jetzt mal ehrlich? Wie genau muss es denn wirklich sein?”
Im Laufe des letzten Projektes kam diese Frage immer wieder hoch. Sei es im Kontext eines Suchergebnisses auf unseren Portalen mit 4,5 Mio Handys, 1,9 Mio T-Shirts oder bei der Frage, ob eine Handtasche zehn oder elfmal gekauft wurde. Als Produktsuchmaschine befinden wir uns im Grenzbereich zu Big Data: Wir jonglieren 40 Mio. Produkte und 6 Mio Nutzerinteraktionen täglich. Irgendwann wurde uns klar, dass es bei der Datenverarbeitung selten auf exakte Zahlen sondern vor allem auf kurze Verarbeitungszeit ankommt.
Selbstverständlich waren wir voll auf den Hadoop-Big-Data-Zug mit aufgesprungen. Wir hatten alle unsere Daten in ein HDFS gestopft - vielleicht würde ja irgendwie etwas Sinnvolles herauskommen. Es war charmant, langsam laufende Analyseprozesse einfach mit Amazon EMR-Clustern zu bewerfen. Teuer aber charmant.
Aus der Produktentwicklung wurden die Forderungen nach (fast) Echtzeitrückkopplung von Nutzerinteraktionen in unsere Suchergebnisse immer lauter. So begannen wir, die Hadoop-Jobs Stück für Stück abzubauen und unsere Verarbeitungsprozesse dahin umzubauen, dass sich alle benötigten Daten im Heap halten lassen. So können Daten auf einem einzelnen System mit moderater Ausstattung verarbeitet werden und andere Systeme können sich dort in (fast) Echtzeit bedienen.
Die “Einstiegsdroge” in die Welt der probabilistischen Datenstrukturen ist wohl der Bloomfilter. Er eignet sich für Existenzfragen auf eine Menge (“Enthält die Datenbasis einen Datensatz mit der ID xy?”). Intern bildet er die hinzugefügten Werte über eine Hashfunktion auf ein Bitset fester Größe ab. Durch die Speicherung als Bitset wird weniger Heap benötigt als beim Vorhalten der Originalwerte z.B. in einem Array. Durch das Abbilden mittels der Hashfunktion kann die Existenzabfrage auch in sublinearer Komplexität realisiert werden - das Durchsuchen eines Arrays hingegen hat lineare Komplexität. Der entscheidende Nachteil des Hashings ist, dass die enthaltenen Werte nicht wieder abgerufen werden können und false Positives entstehen werden. Über die Länge des Bitsets lässt sich die Fehlerwahrscheinlichkeit in Abhängigkeit der Menge der eingegebenen Schlüssel minimieren. Wir nutzen den Bloomfilter u.a. als Cache, ob Produkte für einen Mandanten aktiv sind oder nicht.
Der sog. Count-Min-Sketch ist ein “Bloomfilter auf Steroiden”. Er kann zu einem Key nicht nur einen boolschen sondern einen numerischen Wert speichern. Intern werden über unterschiedliche Hashingfunktionen die Werte auf Bitsets abgebildet. Durch Extraktion des errechneten Minimums aus den Bitsets kann der gespeicherte Wert (mit einer gewissen Wahrscheinlichkeit) wieder abgerufen werden. Wie beim Bloomfilter erfolgt diese Berechnung in sublinearer Komplexität. Die Fehlerwahrscheinlichkeit lässt ich auch hier über die Länge und Anzahl der Bitsets einstellen. Aber auch hier können die eingegebenen Keys nicht wieder extrahiert werden.
Durch die extrem kompakte Speicherung mittels Bitsets lassen sich sehr viele Key-Value-Paare auch im Heap vorhalten. Wir nutzen Count-Min-Sketches zum Vorhalten von Popularitätswerten von Produkten zu Suchanfragen. Dabei wird für jede Suchanfrage ein Count-Min-Sketch vorgehalten, in dem zu jedem Produkt die Popularitätswerte vorgehalten werden. Die intern genutzten Bitsets lassen sich serialisieren und in nahezu Echtzeit im Cluster replizieren. Da die Bitsetlänge fest ist, kann für eine Menge von Count-Min-Sketchen oder auch Bloomfiltern vorberechnet werden, wieviel Heap benötigt wird.
Auch für andere Probleme finden sich spannende probabilistische Datenstrukturen. Der TopK-Algorithmus z.B. eignet sich dafür, aus einem kontinuierlichen Datenstrom die Top n Begriffe zu extrahieren (nutzen wir z.B. für Top-Suchbegriffe). In einem HyperLogLog lässt sich die Kardinalität unterschiedlicher Werte einer Menge effizient festhalten. Wem diese Algorithmen noch nicht genug Mathe sind, dem sei noch ein Blick in die Statistik angeraten. Analysen auf großen Datenmengen lassen sich auf statistisch repräsentativen Teilmengen wesentlich schneller durchführen.
Zuviel Mathe? Kann ich gut verstehen. Formeln beeindrucken und schrecken gleichzeitig ab. Und wie implementiert man nochmal ein Integral in Java? Das Gute: Für alle o.g. Algorithmen finden sich sehr brauchbare Bibliotheken. Für Java und Scala die Streaming-Library, der HyperLogLog hat in die meisten Datastores Einzug gefunden (u.a. Postgresql, Redis) und für Spark finden sich auch Implementationen.
Die Benutzung probabilistischer Algorithmen muss in einen fachlichen Kontext passen, in dem Exaktheit nicht das primäre Ziel ist. Wenn der PO eine 100%ige Nachvollziehbarkeit der Ergebnisse fordert, hat man ein Problem. Auch sollte der Einsatzkontext in wirklich großen Datenmengen liegen, sonst lohnt sich der (mentale) Overhead nicht. Was eine große Datenmenge ist? Kommt drauf an: Ausprobieren!
