Schnellste Möglichkeit zum Abrufen/Speichern von Millionen von kleinen binären Objekten

Question

Ich bin auf der Suche nach einer schnellen (wie in großen Leistung, nicht schnelle Lösung) Lösung für das Andauern und Abrufen Dutzende von Millionen kleiner (etwa 1k) binärer Objekte. Jedes Objekt sollte eine eindeutige ID zum Abrufen haben (vorzugsweise eine GUID oder SHA). Zusätzliche Anforderungen sind, dass es von .NET verwendet werden kann und keine zusätzliche Softwareinstallation erforderlich sein sollte.

Derzeit verwende ich eine SQLite-Datenbank mit einer einzigen Tabelle für diesen Job, aber ich möchte den Aufwand für die Verarbeitung einfacher SQL-Anweisungen wie SELECT Daten aus dem Speicher WHERE ID = ID loswerden.

Ich habe auch direkte Dateisystempersistenz unter NTFS getestet, aber die Leistung verschlechtert sich sehr schnell, sobald es eine halbe Millionen Objekte erreicht.

P.S. Übrigens, Objekte müssen nie gelöscht werden, und die Einfügungsrate ist sehr, sehr niedrig. Jedes Mal, wenn sich ein Objekt ändert, wird eine neue Version gespeichert und die vorherige Version bleibt erhalten. Dies ist eigentlich eine Voraussetzung, um Zeitreisen zu unterstützen.

Nur einige zusätzliche Informationen zu diesem Thema ergänzt: Large Object Speicherung in einer Datenbank oder ein Dateisystem http://arxiv.org/abs/cs.DB/0701168

Answer 1

Sie können möglicherweise die Leistungsprobleme von NTFS verringern, indem Sie die GUID-Kennung des Objekts in Teile zerlegen und sie als Verzeichnisnamen verwenden. Auf diese Weise enthält jedes Verzeichnis nur eine begrenzte Anzahl von Unterverzeichnissen oder Dateien.

z.B. Wenn der Bezeichner aaaa-bb-cc-ddddeeee lautet, würde der Pfad zum Element c:\store\aaaa\bbcc\dddd\eeee.dat lauten und jedes Verzeichnis auf nicht mehr als 64.000 Unterelemente beschränken.

Answer 2

ich denke, die Datenbank-Abfrage ist die beste Wahl:

Um Blob oder nicht.

Die gesamte Struktur einer Datenbank ist genau auf diese Art von Fall abgestimmt, und das Parsen und Optimieren der einfachen Abfrage ist ziemlich unbedeutend.

Möglicherweise können Sie ein Schema erstellen, in dem Sie alle Objekte in einem großen Blob direkt im Dateisystem speichern und dann eine Speicherabbilddateiansicht öffnen und die Objekt-IDs mit einem Offset in den Blob indexieren , aber ich bezweifle, dass Sie viel mehr Leistung als die DB sehen würden, da dies im Wesentlichen ist, was es tut.

Answer 3

Speichern Sie einen separaten Index (eine andere Datei) von [Guid -> Dateinummer + Offset in Datei]. Verwenden Sie eine binäre Suche zum Abrufen und verschieben Sie sie in die Datei n + 1, sobald Datei n eine bestimmte Größe erreicht. Jede Zeile in der Indexdatei ist nur 24 Bytes (feste Größe: GUID + Dateinummer + Offset, geteilte Dateien bei 4 GB) und Sortierung ist schnell (Insertion Sortierung mit einer niedrigen Rate.)

Edit: Sie haben sehr einfache Anforderungen, die einfach zu optimieren sind. Dieses sorgfältig konstruierte System sollte die Datenbank übertreffen, insbesondere wenn Sie bei Blocklesungen der Daten und asynchroner E/A vorsichtig sind. Die Datenbankabfragen haben immer den Overhead der Analyse.

Edit 2: Wenn Sie es auch sicher brauchen (immer eine gute Idee), werfen Sie hier einen Blick auf eine Beschreibung, wie das Konzept file system transactions Ihnen kugelsichere Dinge helfen kann.

Answer 4

Sie müssen eine prepare Funktion nur einmal pro Anweisung aufrufen, wobei der Parameter z.von ? (so SELECT data FROM store WHERE id=? ist die Aussage, die Sie vorbereiten würden); dann was du "millionenfach" machst ist nur bind der Parameter in die vorbereitete Anweisung und sqlite_step aufrufen - das sind schnelle Operationen. Benchmarking lohnt sich, wenn blob open vielleicht nicht noch schneller ist. IOW, ich empfehle, mit SQLite zu bleiben und in seine Low-Level-Schnittstelle (aus verwaltetem C++, wenn Sie müssen) für maximale Leistung zu graben - es ist wirklich eine erstaunliche kleine Engine, und es hat mich oft positiv überrascht mit seiner Leistung!

Answer 5

Haben Sie in Erwägung gezogen, Objektdatenbank wie db4o zu testen? Es kann jedes CLR-Objekt beibehalten und mit der Abfragesprache schnell darauf zugreifen (unterstützt LINQ!). Ich hatte nicht Millionen von Objekten, aber mit einigen Tausend Zugriffen war ziemlich schnell, kein größerer Unterschied als eine ähnliche SQL-Abfrage mit indexiertem ID-Feld.

Answer 6

Wie über eine Binärdatei mit Blöcken fester Größe von etwa 2 K ist, wobei die ersten 4 Bytes die Länge des Objektes ...

Lage der i an i * 2048 Bytes ist, lesen dann 2048 Bytes für das Objekt, wobei die Länge des tatsächlichen Objekts aus den ersten 4 Bytes ermittelt wird (ohne Vorzeichen).

Answer 7

Ich mag Earwickers Lösung. Die Art, wie ich damit umgegangen bin, ist sehr ähnlich.

Was ich dies tat:

Lassen Sie uns sagen, dass Ihre guid ist 3F2504E0-4F89-11D3-9A0C-0305E82C3301.

Hash die Guid bis zu einem Drei-Buchstaben-Hash. aaa-zzz.

Angenommen, Ihre Guid Hashes auf "xap". \ Store \ x \ xa \ xap \ 3F2504E04F8911D39A0C0305E82C3301.dat

Natürlich gibt es viele Varianten dieser Strategie:

Ihre Informationen werden in der Datei c gefunden werden. Zum Beispiel könnte xap eine Datei mit allen angehängten binären Objekten sein, mit einem Header oder einer externen Datei, die die Guides und Offsets in der Datei hat.

Answer 8

Sie können prüfen, ob HDF5 Strukturen geeignet sind für Ihre Aufgaben

• .Net interface

Answer 9

Ich neige dazu, w/Alex zustimmen, wenn Sie Ihre eigene Lösung schreiben Sie Sachen sind neu zu erfinden, die bereits wahrscheinlich ist, in SQLite, aber wenn Sie müssen ...

Sie können wahrscheinlich ein BTree hier arbeiten. Es ist das Arbeitspferd jeder Datenbank und Ihr Problemraum ist nicht so schlecht. 10 Millionen von 1k-Objekten sind immer noch nur 10er Milliarden von Bytes, so dass die Datei vom Betriebssystem verwaltet werden kann und es gibt viele BTree-Beispiele, die es zu testen gibt.

Verglichen mit der Verwendung der Dateisystemverzeichnisstruktur, um im Wesentlichen ein BTree-Analog zu erzeugen, das ein reelles BTree verwendet, wird viel schneller sein.

Eine andere Lösung, die von Interesse sein könnte, ist Mogilfs, die ein verteiltes redundantes Dateisystem ist.

Answer 10

Ich weiß nicht, ob SQLite Index unterstützt oder nicht, aber wenn dies der Fall ist, können Sie die Dinge beschleunigen, indem Sie einen Index über das ID-Feld erstellen.

Wenn nicht, dann ist Ihre beste Option B + Bäume. Danke