Effiziente Methoden zum Speichern von Millionen von Objekten zum Abfragen mit einer hohen Anzahl von Einfügungen pro Sekunde?

15

Dies ist im Grunde eine Protokollierungs- / Zählanwendung, die die Anzahl der Pakete und den Pakettyp usw. in einem P2P-Chat-Netzwerk zählt. Dies entspricht ungefähr 4-6 Millionen Paketen in einem Zeitraum von 5 Minuten. Und weil ich nur einen "Schnappschuss" dieser Informationen mache, entferne ich nur alle fünf Minuten Pakete, die älter als 5 Minuten sind. Die maximale Anzahl der Artikel in dieser Sammlung liegt bei 10 bis 12 Millionen.

Da ich 300 Verbindungen zu verschiedenen SuperPeers herstellen muss, ist es möglich, dass jedes Paket mindestens 300 Mal versucht, eingefügt zu werden.

Derzeit verwende ich ein Wörterbuch zum Speichern dieser Informationen. Aufgrund der großen Anzahl von Elementen, die ich speichern möchte, treten jedoch Probleme mit dem großen Objekthaufen auf, und die Speichernutzung nimmt im Laufe der Zeit kontinuierlich zu.

Dictionary<ulong, Packet>

public class Packet
{
    public ushort RequesterPort;
    public bool IsSearch;
    public string SearchText;
    public bool Flagged;
    public byte PacketType;
    public DateTime TimeStamp;
}

Ich habe versucht, mysql zu verwenden, aber es war nicht in der Lage, mit der Datenmenge Schritt zu halten, die ich einfügen musste (während ich überprüfte, ob es sich um ein Duplikat handelte), und das während der Verwendung von Transaktionen.

Ich habe mongodb ausprobiert, aber die CPU-Auslastung dafür war verrückt und hat auch nicht gehalten.

Mein Hauptproblem tritt alle 5 Minuten auf, weil ich alle Pakete entferne, die älter als 5 Minuten sind, und einen "Schnappschuss" dieser Daten mache. Da ich LINQ-Abfragen verwende, um die Anzahl der Pakete zu zählen, die einen bestimmten Pakettyp enthalten. Ich rufe auch eine distinct () - Abfrage für die Daten auf, bei der ich 4 Bytes (IP-Adresse) aus dem Schlüssel des Schlüsselpaars entferne und diese mit dem Wert für requestingport im Wert des Schlüsselpaars kombiniere, um eine eindeutige Anzahl von zu erhalten Peers von allen Paketen.

Die Anwendung verwendet derzeit etwa 1,1 GB Arbeitsspeicher, und wenn ein Snapshot aufgerufen wird, kann er die Auslastung verdoppeln.

Nun, das wäre kein Problem, wenn ich eine verrückte Menge an RAM habe, aber die VM, auf der ich das lauffähig habe, ist im Moment auf 2 GB RAM begrenzt.

Gibt es eine einfache Lösung?

Josh
quelle
Es ist ein sehr speicherintensives Szenario und obendrein verwenden Sie ein VM zum Ausführen der Anwendung, wow. Wie auch immer, haben Sie Memcached untersucht, um die Pakete zu speichern. Grundsätzlich können Sie memcached auf einem separaten Computer ausführen und die Anwendung kann auf dem virtuellen Computer selbst weiter ausgeführt werden.
Da Sie bereits sowohl MySQL als auch MongoDB ausprobiert haben, scheint es, als ob die Anforderungen Ihrer Anwendung (wenn Sie es richtig machen möchten) vorschreiben, dass Sie einfach mehr Leistung benötigen. Wenn Ihre Anwendung für Sie wichtig ist, sollten Sie den Server aufrüsten. Möglicherweise möchten Sie auch Ihren "Bereinigungs" -Code erneut aufrufen. Ich bin sicher, Sie könnten eine optimierte Methode finden, um damit umzugehen, sofern Ihre App dadurch nicht unbrauchbar wird.
Matt Beckman
4
Was sagt Ihnen Ihr Profiler?
Jasonk
Sie werden nichts schneller als lokale Haufen bekommen. Mein Vorschlag wäre, die Garbage Collection nach dem Löschen manuell aufzurufen.
Vartec
@vartec - Entgegen der landläufigen Meinung garantiert das manuelle Aufrufen des Garbage Collectors nicht die sofortige, ordnungsgemäße ... Garbage Collection. Der GC kann die Aktion nach eigenem GC-Algorithmus auf einen späteren Zeitraum verschieben. Das Aufrufen alle 5 Minuten kann die Belastung sogar erhöhen, anstatt sie zu entlasten. Nur sagen;)
Jas

Antworten:

12

Anstatt ein Wörterbuch zu haben und dieses nach zu alten Einträgen zu durchsuchen; habe 10 Wörterbücher. Erstellen Sie etwa alle 30 Sekunden ein neues "aktuelles" Wörterbuch und verwerfen Sie das älteste Wörterbuch, ohne es zu durchsuchen.

Wenn Sie als Nächstes das älteste Wörterbuch verwerfen, legen Sie alle alten Objekte für später in eine FILO-Warteschlange und ziehen Sie ein altes Objekt aus der FILO-Warteschlange, anstatt mit "new" neue Objekte zu erstellen. Verwenden Sie eine Methode, um das alte zu rekonstruieren Objekt (es sei denn, die Warteschlange alter Objekte ist leer). Dies kann viele Zuordnungen und einen hohen Speicherbereinigungsaufwand vermeiden.

Brendan
quelle
1
Partitionierung nach Zeitscheibe! Genau das, was ich vorschlagen wollte.
James Anderson
Das Problem dabei ist, dass ich alle Wörterbücher abfragen muss, die in den letzten fünf Minuten erstellt wurden. Da es 300 Verbindungen gibt, wird das gleiche Paket mindestens einmal bei jedem ankommen. Um dasselbe Paket nicht mehr als einmal zu bearbeiten, muss ich es mindestens 5 Minuten lang aufbewahren.
Josh
1
Ein Teil des Problems bei generischen Strukturen besteht darin, dass sie nicht für einen bestimmten Zweck angepasst sind. Vielleicht sollten Sie Ihrer Paketstruktur ein Feld "nextItemForHash" und ein Feld "nextItemForTimeBucket" hinzufügen, eine eigene Hash-Tabelle implementieren und die Verwendung von Dictionary beenden. Auf diese Weise können Sie schnell alle Pakete finden, die zu alt sind, und nur einmal suchen, wenn ein Paket eingefügt wurde (dh Ihren Kuchen haben und ihn auch essen). Dies würde auch bei der Speicherverwaltung helfen (da "Dictionary" keine zusätzlichen Datenstrukturen für die Wörterbuchverwaltung bereitstellt / freigibt).
Brendan
@Josh der schnellste Weg, um festzustellen, ob Sie etwas gesehen haben, ist ein Hashset . Zeitlich begrenzte Hash-Sets wären schnell und Sie müssten immer noch nicht suchen, um alte Gegenstände zu entfernen. Wenn Sie es noch nicht gesehen haben, können Sie es in Ihrem Wörterbuch aufbewahren.
Basic
3

Der erste Gedanke, der mir einfällt, ist, warum Sie 5 Minuten warten. Könnten Sie die Schnappschüsse häufiger machen und so die große Überlastung reduzieren, die Sie an der 5-Minuten-Grenze sehen?

Zweitens eignet sich LINQ hervorragend für prägnanten Code, aber in Wirklichkeit ist LINQ syntaktischer Zucker in "normalem" C #, und es gibt keine Garantie dafür, dass er den optimalsten Code generiert. Als Übung könnten Sie versuchen, die Hotspots mit LINQ neu zu schreiben. Möglicherweise verbessern Sie die Leistung nicht, aber Sie haben eine klarere Vorstellung davon, was Sie tun, und dies würde die Profilerstellung erleichtern.

Eine andere Sache zu betrachten ist Datenstrukturen. Ich weiß nicht, was Sie mit Ihren Daten machen, aber könnten Sie die von Ihnen gespeicherten Daten auf irgendeine Weise vereinfachen? Könnten Sie eine Zeichenfolge oder ein Byte-Array verwenden und dann relevante Teile aus diesen Elementen nach Bedarf extrahieren? Könnten Sie eine Struktur anstelle einer Klasse verwenden und mit stackalloc sogar etwas Böses anstellen, um Speicher zu reservieren und GC-Läufe zu vermeiden?

Steve
quelle
1
Verwenden Sie kein String / Byte-Array, sondern ein BitArray: msdn.microsoft.com/en-us/library/… , um nicht manuell Bit- Twiddle ausführen zu müssen. Ansonsten ist dies eine gute Antwort. Es gibt keine wirklich einfache Option außer besseren Algorithmen, mehr Hardware oder besserer Hardware.
Ed James
1
Das Fünf-Minuten-Problem ist auf die Tatsache zurückzuführen, dass diese 300 Verbindungen möglicherweise dasselbe Paket empfangen. Ich muss also nachverfolgen, was ich bereits erledigt habe, und 5 Minuten sind die Zeit, die Pakete benötigen, um sich vollständig auf alle Knoten in diesem bestimmten Netzwerk auszubreiten.
Josh
3

Einfacher Ansatz: Versuchen Sie es im Memcached-Modus .

  • Es ist für die Ausführung solcher Aufgaben optimiert.
  • Es kann freien Speicher für weniger ausgelastete Boxen wiederverwenden, nicht nur für Ihre dedizierte Box.
  • Es hat einen eingebauten Cache-Ablaufmechanismus, der faul ist, so dass es keine Schluckaufe gibt.

Der Nachteil ist, dass es speicherbasiert ist und keine Persistenz hat. Wenn eine Instanz inaktiv ist, sind die Daten nicht mehr vorhanden. Wenn Sie Persistenz benötigen, serialisieren Sie die Daten selbst.

Komplexerer Ansatz: Versuchen Sie es mit Redis .

  • Es ist für die Ausführung solcher Aufgaben optimiert.
  • Es hat einen eingebauten Cache-Ablaufmechanismus .
  • Es lässt sich leicht abschuppen.
  • Es hat Ausdauer.

Der Nachteil ist, dass es etwas komplexer ist.

9000
quelle
1
Memcached kann auf mehrere Maschinen aufgeteilt werden, um die verfügbare RAM-Menge zu erhöhen. Sie könnten einen zweiten Server haben, der Daten in das Dateisystem serialisiert, damit Sie nichts verlieren, wenn eine Memcache-Box ausfällt. Die Memcache-API ist sehr einfach zu verwenden und funktioniert in jeder Sprache, sodass Sie verschiedene Stapel an verschiedenen Orten verwenden können.
Michael Shopsin
1

Sie müssen nicht alle Pakete für die von Ihnen erwähnten Abfragen speichern. Zum Beispiel - Pakettypzähler:

Sie benötigen zwei Arrays:

int[] packageCounters = new int[NumberOfTotalTypes];
int[,] counterDifferencePerMinute = new int[6, NumberOfTotalTypes];

Das erste Array protokolliert, wie viele Pakete in verschiedenen Typen vorliegen. Das zweite Array protokolliert, wie viele Pakete in jeder Minute hinzugefügt wurden, sodass Sie wissen, wie viele Pakete in jedem Minutenintervall entfernt werden müssen. Ich hoffe, Sie können feststellen, dass das zweite Array als runde FIFO-Warteschlange verwendet wird.

Daher werden für jedes Paket die folgenden Vorgänge ausgeführt:

packageCounters[packageType] += 1;
counterDifferencePerMinute[current, packageType] += 1;
if (oneMinutePassed) {
  current = (current + 1) % 6;
  for (int i = 0; i < NumberOfTotalTypes; i++) {
    packageCounters[i] -= counterDifferencePerMinute[current, i];
    counterDifferencePerMinute[current, i] = 0;
}

Die Paketzähler können jederzeit sofort vom Index abgerufen werden, und wir müssen nicht alle Pakete speichern.

Kodismus
quelle
Der Hauptgrund, warum ich meine Daten speichern muss, ist die Tatsache, dass diese 300 Verbindungen möglicherweise dasselbe genaue Paket empfangen. Ich muss also jedes gesehene Paket mindestens fünf Minuten aufbewahren, um sicherzustellen, dass ich es nicht mehr als einmal bearbeite / zähle. Wofür ist der ulong für den Wörterbuchschlüssel.
Josh
1

(Ich weiß, dass dies eine alte Frage ist, aber ich bin ihr begegnet, als ich nach einer Lösung für ein ähnliches Problem gesucht habe, bei dem die App beim Durchlauf der zweiten Garbage Collection für einige Sekunden angehalten wurde, um für andere Personen in einer ähnlichen Situation aufzuzeichnen.)

Verwenden Sie eine Struktur anstelle einer Klasse für Ihre Daten (denken Sie jedoch daran, dass diese als Wert mit einer Semantik für das Weitergeben von Kopien behandelt werden). Dies nimmt eine Ebene der Suche in Anspruch, die der GC für jeden Markierungsdurchgang durchführen muss.

Verwenden Sie Arrays (wenn Sie die Größe der gespeicherten Daten kennen) oder List (wenn Sie intern Arrays verwenden). Wenn Sie wirklich den schnellen Direktzugriff benötigen, verwenden Sie ein Wörterbuch mit Array-Indizes. Dies nimmt ein paar weitere Ebenen in Anspruch (oder ein Dutzend oder mehr, wenn Sie ein SortedDictionary verwenden), damit der gc suchen muss.

Je nachdem, was Sie gerade tun, kann das Durchsuchen einer Liste von Strukturen schneller sein als das Nachschlagen des Wörterbuchs (aufgrund der Speicherlokalisierung) - Profils für Ihre bestimmte Anwendung.

Die Kombination von struct & list reduziert sowohl die Speichernutzung als auch die Größe des Garbage Collector Sweeps erheblich.

Malcolm
quelle
Ich habe kürzlich ein Experiment durchgeführt, bei dem Sammlungen und Wörterbücher mit sqlite github.com/modma/PersistenceCollections
ModMa