Preskoči na glavni sadržaj

Savladajte Java CopyOnWriteArrayList za intervju

Chenmo Wang ErJava jezgroJava konkurentno programiranje1364 reči5 minuta

Čitaoci koji su učili o ArrayList-i sigurno se sećaju da je ArrayList kontejner koji nije bezbedan za niti; u višenitnom okruženju ga je potrebno ručno zaključati, ili koristiti metod Collections.synchronizedList() da se pretvori u bezbedan za niti kontejner.

U suprotnom će se pojaviti izuzetak ConcurrentModificationException.

Zato nam je majstor Doug Lea pružio konkurentnu verziju ArrayList-e — CopyOnWriteArrayList.

CopyOnWriteArrayList je bezbedan za niti i može se koristiti u višenitnom okruženju. CopyOnWriteArrayList sledi princip pisanja uz kopiranje: svaki put kada se lista modifikuje (na primer dodavanje, brisanje ili izmena elementa), kreira se nova kopija liste; ta nova kopija zamenjuje staru listu, dok sve operacije čitanja na staroj listi i dalje mogu da se nastave.

Pošto se pri izmeni kreira nova kopija, operacije čitanja ne zahtevaju zaključavanje. To čini operacije čitanja veoma efikasnim u scenarijima sa mnogo čitalaca i malo pisaca. Naravno, pošto svaka operacija pisanja kreira novu kopiju niza, povećava se memorijski i vremenski trošak. Ako su operacije pisanja veoma učestale, performanse će patiti.

Šta je CopyOnWrite

Sigurno se sećate brava za čitanje i pisanje ReentrantReadWriteLock? Brava za čitanje i pisanje se ostvaruje kroz ideju razdvajanja čitanja i pisanja, odnosno brave za čitanje i brave za pisanje su odvojene, čime se omogućava konkurentno izvršenje operacija čitanja i pisanja.

Međutim, brava za čitanje i pisanje ima i nekih problema — na primer, kada se acquire-uje brava za pisanje, niti čitači će biti blokirane dok se brava za pisanje ne oslobodi; tek tada niti čitači imaju priliku da acquire-uju bravu i pročitaju najnovije podatke. Iz ugla niti čitača, nit čitalac u svakom trenutku može dobiti najnovije podatke, što zadovoljava zahtev realnovremenosti podataka.

CopyOnWriteArrayList pak, kroz ideju Copy-On-Write (COW), odnosno pisanja uz kopiranje, koristi strategiju odloženog ažuriranja da ostvari konačnu konzistentnost podataka, i pri tome garantuje da se niti čitači međusobno ne blokiraju. Naravno, to zahteva žrtvovanje realnovremenosti podataka.

Prosto rečeno, CopyOnWrite znači da kada u kontejner dodajemo element, ne dodajemo ga direktno u kontejner, već prvo iskopiramo novi kontejner, zatim u taj novi kontejner dodamo element, a nakon toga referencu originalnog kontejnera preusmerimo na novi kontejner. Kada više niti čita, ne moraju se zaključavati, jer se u tekući kontejner neće dodati nijedan element.

Već smo pomenuli ovo kada smo predstavljali konkurentne kontejnere, pa se nadamo da vam je ostalo u sećanju.

Princip rada CopyOnWriteArrayList

Hajde da pogledamo izvorni kod CopyOnWriteArrayList. Kao što ime sugeriše, CopyOnWriteArrayList interno održava jedan niz:

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

Ovaj niz je obeležen sa volatile, što garantuje vidljivost podataka u memoriji.

get metod

Izvorni kod get metoda:

public E get(int index) {
    return get(getArray(), index);
}
/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

Implementacija get metoda je veoma jednostavna, gotovo „jednonitna“ — bez ikakve kontrole bezbednosti niti, bez zaključavanja i bez CAS operacija. Razlog je taj što sve niti čitači samo čitaju podatke iz kontejnera, bez da ih menjaju.

add metod

Izvorni kod add metoda:

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
	  //1. Koristi Lock da osigura da u istom trenutku samo jedna nit piše
    lock.lock();

    try {
				//2. Preuzima referencu na stari niz
        Object[] elements = getArray();
        int len = elements.length;

				//3. Kreira novi niz i kopira podatke iz starog niza u novi
        Object[] newElements = Arrays.copyOf(elements, len + 1);

				//4. Dodaje nove podatke u novi niz
				newElements[len] = e;

				//5. Preusmerava referencu starog niza na novi niz
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

Logika add metoda je prilično lako razumeti; treba obratiti pažnju na sledeće:

  1. Koristi se ReentrantLock da osigura da u istom trenutku samo jedna nit koja piše vrši kopiranje niza;

  2. Pozivom metoda getArray() preuzima se stari niz.

final Object[] getArray() {
    return array;
}
  1. Zatim se kreira novi niz, u njega se kopira stari niz, zatim se u novi niz dodaju podaci, a zatim se novi niz dodeljuje referenci starog niza.
final void setArray(Object[] a) {
    array = a;
}

Prema happens-before pravilu za volatile, ova izmena je svim nitima odmah vidljiva.

  1. Na kraju, u finally bloku se oslobađa brava kako bi druge niti mogle pristupati listi i menjati je.

Korišćenje CopyOnWriteArrayList

Korišćenje CopyOnWriteArrayList je veoma jednostavno i skoro identično korišćenju ArrayList-e — jedino pri kreiranju objekta treba koristiti konstruktor CopyOnWriteArrayList, kao u primeru:

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("element1");
list.add("element2");

for (String element : list) {
    System.out.println(element);
}

Mane CopyOnWriteArrayList

CopyOnWrite kontejner ima mnogo prednosti, ali sa sobom nosi i dva problema: problem zauzeća memorije i problem konzistentnosti podataka. Zato pri razvoju treba obratiti posebnu pažnju.

  1. Problem zauzeća memorije: zbog mehanizma pisanja uz kopiranje, tokom operacije pisanja u memoriji istovremeno postoje dva objekta — stari i novoupisani, što smo videli u analizi add metoda.

Ako ti objekti zauzimaju prilično memorije, na primer oko 200 MB, onda upisivanje dodatnih 100 MB podataka znači da će memorija zauzeti 600 MB, što dovodi do učestalog minor GC i major GC.

  1. Problem konzistentnosti podataka: CopyOnWrite kontejner može da garantuje samo konačnu konzistentnost podataka, a ne i realnovremensku konzistentnost. Dakle, ako želite da podatak koji upišete odmah pročitate, nemojte koristiti CopyOnWrite kontejner — bolje je da preko ReentrantReadWriteLock napravite sopstvenu listu.

Hajde da uporedimo CopyOnWrite i bravu za čitanje/pisanje.

Zajedničke tačke:

  1. Oboma se ideja ostvaruje kroz razdvajanje čitanja i pisanja;
  2. Niti čitači se međusobno ne blokiraju.

Razlike:

Da bi se ostvarila realnovremenost podataka, kada se acquire-uje brava za pisanje, niti čitači se blokiraju; ili kada se acquire-uje brava za čitanje, niti pisci se blokiraju, čime se rešava problem „prljavog čitanja“. CopyOnWrite pak ažurira podatke pisanjem uz kopiranje, pa su niti čitači usporeno svesni promena, ali bez blokiranja.

Ovo je iz teksta možda teže razumeti, pa hajde da pogledamo kroz debug. Ključni kod add metoda je:

1.Object[] elements = getArray();
2.int len = elements.length;
3.Object[] newElements = Arrays.copyOf(elements, len + 1);
4.newElements[len] = e;
5.setArray(newElements);

Zamislimo da promena u COW izgleda kao na slici ispod:

Analiza konačne konzistentnosti
Analiza konačne konzistentnosti

Niz već sadrži podatke 1, 2, 3, a sada nit koja piše želi da doda podatak 4; postavimo breakpoint na redu 5 i pauzirajmo nit koja piše.

U tom trenutku, nit koja čita i dalje „neometano“ čita iz niza, ali još uvek može pročitati samo 1, 2, 3.

Ako nit koja čita može odmah pročitati novododatni podatak, to je realnovremena konzistentnost. Kada se breakpoint na redu 5 oslobodi, nit koja čita postaje svesna promene i čita kompletne podatke 1, 2, 3, 4 — to je konačna konzistentnost, iako je možda prošlo nekoliko sekundi dok je postala svesna.

Kratak pregled

CopyOnWriteArrayList je bezbedna za niti varijanta, konkurentna verzija Java klase ArrayList. Bezbednost niti ove klase se ostvaruje jednostavnom ali moćnom idejom: svaki put kada se lista menja, kreira se nova kopija te liste.

CopyOnWriteArrayList je pogodan za scenarije u kojima operacija čitanja daleko premašuje operacije pisanja, na primer keš. Pošto CopyOnWriteArrayList usvaja ideju pisanja uz kopiranje, performanse operacija pisanja su niže, pa nije pogodan za scenarije sa učestalim pisanjem.

CopyOnWriteArrayList ima i nekih mana, poput problema sa zauzećem memorije i konzistentnošću podataka, pa pri razvoju treba obratiti posebnu pažnju.

Autor: Chenmo Wang Er. Deo sadržaja potiče iz GitHub repozitorijuma CL0610 https://github.com/CL0610/Java-concurrency.