Author: Code elder byte Public number: code elder byte

If need to reprint please contact me (WX ID) : MageByte1024

An overview of

The introduction of StampedLock in JDK 1.8 can be interpreted as an enhancement to ReentrantReadWriteLock in some ways, adding a mode called Optimistic Reading to the original read and write lock. This mode does not lock, so it does not block threads, resulting in higher throughput and better performance.

It is designed as an internal tool class for developing other thread-safe components to improve system performance, and its programming model is more complex than ReentrantReadWriteLock, so it is prone to deadlocks and thread-safe problems.

Learn what StampedLock brings to the table with questions from “Code Boy Byte”…

  • There are theReentrantReadWriteLock, why introduceStampedLock?
  • What is optimistic reading?
  • In the concurrent scenario of more reading and less writing,StampedLockHow to solve the problem of thread hunger when writer threads have difficulty acquiring locks?
  • What kind of scenarios are used?
  • Implementation principle analysis, is it through AQS or something else?

features

Three data access modes:

  • Writing lock:writeLockMethod blocks the thread waiting for exclusive access, analogicallyReentrantReadWriteLockIn write lock mode, only one writer thread can acquire lock resource at the same time.
  • Reading (pessimistic read lock) :readLockMethod that allows multiple threads to acquire pessimistic read locks at the same time. Pessimistic read locks are mutually exclusive with exclusive write locks and shared with optimistic reads.
  • Optimistic Reading: Note that this is Optimistic Reading, not locked. There will be no CAS mechanism and no blocking threads. Only if you are not currently in Writing modetryOptimisticReadIf there is no write mode thread to acquire the lock after obtaining optimistic read, then in the methodvalidateReturns true,Allows multiple threads to acquire optimistic reads and read locks. It also allows a writer thread to acquire a write lock.

Support read/write lock conversion

ReentrantReadWriteLock A thread that has acquired a write lock can be degraded to a read lock, but not vice versa.

StampedLock supports the conversion between read locks and write locks, making StampedLock applicable to more application scenarios.

Matters needing attention

  1. StampedLockIs a non-reentrant lock. If the current thread has already acquired a write lock, it will be deadlocked if it acquires it again.
  2. Don’t supportConditonCondition will thread wait;
  3. StampedLockThe write lock and the pessimistic read lock will return a stamp after being successfully locked. Then when unlocking, you need to pass in the stamp.

Explain the performance benefits of optimistic reading

So why is StampedLock performing better than ReentrantReadWriteLock?

The key is the optimistic read provided by StampedLock. We know that ReentrantReadWriteLock allows multiple threads to acquire the read lock at the same time, but when multiple threads read at the same time, all writer threads are blocked.

StampedLock’s optimistic read allows one writer thread to acquire the write lock, so it does not block all writer threads. That is, when there are too many reads and too few writes, the writer thread has the opportunity to acquire the write lock, reducing thread hunger and greatly improving throughput.

If you allow multiple optimistic reads and one thread to enter a critical resource operation at the same time, what if the read data may be wrong?

Yes, optimistic reading does not guarantee that the data read is up to date, so reading data to local variables requires passinglock.validate(stamp)Whether the prawns have been modified by the writer thread, if so, the pessimistic read lock is required, and the data is re-read to the local variable.

And because optimistic reads are not locks, they perform better without context switches caused by thread wake up and blocking.

In fact, with the database “optimistic lock” has the same wonderful, its implementation idea is very simple. Let’s take an example of a database.

Add a numeric version number field version to product_doc, increment version by 1 each time product_doc is updated.

select id. .version
from product_doc
where id = 123
Copy the code

Updates are performed only if version is matched at update time.

update product_doc
set version = version + 1.where id = 123 and version = 5
Copy the code

Optimistic locking of the database is to check version during query and verify version field during update. If the data is equal, it indicates that the data has not been modified and the data read is safe.

The version here is similar to StampedLock’s Stamp.

Use the sample

Mock write saves the user ID and user name data in the shared variable idMap, and provides the PUT method to add data, get method to get data, and putIfNotExist method to get data from the map. If not, simulate querying data from the database and putting the data into the map.

public class CacheStampedLock {
    /** * Share variable data */
    private final Map<Integer, String> idMap = new HashMap<>();
    private final StampedLock lock = new StampedLock();

    /** * Add data, exclusive mode */
    public void put(Integer key, String value) {
        long stamp = lock.writeLock();
        try {
            idMap.put(key, value);
        } finally{ lock.unlockWrite(stamp); }}/** * read data, read-only method */
    public String get(Integer key) {
        // 1. Try to read data in optimistic read mode without blocking
        long stamp = lock.tryOptimisticRead();
        // 2. Read data into the current thread stack
        String currentValue = idMap.get(key);
        // 3. Check whether it has been modified by other threads. True indicates that it has not been modified
        if(! lock.validate(stamp)) {// 4. On the pessimistic read lock and re-read data into the current thread-local variable
            stamp = lock.readLock();
            try {
                currentValue = idMap.get(key);
            } finally{ lock.unlockRead(stamp); }}// 5. If the verification succeeds, data is directly returned
        return currentValue;
    }

    /** * If the data does not exist, it is read from the database and added to the map@param key
     * @paramValue can be understood as data read from the database, assuming it is not null *@return* /
    public String putIfNotExist(Integer key, String value) {
        Optimistic reads can also be used by calling get directly
        long stamp = lock.readLock();
        String currentValue = idMap.get(key);
        // If the cache is empty, a write lock is attempted to read data from the database and write to the cache
        try {
            while (Objects.isNull(currentValue)) {
                // Try to upgrade the write lock
                long wl = lock.tryConvertToWriteLock(stamp);
                // Failed to upgrade write lock for 0
                if(wl ! =0L) {
                    // Simulate reading data from the database and writing it to the cache
                    stamp = wl;
                    currentValue = value;
                    idMap.put(key, currentValue);
                    break;
                } else {
                    // Upgrade failed, release the read lock and attach the write lock, retry through the looplock.unlockRead(stamp); stamp = lock.writeLock(); }}}finally {
            // Release the last lock
            lock.unlock(stamp);
        }
        returncurrentValue; }}Copy the code

In the example above, the get() and putIfNotExist() methods need to be noticed. The first one uses optimistic reads so that reads and writes can be executed concurrently. The second one uses a programming model that converts read locks to write locks, queries the cache first, reads data from the database when it does not exist and adds it to the cache.

When using optimistic reading, we must write according to the fixed template, otherwise it is easy to bug, we summarize the template of optimistic reading programming model:

public void optimisticRead(a) {
    // 1. Obtain version information in non-blocking optimistic read mode
    long stamp = lock.tryOptimisticRead();
    // 2. Copy shared data to thread local stack
    copyVaraibale2ThreadMemory();
    // 3. Check whether the data read in optimistic mode is modified
    if(! lock.validate(stamp)) {// 3.1 Check failed, upread lock
        stamp = lock.readLock();
        try {
            // 3.2 Copying shared variable data to local variables
            copyVaraibale2ThreadMemory();
        } finally {
            // Release the read locklock.unlockRead(stamp); }}// 3.3 If the check passes, the thread local stack data is used for logical operations
    useThreadMemoryVarables();
}
Copy the code

Usage scenarios and precautions

StampedLock performs well in high-concurrency scenarios with too many reads and too few writes. The problem of writer thread hunger is solved by optimistic read mode. We can use StampedLock to replace ReentrantReadWriteLock. However, it is important to note that StampedLock’s functionality is only a subset of ReadWriteLock. There are a few things to be aware of when using StampedLock.

  1. StampedLock Is not reentrant lock, use the process must pay attention to;
  2. Pessimistic read and write locks do not support conditional variablesConditonNote when this feature is needed;
  3. If a thread blocks on StampedLock’s readLock() or writeLock(), calling interrupt() on that blocking thread will cause a CPU spike. Therefore, do not call interrupt operations when using StampedLock. If you want to support interrupt functions, always use the interruptible pessimistic read lock readLockInterruptibly() and write lock writeLockInterruptibly(). This rule must be kept in mind.

The principle of analysis

We find that it is not like other lock by defining the inner class inheritance AbstractQueuedSynchronizer abstract classes and subclasses implement template method to realize the synchronization logic. However, the implementation idea is still similar, CLH queue is still used to manage threads, by synchronizing the state value state to identify the lock state.

Many variables are defined internally. The purpose of these variables is the same as that of ReentrantReadWriteLock. The state is shred by bit.

For example, if the write lock uses the eighth bit 1, it indicates that the write lock uses the eighth bit 1, and the read lock uses the 0-7 bit. Therefore, generally the number of threads that acquire the read lock is 1-126. After the number exceeds, the readerOverflow int variable will be used to save the number of threads that exceed the number.

Spin optimization

The multi-core CPU is also optimized to obtain the number of cores. When the number of cores exceeds 1, the thread will have spin operation for lock retries and queue money retries. It is mainly judged by some internally defined variables, as shown in the figure.

Waiting queue

The nodes of the queue are defined by WNode, as shown in the figure above. Nodes waiting for queues are simpler than AQS, with only three states:

  • 0: initial state.
  • -1: waiting.
  • Cancel;

There is also a field, cowait, that points to a stack to hold the reader thread. The structure is shown in the figure

Two variables are defined to refer to the head node and the tail node respectively.

/** Head of CLH queue */
private transient volatile WNode whead;
/** Tail (last) of CLH queue */
private transient volatile WNode wtail;
Copy the code

Another important point to note is cowait, which holds all read node data using a header interpolation method.

When read-write threads compete to form a wait queue, the data is shown below:

Access to write lock

public long writeLock(a) {
    long s, next;  // bypass acquireWrite in fully unlocked case only
    return ((((s = state) & ABITS) == 0L &&
             U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
            next : acquireWrite(false.0L));
}
Copy the code

This method does not respond to interrupts. Call writeLockInterruptibly() if an interrupt is required. Otherwise, high CPU usage may occur.

(s = state) & ABITS indicates that the read lock and write lock are not in use, so execute U.compareAndSwapLong(this, state, S, next = S + WBIT)) CAS operation to set the eighth bit to 1, indicating that the write lock is occupied successfully. If CAS fails, call acquireWrite(false, 0L) to join the queue and block the thread.

The acquireWrite(false, 0L) method is complex, using lots of spin operations such as auto-queuing.

Access to read lock

public long readLock(a) {
    long s = state, next;  // bypass acquireRead on common uncontended case
    return ((whead == wtail && (s & ABITS) < RFULL &&
             U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
            next : acquireRead(false.0L));
}
Copy the code

Obtain key steps of the read lock

(whead == wtail && (s & ABITS) < RFULL If the queue is empty and the number of read lock threads does not exceed the limit, Modify the STATE identifier to obtain read lock successfully through U.compareAndSwapLong(this, STATE, S, next = S + RUNIT) CAS.

Otherwise, acquireRead(false, 0L) is called to attempt to acquire the read lock using spin, failing which, the lock is queued.

acquireRead

When thread A acquires the write lock and thread B acquires the read lock, the acquireRead method is called, and it joins the blocking queue and blocks thread B. The method is still very complicated internally, and the general process is as follows:

  1. If the write lock is not occupied, the system immediately attempts to obtain the read lock. If the CAS status is changed successfully, the system returns.
  2. If the write lock is occupied, the current thread is wrapped as a WNode read node and inserted into the wait queue. If it is a writer-thread node, it goes directly to the end of the queue, otherwise it goes to the stack pointed to by WNode Cowait, the reader thread, at the end of the queue. The stack structure is a header insertion method to insert data and finally wake up the read node, starting from the top of the stack.

Release the lock

Whether unlockRead releases the read lock or unlockWrite releases the write lock, the overall process is basically through CAS operation. After the state is successfully modified, the release method is called to wake up the subsequent node threads of the head node of the waiting queue.

  1. You want to set the wait state of the head node to 0 to indicate that the successor node is about to wake up.
  2. Wake up The subsequent node obtains the lock through CAS, and if it is a read node, wakes up all the read nodes of the stack to which the COwait lock points.

Release read lock

UnlockRead (Long stamp) If the stamp passed in is the same as the one held by the lock, the non-exclusive lock will be released. Internally, the state is successfully modified through spin + CAS. Before modifying the state, it determines whether the number of read threads exceeds the limit. If it is less than the limit, change the state synchronization through CAS, and then call the release method to wake up the whead successor.

Release the write lock

UnlockWrite (Long stamp) If the stamp passed is the same as that held by the lock, the write lock is released, the WHEad is not empty, and the current node status is status! If = 0, the release method is called to wake up the subsequent node threads of the header.

conclusion

StampedLock cannot completely replace ReentrantReadWriteLock. The optimistic read mode allows a writer thread to acquire the write lock in a scenario where there are many reads and few writes, thus solving the problem of writer thread hunger and greatly improving throughput.

When using optimistic reads, you need to be careful to follow the programming model template, otherwise you can easily create deadlocks or unexpected thread-safety issues.

It is not a reentrant lock and does not support the condition variable Conditon. And when a thread blocks on readLock() or writeLock(), calling interrupt() on that blocking thread causes the CPU to spike. Be aware of calling the pessimistic read lock readLockInterruptibly() and the write lock writeLockInterruptibly() if thread interruption scenarios are required.

In addition, the thread awakening rule is similar to AQS, that is, the head node is awakened first. The difference is that when StampedLock awakens a read node, all read nodes of the stack pointed to by the cowait lock of the read node will be awakened, but the order of awakening is opposite to that of insertion.

Recommended reading

The following articles have been well received and received by readers, so I recommend reading them:

  • RESTful Best Practices
  • The principles of Tomcat architecture are analyzed for reference in architecture design
  • Tomcat high concurrency principle disassembly and performance tuning
  • Overview of database system design

Refer to the content

[Java advanced multithreading (11) — locks framework for J.U.C: StampedLock]