Pričajmo o Java kolekcijama za konkurentnost: ConcurrentHashMap, redovi blokiranja i CopyOnWrite kontejneri

Chenmo Wang Er2061 reči7 minuta

Java kolekcije za konkurentnost pružaju strukture podataka za efikasan pristup i rad u višenitnom okruženju. Ovi kontejneri kroz interne mehanizme sinhronizacije ostvaruju bezbednost niti, čime se omogućava programerima da bez eksplicitne sinhronizacije koda bezbedno koriste te kontejnere u konkurentnom okruženju — na primer: ConcurrentHashMap, redovi blokiranja i CopyOnWrite kontejneri.

Paket java.util pruža neke klase kontejnera (okvir kolekcija), među kojima su Vector i Hashtable bezbedni za niti, ali je njihov način implementacije prilično grub — realizovan dodavanjem ključne reči „sychronized" na metode.

Ali čak i za klasu bezbednu za niti kao što je Vector, pri složenim operacijama u višenitnom okruženju potrebno je i na strani klijenta nastaviti sa zaključavanjem kako bi se garantovala atomičnost. Pogledajte sledeći primer:

public class TestVector {
	private Vector<String> vector;

	//Metod jedan
	public  Object getLast(Vector vector) {
	    int lastIndex = vector.size() - 1;
	    return vector.get(lastIndex);
	}

	//Metod dva
	public  void deleteLast(Vector vector) {
	    int lastIndex = vector.size() - 1;
	    vector.remove(lastIndex);
	}

	//Metod tri
	public  Object getLastSysnchronized(Vector vector) {
		synchronized(vector){
			int lastIndex = vector.size() - 1;
			return vector.get(lastIndex);
		}
	}

	//Metod četiri
	public  void deleteLastSysnchronized(Vector vector) {
		synchronized (vector){
			int lastIndex = vector.size() - 1;
			vector.remove(lastIndex);
		}
	}

}

Ako su metod jedan i metod dva jedna kombinacija, onda kada metod jedan dobije vector-ov size, metod dva je već završio, što će dovesti do greške u programu.

Ako se kombinuju metod tri i metod četiri, potrebno je dodati internu bravu kako bi se garantovala atomska operacija nad vector-om.

Tako su nastali konkurentni kontejneri — oni su bezbedni za niti i omogućavaju efikasan pristup i rad sa podacima u višenitnom okruženju, bez potrebe za dodatnim merama sinhronizacije.

Klase konkurentnih kontejnera

Celokupna arhitektura je prikazana na slici ispod:

Konkurentna mapa

ConcurrentMap interfejs

ConcurrentMap interfejs nasleđuje interfejs Map i na osnovu interfejsa Map definiše još četiri metode:

public interface ConcurrentMap<K, V> extends Map<K, V> {

    //Umetanje elementa
    V putIfAbsent(K key, V value);

    //Uklanjanje elementa
    boolean remove(Object key, Object value);

    //Zamena elementa
    boolean replace(K key, V oldValue, V newValue);

    //Zamena elementa
    V replace(K key, V value);

}

putIfAbsent: za razliku od prvobitne metode put, putIfAbsent ne zamenjuje prvobitnu vrednost value ako je umetnuti ključ isti.

remove: za razliku od prvobitne metode remove, nova metoda remove dodaje proveru vrednosti value; ako par ključ-vrednost koji treba obrisati ne odgovara originalnom paru ključ-vrednost u mapi, taj element se neće obrisati.

replace(K,V,V): dodata je provera vrednosti value; samo ako key-oldValue odgovara originalnom paru ključ-vrednost u mapi, vrši se zamena.

replace(K,V): za razliku od gore navedenog replace, ovaj replace ne poredi originalni par ključ-vrednost u mapi; ako ključ postoji, direktno se vrši zamena.

ConcurrentHashMap

ConcurrentHashMap, kao i HashMap, je mapa zasnovana na hash tabeli, ali pruža strategiju zaključavanja potpuno drugačiju od Hashtable-a, čime pruža efikasniju konkurentnost i skalabilnost.

Kasnije ćemo otvoriti poseban članak za detaljan prikaz ConcurrentHashMap — kliknite na link za direktan pristup.

ConcurrentSkipListMap

ConcurrentNavigableMap interfejs nasleđuje interfejs NavigableMap, koji pruža navigacione metode koje za zadati cilj pretrage vraćaju najsličnije poklapanje.

Glavna klasa implementacije ConcurrentNavigableMap interfejsa je klasa ConcurrentSkipListMap. Iz imena se vidi da njeno donje složenje koristi skočnu listu (SkipList). Skočna lista je struktura podataka kojom se „prostorno zamenjuje vreme", a može koristiti CAS za garantovanje konkurentne bezbednosti.

U poređenju sa operacijama intenzivnim po čitanju u ConcurrentHashMap-u, performanse čitanja i pisanja ConcurrentSkipListMap-a su relativno niže. To je posledica njene strukture podataka, jer umetanje i brisanje u skočnoj listi zahtevaju složenije operacije sa pokazivačima. Međutim, ConcurrentSkipListMap pruža uređenost, što ConcurrentHashMap nema.

ConcurrentSkipListMap je pogodan za situacije gde je potrebna bezbednost niti, a i uređenost elemenata. Ako uređenost nije potrebna, ConcurrentHashMap je možda bolji izbor, jer obično ima veće performanse.

Konkurentni red

JDK ne pruža klasu liste bezbednu za niti, jer je za listu veoma teško razviti opštu listu bezbednu za niti koja nema usko grlo u konkurentnosti. Jer čak i jednostavna operacija čitanja, kao što je contains(), zahteva da se pri pretrazi zaključa cela lista.

Zato je JDK, kao kompromis, pružio klase redova i dvoredova bezbedne za niti: ConcurrentLinkedQueue i ConcurrentLinkedDeque. Red, u poređenju sa listom, ima više ograničenja. Ove dve klase koriste CAS za ostvarivanje bezbednosti niti.

Kasnije ćemo otvoriti poseban članak za detaljan prikaz ConcurrentLinkedQueue — kliknite na link za direktan pristup.

Konkurentni skup

ConcurrentSkipListSet je uređena kolekcija bezbedna za niti. Donje složenje koristi ConcurrentSkipListMap za implementaciju.

Googleov Guava implementirao je ConcurrentHashSet bezbedan za niti:

Set<String> s = Sets.newConcurrentHashSet();

Skup se u svakodnevnom razvoju ne koristi mnogo, pa ovde nećemo ulaziti u detalje.

Red blokiranja

Pretpostavimo scenario: proizvođač stalno proizvodi resurse, potrošač stalno troši resurse (detaljno će biti obrađeno kasnije, kliknite na link za direktan pristup). Resursi se čuvaju u baferu: proizvođač ubacuje proizvedene resurse u bafer, a potrošač uzima resurse iz bafera da bi ih potrošio — to je čuveni model proizvođač-potrošač.

Ovaj model može da pojednostavi proces razvoja: s jedne strane eliminiše zavisnost u kodu između klase proizvođača i klase potrošača, a sa druge strane raskida proces proizvodnje podataka od procesa korišćenja podataka, čime se pojednostavljuje opterećenje.

Kada sami kodiramo ovaj model, pošto je potrebno da više niti operiše nad deljenim promenljivama (odnosno resursima), lako može doći do pitanja bezbednosti niti, uzrokujući dvostruku potrošnju i mrtvu blokadu, posebno kada postoji više proizvođača i potrošača. Pored toga, kada je bafer prazan, potrebno je blokirati potrošača i probuditi proizvođača; kada je bafer pun, potrebno je blokirati proizvođača i probuditi potrošača. Sva ova čekanje-buđenje logika mora da se implementira ručno.

Naravno da nam JDK pomaže u ovako podložnoj greškama stvari — to je red blokiranja (BlockingQueue): samo ubacujete i izvlačite, bez brige o pitanjima bezbednosti niti pri ubacivanju i izvlačenju deljenih promenljivih u višenitnom okruženju.

BlockingQueue je važna struktura podataka u Java paketu java.util.concurrent. Za razliku od običnog reda, BlockingQueue pruža način pristupa redu bezbedan za niti, a implementacija mnogih naprednih klasa sinhronizacije u paketu za konkurentnost zasnovana je na BlockingQueue-u.

BlockingQueue se obično koristi u modelu proizvođač-potrošač: proizvođač je nit koja dodaje elemente u red, a potrošač je nit koja uzima elemente iz reda. BlockingQueue je kontejner za čuvanje elemenata.

Metode operacija BlockingQueue-a

Red blokiranja pruža četiri grupe različitih metoda za umetanje, uklanjanje i proveru elemenata:

Metod\način obrade	Baca izuzetak	Vraća specijalnu vrednost	Stalna blokada	Izlaz nakon isteka vremena
Metod umetanja	add(e)	offer(e)	put(e)	offer(e,time,unit)
Metod uklanjanja	remove()	poll()	take()	poll(time,unit)
Metod provere	element()	peek()	-	-

Baca izuzetak: ako operacija ne može da se izvrši odmah, baca izuzetak. Kada je red blokiranja pun, ubacivanje elementa u red će baciti izuzetak IllegalStateException("Queue full"). Kada je red prazan, uzimanje elementa iz reda će baciti izuzetak NoSuchElementException.
Vraća specijalnu vrednost: ako operacija ne može da se izvrši odmah, vraća specijalnu vrednost, obično true / false.
Stalna blokada: ako operacija ne može da se izvrši odmah, blokira se dok se ne izvrši ili dok ne odgovori na prekid.
Izlaz nakon isteka vremena: ako operacija ne može da se izvrši odmah, poziv metode će biti blokiran dok ne bude mogla da se izvrši, ali vreme čekanja neće preći zadatu vrednost. Vraća specifičnu vrednost kojom se saopštava da li je operacija uspela, obično true / false.

Napomena:

Ne može se ubaciti null u red blokiranja; biće bačena izuzetak praznog pokazivača.
Može se pristupiti bilo kom elementu u redu blokiranja; poziv remove(o) može ukloniti određeni objekat iz reda, ali to nije efikasno i treba ga izbegavati.

Kasnije ćemo otvoriti poseban članak o BlockingQueue za detaljnu obradu — kliknite na link za direktan pristup.

Klase implementacije BlockingQueue-a

ArrayBlockingQueue

Ograničeni red blokiranja sačinjen od strukture niza. Interna struktura je niz i ima osobine niza.

public ArrayBlockingQueue(int capacity, boolean fair){
 //..izostavljen kod
}

Može se inicijalizovati veličina reda, a jednom kada se inicijalizuje ne može se promeniti. Parametar fair u konstruktoru označava da li interna brava objekta kontrole koristi fer bravu; podrazumevano je nefer brava.

LinkedBlockingQueue

Ograničeni red blokiranja sačinjen od strukture povezane liste. Interna struktura je povezana lista i ima osobine povezane liste. Podrazumevana veličina reda je Integer.MAX_VALUE, ali može se zadati i veličina. Ovaj red sortira elemente po principu prvi-ušao-prvi-izašao.

DelayQueue

Elementi u ovom redu mogu se dobiti iz reda tek kada njihovo zadato vreme kašnjenja istekne. Elementi koji se ubacuju moraju implementirati interfejs java.util.concurrent.Delayed.

DelayQueue je red bez ograničenja veličine, pa operacija ubacivanja podataka u red (proizvođač) nikada neće biti blokirana, dok će samo operacija dobijanja podataka (potrošač) biti blokirana.

PriorityBlockingQueue

Neograničeni red blokiranja zasnovan na prioritetu (prioritet se određuje objektom Comparator prosleđenim konstruktoru), a brava koja kontroliše internu sinhronizaciju niti koristi nefer bravu.

Većina blogova na internetu navodi da je PriorityBlockingQueue fer brava, što zapravo nije tačno. Pregledom izvornog koda (hvala github korisniku ambition0802 na uočavanju):

public PriorityBlockingQueue(int initialCapacity,
                                 Comparator<? super E> comparator) {
    this.lock = new ReentrantLock(); //podrazumevani konstruktor - nefer brava
    ...//ostali kod izostavljen
}

SynchronousQueue

Ovaj red je prilično poseban — nema nikakav interni kapacitet, čak ni kapacitet jednog reda. Svaki put kada se uradi put, mora se sačekati take, i obrnuto.

Treba ga razlikovati od ArrayBlockingQueue i LinkedBlockingQueue sa kapacitetom 1.

Povratne vrednosti sledećih metoda mogu pomoći u razumevanju ovog reda:

iterator() uvek vraća prazno, jer unutra nema ničega.
peek() uvek vraća null.
put() nakon što se u red ubaci element, čeka se sve dok druga nit ne dođe i ne izuzme taj element.
offer() ubaci element u red i odmah se vraća; ako se desi da je taj element izuzeo druga nit, metoda offer vraća true i smatra se da je offer uspeo; inače vraća false.
take() izuzima i uklanja element iz reda; ako ne može ništa da izuzme, čekaće.
poll() izuzima i uklanja element iz reda; samo ako druga nit baš u tom trenutku ubacuje podatke u red offer metodom ili put metodom, ova metoda će moći da izuzme nešto. Inače odmah vraća null.
isEmpty() uvek vraća true.
remove()&removeAll() uvek vraćaju false.

Napomena

PriorityBlockingQueue ne blokira proizvođača podataka (jer je red neograničen), već blokira potrošača podataka samo kada nema podataka za potrošnju. Zato ga treba posebno pažljivo koristiti — brzina kojom proizvođač proizvodi podatke apsolutno ne sme biti veća od brzine kojom potrošač troši podatke, jer će vremenom to konačno iscrpiti sav dostupni prostor heap memorije. Isto važi i za LinkedBlockingQueue sa podrazumevanom veličinom.

CopyOnWrite kontejner

Pre nego što pričamo o CopyOnWrite kontejneru, hajde prvo da kažemo šta je CopyOnWrite mehanizam. CopyOnWrite je strategija optimizacije u oblasti dizajna računara, a i česta dizajnerska ideja u konkurentnim scenarijima — kopiranje pri pisanju.

Šta je kopiranje pri pisanju?

To je kada više pozivaoca istovremeno traži jedan resurs podataka, a jedan od pozivalaca iz nekog razloga želi da izmeni trenutni izvor podataka — tada sistem pravi kopiju trenutnog izvora podataka koja se daje pozivaocu na izmenu.

CopyOnWrite kontejner je kontejner koji kopira pri pisanju. Kada dodajemo element u kontejner, ne dodajemo direktno u kontejner, već vršimo kopiju trenutnog kontejnera, napravimo novi kontejner, zatim u novi kontejner dodamo potrebni element, i konačno referencu originalnog kontejnera preusmerimo na novi kontejner.

Prednost ovog pristupa je u tome što u konkurentnim scenarijima možemo vršiti „operaciju čitanja" nad kontejnerom bez „zaključavanja", čime se postiže cilj razdvajanja čitanja i pisanja. Počevši od JDK 1.5, Java paket za konkurentnost pruža dva konkurentna kontejnera implementirana CopyOnWrite mehanizmom: CopyOnWriteArrayList (detaljno će biti obrađen kasnije, kliknite na link za direktan pristup) i CopyOnWriteArraySet (ređe se koristi).

Rezime

Ovaj tekst je uglavnom predstavio tri važne klase kontejnera u paketu za konkurentnost: mapu, red blokiranja i CopyOnWrite kontejner. Mapa služi za čuvanje parova ključ-vrednost, red blokiranja za model proizvođač-potrošač, a CopyOnWrite kontejner za konkurentne scenarije sa „mnogo čitanja, malo pisanja".

Urednik: Chenmo Wang Er. Deo sadržaja potiče iz ovog repozitorijuma mog prijatelja Xiaoqi Yinghuochong-a: Java višenitnost jednostavno objašnjena. Preporučeno čitanje: Shiguang yibei ovaj članak o ConcurrentSkipListMap je vrlo dobar, vredi naučiti.