Volatile, Lock-free, Immutable, Atomic in Java. How to understand and start using

Introduction

Hi, my name is Denis Agapitov, I am the head of the Platform Core group at Bercut.

Today I want to talk about one of the options lock-free algorithms in Java. Let's figure out how the keyword is connected to it volatile and pattern immutable.

Volatile

I think many have come across different definitions of the keyword volatile. Let us give some.

Definition of the keyword “in your own words”:

Keyword volatile used to denote
variables that can be changed by multiple threads. It
ensures that changes to a variable are visible to other threads.

If we dig deeper into JMM, we find this definition:

Entry in volatile variable happens-before each subsequent read of the same variable (A write to a volatile variable v happens-before all subsequent reads of v (by any thread).

Based on the definition volatilereading a primitive or reference will always correspond to the last written value without using any locks, such as on an object monitor, etc.

Lock-free

So what does this have to do with it? lock-free you ask? And despite the fact that if you mark the variable as volatilethen no locks need to be performed for reading and writing the primitive or reference.

Let's look at a code example that uses lock-free And volatile:

public class Configuration {
     
    private volatile boolean tracingEnabled = false;
     
    public void enableTracing() {
        tracingEnabled = true;
    }
     
    public void disableTracing() {
        tracingEnabled = false;
    }
     
    public boolean isTracingEnabled() {
        return tracingEnabled;
    }
     
}

In this case, each call to the code to request the need for tracing through the method isTracingEnabled does not require any synchronization or blocking. The last value set will always be returned.

In this case, if methods are called from the administration panel of our application enableTracing or disableTracingthen immediately after setting a new value for the variable tracingEnabledall running code will either write traces or stop doing so.

What if our application configuration is more complex? For example, we want to control the logging level on the fly. This can be easily done by extending our Configuration class:

public class Configuration {
     
    private volatile boolean tracingEnabled = false;
    private volatile Logger.Level logLevel = Logger.Level.OFF;
     
    public void enableTracing() {
        tracingEnabled = true;
    }
     
    public void disableTracing() {
        tracingEnabled = false;
    }
     
    public boolean isTracingEnabled() {
        return tracingEnabled;
    }
     
    public void setLogLevel(Logger.Level level) {
        logLevel = level;
    }
     
    public boolean isLoggable(Logger.Level level) {
        return logLevel.getSeverity() <= level.getSeverity();
    }
     
}

Immutable

So what does it have to do with it immutable you ask.

Let's look at a different approach to storing our configuration class data. Let's make named view settings key-value.

For compatibility, we will leave the already implemented methods for working with tracing and logging level:

public class Configuration {
     
    public static final String KEY_TRACING = "tracing";
    public static final String KEY_LOG_LEVEL = "logLevel";
     
    private volatile Map<String, String> parameters = new HashMap<>();
 
    public void setValue(String key, String value) {
        parameters.put(key, value);
    }
     
    public String getValue(String key) {
        return parameters.get(key);
    }
 
    public void enableTracing() {
        setValue(KEY_TRACING, Boolean.TRUE.toString());
    }
     
    public void disableTracing() {
        setValue(KEY_TRACING, Boolean.FALSE.toString());
    }
     
    public boolean isTracingEnabled() {
        String value = getValue(KEY_TRACING);
        return value != null && Boolean.parseBoolean(value);
    }
     
    public void setLogLevel(Logger.Level level) {
        setValue(KEY_LOG_LEVEL, level.getName());
    }
     
    public boolean isLoggable(Logger.Level level) {
        String currentLevel = getValue(KEY_LOG_LEVEL);
        return Logger.Level.valueOf(currentLevel).getSeverity() <= level.getSeverity();
    }
     
}

Here we see two new methods setValue And getValue. But this code is unsafebecause the keyword volatile complex object is marked and happens-before does not apply to the object itself, but only to the reference to it.

To solve this problem, a pattern comes to the rescue Immutable. Let's rewrite the code using this pattern to make it safe to use:

public class Configuration {
 
    ...
     
    private volatile Map<String, String> parameters = Collections.unmodifiableMap(new HashMap<>());
 
    public void setValue(String key, String value) {
        Map<String, String> map = new HashMap<>(parameters);
        map.put(key, value);
        map = Collections.unmodifiableMap(map);
        parameters = map;
    }
     
    public String getValue(String key) {
        return parameters.get(key);
    }
 
    ...
     
}

Here we have changed the method setValue. Now happens-before for correct installation of a new named value in our settings collection is provided. Method Collections.unmodifiableMap() optional – if the method call is removed, the code will still work, but it makes it clear that this collection cannot be changed.

This is useful for further possible expansion of the code. Or you can leave a comment that this collection should only be changed by assignment to a variable parameters new object that will never change.

Blockages

And yet they are needed in certain situations. If our administration panel is served by one thread (only one thread makes changes in the class Configuration), then the class code is thread-safe and works as lock-free algorithm.

But what if there are more writing threads? In this case, at the moment of reassembly immutable object, we may lose data from some threads. For example, to our method setValue two threads arrived, both created a copy of the collection parametersadded each of their parameters and replaced the link in turn. In this case, the data of the first stream that changed the link to the collection parameters will be lost.

What to do to secure changes from two or more threads? One option is to protect rebuild immutable object by blocking. Let's change the method setValueso that changing our configuration data is safe from 2 or more threads:

public class Configuration {
 
    ...       
     
    private volatile Map<String, String> parameters = Collections.unmodifiableMap(new HashMap<>());
 
    public synchronized void setValue(String key, String value) {
        Map<String, String> map = new HashMap<>(parameters);
        map.put(key, value);
        map = Collections.unmodifiableMap(map);
        parameters = map;
    }
     
    public String getValue(String key) {
        return parameters.get(key);
    }
 
    ...
     
}

In the above code we added synchronization across the object monitor Configuration during the reassembly of our immutable object and assigning a new link to our volatile variable.

This code is completely safe for use by multiple threads.

Atomic

Is it possible to write the same class completely? lock-free? Yes, we can. But for this we will need more than just volatileand atomic operations built on CAS (Compare and swap). They are implemented in the package java.util.concurrent.atomic.

Let's rewrite the method to use AtomicReference instead of volatile:

public class Configuration {
 
    ...
 
    private final AtomicReference<Map<String, String>> parameters = new AtomicReference<>(Collections.unmodifiableMap(new HashMap<>()));
 
    public void setValue(String key, String value) {
        for (;;) {
            Map<String, String> currentMap = parameters.get();
            Map<String, String> newMap = new HashMap<>(currentMap);
            newMap.put(key, value);
            newMap = Collections.unmodifiableMap(newMap);
            if (parameters.compareAndSet(currentMap, newMap)) {
                break;
            }
        }
    }
 
    public String getValue(String key) {
        return parameters.get().get(key);
    }
 
    ...
 
}

This code is completely lock-free and is safe to use from any number of threads. However, it is worth keeping in mind that if there are many writing threads, and our immutable the object is large, then you may see increased CPU and decreased latency of the writing method due to the fact that they will simultaneously rebuild the object and interfere with each other's execution compareAndSet.

Conclusion

Lock-free algorithms are used at Bercut in our ESB bus and in a number of services where it is necessary to achieve minimal response time.

The main pitfalls to consider when working with volatile + immutable This:

• This approach gives the best results with a load profile from 90% to 99.9(9)% for reading. If there are more write operations, it is better to switch to standard locks or read/write locks.

• Reassembling an object, especially a large one, uses a lot of additional memory. At the same time, it is necessary to take into account that released by reference volatile the old object is most likely already in old memory.

• If reassembling an object is a long process and there are many writing threads, then there is a risk of a long parking of some threads when a block occurs. In the case of AtomicReference you will have to use the CPU more actively and abuse memory consumption by creating many new objects.

However, if used in the right place, the approach can provide a performance boost to your multithreaded application.