How to use CAS and java optimistic locking

What is CAS

CAS is CompareAndSwap, which is comparison and exchange. Why does CAS not use locks but still ensure safe data manipulation under concurrent conditions? The name actually shows the principle of CAS very intuitively. The specific process of modifying data is as follows:

1. Use CAS operation When data is generated, pass the original value of the data and the value to be modified to the method

2. Compare whether the current target variable value is the same as the original value passed in

3. If they are the same, it means that the target variable has not been modified by other threads. Just modify the target variable value directly.

4. If the target variable value is different from the original value, then it proves that the target variable has been modified. Other threads have modified it, and this CAS modification failed

From the above process, we can see that CAS actually guarantees safe modification of data, but there is a possibility of failure in the modification, that is, the target variable data If the modification is unsuccessful, at this time we need to loop to determine the result of CAS modifying the data, and try again if it fails.

Students who think more carefully may worry that the comparison and replacement operation of CAS itself will cause concurrency security issues. In actual applications, this situation will not happen. Comparison and replacement are performed by JDK with the help of hardware-level CAS originals. idiom to ensure that comparison and substitution is an atomic action.

CAS implements lock-free programming

Lock-free programming refers to the safe operation of shared variables without using locksIn concurrent programming, We use various locks to ensure the security of shared variables. That is to say, it is guaranteed that other threads cannot operate the same shared variable when one thread has not finished operating the shared variable.
The correct use of locks can ensure data security under concurrency, but when the degree of concurrency is not high and competition is not fierce, acquiring and releasing locks becomes unnecessary waste of performance. In this case, you can consider using CAS to ensure data security and achieve lock-free programming

Headache of ABA problem

We have already understood the principle of CAS to ensure safe operation of shared variables, but the above CAS The operation is also flawed. Assume that the value of the shared variable accessed by the current thread is A. During the process of thread 1 accessing the shared variable, thread 2 operates the shared variable and assigns it to B. After thread 2 processes its own logic, it assigns the shared variable to A. At this time, thread 1 compares the shared variable value A with the original value A, mistakenly believes that no other thread operates the shared variable, and directly returns the operation success. This is the ABA problem. Although most businesses do not need to care about whether there have been other changes to shared variables, as long as the original value is consistent with the current value, the correct result can be obtained. However, there are some sensitive scenarios where not only the result of the shared variable is equivalent to not being modified, but also It is not acceptable for shared variables to be modified by other threads in the process. Fortunately, there is a mature solution to the ABA problem. We add a version number to the shared variable, and the version number value will increase automatically every time the shared variable is modified. In the CAS operation, what we compare is not the original variable value, but the version number of the shared variable. The version number updated for each shared variable operation is unique, so the ABA problem can be avoided.

Specific application scenarios

CAS application in JDK

First of all, it is unsafe for multiple threads to perform concurrent operations on ordinary variables. The operation results of one thread may be used by other threads. Overwrite, for example, now we use two threads, each thread increases the shared variable with an initial value of 1 by one. If there is no synchronization mechanism, the result of the shared variable is likely to be less than 3. That is, it is possible that both thread 1 and thread 2 have read the initial value 1, thread 1 assigns it to 2, and the value read by thread 2 from the memory where it is located remains unchanged. Thread 2 also increases the variable by 1 and assigns it to 2, so The final result is 2 which is less than the expected result of 3. The increment operation is not an atomic operation, which leads to the unsafe problem of shared variable operation. In order to solve this problem, JDK provides a series of atomic classes to provide corresponding atomic operations. The following is the source code of the getAndIncrement method in AtomicInteger. Let us look at the source code to see how to use CAS to implement thread-safe atomic addition of integer variables.

<code>/**<br> * 原子性的将当前值增加1<br> *<br> * @return 返回自增前的值<br> */<br>public final int getAndIncrement() {<br>    return unsafe.getAndAddInt(this, valueOffset, 1);<br>}<br></code>

You can see that getAndIncrement actually calls the getAndAddInt method of the UnSafe class to implement atomic operations. The following is the getAndAddInt source code

<code>/**<br> * 原子的将给定值与目标字变量相加并重新赋值给目标变量<br> *<br> * @param o 要更新的变量所在的对象<br> * @param offset 变量字段的内存偏移值<br> * @param delta 要增加的数字值<br> * @return 更改前的原始值<br> * @since 1.8<br> */<br>public final int getAndAddInt(Object o, long offset, int delta) {<br>    int v;<br>    do {<br>    	// 获取当前目标目标变量值<br>        v = getIntVolatile(o, offset);<br>    // 这句代码是关键, 自旋保证相加操作一定成功<br>    // 如果不成功继续运行上一句代码, 获取被其他<br>    // 线程抢先修改的变量值, 在新值基础上尝试相加<br>    // 操作, 保证了相加操作的原子性<br>    } while (!compareAndSwapInt(o, offset, v, v + delta));<br>    return v;<br>}<br></code>

We are all familiar with locks, such as the reentrant lock ReentrantLock. The various locks provided by the JDK basically rely on the AbstractQueuedSynchronizer class. When multiple threads try to acquire the lock, they will enter a queue and wait, including multi-thread enqueue operations. The atomicity is guaranteed by CAS. The source code is as follows:

<code>/**<br> * 锁底层等待获取锁的线程入队操作<br> * @param node 要入队的线程节点<br> * @return 入队节点的前驱节点<br> */<br>private Node enq(final Node node) {<br>// 自旋等待节点入队, 通过cas保证并发情况下node安全正确入队<br>    for (;;) {<br>        Node t = tail;<br>        // head为空时构造dummy node初始化head和tail<br>        if (t == null) {<br>            if (compareAndSetHead(new Node()))<br>                tail = head;<br>        } else {<br>            node.prev = t;<br>            // 如果cas设置tail失败了<br>            // 下个循环取到了最新的其他线程抢先设置的tail<br>            // 继续尝试设置.<br>            if (compareAndSetTail(t, node)) {<br>                t.next = node;<br>                return t;<br>            }<br>        }<br>    }<br>}<br>/**<br> * 原子性的设置tail尾节点为新入队的节点<br> */<br>private final boolean compareAndSetTail(Node expect, Node update) {<br>// 可以看到此处又是调用了Unsafe类下的原子操作方法<br>// 如果目标字段(tail尾节点字段)当前值是预期值<br>// 即没有被其他线程抢先修改成功, 那么就设置成功<br>// 返回true<br>    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);<br>}</code>  
  

Optimistic locking application in enterprise development

In addition to the various atomic operations provided by the Uusafe class in the JDK, we actually During development, CAS ideas can be used to ensure safe database operation under concurrent conditions. Assume that the user table structure and data are as follows. The version field is the key to implementing optimistic locking

id	user	coupon_num	version
1	Zhu Xiaoming	0	0

假设我们有一个用户领取优惠券的按钮，怎么防止用户快速点击按钮造成重复领取优惠券的情况呢。我们要安全的更改id为1的用户的coupon_num优惠券数量，将version字段作为CAS比较的版本号，即可避免重复增加优惠券数量，比较和替换这个逻辑通过WHERE条件来实现. 涉及sql如下：

<code>UPDATE user <br>SET coupon_num = coupon_num + 1, version = version + 1 <br>WHERE version = 0</code>

可以看到，我们查询出id为1的数据， 版本号为0，修改数据的同时把当前版本号当做条件即可实现安全修改，如果修改失败，证明已经被其他线程修改过，然后看具体业务决定是否需要自旋尝试再次修改。这里要注意考虑竞争激烈的情况下多个线程自旋导致过度的性能消耗，根据并发量选择适合自己业务的方式

The above is the detailed content of How to use CAS and java optimistic locking. For more information, please follow other related articles on the PHP Chinese website!