08.062016

Redis 3.2 Geo-API

Redis 3.2 ist ja nun schon eine Weile in freier Wildbahn. Somit haben wir Grund genug die einzelnen Features nochmal genauer unter die Lupe zu nehmen.
Wir schauen uns heute die GEO-Api an.

Zunächst einmal schauen wir uns die in Redis 3.2 verfügbaren Befehle an:

  • GEOADD
  • GEODIST
  • GEOHASH
  • GEOPOS
  • GEORADIUS
  • GEORADIUSBYMEMBER

Mehr gibt es zur Zeit nicht, allerdings lassen sich durch diese Befehle schon eine ganze Reihe einfacher Anfragen erledigen:

  • Wie weit sind 2 Orte voneinander entfernt (GEOADD beider Orte + GEODIST)
  • Welche Orte sind weniger als 10 km von meinem aktuellen Standort entfernt (GEOADD aller Orte + GEORADIUS)

Ein nettes Feature sind sicherlich auch die GEOHASHes, die Geo-Coordinaten in einem Format kodieren, welches einfach geteilt und komprimiert werden kann.

Natürlich wollen wir in unseren Post auch ein wenig zum Experimentieren anregen:

Angenommen wir wollen die Position von mehreren Usern live tracken und diese an alle Teilnehmer verteilen. Jeder User schickt (interaktiv) seine aktuellen Koordinaten. Nun lässt sich mit Hilfe eines Redis-Server sehr schnell das folgende Verhalten bauen:

Informiere einen User über die Position anderer User, sobald diese in dessen Nähe kommen:

  1. Ein neuer User erhält eine eindeutige, feste Id.
  2. Der User abonniert seinen eigenen PUBSUB-Channel (mittels seiner Id)
  3. der User sucht via GEORADIUSBYMEMBER seine aktuellen Nachbarn und merkt sich diese. Die Liste seiner alten Nachbarn wird benötigt, um mitzuteilen, dass der aktuelle User den Suchradius verlassen hat
  4. die aktuelle Position des Users wird via GEOADD in einem geoset gespeichert
  5. nach dem GEOADD sucht der User via GEORADIUSBYMEMBER seine Nachbarn nun neuen Nachbarn und merkt sich diese
  6. Nun kann der User direkt die Koordinaten der gefunden Nachbarn aktualisieren. Dieser Schritt ist nur nötig, wenn der User zum ersten Mal seinen Standort bekannt gegeben hat, damit er nicht auf Einzelupdates warten muss.
  7. Jeder Nachbar wird über einen eigenen Channel über die aktuellen Koordinaten informiert. (diese, die nur in der "alt" Menge sind werden informiert, dass der User den Bereich verlassen hat)
  8. Der User aktualisiert erneut seine Position indem er wieder bei Schritt 3) beginnt

Somit kennt jeder User zu jedem Zeitpunkt die aktuellen Koordinaten seiner Nachbarn.

Der Algorithmus hat (pro Aktualisierung) eine Gesamtkomplexität von O(N + log(M)) mit N = Anzahl der User innerhalb des eigenen Suchradius und M = Anzahl der User insgesamt. Demnach ist das vorgeschlagene Verfahren besonders effizient, wenn viele Mitglieder nicht in Reichweite der Anderen sind.

Kurzum: so einfach die Befehle auch erscheinen, durch kreativen Einsatz dieser und weiterer Redis-Commands lassen sich sehr viele Anwendungsfälle angehen, die vielleicht auf Anhieb nicht offensichtlich erscheinen.

Der Vollständigkeit halber möchte ich natürlich auch noch auf das Projekt geo-lua hinweisen. Hier entsteht Unterstützung für erweiterte Datentypen und Abfragen in Redis über eine LUA-basierte Library.
Schaut doch mal vorbei - einfache GeoJSON Datentypen sowie Polygonzüge werden bereits unterstützt.

Viel Spaß beim Ausprobieren!