Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchcronization Method
（下文中的锁Lock指的都是Latch）
传统的细粒度锁在现在的CPU上扩展性很差，已经不适用了；而Latch-Free设计和实现上都非常复杂，开销很大(详细看前文)。而这里乐观锁耦合作为替代方案，同时具有扩展性强和易于实现的优点，而且尤其适用于树形结构。
传统上数据库使用的是细粒度锁来同步内部数据结构，但是虽然细粒度锁避免了锁的争用，但是仍会导致不好的可扩展性，主要在于锁的获取与释放都要写入共享内存，而由于现代多核CPU实现缓存一致性的方式，这种写入方式会导致额外的Cache miss，并且包含内部数据的缓存线会成为物理争用点。因此任何频繁访问的锁如树的根节点都严重限制了可扩展性。
而无锁结构，通常比基于锁的方法(尤其是以读取为主的工作负载)扩展性要好很多。但它有两个缺点：实现困难，复杂且容易出错的代码；硬件提供的原子原语功能有限(如原子的CaS只能是8byte)，复杂的操作需要在数据结构中进行额外的间接寻址——如Bw树中，需要一个间接表来获取下一个节点的地址，会导致额外的Cache miss增加开销。
乐观锁耦合OLC是集合基于锁的和无锁同步的同步方法。OLC有两种模式：第一种类似于传统的互斥锁，通过物理方式获取底层锁来排除其他线程；第二种，通过验证版本计数器version counter，读可以乐观进行。第一种用于写，第二种用于读。
OLC有以下几种乐观的特性
- 减少对共享内存的写入次数，减少cache miss，适用于大多数负载。(主要体现在乐观锁上，不用写只用验证)
- 与不同步代码相比，只需要增加很少的额外CPU指令
- OLC适用于BSL, tries, trie/B-tree混合和B-tree，这样的树形结构
- 与无锁模式相比，OLC也是单线程数据结构，易于使用，只需要少量的修改
相关工作
锁耦合是1977年提出的在B树上并发操作的方法。树遍历期间最多持有两个锁，读/写锁。
1981年B-link树。一次持有一个锁，在释放父锁和获取子锁之间，有节点拆分的中间状态，当发生拆分时，正在搜索的键可能在该节点的右兄弟节点。B-link树和锁耦合有相同的可扩展性问题(获得的锁数量相同)。
2001年乐观无锁索引遍历OLFIT，引入了版本计数器的概念，称之为乐观锁。OLFIT十分复杂
接下来20年，内存容量的增长导致对其他数据结构的大量研究。2010年的A practical concurrent binary search tree是第一个提出跨节点交叉验证的论文，而不是像OLFIT分别验证每个节点——"hand-over-hand, optimistic validation"。后来的MassTree基于相同的思想，用于复杂协议的部分使用。
关于ART提出了两个实用性强的并发控制协议ROWEX和OLC。而ROWEX需要修改底层的数据结构(在原始ART中节点内有序，为适应ROWEX改为了无序)。OLC无需对数据结构进行其他修改。
Bw-tree的研究也证明了OLC的优秀性能。而前文也表明了对于写密集的工作负载，有锁通常比无锁的同步性能更好。这仿佛在暗示OLC可以作为同步的通用标准，同步的范式。
乐观锁耦合
在传统锁耦合上，用的还是读写锁，获取释放锁都要写入共享内存导致cache miss。这样就算是只读的工作负载，根节点的锁仍然会成为争用的焦点。
悲观锁对于B树很不友好，因为根节点的修改非常罕见，但是遍历树的过程中都要锁定根节点。更乐观的方法，即不需要锁定内部节点，更有利于B 树。
乐观锁的工作
读操作：
1.读取锁的版本(如果锁未释放，restart)
2.访问节点
3.再次读版本验证访问期间没有修改
如果最后一步验证失败，restart。
写操作和传统的排它锁一样
1.获取锁(必要时等待)
2.访问/写节点
3.版本号++，解锁节点
传统lock coupling和opitmistic lock couping的对比
OLC代码
代码中readLockOrRestart读取版本，readUnlockOrRestart验证版本。
OLC的一个问题：从节点推测性读的指针可能会指向无效内存(如果该节点同时被修改)。取消这类指针的引用(如读它的乐观锁)可能会导致分段错误或未定义的行为。在上面的代码中第25行的检查可以规避这个问题，确保从包含指针的节点中读取的数据是正确的。
不太懂没有 这个额外的验证，代码将在27行取消引用23行中推测读取的指针。OLC另一个潜在的问题是不终止的代码。如果一个节点一直写，读总是restart-验证错误-restart这样的循环。
实现乐观锁，可以把锁和版本计数器合成一个64bit的word。典型的读操作原子地读版本计数器，在C++11中可以用std::atomic实现。
在x86中，由于x86强内存顺序保证，原子读是很便宜的。顺序一致的加载不需要memory fences。因此加载时std::atomic的唯一作用就是防止指令重排。这使得版本访问和验证很便宜。以排他模式获取和释放乐观锁与传统锁的代价相当。
OLC代码需要能够处理重新启动，因为验证或锁升级可能会导致并发失败。放在循环中的容易实现restart，这样的循环还可以限制乐观restart的次数，并在竞争严重的时候恢复到悲观锁模式。会退到传统锁能力是OLC健壮性的一个主要优势。
OLC在删除和重用节点时需要小心，因为删除线程不能确定某个节点可以被回收，因为其他线程仍然可能乐观地从该节点读取数据。因为需要使用如epoch-based回收, hazard pointers或optimized hazard pointers。
评估
对于查找，OLC直到20个线程时可扩展性仍可达到线性。
网友评论