AngelikaLanger.com - CopyOnWriteArrayList - Angelika Langer Training/Consulting (original) (raw)

CopyOnWriteArrayList

Java Memory Model CopyOnWriteArrayList Java Magazin, Dezember 2009 Klaus Kreft & Angelika Langer	Dies ist das Manuskript eines Artikels, der im Rahmen einer Kolumne mit dem Titel "Effective Java" im Java Magazin erschienen ist. Die übrigen Artikel dieser Serie sind ebenfalls verfügbar (click here). Die ganze Serie zum "Java Memory Modell" als PDF(985 KB).

In diesem Beitrag wollen wir die CopyOnWriteArrayList aus dem JDK hernehmen und an ihrem Beispiel das Zusammenspiel der Speichereffekte von Synchronisation, volatile, und atomaren Referenzen noch einmal abschließend erläutern.

In unserer Serie über das Java Memory Modells haben wir eine Reihe von Aspekten angeschaut, mit denen sich die Verwendung von Synchronisation reduzieren läßt. Dabei soll mit der Vermeidung der Synchronisation in der Regel die Performance der betroffenen Abstraktion verbessert und der Durchsatz erhöht werden, weil ohne Synchronisation mehrere Threads ungehindert parallel arbeiten können, ohne aufeinander warten zu müssen. Wir haben die Effekte von final-, volatile- und atomaren Variablen betrachtet und an kleineren Beispielen demonstriert. Dieses Mal wollen wir zeigen, wie diese Sprachmittel in einer realistischen Abstraktion in der Praxis genutzt werden. Dazu wollen wir uns die Implementierung der CopyOnWriteArrayList aus dem JDK-Package java.util.concurrent genauer ansehen, weil sie ein geschicktes Zusammenspiel von volatile und Synchronisation zeigt.

Was ist eine CopyOnWriteArrayList?

Die CopyOnWriteArrayList ist eine thread-sichere Implementierung einer Liste, die man - ähnlich wie eine synchonisierte Liste - mehreren Thread zum gemeinsamen, konkurrierenden Zugriff zur Verfügung stellen kann. Während die synchronisierte Liste, die man über Collections.synchronizedList() bekommt, alle Zugriffsmethoden per Synchronisation auf dem Mutex des Listenobjekts schützt, ist die CopyOnWriteArrayList dahingehend optimiert, dass sie einen schnelleren Lesezugriff bietet, der ganz ohne Synchronisation auskommt. Im Gegenzug sind die modifizierenden Methoden relativ teuer, weil sie die Modifikation auf einer Kopie des unterliegenden Arrays ausführen und anschließend das alte gegen das neue modifizierte Array austauschen. Man bezahlt also die schnellen Lesezugriffe durch das relativ teure Kopieren bei den Schreibzugriffen. Wenn Modifikationen an der Liste selten und Lesezugriffe wesentlich häufiger vorkommen, dann ist die CopyOnWriteArrayList performanter als die normale synchronisierte Liste.

Wie funktioniert eine CopyOnWriteArrayList?

Die CopyOnWriteArrayList besteht aus einem Array, in dem die Referenzen auf die Elemente der Liste abgelegt sind. Die wesentliche Idee bei der CopyOnWriteArrayList ist, dass dieses Array unveränderlich ist. Es wird von keiner Methode der CopyOnWriteArrayList modifiziert und deshalb können alle lesenden Zugriffe ohne Synchronisation erfolgen. Hier ist ein Ausschnitt aus der Implementierung, der zunächst einmal nur eine lesende Methode, nämlich die get()-Methode, und die relevanten Felder der CopyOnWriteArrayList zeigt:

public class CopyOnWriteArrayList implements List {

private volatile transient Object[] array;

private final Object[] getArray() {
return array;
}

public E get(int index) {
return (E)(getArray()[index]);
}
}

Man sieht, dass die Referenz auf das Array volatile ist und dass die get()-Methode über diese Referenz auf das benötigte Array-Element zugreift. Man sieht außerdem, dass die get()-Methode nicht synchronisiert ist. Sie kann also gleichzeitig mit anderen lesenden oder modifizierenden Methoden auf das Array der CopyOnWriteArrayList zugreifen. Warum das keine Race Conditions ergibt, nicht einmal wenn die get()-Methode gleichzeitig mit einer modifizierenden Methode wie set() abläuft, sehen wir uns später im Zusammenhang mit der set()-Methode an.

Das Fehlen jeglicher Synchronisation bedeutet, dass wir in der get()-Methode einen unsynchronisierten Zugriff auf die Array-Referenz haben. Bei unsynchronisierten Zugriffen stellt sich stets die Frage nach der Sichtbarkeit von Modifikationen, die ein anderer Thread gemacht hat. Kann die get()-Methode alle Modifikationen am Array sehen, die beispielsweise eine set()-Methode zuvor in einem anderen Thread ausgelöst hat?

Die Referenz auf das Array der CopyOnWriteArrayList ist als volatile deklariert und die get()-Methode greift lesend auf die Referenz zu (über die Hilfs-Methode getArray()). Weil die Array-Referenz volatile ist, ist garantiert, dass die get()-Methode alle Modifikationen sehen kann, die ein anderer Thread vor einem schreibenden Zugriff auf die Array-Referenz gemacht hat. Sehen wir uns also eine modifizierende Methode näher an. Hier ist ein größerer Ausschnitt aus der Implementierung, der zusätzlich zur get()-Methode auch die set()-Methode zeigt:

public class CopyOnWriteArrayList implements List {

/** The lock protecting all mutators */
transient final ReentrantLock lock = new ReentrantLock();

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

private final Object[] getArray() {
return array;
}

private final void setArray(Object[] a) {
array = a;
}

public E get(int index) {
return (E)(getArray()[index]);
}

public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
Object oldValue = elements[index];

if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf (elements, len); // 1
newElements[index] = element; // 2
setArray(newElements); // 3
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements); // 3
}
return (E)oldValue;
} finally {
lock.unlock();
}
}
}

Sehen wir uns als erstes einmal die Funktionalität der set()-Methode an. Sie kopiert das Array (siehe Zeile //1), modifiziert die Kopie (siehe //2) und legt am Ende die Adresse der Kopie in der volatile Referenzvariablen array ab (siehe //3). Dieser schreibende Zugriff (über die Methode setArray()) auf die volatile Referenz löst eine Memory Barrier aus, bei der alle Modifikationen, die in der set()-Methode bis dahin vorgenommen wurden, im Hauptspeicher sichtbar gemacht werden für Methoden die später lesend auf die volatile Referenzvariable array zugreifen. Hierbei ist wichtig, dass der schreibende Zugriff auf die volatile Array-Referenz erst ganz am Ende nach der Modifikation des kopierten Arrays erfolgt, sonst wäre nicht gewährleistet, dass neben der Array-Adresse auch die Array-Elemente für die anderen Threads sichtbar werden.

Man kann nun auch sehen, warum der konkurriende unsynchronisierte Ablauf von set()- und get()-Methode keine Race Condition ist. Das Array, das die get()-Methode liest, wird von der set()-Methode nicht verändert, denn sie verändert nur eine lokale Kopie des Arrays. Die einzige Modifikation, die die set()-Methode an den Feldern der CopyOnWriteArrayList vornimmt, ist die Zuweisung der Adresse des neu erstellten Arrays an die Referenzvariable array (siehe //3). Diese Adresszuweisung ist atomar, also unkritisch, weil sie ununterbrechbar ist. Die get()-Methode erwischt also die Adresse des unveränderten Arrays vor dem Aufruf von setArray() oder die Adresse der modifizierten Kopie nach dem Aufruf von setArray(). Auf irgendwelche inkonsistenten Zwischenzustände des Arrays hat die get()-Methode keinen Zugriff.

Der konkurrierende Ablauf von zwei set()-Methode wäre hingegen sehr wohl eine Race Condition. Wenn sich beide set()-Methoden die Adresse des Arrays holen, beide eine lokale Kopie anlegen und ihre jeweilige Modifikation an der lokalen Kopie machen, dann wird die eine set()-Methode die Modifikation der anderen set()-Methode überschreiben, wenn sie die Referenzvariable array überschreibt. Nach einem unsynchronisierten Ablauf beider set()-Methoden bliebe nur eine der beiden Modifikationen übrig; wir hätte also ein Lost-Update-Problem. Die modifizierenden Methoden der CopyOnWriteArrayList sind deshalb alle gegeneinander synchronisiert. Dazu wird ein explizites Lock verwendet.

Die übrigen lesenden und modifizierenden Methoden der CopyOnWriteArrayList sehen analog aus. Interessant ist noch der Iterator. Die Beschreibung sagt, der Iterator iteriert über die Liste, so wie im Augenblick der Konstruktion des Iterators ausgesehen hat. Deshalb ist von einem Snapshot die Rede. Was hat es mit dem Snapshot auf sich?

Wie funktioniert der Iterator der CopyOnWriteArrayList

Der Iterator der CopyOnWriteArrayList ist ein reiner Lese-Iterator. Modifikationen läßt er nicht zu; modifizierende Iterator-Methoden wie remove() werfen immer eine UnsupportedOperationException. Sämtliche Methoden des Iterators sind unsynchronisiert, das heißt, der Iterator iteriert konkurrierend mit lesenden und schreibenden Methoden und anderen Iteratoren. Er ist - anders als der Iterator einer synchronisierten Liste - kein Fast-Fail-Iterator und wirft keine ConcurrentModificationException, wenn während der Iteratierung Modifikationen an der Liste vorgenommen werden.

Hier ist ein Auszug aus der Implementierung des Iterators der CopyOnWriteArrayList:

public class CopyOnWriteArrayList

private volatile transient Object[] array;

private final Object[] getArray() {
return array;
}
public Iterator iterator() {
return new COWIterator(getArray(), 0);
}

private static class COWIterator implements ListIterator {
/* Snapshot of the array **/
private final Object[] snapshot;
/* Index of element to be returned by subsequent call to next.*/
private int cursor;

private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}

public boolean hasNext() {
return cursor < snapshot.length;
}

public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}

/* Not supported. Always throws UnsupportedOperationException. */
public void remove() {
throw new UnsupportedOperationException();
}
...
}
...
}

Der Iterator enthält zwei Felder: die Referenz auf das Array der CopyOnWriteArrayList und einen Index, der seine Anfangsposition repräsentiert. Beide Felder werden bei der Konstruktion des Iterators initialisiert. Das heißt, der Iterator iteriert über das Array, das zum Zeitpunkt der Konstruktion des Iterators gerade aktuell war. Solange die CopyOnWriteArrayList nicht modifiziert wird, ist klar, dass die unsynchronisierte Iterierung kein Problem ist und keine Race Condition produziert. Wie ist das aber, wenn die CopyOnWriteArrayList modifiziert wird, beispielsweise mit der set()-Methode?

Wie wir schon gesehen haben, legt die set()-Methode eine Kopie des Arrays an, modifiziert die Kopie und überschreibt dann die Array-Referenz in der CopyOnWriteArrayList mit der Adresse der Kopie. Der Iterator bekommt davon nichts mit. Er wird weiterhin auf dem alten Array iterieren. In diesem Sinne arbeitet der Iterator der CopyOnWriteArrayList auf einem Snapshot und dieser Snapshot ist, nachdem eine Änderung an der Liste vorgenommen wurde, eine "alte" Kopie der Liste.

Weil das Array der CopyOnWriteArrayList nie verändert wird, wird im Iterator keine Synchronisation gebraucht. Auch der konkurrierende Ablauf einer Iteration und einer Modifikation der Liste ist kein Problem. Auf diese Weise hat die CopyOnWriteArrayList einen höchst effizienten Iterator, der ein Maximum an konkurrierenden Zugriffen auf die Liste zuläßt.

Allerdings hat der Iterator der CopyOnWriteArrayList eine andere Semantik als der Fast-Fail-Iterator einer synchronisierten Liste. Er zeigt unter Umständen einen alten Stand (stale value) der Liste - eine Situation, die beim Iterieren über eine synchronisierte Liste nicht auftreten kann. Bei der synchronisierten Liste ist die konkurrierende Modifikation ein Fehler, der sich in der ConcurrentModificationException des Iterators ausdrückt. Bei der CopyOnWriteArrayList ist die konkurrierende Modifikation hingegen ein Feature.

Eine andere Anwendung desselben Prinzips

Die grundlegende Idee der Implementierung der CopyOnWriteArrayList besteht darin, dass sich das Array selbst nie ändert; es wird lediglich bei Bedarf durch ein neues ersetzt. Betrachten wir zur Illustration dieses Prinzip ein weiteres Beispiel: ein Interval. Hier ein Auszug aus einer denkbaren Implementierung, die aber nicht thread-safe ist:

public class Interval { // Vorsicht: nicht thread-safe !!!
// INVARIANT: lower <= upper
private volatile int lower = 0
private volatile int upper = 0;

public void setLower(int i) {
if (i > upper.)
throw new IllegalArgumentException(
"can't set lower to " + i + " > upper");
lower = i;
}

public int getLower() {
return lower;
}

public boolean isInRange(int i) {
return (i >= lower && i <= upper);
}
…
}

Diese Implementierung ist nicht thread-safe, weil die beiden Felder lower und upper eine Invariante bilden: lower muss immer kleiner als upper sein. Für den Erhalt der Invariante ist es erforderlich, dass Read-Check-Modify-Sequenzen wie in der setLower()-Methode ununterbrechbar sind: erst wird der aktuelle Wert von upper gelesen, dann wird er mit dem neuen Wert von lower verglichen, und nur wenn alles in Ordnung ist, wird der neue Wert für lower gesetzt. Wenn diese Sequenz unterbrochen würde, könnten sinnlose Intervalle entstehen, bei denen die Untergrenze größer als die Obergrenze ist.

Um diese Interval-Klasse thread-safe zu machen, kann man dasselbe Prinzip anwenden, das auch in der CopyOnWriteArrayList verwendet wird: man sorgt dafür, dass die eigentlichen Daten des Intervals (also das Paar von Unter- und Obergrenze) unveränderlich sind und lediglich bei Bedarf neue Daten erzeugt und gegen die alten ausgetauscht werden.

Hier ist eine korrigierte Fassung:

@ThreadSafe
public class Interval {

@Immutable
private static class IntPair {
private final int lower;
private final int upper;
public IntPair(int l, int u) {
lower =l;
upper =u;
}
}

private final AtomicReference values =
new AtomicReference(new IntPair(0, 0));

public void setLower(int i) {
while (true) {
IntPair oldv = values.get();
if (i > oldv.upper)
throw new IllegalArgumentException(
"Can't set lower to " + i + " > upper");
IntPair newv = new IntPair(i, oldv.upper);
if (values.compareAndSet(oldv, newv))
return;
}
}

public int getLower() {
return values.get().lower;
}

public boolean isInRange(int i) {
IntPair v = values.get();
return (i >= v.lower && i <= v.upper);
}

…
}

Das Paar von Unter- und Obergrenze wird nie verändert. Wenn das Interval geändert werden soll, wie etwa in der setLower()-Methode, dann wird ein neues Paar erzeugt und gegen das alte ausgetauscht. Dazu genügt es aber nicht, lediglich die Referenz auf das Paar auszutauschen, sondern wir brauchen wegen der Invarianten noch immer die ununterbrechbare Read-Check-Modify-Sequenz - ähnlich wie man in der set()-Methode der CopyOnWriteArrayList eine ununterbrechbare Read-Calculate-Modify-Sequenz brauchte. Das könnte man wie in der CopyOnWriteArrayList mit Synchronisation erreichen, aber um eine effizientere Lösung zu bekommen, verwenden wir eine AtomicReference, die eine ununterbrechbare CAS (= compare-and-swap) Methode hat.

Das Verhalten ist bei dieser Lösung ähnlich wie bei der CopyOnWriteArrayList: konkurreirende Lesezugriffe sind sowieso kein Problem; Modifikationen, die konkurrierend zu lesenden Zugriffen passieren, sind auch kein Problem. Der Leser sieht stets ein gültiges Interval, das zu irgendeinem Zeitpunkt einmal existiert hat (und niemals ein fehlerhaftes, bei dem die Untergrenze größer als die Obergrenze ist); schlimmstenfalls sieht er einen älteren Zustand des Intervals (vor der letzten aktuellen Änderung). Sogar konkurrierende Schreibzugriffe kommen wegen der AtomicReference ohne Synchronisation aus; schlimmstenfalls muss ein Thread seinen Modifikationsversuch mehrmals wiederholen.

Zusammenfassung

Die Implementierung der CopyOnWriteArrayList illustriert, wie man den Bedarf an Synchronisatoin senken und die Zahl der konkurrierenden Zugriffe auf eine Abstraktion erhöhen kann. Wir haben dasselbe Prinzip auch noch am Beispiel einer Interval-Klasse gezeigt. Das Idiom hat folgende Elemente:

• Die Implementierung der Abstraktion hält lediglich eine Referenz auf alle Daten der Abstraktion und diese Daten sind unveränderlich; lediglich die Referenz kann sich ändern. Die Referenz ist wegen der Sichtbarkeitsanforderungen entweder volatile oder atomar.
• Alle Modifikationen werden auf einer Kopie der aktuellen Daten gemacht und am Ende wird die Referenz auf die alten Daten gegen eine Referenz auf die neuen Daten ausgetauscht. Weil die eigentlichen Daten der Abstraktion unveränderlich sind, können lesende Zugriffe miteinander und mit den modifizierenden Zugriffen zusammen parallel ohne Synchronisation ablaufen. Diesen Gewinn an Parallelität bezahlt man mit den Kosten für das Kopieren. Das Idiom lohnt sich also in erster Linie bei Abstraktionen, die wesentlich häufiger gelesen als modifiziert werden.
• Für die Modifikationen ist es erforderlich, dass eine Sequenz von "Lesen der aktuellen Daten" - "Bewerten der gelesenen Daten (Vergleich, Berechnung, etc.) - "Verändern der Daten" ununterbrechbar abläuft. Die Atomarität kann entweder per Synchronisation erreicht werden, wie bei der CopyOnWriteArrayList, oder mit Hilfe einer atomaren Referenz, wie im Interval-Beispiel. Damit haben wir an einem realen Beispiel aus dem JDK gesehen, wie die Elemente des Java Memory Modells in der Praxis verwendet werden können.

Literaturverweise

Die gesamte Serie über das Java Memory Model:

If you are interested to hear more about this and related topics you might want to check out the following seminar:
Seminar Concurrent Java - An in-depth seminar covering all that is worth knowing about concurrent programming in Java, from basics such as synchronization over the Java 5.0 concurrency utilities to the intricacies of the Java Memory Model (JMM). 4 day seminar (open enrollment and on-site)