Lock-Free Linked List

In the world of multi-core processors, traditional locking mechanisms can become a major performance bottleneck, forcing threads to wait idly and hindering scalability. Lock-free programming offers a powerful alternative, enabling multiple threads to operate on shared data structures simultaneously without ever blocking one another. However, this parallelism introduces significant complexities, creating subtle race conditions that can be notoriously difficult to manage. This article explores one of the most fundamental lock-free data structures: the linked list.

This article provides a comprehensive guide to understanding the intricate dance of lock-free linked lists. The first chapter, "Principles and Mechanisms," will deconstruct the core concepts, starting with the atomic Compare-And-Swap (CAS) operation. It will guide you through common pitfalls like the infamous ABA problem and explain the sophisticated solutions required for safe node deletion and memory reclamation. Following this, the "Applications and Interdisciplinary Connections" chapter will bridge theory and practice, showing how these principles are used to build the high-performance queues, caches, and schedulers that form the backbone of modern operating systems, databases, and large-scale applications.

Imagine a bustling kitchen with many chefs all trying to work at the same counter. The traditional approach is to give only one chef at a time a special token—a lock—granting them exclusive access. While one chef works, all others must wait. It's safe, but terribly inefficient. What if we could design a system where all chefs could work simultaneously, coordinating their actions with subtle, lightning-fast gestures, never getting in each other's way? This is the promise of lock-free programming, a beautiful and intricate dance of concurrent execution. In this chapter, we will embark on a journey to understand the fundamental principles that make this dance possible, using the humble linked list as our stage.

The entire edifice of lock-free data structures rests on a single, powerful tool provided by modern processors: an atomic operation. The most common of these is called ​​Compare-And-Swap​​, or ​​CAS​​.

Imagine you want to replace a book on a library shelf. Before reaching for it, you take a mental snapshot: "I expect to find Moby Dick in slot C4." You walk over, and just before you place your new book, The Great Gatsby, you check: "Is Moby Dick still in C4?" If it is, you swap the books. If, however, another librarian has already replaced it with War and Peace, your expectation is violated. You don't just blindly jam your book in; you step back, note the change, and rethink your plan.

This is precisely what CAS does, but in a single, indivisible, instantaneous step. The operation CAS(address, expected_value, new_value) says: "Look at the memory address. If its content is exactly what I expected_value, update it with the new_value and tell me I succeeded. Otherwise, don't touch anything and tell me I failed."

This simple, conditional update is our atomic handshake. It's the only guarantee of order in the potential chaos of multiple threads acting at once. With it, we can build algorithms where threads speculatively do work and then try to "commit" their change with a CAS. If they succeed, their work is done. If they fail, it means the world has changed, and they must try again based on the new state of affairs.

Let's start with a simple structure: a last-in, first-out (LIFO) stack, implemented as a linked list where we only ever access the head.

To ​​push​​ a new value, a thread creates a new node "offline". It sets this new node's next pointer to point to what it currently sees as the head of the stack. Then, it uses CAS to try and swing the global head pointer from the old head to its new node.

To ​​pop​​ a value, a thread reads the current head and its next node. It then uses CAS to swing the head pointer to that next node, effectively removing the top element.

This "read, modify, CAS" loop is the fundamental pattern of lock-free algorithms. But when, exactly, does an operation take effect? This is answered by the crucial concept of ​​linearizability​​. For these algorithms, the operation is considered to happen instantaneously at the exact moment of the successful CAS. Before that instant, the push or pop has not occurred. After that instant, it has, and it is visible to the entire system. This gives us a way to reason about our chaotic kitchen, by imagining that each chef's action, no matter how long it took to prepare, happens in a single, a-tomic instant.

Our elegant CAS-based stack seems perfect, but it hides a subtle and dangerous flaw known as the ​​ABA problem​​. It's a case of mistaken identity that can corrupt our data structure.

Let's follow a story:

1. Thread $T_1$ wants to pop from a stack whose head is node $A$, which points to node $B$. $T_1$ reads the head, getting $A$, and determines the new head should be $B$. It prepares to execute CAS(, A, B).
2. But before it can, the operating system puts $T_1$ to sleep.
3. While $T_1$ is sleeping, Thread $T_2$ comes along. It pops $A$, so the head becomes $B$. Then it pops $B$, so the head becomes $C$.
4. Now, $T_2$ pushes a new node. By coincidence, the memory allocator gives it the exact same memory address that the original node $A$ had. Let's call this new node $A'$. $T_2$ pushes $A'$ onto the stack, so the head is now $A'$.
5. $T_1$ wakes up! It resumes its plan to execute CAS(, A, B). It checks the head, sees that it points to address $A$ (it's actually $A'$, but the address is the same!), and the CAS succeeds. The head is now incorrectly set to $B$, a node that was already popped and might be garbage memory. We've just lost node $A'$ and corrupted our stack!

This is the ABA problem: the pointer value changed from $A$ to $B$ and back to $A$, fooling the CAS. To defeat this ghost, we need more than just the address; we need to know if the pointer's history has changed.

The solution is to "tag" or "stamp" our pointers. Instead of the head being just a pointer, it becomes a pair: (pointer, version). Every time we successfully CAS the head, we increment the version number.

In our story, $T_1$ would read (A, version=0). After $T_2$'s shenanigans, the head would be (A, version=3). When $T_1$ wakes up and tries CAS(, (A, 0), (B, 1)), the comparison fails because the current version (3) does not match its expected version (0). The corruption is averted.

With the ABA problem tamed, we can move from the simple stack to a general-purpose linked list, where we can insert and delete anywhere.

​​Insertion​​ follows a beautifully safe principle: prepare new nodes entirely off to the side before making them public. To insert a new node $N$ after a predecessor $P$, we first set $N$'s next pointer to whatever $P$'s next pointer is currently pointing to. Only when $N$ is fully formed do we attempt a single CAS on $P.next$ to swing it to $N$. This ensures that any other thread traversing the list will either see the list before the insertion or after, but never a partially constructed, broken state.

​​Deletion​​ is far more devious. You cannot simply find a node's predecessor and CAS its next pointer to bypass the node. Why? Because while you are finding the predecessor, another thread might be at the very node you want to delete, about to read its next pointer! If you pull the rug out from under it, that thread will be left with a dangling pointer.

The solution is a graceful two-phase process: first mark, then remove.

1. ​​Logical Deletion (The Mark):​​ Instead of immediately unlinking a node, you first mark it as "logically deleted". This is often done by setting a special bit in its next pointer using a CAS. This CAS is the linearization point: the moment the deletion legally occurs. The node is now a ghost; it's physically in the list, but logically gone.
2. ​​Physical Deletion (The Unlink):​​ After a node is marked, it must be physically unlinked. This is done by a second CAS, on the predecessor's next pointer, to make it bypass the marked node.

The true beauty of this scheme is the ​​helping​​ mechanism. Any thread that encounters a marked node during its traversal can—and should—help complete the physical deletion. If a thread marks a node and then gets delayed, the system doesn't grind to a halt. Other threads will clean up the marked "ghosts" as they find them. This cooperative cleanup is the heart of what makes the algorithm ​​lock-free​​: it guarantees that the system as a whole always makes progress.

We've built a magnificent, intricate machine. We've defeated the ABA ghost with version tags. We've designed a cooperative deletion strategy. But one final, formidable challenge remains: What do we do with the memory of the nodes we've deleted?

If we immediately return a physically unlinked node's memory to the operating system, disaster strikes. A thread $T_1$ might still hold a pointer to that very node, which it read just before the node was unlinked. If the memory is freed and re-purposed while $T_1$ is paused, when it wakes up it will be holding a "dangling pointer" into garbage, leading to a "use-after-free" bug—the most dreaded of concurrent nightmares.

This reveals that versioned pointers on their own are not a complete solution. They solve the ABA problem for the CAS logic, but not the memory lifetime ABA problem. We need a ​​safe memory reclamation​​ scheme. We can't free memory until we are absolutely certain no thread is still looking at it. Two main strategies emerge.

1. ​​Hazard Pointers (HP):​​ This is a personal declaration system. Before a thread dereferences a pointer, it publicly declares it in its personal "hazard list". "I'm about to use this pointer, please don't delete it!" The memory manager, before freeing a block of memory, must check the hazard lists of all threads. If the memory is on any list, it cannot be freed. It's a simple, direct contract that prevents use-after-free errors.

2. ​​Epoch-Based Reclamation (EBR):​​ This is a synchronized batching system. Time is divided into "epochs". When a thread wants to read the list, it joins the current global epoch. When a node is deleted, it is placed on a "retirement list" for that epoch. The memory for nodes retired in epoch $E$ is only freed after a "grace period" has passed, which is defined as the moment when every single thread has moved on to an epoch greater than $E$. It's like waiting for everyone to leave a classroom before turning off the lights and locking the door.

These two approaches reveal a profound trade-off. In EBR, if a single thread stalls or gets stuck in an old epoch, it prevents any memory from being reclaimed system-wide, potentially leading to unbounded memory growth. In contrast, with Hazard Pointers, a stalled thread only prevents the handful of nodes it is actively looking at from being freed. The impact is localized.

The journey to a correct lock-free linked list is a masterclass in concurrent thinking. It begins with the simple power of a CAS, but quickly forces us to confront subtle ghosts like the ABA problem, the complexities of multi-phase operations, and finally, the fundamental problem of memory's lifetime in a world where time itself is relative. The resulting algorithms are a symphony of cooperation, where threads work in parallel, implicitly helping each other maintain a consistent and correct reality without ever needing to stop and wait.

Having journeyed through the intricate principles and mechanisms of lock-free linked lists, you might be asking yourself a perfectly reasonable question: "This is all very clever, but where does it live? What is it for?" It is a wonderful question, because the answer reveals that these abstract ideas are not just intellectual curiosities. They are the invisible, tireless architects of our entire digital world. We are about to see that from this one simple-sounding concept—linking nodes together without locks—we can build the core machinery of operating systems, databases, and the very fabric of the internet.

The most immediate and obvious thing we can do with a lock-free linked list is build other fundamental data structures. Imagine you have multiple workers—threads in a computer program—that need to communicate. One worker produces a piece of work, and another consumes it. How do you hand off the work? You could put it in a shared queue. The producer adds to the back, and the consumer takes from the front. A lock-free queue, such as the classic Michael–Scott queue, is a marvel of efficiency for this exact task. Using nothing more than atomic compare-and-swap (CAS) operations, threads can enqueue and dequeue items with minimal interference. If one thread is slow, it doesn't bring the whole system to a halt. This kind of queue is the beating heart of countless systems: it's how web servers distribute incoming requests to worker threads, how user interface frameworks process events, and how parallel computations divide up their tasks.

Of course, if we can build a queue (First-In-First-Out), we can also build its simpler cousin, the stack (Last-In-First-Out). A lock-free stack is even easier: you just add and remove items from the head of the list. And what is one of the most fundamental problems in computing? Managing memory. When a program is finished with a piece of memory, it "frees" it. Where does that memory go? It goes onto a "free list," ready to be reused. This free list is very often implemented as a stack. Using lock-free techniques, we can build an incredibly fast memory allocator where threads can grab and return memory blocks without ever waiting on each other. We can even get more sophisticated, creating an array of free lists, one for each common block size—a "segregated list allocator"—which is a common design in real-world malloc implementations. So, from the humble linked list, we have built a cornerstone of the operating system itself!

This all sounds wonderful, but nature does not give up her secrets easily. When you step into the world of lock-free programming, you encounter fascinating and subtle challenges—dragons that must be tamed with cleverness and insight.

One of the most famous is the ​​ABA problem​​. Imagine a thread that reads a memory location and sees the value A. It goes off to do some work, planning to come back and CAS that location, assuming it is still A. But while it's away, other threads come along, change the value from A to B, do some work, and then change it back to A. When our first thread returns, it looks at the location, sees A, and thinks, "Aha! Nothing has changed." But everything has changed! The A it sees now might be a pointer to a completely different piece of data that just happens to reside at the same memory address. A CAS based on this false assumption can lead to catastrophic list corruption.

How do we solve this puzzle? We need a way to know not just the value, but its history. One beautiful solution is to use "tagged" or "stamped" pointers. Instead of just storing the pointer A, we store a pair: (A, version). Every time the pointer is updated, we increment the version number. So the sequence becomes (A, 0) -> (B, 1) -> (A, 2). Now, when our original thread returns, it expects to see (A, 0), but it finds (A, 2). The CAS fails, and disaster is averted. This simple versioning is sufficient to guard against the ABA problem as long as the version number doesn't wrap around too quickly. Other solutions, like hazard pointers or epoch-based reclamation, solve the problem from a different angle: they prevent the memory manager from reusing address A until it's absolutely certain that no thread could possibly still be looking at the old A.

Another dragon is ​​performance​​. Lock-free does not always mean fast. Consider two threads trying to add to the head of a list. Thread 1 reads the head, and prepares its CAS. Thread 2 does the same. They both issue their CAS at the same time. Both fail. So they both immediately retry. They read the head again, prepare, and CAS again. They fail again. This can go on forever! The threads are all busy, burning CPU cycles, but no actual work is getting done. This is a pathological state known as ​​livelock​​. It's like two overly polite people trying to get through a doorway, each saying "after you," "no, after you," and neither ever moving. The solution is beautifully simple: break the symmetry. We introduce a little bit of randomness. After a failed CAS, a thread waits for a random amount of time before retrying. This "probabilistic backoff" makes it astronomically unlikely that the threads will keep colliding, and the system makes progress again.

This idea of contention leads to another key insight. Not all parts of a data structure are created equal. The head of a list is often a "hot spot" where many threads are trying to make changes. An insertion deep in the middle of a long list, however, is a much quieter affair; it's unlikely another thread is working on that exact same spot. We can analyze this mathematically. Using models from probability theory, like the Poisson process, we can calculate the expected number of retries for an insertion. The result confirms our intuition: the contention at the head is dramatically higher than in the middle. The number of retries for a head insertion can be orders of magnitude larger, especially as the list grows long. This isn't just an academic exercise; it tells designers of real systems to be wary of algorithms that focus all their activity on a single hot spot.

Armed with these robust and well-understood building blocks, we can now assemble far more complex and powerful systems.

A simple sorted linked list is slow to search. A ​​skip list​​ is a brilliant enhancement—it's a linked list with multiple "express lanes". Nodes are randomly promoted to higher-level lists that skip over many intermediate nodes, allowing for lightning-fast searches. We can build concurrent skip lists that allow threads to insert, delete, and search without locking the whole structure. Using a strategy of "optimistic search" (searching without locks) followed by locking only the few nodes that need to be changed, we can build high-performance, in-memory databases and search indexes that scale beautifully.

Another universal application is ​​caching​​. Almost every high-performance system, from a CPU to a web browser, uses a cache to keep frequently accessed data close at hand. A common strategy for deciding what to keep in the cache is "Least Recently Used" (LRU). Whenever an item is accessed, it is moved to the "most-recently-used" end of a list. When the cache is full and a new item needs to be added, the item at the "least-recently-used" end is evicted. This list is constantly being modified at the head, tail, and middle. Building a concurrent LRU cache requires a doubly linked list that can be safely modified by many threads at once. This introduces a new puzzle: deadlock. If threads lock nodes in an arbitrary order, they can end up in a circular wait. The solution is an elegant rule: always acquire locks in a fixed, global order (for example, by their position in the list or by their memory address). This simple discipline makes deadlock impossible, enabling the construction of efficient, scalable caches.

The real world is even more complex. An object in a system often participates in multiple relationships at once. Consider a task in an operating system scheduler. It might exist on a list sorted by priority, and at the same time on another list sorted by its deadline. When we need to delete this task, we must remove it from both lists, and this entire operation must appear atomic. This is a formidable challenge. A robust solution combines the techniques we've seen: first, an atomic CAS is used to "logically delete" the task by setting a flag. This single operation wins the race and ensures the deletion happens exactly once. Then, the winning thread can proceed with the physical cleanup, carefully acquiring locks on the task's neighbors in both lists (using a global lock order to prevent deadlock) and unlinking it. This pattern is the key to managing complex, interrelated states in large-scale concurrent software.

The journey doesn't end with the algorithm. For the ultimate performance, software must be in harmony with the physical hardware it runs on. Modern multi-core processors have a complex memory hierarchy. For a given CPU core, some memory is "local" and very fast to access. Other memory is "remote," belonging to another processor on the same chip, and is much slower to access. This is called ​​Non-Uniform Memory Access (NUMA)​​.

An algorithm that is unaware of this "memory geography" can suffer huge performance penalties. Imagine a naive implementation of our concurrent list where the head and tail pointers are stored in the memory of CPU 0, but threads on CPU 1 are constantly trying to access them. Every operation from CPU 1 will incur the high cost of a remote memory access. A much smarter, NUMA-aware strategy would be to design the data structure so that threads primarily operate on local memory. For example, one could partition the list or use per-node sentinels, ensuring that threads on CPU 0 work on one part of the structure and threads on CPU 1 work on another. By co-designing the algorithm and its data placement strategy with the hardware architecture in mind, we can achieve dramatic gains in throughput. This reveals a profound truth: the most elegant algorithm is one that respects the physical reality of the machine.

So, we see the full arc. We start with a simple, abstract principle—atomic updates on a linked list. This allows us to build the basic queues and stacks that form the plumbing of concurrent programs. We learn to tame the subtle dragons of the ABA problem, livelock, and contention hot spots. We then use these hardened building blocks to construct sophisticated caches, databases, and schedulers. Finally, we tune these structures to live in harmony with the physical silicon of the processor.

The next time you load a webpage, play a multiplayer game, or even just move your mouse across the screen, take a moment to appreciate the silent, furious ballet taking place inside your computer. Trillions of electrons are flowing, orchestrated by these incredibly clever, lock-free algorithms, ensuring that thousands of concurrent tasks cooperate seamlessly, efficiently, and correctly. It is the beautiful, unseen machinery that makes our modern world possible.