Einführung in Lock Striping

1. Einleitung

In diesem Tutorial erfahren Sie, wie Sie eine fein abgestimmte Synchronisation erzielen, die auch als Lock Striping bezeichnet wird. Dabei handelt es sich um ein Muster für den gleichzeitigen Zugriff auf Datenstrukturen bei gleichzeitiger Aufrechterhaltung einer guten Leistung.

2. Das Problem

HashMap ist aufgrund seiner nicht synchronisierten Natur keine threadsichere Datenstruktur. Das bedeutet, dass Befehle aus einer Multithread-Umgebung zu Dateninkonsistenzen führen können.

Um dieses Problem zu beheben , können wir entweder die ursprüngliche Map mit der Collections # synchronizedMap- Methode konvertieren oder die HashTable- Datenstruktur verwenden. Beide geben eine thread-sichere Implementierung der Map- Schnittstelle zurück, gehen jedoch zu Lasten der Leistung.

Der Ansatz, exklusiven Zugriff auf Datenstrukturen mit einem einzelnen Sperrobjekt zu definieren, wird als grobkörnige Synchronisation bezeichnet .

In einer grobkörnigen Synchronisationsimplementierung muss jeder Zugriff auf das Objekt jeweils von einem Thread ausgeführt werden. Am Ende haben wir sequentielle Zugriffe.

Unser Ziel ist es, gleichzeitigen Threads die Möglichkeit zu geben, an der Datenstruktur zu arbeiten und gleichzeitig die Thread-Sicherheit zu gewährleisten.

3. Lock Striping

Um unser Ziel zu erreichen, verwenden wir das Lock Striping-Muster. Lock Striping ist eine Technik, bei der das Sperren an mehreren Buckets oder Stripes erfolgt. Dies bedeutet, dass beim Zugriff auf einen Bucket nur dieser Bucket und nicht die gesamte Datenstruktur gesperrt wird.

Es gibt verschiedene Möglichkeiten, dies zu tun:

  • Erstens könnten wir eine Sperre pro Aufgabe verwenden, um die Parallelität zwischen Aufgaben zu maximieren - dies hat jedoch einen höheren Speicherbedarf
  • Oder wir könnten für jede Aufgabe eine einzige Sperre verwenden, die weniger Speicher benötigt, aber auch die Leistung bei gleichzeitiger Verwendung beeinträchtigt

Um diesen Kompromiss zwischen Leistung und Speicher zu bewältigen, wird Guava mit einer Klasse namens Striped ausgeliefert. Es ähnelt der Logik in ConcurrentHashMap , aber die Striped- Klasse geht noch weiter, indem sie die Synchronisation bestimmter Aufgaben mithilfe von Semaphoren oder wiedereintretenden Sperren reduziert.

4. Ein kurzes Beispiel

Lassen Sie uns ein kurzes Beispiel geben, um die Vorteile dieses Musters zu verstehen.

Wir werden HashMap vs. ConcurrentHashMap und eine einzelne Sperre mit einer gestreiften Sperre vergleichen, was zu vier Experimenten führt.

Für jedes Experiment führen wir gleichzeitige Lese- und Schreibvorgänge auf der zugrunde liegenden Karte durch . Was variieren wird, ist, wie wir auf jeden Eimer zugreifen.

Und dafür erstellen wir zwei Klassen - SingleLock und StripedLock. Dies sind konkrete Implementierungen einer abstrakten Klasse ConcurrentAccessExperiment , die die Arbeit erledigt.

4.1. Abhängigkeiten

Da wir die Striped- Klasse von Guava verwenden , fügen wir die Guavenabhängigkeit hinzu :

 com.google.guava guava 28.2-jre 

4.2. Hauptprozess

Unsere ConcurrentAccessExperiment- Klasse implementiert das zuvor beschriebene Verhalten:

public abstract class ConcurrentAccessExperiment { public final Map doWork(Map map, int threads, int slots) { CompletableFuture[] requests = new CompletableFuture[threads * slots]; for (int i = 0; i < threads; i++) { requests[slots * i + 0] = CompletableFuture.supplyAsync(putSupplier(map, i)); requests[slots * i + 1] = CompletableFuture.supplyAsync(getSupplier(map, i)); requests[slots * i + 2] = CompletableFuture.supplyAsync(getSupplier(map, i)); requests[slots * i + 3] = CompletableFuture.supplyAsync(getSupplier(map, i)); } CompletableFuture.allOf(requests).join(); return map; } protected abstract Supplier putSupplier(Map map, int key); protected abstract Supplier getSupplier(Map map, int key); }

Da unser Test CPU-gebunden ist, haben wir die Anzahl der Buckets auf ein Vielfaches der verfügbaren Prozessoren beschränkt.

4.3. Gleichzeitiger Zugriff mit ReentrantLock

Jetzt implementieren wir die Methoden für unsere asynchronen Aufgaben.

Unsere SingleLock- Klasse definiert mithilfe eines ReentrantLock eine einzelne Sperre für die gesamte Datenstruktur :

public class SingleLock extends ConcurrentAccessExperiment { ReentrantLock lock; public SingleLock() { lock = new ReentrantLock(); } protected Supplier putSupplier(Map map, int key) { return (()-> { lock.lock(); try { return map.put("key" + key, "value" + key); } finally { lock.unlock(); } }); } protected Supplier getSupplier(Map map, int key) { return (()-> { lock.lock(); try { return map.get("key" + key); } finally { lock.unlock(); } }); } }

4.4. Gleichzeitiger Zugriff mit Striped

Anschließend definiert die StripedLock- Klasse für jeden Bucket ein Striped Lock:

public class StripedLock extends ConcurrentAccessExperiment { Striped lock; public StripedLock(int buckets) { lock = Striped.lock(buckets); } protected Supplier putSupplier(Map map, int key) { return (()-> { int bucket = key % stripedLock.size(); Lock lock = stripedLock.get(bucket); lock.lock(); try { return map.put("key" + key, "value" + key); } finally { lock.unlock(); } }); } protected Supplier getSupplier(Map map, int key) { return (()-> { int bucket = key % stripedLock.size(); Lock lock = stripedLock.get(bucket); lock.lock(); try { return map.get("key" + key); } finally { lock.unlock(); } }); } }

Welche Strategie ist also besser?

5. Ergebnisse

Verwenden wir JMH (das Java Microbenchmark Harness), um dies herauszufinden. Die Benchmarks finden Sie über den Quellcode-Link am Ende des Tutorials.

Wenn wir unseren Benchmark ausführen, sehen wir etwas Ähnliches wie das Folgende (beachten Sie, dass ein höherer Durchsatz besser ist):

Benchmark Mode Cnt Score Error Units ConcurrentAccessBenchmark.singleLockConcurrentHashMap thrpt 10 0,059 ± 0,006 ops/ms ConcurrentAccessBenchmark.singleLockHashMap thrpt 10 0,061 ± 0,005 ops/ms ConcurrentAccessBenchmark.stripedLockConcurrentHashMap thrpt 10 0,065 ± 0,009 ops/ms ConcurrentAccessBenchmark.stripedLockHashMap thrpt 10 0,068 ± 0,008 ops/ms 

6. Schlussfolgerungen

In diesem Tutorial, erkundeten wir verschiedene Möglichkeiten, wie wir eine bessere Leistung mit Lock - Striping in erreichen können Map -ähnlichen Strukturen. Wir haben einen Benchmark erstellt, um die Ergebnisse mit mehreren Implementierungen zu vergleichen.

Anhand unserer Benchmark-Ergebnisse können wir verstehen, wie unterschiedliche gleichzeitige Strategien den Gesamtprozess erheblich beeinflussen können. Das Striped-Lock-Muster bietet eine erhebliche Verbesserung, da es sowohl mit HashMap als auch mit ConcurrentHashMap ~ 10% mehr Punkte erzielt .

Wie üblich ist der Quellcode für dieses Tutorial auf GitHub verfügbar.