一文彻底搞懂Lockfree/Lockless

IT知识刺客 2024-02-23

266

春节假期结束，开工。

《数据库传奇：被忽略的历史》第一部，科德与巴赫曼双雄传奇，已经接近尾声，读故事比读技术文章有意思多了吧，角度够新颖吧。但读读技术文章，还是少不了的。

《数据库传奇：被忽略的历史》第五集，马上推出，创作不易，关注、点赞、分享，是对IT知识刺客最大的鼓励。

正文开始。

这篇文章，本是为了回答一个和“无锁”相关问题：

https://www.zhihu.com/question/374142552/answer/3401692614

正好前面写了三篇《基础软件开发新坑 -- 神秘的MESI和坑爹的LockFree》，用这个回答，做为“神秘的MESI和坑爹的LockFree”最终章吧。

这篇难度系数很小，可以放心阅读。

前置知识：

CPU对数据的读、写，是针对L1 Cache。数据如果不在L1中，先要从下层（L2、L3、Memory）读入L1，再在L1中读、写。

L1 Cache有一个CacheLine的概念。一个CacheLine 64字节。（个别有128字节，或其他）

其实相当于“块“的概念。L1 Cache的块大小为64字节。

读、写时，先把数据所在块（也就是CacheLine，64字节），从下层读入L1，再在L1中读、写块中指定的字节。

多数CPU，x64、大部分的ARM等，在不跨L1 CacheLine的情况下，一次读、写都是原子的。

这些是前置知识。

下面，考虑一个问题，如果有这样一条链表：

图1

你沿着链表遍历，读“Next指针”时（只考虑读Next指针，暂时不考虑读更多数据），需不需要加锁。

这个问题其实就是，一个指针8个字节，有没有可能我读前4个字节时，后4个字节被其他进/线程给改了，导致我读出的8个字节，一半是新数据、一半是老数据。

根据前面的前置知识，我们知道，如果可以保证“Next指针”的8个字节不跨CacheLine，读“next指针”就是原子操作，不会读到一半新、一半旧的数据。

也就是说，只要合理的按排Node内存，保证Next指针不跨CacheLine，在遍历时，就不需要加锁。

（这里的遍历，只考虑读Next指针）

其实前面讨论的，是读、写并发时，读与写是否需要用锁来保障一致性。结论是，保证Next指针不跨CacheLine，不需要锁。

那么，再看写、写并发时的情况：

图2

如图2，现在两个进/线程同时在Node 3后增加一个新节点，就算在保证Node 3的“Next指针“不跨CacheLine，写”Next指针“是原子的，不会出现我写了前4个字节，你写了后4个字节这种情况。

但如果没有锁保护，很有可能Node 4_1成功修改了Node 3的Next指针，认为自己已经加入链表。但马上Node 4_2也成功修改了Node 3，把自己加入链表。就如图2中情况。

Node 4_1、Node 4_2，都认为自己在Node 3后面，但只有一个人是真的在Node 3后面。这就会出现问题。

读、写明明都是原子的，为什么这里会出现问题？

因为这里不是原不原子的问题，这里的问题是”同步“。

两个进/线程在两个核上同时发起对Node 3中“Next指针”的写操作，这个写操作是原子的，不会出现一个人写了前一半、另一个人写后一半。

但是，当进/线程2修改Node 3中“Next指针”时，它并不知道进/线程1刚刚完成了Node 3中“Next指针”的修改。你刚修改了，但我还不知道，以为你没修改，这就是“同步”问题。

其实原子问题，本质上也是同步。一个Core写L1 的CacheLine时，为了保证对应的内存不会出现写了前一半，后一半被另外Core写了，Core间也是需要同步的。

但这个“同步”被优化了，MESI协议就是用来优化这个同步的，不会每次读、写都同步，只要必要的时候同步。

MESI这块，这里不展开了，我之前写过一个系列专门讲这个，《基础软件开发新坑 -- 神秘的MESI和坑爹的LockFree》，有兴趣到这里看吧：

https://mp.weixin.qq.com/s/bt2YVej-vXTHPA1Nfi_mHw

https://mp.weixin.qq.com/s/Rf5A8n60PSYnQ6uRE3lhfw

https://mp.weixin.qq.com/s/3HcsiQp6-4pCOSUKfWCqEw

还有一个系列，也和这个问题相关，《HPC(高性能计算第一篇):一文彻底搞懂并发编程与内存屏障》：

https://mp.weixin.qq.com/s/FOmUP9YcMORpPxqrz_Ravw

https://mp.weixin.qq.com/s/lKRzDjjBmXKlGKtzZQb2HA

https://mp.weixin.qq.com/s/vZDZGv1n6Ihz3A5sv7coZA

考虑到大家的时间都比较紧，我简单的、不太严谨的，结合这个问题说一下上面几篇文章的结论。

这里我们还把MESI保证的一致性，称为原子性。

继续说原子和同步。原子性无法保证图2这种情况，两个进/线程同时修改Node 3中的“Next指针”，在原子性的保证下，它们的修改一先、一后，都成功完成了，但后完成的覆盖了先完成的修改。

这里的关键就是，“后完成的覆盖了先完成的修改”。如何让“后完成的”在修改时，能感知到Node 3的Next指针已经被修改了？

CPU专门提供了一个指令，比如x64中有一个可以加LOCK前缀的“比较并交换”指令：

LOCK cmpxchg reg, (mem)

（关于LOCK前缀的作用、延迟的测量、对程序的影响，《基础软件开发新坑 -- 神秘的MESI和坑爹的LockFree》1至3篇有详细分析）

假设原来的链表尾：Node 3，其Next指针为0。

多个进/线程同时使用带有LOCK前缀的比较并交换，CPU内部的具体步骤如下：

1) 比较Next指针是否为0。

2) 如为0，将Next指针修改为指向Node 4_1，返回成功。

3) 如不为0，不做任何修改，返回失败。

（返回成功、失败是如何体现的，可以查查cmpxchg指令，太细节的就不在这里讲了，后面再写文章描述）

也就是说，带LOCK前缀的比较并交换，可以在修改指定内存前，感知到该内存是否已经被修改。比较Next指针是否为0，就是感知是否已经被修改的过程。

使用它，就可以完美解决问题。如下图：

图3

如图3所示，虽然Node 4_1、Node 4_2的修改需求同时到达CPU，但毕竟有先后，就算真的是同时，CPU中也还有仲裁机制。

假设仲裁机制认为Node 4_1的写应该先执行。那么，Node 4_2的写将等待。

此时Node 3中的Next指针为0，比较Next指针是否为0，结果为“True”，Node 4_1地址被写入Node 3的Next指针。

然后，Node 4_2的等待可以继续了，它先比较Node 3 Next指针是否为0，结果为“False”，失败了，比较并交换指令然后什么都不做，结束。

之后进/线程可以重新发起加入链表的操作，把Node 4_2加入到Node 4_1后面。这就看你程序怎么写了，也可以干脆就放弃操作，……。

这就是无锁链表的本质。使用带 LOCK前缀的比较并交换，可以感知到其他Core最新的修改，但要牺牲掉性能。

“感知该内存是否被修改”，这个过程非常耗时。CPU中普通的指令，通常只要1个周期。就算是乘、除这样复杂的指令，十几个周期也能完成大部分乘除指令。

LOCK cmpxchg reg, (mem)指令，至少一、两百周期。在多路CPU的服务器中，甚至要400周期以上，是普通指令的几十、几百倍。

做为对比，MySQL中一次在Buffer Pool中搜索指定Buffer的HASH搜索，大概1000周期左右（Skylate-X微架构测得的结果）。

如果是多路CPU的服务器，两条LOCK cmpxchg指令，就差不多够MySQL完成一次HASH搜索。

因此，无锁，可并不意味着低延迟、高性能。这一点一定要注意。

无锁算法有很多变形，比如有环形链表的无锁：

图4

图中环中共有8个空间，当前指针指向4。

如果想从环中分配空间，当前指针指向的4号块，就是可用空间。分配空间结束，要把当前指针修改为5，指向下一块可用空间。

如果有多个进程同时分配内存、同时要求修改当前指针：

图5

如图5所示，有4个进程同时要求修改当前指针为5。也就是同时要求从环中分配空间。

它的伪码如下：

1）读取环的当前指针值：4

2）比较并交换：比较当前指针是否为4，如为True，修改当前指针为5。如为False，失败。

假设进程3更先一步，或它运气好被仲裁电路选中，如图6所示：

图6

进程3修改成功了，它得到4号空间，并成功修改当前指针为5。接着，如图7所示：

图7

其他三个进程继续抢着修改5为6。进程3开始使用4号块中的空间。

除了环状无锁，还有其他玩法，本质都是使用LOCK cmpxchg，在能感知到其他Core是否修改了目标内存情况下，完成目标内存的修改。

LOCK cmpxchg一次修改的内存，最多只能是8个字节，64个二进制位。

它的使用也十分有限，如果想并发的读、写超过64位，使用一条LOCK cmpxchg指令，无法保证一致性。

CPU一次读、写只能是64位（8字节），读、写超过8字节数据时，一定是多条指令，CPU不保证多条指令的原子性、一致性。这个时候，还是要使用“锁“。

锁的实现，也是通过LOCK cmpxchg。这里就不详细说了。

最后再强调一下，无锁也是要LOCK cmpxchg的（也有可能使用带LOCK前缀的其他指令），LOCK前缀的延迟很高，并不是使用了无锁，一切万事大吉，就低延迟、高性能了。

指针原子操作指令周期 cpu时间 next

文章转载自IT知识刺客，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

一文彻底搞懂Lockfree/Lockless

评论