Introduzione al blocco dello striping

1. Introduzione

In questo tutorial, impareremo come ottenere una sincronizzazione a grana fine, nota anche come Lock Striping, un modello per la gestione dell'accesso simultaneo alle strutture di dati mantenendo una buona prestazione.

2. Il problema

HashMap non è una struttura dati thread-safe a causa della sua natura non sincronizzata. Ciò significa che i comandi da un ambiente multi-thread potrebbero causare incoerenze dei dati.

Per superare questo problema, possiamo convertire la mappa originale con il metodo Collections # synchronizedMap o utilizzare la struttura dati HashTable . Entrambi restituiranno un'implementazione thread-safe dell'interfaccia Map , ma hanno un costo in termini di prestazioni.

L'approccio di definire l' accesso esclusivo su strutture di dati con un singolo oggetto blocco è chiamato sincronizzazione grossolana .

In un'implementazione di sincronizzazione a grana grossa, ogni accesso all'oggetto deve essere effettuato alla volta da un thread. Finiamo per avere accessi sequenziali.

Il nostro obiettivo è consentire a thread simultanei di lavorare sulla struttura dei dati garantendo la sicurezza dei thread.

3. Blocca striping

Per raggiungere il nostro obiettivo, utilizzeremo il pattern Lock Striping. Lo striping dei blocchi è una tecnica in cui il blocco si verifica su più bucket o strisce, il che significa che l'accesso a un bucket blocca solo quel bucket e non l'intera struttura dei dati.

Ci sono un paio di modi per farlo:

  • Innanzitutto, potremmo utilizzare un blocco per attività, massimizzando così la concorrenza tra le attività - questo ha un impatto di memoria maggiore, però
  • Oppure potremmo utilizzare un singolo blocco per ogni attività, che utilizza meno memoria ma compromette anche le prestazioni in simultanea

Per aiutarci a gestire questo compromesso tra prestazioni e memoria, Guava viene fornito con una classe chiamata Striped. È simile alla logica trovata in ConcurrentHashMap , ma la classe Striped va ancora oltre riducendo la sincronizzazione di attività distinte utilizzando semafori o blocchi rientranti.

4. Un rapido esempio

Facciamo un rapido esempio per aiutarci a comprendere i vantaggi di questo modello.

Ci confrontiamo HashMap vs ConcurrentHashMap e un singolo blocco contro un blocco a righe con conseguente quattro esperimenti.

Per ogni esperimento, eseguiremo letture e scritture simultanee sulla mappa sottostante . Ciò che varierà è il modo in cui accediamo a ciascun bucket.

E per questo, creeremo due classi: SingleLock e StripedLock. Queste sono implementazioni concrete di una classe astratta ConcurrentAccessExperiment che fa il lavoro.

4.1. Dipendenze

Dato che useremo la classe Striped di Guava , aggiungeremo la dipendenza guava :

 com.google.guava guava 28.2-jre 

4.2. Processo principale

La nostra classe ConcurrentAccessExperiment implementa il comportamento descritto in precedenza:

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); }

È importante notare che, poiché il nostro test è legato alla CPU, abbiamo limitato il numero di bucket ad alcuni multipli dei processori disponibili.

4.3. Accesso simultaneo con ReentrantLock

Ora implementeremo i metodi per le nostre attività asincrone.

La nostra classe SingleLock definisce un singolo blocco per l'intera struttura dati utilizzando un ReentrantLock :

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. Accesso simultaneo con strisce

Quindi, la classe StripedLock definisce un blocco con striping per ogni bucket:

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(); } }); } }

Quindi, quale strategia funziona meglio?

5. Risultati

Usiamo JMH (il Java Microbenchmark Harness) per scoprirlo. I benchmark possono essere trovati tramite il collegamento al codice sorgente alla fine del tutorial.

Eseguendo il nostro benchmark, siamo in grado di vedere qualcosa di simile al seguente (nota che una velocità effettiva maggiore è migliore):

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. Conclusioni

In questo tutorial, abbiamo esplorato diversi modi per ottenere prestazioni migliori utilizzando Lock Striping in strutture simili a mappe . Abbiamo creato un benchmark per confrontare i risultati con diverse implementazioni.

Dai nostri risultati di benchmark, possiamo capire come diverse strategie simultanee potrebbero influenzare in modo significativo il processo complessivo. Il pattern Striped Lock garantisce un bel miglioramento in quanto ottiene un punteggio extra di ~ 10% sia con HashMap che con ConcurrentHashMap .

Come al solito, il codice sorgente di questo tutorial è disponibile su GitHub.