3.200 % CPU-Auslastung

 (josephmate.github.io)
2 Punkte von GN⁺ 2025-03-01 | 1 Kommentare | Auf WhatsApp teilen
  • In einer Java-17-Anwendung waren alle 32 Kerne ausgelastet, die CPU-Auslastung stieg auf 3.200 %, und durch Sortieren des Thread-Dumps nach CPU-Zeit zeigte sich, dass mehrere Threads in TreeMap.put() festhingen
  • Der zunächst verdächtige Schleifencode war zwar ineffizient, doch die Komplexität von O(N lg(M)) und die geprüften Eingabegrößen konnten die Laufzeit im Ausmaß eines Ausfalls nicht erklären
  • Die eigentliche Ursache war, dass mehrere Threads eine gemeinsam genutzte TreeMap ohne Schutz veränderten, wodurch im Inneren des Red-Black-Trees ein Cycle entstand und Suchen bzw. Einfügen in eine Endlosschleife gerieten
  • Dasselbe Verhalten trat auch in einfachem Repro-Code, mit ExecutorService und in einem gRPC-Service auf; der Thread-Pool gab NPEs nicht auf der Standardausgabe aus, was die Ursachenanalyse zusätzlich erschwerte
  • Die Behebung ist nicht mit Collections.synchronizedMap oder dem Wechsel zu ConcurrentHashMap allein erledigt; zusätzlich braucht es Exception-Handling im Executor, CPU- und NPE-Alerts, statische Analyse und Multithread-Tests

Ausfallsymptome und der erste Hinweis

  • Die Maschine war so stark beeinträchtigt, dass selbst ssh-Zugriff kaum noch möglich war; die CPU-Auslastung stieg auf 3.200 %
    • Auf dem Host waren alle 32 Kerne in Nutzung
    • Das unterschied sich von einem früheren Bug, bei dem nur ein einzelner Kern zu 100 % ausgelastet war
  • Der Thread-Dump der Java-17-Runtime enthielt CPU time, und eine Sortierung nach CPU-Zeit machte ähnliche Threads sichtbar
    • Der Stack zeigte auf java.util.TreeMap.put()
    • Die Stelle im Anwendungscode war BusinessLogic.someFunction(BusinessLogic.java:29)

Der zuerst verdächtigte Code und ausgeschlossene Hypothesen

  • Der Code an der Problemstelle iterierte über unrelatedObjects, verwendete im Schleifenrumpf aber nur relatedObject
for (SomeOtherType unrelatedObject : unrelatedObjects) {
    treeMap.put(relatedObject.a(), relatedObject.b()); // line 29
}
  • Dieser Code ließ sich auf ein einzelnes put reduzieren:
treeMap.put(relatedObject.a(), relatedObject.b());
  • Da unrelatedObjects später in der Funktion verwendet wird, konnte der Parameter selbst nicht entfernt werden
  • Möglich war, dass die Nutzung von unrelatedObject bei einem Refactoring verschwunden war
  • In Unit-Tests ließ sich das Problem nicht reproduzieren, selbst als treeMap und unrelatedObjects jeweils auf 1.000.000 Einträge vergrößert wurden
    • Wenn die Größe von unrelatedObjects N und die Größe von treeMap M ist, beträgt die Komplexität O(N lg(M))
    • Für Laufzeiten im Minutenbereich hielt man Größenordnungen von 100 Millionen bis 1 Milliarde Einträgen für nötig
    • Das passte auch nicht zur Annahme, dass beide Datenstrukturen in der echten Anwendung nicht über 1.000 Einträge hinausgingen

Die Endlosschleife durch eine ungeschützte TreeMap

  • Die Definition des TreeMap-Felds sah so aus:
private final Map<K,V> treeMap = new TreeMap<>();
  • Mehrere Threads griffen auf diese TreeMap zu, aber es gab weder Synchronisierung noch andere Schutzmechanismen
  • Javas TreeMap ist als Red-Black-Tree implementiert; wenn gleichzeitige Änderungen interne Node-Verknüpfungen beschädigen, kann ein Cycle entstehen
  • Beim Suchen oder Einfügen eines noch nicht vorhandenen Werts kann der Code diesem Cycle folgen und in eine Endlosschleife geraten

Einfaches Repro-Experiment

  • Es wurde ein Experiment geschrieben, bei dem mehrere Threads eine gemeinsam genutzte TreeMap zufällig aktualisieren
for (int i = 0; i < numThreads; i++) {
    threads.add(new Thread(() -> {
        Random random = new Random();
        for(int j = 0; j < numUpdates; j++) {
            try {
                treeMap.put(random.nextInt(1000), random.nextInt(1000));
            } catch (NullPointerException e) {
                // let it keep going so we can reproduce the issue.
            }
        }
    }));
}
  • Das vollständige Projekt ist in SimpleRepro.java zu finden
  • Zunächst wirkte try/catch wie der entscheidende Punkt
    • Ohne try/catch starben einige Threads mit einer NullPointerException, und das Programm blieb stehen
    • Nach dem Einfügen von try/catch zeigte sich nach einigen Läufen eine CPU-Auslastung von 500 %
  • Eine Race Condition kann nicht nur zu Datenbeschädigung oder Deadlocks führen, sondern eine Datenstruktur auch so beschädigen, dass Endlosschleifen möglich werden und daraus ein Performance-Ausfall entsteht

Cycle innerhalb der TreeMap bestätigen

  • Per Reflection wurde ein Experiment geschrieben, das auf die Felder root, left, right, key und color der TreeMap zugreift und Nodes samt Farbe ausgibt
  • Wenn beim Traversieren eine bereits besuchte TreeMap.Entry erneut angetroffen wird, wird dies als Cycle gewertet
private void print(
    Object treeMapEntry, String tabs, IdentityHashMap<Object, Object> visited
) throws Exception {
    if (treeMapEntry != null && !visited.containsKey(treeMapEntry)) {
        visited.put(treeMapEntry, treeMapEntry);
        print(treeMapEntryLeft.get(treeMapEntry), tabs + " ", visited);
        System.out.println(tabs + treeMapEntryKey.get(treeMapEntry) + ":"
            + (treeMapEntryColor.getBoolean(treeMapEntry) ? "BLACK" : "RED"));
        print(treeMapEntryRight.get(treeMapEntry), tabs + " ", visited);
    } else if (treeMapEntry != null && visited.containsKey(treeMapEntry)) {
        System.out.println(tabs + treeMapEntryKey.get(treeMapEntry) + ":"
            + (treeMapEntryColor.getBoolean(treeMapEntry) ? "BLACK" : "RED")
            + " CYCLE"
        );
    }
}
  • Um die Zugriffsbeschränkungen des Java-Modulsystems zu öffnen, war beim Ausführen folgendes JVM-Argument nötig:
--add-opens java.base/java.util=ALL-UNNAMED

Frühere ähnliche Fälle und Unterschiede

Realistischere Reproduktion mit ExecutorService

  • Code, der NPEs einfach ignoriert, kann unrealistisch wirken; bei ExecutorService treten Exceptions jedoch leicht nicht sichtbar zutage
final ExecutorService pool = Executors.newFixedThreadPool(numThreads);
final TreeMap<Integer,Integer> treeMap = new TreeMap<>();
Random random = new Random();

for (int i = 0; i < numThreads*numUpdatesPerThread; i++) {
    pool.submit(() -> {
        treeMap.put(random.nextInt(10000), random.nextInt(10000));
    });
}
  • Der vollständige Code steht in ExecutorUncaughtRepro.java
  • Beim Ausführen bleibt das Programm hängen, und der Thread-Dump zeigt Threads, die in TreeMap.put() festhängen
  • Auf der Standardausgabe erschien nichts
    • Der Thread-Pool verschluckte die NPE, sodass kein Problemsignal sichtbar wurde
    • In der echten Situation war es genauso
  • Wer einen Thread-Pool selbst verwaltet, sollte folgende Maßnahmen treffen
    • Über eine Thread Factory einen uncaught exception handler registrieren
    • Das zurückgegebene Future verarbeiten und per future.get() die in ExecutionException gekapselte NPE prüfen

Dasselbe Problem in einem gRPC-Service

  • Auch in Thread-Pool-basierten Diensten wie einem gRPC-Service kann eine ungeschützte TreeMap dasselbe Problem verursachen
@Override
public void addReceipt(
    ReceiptProcessorServiceOuterClass.AddReceiptRequest req,
    StreamObserver<ReceiptProcessorServiceOuterClass.AddReceiptResponse> responseObserver
) {
    int timestamp = req.getTimestamp();
    int totalPrice = req.getTotalPrice();
    receipts.put(timestamp, totalPrice);
    ReceiptProcessorServiceOuterClass.AddReceiptResponse response =
        ReceiptProcessorServiceOuterClass.AddReceiptResponse.newBuilder().build();
    responseObserver.onNext(response);
    responseObserver.onCompleted();
}
  • Der vollständige Code steht in GrpcRepro.java
  • Die Protobuf-Definition ist in ReceiptProcessorService.proto zu finden
  • Der Thread-Dump zeigt, dass Threads namens grpc-default-executor-* im Runnable-Zustand in TreeMap.put() festhängen

Vermutungen zur Ursache und Experimente in verschiedenen Sprachen

  • Als mögliche Ursache wurde vermutet, dass zwei Threads den Baum unabhängig voneinander in entgegengesetzte Richtungen rotieren oder dass sich die Schreiboperationen überlappender Rotationen so interleaven, dass ein Cycle entsteht
  • Einen Beweis dafür, welches Thread-Interleaving den Cycle erzeugt, gibt es jedoch nicht
  • Zunächst wurde vermutet, dass eine NPE erforderlich sei, doch spätere Experimente widerlegten diese Annahme
  • Es wurde versucht, dasselbe Problem in mehreren Sprachen zu reproduzieren
    • Java ist die Grundlage des gesamten Falls und reproduziert das Problem
    • C++ std::map verwendet einen Red-Black-Tree und zeigte in seltenen Fällen statt eines Segfaults einen hängenden Thread mit hoher CPU-Auslastung
    • Auch Go ließ sich wider Erwarten reproduzieren; der Code liegt im Go-Experiment
    • Ruby ließ sich trotz einer Sprache, in der NPEs abgefangen werden können, nicht reproduzieren; möglicherweise verhinderte der GIL das problematische Interleaving
  • Im C++-Experiment reproduzierte sich die Endlosschleife unerwartet auch ohne try/catch oder Null-Pointer-Exception
    • Manchmal endete es mit einem segmentation fault
    • Sehr selten blieb die Ausführung länger als 10 Minuten hängen, und top zeigte für SimpleRepro eine CPU-Auslastung von 170,8 %
    • Da ein Null-Pointer-Zugriff in C++ ein Segfault ist, muss es ein Interleaving geben, das ohne Null-Zugriff auskommt
  • Nach diesem Ergebnis wurde das Java-Experiment noch 12-mal ohne Abfangen der NPE erneut ausgeführt, und auch ohne NPE-Catch ließ sich die Endlosschleife in TreeMap.put() reproduzieren

Einfache Fixes und Schutz auf Datenstrukturebene

  • Der einfachste Fix besteht darin, die gemeinsam genutzte TreeMap zu schützen
    • Mit Collections.synchronizedMap umwickeln
    • Auf ConcurrentHashMap wechseln und nur dann sortieren, wenn es nötig ist
  • Eine kontroversere Schutzmaßnahme ist, beim Traversieren des Red-Black-Trees besuchte Nodes zu verfolgen
    • Wenn ein bereits besuchter Node erneut angetroffen wird, wird eine ConcurrentModificationException geworfen
    • Die Datenbeschädigung selbst verhindert das nicht
    • Es kann aber 100 % CPU-Auslastung durch eine Endlosschleife verhindern
    • Der zusätzliche Speicher ist durch die Baumhöhe begrenzt und beträgt O(lg(n))
    • Die Höhe eines Red-Black-Trees ist garantiert O(lg(n))
    • Es wird für unwahrscheinlich gehalten, dass die Standardbibliothek diesen Ansatz übernimmt
  • Der Beispiel-Fix zeichnet in getEntry und put besuchte Nodes mit einer IdentityHashMap auf
IdentityHashMap<Entry<?,?>, Boolean> visited = new IdentityHashMap<>();

while (p != null) {
    visited.put(p, true);
    int cmp = k.compareTo(p.key);
    if (cmp < 0)
        p = p.left;
    else if (cmp > 0)
        p = p.right;
    else
        return p;

    if (visited.containsKey(p)) {
        throw new ConcurrentModificationException("TreeMap corrupted. Loop detected");
    }
}

Mehrere Verteidigungsschichten aufbauen

  • Fehler passieren; eine einzige Schutzschicht reicht daher nicht aus

  • In diesem Fall kamen mehrere Fehler zusammen, aber einige Monitoring-Signale waren noch vorhanden, sodass das Problem entdeckt werden konnte

  • NPE-Alerts

    • Es gab keinen Alert für das Auftreten von NPEs selbst
    • Es gab nur Alerts für Fehlerraten, und diese NPE trat nur einmal pro API-Handler-Worker-Thread auf, sodass der Schwellwert der Fehlerrate nicht überschritten wurde
    • Wegen der Arbeitsweise des Executors blieb auch kein NPE-Log zurück

  • Alert bei ungewöhnlicher CPU-Auslastung

    • Die CPU-Auslastung wurde überwacht und ein einfacher schwellwertbasierter Alert verwendet
    • Als die CPU-Auslastung den Schwellwert überschritt, wurde dies als anormales Verhalten gewertet und ein Alert ausgelöst; über diesen Weg wurde das Problem entdeckt

  • Exception-Handling im Executor

    • Wenn man Jobs in einen Executor legt, sollte unbedingt ein uncaught exception handler gesetzt werden
    thread.setUncaughtExceptionHandler(
    (dyingThread, throwable) -> {
        logger.error("uncaught exception!", throwable);
    }
);

  • Code-Review und statische Analyse

    • Im Code-Review hätte die Kombination aus Threads und TreeMap auffallen können, oder es hätte der Vorschlag kommen können, TreeMap nicht zu verwenden, wenn keine Sortierung nötig ist; in diesem Fall geschah das jedoch nicht
    • Statische Analysewerkzeuge wie SpotBugs, JLint und Chord können solche Arten von Nebenläufigkeitsproblemen zur Build-Zeit finden
    • Als Material zu statischer Analyse wird How Good is Static Analysis at Finding Concurrency Bugs? genannt

  • Tests

    • Für diesen Codepfad gab es keine Multithread-Tests
    • Wenn Code gleichzeitigen Zugriff zulässt, sollten auch die Tests Multithread-Szenarien abdecken

Fazit

  • Ungeschützte gleichzeitige Änderungen können sich nicht nur als Datenbeschädigung, sondern auch als Endlosschleife und hohe CPU-Auslastung äußern
  • Wenn mehrere Threads gleichzeitig eine Datenstruktur mit internen Zeigerstrukturen wie TreeMap verändern, kann die Red-Black-Tree-Struktur Cycles bilden
  • Mit synchronisierten Datenstrukturen, Exception-Handling, Alerts, statischer Analyse und Multithread-Tests lassen sich solche Probleme schneller entdecken oder verhindern

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-03-01
Meinungen auf Hacker News

  • Es ist allgemein bekannt, dass die zentralen Collections in Java per Design nicht Thread-sicher sind; das hätte also auffallen müssen.
    OP sollte auch den restlichen Code durchsehen und prüfen, ob es weitere Stellen gibt, an denen mehrere Threads Collections gleichzeitig manipulieren könnten.
    Wenn man sie mit Collections.synchronizedMap umhüllt oder durch ConcurrentHashMap ersetzt, werden einzelne Map-Operationen Thread-sicher, aber ob auch aufeinanderfolgende Gruppen von Operationen sicher sind, ist eine andere Frage.
    Auch ob das Objekt, dem die TreeMap gehört, selbst Thread-sicher ist, ist fraglich; Änderungen wie das Nachverfolgen besuchter Knoten sorgen nur dafür, dass die Collection weiterhin unsicher ist und auf subtilere Weise fehlschlägt.
    Der Kern des Problems sind nicht die Seiteneffekte der TreeMap, sondern dass der Vertrag der Collection verletzt wurde; auch ein Wechsel zu HashMap wäre weiterhin falscher Code.
    In Code, der von mehreren Threads bearbeitet wird, hat sich am zuverlässigsten erwiesen, möglichst alle Objekte unveränderlich zu machen und Objekte, die nicht unveränderlich sein können, auf kleine, unabhängige und streng kontrollierte Bereiche zu beschränken.

    • Dieser Punkt ist wirklich wichtig: Selbst wenn es ein Thread-sicheres dynamisches Array gibt, ist die Kombination aus size() zum Prüfen der Länge und anschließendem Zugriff auf element(10) nicht atomar.
      Wenn zwischen den beiden Aufrufen ein anderer Thread ein Element entfernt, kann ein Zugriff außerhalb des gültigen Bereichs entstehen.
      Die Lösung ist eine atomare Methode, die beides zusammen erledigt, etwa element_or_null(), oder von vornherein ein normales Array zu verwenden und die gesamte Abfolge beider Operationen mit einem Mutex zu schützen.
    • Datenrennen entstehen bei nicht synchronisiertem gemeinsam genutztem veränderlichem Zustand.
      Da alle drei Bedingungen erforderlich sind, gibt es auch drei Lösungswege: Synchronisierung etwa durch Locks hinzufügen, veränderlichen Zugriff nicht teilen, wie bei einem Single-Owner-Modell mit Channels, oder Daten unveränderlich machen, wie es die Einsichten aus rein funktionalen Sprachen nahelegen.
      Soweit ich weiß, hat auch Google mit Guava einiges in dieses Modell investiert.
      Rust lässt einen auswählen, auf welche dieser drei Bedingungen man verzichten will, und verhindert statisch, dass alle drei gleichzeitig erfüllt sind.
    • Mein erster Gedanke war ebenfalls: „Moment, ist diese Datenstruktur Thread-sicher?“ Letztlich sieht es nach einer für den Zweck ungeeigneten Datenstrukturwahl aus.
      Wenn man das mit einem Mutex gewaltsam passend macht, entstehen meist andere Probleme und Engpässe.
      Wenn man unveränderliche Objekte verwenden will, sollte man unveränderliche Datenstrukturen mit strukturellem Sharing nutzen, um einen explosionsartigen Speicherverbrauch zu vermeiden oder zu reduzieren.
      Mit rein funktionalen Datenstrukturen verschwindet eine Seite des Problems, aber wenn Threads von Zwischenversionen abhängen, die andere Threads erzeugt haben, entsteht ein anderes unangenehmes Problem, und es kann eine andere Datenstruktur nötig sein.
      Wenn man die bereits verwendete veränderliche Datenstruktur unbedingt retten will, kann man Zugriffsversuche serialisieren, bevor sie die Datenstruktur erreichen, und Zugriffe zu Transaktionen bündeln, sodass nur vollständige Transaktionen ausgeführt werden; dabei fühlt es sich irgendwann fast so an, als würde man eine Datenbank implementieren.
    • Ich halte schon das Threading-Modell, das in einer Shared-Memory-Umgebung unabhängige Ausführung erreichen will, grundsätzlich für falsch.
      Der Aufwand, so etwas zum Laufen zu bringen, hätte meiner Meinung nach besser in ein besseres Prozessmodell fließen sollen.

  • Das im Original vereinfachte Codebeispiel ist nicht korrekt.
    Im ursprünglichen Code wird treeMap.put nur ausgeführt, wenn unrelatedObjects nicht leer ist; dieser Unterschied kann ein Bug sein oder auch nicht.
    Außerdem sollte man prüfen, ob a und b jedes Mal denselben Wert zurückgeben und ob sich treeMap wirklich nur wie eine Map verhält.
    Wenn es zum Beispiel eine Map ist, die Updates protokolliert, muss man abwägen, ob es in Ordnung ist, sie so zu ändern, dass sie nur einmal protokolliert.

    • Richtiger Hinweis. Es sollte in ein if geändert werden, das prüft, ob es nicht leer ist.

  • Auch wenn eine Implementierung von Comparator oder Comparable keine konsistente totale Ordnung liefert, kann eine Endlosschleife entstehen: https://stackoverflow.com/questions/62994606/concurrentskips...
    Das hat nichts mit Nebenläufigkeit zu tun.
    Ob es auftritt, kann von den konkreten verarbeiteten Daten und der Verarbeitungsreihenfolge abhängen, sodass es lange normal wirkt und dann in der Produktionsumgebung hochgeht.

    • Ich frage mich, ob jemand das tatsächlich schon direkt gesehen hat. Das wäre ein gutes Thema für einen Blogbeitrag.
      Einen fehlerhaften Comparator ohne totale Ordnung habe ich persönlich bisher noch nicht erlebt.

  • Ich dachte immer, Race Conditions führten nur zu Datenkorruption oder Deadlocks – aber nicht dazu, dass sie Performance-Probleme verursachen können.
    Wenn sie aber Daten so beschädigen können, dass eine Endlosschleife entsteht, ergibt das Sinn.
    Deshalb denke ich oft, dass Fehler, Fehlverhalten und Warnungen in einem Projekt grundsätzlich behoben werden sollten. Sie können nämlich scheinbar nicht zusammenhängende Probleme auslösen.
    Allerdings wird ein solches Prinzip von den Leuten, die entscheiden, was getan wird, nur selten akzeptiert.

    • Das ist eine brauchbare Faustregel, aber es braucht Pragmatismus.
      In manchen Projekten können die Kosten, alle Fehler, Fehlverhalten und Warnungen zu beseitigen, deutlich höher sein als die Kosten, gelegentlich ein scheinbar nicht zusammenhängendes Problem in Kauf zu nehmen.
      Ob ein bestimmter Fehler wahrscheinlich an künftigen Problemen beteiligt sein wird und ob es günstiger ist, ihn im Voraus zu beheben, lässt sich kaum vorhersagen; am Ende ist es eher Handwerk als Wissenschaft.
      „Gar nichts reparieren“ ist furchtbar, und „alles reparieren“ ist meist unrealistisch. Man braucht also einen Entscheidungsrahmen, ein Gespür aus Erfahrung und das Vertrauen der Stakeholder.
    • Bei uns in der Arbeit werden alle Warnungen als Fehler behandelt, und ein Pull Request kann nicht gemergt werden, wenn nicht alle automatisch laufenden CI-Pipelines erfolgreich sind.
      Das erfordert Disziplin, aber wenn man diesen Zustand einmal erreicht hat, ist er viel leichter zu halten.
    • Wichtig ist auch, Exceptions nicht einfach zu fangen und zu ignorieren.
      Wenn man nicht konkret weiß, dass es sicher ist, die Programmausführung fortzusetzen, ist auch „fangen und nur loggen“ eine schlechte Idee.
      Besser ist es, die Exception einfach weiterzureichen, bis sie an einer Stelle ankommt, die sinnvoll damit umgehen kann, etwa indem sie 500 zurückgibt oder einen Fehlerdialog anzeigt.
    • Letztlich muss man sich aussuchen, welche Kämpfe man führt.
      In einem Rails-Projekt, das ich betreue, gab es das Problem, dass die Logs mit „unsupported parameters“ voll waren. Ich habe die Controller sorgfältig geprüft und die Parameter erlaubt, aber es tauchte weiter auf.
      Wahrscheinlich harmlos, aber es erzeugt viel Rauschen in den Logs.
      Mehrere Leute haben versucht, es zu lösen, aber es gab immer etwas mit höherer Priorität, und es war schwer zu rechtfertigen, viel Zeit in etwas ohne funktionale Auswirkungen zu stecken.
      Es ist so ein lästiges Problem wie Hämorrhoiden: Man hat die Wahl, sich operieren zu lassen und ein paar Wochen große Schmerzen zu haben, oder einfach damit zu leben. Meist ist es gutartig, kann sich aber auch verschlimmern und zu einem großen Problem werden.
      Man könnte so etwas wohl digitale Hämorrhoiden nennen.
    • Auch ohne Korruption können Race Conditions dazu führen, dass dieselbe Arbeit mehrfach erledigt wird und am Ende nur ein Ergebnis übrig bleibt, was große Performance-Probleme verursachen kann.
      Wenn man entschieden hat, dass eine Warnung irrelevant ist, sollte man das zumindest in einem Kommentar erklären und die Warnung nach Möglichkeit mit einem pragma in einem möglichst engen Bereich deaktivieren.
      Fehlverhalten beseitige ich lieber. Ich habe schon erlebt, dass Code, der mit „Ich weiß nicht, warum das funktioniert, aber …“ markiert war, später nicht mehr funktionierte; hätte man ihn vorher bereinigt, hätte man Zeit für eine sorgfältige Korrektur gehabt, statt ihn in Eile neu schreiben zu müssen.

  • Bei der Stelle „ich kam gerade noch per ssh drauf“ musste ich an eine Situation aus meiner Graduiertenzeit denken.
    Unsere Forschungsgruppe war eine kleine Gruppe für Parallel- und verteilte Verarbeitung mit etwa acht Leuten, die sich eine Maschine teilten, vermutlich eine Sun UltraSparc 170, mit 1 GB Festplatte und 128 oder 256 MB RAM.
    Man muss auch bedenken, dass Sun-Maschinen kaum neu gestartet wurden.
    Ein neuer Student hatte offenbar eine große Textdatei anhand der Zeilennummern in 32 oder 64 Bereiche aufgeteilt und dann, ohne separate Dateien zu erzeugen, N Kopien von perl parallel gestartet, damit jede ihren eigenen Zeilenbereich verarbeitet.
    Für damalige Verhältnisse fraßen N perl-Interpreter viel RAM, und sobald geswappt wurde, suchten sie wie verrückt in unterschiedlichen Bereichen derselben Datei herum, während jeder Prozess versuchte, noch ein paar Zeilen zu lesen.
    Außerdem musste der J-te Prozess sehr wahrscheinlich J/N der Datei lesen, nur um bis zu seinem eigenen Bereich zu gelangen.
    An der Konsole bekam man nicht einmal mehr einen Login-Prompt, aber glücklicherweise gab es bereits eine eingeloggte Session, und su zeigte nach 20 bis 30 Minuten den Passwort-Prompt an.
    Weitere 5 bis 10 Minuten später hatten wir eine Root-Session, sahen mit top die Ursache, versuchten den Benutzer zu kontaktieren und killten die problematischen Prozesse, woraufhin das System wieder normal lief.
    Die Idee an sich war richtig, aber die Systemgrenzen wurden überhaupt nicht verstanden. Wegen der Festplatte und des geringen RAM war der I/O-Flaschenhals so extrem, dass eine einfache lineare Verarbeitung viel besser gewesen wäre.

  • Ob Java oder eine andere Sprache: Wenn man gleichzeitige Operationen auf nicht thread-sicheren Objekten ausführt, entstehen einige der interessantesten Bugs der Welt.

    • Deshalb muss man beim Einsatz nicht thread-sicherer Objekte in mehreren Threads den atomaren Zugriff selbst verwalten oder eine thread-sichere Version verwenden.
      Multithreading-Fehler sind beim Debugging das Schlimmste.
      In diesem Fall wäre das schon beim Design sehr leicht zu erkennen gewesen, und sobald man in einer Multithread-Umgebung einen normalen Container verwenden will, hätten die Warnlampen angehen müssen.
    • Ich habe schon einige Nebenläufigkeitsbugs erlebt, aber nie absichtlich eine Inkonsistenz reproduziert, die dadurch entsteht, dass man bei einem veränderlichen Feld in Java den volatile-Modifier entfernt.
      Vielleicht war die damals verwendete JVM einfach zu gut gebaut.
    • Selbst wenn ich sicher war, dass ich die Konsequenzen akzeptieren kann, wenn ich etwas Unsynchronisiertes teile, war das tatsächliche Ergebnis immer unerwartet.
    • Das ist vielleicht ein etwas radikaler Gedanke, aber aus diesem Grund bevorzuge ich das Debugging von Races in C/C++.
      Die Sprache definiert im Fall von Races zwar im Grunde verrückte Semantiken ohne wirklichen Sinn, aber in der Praxis zeigen sich oft Speicherbeschädigungen oder laute Probleme.
      Weil Races größtenteils illegal sind, kann man Werkzeuge wie Thread-Checker bauen, ohne den Quellcode ändern zu müssen, um die Bedeutung zu markieren.
      Java dagegen hat kein Undefined Behavior, aber es kann leicht passieren, dass zwei Felder subtil auseinanderlaufen, und so etwas ist deutlich schwerer nachzuverfolgen.
    • Einige, vielleicht sogar die meisten Operationen der Java Collections führen Integritätsprüfungen durch, um vor solchen Problemen zu warnen.
      Zum Beispiel indem eine Map eine ConcurrentModificationException wirft.

  • Ich habe dasselbe Phänomen auch in produktivem C# gesehen.
    Die Symptome waren identisch, und im Prozess-Dump fand sich ein beschädigtes Dictionary.
    Wir dachten, überall werde ConcurrentDictionary verwendet, aber eines kam aus einer Bibliothek und war das Problem.
    Damals nutzten wir .NET Framework, und soweit ich mich erinnere, hat .NET Core Code zur Erkennung gleichzeitiger Änderungen.
    Ich kenne die Implementierung nicht genau, aber schon ein Versionszähler würde dafür ausreichen.
    Es ist seltsam, wie sehr man sich darauf versteift, als wäre eine NPE der zentrale Bestandteil. Im ursprünglichen Auftreten scheint sie nicht vorhanden gewesen zu sein, und nur weil es keine Exceptions gibt, ist das kein Grund anzunehmen, dass es solche Bugs in C nicht gibt.
    Der Kern sind Klasseninvarianten. Im Allgemeinen gilt die Invariante nicht, während ein Mutator läuft, sondern wird erst am Ende wiederhergestellt.
    Wenn ein anderer Mutator ausgeführt wird, bevor die Invariante wiederhergestellt ist, wird die Datenstruktur beschädigt. Wenn man nicht in einem gültigen Zustand beginnt, ist es unwahrscheinlich, dass man am Ende in einem gültigen Zustand landet.

    • Letztlich lag es an falscher Logik.
      Weil ich das Pech hatte, dass es sich mit einer nicht abgefangenen NPE nicht reproduzieren ließ, zog ich fälschlich den Schluss, dass eine nicht abgefangene NPE eine notwendige Bedingung sei.

  • Dasselbe habe ich auch schon bei einer nicht ausreichend synchronisierten java.util.HashMap gesehen.
    Das war zwar um 2009 herum, aber soweit ich weiß, ist es auch heute noch möglich.
    Soweit ich mich erinnere, verwendet HashMap zur Kollisionsauflösung Chaining; vermutlich ist innerhalb einer Chain ein Zyklus entstanden.
    Ich habe mich allerdings eher darauf konzentriert, den problematischen Code komplett zu entfernen, statt mich zur Verifikation hineinzuknien.
    Wissen über Nebenläufigkeit wird in Interviews oft abgefragt; wenn man Data Races nur für ein nebensächliches Problem hält, macht das keinen guten Eindruck, und dieser Fall zeigt, warum.

    • Ich wusste nicht, dass so etwas auch bei HashMap passieren kann.
      Hat das mit der verketteten Liste zu tun, die für die Kollisionsbehandlung verwendet wird?

  • Ich frage mich, ob es nicht eine Möglichkeit wäre, zum Finden von Zyklen einen hochzählenden Zähler zu verwenden und eine Exception zu werfen, wenn er größer wird als die Baumtiefe oder die Größe der Collection.
    Anders als der vom Autor vorgeschlagene Ansatz mit einem Hash-Set hätte das fast keinen Speicher- oder CPU-Overhead und wirkt auch eher akzeptabel.
    Allerdings ist es mir in über zehn Jahren C# nie passiert, dass ich bei nebenläufigen Situationen gleichzeitigen Zugriff auf Datenstrukturen nicht berücksichtigt hätte.

    • Keine schlechte Idee, aber in einer Situation mit Data Races ist es im Allgemeinen ziemlich schwierig, nützliche Vorbedingungen hinzuzufügen.
      Es gibt viele andere Arten, wie ein Baum kaputtgehen kann.
    • Gute Idee. Ich habe das früher bei binärer Suche und Baumstrukturen gemacht.
      Wenn möglich, sollte man Endlosschleifen vermeiden; Fälle, in denen das nicht geht, sind ziemlich selten.
      Das ist keine Korrektur, aber eine gute Abmilderungsstrategie.
      Endlosschleifen gehören zu den übelsten Bugs. Im Debugger sind sie leicht zu finden, aber wie in der Situation des OP, in der „ssh gerade noch so geht“, können die Folgen sehr unfreundlich sein.
      Besonders unangenehm sind Endlosschleifen in Library-Code.
    • Das ist deutlich besser. Man braucht nur konstanten Speicher.
      Es gibt die Garantie, dass die Anzahl der Nodes höchstens der Baumhöhe entspricht.

  • Exceptions in Threads sind wirklich fatal.
    Es gibt eine schreckliche Bug-Hunting-Geschichte, in der C++, select() und ein Thread, der mit Exceptions um sich wirft, die Hauptrollen spielen: https://news.ycombinator.com/item?id=42532979

    • Ich erinnere mich, den Beitrag gelesen zu haben, habe ihn aber mangels Fachwissen in dem Bereich nicht verstanden.
      Ich sollte ihn noch einmal lesen.