Großer Geodatensatz (> 22 Billionen Elemente) mit schneller Abfrageleistung (<1s)

20

Ich bin dabei, ein neues System für einen großen Geodatensatz zu entwerfen, für den eine schnelle Leseabfrageleistung erforderlich ist. Daher möchte ich sehen, ob jemand der Meinung ist, dass es in der folgenden Situation möglich ist oder Erfahrung / Ratschläge zu geeigneten DBMSs, Datenstrukturen oder alternativen Methoden hat, um die erforderliche Leistung zu erzielen:

Daten werden kontinuierlich aus verarbeiteten Satellitenradardaten erzeugt, die eine globale Abdeckung haben werden. Basierend auf der Satellitenauflösung und der Landbedeckung des Globus schätze ich, dass der gesamte Datensatz Werte an 75 Milliarden diskreten Orten auf dem Globus liefert. Über die Lebensdauer eines einzelnen Satelliten werden an jedem dieser Standorte bis zu 300 Werte ausgegeben (also ein Gesamtdatensatz von> 22 Billionen Werten). Dies gilt für einen Satelliten, und es gibt bereits einen zweiten Satelliten im Orbit, wobei zwei weitere in den nächsten Jahren geplant sind. Es wird also eine Menge Daten geben! Ein einzelnes Datenelement ist sehr einfach und besteht nur aus (Längengrad, Breitengrad, Wert), aber aufgrund der Anzahl der Elemente schätze ich, dass ein einzelner Satellit bis zu 100 TB produzieren kann.

Die geschriebenen Daten sollten niemals aktualisiert werden müssen, da sie nur wachsen, wenn neue Satellitenerfassungen verarbeitet werden. Die Schreibleistung ist nicht wichtig, aber die Leseleistung ist entscheidend. Das Ziel dieses Projekts ist es, die Daten über eine einfache Oberfläche wie einen Layer über Google Maps zu visualisieren, wobei jeder Punkt einen Farbwert hat, der auf dem Durchschnitt, dem Gradienten oder einer Funktion über die Zeit basiert. (Demo am Ende des Beitrags).

Ausgehend von diesen Anforderungen muss die Datenbank skalierbar sein, und wir werden wahrscheinlich nach Cloud-Lösungen suchen. Das System muss in der Lage sein, Geodatenabfragen wie "Punkte in der Nähe (lat, lon)" und "Punkte innerhalb (box)" zu verarbeiten und eine Leseleistung von <1s für die Lokalisierung eines einzelnen Punkts sowie Polygone mit bis zu 50.000 Punkte (obwohl bis zu 200.000 Punkte vorzuziehen wären).

Bisher habe ich einen Testdatensatz von ~ 750 Millionen Datenelementen an 111 Millionen Standorten. Ich habe eine postgres / postGIS-Instanz ausprobiert, die einwandfrei funktioniert hat, aber ohne die Möglichkeit des Splitterns kann ich dies nicht, da die Daten wachsen. Ich habe auch eine mongoDB-Instanz ausprobiert, was wiederum für OK erscheint und mit Sharding kann es ausreichend sein, mit dem Datenvolumen zu skalieren. Ich habe kürzlich etwas über Elasticsearch gelernt, daher sind Kommentare dazu hilfreich, da sie für mich neu sind.

Hier ist eine kurze Animation dessen, was wir mit dem gesamten Datensatz erreichen wollen: Tileserver zur Visualisierung von 750 Millionen Datenelementen.

Dieses GIF (aus meiner Postgres-Testversion) liefert (6x3) vorberechnete Raster-Kacheln, die jeweils ~ 200.000 Punkte enthalten und jeweils ~ 17 Sekunden benötigen, um sie zu generieren. Durch Klicken auf einen Punkt wird das Diagramm erstellt, indem alle historischen Werte in <1s an der nächstgelegenen Position gezogen werden.

Entschuldigung für den langen Beitrag, alle Kommentare / Ratschläge sind willkommen.

Azwok
quelle

Antworten:

4

Sie könnten nach Ort scherben. Teilen Sie den Globus in ein Raster, und weisen Sie jedem Quadrat in diesem Raster einen Server zu. Da Sie Cloud erwähnt haben, wäre das gut für Cloud geeignet. Natürlich müssen Sie die Ergebnisse von mehreren Servern manuell zusammenführen.

Auf diese Weise können Sie jede beliebige Datenbanklösung verwenden. Es muss nicht eigenständig skalierbar sein.

Die einzelnen Quadrate enthalten unterschiedliche Datenmengen. Sie können für sie unterschiedlich große Computer verwenden (da dies eine Cloud ist) oder mehrere kleine Shards auf demselben Computer platzieren.

Dieses Sharding-Schema eignet sich hervorragend für die Art von Abfragen, die Sie ausführen, da jede Abfrage nur sehr wenige Shards berühren muss. Die Zeitverschiebung ist schlechter, da für jede Abfrage alle Zeitverschiebungen berührt werden müssen. Zufälliges Sharding hat das gleiche Problem.

Alles in allem ist dies ein einfacher Sharding-Fall, da das Abfragemuster so gut zum Sharding-Schema passt.

Eigentlich frage ich mich, ob Sie dafür überhaupt eine Datenbank brauchen. Vielleicht können Sie den Globus in 1000x1000 Kacheln oder kleiner unterteilen und für jede Kachel eine flache Datei im Blob-Speicher haben. Die Speicherung von Blobs macht 1M-Blobs überhaupt nichts aus.

Das Ausführen einer Abfrage ist mit diesem Speicherschema konzeptionell sehr einfach. Sie können die Daten auch redundant in mehreren Rasterauflösungen speichern.

usr
quelle
Die Aufteilung nach Regionen ist der Ansatz, den ich mit MongoDB verfolgt habe, und mit der rechtzeitigen Veröffentlichung von MongoDB Atlas tendiere ich derzeit in diese Richtung (unter Verwendung vorberechneter aggregierter Werte). Im Moment bin ich mir nicht sicher, wie viele Replikations- / Shard-Server ich benötigen würde. Daher kann die Kostenberechnung zu einem Problem werden. Interessant ist auch Ihr Vorschlag, BLOB-Speicher zu verwenden, und Sie sind die zweite Person, die ihn vorschlägt. Die Verwendung von BLOBs ist für mich jedoch völlig neu, daher muss ich weitere nützliche Quellen nachlesen, die Sie kennen. Danke für die Antwort.
Azwok
Die Verwendung von Blobs ist trivial. Die Komplexität ergibt sich aus der Notwendigkeit, Datenbankfunktionen wie Serialisierung, Abfragen, Transaktionen, Sicherungen, HA, DA zu implementieren. Das ist alles machbar, aber vielleicht nicht klug. Vielleicht können Sie die Blobs in einer Postgres-Tabelle speichern. Das automatisiert alles außer Serialisierung und Abfrage. Perf könnte besser sein als Blob-Speicher und vielleicht ist es sogar billiger. Blobs und VMs werden nicht nach Kosten berechnet, sie haben eine schöne Marge (Beweis: Mein lokaler Webhoster berechnet 3-5x weniger für die gleiche Rechenleistung wie die Cloud. Dies impliziert hohe Cloud-Margen).
USR
Beachten Sie, dass Sie mehrere Shards auf derselben Mongo-Instanz ausführen können. Sie können "überhärten". Auf diese Weise können Sie die Server ausgleichen.
usr
1
Ich bin mir nicht sicher, ob Sie überhaupt räumliche Merkmale benötigen. All das können Sie in der App berechnen. Sie müssen nur die Möglichkeit haben, alle Daten für ein Rechteck abzufragen. Dies kann durch manuelles Aufteilen des Globus in ein Gitter (oder Gitter mit mehreren Auflösungen) erfolgen. Ihre DB muss räumlich glaube ich nicht unterstützen.
USR
8

Wie aktuell müssen Ihre Leseanfragen sein?

Sie können die Datenbank nach Zeit partitionieren, wenn auf der Karte nur die aktuellste Messung angezeigt werden soll. Dies würde Ihre Abfragelast für die Karte verringern.

Für den Verlauf eines bestimmten Punkts können Sie einen zweiten Speicher halten, indem x und y den Verlauf anzeigen. Dies kann mit einer nächtlichen Aktualisierung / Aktualisierung erfolgen, da sich die Verlaufsdaten nicht ändern.

Dann könnten Sie Durchschnittswerte mit gröberen Auflösungen vorberechnen, um Karten mit verschiedenen Zoomstufen zu integrieren. Dies würde die Anzahl der abzurufenden Punkte für große Kartenbereiche verringern (verkleinern). Feinere Auflösungen würden für stärker gezoomte Karten verwendet, die kleinere Bereiche abfragen. Wenn Sie dies wirklich beschleunigen müssen, können Sie Kacheln als Blobs berechnen und in Ihrer Anwendung interpretieren.

Da dies eine Neuberechnung der aggregierten Informationen mit sich bringen würde, würden die Abfrageergebnisse eine gewisse Latenz aufweisen. Je nachdem, wie viel Latenz akzeptabel war, können Sie mit dieser Methode Ihre Lesevorgänge optimieren.

OK, also müssen Ihre Punkte im Laufe der Zeit gemittelt werden. Bei dieser Berechnung gehen Ihre tatsächlichen Abfragen vermutlich von 22 Billionen Elementen ziemlich weit zurück, da die Rasterwerte für die Abfrage vorberechnet werden können.

Betroffen vonTunbridgeWells
quelle
Die Leseabfragen können eine gewisse Verzögerung aufweisen (ein oder zwei Tage), sodass die Stapelverarbeitung eine gültige Option ist. An einem bestimmten Ort wird nur alle 6 Tage ein neuer Wert hinzugefügt (der nächste Satellitendurchlauf). Die Ausgabe auf der Karte ist nicht nur der neueste Wert, sondern wird basierend auf dem gesamten Verlauf der Werte an diesem Standort berechnet, z. B. dem Durchschnitt, dem Verlauf oder einer benutzerdefinierten Funktion. Für verkleinerte Ebenen arbeite ich bereits an einer Clustering- / Pyramidenstruktur, sodass ich eine Tabelle / Sammlung mit gemittelten Werten habe, sodass keine Kachel (Abfrage) mehr als 200.000 (oder 50.000) Positionselemente enthält.
Azwok
Ich denke, dass die Vorberechnung von Aggregaten der Schlüssel ist - Ihre zeitlichen Berechnungen können weiterhin stapelweise durchgeführt werden. Auf diese Weise erhalten OLAP-Systeme eine schnelle Abfrageleistung, und Sie müssen wahrscheinlich einen solchen Ansatz wählen. Besonders relevant, wenn Sie mit Daten leben können, die für Ihre Abfragen einen Tag alt sind.
ConcernedOfTunbridgeWells
Wenn Sie berechnete Durchschnittswerte abfragen, an wie vielen diskreten Orten nehmen Sie Abtastungen vor - dh wie hoch ist die Auflösung der tatsächlichen Bitmap bei der höchsten Zoomstufe?
ConcernedOfTunbridgeWells
Ich bin damit einverstanden, dass vorberechnete Aggregate sehr wahrscheinlich den Weg weisen. Die berechneten Durchschnittswerte beim höchsten Zoom werden nicht über einen Bereich gemittelt, sondern sind der Durchschnitt der Werte über die Zeit an einem Ort. Nur wenn es verkleinert wird, habe ich separate Tabellen / Sammlungen, die Bereiche mitteln, um sicherzustellen, dass keine Abfrage / Kachel zu viele Positionspunkte enthält (max. 50.000-200.000). Die maximale Auflösung einer Kachel beträgt 256x256 Pixel.
Azwok
3

Es klingt so, als gäbe es zwei Abfrageklassen: eine, um zu verstehen, welche Positionen im aktuellen Ansichtsfenster liegen, und eine, um die gewünschte Statistik für diese Punkte zu liefern. Mein Vorschlag ist, für jedes einzelne Werkzeug ein eigenes Spezialwerkzeug zu verwenden.

Ich gehe davon aus, dass sich alle Messungen auf den gleichen Satz von 75 Mrd. Punkten beziehen. Diese Lat / Longs sind daher statisch, sobald sie hergestellt sind. Sie können zu einmaligen Kosten gruppiert, aggregiert und indiziert werden. Daher würde ich vorschlagen, nach Region und Zoomstufe zu splittern. Die Größe jedes Shards hängt von der Leistung ab, die mit jeder GIS-Instanz erzielt werden kann.

Das GIS gibt eine Reihe von Punkten zurück, die an eine Zeitreihendatenbank übergeben werden. Dieser hält die Messwerte und führt Aggregate durch. KDB ist eine, die ich kenne. Es zielt auf den Wertpapierhandel ab, der weniger Schlüssel, aber mehr Datenpunkte pro Schlüssel enthält als Ihr Szenario.

Die Übertragung der Schlüsselwerte vom GIS-Server in die timeseries DB ist kostenpflichtig. Meine Hypothese ist, dass diese Kosten durch die schnellere Verarbeitung in der aufgabenspezifischen Zeitreihen-DB erstattet werden. Aus dem Wortlaut der Frage geht hervor, dass eine einzelne Instanz nicht in der Lage sein wird, alle Daten zu speichern, sodass ein gewisser serverübergreifender Datenverkehr unvermeidlich erscheint. Angesichts der relativen Geschwindigkeit der Komponenten ist es wahrscheinlich, dass das Senden eines Keysets an einen Remote-Server, auf dem die Daten zwischengespeichert sind, schneller ist als das Lesen der Daten von der lokalen Festplatte.

Wenn der Punktfindungs- und der Wertberechnungsteil lokal zueinander sein können, würde ich natürlich eine schnellere Reaktion erwarten. Mein (begrenztes) Verständnis ist, dass das Finden der N nächsten Nachbarn zu einem bestimmten Punkt eine nicht triviale Aufgabe ist. Aus diesem Grund habe ich vorgeschlagen, für die Ausführung eine bestimmte Software zu verwenden. Wenn die Punktfindung auf reduziert werden kann

where latitude between x1 and x2
and logitude between y1 and y2

dann könnte dieser Teil von der wertspeichernden Software verarbeitet und das GIS aus der Architektur entfernt werden.

Ich habe ein solches System nicht implementiert. Ich denke hier wirklich nur laut nach. Im Petabyte-Bereich gibt es keine Standardlösungen. Es gibt jedoch viele Anbieter von Satellitendaten, sodass Ihr Problem behoben werden kann. Viel Glück.

Michael Green
quelle
Einverstanden sind zwei Klassen. 1) Machen Sie sich ein Bild der einzelnen Werte von vielen Orten, 2) Holen Sie sich alle historischen Werte an einem Ort. Alle Messungen beziehen sich auf die gleichen Milliarden von Standorten. Die einzige Änderung ist die Anzahl der historischen Werte an jedem Punkt. Die Aufteilung nach Regionen ist der Ansatz, den ich aus den von Ihnen genannten Gründen verfolgen möchte. Ich hatte nicht daran gedacht, die zurückgegebenen Werte in einen separaten Zeitreihen-DB zu übertragen. Ich hätte gedacht, die Auswahl und Übertragung in eine Zeitreihendatenbank würde zu viel Zeit hinzufügen, um dies zu einer praktikablen Option zu machen, es sei denn, ich habe Ihren Vorschlag missverstanden.
Azwok