I've seen this exact pattern countless times in production codebases. A developer wants to track a global metric—say, the total number of requests processed across all threads—and they think they're being clever by avoiding heavy locks. They use a volatile variable, assuming that because the value is "visible" across threads, the update is safe. It isn't.

import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future
import scala.concurrent.Await
import scala.concurrent.duration._

object RequestTracker {
  @volatile var totalRequests = 0

  def increment(): Unit = {
    totalRequests += 1
  }
}

// Simulation: 100 threads each incrementing 1,000 times
val futures = (1 to 100).map { _ =>
  Future {
    (1 to 1000).foreach(_ => RequestTracker.increment())
  }
}

Await.result(Future.sequence(futures), 10.seconds)
println(s"Final count: ${RequestTracker.totalRequests}") 
// Expected: 100,000. Actual: Often 94,231 or some other random number.

The Invisible Lost Update

You'll notice the final count is almost always lower than 100,000. The culprit here is the += 1 operation. Even though totalRequests is marked as @volatile, that only ensures that when one thread reads the value, it gets the most recent write. It does not make the operation atomic.

Under the hood, totalRequests += 1 is actually three distinct steps: read the current value, add one to it in a local register, and write the result back. If two threads read the value 10 at the same time, both will calculate 11, and both will write 11 back. You just "lost" an entire increment. This is the classic race condition that plagues shared mutable state.

Switching to AtomicReference and the CAS Loop

To fix this without resorting to synchronized blocks—which would put threads to sleep and kill your throughput—we use Lock-Free programming. The heart of this is the Compare-And-Swap (CAS) operation. Instead of locking the variable, we tell the CPU: "Update this value to X, but only if the current value is still Y."

In Scala, we usually lean on java.util.concurrent.atomic.AtomicReference (or AtomicInteger for simple numbers) to handle this. Here is how I would rewrite that tracker to be truly lock-free:

import java.util.concurrent.atomic.AtomicInteger

object RequestTracker {
  // AtomicInteger uses a native CAS instruction under the hood
  private val counter = new AtomicInteger(0)

  def increment(): Unit = {
    counter.incrementAndGet()
  }

  def getTotal: Int = counter.get()
}

For more complex state than a simple integer, you can't use incrementAndGet. You'll need to implement a CAS loop manually using AtomicReference. It looks like this:

import java.util.concurrent.atomic.AtomicReference

case class State(count: Int, lastUser: String)

object GlobalState {
  val ref = new AtomicReference(State(0, "none"))

  def update(user: String): Unit = {
    var success = false
    while (!success) {
      val current = ref.get() // 1. Read the current state
      val next = current.copy(count = current.count + 1, lastUser = user) // 2. Compute new state
      
      // 3. Try to commit. If 'ref' is still 'current', it updates to 'next' and returns true.
      success = ref.compareAndSet(current, next)
    }
  }
}

Why This Scales Better Than Mutexes

You might be wondering why we bother with a while loop instead of just using a lock. When you use synchronized or a ReentrantLock, the operating system may "suspend" a thread that can't get the lock. Waking that thread back up (a context switch) is incredibly expensive in terms of CPU cycles.

Lock-free programming is optimistic. It assumes that most of the time, there won't be a collision. If there is a collision (the compareAndSet returns false), the thread doesn't sleep; it just immediately tries again. In high-contention scenarios, you might spin a few times, but you avoid the massive overhead of kernel-level thread scheduling. Just be careful: if your update logic inside that loop is computationally expensive, you can end up burning CPU cycles for nothing. Keep the "compute" part of your CAS loop lean.

📋 Practical Task

Implementation: Lock-Free Concurrent Stack (Treiber Stack)

Your task is to implement a simplified Treiber Stack. This is a classic lock-free data structure that allows multiple threads to push and pop elements without using any synchronized blocks or locks.

Requirements:

• Create a class LockFreeStack[T].
• Use an AtomicReference to hold the "head" of the stack.
• The stack should be composed of a simple Node case class (containing the value and a reference to the next node).
• Implement push(value: T): Unit using a CAS loop.
• Implement pop(): Option[T] using a CAS loop. If the stack is empty, return None.

Verification:
To test your implementation, spawn 50 concurrent futures that each push 100 items onto the stack, and then 50 concurrent futures that each pop 100 items. Verify that the final size of the stack is 0 and no items were "lost" or duplicated during the process.