A wild Thread appeared! Multithreaded Testing and Thread-safety

Today we'll talk a little about how threads work on computers and how to extract more value from concurrent tasks. For this, I will present techniques on how to develop and especially how to test code that uses multiple threads, avoiding the main pitfalls that involve this theme.

Of course, along the way, you'll also learn more about Java's Concurrent package, non-blocking algorithms, immutability, and more. However, we need to start by talking a little bit about butter.

Butter is a product that is part of everyday life for many people. Present in cookies, cakes, bread, sweets, and snacks, as well as other culinary items that make our mouths water just imagining.

Butter is not recent; we have historical records of its manufacturing process over 2500 BC. Most often made with cow's milk but it can also be produced with the milk of other mammals such as sheep, goats, and buffalo.

Salt has been added to butter since ancient times as a method of preservation, but over time salt has lost this importance as the supply chain has become generally refrigerated. Today, so to speak, salt is added only for taste.

Sometimes food colorings are added to butter, in Brazil, for example, it is common to use Annatto seeds.

And one thing I really like to eat is bread and butter. In fact, a delicious slice of bread just out of the oven with a little butter on top, which starts to melt on the hot bread. Oh, how delicious!

Sadly, my wife happens to like hazelnut cream on top of her bread. And this created a problem with our breakfast, now we have to get two knives dirty to apply the toppings that we like. A knife for the butter, and another knife for the hazelnut cream.

However, our concern for the environment and its natural resources, which are not unlimited, made us rethink this process.

Let's turn this problem into a software. After all, Moore's law has given us processors with more and more cores, and as nowadays virtually all computers have multiple execution cores, a computer must be able to simulate my kitchen.

First, we need a straightforward Bread that takes 50 milliseconds to be ready (what a blazing fast oven, huh!?)

public class Bread {
   private String name = "bread";

   public Bread() {
       try {
           TimeUnit.MILLISECONDS.sleep(50);
       } catch (InterruptedException e) {
           Thread.currentThread().interrupt();
       }
   }

   public void setTopping(String toppingName) {
       this.name += " with " + toppingName;
   }

   @Override
   public String toString() {
       return this.name;
   }
}

Now we need a naive knife that can apply the topping to our bread.

public class Knife {
   private String topping;

   public Knife setTopping(String topping) {
       this.topping = topping;
       return this;

   }

   public Knife applyToppingTo(Bread bread) {
       if (topping != null) {
           bread.setTopping(topping);
           topping = null;
       }
       return this;
   }
}

We can verify that everything is working using a test. I'm using the AssertJ library, a java assertion library which I do recommend that you have a look on at, as it could enhance your tests and improve readability.

@Test
void givenKnifeWhenApplyToppingToThenChangeBreadName() {
   var knife = new Knife();
   var bread = new Bread();

   knife.setTopping("butter").applyToppingTo(bread);

   assertThat(bread).hasToString("bread with butter");
}

It seems good, lets's see what happens when we are hungry and want 10 pieces of bread made at the same time! For that, we will need a basket where we will put all the cooked bread.

@Test
void givenHungryThenCook10BreadsAtTheSameTime() {
   var basket = new ArrayList<Bread>();
   var knife = new Knife();
   for (int i = 0; i < 10; i++) {
       var bread = new Bread();
       knife.setTopping("butter")
               .applyToppingTo(bread);
       basket.add(bread);
   }
   assertThat(basket)
           .isNotEmpty()
           .allSatisfy(bread -> assertThat(bread).hasToString("bread with butter"));
}

Oops!, it worked, but it took too much time. Each bread takes 50 milliseconds to be ready, so now the whole process is taking 500 milliseconds. If we consider the real-world cook time for bread, it could take hours to cook all those pieces of bread like this.

Multiple Threads

I know what to do, we just need more workforce! I will call my wife to help me. As I said, the majority of current computer machines have more than one core, which allows us to work in parallel. Joshua Bloch, in his book Effective Java, warns that we should prefer executors, tasks, and streams to threads, but for simplicity let me demonstrate this problem using threads by hand.

@Test
void givenHungryThenCook10BreadsWithMyWife() {
   var basket = new ArrayList<Bread>();
   var knife = new Knife();
   Runnable preparation = () -> {
       var bread = new Bread();
       knife.setTopping("butter")
               .applyToppingTo(bread);
       basket.add(bread);
   };
   for (int i = 0; i < 5; i++) {
       var me = new Thread(preparation);
       var myWife = new Thread(preparation);
       me.start();
       myWife.start();
   }
   assertThat(basket)
           .isNotEmpty()
           .allSatisfy(bread -> assertThat(bread).hasToString("bread with butter"));
}

But wait, the test is failing, what is going wrong?

java.lang.AssertionError: 
Expecting actual not to be empty

It is like the basket is empty, but we didn't change the process at all despite adding the new threads. Yes, it is a common problem that every software engineer faces when starting to work with multiple threads (or multi-thread apps).

Java's Concurrent Package

In fact, there is a thread that is responsible for running the test suite which executes each step on our test in sequential order. But when we delegate part of the process to other threads, it follows its flow without waiting for them to finish their job. When it reaches the assertion, the previously created threads have not finished creating their bread. That is why our basket is empty.

Please, don't listen to this evil inner thought suggesting that it is just a matter of creating a Thread.sleep() or something like that, so that the assertion waits for the other threads. It will give you a slow and fragile test. On one hand, if you give it a big delay time, it will slow down your tests. On the other hand, with a small delay, the result could vary depending on the processing power of the machine where the tests are being executed.

Testing

The answer for cases like those is to use some tools from java's concurrent package. We have to ensure that both workers start to do their job at the same time. As a second requirement, we need that the test thread verifies the assertion only after the job is done by the other threads. For this, we can use a CountDownLatch like those below. CountDownLatch is a synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes. It does it by holding the thread until the count reaches 0.

@Test
void givenHungryThenCook10BreadsWithMyWife() throws InterruptedException {
   var basket = new ArrayList<Bread>();
   var knife = new Knife();
   var startGate = new CountDownLatch(1);
   var endGate = new CountDownLatch(10);
   Runnable preparation = () -> {
       try {
           startGate.await();
       } catch (InterruptedException e) {
           throw new RuntimeException();
       }
       var bread = new Bread();
       knife.setTopping("butter")
               .applyToppingTo(bread);
       basket.add(bread);
       endGate.countDown();
   };
   for (int i = 0; i < 5; i++) {
       var me = new Thread(preparation);
       var myWife = new Thread(preparation);
       me.start();
       myWife.start();
   }

   startGate.countDown();
   endGate.await();
   assertThat(basket)
           .hasSize(10)
           .allSatisfy(bread -> assertThat(bread).hasToString("bread with butter"));
}

The startGate will hold all threads so that they start virtually at the same time when the test execution reaches the startGate.countDown(). After that, the assertion will not be verified before the endGate reaches zero, which will only happen when all threads have finished their tasks.

The bad news is that we have a problem with this current implementation. If you are unlucky enough (or simply repeat this test a few times), you will face the following error:

java.lang.AssertionError: 
Expected size:<10> but was:<6> in:
<[bread with butter,
    bread with butter,
    bread with butter,
    bread with butter,
    bread with butter,
    bread with butter]>

It happened because we are using as our basket an ArrayList, which states in its documentation:

"Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally."

Synchronized Collections

In other words, this implementation of the List interface is not thread-safe. Once more, to face this issue, we have at our disposal other collection implementations on the concurrent package. Instead of ArrayList, we could use CopyOnWriteArrayList or a ConcurrentLinkedQueue.

As the first one is more efficient in use cases where mutations are less frequent than other operations, let's stick with ConcurrentLinkedQueue.

var basket = new ConcurrentLinkedQueue<>();

But as soon as you execute the test repeatedly, you will see errors like those:

java.lang.AssertionError: 
Expecting all elements of:
  <[bread with butter,
    bread with butter,
    bread with butter,
    bread with butter,
    bread with null,
    bread with null,
    bread with butter,
    bread with butter,
    bread with butter,
    bread with butter]>
to satisfy given requirements, but these elements did not:

  <bread with null> 
Expecting actual's toString() to return:
  <"bread with butter">
but was:
  <bread with null>

We should have a problem in another part of the code, could you imagine where it is?

Things get worse when my wife starts to make her bread with hazelnut cream:

@Test
void givenHungryThenCook10BreadsWithMyWife() throws InterruptedException {
   var basket = new ConcurrentLinkedQueue<>();
   var knife = new Knife();
   var startGate = new CountDownLatch(1);
   var endGate = new CountDownLatch(10);

   Function<String, Runnable> preparation = topping -> () -> {
       try {
           startGate.await();
       } catch (InterruptedException e) {
           throw new RuntimeException(e);
       }
       var bread = new Bread();
       knife.setTopping(topping).applyToppingTo(bread);
       basket.add(bread);
       endGate.countDown();
   };

   for (int i = 0; i < 5; i++) {
       var me = new Thread(preparation.apply("butter"));
       me.start();
       var myWife = new Thread(preparation.apply("hazelnut cream"));
       myWife.start();
   }

   startGate.countDown();
   endGate.await();
   assertThat(basket)
           .hasSize(10)
           .haveExactly(5, new Condition<>(bread -> bread.toString().contains("butter"), "butter bread"))
           .haveExactly(5, new Condition<>(bread -> bread.toString().contains("hazelnut"), "hazelnutcream bread"));
}

First, notice the use of a new helper method from AssertJ, we specified that the collection should have exactly 5 items that satisfy a condition.

The Condition entity from the AssertJ library helps us to create a whole new set of assertions. If you are interested, please take a look at a delicious example in the appendix of this article.

But let's come back to our bread story. After executing the test now with hazelnut cream, sometimes we face errors that are even strange:

java.lang.AssertionError: 
Expecting elements:
<[bread with hazelnut cream,
    bread with hazelnut cream,
    bread with hazelnut cream,
    bread with hazelnut cream,
    bread with butter,
    bread with hazelnut cream,
    bread with butter,
    bread with butter,
    bread with hazelnut cream,
    bread with hazelnut cream]>
 to have exactly 5 times <butter bread>

Why do we have only 3 bread with butter, but 7 bread with hazelnut cream?

Summary so far

Before advancing, let's recap what we have seen until now:

• Most today's computers have multiple cores, allowing us to get even more value from concurrent tasks;

• Working with multiple threads creates some difficulties when we depend on timing to verify our tests' assertions, nothing that couldn't be handled using tools from java's Concurrent package, like CountDownLatch;

• AssertJ is a java assertion library that helps us to improve our tests also on their readability.

• We should keep in mind that not all classes are thread-safe, like ArrayList for example. When many threads will share access to a common collection, we should use one of the thread-safe Collection implementations from the Concurrent package;

Ok, with all that knowledge in mind let's figure out what is the reason for the weird errors that we are facing.

Thread-safety

Race Condition

First of all, this is a typical symptom of a Race Condition, or more specifically, a Data Race. Quoting Brian Goetz, in the book Java Concurrency in Practice

"A race condition occurs when the correctness of a computation depends on the relative timing or interleaving of multiple threads by the runtime; in other words, when getting the right answer relies on lucky timing."

On our baking issue, we have multiple threads fighting to access the same shared property. My wife and I are fighting for toppings at the same knife.

In the real world, one could think of it like this:

1. I get my knife and put butter on that;

2. Just when I leave the knife to take the bread, my wife gets that knife and puts hazelnut cream on it;

3. I take back the knife and, with tears in my eyes, realize that I'm topping my bread with some strange brown cream;

4. Now my wife with her bread in hand stares at an empty knife, trying to figure out who is sabotaging her.

It could only work if each one of us does the topping at the perfect timing, that is, only getting the knife when the work of the other one is done.

About our code, we have at least two problems in it: 1) we set the topping and add it to the bread in two different steps; and 2) when we add the topping to the bread, its removal from the knife also occurs in a separate step.

Because of that, just before a thread applies the topping to the bread, another thread could change the topping or even remove it. And again, just before removing the topping from the knife, another thread could use that knife to add topping to other bread.

That is why in the last two test logs we got some bread without topping, and more bread with one of the toppings than the other.

Atomicity

We wrote those naive classes just to enlighten the lack of atomicity in them, but even single-line codes like ++i are not atomic, in fact, it comprehends three operations: 1) get the value; 2) add one to it; and 3) update the value back.

What we should do is enforce the concept of atomicity, which means that each of our tasks should be considered as one. One indivisible task, an atom.

Java has a built-in mechanism that allows us to achieve atomicity, which is called “synchronized block”.

synchronized(lock) {
	// Code that handles the shared memory
}

We can use any java object to act as a lock, and it will ensure that only one thread that acquires that lock will be able to execute the code within. When the thread finishes its job, it releases that lock so that other threads could do the same thing.

It is also allowed to create a synchronized method, just by adding the synchronized keyword before the return type of the method. Doing so, the lock will be the object on which the method is being invoked.

Ok, let's stop talking, and let's get our hands dirty!

@Test
void givenHungryThenCook10BreadsWithMyWife() throws InterruptedException {
   var basket = new ConcurrentLinkedQueue<>();
   var knife = new Knife();
   var startGate = new CountDownLatch(1);
   var endGate = new CountDownLatch(10);

   Function<String, Runnable> preparation = topping -> () -> {
       try {
           startGate.await();
       } catch (InterruptedException e) {
           throw new RuntimeException(e);
       }
       synchronized (knife) {
           var bread = new Bread();
           knife.setTopping(topping).applyToppingTo(bread);
           basket.add(bread);
           endGate.countDown();
       }
   };

   // (...) omitted for brevity
}

Now the fix of our code is just a matter of adding a synchronized block using the knife as the lock. With this, only one thread at a time can take the knife and execute the code inside it.

Thread blocking

"Oh! This is the solution for everything, we should synchronize everything!" Think twice. Synchronization isn't for free; it creates a performance problem, as now all other threads are blocked waiting for the availability of the lock, which in our case is the knife.

In our kitchen, we could say that when my wife touches the knife I become blocked, waiting for her. If the phone rings, she should say: "darling, please answer the phone". But I will be blocked, I'll not be able to do anything except wait for her to leave the knife.

A blocked thread goes to the TIMED_WAITING state, and during this time it can not be used. It is really advisable to keep track of how many threads our applications are using because threads are a scarce resource.

But there is light at the end of the tunnel, at least in this concern you should know that Java 19 is coming up with the concept of Virtual threads, in its Project Loom. This new feature will cut the one-to-one relationship between Java threads and OS threads, which means that more than one Java virtual thread will be able to use the same OS thread. With that, when some virtual thread gets blocked by an I/O operation, for example, another virtual thread can perform calculations on that same OS thread.

But, as we said, until there we should use our threads with wisdom.

Nonblocking Algorithms

"But, what to do?", you could ask. Well, if you need better performance you can use Nonblocking Synchronization. Nonblocking algorithms are widely used by JVMs implementations, Operational Systems, and in Java itself to implement locks and other concurrent data structures.

Those Nonblocking algorithms are way more complicated to design and implement, but they provide better performance by avoiding the thread block itself and give us other benefits like being immune to Deadlock.

To provide a simple example of Deadlock, imagine that my wife and I are in the living room. The remote controller of the TV and the sofa are Locks. To watch TV, a person needs to sit on the sofa and press the button on the remote controller. A Deadlock would occur if I get the remote controller and my wife sits on the sofa. She will be blocked waiting for the remote controller, and I'll be blocked waiting for the sofa. And we will be like that "until death does us part."

Let's go back to the Nonblocking algorithm. First of all, we need a way to ensure atomicity to our tasks. And it is possible because modern computer processors have special instructions for managing access to shared data. A common approach is the implementation of the compare-and-swap (CAS) instruction. It guarantees us that the access to the value and its update will occur as a single task.

Java's Concurrent package provides us with some so-called atomic classes. Let's take AtomicInteger as an example, its documentation states that it is "An int value that may be updated atomically".

The following code shows us the same algorithm, but only the last one achieves thread-safe by delegating its thread-safety to an AtomicInteger:

class Counter {
   private Integer count = 0;

   public void incrementCount() {
       this.count = count + 1;
   }

   public int getCount() {
       return count;
   }
}

class ThreadSafeCounter {
   private AtomicInteger count = new AtomicInteger();

   public void incrementCount() {
       this.count.incrementAndGet();
   }

   public int getCount() {
       return count.get();
   }
}

And how does AtomicInteger ensure atomicity? Using the CAS algorithm! Its incrementAndGet method executes a code that could be simplified like this:

private int value;

public final int incrementAndGet(int expectedValue) {
   int oldValue;
   do {
       oldValue = value;
   } while (!compareAndSetInt(oldValue, oldValue + 1));
   return oldValue;
}

To start, it gets the current value and stores it in a local variable. Then using the compareAndSetInt method it first checks if, at that precise moment, the current value is the same that was earlier fetched. If it is so, it proceeds with the update and then returns True. If the current value was changed by another thread, the compareAndSetInt method returns False and restarts the process.

It is worth saying that the compareAndSetInt method is a native method, which uses the most efficient instructions provided by the underlying hardware.

With this new knowledge, what about trying it on our bread? Let's remove the blocking synchronization and create the faster bread with butter that a computer could have (and some with hazelnut cream too, for the sake of my wife's happiness). We can do this using an AtomicReference.

public class Knife {
   private final AtomicReference<String> topping = new AtomicReference<>();

   public Knife setTopping(String topping) {
       while (!this.topping.compareAndSet(null, topping)) {}
       return this;
   }

   public Knife applyToppingTo(Bread bread) {
       String currentTopping;
       if ((currentTopping = topping.getAndUpdate(s -> null)) != null)
           bread.setTopping(currentTopping);
       return this;
   }
}

Of course, we did that after removing the synchronized block from our test. Good, fast, and easy, and without thread blocking! But, please pay close attention to this piece of code. We have some problems there as it is some kind of adaptation of the canonical CAS algorithm.

The hard part of building nonblocking algorithms is to isolate the shared memory into an atomic single change. But in our baker issue, we have a two-step action: first, we set the topping to the knife, and then we add the topping to the bread. So we have two states to keep track of: the knife and the bread.

As we said, this code works and does not block the thread, but doesn't give us all the advantages of the CAS algorithm, because we still can have a Livelock issue.

A Livelock issue can occur even when the thread is not blocked, if it is waiting for an operation that will never succeed. In our code, we used the topping value as a kind of lock. The first thread that moves it from null to another value, it will put all other threads waiting for that value to become null again. It works, but if any thread fails to add the topping to the bread, which moves the topping value back to null, all the other threads will be waiting forever.

The control mechanism, when more than one thread fights for the knife topping, is done by retrying again immediately, like in the CAS. But the canonical CAS will not fail indefinitely if any other thread fails. It will just finish its job as soon as no other thread touches the shared memory when it is still working.

Immutability

"So, what to do!? I'm reading this to find answers, not questions!" Ok, I'll let you know. The other side of the coin, in the context of thread safety, is Immutability. If we use an immutable object, virtually all problems with atomicity are gone. That's because all problems that we are facing here are based on threads fighting to access the same shared memory. If the memory that they want to access cannot be modified, those risks are gone and thread safety is achieved.

We can summarise that an Immutable object is one that can't be changed after its creation.

Java introduced the Record, which is a simple way to create immutable objects. We just need to provide the type and name of the fields. The public constructor, equals, hashCode, and toString methods, along with the private, final fields, are all given for free to us, by the compiler.

Take a look at the following code:

public record Knife (String topping) {

   public Knife setTopping(String topping) {
       return new Knife(topping);
   }
   public Knife applyToppingTo(Bread bread) {
       if (topping != null)
           bread.setTopping(topping);
       return new Knife(null);
   }
}

Some could argue that immutable objects are a waste of resources, but it isn't true in the majority of cases. Dealing with immutable objects offers us performance advantages when it frees us from using synchronization or creating defensive copies, it even reduces the impact on generational garbage collection.

But talking about defensive copies, is the record really immutable? Look at this test:

@Test
void givenReferenceToRecordThenItShouldBeImmutable() {
   record Parent(String name, List<String> childrenNames){};
   var childrenNames = new ArrayList<>(List.of("Haru"));
   var parent = new Parent("Bruno", childrenNames);

   var parentBeforeNewChild = parent.toString();
   childrenNames.add("Ayumi");

   assertThat(parent).hasToString(parentBeforeNewChild);
}

This task will fail with the following log:

java.lang.AssertionError: 
Expecting actual's toString() to return:
  <"Parent[name=Bruno, childrenNames=[Haru]]">
but was:
  <Parent[name=Bruno, childrenNames=[Haru, Ayumi]]>

We have to keep in mind that in the way that we created the Parent record we have kept a reference to its internals. A record is still unmodifiable, but to achieve immutability you have to avoid exposing its inner state. In our example, we can avoid that by overriding the constructor and coping the list of children's names:

record Parent(String name, List<String> childrenNames){
   public Parent(String name, List<String> childrenNames) {
       this.name = name;
       this.childrenNames = new ArrayList<>(childrenNames);
   }
};

Now the test is successful, but we are still publishing the internal state of the record. The getter method for the property childrenNames is publishing the reference to the record's inner state, allowing it to be modified:

@Test
void givenReferenceToRecordThenItShouldBeImmutable() {
   record Parent(String name, List<String> childrenNames){
       public Parent(String name, List<String> childrenNames) {
           this.name = name;
           this.childrenNames = new ArrayList<>(childrenNames);
       }
   }
   var childrenNames = new ArrayList<>(List.of("Haru"));
   var parent = new Parent("Bruno", childrenNames);

   var parentBeforeNewChild = parent.toString();
   parent.childrenNames().add("Ayumi");

   assertThat(parent).hasToString(parentBeforeNewChild);
}

This code will fail as well:

java.lang.AssertionError: 
Expecting actual's toString() to return:
  <"Parent[name=Bruno, childrenNames=[Haru]]">
but was:
  <Parent[name=Bruno, childrenNames=[Haru, Ayumi]]>

To avoid that you have at least two options: override the getter and return a copy of our list, or the one that I prefer: save our internal state as an unmodifiable list:

record Parent(String name, List<String> childrenNames){
   public Parent(String name, List<String> childrenNames) {
       this.name = name;
       this.childrenNames = List.copyOf(childrenNames);
   }
}

Like this, every time someone tries to update our inner state, they will get a UnsupportedOperationException, which I believe is what we should expect from trying to modify something supposed to be immutable.

Summary so far

What we have seen so far?

• We learned more about Race Conditions, in real life and in the software, and the main solution tool from Java: the monitor pattern, using the synchronized keyword;

• After understanding the downside of locking, we were introduced to the compare-and-swap (CAS) nonblocking algorithm, which despite being hard to develop can lead us to better performance and protect us from Deadlock

• For the cases when we are unable to isolate our shared memory, or even in other scenarios where we just need more protection, we talked about immutability and how immutable objects can grant us thread safety.

• We then revisited the java Record, which is a fairly easy way to create an immutable object, but that is not immune to bad programming technic. To really achieve immutability in our objects we saw how we should avoid publishing its inner state.

Conclusion

Oh, it was an amazing journey, we started with a brief introduction about threads, how to properly test them, and we met some new friends from Java's Concurrency package. With new algorithms and tools under our belt, we are ready to travel to the multithreaded world riding our thread-safe software. I'll now eat my bread with butter, see you soon!

Appendix

Baking delicious cakes with AssertJ's Condition entity:

@Test
void testTheCake() {
   record Cake(String name, boolean hasFruit, int weightInKg){};

   var chocolateCake = new Cake("Chocolate", false, 5);
   var strawberryCake = new Cake("Strawberry", true, 3);

   var bakery = List.of(chocolateCake, strawberryCake);

   var heavyCakes = new Condition<Cake>(cake -> cake.weightInKg >= 3, "heavy cake");
   var bigChocolate = new Condition<Cake>(cake ->
           cake.name.contains("Chocolate") &&
           cake.weightInKg >= 5
           , "big chocolate");

   assertThat(bakery)
           .haveExactly(2, heavyCakes)
           .haveExactly(1, bigChocolate);
}