Introduktion til Lock Striping

1. Introduktion

I denne vejledning lærer vi, hvordan man opnår finkornet synkronisering, også kendt som Lock Striping, et mønster til håndtering af samtidig adgang til datastrukturer, samtidig med at man holder en god præstation.

2. Problemet

HashMap er ikke en trådsikker datastruktur på grund af dens ikke-synkroniserede natur. Det betyder, at kommandoer fra et miljø med flere tråde kan resultere i datainkonsistens.

For at løse dette problem kan vi enten konvertere det originale kort med Samlinger # synchronizedMap metode eller brug HashTable datastruktur. Begge returnerer en trådsikker implementering af Kort interface, men de koster præstation.

Metoden med at definere eksklusiv adgang over datastrukturer med et enkelt låseobjekt kaldes grovkornet synkronisering.

I en grovkornet synkroniseringsimplementering skal enhver adgang til objektet foretages ad gangen af ​​en tråd. Vi ender med at have sekventielle adganger.

Vores mål er at tillade samtidige tråde at arbejde på datastrukturen og samtidig sikre trådsikkerhed.

3. Låsestribning

For at nå vores mål bruger vi Lock Striping-mønsteret. Låsestribning er en teknik, hvor låsning sker på flere skovle eller striber, hvilket betyder at adgang til en skov kun låser skovlen og ikke hele datastrukturen.

Der er et par måder at gøre dette på:

  • For det første kunne vi bruge en lås pr. Opgave og dermed maksimere samtidigheden mellem opgaver - dette har dog et højere hukommelsesfodaftryk
  • Eller vi kunne bruge en enkelt lås til hver opgave, der bruger mindre hukommelse, men også kompromitterer ydeevnen i samtidighed

For at hjælpe os med at styre denne kompromis mellem ydeevnehukommelse leveres Guava med en klasse kaldet Stribet. Det svarer til logikken, der findes i ConcurrentHashMap, men Stribet klasse går endnu længere ved at reducere synkroniseringen af ​​forskellige opgaver ved hjælp af semaforer eller reentrant-låse.

4. Et hurtigt eksempel

Lad os gøre et hurtigt eksempel for at hjælpe os med at forstå fordelene ved dette mønster.

Vi sammenligner HashMap vs. ConcurrentHashMap og en enkelt lås mod en stribet lås, hvilket resulterede i fire eksperimenter.

For hvert eksperiment udfører vi samtidige læser og skriver om det underliggende Kort. Hvad der vil variere er, hvordan vi får adgang til hver spand.

Og til det opretter vi to klasser - SingleLock og StripedLock. Dette er konkrete implementeringer af en abstrakt klasse ConcurrentAccessExperiment det gør arbejdet.

4.1. Afhængigheder

Da vi skal bruge Guava Stribet klasse, tilføjer vi guava afhængighed:

 com.google.guava guava 28.2-jre 

4.2. Hovedproces

Vores ConcurrentAccessExperiment klasse implementerer den tidligere beskrevne adfærd:

offentlig abstrakt klasse ConcurrentAccessExperiment {public final Map doWork (Map map, int threads, int slots) {CompletableFuture [] anmodninger = ny CompletableFuture [threads * slots]; for (int i = 0; i <threads; i ++) {anmodninger [slots * i + 0] = CompletableFuture.supplyAsync (putSupplier (kort, i)); anmodninger [slots * i + 1] = CompletableFuture.supplyAsync (getSupplier (kort, i)); anmodninger [slots * i + 2] = CompletableFuture.supplyAsync (getSupplier (kort, i)); anmodninger [slots * i + 3] = CompletableFuture.supplyAsync (getSupplier (kort, i)); } CompletableFuture.allOf (anmodninger). Sammenføjning (); returkort; } beskyttet abstrakt Leverandør putSupplier (kortkort, int-nøgle); beskyttet abstrakt leverandør getSupplier (kortkort, int-nøgle); }

Det er vigtigt at bemærke, at da vores test er CPU-bundet, har vi begrænset antallet af skovle til nogle multiple af de tilgængelige processorer.

4.3. Samtidig adgang til ReentrantLock

Nu implementerer vi metoderne til vores asynkrone opgaver.

Vores SingleLock klasse definerer en enkelt lås for hele datastrukturen ved hjælp af en ReentrantLock:

offentlig klasse SingleLock udvider ConcurrentAccessExperiment {ReentrantLock-lås; offentlig SingleLock () {lås = ny ReentrantLock (); } beskyttet leverandør putSupplier (kortkort, int-nøgle) {return (() -> {lock.lock (); prøv {return map.put ("nøgle" + nøgle, "værdi" + nøgle);} endelig {lås. låse op ();}}); } beskyttet leverandør getSupplier (kortkort, int-nøgle) {return (() -> {lock.lock (); prøv {return map.get ("nøgle" + nøgle);} endelig {lock.unlock ();}} ); }}

4.4. Samtidig adgang til Stribet

Derefter StripedLock klasse definerer en stribet lås til hver skovl:

offentlig klasse StripedLock udvider ConcurrentAccessExperiment {Striped lock; offentlig StripedLock (int spande) {lås = Striped.lock (spande); } beskyttet leverandør putSupplier (kortkort, int-nøgle) {return (() -> {int bucket = key% stripedLock.size (); Lock lock = stripedLock.get (bucket); lock.lock (); prøv {return map .put ("nøgle" + nøgle, "værdi" + nøgle);} endelig {lock.unlock ();}}); } beskyttet leverandør getSupplier (kortkort, int-nøgle) {return (() -> {int bucket = key% stripedLock.size (); Lock lock = stripedLock.get (bucket); lock.lock (); prøv {return map .get ("nøgle" + nøgle);} endelig {lock.unlock ();}}); }}

Så hvilken strategi klarer sig bedre?

5. Resultater

Lad os bruge JMH (Java Microbenchmark Harness) til at finde ud af det. Benchmarks kan findes via kildekodelinket i slutningen af ​​vejledningen.

Når vi kører vores benchmark, kan vi se noget der ligner følgende (bemærk at højere kapacitet er bedre):

Benchmark Mode Cnt Score Fejlenheder ConcurrentAccessBenchmark.singleLockConcurrentHashMap thrpt 10 0,059 ± 0,006 ops / ms ConcurrentAccessBenchmark.singleLockHashMap thrpt 10 0,061 ± 0,005 ops / ms ConcurrentAccessBenchmark.stripedLockConcurrentHashMap thrpt9 0,0 

6. Konklusioner

I denne vejledning undersøgte vi forskellige måder, hvordan vi kan opnå bedre ydeevne ved hjælp af Lock Striping in Kort-lignende strukturer. Vi skabte et benchmark for at sammenligne resultaterne med flere implementeringer.

Fra vores benchmark-resultater kan vi forstå, hvordan forskellige samtidige strategier i væsentlig grad kan påvirke den samlede proces. Stribet låsemønster giver en ganske forbedring, da det scorer ~ 10% ekstra med begge HashMap og ConcurrentHashMap.

Som normalt er kildekoden til denne vejledning tilgængelig på GitHub.