Probleme mit elegantem Design umschiffen statt komplexer Lösungen — Laden von Points of Interest (POIs)

Vor einigen Monaten haben wir damit begonnen eine neue Version der smartmove App zu entwickeln. Dabei wollten wir nicht nur die User Experience an moderne Mobile-Design-Standards anpassen, sondern auch die technische Grundlage komplett überarbeiten. Im Mittelpunkt dieser neuen App befindet sich eine bildschirmfüllende Karte, die relevante Points of Interest (POIs), wie z.B. Leihwagenstellplätze, anzeigt. Bei diesen POIs handelt es sich um statische Daten, das heißt, dass sie sich nicht bewegen und an ihren Positionen fixiert sind. Trotzdem stellte sich das Laden dieser Daten als größere Schwierigkeit heraus, als ursprünglich gedacht.Gemeinsam werden wir uns in diesem Blogpost anschauen, wie wir es geschafft haben, große Performance-Probleme zu umschiffen indem sie einfache Tricks angewandt haben. Wir werden sehen, wie ohne Zuhilfenahme komplexer algorithmischer Lösungsansätze schnell und einfach eine erste Implementierung umgesetzt werden konnte.

Status Quo und Heimtückische Fallen

Wie bereits beschrieben, wollten wir in der neuen Version der smartmove App Nutzerinnen und Nutzern eine prominent platzierte Karte mit den wichtigsten POIs bieten. Die zugrundeliegenden Daten werden innerhalb der Backend-Infrastruktur aggregiert und über eine RESTful API der App zur Verfügung gestellt (einen groben Überblick über dieses Backend bieten wir am Ende des Blogposts). Wie du sehen kannst, ist also aus Sicht der neuen smartmove App die größte Herausforderung das Laden und lokale Cachen der Daten. Nichtsdestotrotz kann man dabei in gröbere Fallen tappen, wenn man nicht aufpasst. Das könnte zu Performance-Problemen oder auch komplexem und schwer wartbarem Code führen.

Erstens wäre es keine gute Idee sämtliche POIs auf einmal zu laden, da dies zu sehr langen Ladezeiten führen würde. Üblicherweise sind Benutzerinnen und Benutzer der App nur an jenen POIs interessiert, die sich im derzeitigen Sichtfeld der Karte befinden. Daher würde das Laden aller POIs, die über die gesamte Welt verteilt sind, unnötig viele Hardware-Ressourcen benötigen und blockieren. Nicht nur in der App selbst, sondern auch in der Netzwerkinfrastruktur des Backends.

Zweitens könnte das Aufteilen der POIs in kleinere Pakete, um dem vorhergehenden Problem entgegenzuwirken, zu einem weiteren Problem führen: Möglicherweise könnte nun der gleiche POI mehrmals vom Backend geladen werden; sprich, ein POI wird geladen, den die smartmove App bereit im Cache hat. Das würde implizieren, dass jedes entgegengenommene Paket mit sämtlichen POIs im Cache abgeglichen werden müsste. Ein passender Deduplikationsalgorithmus müsste entworfen werden, welcher folglich natürlich wiederum Hardwareressourcen bindet.

Letztens kann gecachte POI-Information ablaufen. Daher müsste ein Mechanismus geschaffen werden, der es ermöglicht das Alter gecachter Information festzuhalten, um diese anschließend als abgelaufen zu markieren. In Kombination mit der oben angesprochenen möglichen Duplikation könnte dies zu komplexen Cache-Management führen.

Wie oben angedeutet, wollten wir eine einfache Lösung finden, die all diese Probleme kurzerhand umgeht, anstatt sie zu lösen. Komm mit in den nächsten Abschnitt um die Lösung von Hotsource anzuschauen.

Die Lösung und wie sie funktioniert

Am Anfang des Blogposts habe ich eine einfache Lösung versprochen, mit der wir in der neuen smartmove App Geostandorte laden und die oben genannten Problemfelder umschifft: Wir spannen einen Raster über die Welt!

Bei genauerer Betrachtung des Koordinatensystems, das den Erdball überspannt, können wir feststellen, dass jede Position durch eine Kombination aus Längengrad und Breitengrad beschrieben werden kann. Wenn dieses Koordinatensystem also auf eine 2-dimensionale Ebene projiziert wird (Web Mercator Projection) erhalten wir ein Quadrat, das in einen Raster zerschnitten werden kann.

Trotz seiner Einfachheit, ist dieser Lösungsschritt der essenziellste. Beachte, dass das Raster die komplette Globusprojektion überspannt, ohne dass sich Zellen des Rasters überschneiden. Zusätzlich ist die Breite des Rasters teilbar durch die Zellenbreite (und vice versa für deren Höhen), wodurch die Zellen des Rasters, zurückprojiziert auf den Globus, entlang der Nähte perfekt aneinander anliegen. Letztendlich braucht es nur noch eines, um den Lösungsansatz von Hotsource zu verstehen: Die Zellen repräsentieren die Pakete, in die die POIs unterteilt sind. Betrachte beispielsweise die zweite Abbildung. Das strichlierte Rechteck stellt stellt das Sichtfeld der Karte dar und die hervorgehobenen Rasterzellen sind jene Zellen, die sich im Sichtfeld befinden. Nun laden wir pro hervorgehobener Rasterzelle die darin befindlichen POIs. Dadurch sind die ersten beiden erwähnten Fallen aus dem vorigen Abschnitt einfach umgangen: Es werden weder alle POIs auf einmal geladen (nur die notwendigen im sichtbaren Bereich) noch werden POIs doppelt geladen, da Rasterzellen nicht überlappen. Wird die Karte nun bewegt, müssen wir von nun an nur die POIs aus jenen Zellen laden, die in den sichtbaren Bereich wandern.

Der wichtigste Aspekt dieses Lösungskonzept ist folglich, dass das Raster absolut auf dem Erdball platziert ist und nicht relativ zum Sichtfeld.

Nun fragst du dich wahrscheinlich, wie die Rasterzellengröße festgelegt wurde. Neben den offensichtlichen Einschränkungen (die Rasterbreite muss durch die Zellenbreite teilbar sein) gibt es eine Reihe an sinnvollen Zellengrößen. Zum Beispiel sind größere Zellen hilfreich, wenn die Karte weiter hinausgezoomt ist, da dann die Anzahl der Backendrequests geringer ist) und vice versa. Da die Zoomlevel der Karte in der neuen smartmove App jedoch auf einen sinnvollen Bereich eingeschränkt wurden, haben wir uns für eine fixe Zellengröße entschieden. Nach Notwendigkeit kann hier in Zukunft eine dynamische Lösung implementiert werden.

Eine weitere Verbesserung stellt das App-seitige Cachen der geladenen POIs dar. Im Bestreben nach Einfachheit haben wir uns hier entschlossen ein einfaches 2-dimensionales Array zu nutzen, das die selben Abmessungen hat wie das Raster auf der Globusprojektion. Auch wenn es hierbei zu einem etwas höheren Speicherbedarf kommt (das gesamte Array wird direkt zu Beginn initialisiert), ermöglicht es einen sehr schnellen Cache-Zugriff. Immer, wenn wir die POIs einer Rasterzelle erhalten, legen wir sie in der zugehörigen Array-Zelle ab. Wenn die Nutzerin bzw. der Nutzer die selbe Rasterzelle später nochmal ins Sichtfeld schiebt, können wir in konstanter Zeit das Array nach gecachten Daten überprüfen. Sind sie vorhanden, können wir direkt Pins auf der Karte rendern, ansonsten laden wir die POIs einfach vom Backend. Zusätzlich kann jeder Array-Zelle einfach ein Timestamp hinzugefügt werden um anhand dem Alter der Daten den Cache invalidieren zu können. Dadurch wird der letzte Stolperstein aus dem vorigen Abschnitt umgangen.

Ein Blick hinter den Vorhang

Es wurde bereits klar, dass in der überarbeiteten smartmove App von Hotsource Geostandorte innerhalb rechteckiger Rahmen geladen werden.

Im Backend haben wir daher für unsere POIs ein MongoDB-Schema eingesetzt, indem wir Geostandorte im GeoJSON-Format speichern können. Dieses Format eignet sich zum Speichern von geographischen Datenstrukturen (GeoJSON Objects). Ein Punkt auf der Erde wird darin als GeoJSONPoint abgebildet.

Um die notwenigen geographischen Abfragen effizient beantworten zu können, nutzt MongoDB geographische Indizes. Im konkreten Fall benutzen wir einen „GEO_2DSPHERE“ Index, welcher sich gut eignet um Standorte auf einer Kugel, sprich der Erdoberfläche, abzufragen. In Spring kann dies einfach umgesetzt werden:

@GeoSpatialIndexed(type = GeoSpatialIndexType.GEO_2DSPHERE) private GeoJsonPoint location;

Beim Eintreffen einer Abfrage konstruiert das Backend eine sogenannte „MongoDB $geoWithin Aggregation Pipeline“ anhand der gewünschten Koordinaten. Diese kann dann dazu genutzt werden, alle Geostandorte innerhalb der spezifizierten Fläche (in diesem Fall ein Rechteck) abzufragen. Anhand zweier Koordinaten an den gegenüberliegenden Ecken des Rechtecks können wir wie folgt die Abfrage konstruieren:

Criteria geoCriteria = Criteria.where("address.location").within(new Box(
  new GeoJsonPoint(minLongitude, minLatitude),
  new GeoJsonPoint(maxLongitude, maxLatitude)
));

Mit diesem Ansatz haben wir einige Vorteile:

• Präzision und Flexibilität: Die „MongoDB $geoWithin Aggregation Pipeline“ erstellt präzise Abfragen anhand unserer Rasterzellen, die entsprechend die gewölbte Oberfläche der Erdkugel berücksichtigen.
• Skalierbarkeit und Geschwindigkeit: Die Kombination aus geographischen Indizes, Rasterabfragen und dynamischen Sichtfeld-Updates in der App erzielen eine effiziente Infrastruktur, die sich leicht skalieren lässt; selbst mit großen Datensätzen und gleichzeitigen Abfragen mehrerer Benutzerrinnen und Benutzer.
• Effizienz: Dadurch, dass wir für jede spezifische Nutzerin bzw. jeden spezifischen Nutzer nur jene Daten laden, die wirklich notwendig sind, reduzieren wir den Datenverbrauch und gehen sparsam mit unseren Ressourcen um.

Es zeigt sich also, dass mit geschicktem Design selbst schwierige Probleme elegant gelöst werden können. Anstatt die beschriebenen Problemfelder zu lösen, sind wir sie einfach umgangen. Dadurch bieten wir unseren Nutzerinnen und Nutzern schnellen Mehrwert.

Wir sehen uns im nächsten Blogpost!