How C# Concurrent Collections Achieve Thread Safety

This article explores how .NET's concurrent collections—such as ConcurrentDictionary<TKey, TValue>, ConcurrentQueue<T>, ConcurrentStack<T>, and ConcurrentBag<T>—provide thread-safe data access without the performance penalties of global locks. By examining internal mechanisms like fine-grained bucket striping, lock-free Compare-And-Swap (CAS) operations, and thread-local work-stealing algorithms, you will understand how these structures balance concurrency, data integrity, and throughput.

The Problem with Standard Collections

Standard collections like Dictionary<TKey, TValue> and List<T> are not thread-safe. When multiple threads mutate a standard collection simultaneously, internal arrays can resize improperly, pointers can corrupt, or reads can enter infinite loops due to race conditions during rehashing. Protecting these structures with simple lock statements creates contention, forcing threads to block and serializing execution even when operations target unrelated parts of the collection.

The System.Collections.Concurrent namespace solves this by employing targeted synchronization strategies tailored to specific access patterns.

ConcurrentDictionary<TKey, TValue>: Fine-Grained Locking and Lock-Free Reads

ConcurrentDictionary<TKey, TValue> handles concurrent access through a combination of lock-striping and volatile memory reads.

Lock-Free Reads

Read operations (TryGetValue, indexing, ContainsKey) are completely lock-free. Internally, bucket tables are implemented as arrays of linked node lists. Nodes are treated as immutable with respect to their link pointers. When a read traverses a bucket chain, it reads volatile references to ensure CPU cache coherency without acquiring a mutex.

Striped Locks for Writes

Modifications (TryAdd, TryUpdate, TryRemove) do not lock the entire dictionary. Instead, the dictionary maintains an array of lock objects known as lock stripes:

  1. The key’s hash code determines which bucket it belongs to.
  2. The bucket index maps directly to a specific lock in the lock array.
  3. Only the lock responsible for that subset of buckets is acquired.

This design allows multiple threads to insert or update items simultaneously, provided those keys resolve to different lock stripes. By default, the number of locks scales with the number of logical processor cores on the machine.

Table Resizing

When the ratio of entries to buckets exceeds a predefined threshold, the table must grow. Resizing requires acquiring every lock in the striped array simultaneously. Once all locks are held, the internal bucket array is reallocated, existing nodes are redistributed, and the locks are released. Because reads do not check locks, reads during a resize continue reading from the old array until the pointer to the new bucket array is swapped atomically.

ConcurrentQueue<T> and ConcurrentStack<T>: Lock-Free CAS Operations

ConcurrentQueue<T> and ConcurrentStack<T> avoid OS-level locks entirely, relying instead on CPU-level atomic instructions through the Interlocked class.

ConcurrentStack<T>

ConcurrentStack<T> implements a lock-free linked list using the Treiber Stack algorithm:

  1. A node is created containing the new value.
  2. The node's Next pointer is set to the current Head.
  3. An Interlocked.CompareExchange atomically compares the current Head with the observed Head.
  4. If Head has not changed, it is updated to point to the new node. If another thread modified Head first, the operation fails, and the loop retries with the updated Head.

Popping an element follows the same pattern: read Head, read Head.Next, and attempt a CompareExchange to point Head to Head.Next.

ConcurrentQueue<T>

Modern implementations of ConcurrentQueue<T> use an array-based segmented ring buffer. Instead of allocating a node for every enqueue operation, the queue allocates a linked list of fixed-size array segments:

  • Each segment manages its own Head and Tail indexes using atomic interlocked operations.
  • Enqueueing increments the Tail index atomically.
  • Dequeueing increments the Head index atomically.
  • When a segment fills, a new segment is allocated and linked. This prevents unbounded allocations and drastically reduces garbage collection pressure compared to node-per-element approaches.

ConcurrentBag<T>: Thread-Local Storage and Work-Stealing

ConcurrentBag<T> is an unordered collection optimized for scenarios where the thread adding an item is often the same thread consuming it (such as parallel processing loops).

  1. Thread-Local Queues: Each thread that interacts with a ConcurrentBag<T> is assigned its own doubly-linked list (deque).
  2. Local Access: When a thread adds or removes an item, it targets its own local deque. If only the owning thread operates on its list, operations require zero synchronization locks.
  3. Work-Stealing: If a thread attempts to take an item but its local deque is empty, it attempts to "steal" an item from another thread's deque. Stealing requires taking a lock on the target thread's deque, but contention remains minimal because stealing only occurs when a thread runs out of work.

Snapshot and Enumeration Semantics

Concurrent collections do not throw InvalidOperationException when enumerated while being modified. However, their enumeration behavior differs significantly from standard collections:

  • Moment-in-Time Iteration: ConcurrentDictionary<TKey, TValue> and ConcurrentBag<T> provide an "eventually consistent" view. An iterator represents a snapshot of the state at the moment enumeration began, but subsequent concurrent modifications may or may not be reflected in the remaining loop.
  • Whole-Collection Properties: Properties such as Count and IsEmpty are not instantaneous constants. In ConcurrentDictionary, calculating Count requires acquiring all lock stripes to sum the entries accurately. In ConcurrentQueue, checking IsEmpty checks whether the current head has caught up to the tail without locking the entire structure.