图片来自 Gnist Design
前言
前几天研究 热点扣减场景的时候,比较深入的学习到无锁并发更新的常见算法 cas 的使用场景。本文是对CAS的自我学习笔记。
当涉及到多线程更新共享变量时,比如涉及到线程安全。如何解决呢?大家第一个反应必然是 加锁 来保障变量的数据一致性和安全性。
对于程序中的锁有两种,悲观锁和乐观锁。
使用悲观锁时,共享资源每次只给一个线程使用,其它线程阻塞,持有锁的线程释放锁之后,其他线程才可以申请锁,进而访问和操作共享资源。比较常见的MySQL 的表锁,行锁,python 中的threading模块的lock 等等。
使用乐观锁时,默认不会阻塞其他线程访问操作该对象,但是需要在更新的时候去判断该值有没有被其他进程更新过。通常使用CAS和版本号来实现乐观锁并发更新。
首先来看看维基百科对CAS的定义:
比较并交换(compare and swap, CAS),是原子操作的一种,可用于在多线程编程中实现不被打断的数据交换操作,从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较,当数值一样时将内存中的数据替换为新的值。
CAS 包含三个操作数:内存值V 预期原值A 和新值B。先比较内存值V与预期原值A是否相等,如果相等就将内存值V更新为新值B。如果不相等则返回,若CAS操作失败,会循环执行或到达某个终止处。
多并发的情况下从db中获取到一个值v,并计算,更新为新值new_v。比如v=100,线程1 扣减30 , 线程2 扣减50 。
线程1 T1 select v from t where id=1;线程2 T2 select v from t where id=1;
线程1 和线程2第一次获取v的值都为100,各自运算之后得到不同的值new_v。
线程1 T3 update t set v= new_v1 where id=1 ##结果 v=70线程2 T4 update t set v= new_v2 where id=1 ##结果 v=50
线程1扣减30之后v为70,线程2 扣减50 v为50,覆盖线程1更新的结果。显然两次更新的结果和实际的数据(100-30-50)是不一致的。那么如何使用 CAS方式解决呢?需要在where条件中 加上 v=old_value 的条件。
线程1 update v=v-30 where id=1 and v=100 #成功 v=70线程2 update v=v-50 where id=1 and v=100 #失败 affect rows=0
这样就能避免数据被覆盖更新的问题。
1.ABA的问题
如果一个变量v 被线程读取的时候是A,经过逻辑运算,更新的时候还是A,那么能确保该变量没有被修改过? 比如值从 A-->B-->A ,中间被修改为B,最后又修改为A ,这个就是CAS的 ABA 问题。如何解决呢?增加版本号的对比。取数据时,同时取出记录的版本号的值,更新的时候 将版本号加一。
select id,v,version from t where id=x;
update t set v=new_v ,version=version+1 where id=x and v=v_old and version=version_old;
优化之后的更新逻辑 v=100,version=0
线程1 update v=v-30,version=1 where id=1 and v=100 and version=0 #成功 v=70,version=1
线程2 update v=v-50,version=1 where id=1 and v=100 and version=0 #失败 affect rows=0
2.循环
如果并发更新失败,基于cas的方式会不断的循环重试,给cpu带来一定的压力,影响性能。
-The End-