Kolumne

Nebenläufig – und auch schnell? Concurrency mit und ohne Locks [Java-Trickkiste]

Arno Haase

© Shutterstock/cherezoff

Moderne Systeme arbeiten eigentlich immer mit mehreren Threads. Und manchmal muss man sich trotz Frameworkunterstützung selber darum kümmern, wie mehrere Threads auf dieselben Daten zugreifen.

In einem meiner Projekte wollten wir Kennzahlen sammeln und aggregiert zur Auswertung bereitstellen. Stark vereinfacht gab es eine Klasse, bei der Anwendungscode Messwerte registrieren konnte und die Klasse sich intern die Zahl der Messwerte sowie ihre Summe gemerkt hat. Listing 1 zeigt eine einfache Implementierung.

class CountAndSumSync {
  private int count = 1;
  private int sum;

  public CountAndSumSync(int initialValue) {
    sum = initialValue;
  }

  public synchronized void add(int value) {
    count += 1;
    sum += value;
  }

  public synchronized double getAverage() {
    if(count == 0) return 0;
    return 1.0 * sum / count;
  }
}

Viele verschiedene Threads greifen gleichzeitig darauf zu, und deshalb sind alle Methoden synchronized. Es gibt eine ganze Reihe dieser Datentöpfe, die in einer Map abgelegt sind (Listing 2). Verschiedene Threads können parallel neue Datentöpfe anlegen, weshalb eine ConcurrentHashMap zum Einsatz kommt.

final Map<Integer, CountAndSumSync> mapSync = 
    new ConcurrentHashMap<>();

void updateSynchronized (Integer key, int value) {
  if(mapSync.containsKey(key)) {
    mapSync.get(key).add(value);
  }
  else {
    mapSync.put(key, new CountAndSumSync(value));
  }
}

Beim Hinzufügen eines neuen Wertes gibt es zwei Fälle. Entweder ist für den Schlüssel schon ein Eintrag hinterlegt, dann wird der Wert dort hinzugefügt. Oder es ist der erste Wert für diesen Schlüssel, dann wird ein neues CountAndSumSync-Objekt erzeugt und in die Map gelegt. Wenn zwei Threads „gleichzeitig“ einen ersten Wert für einen neuen Key anlegen, wird eventuell einer von ihnen verworfen. Diese Unschärfe ist in unserem Beispiel aber akzeptabel.

Performancemessungen

Das Erfassen der Kennzahlen soll die eigentliche Anwendung natürlich möglichst wenig bremsen. Messen wir also, wie viel Zeit unsere Implementierung frisst. Dazu lassen wir mehrere Threads parallel Werte ändern und auslesen (Listing 3). Das Auslesen ist dabei wichtig, weil Lese- und Schreibzugriffe miteinander kollidieren können.

final int NUM_THREADS = 10;
final int NUM_KEYS = 10;

final CountDownLatch latch = new CountDownLatch(NUM_THREADS);

for(int i=0; i<NUM_THREADS; i++) {
  new Thread(latch) {
    final Random rand = new Random();

    public void run() {
      for(int i=0; i<1_000_000; i++) {
        try {
          for(int j=0; j<10; j++) {
            mapSync.get(rand.nextInt(NUM_KEYS)).getAverage();
          }
        } 
        catch (NullPointerException e) {}
        updateSynchronized(rand.nextInt(NUM_KEYS), i);
      }
      latch.countDown();
    }
  }.start();
}

long start = System.nanoTime();
latch.await();
System.out.println((System.nanoTime() - start) + "ns");

Die Anzahl der gleichzeitig gestarteten Threads steuert dabei den Grad der Kollisionen – je mehr Threads versuchen, auf dieselben Ressourcen zuzugreifen, desto wahrscheinlicher kommen sie sich dabei in die Quere. Jeder Thread liest und aktualisiert in einer Schleife Kennzahlen. Dabei führt er zehnmal so viele Lesezugriffe wie Schreibzugriffe aus. Dieses Zahlenverhältnis entspricht in etwa der Situation im tatsächlichen System. Die Schlüssel für alle Zugriffe werden dabei zufällig aus einem vorgegebenen Wertebereich gewählt. Die Gesamtzahl der Schlüssel beeinflusst dabei stark die Häufigkeit von Kollisionen. Jeder Schlüssel hat ja sein eigenes CoutAndSumSync-Objekt und damit sein eigenes Lock, auf das synchronisiert wird.
Wenn es z. B. nur zwei Schlüssel gibt, versuchen sehr häufig mehrere Threads, dasselbe Lock zu bekommen, und müssen aufeinander warten. Wenn es dagegen 1 000 verschiedene Schlüssel gibt, bekommen Threads sehr wahrscheinlich die angefragten Locks, ohne warten zu müssen. Die Ausführung mit 10 Threads und 10 Keys dauert auf meinem Laptop etwa 3,5 Sekunden. Wenn dieselben 10 Threads sich um fünf Keys streiten, dauert die Ausführung 6,2 Sekunden und bei zwei Keys steigt sie sogar auf 15 Sekunden. Diese Zahlen wurden mit einem etwas aufwändigeren Test-Set-up ermittelt, das insbesondere HotSpot vor den eigentlichen Messungen „aufwärmt“. Unsere Lock-basierte Implementierung skaliert jedenfalls nicht gut bei stark konkurrierendem Zugriff.

Aufmacherbild: Futuristic integrated circuit, code lock and globe. The concept of electronic security von Shutterstock / Urheberrecht: cherezoff

[ header = Seite 2: Lock-freie Implementierung ]

Lock-freie Implementierung

Man kann die gleiche Funktionalität aber auch ohne Locks implementieren, ohne die Konsistenz der Daten zu gefährden. Solche Lock-freien Algorithmen glänzen allgemein bei starker Nebenläufigkeit, besonders wenn Lesezugriffe häufiger sind als Schreibzugriffe.

class CountAndSumFinal {
  private final int count;
  private final int sum;

  CountAndSumFinal(int count, int sum) {
    this.count = count;
    this.sum = sum;
  }

  CountAndSumFinal withNewValue(int value) {
    return new CountAndSumFinal(count + 1, sum + value);
  }

  double getAverage() {
    if(count == 0) return 0;
    return 1.0 * sum / count;
  }
}

Die neue Klasse zur Datenhaltung ist komplett immutable (Listing 4). Wenn ein Wert hinzukommt, erzeugt sie eine neue Instanz mit den neuen Werten. Dadurch ist jede Instanz automatisch zu jedem Zeitpunkt konsistent, ohne dass man dafür Locks bräuchte. Lesezugriffe brauchen also keinen Overhead für Nebenläufigkeit. Das erfordert natürlich andere Zugriffsmuster (Listing 5). Die Map speichert jetzt für jeden Schlüssel eine AtomicReference auf das jeweilige CountAndSumFinal-Objekt.

final Map<Integer, AtomicReference<CountAndSumFinal>> mapRef = 
    new ConcurrentHashMap<>();

void updateLockFree(Integer key, int value) {
  if(mapRef.containsKey(key)) {
    final AtomicReference<CountAndSumFinal> ref = mapRef.get(key);
    CountAndSumFinal prev;
    do {
      prev = ref.get();
    }
    while(! ref.compareAndSet(prev, prev.withNewValue(value)));
  }
  else {
    mapRef.put(key, new AtomicReference<>(new CountAndSumFinal(1, value)));
  }
}

Ein Update merkt sich die aktuelle CountAndSumFinal-Referenz und erzeugt eine aktualisierte Instanz. Dann ruft sie AtomicReference.compareAndSet auf und übergibt dabei sowohl die alte als auch die neue Referenz.  Diese Methode aktualisiert den Wert nur dann, wenn niemand sonst ihn in der Zwischenzeit geändert hat. Bei Erfolg liefert sie true zurück, und wir sind fertig. Wenn jemand anderes schneller war, wiederholen wir das Ganze so lange, bis es klappt. Moderne Prozessoren haben für solche atomaren, Thread-sicheren CAS-Operationen eigene Befehle (z. B.). Auf diese Weise kommt auch ein Update ohne Lock aus. Dafür gibt es jetzt eine Schleife, die bei extrem konkurrierenden Schreibzugriffen mit teurer Updatelogik die Vorteile mehr als auffressen kann (siehe z. B. [5]). Tabelle 1 vergleicht für verschiedene Szenarien die Performance der beiden Implementierungen.

Threads Keys Dauer Synchronized Dauer Lock-frei
10 10 3,5s 2s
10 5 6s 2s
10 2 15s 2s
30 10 10,5s 6s
30 2 46s 6s
100 10 34s 16s
100 2 161s 16s

Tabelle 1: Performance der Implementierungen

Die Lock-freie Implementierung ist bei jedem Lastszenario eine Nasenlänge schneller als die Lock-basierte. Je weniger Keys es gibt, desto stärker ist dieser Effekt. Die Threadzahl hat dagegen praktisch keinen Einfluss – einfach weil die Prozessoren voll ausgelastet sind und mehr Threads deshalb kaum tatsächliche zusätzliche Concurrency mit sich bringen.

Fazit

Eine naive threadsichere Implementierung mit synchronized funktioniert, es gibt aber oft effizientere Alternativen. Lock-freie Algorithmen sind oft extrem effizient, aber komplexer zu schreiben und zu warten. Alternativ gibt es speziellere Lock-Implementierungen wie ReentrantReadWriteLock oder StampedLock (neu in Java 8). Was sollte man also wählen? Das hängt vom konkreten Lastszenario ab. Und erst wenn man konkrete Messergebnisse für die verschiedenen Alternativen hat, kann man sie seriös vergleichen. Für die eingangs erwähnte Kennzahlen-Aggregierung haben wir uns jedenfalls für eine einfache Implementierung auf Basis von synchronized entschieden – einfach weil dort der Synchronisierungs-Overhead verglichen mit der Gesamtlast der Anwendung vernachlässigbar war.

Geschrieben von
Arno Haase
Arno Haase
Arno Haase ist freiberuflicher Softwareentwickler. Er programmiert Java aus Leidenschaft, arbeitet aber auch als Architekt, Coach und Berater. Seine Schwerpunkte sind modellgetriebene Softwareentwicklung, Persistenzlösungen mit oder ohne relationaler Datenbank und nebenläufige und verteilte Systeme. Arno spricht regelmäßig auf Konferenzen und ist Autor von Fachartikeln und Büchern. Er lebt mit seiner Frau und seinen drei Kindern in Braunschweig.
Kommentare

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu: