Why TreeSet Throws ConcurrentModificationException and How to Fix It

Background

In a feed‑forward service the incoming feed messages are stored in a tree structure. The child‑node collection is implemented with TreeSet to obtain de‑duplication, ordering and fast lookup. Under normal load the system runs smoothly, but a ConcurrentModificationException (CME) suddenly appears during high‑concurrency writes.

Reproducing the CME

The test code creates two threads that repeatedly add elements to the same TreeSet. When the loop runs 100 times on JDK 8 the CME occurs frequently, while on JDK 17 the probability drops dramatically; increasing the loop to 1 000 iterations makes the exception common again on JDK 17.

Typical test snippet (simplified):

for (int i = 0; i < N; i++) {
    set.add(i);
}

Root Cause Analysis

The underlying TreeSet is built on a red‑black tree (implemented by TreeMap). Insertion and deletion require a series of rotations and recolorings that are not atomic. When a thread is pre‑empted in the middle of fixAfterInsertion, the tree can be left in an inconsistent state, and the fail‑fast iterator detects the modification and throws CME.

Typical interruption points:

Thread time‑slice exhaustion – the OS pauses the thread after a few microseconds.

Garbage‑collection pauses (STW) – the JVM stops all user threads.

Higher‑priority thread pre‑emption – the scheduler switches to a more important task.

Explicit thread interrupt or lock contention – the fixing thread is blocked.

Hardware/OS interrupts (IO, timer) – cause an unexpected context switch.

Red‑Black Tree Mechanics

A red‑black tree is a self‑balancing binary search tree with the following invariants:

Node colour is either RED or BLACK.

The root is BLACK.

RED nodes cannot have RED children.

Every path from a node to its descendant leaves contains the same number of BLACK nodes.

All leaf (NIL) nodes are BLACK.

During insertion fixAfterInsertion restores these rules by recolouring and rotating nodes. If the process is interrupted after recolouring the parent and uncle but before recolouring the grandparent, the tree violates the black‑height rule.

Example insertion steps (simplified):

// step 1: new node 5 is coloured RED, parent 10 is RED
// step 2: while (x != root && x.parent.colour == RED) { … }
// step 3: uncle 30 is RED → case 1
// step 4: setColor(10, BLACK)
// step 5: setColor(30, BLACK)
// thread is pre‑empted before setColor(20, RED) and x = 20

Consequences of an Inconsistent Tree

Lookup errors – TreeMap.get() may mis‑judge the existence of a key or enter an infinite loop.

Traversal anomalies – missing nodes, duplicate visits, or dead‑loops caused by broken parent/child pointers.

Data loss or total corruption – subsequent rotations on a malformed tree can create orphan nodes or cycles.

Concurrency Solutions

Several strategies can replace the plain TreeSet in high‑concurrency scenarios:

SynchronizedSortedSet (via Collections.synchronizedSortedSet()) – simple but serialises all access, leading to poor performance under load.

Read‑Write Lock – allows concurrent reads while writes acquire an exclusive lock; still suffers when writes dominate.

ConcurrentSkipListSet – lock‑free skip‑list implementation offering true concurrent reads and writes with O(log n) operations.

CopyOnWriteArraySet – snapshot‑based, suitable for small collections with far more reads than writes; does not preserve order.

Custom segmented/optimistic TreeSet – partitions the key space and applies fine‑grained locks or CAS updates; complex to implement but can be tuned for extreme write‑heavy workloads.

Performance Test (JDK 17)

The author measured single‑thread, low‑concurrency, high‑concurrency read‑write, and small‑data high‑write scenarios. Results:

Single‑thread / low‑concurrency – TreeSet is fastest because no lock overhead.

High‑concurrency read‑write with large data – ConcurrentSkipListSet outperforms all others.

Small data with intense writes – SynchronizedTreeSet can match write throughput but reads lag behind ConcurrentSkipListSet.

Images illustrating the test setup and results are retained below.

Conclusion

For most high‑concurrency ordered‑set needs in Java, ConcurrentSkipListSet provides the best balance of performance and correctness. Simpler synchronized wrappers are only viable for low‑traffic or read‑heavy workloads, while copy‑on‑write sets suit tiny, read‑dominant collections. Custom segmented locks can be considered for extreme write‑heavy scenarios, but they require careful design and thorough testing.