Optimale Speicherung von Datenstruktur für schnelles Nachschlagen und Ausdauer

Question

Szenario

Ich habe die folgenden Methoden:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

Zunächst denke ich Speicher auf der Form:

itemId -> userId, userId, userId

und

userId -> itemId, itemId, itemId

AddItemSecurity basiert darauf, wie ich Daten von einem Dritten API bekommen, GetValidItemIds ist, wie ich es zur Laufzeit verwendet werden soll.

Es gibt potenziell 2000 Benutzer und 10 Millionen Objekte. Artikel-IDs sind auf dem Formular. 2007123456, 2010001234 (10 Stellen, wo das Jahr ersten vier repräsentieren)

AddItemSecurity muss nicht super schnell durchführen, aber GetValidIds muss Subsekunden sein. Auch wenn es auf einem vorhandenen itemId ein Update I vorgesehen ist, dass itemId für Benutzer nicht mehr in der Liste zu entfernen.

Ich versuche, darüber nachzudenken, wie ich dies in optimaler Weise gespeichert werden soll. Vorzugsweise auf der Festplatte (mit Caching), aber ich mag den Code wartbar und sauber.

Wenn die Element-IDs bei 0 begonnen hatte, dachte ich über einen Byte-Array die Länge MaxItemId / 8 für jeden Benutzer erstellen, und legen Sie einen Wahr / Falsch-Bit, wenn das Element vorhanden war oder nicht. Das würde die Feldlänge auf etwas mehr als 1 MB pro Benutzer begrenzen und schnelle Lookups geben sowie eine einfache Möglichkeit, die Liste pro Benutzer zu aktualisieren. Durch die anhaltende dies als Memory Mapped Files mit dem .NET 4 Framework ich glaube, ich würde als anständig Caching erhalten gut (wenn die Maschine hat genug RAM), ohne mich Caching-Logik zu implementieren. Parsen der ID, das Jahr, Strippen, und speichern Sie ein Array pro Jahr eine Lösung sein könnte.

Die ItemId. -> Benutzer-ID [] Liste direkt auf der Festplatte serialisiert werden kann und Lese- / Schreib mit einem normalen FileStream, um die Liste und diff es bestehen bleiben, wenn es Änderungen

Jedes Mal, wenn ein neuer Benutzer hinzugefügt wird, um alle Listen müssen ebenfalls aktualisiert, aber das jede Nacht getan werden kann.

Frage

Sollte ich weiterhin diesen Ansatz auszuprobieren, oder gibt es andere Wege, die auch untersucht werden sollten? Ich denke, SQL Server nicht schnell genug durchführen werden, und es würde einen Overhead geben (zumindest, wenn es auf einem anderen Server gehostet wird), aber meine Annahmen falsch sein könnten. Jeder Gedanke oder Erkenntnisse über die Materie wird geschätzt. Und ich will versuchen, es zu lösen, ohne zu viel Hardware hinzuzufügen:)

[Update 2010-03-31]

Ich habe jetzt mit SQL Server 2008 unter den folgenden Bedingungen getestet.

• Tabelle mit zwei Spalten (Benutzer-ID, itemid) sind beide Int
• Clustered-Index auf den beiden Säulen
• hinzugefügt ~ 800,000 Artikel für 180 Benutzer - insgesamt 144 Millionen Zeilen
• Zugeteilte 4gb ram für SQL Server
• Dual Core 2.66GHz Laptop
• SSD Platte
• Verwenden Sie ein SqlDataReader alle itemid die in eine List
lesen
• Schleife über alle Benutzer

Wenn ich einen Thread es durchschnittlich auf 0,2 Sekunden laufen. Wenn ich einen zweiten Thread In geht es auf 0,4 Sekunden, die noch in Ordnung ist. Von dort über die Ergebnisse sind rückläufig. ein drittes Gewinde Hinzufügen bringt eine Menge der Abfragen bis zu 2 seonds. Ein vierte Gewinde, bis zu 4 Sekunden, ein fünfte spikes einige der Abfragen bis zu 50 Sekunden.

Die CPU ist das Dach, während dies vor sich geht, auch auf einem Thread. Mein Test-App einige aufgrund der schnellen Schleife nimmt und SQL den Rest.

Was mich zu dem Schluss führt, dass es nicht sehr gut skaliert. Zumindest nicht auf meiner getesteten Hardware. Gibt es Möglichkeiten, um die Datenbank zu optimieren, sagen Speicher eine Reihe von int der pro Benutzer statt einem Datensatz pro Element. Aber das macht es schwieriger, Gegenstände zu entfernen.

[Update 2010-03-31 # 2]

Ich habe einen schnellen Test mit den gleichen Daten als Bits im Speicher abgebildeten Dateien setzen. Es führt viel besser. Sechs Fäden ergeben Zugriffszeiten zwischen 0,02s und 0.06s. Rein gebunden Speicher. Die abgebildeten Dateien wurden von einem Prozess abgebildet und gleichzeitig von sechs anderen abgerufen. Und da die SQL-Basis 4gb nahm, nahm die Dateien auf der Festplatte 23MB.

Answer 1

Nach zahlreichen Tests landete ich mit Memory Mapped Files, so dass sie mit dem spärlichen Bit (NTFS) Markierung, unter Verwendung von Code von NTFS Sparse-Dateien mit C # .

Wikipedia hat eine Erklärung, was eine Datei mit geringer Dichte ist.

Die Vorteile einer Datei mit geringer Dichte zu verwenden, ist, dass ich etwa nicht, was meine ids reichen sind in. Wenn ich nur schreiben ids zwischen 2006000000 und 2010999999, nur die Datei 625.000 Bytes von Offset 250.750.000 in der Datei zuteilen wird . All Raum bis zu diesem Offset ist nicht zugeordneten im Dateisystem. Jede ID wird als ein Satz Bit in der Datei gespeichert. Art als Bitfeld behandelt. Und wenn die ID-Sequenz plötzlich ändert, dann wird es in einem anderen Teil der Datei zugeordnet werden.

Um die IDs abzurufen gesetzt sind, kann ich ein OS Anruf führen Sie die zugeordneten Teile der Datei mit geringer Dichte zu erhalten, und dann lese ich jedes Bit in diesen Sequenzen. Auch die Überprüfung, ob eine bestimmte ID gesetzt ist sehr schnell. Wenn es außerhalb der zugewiesenen Blöcke fällt, dann ist es nicht da ist, wenn es innerhalb fällt, es ist nur ein Byte gelesen und eine Bitmaske überprüfen, ob das richtige Bit gesetzt ist.

So für das jeweilige Szenario, in dem Sie viele IDs haben, die Sie mit möglichst viel Geschwindigkeit überprüfen wollen, ist dies die optimalste Weise, die ich bisher gefunden habe.

Und das gute daran ist, dass die Memory-Mapped-Dateien können auch mit Java gemeinsam genutzt werden (was etwas benötigt entpuppte). Java hat auch Unterstützung für Memory-Mapped-Dateien auf Windows, und die Lese- / Schreiblogik Implementierung ist ziemlich trivial.

Answer 2

Ich glaube wirklich, sollten Sie eine schöne Datenbank versuchen, bevor Sie Ihre Entscheidung treffen. So etwas wie das wird eine Herausforderung zu halten auf lange Sicht sein. Ihre Benutzer-Basis ist eigentlich recht klein. SQL Server sollte in der Lage zu handhaben, was Sie ohne Probleme benötigen.

Answer 3

2000-Benutzer ist nicht so schlecht, aber mit 10 mil verwandte Elemente sollten Sie wirklich in Betracht ziehen diese in eine Datenbank eingegeben. DBs alles tun, die Lagerung, Ausdauer, Indexierung, Caching etc., die Sie brauchen, und sie eine sehr gute Leistung.

Sie ermöglichen auch eine bessere Skalierbarkeit in die Zukunft. Wenn Sie plötzlich müssen mit zwei Millionen Nutzern und Milliarden von Einstellungen beschäftigen eine gute db statt mit einem Nicht-Thema machen Skalierung.