Concurrent Datenstrukturentwurf

Question

Ich versuche, die beste Datenstruktur für den Einsatz in einem C++ - Server mit hohem Durchsatz zu finden. Die Datenstruktur wird verwendet, um alles von einigen bis zu mehreren Millionen Objekten zu speichern, und es ist keine Sortierung erforderlich (obwohl ein eindeutiger Sortierschlüssel sehr billig bereitgestellt werden kann).

Die Anforderungen sind, dass es effiziente Einfügung, idealerweise O (1), mäßig effiziente Entfernung und effiziente Traversierung unterstützen kann. Es muss keine Suchoperation unterstützt werden (außer zum Entfernen).

Der Twist ist, dass es thread sicher in Bezug auf Änderungen sein muss, während andere Threads die Datenstruktur aufzählen. Dies bedeutet, dass ein einfacher Rot-Schwarz-Baum nicht funktioniert, da ein Thread kein Element einfügen kann (und die notwendigen Baumrotationen durchführen kann), ohne dass Cursor, die von anderen Threads gehalten werden, durcheinander gebracht werden.

Es ist nicht akzeptabel, eine Schreib-/Lesesperre zu verwenden und die Schreiboperationen aufzuschieben, bis alle Leser fertig sind, da Lesevorgänge lange dauern können. Es spielt keine Rolle, ob Einfügungen, die passieren, während ein Leser vorhanden ist, für diesen Leser sichtbar sind oder nicht.

Speicherabdruck ist auch sehr wichtig, und klein ist offensichtlich besser!

Welche Vorschläge gibt es?

Antwort auf Kommentare:

Danke für die Antworten.

Nein, Inserts können vorhandene Iteratoren nicht ungültig machen. Iteratoren können die neue Einfügung sehen oder nicht, aber sie müssen alles sehen, was sie gesehen hätten, wenn die Einfügung nicht stattgefunden hätte.

Löschen ist erforderlich, aber aufgrund höherer Regeln kann ich garantieren, dass ein Iterator niemals auf einem Element gestoppt wird, das zum Löschen verfügbar ist.

Das Sperren pro Knoten für einen Cursor hätte einen zu großen Einfluss auf die Leistung. Es kann sein, dass mehrere Threads gleichzeitig lesen, und jede Art von Speicher-Hotspot, die mehrere Threads in einer Sperre verwenden, zerstört die Speicherbandbreite (wie wir es auf die harte Tour herausgefunden haben!). Selbst eine einfache Anzahl von Lesern mit mehreren Threads, die InterlockedIncrement aufrufen, kann nicht sauber skaliert werden.

Ich stimme zu, eine verkettete Liste ist wahrscheinlich der beste Ansatz. Löschvorgänge sind selten, daher ist die Zahlung der Speicherstrafe für die Rückzeiger zur Unterstützung von O (1) delete kostspielig, und wir können diese separat auf Anforderung berechnen, und da Löschvorgänge dazu tendieren, Stapeloperationen zu sein.

Zum Glück erfordert das Einfügen in eine verknüpfte Liste kein Sperren für Leser, solange die Zeiger im eingefügten Knoten aktualisiert werden, bevor der Kopfzeiger geändert wird.

Die Lock-Copy-Unlock-Idee ist interessant. Die Menge der beteiligten Daten ist zu groß, um als Standard für Leser zu dienen, aber sie könnte für Autoren verwendet werden, wenn sie mit Lesern kollidieren. Eine Lese-/Schreibsperre würde die gesamte Struktur schützen, und der Schreibvorgang würde die Datenstruktur klonen, wenn sie mit einem Lesegerät kollidiert. Schreiben sind viel seltener als lesen.

Answer 1

Persönlich bin ich ziemlich hartnäckig unveränderliche unveränderliche Datenstrukturen in hoch-konkurrierenden Situationen. Ich kenne keine speziell für C++, aber Rich Hickey hat in Java für Clojure einige ausgezeichnete (und blitzartig schnelle) unveränderliche Datenstrukturen geschaffen Ashtable und Hashset. Sie sind nicht zu schwer zu portieren, also sollten Sie eine davon in Betracht ziehen.

Um ein bisschen mehr zu erarbeiten, lösen dauerhafte unveränderliche Datenstrukturen wirklich viele Probleme im Zusammenhang mit Nebenläufigkeit. Da die Datenstruktur selbst unveränderlich ist, gibt es kein Problem, wenn mehrere Threads gleichzeitig lesen/iterieren (solange es ein konstanter Iterator ist). "Schreiben" kann auch asynchron sein, weil es nicht wirklich in die bestehende Struktur schreibt, sondern eine neue Version dieser Struktur erzeugt, die das neue Element enthält. Diese Operation wird effizient gemacht (O (1) in allen Strukturen von Hickey) durch die Tatsache, dass Sie nicht wirklich alles kopieren. Jede neue Version teilt den größten Teil ihrer Struktur mit der alten Version.Dadurch werden die Speicher effizienter und die Leistung gegenüber der einfachen Copy-on-Write-Technik deutlich verbessert.

Mit unveränderlichen Datenstrukturen ist die einzige Zeit, in der Sie tatsächlich synchronisieren müssen, das Schreiben in eine Referenzzelle. Da der Speicherzugriff atomar ist, kann auch dieser normalerweise sperrfrei sein. Die einzige Einschränkung hier ist, dass Sie möglicherweise Daten zwischen Threads verlieren (Race Conditions). Die Datenstruktur wird niemals aufgrund von Parallelität beschädigt, aber das bedeutet nicht, dass inkonsistente Ergebnisse in Situationen nicht möglich sind, in denen zwei Threads eine neue Version der Struktur basierend auf einem einzelnen alten erstellen und versuchen, ihre Ergebnisse zu schreiben (einer davon wird) "gewinnen" und die Änderungen des anderen werden verloren gehen. Um dieses Problem zu lösen, müssen Sie entweder eine Sperre für "Schreiboperationen" haben oder eine Art von STM verwenden. Ich mag den zweiten Ansatz für Benutzerfreundlichkeit und Durchsatz in Systemen mit geringer Kollision (Schreibvorgänge sind im Idealfall nicht blockierend und lesen nie Block), aber beide funktionieren.

Sie haben eine schwierige Frage gestellt, für die es keine wirklich gute Antwort gibt. Concurrency-sichere Datenstrukturen sind schwer zu schreiben, insbesondere wenn sie veränderbar sein müssen. Vollständig blockierungsfreie Architekturen sind bei Vorhandensein eines gemeinsamen Zustands nachweisbar unmöglich, daher sollten Sie diese Anforderung aufgeben. Das Beste, was Sie tun können, ist das Minimieren der erforderlichen Sperren, daher die unveränderlichen Datenstrukturen.

Answer 2

Ich denke, verknüpfte Liste sollte Ihre Anforderungen beantworten. Beachten Sie, dass Sie nur die Knoten sperren können, die geändert werden (d. H. Gelöscht/angehängt), damit die Leser die meiste Zeit in voller Parallelität mit den Schreibern arbeiten können. Dieser Ansatz erfordert eine Sperre pro verknüpftem Listenknoten. Dies ist jedoch kein Muss.Sie können eine begrenzte Anzahl von Sperren haben, und dann werden mehrere Knoten derselben Sperre zugeordnet. Das heißt, mit einem Array von N Sperren und Knoten mit der Nummer 0..M können Sie die Sperre (NodeId% N) zum Sperren dieses Knotens verwenden. Diese können Lese-Schreib-Sperren sein, und durch Steuern der Anzahl der Sperren können Sie die Menge der Parallelität steuern.

Answer 3

Nun, um threadsicher zu sein, müssen Sie irgendwann etwas sperren. Eine wichtige Sache besteht darin, sicherzustellen, dass die Objekte in Ihrem Repository getrennt von der Repository-Struktur selbst gesperrt werden können: d. H. Keine _next-Verknüpfung oder irgendetwas von der Art innerhalb der Daten, die Sie speichern. Auf diese Weise können Lesevorgänge den Inhalt der Objekte sperren, ohne die Struktur des Repositorys zu sperren.

Effiziente Einfügung ist einfach: Verkettete Liste, unsortierte Arrays, Hashtables funktionieren alle ok. Effizientes Löschen ist schwieriger, da dabei das gelöschte Objekt im Repository gefunden wird. Aber für rohe Einfachheit und Geschwindigkeit ist eine verkettete Liste eine gute Wahl. Können Löschungen für Zeiten, in denen kein Besetztzeichen vorhanden ist, und für gerade als "inaktiv" markierte Posten verschoben werden? Dann sind die Kosten des Findens/Löschens nicht so einschränkend.

Sie werden immer noch Probleme mit Traversal haben. Alles, was Sie tun können, ist das Sperren und Erstellen eines Snapshots dessen, was durchlaufen werden muss. Überprüfen Sie dann nach dem Betrachten des Snapshots alle Änderungen. Tough problem ...

Answer 4

Wenn Sie keine Sortierreihenfolge benötigen, verwenden Sie keinen rot/schwarzen Baum oder irgendetwas anderes, das inhärent sortiert.

Ihre Frage ist nicht gut genug genug, um Interaktion zwischen Lesen und Schreiben. Wäre es in Ordnung, wenn ein "read" durch ein lock + copy + unlock implementiert wird und dann die neue Kopie verwendet?

Sie können über Seqlocks in http://en.wikipedia.org/wiki/Seqlock lesen, und auf "sperren frei" Prozesse im Allgemeinen - obwohl Sie Ihre Anforderungen so viel wie möglich entspannen möchten - eine Lock-Free-Hash-Tabelle Implementierung ist ein wichtiger Unternehmen.

Answer 5

Verknüpfte Listen sind definitiv die Antwort hier. Einfügen und Löschen in O (1), Iteration von einem Knoten zum nächsten in O (1) und Stabilität über Operationen hinweg. std::list garantiert all dies, einschließlich der Tatsache, dass alle Iteratoren gültig sind, es sei denn, das Element wird aus der Liste entfernt (dies beinhaltet Zeiger und Verweise auf Elemente). Zum Sperren können Sie die Liste einfach in eine Sperrklasse einbinden, oder Sie könnten Ihre eigene Listenklasse schreiben (Sie könnten std::list in diesem Fall nicht verwenden, das die node-basierte Sperrung unterstützt - z. B. können Sie bestimmte Bereiche sperren Die Liste wird verwendet, während andere Threads Operationen in verschiedenen Bereichen ausführen.Welche Sie verwenden, hängt weitgehend von der Art des gleichzeitigen Zugriffs ab, den Sie erwarten - wenn mehrere Operationen an verschiedenen Teilen der Liste wirklich üblich sind, schreiben Sie Ihre eigenen, aber denken Sie daran ein Mutex-Objekt in jedem Knoten zu platzieren, was nicht platzsparend ist.

Answer 6

Apologies für die Doppel Antwort ...

Da schreibt sind ziemlich selten, Sie wirklich sollte mit STM statt Sperren berücksichtigen. STM ist eine Form des optimistischen Sperrens, was bedeutet, dass es in Bezug auf die Leistung gegenüber kollisionsfreien Systemen stark voreingenommen ist (auch weniger Schreibvorgänge). Im Gegensatz dazu ist pessimistisches Sperren (Sperren-Schreiben-Entsperren) für kollisionslastige Systeme optimiert (auch viele Schreibvorgänge). Der einzige Haken bei STM ist, dass Sie nahezu unveränderliche Datenstrukturen innerhalb der TVar-Zellen benötigen, sonst bricht das ganze System zusammen. Ich persönlich denke nicht, dass dies ein Problem ist, da eine anständige, unveränderliche Datenstruktur genauso schnell wie eine änderbare sein wird (siehe meine andere Antwort), aber es ist eine Überlegung wert.

Answer 7

Sie haben drei Arten von Aufgaben:

1. Iteration (langsam)
2. Insertion (schnell)
3. Deletion (schnell)

Wenn in der Nähe von Konsistenz gut genug ist, dann Spur halten der Anzahl der aktiven Iterationsaufgaben.

Wenn Iterationen Aufgaben aktiv sind und eine neuer Einsatz oder Löschung Aufgaben kommen in der Warteschlange diese Aufgaben für die spätere Verarbeitung (aber man kann die Rückkehr sofort an Anrufer)

Sobald die letzte Iteration, wenn fertig Prozesseinsätze der Warteschlange und löscht.

Wenn eine Iterationsanforderung eingeht, während Einfügungen oder Löschungen ausstehen, dann stellen Sie sie in eine Warteschlange.

Wenn eine Iterationsanforderung eingeht, während gerade Iterationen ausgeführt werden, lassen Sie sie einfach durchlaufen und iterieren.

Sie sollten die Iteration immer noch so schnell wie möglich schreiben, indem Sie eine Kopie der Daten erstellen, die Sie durchlaufen, und diese Daten dann im Client verarbeiten, wenn die eigentliche Datenverarbeitung viel länger dauert als die Iteration selbst.

Ich würde die Hauptsammlung mit einer Hashtable oder STL implementieren: Karte könnte sogar schnell genug sein. Anforderungen zum Einfügen/Löschen können in eine Liste eingereiht werden.

Answer 8

Die einzige Möglichkeit, dies zu erreichen, ist durch etwas ähnliches wie Multiversion Concurrency-Protokoll in Datenbanken wie Orakel/Postgresql usw. Dies garantiert, dass Leser nicht blockiert Leser, Schreiber nicht blockiert Leser, sondern Schriftsteller blockieren nur diejenigen Autoren, die das gleiche Stück Daten aktualisieren. Diese Eigenschaft von Schreibern, die die Schreiber blockieren, die dasselbe Stück Daten aktualisieren, ist in der Welt der konkurrierenden Programmierung wichtig, da sonst Daten/Systeminkonsistenzen möglich sind. Für jede Schreiboperation in die Datenstruktur erstellen Sie einen Snapshot der Datenstruktur oder zumindest den Teil der Datenstrukturknoten, der von der Schreiboperation betroffen ist, bevor Sie den Schreibvorgang ausführen. Wenn also während des Schreibvorgangs ein Leser-Thread einen Teil der Daten aus dem Writer-Teil lesen möchte, verweisen Sie immer auf den letzten Snapshot &, der über diesen Snapshot iteriert, indem eine konsistente Datenansicht für alle Leser bereitgestellt wird. Schnappschüsse sind teuer, da sie mehr Speicher verbrauchen, aber für Ihre gegebene Anforderung ist diese Technik die richtige. Und ja, benutze Locks (Mutex/Semaphore/Spinlock), um die Schreiboperation vor anderen Writer-Threads/Prozessen zu schützen, die das gleiche Stück Daten aktualisieren müssen.

Answer 9

FWIW, das ist trivial zu lösen, wenn Sie einen Garbage Collector haben. In F # können Sie beispielsweise eine veränderbare Referenz zu einer verketteten Liste oder einer rein funktionalen Map (balanced binary tree) ohne Sperren verwenden. Dies funktioniert, weil die Datenstrukturen unveränderlich sind und das Schreiben einer Referenz (um nach einem Schreibvorgang zu aktualisieren) atomar ist, so dass gleichzeitige Leser entweder die alte oder die neue Datenstruktur sehen, aber niemals eine Beschädigung. Wenn Sie mehrere Writer haben, können Sie sie serialisieren.

Dies ist jedoch viel schwieriger in C++ zu lösen ...

Answer 10

Ich bin nicht sicher, ob jemand dies erwähnt hat, aber ich würde inspiriert von Java ConcurrentHashMap nehmen. Es bietet Traversieren, Abrufen und Einfügen ohne Sperren oder Warten. Die einzige Sperre tritt auf, sobald Sie einen Bucket mit Daten gefunden haben, der dem Hash-Schlüssel entspricht, und Sie durchlaufen diesen Bucket (d. H. Sie sperren nur den Bucket, nicht die tatsächliche Hash-Map). "Anstelle einer einzelnen Auflistungssperre verwendet ConcurrentHashMap einen festen Pool von Sperren, die eine Partition über der Sammlung von Buckets bilden."

Sie finden weitere Details zur tatsächlichen Implementierung here. Ich glaube, dass alle in der Implementierung gezeigten Dinge genauso einfach mit C++ erledigt werden können.

Also lassen Sie sich durch Ihre Liste der Anforderungen gehen:

1. High throughput. CHECK 
2. Thread safe. CHECK 
3. Efficient inserts happen in O(1). CHECK 
4. Efficient removal (with no data races or locks). CHECK 
5. VERY efficient traversal. CHECK 
6. Does not lock or wait. CHECK 
7. Easy on the memory. CHECK 
8. It is scalable (just increase the lock pool). CHECK 

Hier ein Beispiel einer Karte Eintrag ist:

protected static class Entry implements Map.Entry { 
    protected final Object key; 
    protected volatile Object value; 
    protected final int hash; 
    protected final Entry next; 
    ... 
} 

Beachten Sie, dass der Wert flüchtig ist, so dass, wenn wir das Entfernen einer Eintrag wir setzen den Wert auf NULL, der automatisch für jeden anderen Thread sichtbar ist, der versucht, den Wert zu lesen.

Answer 11

Ich bin ein bisschen spät auf die Party. Aber wenn jemand immer noch nach einer praktischen Lösung für dieses Problem sucht und sich noch nicht für einen Server entschieden hat, lassen Sie mich vorschlagen Google's App Engine. Ihr Datastore ist für diese Art von Anforderungen optimiert.