Big Data für das Internet der Dinge (IoT)
IoT-Netzwerke werden immer größer und ihre Vermaschung nimmt immer weiter zu. Damit steigen auch die Anforderungen, da die Datenmengen erheblich an Volumen zunehmen und in anderen Bereichen oftmals Rechenleistung nicht optimal ausgenutzt wird. Allerdings sind die meisten Ansätze im Bereich IoT derzeitig noch sternförmig. Dennoch kommen einem die Anforderungen doch sehr bekannt vor, wenn man sich mit Big Data beschäftigt. Was also kann man aus der Welt des Big Data transformieren auf die Welt des IoT? Welche Algorithmen, welche Technologien sind für den Einsatz im IoT-Umfeld sinnvoll? Welche Dinge muss man anpassen? Wichtig auf jeden Fall: Welche Erfahrungen können hier gewinnbringend eingesetzt werden.
Eigenschaften Big Data
Aber sehen wir uns zuerst die Kerneigenschaften von Big Data an. Hier gibt es einige implizite Annahmen, die auch Auswirkungen auf die Algorithmen haben. Es wird angenommen, dass alle Knoten gleichförmig sind. Demnach ist es von diesem Punkt aus egal, auf welchem Knoten eine Aufgabe durchgeführt wird. Demnach hat auch jeder Knoten die gleiche Menge an Arbeitsspeicher, Festplattenkapazität und Prozessoren. Zudem wird davon ausgegangen, das jeder Knoten über eine unerschöpfliche Menge an Energie verfügt. Die Kommunikation zwischen den Knoten wird als weitestgehend stabil angesehen, da in den meisten Fällen alle Knoten in einem Rechenzentrum nahe beisammen stehen.
Die Daten liegen in Big Data-Anwendungen meist in großen Blöcken vor. Hier sprechen wir von mehreren hundert MB oder GB. Ein solches Datenpacket entspricht in der Regel auch einem Arbeitspaket. Diese Annahmen eignen sich bestens für Batch-Prozesse. Hier werden Daten über einen Zeitraum gesammelt und dann in einem Vorgang verarbeitet. Beispiele sind hier die Buchungen einer Bank, die an bestimmten Zeitpunkten des Tages verarbeitet werden. Damit ist meist auch noch eine weitere Annahme getroffen: Die Daten sind zumeist sehr gleichförmig. Im Umkehrschluss bedeutet das aber auch, dass Streamingprozesse nicht so einfach abzubilden sind.
Um Ausfallsicherheit und Skalierbarkeit zu erreichen, werden Daten in Big Data-Anwendungen (z. B. Hadoop/ HDFS ) n-fach vorgehalten. Es kann damit eine Verarbeitung eines Datenpakets auf n Knoten gestartet werden. Sobald einer fertig ist, werden die anderen Berechnungen abgebrochen. Damit kann man den Durchsatz der Anwendung erhöhen. Ebenfalls wird damit die Ausfallsicherheit erhöht, da der Ausfall eines Knotens nicht zu Verlusten führt. Das hat natürlich auch Auswirkungen auf das Design der Algorithmen. Allerdigs erhöht man dadurch auch das Verhältnis Energieverbrauch/ Datenpaket und Berechnung. Darauf komme ich später nocheinmal zurück.
Bei Big Data-Systemen handelt es sich meistens um verteilte Systeme. Zur Definition verteilter Systeme gehören verschiedene Formen der Transparenzen, wobei ich hier lediglich die Ortstransparenz der Datenblöcke anmerken möchte. Demnach ist nicht bekannt, auf welchem Knoten die Daten und die Replikationen vorhanden sind. Der große Durchbruch erfolgte, als die Idee und erste Implementierung von MapReduce vorgestellt worden ist. Der Grundgedanke ist hierbei, dass sich die Algorithmen zu den Daten bewegen und nicht umgekehrt. Man kann sich das so vorstellen, dass es günstiger ist, ein kleines jar-File zu dem Knoten zu senden auf dem die Daten vorhanden sind und nicht umgekehrt.
Eigenschaften von IoT
Wenn man sich nun im Gegenzug die Eigenschaften von IoT-Netzwerken ansieht, stellt man fest, dass nur sehr begrenzte Rechenkapazitäten vorhanden sind. Es handelt sich um Prozessoren mit zumeist weniger Cores als auch weniger Rechenleistung/ Core. Die Hardware ist auf Energieeffizienz hin optimiert. Das bedeutet aber auch, das wir ein sehr gutes Verhältnis von Rechenleistung zu Energieverbrauch (inkl. Kühlung) haben. Warum also damit keine Rechenzentren aufbauen? Dies ist Gegenstand verschiedener Forschungseinrichtungen. Allerdings bezieht sich dies nur auf die Energiebilanz der Prozessoren.
IoT-Netzwerke bestehen teilweise aus mobilen Komponenten. Diese verfügen über unterschiedliche Bandbreite/ Knoten. Die Energieversorgung ist bei mobilen Komponenten endlich. Dadurch ergibt sich eine grundlegende Frage: Dürfen Komponenten "sterben"? Wenn ja, wie entscheidet man dies? Wer kann das entscheiden? Der verfügbare Arbeitsspeicher pro Knoten ist ebenfalls als eher gering anzusehen, was wiederum Auswirkungen auf die Algorithmen hat. Entweder benötigt man mehr Rechenleistung (und damit Energie) um die Zwischenergebnisse wiederholt zu berechnen oder mehr Speicherplatz um Zwischenergebnisse behalten zu können. Leider ist Speicher ebenfalls Mangelware.
Die Teilnehmer in einem IoT-Netzwerk sind oftmals sehr unterschiedlich dimensioniert und die Konfiguration auch noch dynamisch. Alles scheint gegen den Einsatz von Big Data-Technologie zu sprechen. Wie kann man also nun Big Data auf IoT mappen?
Komponenten und Einflussgrößen
Um sich diesem Problem zu nähern müssen wir abstrahieren. Wichtig ist, dass man nicht auf der Suche nach einer global-galaktischen Lösung ist und in der Lage ist, die Randbedingungen zu definieren. Wenn man damit fertig ist, kommt der schwierige Teil: Man versucht, es einem Mathematiker zu erklären. Wenn man nun alle Fragen beantworten konnte, wird das Problem meist zu einem Graphen. Allerdings mit allen Vor- und Nachteilen.
Nun haben wir also eine Menge von Kanten und Knoten.
Der schwierige Teil: Erklären Sie es einem Mathematiker
Knoten
Die Knoten in diesem Netzwerk kann man in verschiedene Typen unterteilen.
- Prozessoren
Prozessoren modellieren wir als Laufzeitcontainer mit Eigenschaften wie z. B. paralleler oder sequenzieller Rechenleistung. Die wichtigeste Eigenschaft jedoch ist die Repräsentation, ob die Energiezuführ endlich oder begrenzt ist. Wenn eine Begrenzung vorhanden ist, dann stellt sich auch gleich die Frage, wie lange der Energievorrat reicht. Können damit die anstehenden Aufgaben gelöst werden oder nicht. Wenn nicht, dann muss entschieden werden, welche noch durchgeführt werden. - Datenspeicher
Eine für die Algorithmen durchaus wichtige Eigenschaft ist die des zur Verfügung stehenden Speichers. Die Attribute sind recht einfach und klar definiert. Das ist zum einen die Größe und zum anderen ob es sich um persistenten oder transienten Speicher handelt. Was sich bisher als nicht wichtig erwiesen hat, ist die Geschwindigkeit des Speicherplatzes. Das führte meist zu komplizierteren Modellen, ohne jedoch den gewünschten Effekt zu bringen. - Ausgabemedien
Ein Knoten des Typs "Ausgabemedium" beschreibt im unidirektionalen Fall Drucker und Monitore und im bidirektionalen Fall z. B. Touchscreens. - Unterscheidung
Eine weitere Ebene der Gruppierung kann es sein, die Knoten in aktive und passive Knoten zu unterteilen. Ob das wichtig ist, hängt von den Optimierungszielen innerhalb des Netzwerkes ab.
Kanten
Mittels der Kanten verbinden wir nun die aktiven Knoten. Auch Kanten können Attribute besitzen, was in diesem Fall der Abbildung der Kommunikationskanäle entspricht. Kanten besitzen Attribute wie
- Bandbreite
- Datenkapazität (un-/begrenzt)
- Energieverbrauch
- Kommunikationsrichtung (uni-/ bi-direktional)
- Stabilität/ Zuverlässigkeit
Aktivitäten im System
Bisher wurden nur die Teilnehmer modelliert. Das allerdings entspricht einem statischen Umfeld. Die Realität sieht meist anders aus. Demnach müssen noch die Aktivitäten in dem System/ Modell abgebildet werden. Die einfachsten Aktivitäten sind der Eingang von Daten und deren Transformation. Hierbei handelt es sich um eine Aktivität, aber keine Veränderung des Systems. Diese wird durch das Hinzukommen und Wegfallen von Knoten und Kanten erreicht. Und genau diese Dynamik sorgt für eine teilweise nicht zu unterschätzende Komplexität. Aber wo und wie zeigt sich dieses?
Lokalität
Um mit dem Begriff der Dynamik besser zurecht zu kommen, betrachten wir zuerst den Begriff der Lokalität. Nur in abgeschlossenen Bereichen hat man die Chance mit verhältnismäßig überschaubarem Aufwand zu Lösungen zu kommen. Aber was bedeutet Lokalität? Im Bereich von Big Data kann man sich das so vorstellen, dass wir die zur Verfügung stehende Hardware (und damit auch die Daten) recht nah beieinander stehen haben, z.B. in einem Rechenzentrum. In diesem Bereich skaliert z. B. Map/Reduce recht gut. Hier kann man die Anzahl und den Ort der Knoten meist sogar sehr genau bestimmen.
Aber wie sieht es bei IoT-Netzwerken aus? Was ist dort Lokalität? Hier definieren wir den Raum über die Anzahl der Hops zwischen Knoten oder anders ausgedrückt: die Summe der Kanten zwischen Start- und Stop-Knoten. Der Begriff "kurz" ist demnach nicht mehr geographisch zu verstehen. Hier spielt die Bandbreite ebenfalls eine Rolle. Gehen wir also im Folgenden davon aus, dass die Nähe untereinander eine Funktion von Kantenanzahl und Bandbreite ist. Nun sind wir in der Lage, den Raum zu begrenzen und darauf basierend unsere Algorithmen anzupassen und zu dimensionieren.
Ziel bei IoT-Netzwerken ist es, eine dezentrale Organisationsform zu finden. Das bedeutet, dass es sich immer um das Finden von lokal optimalen Lösungen handelt. Die Aufgabe ist es, die Prozesse/ Aufgaben in dem Netz nach bestimmten Optimierungskriterien zu verteilen, ohne dass es eine zentrale Steuerungseinheit gibt.
Wie nun beginnt man die Prozesse in dem Gesamtsystem zu distributieren? Es hat sich herausgestellt, dass es besser ist, wenn sich ein Job einen freien Prozessor sucht. Andernfalls müssten die Informationen, welcher Prozessor frei ist, in dem Netz verteilt werden. Das macht natürlich nur Sinn, wenn es mehr Prozesse als Prozessoren gibt. Aus mathematischer Sicht ist das Problem jedoch symmetrisch. Allerdings haben wir hier eine implizite Annahme getroffen. Wir gehen immer davon aus, dass es eine Lösung gibt. Wir haben es hier also mit einem klassischen Matchingproblem zu tun: Job sucht Prozessor.
Allerdings kann ich nur empfehlen, zu Beginn mit rein sequenziellen Suchen zu beginnen. Parallele Suchen führen schnell zu Konflikten und zu einer hohen Anzahl unnötig allokierter Ressourcen. Das kommt daher, dass alle Kanten entlang einer Suchanfrage gesperrt werden müssen. Das auch, wenn man nicht weiß, ob der Weg gerade zu einer Lösung führt. Parallele Suchanfragen führen demnach schnell zu exponenziellem Anstieg in der Ressourcenbelegung. Sobald eine Suche beendet ist und die Abarbeitung beginnt, kann bei jedem erfolgreich beendeten Schritt die verwendete Kante wieder freigegeben werden.
Unabhängig davon stellt sich sofort die Frage: kann ein freier Prozessor eine Suchanfrage eines Jobs annehmen, wenn gleichzeitig eine Suchanfrage von ihm selbst aussteht?
Die Lösung ist recht trivial: Entweder suchen nur Jobs oder nur Prozessoren und jede Komponente hat maximal nur eine ausstehende Suchanfrage. Im allgemeinen gilt, dass Handshake-Verfahren zu vermeiden sind, da es sich hierbei um recht teure Aktionen handelt.
Algorithmus und Daten
Eine Sache haben wir bisher nicht betrachtet. Zu welcher Komponente gehört eigentlich der Algorithmus? Ist er eine eigenständige Komponente oder gehört er zu einem Prozessor oder Job? Da wir verschiedene Algorithmen zur selben Zeit verwenden wollen, definieren wir, dass ein Job aus Daten und Algorithmus besteht. Der Algorithmus wird zu den Daten gesendet und bildet dann eine Einheit.
Anfangs/Ende-Bestimmung
Bei der Definition der Systemzustände kann man nun verschiedene Annahmen treffen, oder auch Forderungen aufstellen. Formulieren wir diese erst einmal als Fragen: Wie kann eine globale Aufgabenerfüllung im System überprüft und sichergestellt werden? Wie ist das (lokale) Ende des Algorithmus überhaupt definiert? Gibt es unterschiedliche "lokale" Ende-Zeitpunkte? Hier meine ich die Endezeitpunkte einer jeden Verarbeitungsstufe in der Kette.
Je mehr man sich damit beschäftigt, desto mehr stellt man fest, dass diese Annahmen und Anforderungen oftmals nicht notwendig sind. Es hat sich gezeigt, das ein vollständiger Verzicht auf eine Ende-Definition sinnvoll sein kann. Das liegt darin begründet, dass die Veränderbarkeit des Gesamtsystems miteinbezogen wird. Genauso verhält es sich mit den Ausgangssituationen. Es gibt nur eine Annahme die zu Beginn getroffen werden sollte: Das Gesamtsystem befindet sich in irgendeinem stabilen Zustand. Das reicht meist aus, um mit den ersten Versionen der Implementierung zu beginnen.
Modellierung der Problemstellung
Wie nun kann man sich praktisch der Problemstellung nähern? Als erstes sollte man mit einem statischen Modell beginnen, um zu einer Verteilung von Jobs auf Knoten zu gelangen. Das beinhaltet unter anderem den Aufbau der Kommunikationswege, also der Wege, die von den jeweligen Datenpaketen und Algorithmen in diesem Netzwerk genommen werden. Hierbei ist auch wieder wichtig, dass man zuerst eine Lösung für ein konkretes Problem sucht und nicht mit zu generischen Lösungen beginnt. Es gibt dabei zwei Ziele die hintereinander anvisiert werden sollten: Zum ersten das robuste Finden einer gültigen Lösung und dann das Finden eines lokalen Optimums. Hierbei muss es sich nicht um das absolute Optimum handeln.
Aus dieser Lösung kann man nun ableiten, wie die Kanten und Knoten untereinander in Relation stehen. Hierbei kann es durchaus unterchiedliche Sichtweisen geben. Jedoch ist es nun möglich, daraus relative Kennzahlen zu ermitteln, die für die Priorisierung und Vergabe von Prozessoren zu einer jeweiligen Aufgabe herangezogen werden können. Sicherlich handelt es sich in diesem Stadium um ein statisches Modell, welches nun als Basis für das dynamische Modell verwendet werden kann. Allerdings sollte man von fixen Kennzahlen Abstand nehmen. Am besten ist es, wenn die Kallibrierung inklusive der Bandbreite von Kennzahlen anhand der derzeit im System befindlichen Komponenten ermittelt werden kann. Ein starres Kennzahlensystem ist meist nicht in der Lage, mit stark schwankenden Komponentendimensionierungen fertig zu werden, da die Effekte zum Teil nicht lineare Auswirkungen haben.
Dynamik im System
Die Dynamik im System kann durch das Hinzukommen und/oder Wegfallen von Kanten erreicht werden. Aber auch die Veränderung der zur Verfügung stehenden Speicherkapazitäten oder Energiemengen an den jeweiligen Knoten muss von dem dynamischen Kannzahlensystem bewältigt werden.
Verwandte Probleme
In der Softwareentwicklung gibt es viele ähnliche Probleme, für die es einen größeren Lösungsvorrat an Algorithmen gibt. Exemplarisch kann man da das Rucksack- und Behälterproblem nennen. Es gibt also viel Basisarbeit auf die zurückgegriffen werden kann.
Zusammenfassung
Wie kann man sich nun der Herausforderung zuwenden? Zusammenfassend kann man es mit den nachfolgenden Schritten beschreiben.
- Bringen Sie die Algorithmen so nah wie möglich an die aktiven Knoten
- Zerteilen Sie die Aufgaben so, dass sie auf die jeweiligen Knoten mit den passenden Eigenschaften gemapped werden können
- Lassen Sie die Daten so lange dort wo sie entstehen
- Abstrahieren Sie die Knoten durch Laufzeitcontainer mit Eigenschaften
- Vermeiden Sie sternförmige Strukturen
- Erstellen Sie dynamisch ein lokales Wertesystem und verwenden Sie kein hartes Wertesystem für Prozessorleistung, Speicher und Co.
Hiermit kann man sich einer Vielzahl bestehender Algorithmen und teilweise auch Tools bedienen. Dem ersten Experiment sollte nun nichts mehr im Wege stehen.
