Kolumne

Aus der Java-Trickkiste: Seiteneffektfreier Code – Mehrere Threads

Arno Haase
java-trickkiste

© Software & Support Media

Die letzten beiden Kolumnen haben seiteneffektfreie Programmierung mit Java vorgestellt und gezeigt, wie Code dadurch besser les- und testbar werden kann. Sogar die Performance kann gewinnen, wenn man unveränderliche („persistente“) Collections mit passenden Algorithmen verwendet.

Dieses Mal betrachten wir seiteneffektfreien Code – d. h. hier konkret Klassen, bei denen alle Felder final sind – im Kontext mehrerer Threads.

Threadsichere Zugriffe

Wenn mehrere Threads auf dieselben Daten zugreifen, müssen sie die Regeln des Java Memory Model (JMM) beachten [1], sonst kommt es zu subtilen, nur sporadisch auftretenden Fehlern. Das kann sich zum Beispiel so äußern, dass verschiedene Threads unterschiedliche Werte sehen, je nachdem auf welchem Prozessorkern sie gerade laufen. Für unveränderliche Datenstrukturen garantiert das JMM, dass jeder Thread sie also vollständig initialisiert sieht.

Nehmen wir an, mehrere Threads verarbeiten Datensätze und wollen eine gemeinsame Statistik darüber führen, wie viele Datensätze erfolgreich verarbeitet wurden und bei wie vielen Fehler aufgetreten sind. Listing 1 zeigt eine unveränderliche Datenstruktur, die für diese beiden Werte je ein int-Feld hat. Lesende Zugriffe auf diese Datenstruktur sind sicher, egal wie viele Threads sie parallel benutzen.

public class Statistics {
  private final int numSuccess;
  private final int numFailure;

  public Statistics (int numSuccess, int numFailure) {
    this.numSuccess = numSuccess;
    this.numFailure = numFailure
  }

  public int getNumSuccess() {
    return numSuccess;
  }
  public int getNumFailure() {
    return numFailure;
  }
}

Spannend wird es, wenn die Counter aktualisiert werden sollen. Denn das tun ja mehrere Threads parallel, und der Code muss Kollisionen vermeiden und allgemein die Regeln des JMM beachten. Listing 2 zeigt eine typische Implementierung.

public class StatisticAccess {
  private final AtomicReference ref =
      new AtomicReference<> (new Statistics (0, 0));

  public Statistics get() {
    return ref.get();
  }
  
  public void increment (int numSuccess, int numFailure) {
    Statistics before, after;
    do {
      before = ref.get();
      after = new Statistics (
        before.getNumSuccess() + numSuccess,
        before.getNumFailure() + numFailure);
    }
    while (! ref.compareAndSet (before, after));
  }
}

Die Klasse StatisticAccess kapselt den Zugriff auf die Statistics: Alle Threads, die lesend oder schreibend darauf zugreifen wollen, teilen sich eine Instanz. Sie enthält im Kern eine java.util.concurrent.AtomicReference auf das gerade aktuelle Statistics-Objekt. Der Code zum Auslesen der aktuell gültigen Statistics ruft einfach die Methode get() auf der AtomicReference auf, die eben den aktuellen Wert liefert.

Zum Aktualisieren gibt es in Listing 2 die Methode increment(), die beide Zähler gleichzeitig um die übergebenen Werte erhöht. Sie verwendet dazu eine „Compare-And-Set“-Schleife (CAS-Schleife).

Dazu liest sie als Erstes die AtomicReference aus und merkt sich den Wert in der Variable before. Dann erzeugt sie ein neues Statistics-Objekt mit den aktualisierten Counter-Werten. Und schließlich ruft sie die Methode compareAndSet() auf der AtomicReference auf und übergibt dabei sowohl das ursprüngliche als auch das veränderte Objekt.

Dieser Aufruf prüft, ob die AtomicReference noch auf das ursprüngliche Objekt zeigt. Wenn das der Fall ist, ändert sie die Referenz auf das neue Objekt und gibt true zurück, andernfalls ändert sie nichts und gibt false zurück. Unser Code wiederholt die Operationen so lange, bis das CAS erfolgreich war, daher der Name CAS-Schleife.

Der Clou dabei ist, dass der Aufruf von compareAndSet() das Vergleichen und ggf. Ändern in einer einzigen, atomaren Operation durchführt, ohne dass ein anderer Thread zwischendurch die Referenz ändern kann. Dadurch können keine Updates verlorengehen. Und das Ganze funktioniert komplett ohne Locks.

Auch mit großen Datenstrukturen

Dieser Ansatz, unveränderliche Datenstrukturen über eine AtomicReference mit CAS-Schleife zu verwalten und dadurch threadsicheren Lese- und Schreibzugriff sicherzustellen, funktioniert auch für sehr viel größere Datenstrukturen, die durchaus Collections enthalten können.

Diese Collections müssen dann allerdings „persistent“ sein: Sie sollten Methoden zum Hinzufügen und Entfernen von Elementen haben, die allerdings die ursprüngliche Collection unverändert lassen und eine veränderte Kopie zurückliefern [2]. Im Folgenden verwende ich dafür Collection-Klassen wie AHashMap, die aus der Open-Source-Bibliothek a-foundation stammen [3] – das JDK selbst enthält leider keine solchen Collections.

Listing 3 zeigt eine extrem vereinfachte Implementierung einer Bank – und ja, ich weiß, dass echte Banksoftware komplett anders aufgebaut ist. Die Klasse CasBank speichert den aktuellen Stand je Konto in einer AHashMap, die an einer AtomicReference hängt.

Beim Erzeugen der Map wird durch einen Aufruf von withDefaultValue (0L) festgelegt, dass für noch unbekannte Kontonummern ein Kontostand von 0 zurückgeliefert wird. Das spart für diese Demo die Logik zum expliziten Anlegen von Konten.

public class CasBank {
  private final AtomicReference<AMap<String, Long>> ref =
    new AtomicReference<> (
    AHashMap.<String, Long>empty ().withDefaultValue (0L));

  public long get (String account) {
    return ref.get ().getRequired (account);
  }

  public void transfer (String from, String to, long amount) {
    AMap<String, Long> before, after;
    do {
      before = ref.get ();
      after = before.updated (from, before.getRequired (from) - amount);
      after = after .updated (to,   after .getRequired (to)   + amount);
    }
    while (! ref.compareAndSet (before, after));
  }

  public long getTotal() {
    long result = 0;
    for (long i: ref.get ().values ()) {
      result += i;
    }
    return result;
  }
}

Die Methode get() liefert den aktuellen Stand eines Kontos zurück, und weil Lesezugriffe auf eine unveränderliche Klasse automatisch threadsicher sind, gibt es dabei nichts weiter zu beachten.

Ein Aufruf von transfer() soll Geld von einem Konto auf ein anderes übertragen und zwar atomar: Es sollen immer entweder beide Konten oder keines von ihnen verändert werden, und kein Zwischenzustand soll je sichtbar werden. Die Änderung erfolgt über eine CAS-Schleife. Dort wird in der Variable after eine AMap erzeugt, die den geänderten Kontostand für Quell- und Zielkonto der Überweisung enthält, und anschließend mit compareAndSet() gespeichert.

Die Methode getTotal() schließlich ermittelt, wie viel Geld insgesamt in der Bank deponiert ist und addiert zu diesem Zweck die Kontostände aller Konten der Bank auf. Dieses Aufsummieren muss dabei auf einem stabilen „Snapshot“ der Daten erfolgen. Sonst könnte es passieren, dass eine Überweisung von Konto A auf Konto B passiert, nachdem der Stand von A und bevor der Stand von B aufsummiert wurde – und die ermittelte Gesamtsumme wäre verfälscht.

Deshalb liest der Code von getTotal() sich einmal zu Beginn die AMap aus der AtomicReference und iteriert dann über deren Einträge. Weil die AMap unveränderlich ist, dient sie als stabiler Snapshot, auch wenn andere Threads parallel dazu Kontostände verändern.

Performance

Die Performance der CasBank unter Last lässt sich am besten einordnen, wenn wir sie mit einer alternativen Implementierung vergleichen. Listing 4 enthält deshalb eine SynchronizedBank, die dieselbe Funktionalität implementiert, die Threadsicherheit aber durch ein synchronized an allen Methoden erreicht. Sie speichert die Kontostände intern in einer normalen java.util.HashMap.

public class SynchronizedBank {
  private final Map<String, Long> map = new HashMap<> ();

  public synchronized long get (String account) {
    if (map.containsKey (account)) return map.get (account);
    else return 0;
  }

  public synchronized void transfer (String from, String to, long amount) {
    final long newFrom = get (from) - amount;
    final long newTo   = get (to)   + amount;
    map.put (from, newFrom);
    map.put (to,   newTo);
  }

  public synchronized long getTotal() {
    long result = 0;
    for (long i: map.values ()) {
      result += i;
    }
    return result;
  }
}

Welche der Implementierungen ist schneller? Das hängt wie so oft vom Lastszenario ab. Ich habe auf meinem Notebook, das einen Intel i7 mit vier Kernen à zwei Hyperthreads hat, Messungen durchgeführt.

Den größten Einfluss darauf, welcher Code schneller läuft, hat die Auswahl der aufgerufenen Methoden. Wenn mehrere Threads am laufenden Band ausschließlich transfer() aufrufen, dann ist die SynchronizedBank durchweg schneller als die CasBank, und zwar umso mehr, je mehr Threads parallel aktiv sind. Das liegt daran, dass dieses Szenario überhaupt nicht von den lockfreien Leseoperationen der CasBank profitiert, während der Overhead für die CAS-Schleife und Kollisionen maximal zum Tragen kommt.

Bei einem Lastmix aus Überweisungen und Abfragen des Kontostands liegen beide in etwa gleichauf und zwar auch noch für eine große Map mit einer Million Konten. Je größer der Anteil an Kontostandsabfragen ist, desto besser schneidet die CasBank im Verhältnis ab. Der Grund ist, dass bei ihr Leseoperationen ohne Locking auskommen, dass sie also parallel mit anderen Leseoperationen und sogar Schreiboperationen laufen können, während bei der SynchronizedBank nur eine Operation gleichzeitig laufen kann, egal ob lesend oder schreibend.

Wirklich groß werden die Unterschiede aber dann, wenn ein zusätzlicher Thread fortlaufend getTotal() aufruft: Bei der SynchronizedBank kommen alle übrigen Operationen praktisch zum Stillstand, während die CasBank nur marginal langsamer wird. Der Grund liegt auf der Hand: In der SynchronizedBank hält getTotal() dasselbe Lock, das auch alle übrigen Operationen benötigen, sodass während dieser lang laufenden Operation alle übrigen Threads auf Eis gelegt sind.

Fazit

Unveränderliche Datenstrukturen, die über eine AtomicReference mit CAS-Schleife verwaltet werden, sind ein leistungsfähiger und skalierbarer Weg, Zustände zwischen Threads zu teilen. Wenn die Daten primär geändert und nur selten gelesen werden, überwiegt der Overhead dieses Ansatzes. Wenn die Daten aber häufig gelesen werden, spielt dieses Design seine Stärken aus – besonders wenn Leseoperationen über einen längeren Zeitraum einen stabilen Stand der Daten benötigen.

Damit ist die Miniserie über seiteneffektfreie Programmierung in Java abgeschlossen, und ich hoffe, sie hat etwas von den Möglichkeiten vermittelt, die dieses Paradigma bietet.

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: