Scannen einer Milliarde Zeilen in einer ultraschnellen Datenbank

9

Hintergrund

Eine lokale Datenbank enthält fast 1,3 Milliarden eindeutige Zeilen. Jede Zeile ist indirekt einem bestimmten Breiten- und Längengrad (Ort) zugeordnet. Jede Zeile hat einen Datumsstempel.

Anwendungsfall

Das Problem ist wie folgt:

  1. Der Benutzer legt ein Start- / Enddatum und einen Wertebereich fest (z. B. 100 bis 105).
  2. Das System sammelt alle Zeilen, die dem angegebenen Datum entsprechen, gruppiert nach Standort.
  3. Das System ermittelt die Orte, an denen während dieser Daten eine statistische Wahrscheinlichkeit besteht, in den angegebenen Wertebereich zu fallen.
  4. Das System zeigt dem Benutzer alle übereinstimmenden Positionen an.

Dies ist ein Problem der Geschwindigkeit und des Maßstabs.

Frage

Was ist die kostengünstigste Lösungsarchitektur, die Sie sich vorstellen können, mit der ein solches System in weniger als fünf Sekunden Ergebnisse für Benutzer abrufen kann?

Aktuelles System

Die Umgebung ist derzeit:

  • PostgreSQL 8.4 (Upgrade ist möglich; Datenbankwechsel ist keine Option)
  • R und PL / R.
  • XFS
  • WD VelociRaptor
  • 8 GB RAM (Corsair G.Skill; 1,3 GHz)
  • Quad Core GenuineIntel 7 (2,8 GHz)
  • Ubuntu 10.10

Hardware-Upgrades sind akzeptabel.

Update - Datenbankstruktur

Die Milliarden von Zeilen befinden sich in einer Tabelle, die ähnelt:

id | taken | location_id | category | value1 | value2 | value3
  • id - Primärschlüssel
  • genommen - Datum, das der Zeile zugewiesen wurde
  • location_id - Verweis auf den Breiten- / Längengrad
  • Kategorie - Eine Beschreibung der Daten
  • value1 .. 3 - Die anderen Werte, die der Benutzer abfragen kann

Die takenSpalte enthält in der Regel aufeinanderfolgende Daten pro location_idTag. Manchmal enthält jeder Standort Daten von 1800 bis 2010 (etwa 77.000 Daten, von denen viele dupliziert wurden, da jeder Standort Daten im gleichen Datumsbereich enthält).

Es gibt sieben Kategorien und die Tabellen sind bereits nach Kategorien unterteilt (unter Verwendung von untergeordneten Tabellen). Jede Kategorie enthält ~ 190 Millionen Zeilen. In naher Zukunft wird die Anzahl der Zeilen pro Kategorie eine Milliarde überschreiten.

Es gibt ungefähr 20.000 Standorte und 70.000 Städte. Die Standorte sind nach Längen- und Breitengrad mit der Stadt korreliert. Das Zuweisen jedes Standorts zu einer bestimmten Stadt bedeutet, die Stadtgrenzen zu finden, was keine triviale Aufgabe ist.

Ideen

Einige Ideen, die ich habe, sind:

  • Suchen Sie einen Cloud-Dienst zum Hosten der Datenbank.
  • Erstellen Sie einen SSD-Raid-Streifen (großartiges Video).
  • Erstellen Sie eine Tabelle, in der alle Standorte nach Städten zusammengefasst sind (Vorberechnung).

Vielen Dank!

architecture database geospatial Dave Jarvis
quelle
10
"Das Wechseln von Datenbanken ist keine Option", die die meisten Lösungen so gut wie eliminiert. Viel Glück!
Steven A. Lowe
1
Es ist schwer zu sagen, ohne weitere Informationen darüber, was genau Sie mit diesen Aufzeichnungen tun. Suchen Sie auch nach dem 5-Sekunden-Worst-Case (was wahrscheinlich bedeutet, dass jeder untersuchte Datensatz und keine Positionen übereinstimmen)?
Guy Sirton
2
@ Dave: Wie viel Zeit braucht das aktuelle System? Verwendet das aktuelle System PostGIS ? Ist location_idein geographyoder geometryoder bezieht sich auf eine zweite Tabelle? Ist die location_idSpalte indiziert?
Rwong
1
@ Thorbjørn & @Darknight - Im Ideenbereich liste ich Vorberechnungen auf, die die Daten auf einen Wert pro Stadt und Tag (pro Kategorie) reduzieren würden. Die Berechnung könnte sich jährlich oder sogar monatlich wiederholen, nehme ich an. Dies war mein Plan, wenn es keine anderen Möglichkeiten gab (die Berechnungen werden wahrscheinlich Wochen dauern).
Dave Jarvis
1
@ Dave, viele Möglichkeiten, aber die Frage ist, was für Sie relevant ist. Haben Sie untersucht, wo die aktuellen Engpässe noch liegen?

Antworten:

12

Das Wichtigste ist, absolut sicher zu sein, wo der Engpass jetzt für eine bestimmte Anzahl repräsentativer Anforderungen liegt, da Sie nicht zwischen Datenbanken wechseln können.

Wenn Sie vollständige Tabellenscans durchführen, benötigen Sie entsprechende Indizes.

Wenn Sie auf E / A warten, benötigen Sie mehr Speicher für das Caching (Jeff Atwood erwähnte kürzlich, dass 24-Gbit-Systeme auf Desktop-Systemen erreichbar waren).

Wenn Sie auf CPU warten, müssen Sie sehen, ob Ihre Berechnungen optimiert werden können.

Dies erfordert einen spitzen DBA-Hut und einen Betriebssystem-Hut, aber es lohnt sich, um sicherzustellen, dass Sie den richtigen Baum bellen.


quelle
Wie auch immer Sie es schneiden und würfeln - selbst wenn jede Zeile nur 100 Bytes benötigt, sind 1,3 Milliarden Zeilen = 121 GB. Mit all Ihren Indizes usw. bin ich sicher, dass dies viel mehr sein wird. Auf einer einzelnen Box werden Sie langsam sein, es sei denn, Sie haben ernsthafte Hardware um SSD + Tonnen RAM. Billiger ist es, über Boxen zu skalieren.
Subu Sankara Subramanian
4
@Subu, willst du verteilt gehen? Jetzt haben Sie zwei Probleme ...
Heh - dem stimme ich zu :) Aber es ist billiger!
Subu Sankara Subramanian
@ Thorbjørn: Danke für deine Zeit und all deine Hilfe. Ich denke, ich werde den Datensatz auf 25 Millionen Zeilen pro Kategorie reduzieren und dann am Datum Indizes anwenden. Das sollte den Scan auf ~ 70000 Zeilen (pro Tag, mit einer Begrenzung von zwei Wochen für den Bereich) reduzieren, was ziemlich bissig sein sollte.
Dave Jarvis
@ Dave, du musst immer noch wissen, wo deine Engpässe sind. Lerne es, während du es nicht musst .
4

Wie wäre es, wenn Sie die Tabelle basierend auf dem Datumsstempel in mehrere Teile auf verschiedenen Hosts aufteilen? Dies ist horizontal skalierbar. Solange Sie über genügend Boxen verfügen, können Sie eine kleine Aggregations-Engine über diese Setups schreiben.

Wenn Sie feststellen, dass sich der Datumsstempel zu stark ändert, können Sie anhand der Positionen partitionieren - wiederum horizontal skalierbar. (Hoffentlich fügen sie nicht mehr viele Breiten- / Längengrade hinzu!)

Subu Sankara Subramanian
quelle
Danke für die Ideen. Es gibt möglicherweise 77.066 Daten, und in Zukunft werden neue Daten hinzugefügt. Ich habe eine einzige Maschine. Es gibt 20.000 Standorte, aber eine Aufteilung nach Standorten würde nicht helfen, da die zu analysierenden Daten alle Standorte umfassen.
Dave Jarvis
und wie unterscheidet sich die Verwendung von Cloud von der obigen Lösung?
Chani
Daran habe ich auch gedacht. Eine Art horizontale Partition, damit die Suche über alle Partitionen hinweg parallel erfolgen kann.
Davidk01
Die Aufteilung am Tag wäre wahrscheinlich am hilfreichsten, was zu 2562 separaten Tabellen (366 Tage x 7 Kategorien) führen würde.
Dave Jarvis
4

Im schlimmsten Fall deckt der Datumsbereich alle Daten in Ihrer Datenbank ab.

Sie möchten 1,3 Milliarden Datensätze lesen und in weniger als 5 Sekunden eine Analyse für jeden Datensatz im Vergleich zu den eingegebenen Werten auf einer physischen Maschine durchführen. Das Ergebnis können alle oder keine Standorte sein - Sie wissen nichts im Voraus.

Angesichts dieser Parameter würde ich sagen, wahrscheinlich unmöglich.

Schauen Sie sich nur Ihre Festplatte an: Die maximale Dauerfrequenz beträgt weniger als 150 MB / s. Das Lesen von 1,3 Milliarden Datensätzen dauert mehr als 5 Sekunden. In Bezug auf die CPU können Sie in 5 Sekunden keine statistischen Analysen für 1,3 Milliarden Datensätze durchführen.

Ihre einzige Hoffnung (tm :-)) findet eine Art Lookup - Funktion basierend auf den Werten vom Benutzer eingegeben , die die (von einigen Größenordnungen) suchen nach unten werden verengen. Sie können diese Suchfunktion offline berechnen. Ohne mehr über die genauen Übereinstimmungskriterien zu wissen, kann Ihnen wohl niemand sagen, wie das geht, aber ein Beispiel wäre, den Wertebereich in ein diskretes Intervall zu unterteilen und eine Suche zu erstellen, die Ihnen alle Datensätze in diesem Intervall liefert. Solange das Intervall klein genug ist, können Sie echte Arbeit darin leisten, z. B. Einträge entfernen, die nicht mit dem vom Benutzer eingegebenen Wert übereinstimmen. Grundsätzlich Raum gegen Zeit tauschen.

Es kann möglich sein, alle Datensätze (oder zumindest den wichtigen Teil) im Speicher zu behalten. Wahrscheinlich nicht in 8 GB. Dadurch wird zumindest der Festplatten-E / A-Teil eliminiert, obwohl selbst die Speicherbandbreite möglicherweise nicht ausreicht, um alles in 5 Sekunden zu durchsuchen. In jedem Fall ist dies eine andere Technik, um diese Art von Anwendungen zu beschleunigen (in Kombination mit meinem vorherigen Vorschlag).

Sie erwähnen die Verwendung eines Cloud-Dienstes. Ja, wenn Sie für genügend CPU- und E / A-Muskeln bezahlen und Ihre Datenbank auf viele Server verteilen, können Sie sie brutal erzwingen / teilen und erobern.

Guy Sirton
quelle
Danke für die Antwort. Hardware-Upgrades sind gemäß den von mir aufgelisteten Ideen eine Überlegung. Eine Lösung unter 750 USD wäre ideal.
Dave Jarvis
2

Ich bin der zweite Kommentar von rwong zu der Frage: PostgreSQL bietet geeignete Indextypen und -tools (GIST-Indizes, GIN-Indizes, Postgis, geometrische Typen) so an, dass Geodaten und datetime-bezogene Daten entlang dieser Kriterien ohne große Probleme durchsucht werden können.

Wenn Ihre Abfragen zu diesen Kriterien Sekunden dauern, bedeutet dies wahrscheinlich, dass keine solchen Indizes verwendet werden. Können Sie bestätigen, dass Sie diese gegebenenfalls untersucht haben?

Denis de Bernardy
quelle
Vielen Dank. Die sieben untergeordneten Tabellen werden mithilfe eines Btree nach Speicherort, Datum und Kategorie gruppiert. Ich habe letztes Jahr nach GIN-Indizes gesucht und sie haben (oder wollten) nicht geholfen, wie ich mich erinnere.
Dave Jarvis
2
Die Indizierung des Speicherorts basierend auf B-Tree ist angesichts der Art der Suche, die Sie untersuchen, nicht das geringste nützlich. Sie benötigen einen invertierten Index, der mit den benötigten Operatoren zusammenarbeitet, was im Fall von Postgis normalerweise GIST bedeutet. Vielleicht möchten Sie einige der langsamen Abfragen hervorheben ...
Denis de Bernardy
1

Wenn Sie PostgreSQL- und Breiten- / Längengraddaten verwenden, sollten Sie auf jeden Fall auch PostGIS verwenden. Auf diese Weise können Sie Ihrer Datenbank einen räumlichen GiST-Index hinzufügen, um die Arbeit zu beschleunigen.

Ich habe eine solche Tabelle (mit 350.000 Zeilen) mit einer Konfiguration, die viel kleiner ist als Ihre (2 Core und kaum 2 GB RAM), aber die Suche dauert weniger als eine Sekunde.

Wildpeaks
quelle
0

Vielleicht könnten Sie ein relationales Modell brechen, wie es Essbase mit seiner OLAP-Architektur getan hat: Essbase Wikipedia

Was ich meine, ist eine Tabelle pro Stadt zu erstellen, was zu mehr als 1000 Tabellen führt. Nicht ein Tisch, wie Sie vorgeschlagen haben, sondern viele. Indizieren Sie jede Tabelle nach Datum und Ort. Viele Tabellen, viele Indizes -> schneller.

mihaela
quelle
Danke für den Hinweis. Es gibt über 70.000 Städte und viele verschiedene Breiten- / Längengrade liegen in einem bestimmten Stadtgebiet.
Dave Jarvis
@ Dave: Kannst du ein Voronoi-Diagramm für Städte erstellen und Lat / Lon-Werte in Tessellationen klassifizieren? (Wenn es sich zufällig anhört, lassen Sie es sein.) Während der Suche suchen Sie dann nach allen Städten, deren Tessellation die Lat / Lon-Bereiche der Abfrage berührt. Wenn die Voronoi-Tessellation zu langsam ist, sollten quadratische Kästchen (z. B. 5 ° Lat x 5 ° Lon) einen Versuch wert sein.
Rwong
0

Sind Sie bei Ihrer Idee, einen Cloud-Dienst zum Hosten der Datenbank zu finden, bereits auf SimpleGeo gestoßen ? Sie haben nur das Menüband eines Speicherdienstes durchtrennt, der anscheinend "speziell darauf abgestimmt ist, Standortdaten wirklich, wirklich schnell zu speichern und abzufragen" - obwohl die Kosten für das Speichern und Abfragen von mehr als einer Milliarde Zeilen diesen Ansatz möglicherweise nicht durchführbar machen.

IanI
quelle
-2

Sie erwarten, dass ein Fahrrad auf der Autobahn fährt. Derzeit suchen Sie nach einer Lösung, um nur dieses Problem anzugehen. Sie sehen das Problem nicht voraus. Was ist, wenn Sie 2 Milliarden Datensätze haben? Skalierbarkeit muss angesprochen werden. Antwort ist einfach Objektdatenbanken verwenden. zB Intersystems Cache

und glauben Sie mir, ich bin nicht von Intersystemen ;-)

anerjan
quelle