知识卡片
B+树并发控制的三级递进:锁耦合→乐观锁→无锁
B+树是动态调整的树形结构,多线程同时读写时如何保证正确性, 存在一条从”粗粒度阻塞”到”完全不阻塞”的优化路径,每一步都在 缩小加锁范围、减少线程互相等待的代价。最粗暴的方式是给整棵树 加一把全局锁,但这样每次写请求都会阻塞树上所有后续读写线程, 吞吐几乎无法扩展。锁耦合机制把粒度细化到节点级别:一个线程 访问时依次锁住从根到叶的路径上的节点,但不是一直攥着整条路径 的锁——父节点的锁可以在获取到子节点锁之后立刻释放,任意时刻 每个线程最多只占用父子两个节点的锁,这样把临界区压到最小,但 读线程和写线程仍然会互相阻塞。乐观锁机制进一步优化:读线程完全 不加锁,只是在访问节点前记录一个写版本号,访问完之后再检查 版本号是否变化——没变就说明这段时间没有写线程动过这个节点, 读取有效;变了就重做一次读取。这样写线程之间仍会互相阻塞,但 读线程彻底不会被写线程卡住,代价是写密集负载下写线程互相阻塞 的瓶颈依然存在。无锁机制(如Bw-tree)走得更远:把对页面的直接 修改变成一条追加在”修改记录链表”上的记录,而不是原地改写页面 本身,插入一条修改记录这个操作本身就能做成无锁的原子操作, 从而让读写线程都不会互相阻塞。这条演化路径的核心规律是:并发 控制优化的本质就是不断缩小”必须互斥”的范围,从整棵树,到两个 节点,到读写分离,最终到单条记录级别的原子操作。
结构图:
flowchart LR
A[全局加锁<br/>整棵树互斥<br/>吞吐几乎不可扩展] --> B[锁耦合机制<br/>节点级加锁<br/>父子最多两把锁]
B --> C[乐观锁机制<br/>读不加锁+版本号校验<br/>写线程仍互相阻塞]
C --> D[无锁机制 Bw-tree<br/>修改变为追加记录<br/>读写线程互不阻塞]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《新型数据库系统:原理、架构与实践》第4章"键值数据库
技术"4.4.2节"基于B+树的存储引擎"(源文件:
_epub-src/EPUB/xhtml/Section0001_0006.xhtml)
- 结论依据:原文分别说明锁耦合"路径上的节点的锁会更早地释放……
每个线程同时最多拥有两个节点的锁";乐观锁"为了实现无阻塞读
线程……每当读线程访问一个节点的时候,首先记录节点版本号……
如果节点写版本号发生变化,读线程重做对该节点的访问";无锁
机制"把直接对page的修改,变成一个修改的操作记录,加入到
'page value'……可以很容易变成一个无锁的方式来实现",三段
依次描述了加锁粒度和阻塞范围逐步收窄的演化过程。
- 原始内容:乐观锁机制试图减少写线程对读线程的阻塞,并进一步
减少加锁的数量……在乐观锁机制中,读线程是不会被阻塞的,但是
写线程会互相阻塞……无锁的设计能够使得读写线程互不阻塞,从而
有望实现更高的多核可扩展性。