GAE-GEO-DB ~ Umkreissuche mit Google App Engine DataStore

Datenmodell für eine Umkreissuche mit der Google App Engine: Ziel ist ein skalierbares Design für den DataStore, um weltweit beliebig viele Geo-Positionen zu speichern.

In einem DataStore-Item der AppEngine werden mehrere Geo-Positionen gespeichert, um die Suche mit möglichst wenigen Read-Operationen zu realisieren. Die Suche erfolgt nicht per DQL, sondern die Daten werden so organisiert, dass die passenden Items zu einer Geo-Lokation gezielt per Key gelesen werden können. Items können zudem nach dem Lesen temporär im MemCache zwischengespeichert werden, um bei erneuten Suchanfragen ohne Read-Operationen auszukommen. Werden je Geo-Position z.B. 250 Byte verwendet, dann können bis zu 4.000 Lokationen in einem 1 Megabyte DataStore-Item gespeichert werden.

Die Erdoberfläche wird dazu in GSP-Quadranten unterteilt und diese werden jeweils auf unterschiedliche Items verteilt. Da 70% der Erde mit Wasser bedeckt sind und wahrscheinlich weltweit nicht zu jeder Region GPS-Koordinaten erfasst werden, kann initial ein sehr grobes Raster für die GPS-Quadranten genutzt werden. Sobald in einem Quadrant mehr als 1 MB gespeichert werden soll, wird dieser dann in kleinere Quadranten unterteilt und die Daten darauf verteilt. Mit zunehmender Datenmenge wächst die Anzahl der DataStore-Items linear und die Quadranten werden immer kleiner.

In einem zentralen Index-Item wird die Auflösung für die gesamte Erdoberfläche verwaltet. Die Anzahl der DataStore-Items skaliert so mit der Anzahl an erfassten Geo-Positionen. Werden keine Geo-Daten in einem GPS-Quadrant erfasst, so wird auch kein DataStore-Item gespeichert. Es wird nur die minimale Anzahl an Items erzeugt und diese werden maximal befüllt, um mit möglichst wenig Read-Operationen die maximale Datenmenge einzulesen.

Quadranten-Raster:
* L1: 8x ~ 890,4 km (8`)
* L2: 4x ~ 445,2 km (4`)
* L3: 2x ~ 222,6 km (2`)
* L4: 1x ~ 111,3 km (1`)
* L5: 1/2x ~ 55,67 km (0,5`)
* L6: 1/4x ~ 27,83 km (0,25`)
* L7: 1/8x ~ 13,91 km (0,125`)
* L8: 1/16x ~ 6,96 km (0,0625`)

Mit diesem Modell können sehr feingranular Geo-Daten gespeichert und gesucht werden sowie die Anzahl der Items / Read-Operationen minimiert werden. Nur 0,074% der Erdoberfläche betreffen Deutschland, d.h. man benötigt nur 25.000 Items für ein 7×7 km Raster mit bis zu 100 Mio GPS-Positionen. In der Praxis werden nur für Ballungsgebiete feine Raster und damit für Deutschland deutlich weniger Items benötigt. Für L1 sind weltweit 2.025 Data-Items (360:8=>45*45) nötig und mit L8 sind bis zu 33.177.600 Data-Items (360*16=> 5.760×5.760) möglich, was einer Datenmenge von bis 33,2 Terabyte entsprechen würde. Sollte L8 nicht ausreichen, dann können zu einem Key sequenziell beliebig viele Erweiterungs-Items gespeichert werden. Mit diesem Modell könnte z.B. jedes Haus der Welt erfasst werden.

Kern ist das Index-Item, welches in 1 MB passt und aus zwei Flag-Rastern (45×45 und 720×720) besteht. In den Flags wird die Auflösung der Quadrante gespeichert. Zusätzlich wird für den Batch die Synchronisation zu jedem Quadrant gekennzeichnet, wenn es Änderungen (neue, geänderte, gelöschte Geo-Positionen) gibt. Für L3..L4 werden im Fein-Raster die genutzen Quadranten mit „9“ markiert. Für L6..L8 werden immer physische Items angelegt, auch wenn diese leer sind oder es wird mit einem Index-Item zu diesem L2-Quadrant erzeugt.

Grob-Raster 45×45 = 2.025 Byte
0: keine Geo-Daten
1: L1 = 890 km Quadrant
2: L2 = 445 km Quadranten
3: L3 = 222 km Quadranten
4: L4 = 111 km Quadranten
5: L1 mit Änderung
6: L2 mit Änderung
7: L3 mit Änderung
8: L4 mit Änderung
9: L5..L8 < 111 km Quadranten

Fein-Raster 720×720 = 518.400 Byte
0: keine Geo-Daten
1: L5 = 55 km Quadranten
2: L6 = 27 km Quadranten
3: L7 = 14 km Quadranten
4: L8 = 7 km Quadranten
5: L5 mit Änderung
6: L6 mit Änderung
7: L7 mit Änderung
8: L8 mit Änderung
9: L1..L4 belegt

L2-Raster 512×512 = 262.144 Byte
0: keine Geo-Daten
2: L2
3: L3
4: L4
5: L5
6: L6
7: L7
8: L8

Jede Geo-Position wird für L8 kodiert und erhält innerhalb des zugehörigen L8-Quadranten eine laufende Nummer von 0000..9999 bzw. 0000..zzzz (bis 14 Mio). Der Code einer Geo-Position passt zum DataStore-Key des Item, in dem die Daten physisch gespeichert werden. Aus logischer Sicht gibt es nur das kleinste L8-Raster, auch wenn der Datensatz physisch in einem L1..L7-Item gespeichert wird.

Kodierung der Geo-Position:
Key1: 000..720
Key1.LAT: ceil((LAT+180)*2)
Key1.LON: ceil((LON+90)*4)
Key2: 0..8
Key2.LAT: ceil (LAT * 1000 mod 1000) / 1000 / 0,125)
Key2.LON: ceil (LON * 1000 mod 1000) / 1000 / 0,125)
0: 0,000
1: 0,125
2: 0,250
3: 0,375
4: 0,500
5: 0,625
6: 0,750
7: 0,875

Aufbau der DataStore-Keys:
L1: A.00.00 – A.45.45
L2: B.00.00 – B.90.90
L3: C.000.000 – C.180.180
L4: D.000.000 – D.360.360
L5: E.000.000 – E.720.720
L6: F.000.000.0.0 – F.720.720.2.2
L7: G.000.000.0.0 – G.720.720.4.4
L8: G.000.000.0.0 – G.720.720.8.8

Sobald ein Item von einem groberen Raster keinen Platz für zusätzliche Daten mehr hat, werden die Daten auf ein kleineres Raster verteilt und das ursprüngliche Item zum groberen Raster wird gelöscht. Es werden dabei nur Items gespeichert, zu den es auch GPS-Daten existieren.

Es sind diverse Anwendungen denkbar, in die eine Geo-Suche implementiert werden kann. Für Googles AppEngine hat das Datenmodell entscheidenden Einfluss auf die Kosten und Performance, aber man wird dadurch quasi zu einer beliebig skalierbaren Lösung gezwungen.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: