streamalism.org

1. Oversikt

I denne veiledningen introduserer vi biblioteket JCTools (Java Concurrency Tools).

Enkelt sagt, dette gir en rekke verktøy datastrukturer som passer for å jobbe i et flertrådet miljø.

2. Ikke-blokkerende algoritmer

Tradisjonelt bruker flertrådede koder som fungerer på en foranderlig delt tilstand, låser for å sikre datakonsistens og publikasjoner (endringer gjort av en tråd som er synlige for en annen).

Denne tilnærmingen har en rekke ulemper:

• tråder kan bli blokkert i et forsøk på å skaffe seg en lås, uten å gjøre fremskritt før en annen tråds operasjon er ferdig - dette forhindrer effektivt parallellitet
• jo tyngre låsekonkurranse er, jo mer tid bruker JVM på å planlegge tråder, håndtere strid og køer med ventetråder og jo mindre ekte arbeid det gjør
• sperrer er mulig hvis mer enn en lås er involvert og de anskaffes / frigjøres i feil rekkefølge
• en prioritert inversjonsfare er mulig - en tråd med høy prioritet er låst i et forsøk på å få en lås holdt av en tråd med lav prioritet
• mesteparten av tiden brukes grovkornede låser, noe som skader parallelliteten mye - finkornet låsing krever mer forsiktig design, øker låsen overhead og er mer feilutsatt

Et alternativ er å bruke a ikke-blokkerende algoritme, dvs. en algoritme der feil eller suspensjon av en hvilken som helst tråd ikke kan forårsake feil eller suspensjon av en annen tråd.

En ikke-blokkerende algoritme er låsfritt hvis minst en av de involverte trådene garantert vil gjøre fremskritt over en vilkårlig tidsperiode, dvs. at det ikke kan oppstå blokkeringer under behandlingen.

Videre er disse algoritmene ventefritt hvis det også er en garantert fremgang per tråd.

Her er en ikke-blokkering Stable eksempel fra den utmerkede Java Concurrency in Practice-boken; den definerer grunntilstanden:

offentlig klasse ConcurrentStack {AtomicReference topp = ny AtomicReference(); privat statisk klasse Node {public E item; offentlig Node neste; // standard konstruktør}}

Og også et par API-metoder:

public void push (E item) {Node newHead = new Node (item); Knutepunkt oldHead; gjør {oldHead = top.get (); newHead.next = oldHead; } while (! top.compareAndSet (oldHead, newHead)); } offentlig E pop () {Node oldHead; Node newHead; gjør {oldHead = top.get (); hvis (oldHead == null) {return null; } newHead = oldHead.next; } while (! top.compareAndSet (oldHead, newHead)); returner oldHead.item; }

Vi kan se at algoritmen bruker finkornet sammenligning og bytte (CAS) instruksjoner og er låsfritt (selv om flere tråder ringer top.compareAndSet () samtidig er en av dem garantert vellykket) men ikke ventefritt siden det ikke er noen garanti for at CAS til slutt lykkes for en bestemt tråd.

3. Avhengighet

La oss først legge til JCTools-avhengigheten til vår pom.xml:

 org.jctools jctools-core 2.1.2 

Vær oppmerksom på at den siste tilgjengelige versjonen er tilgjengelig på Maven Central.

4. JCTools køer

Biblioteket tilbyr en rekke køer som skal brukes i et miljø med flere tråder, dvs. en eller flere tråder skriver til en kø og en eller flere tråder leses fra den på en trådsikker låsfri måte.

Felles grensesnitt for alle Kø implementeringer er org.jctools.queues.MessagePassingQueue.

4.1. Typer køer

Alle køer kan kategoriseres i henhold til produsentens / forbrukerpolitikken:

• enkelt produsent, enkelt forbruker - slike klasser er navngitt ved hjelp av prefikset Spsc, f.eks. SpscArrayQueue
• enkelt produsent, flere forbrukere - bruk Spmc prefiks, f.eks. SpmcArrayQueue
• flere produsenter, én forbruker - bruk Mpsc prefiks, f.eks. MpscArrayQueue
• flere produsenter, flere forbrukere - bruk Mpmc prefiks, f.eks. MpmcArrayQueue

Det er viktig å merke seg det Det er ingen policy sjekker internt, dvs. en kø kan stille fungere feil ved feil bruk.

F.eks. testen nedenfor fyller a enkeltprodusent kø fra to tråder og passerer selv om forbrukeren ikke garantert ser data fra forskjellige produsenter:

SpscArrayQueue kø = ny SpscArrayQueue (2); Trådprodusent1 = ny tråd (() -> kø.tilbud (1)); produsent1.start (); produsent 1. bli med (); Trådprodusent2 = ny tråd (() -> kø.tilbud (2)); produsent2.start (); produsent 2. bli med (); Sett fraQueue = ny HashSet (); Trådforbruker = ny tråd (() -> kø.drenering (fraQueue :: legg til)); forbruker.start (); forbruker. bli med (); assertThat (fromQueue) .containsOnly (1, 2);

4.2. Køimplementeringer

Oppsummering av klassifiseringene ovenfor, her er listen over JCTools-køer:

• SpscArrayQueue – enkeltprodusent, enkeltforbruker, bruker en matrise internt bundet kapasitet
• SpscLinkedQueue – enkelt produsent, enkelt forbruker, bruker koblet liste internt, ubundet kapasitet
• SpscChunkedArrayQueue – enkeltprodusent, enkeltforbruker, starter med startkapasitet og vokser opp til maksimal kapasitet
• SpscGrowableArrayQueue – enkelt produsent, enkeltforbruker, starter med startkapasitet og vokser opp til maks kapasitet. Dette er den samme kontrakten som SpscChunkedArrayQueue, den eneste forskjellen er intern styring av biter. Det anbefales å bruke SpscChunkedArrayQueue fordi den har en forenklet implementering
• SpscUnboundedArrayQueue – enkeltprodusent, enkeltforbruker, bruker en rekke internt, ubundet kapasitet
• SpmcArrayQueue – enkelt produsent, flere forbrukere, bruker en matrise internt, bundet kapasitet
• MpscArrayQueue – flere produsenter, én forbruker, bruker en rekke internt bundet kapasitet
• MpscLinkedQueue – flere produsenter, én forbruker, bruker en koblet liste internt, ubundet kapasitet
• MpmcArrayQueue – flere produsenter, flere forbrukere, bruker en matrise internt, bundet kapasitet

4.3. Atomic Køer

Alle køer som er nevnt i forrige avsnitt bruker sun.misc. usikre. Men med adventen av Java 9 og JEP-260 blir denne APIen utilgjengelig som standard.

Så det er alternative køer som bruker java.util.concurrent.atomic.AtomicLongFieldUpdater (offentlig API, mindre performant) i stedet for sun.misc. usikre.

De genereres fra køene ovenfor, og navnene deres har ordet Atomisk satt inn mellom, f.eks. SpscChunkedAtomicArrayQueue eller MpmcAtomicArrayQueue.

Det anbefales å bruke ‘vanlige’ køer hvis mulig og ty til AtomicQueues bare i miljøer der sun.misc. usikre er forbudt / ineffektivt som HotSpot Java9 + og JRockit.

4.4. Kapasitet

Alle JCTools-køer kan også ha maksimal kapasitet eller være ubundet. Når en kø er full og den er bundet av kapasitet, slutter den å godta nye elementer.

I det følgende eksemplet:

• fylle køen
• sørg for at den slutter å godta nye elementer etter det
• tøm fra den og sørg for at det er mulig å legge til flere elementer etterpå

Vær oppmerksom på at et par kodeuttalelser slettes for lesbarhet. Den komplette implementeringen finner du på GitHub:

SpscChunkedArrayQueue kø = ny SpscChunkedArrayQueue (8, 16); CountDownLatch startConsuming = ny CountDownLatch (1); CountDownLatch awakeProducer = ny CountDownLatch (1); Trådprodusent = ny tråd (() -> {IntStream.range (0, kø.kapasitet ()). ForEach (i -> {assertThat (kø.offer (i)). IsTrue ();}); assertThat (kø .offer (queue.capacity ())). isFalse (); startConsuming.countDown (); awakeProducer.await (); assertThat (queue.offer (queue.capacity ())). isTrue ();}); produsent.start (); startConsuming.await (); Sett fraQueue = ny HashSet (); queue.drain (fraQueue :: add); awakeProducer.countDown (); produsent. bli med (); queue.drain (fraQueue :: add); assertThat (fromQueue) .containsAll (IntStream.range (0, 17) .boxed (). collect (toSet ()));

5. Andre JCTools datastrukturer

JCTools tilbyr også et par ikke-kø-datastrukturer.

Alle er listet opp nedenfor:

• NonBlockingHashMap – en låsfri ConcurrentHashMap alternativ med bedre skaleringsegenskaper og generelt lavere mutasjonskostnader. Det er implementert via sun.misc. usikre, så det anbefales ikke å bruke denne klassen i et HotSpot Java9 + eller JRockit miljø
• NonBlockingHashMapLong – som NonBlockingHashMap men bruker primitiv lang nøklene
• NonBlockingHashSet – en enkel innpakning NonBlockingHashMapsom JDK java.util.Collections.newSetFromMap ()
• NonBlockingIdentityHashMap – som NonBlockingHashMap men sammenligner nøkler etter identitet.
• NonBlockingSetInt – et flertrådet bitvektorsett implementert som en rekke primitive lengter. Fungerer ineffektivt i tilfelle stille autoboksing

6. Ytelsestesting

La oss bruke JMH for å sammenligne JDK-ene ArrayBlockingQueue mot JCTools kø ytelse. JMH er et open-source mikrobench-rammeverk fra Sun / Oracle JVM-guruer som beskytter oss mot ubestemmelig kompilator / jvm-optimaliseringsalgoritmer). Du er velkommen til å få mer informasjon om det i denne artikkelen.

Merk at kodebiten nedenfor savner et par utsagn for å forbedre lesbarheten. Vennligst finn den komplette kildekoden på GitHub:

offentlig klasse MpmcBenchmark {@Param ({PARAM_UNSAFE, PARAM_AFU, PARAM_JDK}) offentlig ustabil implementering av streng; offentlig flyktig kø; @Benchmark @Group (GROUP_NAME) @GroupThreads (PRODUCER_THREADS_NUMBER) public void write (Control control) {// noinspection StatementWithEmptyBody while (! Control.stopMeasurement &&! Queue.offer (1L)) {// intentionally left blank}} @Benchmark @ Group (GROUP_NAME) @GroupThreads (CONSUMER_THREADS_NUMBER) public void read (Control control) {// noinspection StatementWithEmptyBody while (! Control.stopMeasurement && queue.poll () == null) {// intentionally left blank}}}

Resultater (utdrag for 95. persentilen, nanosekunder per operasjon):

MpmcBenchmark.MyGroup: MyGroup · p0,95 MpmcArrayQueue sample 1052.000 ns / op MpmcBenchmark.MyGroup: MyGroup · p0.95 MpmcAtomicArrayQueue sample 1106.000 ns / op MpmcBenchmark.MyGroup: MyGroupB64Que

Vi kan se detMpmcArrayQueue fungerer bare litt bedre enn MpmcAtomicArrayQueue og ArrayBlockingQueue er langsommere med en faktor på to.

7. Ulemper ved bruk av JCTools

Å bruke JCTools har en viktig ulempe - det er ikke mulig å håndheve at bibliotekstimene brukes riktig. Tenk for eksempel på en situasjon når vi begynner å bruke MpscArrayQueue i vårt store og modne prosjekt (merk at det må være en enkelt forbruker).

Dessverre, ettersom prosjektet er stort, er det en mulighet for at noen lager en programmerings- eller konfigurasjonsfeil, og køen blir nå lest fra mer enn en tråd. Systemet ser ut til å fungere som før, men nå er det en sjanse for at forbrukere savner noen meldinger. Det er et reelt problem som kan ha stor innvirkning og det er veldig vanskelig å feilsøke.

Ideelt sett bør det være mulig å kjøre et system med en bestemt systemegenskap som tvinger JCTools til å sikre trådtilgangspolitikk. F.eks. lokale / test / iscenesettelsesmiljøer (men ikke produksjon) kan ha den slått på. Dessverre gir JCTools ikke en slik eiendom.

En annen vurdering er at selv om vi sørget for at JCTools er betydelig raskere enn JDKs motstykke, betyr det ikke at applikasjonen vår får samme hastighet når vi begynner å bruke de tilpassede køimplementeringene. De fleste applikasjoner utveksler ikke mange objekter mellom tråder og er for det meste I / O-bundet.

8. Konklusjon

Vi har nå en grunnleggende forståelse av nytteklassene som tilbys av JCTools og så hvor bra de presterer, sammenlignet med JDKs kolleger under tung belastning.

For å konkludere, Det er verdt å bruke biblioteket bare hvis vi utveksler mange objekter mellom tråder, og til og med da er det nødvendig å være veldig forsiktig med å bevare trådtilgangspolitikken.

Som alltid kan den fullstendige kildekoden for eksemplene ovenfor bli funnet på GitHub.