Some Methods to Reduce Competitive Locks in java

  java

Order

This paper introduces some ways to improve concurrency scalability: reduce the holding time of locks, reduce the granularity of locks, segment locks, avoid hot spots, and replace exclusive locks with non-exclusive locks or non-blocking locks.

Reduce lock holding time

An effective way to reduce the possibility of competition is to shorten the holding time of locks as much as possible. For example, some lock-independent codes can be moved out of the synchronization code block, especially those operations with high overhead and operations that may be blocked, such as I/O operations.

  • Before optimization
@ThreadSafe
public class AttributeStore {
    @GuardedBy("this") private final Map<String, String>
            attributes = new HashMap<String, String>();

    public synchronized boolean userLocationMatches(String name,
                                                    String regexp) {
        String key = "users." + name + ".location";
        String location = attributes.get(key);
        if (location == null)
            return false;
        else
            return Pattern.matches(regexp, location);
    }
}
  • postoptimality
@ThreadSafe
public class BetterAttributeStore {
    @GuardedBy("this") private final Map<String, String>
            attributes = new HashMap<String, String>();

    public boolean userLocationMatches(String name, String regexp) {
        String key = "users." + name + ".location";
        String location;
        synchronized (this) {
            location = attributes.get(key);
        }
        if (location == null)
            return false;
        else
            return Pattern.matches(regexp, location);
    }
}

Reduce the granularity of locks

Another way to reduce the holding time of locks is to reduce the frequency with which threads request locks (thus reducing the possibility of contention). This can be achieved by techniques such as lock decomposition and lock segmentation, in which a plurality of mutually independent locks are used to protect independent state variables, thus changing the situation that these variables were previously protected by a single lock. These technologies can reduce the granularity of lock operation and achieve higher scalability. However, the more locks are used, the higher the risk of deadlock.

  • Before optimization
@ThreadSafe
public class ServerStatusBeforeSplit {
    @GuardedBy("this") public final Set<String> users;
    @GuardedBy("this") public final Set<String> queries;

    public ServerStatusBeforeSplit() {
        users = new HashSet<String>();
        queries = new HashSet<String>();
    }

    public synchronized void addUser(String u) {
        users.add(u);
    }

    public synchronized void addQuery(String q) {
        queries.add(q);
    }

    public synchronized void removeUser(String u) {
        users.remove(u);
    }

    public synchronized void removeQuery(String q) {
        queries.remove(q);
    }
}
  • postoptimality
@ThreadSafe
public class ServerStatusAfterSplit {
    @GuardedBy("users") public final Set<String> users;
    @GuardedBy("queries") public final Set<String> queries;

    public ServerStatusAfterSplit() {
        users = new HashSet<String>();
        queries = new HashSet<String>();
    }

    public void addUser(String u) {
        synchronized (users) {
            users.add(u);
        }
    }

    public void addQuery(String q) {
        synchronized (queries) {
            queries.add(q);
        }
    }

    public void removeUser(String u) {
        synchronized (users) {
            users.remove(u);
        }
    }

    public void removeQuery(String q) {
        synchronized (users) {
            queries.remove(q);
        }
    }
}

Lock segment

In some cases, the lock decomposition technique can be further extended to decompose locks on a group of independent objects, which is called lock segmentation. For example, in the implementation of ConcurrentHashMap, an array containing 16 locks is used, each lock protects 1/16 of all hash buckets, where the nth hash bucket is protected by the (nmod16th) th lock. Assuming that the hash function has reasonable distribution and the keywords can be evenly distributed, then this can reduce the request for locks to about 1/16 of the original. It is this technology that enables ConcurrentHashMap to support up to 16 concurrent writers. (To enable systems with large number of processors to achieve higher concurrency under high traffic conditions, the number of locks can be further increased, but only when you can prove that the competition for concurrent write threads is fierce enough and you need to break through this limit can the number of lock segments exceed the default of 16. )

One disadvantage of lock segmentation is that it is more difficult and expensive to obtain multiple locks to achieve exclusive access than to use a single lock to achieve exclusive access. Generally, only one lock is required to be acquired at most when performing an operation, but in some cases, the entire container needs to be locked. For example, when ConcurrentHashMap needs to expand the mapping range and the hash value of the recalculated key value needs to be distributed to a larger bucket set, all locks in the set of segments need to be acquired.

@ThreadSafe
public class StripedMap {
    // Synchronization policy: buckets[n] guarded by locks[n%N_LOCKS]
    private static final int N_LOCKS = 16;
    private final Node[] buckets;
    private final Object[] locks;

    private static class Node {
        Node next;
        Object key;
        Object value;
    }

    public StripedMap(int numBuckets) {
        buckets = new Node[numBuckets];
        locks = new Object[N_LOCKS];
        for (int i = 0; i < N_LOCKS; i++)
            locks[i] = new Object();
    }

    private final int hash(Object key) {
        return Math.abs(key.hashCode() % buckets.length);
    }

    public Object get(Object key) {
        int hash = hash(key);
        synchronized (locks[hash % N_LOCKS]) {
            for (Node m = buckets[hash]; m != null; m = m.next)
                if (m.key.equals(key))
                    return m.value;
        }
        return null;
    }

    public void clear() {
        for (int i = 0; i < buckets.length; i++) {
            synchronized (locks[i % N_LOCKS]) {
                buckets[i] = null;
            }
        }
    }
}

Avoid hot spots

If a lock protects two independent variables x and y, and thread a wants to access x and thread b wants to access y (this is similar to in ServerStatus, one thread calls addUser and the other thread calls addQuery), then the two threads will not compete on any data, even if they will compete on the same lock. When multiple variables are requested for each operation, it is difficult to reduce the granularity of the lock. This is another aspect of balancing performance and scalability. Some common optimization measures, such as caching some repeatedly calculated results, will introduce some “HotField”, which often limit scalability. When implementing HashMap, you need to consider how to calculate the number of elements in the Map in the size method. The simplest method is to count the number of elements once every time it is called. A common optimization measure is to update a counter when inserting and removing elements. Although this slightly increases some overhead in methods such as put and remove to ensure that the counter is the latest value, this will reduce the overhead of the size method from O(n) to O(l).

In a single-threaded or fully synchronous implementation, using an independent count can improve the execution speed of methods like size and isEmpty, but it makes it more difficult to improve the scalability of the implementation, because every operation to modify map needs to update the shared counter. Even if the hash chain is implemented by using lock segmentation technology, the scalability problem existing when exclusive locks are used will be caused again when the access to counters is synchronized. The result of cache size operation, a seemingly performance optimization measure, has become a scalability problem. In this case, the counter is also referred to as a hotspot domain, because every operation that causes a change in the number of elements requires access to it. To avoid this problem, size in ConcurrentHashMap enumerates each segment and adds the number of elements in each segment instead of maintaining a global count. To avoid enumerating each element, ConcurrentHashMap maintains a separate count for each segment and maintains this value through the lock on each segment.

public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                (int)n);
    }
final long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }    

Instead of an exclusive lock

The third technique to reduce the impact of competitive locks is to abandon the use of exclusive locks, thus helping to use a friendly and concurrent way to manage shared state. For example, concurrent containers, read-write locks, immutable objects, and atomic variables are used. ReadWriteLock provides higher concurrency than exclusive locks. For read-only data structures, the invariance contained therein can completely eliminate the need for locking operations.

public class ReadWriteMap <K,V> {
    private final Map<K, V> map;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock r = lock.readLock();
    private final Lock w = lock.writeLock();

    public ReadWriteMap(Map<K, V> map) {
        this.map = map;
    }

    public V put(K key, V value) {
        w.lock();
        try {
            return map.put(key, value);
        } finally {
            w.unlock();
        }
    }

    public V remove(Object key) {
        w.lock();
        try {
            return map.remove(key);
        } finally {
            w.unlock();
        }
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        w.lock();
        try {
            map.putAll(m);
        } finally {
            w.unlock();
        }
    }

    public void clear() {
        w.lock();
        try {
            map.clear();
        } finally {
            w.unlock();
        }
    }

    public V get(Object key) {
        r.lock();
        try {
            return map.get(key);
        } finally {
            r.unlock();
        }
    }

    public int size() {
        r.lock();
        try {
            return map.size();
        } finally {
            r.unlock();
        }
    }

    public boolean isEmpty() {
        r.lock();
        try {
            return map.isEmpty();
        } finally {
            r.unlock();
        }
    }

    public boolean containsKey(Object key) {
        r.lock();
        try {
            return map.containsKey(key);
        } finally {
            r.unlock();
        }
    }

    public boolean containsValue(Object value) {
        r.lock();
        try {
            return map.containsValue(value);
        } finally {
            r.unlock();
        }
    }
}

doc