Aktuelle Sammlungen in 10 Minuten

^{Foto von Robert V. Ruggiero}

Das Thema ist nicht neu. Aber die Frage stellen: "Was sind gleichzeitige Sammlungen und wann sollen sie verwendet werden?" Bei einem Interview oder einer Codeüberprüfung erhalte ich fast immer eine Antwort, die aus einem Satz besteht: „Sie schützen uns vollständig vor Rennbedingungen“ (was selbst theoretisch unmöglich ist). Oder: „Es ist wie bei gewöhnlichen Sammlungen, aber alles im Inneren ist auf Schlössern“, was auch nicht ganz der Realität entspricht.

Der Zweck dieses Artikels ist es, das Thema in 10 Minuten zu erkennen. Es ist nützlich, um einige Feinheiten schnell kennenzulernen. Oder um Ihr Gedächtnis vor dem Interview aufzufrischen.

Zunächst werfen wir einen kurzen Blick auf den Inhalt des System.Collections.Concurrent- Namespace. Anschließend diskutieren wir die Hauptunterschiede zwischen gleichzeitigen und klassischen Sammlungen und beachten einige nicht offensichtliche Punkte. Abschließend diskutieren wir mögliche Fallstricke und wann welche Arten von Sammlungen es wert sind, verwendet zu werden.

Was ist in System.Collections.Concurrent

Intellisense sagt Ihnen ein wenig:



Lassen Sie uns kurz den Zweck jeder Klasse diskutieren.

ConcurrentDictionary : Eine thread-sichere, universelle Sammlung, die auf eine Vielzahl von Szenarien anwendbar ist.

ConcurrentBag, ConcurrentStack, ConcurrentQueue : Spezialsammlungen. "Spezialität" besteht aus folgenden Punkten:

• Fehlende API für den Zugriff auf ein beliebiges Element
• Stapel und Warteschlange (wie wir alle wissen) haben eine bestimmte Reihenfolge zum Hinzufügen und Extrahieren von Elementen
• ConcurrentBag für jeden Thread verwaltet eine eigene Sammlung zum Hinzufügen von Elementen. Beim Abrufen werden Elemente aus einem benachbarten Stream "gestohlen", wenn die Sammlung für den aktuellen Stream leer ist

IProducerConsumerCollection - Vertrag, der von der BlockingCollection- Klasse verwendet wird (siehe unten). Implementiert von den Sammlungen ConcurrentStack , ConcurrentQueue und ConcurrentBag .

BlockingCollection - Wird in Szenarien verwendet, in denen einige Streams eine Sammlung füllen, während andere Elemente daraus extrahieren. Ein typisches Beispiel ist eine aufgefüllte Aufgabenwarteschlange. Wenn die Sammlung zum Zeitpunkt der Anforderung für das nächste Element leer ist, wechselt der Leser in den Wartezustand des neuen Elements (Abfrage). Durch Aufrufen der CompleteAdding () -Methode können wir angeben, dass die Sammlung nicht mehr aufgefüllt wird und beim Lesen keine Abfrage durchgeführt wird. Sie können den Status der Sammlung mithilfe der Eigenschaften IsAddingCompleted ( true, wenn die Daten nicht mehr hinzugefügt werden) und IsCompleted ( true, wenn die Daten nicht mehr hinzugefügt werden und die Sammlung leer ist) überprüfen .

Partitioner, OrderablePartitioner, EnumerablePartitionerOptions - Grundkonstruktionen zum Implementieren der Segmentierung von Sammlungen . Wird von der Parallel.ForEach- Methode verwendet, um anzugeben, wie Elemente auf Verarbeitungsthreads verteilt werden.

Später im Artikel konzentrieren wir uns auf die Sammlungen: ConcurrentDictionary und ConcurrentBag / Stack / Queue .

Unterschiede zwischen gleichzeitigen und klassischen Sammlungen

Schutz des inneren Staates

Klassische Sammlungen sind auf maximale Leistung ausgelegt, sodass ihre Instanzmethoden keine Thread-Sicherheit gewährleisten.

Sehen Sie sich beispielsweise den Quellcode für die Dictionary.Add- Methode an.
Wir können die folgenden Zeilen sehen (der Code ist zur besseren Lesbarkeit vereinfacht):

if (this._buckets == null) { int prime = HashHelpers.GetPrime(capacity); this._buckets = new int[prime]; this._entries = new Dictionary<TKey, TValue>.Entry[prime]; } 

Wie wir sehen können, ist der interne Status des Wörterbuchs nicht geschützt. Beim Hinzufügen von Elementen aus mehreren Threads ist das folgende Szenario möglich:

1. Thread 1 mit dem Namen Add , die Ausführung wurde sofort nach Eingabe der if- Bedingung gestoppt
2. Thread 2 mit dem Namen Hinzufügen hat die Sammlung initialisiert und das Element hinzugefügt
3. Stream 1 kehrte zur Arbeit zurück, initialisierte die Sammlung neu und zerstörte dadurch die von Stream 2 hinzugefügten Daten.

Das heißt, klassische Sammlungen sind für die Aufnahme aus mehreren Streams ungeeignet.

Die API ist tolerant gegenüber dem aktuellen Status der Sammlung.

Wie wir wissen, können dem Wörterbuch keine doppelten Schlüssel hinzugefügt werden. Wenn wir Add zweimal mit demselben Schlüssel aufrufen, löst der zweite Aufruf eine ArgumentException aus .

Dieser Schutz ist in Single-Thread-Szenarien nützlich. Beim Multithreading können wir uns jedoch nicht sicher sein, wie aktuell die Sammlung ist. Schecks wie die folgenden retten uns natürlich nur, wenn wir uns ständig in ein Schloss wickeln:

 if (!dictionary.ContainsKey(key)) { dictionary.Add(key, “Hello”); } 

Die ausnahmebasierte API ist eine schlechte Option und ermöglicht kein stabiles, vorhersehbares Verhalten in Multithread-Szenarien. Stattdessen benötigen Sie eine API, die keine Annahmen über den aktuellen Status der Sammlung trifft, keine Ausnahmen auslöst und dem Aufrufer eine Entscheidung über die Zulässigkeit eines Status überlässt.

In gleichzeitigen Sammlungen basieren APIs auf dem TryXXX- Muster. Anstelle der üblichen Methoden zum Hinzufügen , Abrufen und Entfernen verwenden wir die Methoden TryAdd , TryGetValue und TryRemove . Und wenn diese Methoden false zurückgeben , entscheiden wir, ob dies eine Ausnahmesituation ist oder nicht.

Es ist erwähnenswert, dass klassische Sammlungen jetzt auch staatstolerante Methoden haben. In klassischen Sammlungen ist eine solche API jedoch eine nette Ergänzung, und in gleichzeitigen Sammlungen ist sie ein Muss.

API zur Minimierung der Rennbedingungen

Betrachten Sie die einfachste Elementaktualisierungsoperation:

 dictionary[key] += 1; 

Bei aller Einfachheit führt der Code drei Aktionen aus: Er ruft den Wert aus der Sammlung ab, addiert 1 und schreibt den neuen Wert. Bei der Ausführung mit mehreren Threads ist es möglich, dass der Code einen Wert abgerufen, ein Inkrement ausgeführt und dann den Wert, der von einem anderen Thread geschrieben wurde, während das Inkrement ausgeführt wurde, sicher gelöscht hat.

Um solche Probleme zu lösen, enthält die API für gleichzeitige Sammlungen eine Reihe von Hilfsmethoden. Zum Beispiel die TryUpdate- Methode, die drei Parameter akzeptiert : den Schlüssel, den neuen Wert und den erwarteten aktuellen Wert. Wenn der Wert in der Auflistung nicht den Erwartungen entspricht, wird die Aktualisierung nicht durchgeführt und die Methode gibt false zurück .

Betrachten Sie ein anderes Beispiel. Buchstäblich jede Zeile des folgenden Codes (einschließlich Console.WriteLine ) kann Probleme bei der Ausführung mit mehreren Threads verursachen:

 if (dictionary.ContainsKey(key)) { dictionary[key] += 1; } else { dictionary.Add(key, 1); } Console.WriteLine(dictionary[key]); 

Das Hinzufügen oder Aktualisieren eines Werts und das anschließende Ausführen einer Operation mit dem Ergebnis ist eine ziemlich typische Aufgabe. Daher verfügt das gleichzeitige Wörterbuch über die AddOrUpdate- Methode, die eine Folge von Aktionen in einem Aufruf ausführt und threadsicher ist:

 var result = dictionary.AddOrUpdate(key, 1, (itemKey, itemValue) => itemValue + 1); Console.WriteLine(result); 

Es gibt einen Punkt, über den es sich zu wissen lohnt.

Die Implementierung der AddOrUpdate- Methode ruft die oben beschriebene TryUpdate- Methode auf und übergibt den aktuellen Wert aus der Auflistung an diese. Wenn die Aktualisierung fehlgeschlagen ist (der benachbarte Thread hat den Wert bereits geändert), wird der Versuch wiederholt und der übertragene Aktualisierungsdelegierte wird erneut mit dem aktualisierten aktuellen Wert aufgerufen. Das heißt, der Update-Delegat kann mehrmals aufgerufen werden , sodass er keine Nebenwirkungen enthalten sollte.

Sperren Sie freie Algorithmen und granulare Sperren

Microsoft hat bei der Leistung gleichzeitiger Sammlungen hervorragende Arbeit geleistet und nicht nur alle Vorgänge mit Sperren versehen. Wenn Sie die Quelle studieren, sehen Sie viele Beispiele für die Verwendung granularer Sperren, die Verwendung kompetenter Algorithmen anstelle von Sperren sowie die Verwendung spezieller Anweisungen und „leichterer“ Synchronisationsprimitive als Monitor .

Welche gleichzeitigen Sammlungen geben nicht

Aus den obigen Beispielen geht hervor, dass gleichzeitige Sammlungen keinen vollständigen Schutz gegen Rennbedingungen bieten, und wir müssen unseren Code entsprechend gestalten. Aber das ist noch nicht alles, es gibt ein paar Punkte, über die es sich zu wissen lohnt.

Polymorphismus mit klassischen Sammlungen

Gleichzeitige Sammlungen implementieren wie die klassischen die Schnittstellen IDictionary , ICollection und IEnumerable . Ein Teil der API dieser Schnittstellen kann jedoch per Definition nicht threadsicher sein. Zum Beispiel die Add- Methode, die wir oben besprochen haben.

Gleichzeitige Sammlungen implementieren solche Verträge ohne Thread-Sicherheit. Um eine unsichere API zu „verbergen“, verwenden sie eine explizite Implementierung der Schnittstellen. Dies ist zu beachten, wenn wir gleichzeitige Sammlungen an Methoden übergeben, die Eingaben vornehmen, z. B. ICollection.

Gleichzeitige Sammlungen entsprechen auch nicht dem Liskov-Substitutionsprinzip in Bezug auf klassische Sammlungen.

Beispielsweise kann der Inhalt einer klassischen Sammlung während der Iteration nicht geändert werden. Der folgende Code löst eine InvalidOperationException für die List- Klasse aus:

 foreach (var element in list) { list.Remove(element); } 

Wenn es sich um gleichzeitige Sammlungen handelt, führt die Änderung zum Zeitpunkt der Aufzählung nicht zu einer Ausnahme, sodass wir gleichzeitig aus verschiedenen Streams lesen und schreiben können.

Darüber hinaus implementieren gleichzeitige Sammlungen die Möglichkeit der Änderung während der Aufzählung unterschiedlich. ConcurrentDictionary führt einfach keine Überprüfungen durch und garantiert nicht das Ergebnis der Iteration. ConcurrentStack / Queue / Bag sperrt und erstellt eine Kopie des aktuellen Status, die durchlaufen wird.

Mögliche Leistungsprobleme

Wir haben oben erwähnt, dass ConcurrentBag Elemente aus benachbarten Threads "stehlen" kann. Dies kann zu Leistungsproblemen führen, wenn Sie aus verschiedenen Threads in die ConcurrentBag schreiben und lesen.

Gleichzeitige Auflistungen führen außerdem zu vollständigen Sperren, wenn der Status der gesamten Auflistung ( Count , IsEmpty , GetEnumerator , ToArray usw.) abgefragt wird , und sind daher erheblich langsamer als ihre klassischen Gegenstücke.

Fazit: Die Verwendung gleichzeitiger Sammlungen lohnt sich nur, wenn sie wirklich notwendig sind, da diese Auswahl nicht „frei“ ist.

Wann welche Arten von Sammlungen verwendet werden sollen

• Single-Threaded-Skripte: Nur klassische Sammlungen mit der besten Leistung.
• Aufzeichnung aus mehreren Streams: Nur gleichzeitige Sammlungen, die den internen Status schützen und über eine geeignete API für wettbewerbsfähige Aufzeichnungen verfügen.
• Lesen aus mehreren Threads: Keine eindeutigen Empfehlungen. Gleichzeitige Sammlungen können Leistungsprobleme mit intensiven Statusanforderungen für die gesamte Sammlung verursachen. Für klassische Sammlungen garantiert Microsoft jedoch keine Leistung, selbst für Lesevorgänge. Beispielsweise kann eine interne Implementierung einer Sammlung verzögerte Eigenschaften aufweisen, die beim Lesen von Daten initiiert werden. Daher ist es möglich, den internen Status beim Lesen aus mehreren Threads zu zerstören. Eine gute gemittelte Option ist die Verwendung unveränderlicher Sammlungen .
• Lesen und Schreiben aus mehreren Threads: einzigartig gleichzeitige Sammlungen, die sowohl den Statusschutz als auch eine sichere API implementieren.

Schlussfolgerungen

In diesem Artikel haben wir kurz die gleichzeitigen Sammlungen untersucht, wann sie verwendet werden sollen und welche Besonderheiten sie haben. Natürlich erschöpft der Artikel das Thema nicht, und bei ernsthafter Arbeit mit Multithread-Sammlungen sollten Sie tiefer gehen. Der einfachste Weg, dies zu tun, besteht darin, den Quellcode der verwendeten Sammlungen zu betrachten. Dies ist informativ und überhaupt nicht kompliziert, der Code ist sehr, sehr gut lesbar.