Kann ich einen Schlüsselwertspeicher für Geodaten verwenden?

26

Ich habe in der Vergangenheit viele relationale Datenbanken verwendet, aber ich habe auch über alle NoSQL-Datenbanken gelesen, und die Key-Value-Speicher sehen interessant aus.

Wenn ich ein geometrisches Objekt speichere, verwende ich meistens die fünf indizierten Spalten ID, MIN_X, MAX_X, MIN_Y und MAX_Y (wobei X und Y in einer Kartenprojektion sind). Ich brauche keinen Index für meine anderen Daten.

Ich benötige die X- und Y-Werte, um Objekte an einem bestimmten Ort (Kartenrechteck) nachzuschlagen, und ich benötige den ID-Wert, wenn ich ein bestimmtes Objekt aktualisieren möchte.

Kann ich dafür einen Key-Value-Store verwenden?

database key-value-store nosql Jonas
quelle

Antworten:

18

Wir verwenden Google AppEngine, um räumliche Abfragen / Attributabfragen auszuführen. Das Hauptproblem (vom ersten Tag an) besteht darin, große Mengen von Linien / Polygonen beliebiger Größe zu indizieren. Punktdaten sind nicht allzu schwierig (siehe Geohash, Geomodell usw.), aber Sätze von zufällig gruppierten kleinen / großen Polygonen waren immer ein Problem (und sind es in einigen Fällen immer noch).

Ich habe verschiedene Versionen der räumlichen Indizierung auf GAE ausprobiert, aber die meisten sind nur Varianten von zwei unten. Keine war so schnell wie SQL-Datenbanken und alle haben Vor- und Nachteile. Die Kompromisse scheinen jedoch für die meisten internetbasierten Kartierungs-Apps angemessen zu sein. Außerdem müssen die beiden folgenden Elemente mit In-Memory-Geometrie-Culling (über JTS usw.) gekoppelt werden, um Features zu entfernen, die nicht den endgültigen Suchparametern entsprechen. und schließlich basieren sie auf GAE-spezifischen Funktionen, aber ich bin sicher, dass sie auch auf andere Architekturen angewendet werden können (oder verwenden Sie TyphoonAE, um auf einem Linux-Cluster, EC2 usw. zu laufen).

Grids - Packung alle Funktionen für einen bestimmten Bereich in einem bekannten Rasterindex. Platzieren Sie einen kleinen räumlichen Index im Raster, damit Sie schnell durch die darin enthaltenen Features navigieren können. Bei den meisten Abfragen müssen Sie nur eine Handvoll Raster ziehen, was sehr schnell ist, da Sie die genaue Namenskonvention für Raster kennen und wissen, wie sie sich auf K / V-Entitäten bezieht (erhält, nicht Abfragen).

Vorteile - ziemlich schnell, einfach zu implementieren, kein Speicherbedarf.

Cons - Vorverarbeitung erforderlich, Benutzer muss die Größe des Grids festlegen, große Geoms werden auf mehreren Grids gemeinsam genutzt, Clustering kann zu einer Überlastung der Grids führen, Serialisierungs- / Deserialisierungskosten können ein Problem darstellen (auch bei Komprimierung über Protokollpuffer)

QuadKeys - Dies ist die aktuelle Implementierung. Grundsätzlich ist es dasselbe wie bei Grids, außer dass es keine festgelegte Grid-Ebene gibt. Wenn Features hinzugefügt werden, werden sie durch das Quadkey-Raster indiziert, das ihre Grenzen vollständig enthält (oder in einigen Fällen zweigeteilt, wenn ein einzelner Quadkey nicht verwendet werden kann, denken Sie an die Datumsgrenze). Nachdem das qk gefunden wurde, wird es in eine maximale Anzahl kleinerer qk aufgeteilt, die feinere Körnungsdarstellungen des Merkmals liefern. Ein Zeiger / eine Box auf dieses Feature wird dann in einen kompakten Gridindex (eine Gruppe von Features) gepackt, der abgefragt werden kann (ein ursprüngliches Design hat die Features direkt abgefragt, dies erwies sich jedoch in Fällen, in denen die Ergebnismenge groß war, als zu langsam / CPU-intensiv).

Polyline Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_1.png Polygon-Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_2.png

Die oben verwendete Namenskonvention für Quadkeys ist allgemein bekannt und neigt, was noch wichtiger ist, dazu, die Lokalität zu bewahren (wird hier genauer beschrieben ).

Das obige Polygon sieht ungefähr so ​​aus:

Wenn die Abfragegrenzen klein genug sind, können Sie sie direkt über qk abrufen. Dies ist optimal, da es sich nur um einen einzelnen Batch-RPC-Aufruf des GAE-Datenspeichers handelt. Wenn die Grenzen groß genug sind, dass sie zu viele mögliche qks (> 1000) enthalten, können Sie alternativ mit einem Filter abfragen (z. B .: qk> = 0320101013 und qk <= 0320101013 + \ ufffd). Die Quadkey-Namenskonvention und die Art und Weise, wie GAE Zeichenfolgen indiziert, ermöglichen es der obigen Abfrage, nur die vorhandenen Gitter abzurufen, die unter diesen qk-Wert fallen.

Es gibt noch andere Vorbehalte und Leistungsprobleme, aber im Allgemeinen ist es die Fähigkeit, die Quadkeys abzufragen, die es möglich macht

Beispiele - Abfrage nach US-Landkreisen: Geojson

Vorteile - ziemlich schnell, keine Konfiguration der Rastergröße, kein Speicherbedarf, keine überfüllten Raster

Cons - Preprocessing erforderlich, in einigen Szenarien mögliches Overfetch, keine polaren Daten

Raumfüllende Kurven - Sehen Sie sich in diesem Jahr Alfred's NextGen Queries Talk bei Google I / O an. Die Einbeziehung generischer Raum / Zeit-Füllkurven zusammen mit den neuen MultiQuery-Operatoren (parallel ausgeführt) ermöglicht einige wirklich coole räumliche Abfragen. Wird es die traditionelle SQL-Leistung übertreffen? Schwer zu sagen, aber es sollte wirklich gut skalieren. Und wir nähern uns schnell einer Zukunft, in der immer verfügbare mobile Geräte aller Formen und Größen den Verkehr zu Ihrer Site / Ihrem Service dramatisch ansteigen lassen.

Schließlich stimme ich auch zu, dass Sie sich Ihre Problemdomäne genau ansehen sollten, bevor Sie sich für NoSQL statt SQL entscheiden. In unserem Fall hat mir das Preismodell von GAE sehr gut gefallen. Es gab also keine andere Wahl. Wenn Sie jedoch nicht skalieren müssen, sparen Sie sich Zeit und verwenden Sie einfach eine Standard-SQL-Datenbank

bFlood
quelle
Sie erwähnen GAE, aber welche Datenbank verwenden Sie? Es gibt mehrere: cloud.google.com/products/storage
Don McCurdy
11

Ich habe von GeoCouch gehört, einer Implementierung von CouchDB für ortsbasierte Daten. Und ich denke auch, dass MongoDB Geodatenindizierungsfunktionen hat.

JoshFinnie
quelle
Ja, und SimpleGeo baut eine räumliche Erweiterung für Cassandra auf. Ich habe nichts in Voldemort oder MemCache gehört
TheSteve0
Oh, ich liebe, was SimpleGeo tut. Ich bin eifersüchtig und würde gerne für sie arbeiten!
JoshFinnie
8

Dies ist hauptsächlich eine Frage zu Algorithmen. Ein Stapelüberlauf kann auch ein guter Ort sein, um danach zu fragen.

In jedem Fall lautet die Antwort auf Ihre direkte Frage "Ja, Sie können einen kvp-Speicher verwenden, um räumliche Daten darzustellen." Eine bessere Frage könnte jedoch lauten: "Soll ich einen kvp-Speicher zur Darstellung von Geodaten verwenden?"

Die Antwort auf diese Frage lautet (wie bei vielen anderen) "es kommt darauf an". Dies hängt von Ihrer Größenordnung, Ihrer (Transaktions-) Arbeitslast, der Art der Daten und der Computerinfrastruktur ab, über die Sie verfügen.

Ein kvp-Speicher hat einen geringen Overhead, wodurch der Durchsatz für hohe Einfüge- und Aktualisierungsparallelitäten erhöht werden kann. Es ist jedoch nicht sehr schnell, räumliche Suchen durchzuführen (alle Objekte innerhalb eines Rechtecks ​​finden). Dafür möchten Sie einen räumlichen Index, wie einen R-Baum.

Wenn Sie jedoch über ein sehr großes Datenvolumen und eine große Anzahl von Computern verfügen, kann die Verwendung eines kvp-Index einige Leistungsvorteile bieten. Die einzige Möglichkeit, wirklich sicher zu sein, besteht darin, Perfektionsmessungen unter Verwendung der tatsächlichen Daten und Zugriffsmuster durchzuführen, auf die Sie voraussichtlich stoßen werden.

Update :

Hier ist ein bisschen mehr Info. Sie können einen KVP-Speicher verwenden, um räumliche Suchen durchzuführen. Das Problem ist, dass es langsam ist. Um zu sehen, warum, überlegen Sie sich Folgendes:

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********

Wobei * und # Objekte darstellen, die in einem 11x11-Raster angeordnet sind und deren Ursprung sich in der oberen linken Ecke befindet. Stellen Sie sich eine Suche nach Objekten im Rechteck (4,4) - (7,7) vor. Das sollte alle "#" finden. Angenommen, Sie verwenden einen b + -Baum, um Ihre Indizes im KVP-Speicher darzustellen, können Sie die Ergebnisse entweder über den "X" -Index oder den "Y" -Index ermitteln. In diesem Fall spielt es keine Rolle, welche. Zur Erörterung verwende ich den x-Index. Sie würden im X-Index ein Protokoll (n) nachschlagen, um den ersten Knoten mit dem X-Wert "4" zu finden, und dann die b + -Baum-Blattknoten durchlaufen, bis Sie einen Knoten mit einem Wert größer als 7 gefunden haben Durchlaufen Sie den x-Index, um alles abzulehnen, was außerhalb des gewünschten y-Bereichs liegt.

Das ist langsam. Stellen Sie es sich in einem großen Raster mit der gleichen Dichte vor, beispielsweise 100 K * 100 K. Dort müssten Sie am Ende "300.000" Indexeinträge scannen, um nur 9 Datensätze zu finden. Wenn Sie jedoch einen richtig ausgeglichenen R-Tree verwenden, muss die Indexsuche wahrscheinlich nur etwa 90 Datensätze durchsuchen. Das ist ein großer Unterschied.

Das Problem ist jedoch, dass es teuer ist, einen R-Tree im Gleichgewicht zu halten. Deshalb lautet die Antwort "es kommt darauf an", und warum ist die Frage "sollte ich das tun" viel wichtiger als "wie mache ich das?".

Wenn Sie häufig Datensätze einfügen und entfernen und meistens nach "Objekt-ID" suchen und nicht häufig nach "räumlichen" Datensätzen suchen, erhalten Sie mit Ihrem KVP-Index eine bessere Leistung für das, wofür Sie das System tatsächlich verwenden möchten . Wenn Sie jedoch nur selten einfügen oder löschen, aber häufig räumliche Suchen durchführen, möchten Sie einen R-Tree verwenden.

Scott Wisniewski
quelle
Ich würde eine Antwort wie "Ja, das können Sie" nicht akzeptieren. weil ich wissen will WIE . Und "SOLLTE ICH ..." ist keine bessere Frage, denn wie Sie sagten "es kommt darauf an".
Jonas
1
Ich muss mit dir nicht einverstanden sein. Wenn Sie ein nützliches System erstellen oder eine nützliche Referenz im Internet für andere Benutzer hinterlassen möchten, die ähnliche Systeme erstellen, ist "sollte ich" viel wichtiger als "wie". Um hilfreich zu sein, habe ich meine Antwort jedoch bearbeitet, damit Sie einige Informationen darüber erhalten, wie.
Scott Wisniewski
@Jonas Ich glaube, die "Ratschläge", die Sie erhalten haben, beruhten auf der Art und Weise, wie Sie die Frage gestellt haben: "Aber ich habe auch über alle NoSQL-Datenbanken gelesen, und die Key-Value-Stores sehen interessant aus." Dies hat alle Merkmale einer Lösung, die nach einem Problem sucht.
JasonBirch
NoSQL löst ein Problem, aber es ist ein Problem, das praktisch niemand hat, weil sie nicht massiv genug arbeiten. Leider ist es immer schön zu denken, dass unsere eigenen Systeme im großen Stil der Dinge größer sind als sie tatsächlich sind. :)
JamesRyan
1

In den meisten Fällen erhalten Sie mehr Nutzen aus der relationalen Datenspeicherung als aus der Speicherung von Schlüssel / Wert oder Schlüssel / Wert / Typ. Bei der effizienten Abfrage und Berichterstellung für diese Art von Datenschema treten erhebliche Schwierigkeiten auf.

Mein Rat wäre, genau zu prüfen, ob Ihre Waage tatsächlich NoSQL benötigt, bevor Sie überlegen, wie Sie sie verwenden.

JasonBirch
quelle
1
Hier ist ein Beispiel für ein Problem, das Sie möglicherweise haben (und eine Lösung dafür), wenn Sie berechnen müssen, ob sich ein Punkt innerhalb oder außerhalb einer Geometrie befindet. code.google.com/p/giscloud/wiki/SerializedSpatialIndexes
Jon Bringhurst
Hey @Jon, das wäre besser als Antwort hinzuzufügen. Auf diese Weise kann es für sich allein stehen, und Sie erhalten Anerkennung dafür, wenn die Leute denken, dass es Verdienst hat!
JasonBirch