ART最初提出没有考虑同步问题，本篇论文 The ART of Practical Synchronization是为ART设计的并发协议。
最传统的方式就是细粒度的锁读写锁和无锁了
本文提出了乐观Lock coupling和ROWEX(Read-Optimized Write Exculsion)。
简介
在传统数据库中用的最多的就是细粒度锁了，这种锁这需要占很短的时间——和磁盘I/O比起来是微不足道的。然而随着内存的增大，大多数据都能放入内存了，且细粒度锁严重影响了现代多核CPU的扩展性，同步就成了扩展性的瓶颈了。
乐观Lock Coupling
Lock Coupling是在B+树上的一种常见用法，并且对于ART来说实现起来更加简单——因为ART的插入与删除只会影响到当前节点和父节点，需要考虑两个方面，一是插入与删除导致的节点类型的变化，二是由于路径压缩，一些被压缩的路径由于插入创建节点或由于删除导致该节点的Partial key需要并入。（对比B树来说节点的分裂与合并会向上向下影响多个节点）。
（B+树上的Lock Coupling：查找的时候 获取孩子节点读锁，若孩子节点安全unlock父亲节点；插入与删除的时候，给孩子节点加写锁，若一个节点是安全的释放父亲节点上的所有锁； 乐观Lock Coupling是无论什么操作都是加写锁，只有发现节点需要分裂或合并的时候restart按前面的Lock Coupling再来一遍——这个乐观Lock Coupling和本文的这个应该叫乐观锁 Coupling完全不是一回事）
Lock Coupling足够简单，看起来像有很好的并发度，但事实并非如此即使是没有锁的冲突，原因在于树结构上的并发锁会导致不可避免的Cache miss，每次一个core获得一个节点的读锁(都需要写到这个节点里面)，都会导致其他core cache中的cache line里的副本失效。线程实际上在争夺lock持有的cache line的排他使用权。因此引入了乐观Lock Coupling
而乐观Lock Coupling可以显著提高扩展性。其不再预防多个线程并发修改一个节点，至多给父子两个节点加锁，基本的思想是假设没有冲突，用Version counter进行检测操作期间是否有修改，必要时restart。——极大减少了在共享内存位置上的写操作。
实现上，乐观锁用的是(写)锁+Version Counter
查找到一个节点，读的时候无需获得/释放锁，readLockOrRestart在得到当前节点的version前看锁有没有被占用，被占用就等待；然后检查父亲节点version是否改变，改变 restart
获得Version前看锁有没有被占用，前缀不配，给父节点加写锁，当前节点升级写锁，分裂前缀；前缀匹配.....
如前文提到的Lock Coupling读的时候每次都会加读锁——需要(物理地)写到这个节点上，导致cache miss，而乐观锁 Coupling只要一种锁就是写锁，避免这个问题
Read-Optimized Write Exclusion
乐观Lock Coupling的缺点是所有的操作都可能restart，这对于读操作来说是需要极力避免的。而ROWEX的优点就是一定成功，不会被阻塞，也不会restart。
与Latch-Free相比，只需要写的时候用少量的写锁来实现高扩展性是很划算的。
主要思想：修改需要先获得写锁，写锁不阻塞读，读也不用获得锁，不检查版本，写用原子性操作保证读是一致的。
Lock-Free经常有cache line失效的问题(?)
实现上
允许并发的本地修改，访问必须是原子的。C++ 11的std::atomic可以保证合适的内存屏障。
在原来的ART中节点内(Node4, Node16)是有序的，但是为了在读的时候能够并发的修改，在这里改成了无序存放（查找需要检查所有的key，但这在SIMD指令中并没有影响到性能）
节点的替换：节点满了需要扩张到更大的节点；或节点不满需要换成更小的节点
- 当前节点和父节点加锁
- 创建一个相应的新节点，把数据从老节点中复制过来
- 父节点指向旧节点的指针换成新节点的位置（CaS 原子操作）
- 旧节点unlock并标记为废弃，父节点unlock
writer等待锁的时候发现这个节点已经被标记为废弃了，需要restart。reader不用管废不废弃
路径压缩：
分成两步：1)添加新节点（绿色） 2)修改前缀(蓝色)
这两步都是原子操作，第一步就是在创建新节点之后CaS修改父节点里的指针就好；第二步是修改蓝色节点的前缀，这里的更新也是一个原子操作。
但是这两个操作不能合并为一个原子操作，也就是其他线程会看到中间状态。——为了解决这个问题，在每个节点前加了一个level（level的值是当前节点存的最后一个字符的位置，就像第一个蓝色节点，它的level是2，是E和T在字符串中的位置）——通过level保证图4中间的这个中间状态（绿色的中间节点加上了，蓝色节点中的前缀R还没有删除）就是安全的，直接跳过前缀（我觉得是因为已经知道了前面读过的key的长度，当前的level又是前面长度+1，当然直接跳过前缀）。还有一种情况，一个线程已经看到了修改过前缀的蓝色节点，但是不知道前面的绿色节点，这种情况也可以通过level解决（也是读到的长度和当前level的关系）。
评估
三个方面
扩展性
单线程-20线程下的性能与 关键参数的变化(时钟周期、指令数、L1 misses, L3 misses)
争用（冲突）
通过设置Zipf parameter(数据的访问频率问题，越大冲突越多)
String
代码的复杂度
总结与讨论
又征伐了一遍Lock-Free
作者认为Lock-Free的ART性能肯定不如乐观Lock Coupling ART和ROWEX ART。
网友评论