ART最初提出沒有考慮同步問題，本篇論文 The ART of Practical Synchronization是為ART設計的并發(fā)協(xié)議。
最傳統(tǒng)的方式就是細粒度的鎖讀寫鎖和無鎖了
本文提出了樂觀Lock coupling和ROWEX(Read-Optimized Write Exculsion)。
簡介
在傳統(tǒng)數據庫中用的最多的就是細粒度鎖了，這種鎖這需要占很短的時間——和磁盤I/O比起來是微不足道的。然而隨著內存的增大，大多數據都能放入內存了，且細粒度鎖嚴重影響了現代多核CPU的擴展性，同步就成了擴展性的瓶頸了。
樂觀Lock Coupling
Lock Coupling是在B+樹上的一種常見用法，并且對于ART來說實現起來更加簡單——因為ART的插入與刪除只會影響到當前節(jié)點和父節(jié)點，需要考慮兩個方面，一是插入與刪除導致的節(jié)點類型的變化，二是由于路徑壓縮，一些被壓縮的路徑由于插入創(chuàng)建節(jié)點或由于刪除導致該節(jié)點的Partial key需要并入。（對比B樹來說節(jié)點的分裂與合并會向上向下影響多個節(jié)點）。
（B+樹上的Lock Coupling：查找的時候 獲取孩子節(jié)點讀鎖，若孩子節(jié)點安全unlock父親節(jié)點；插入與刪除的時候，給孩子節(jié)點加寫鎖，若一個節(jié)點是安全的釋放父親節(jié)點上的所有鎖； 樂觀Lock Coupling是無論什么操作都是加寫鎖，只有發(fā)現節(jié)點需要分裂或合并的時候restart按前面的Lock Coupling再來一遍——這個樂觀Lock Coupling和本文的這個應該叫樂觀鎖 Coupling完全不是一回事）
Lock Coupling足夠簡單，看起來像有很好的并發(fā)度，但事實并非如此即使是沒有鎖的沖突，原因在于樹結構上的并發(fā)鎖會導致不可避免的Cache miss，每次一個core獲得一個節(jié)點的讀鎖(都需要寫到這個節(jié)點里面)，都會導致其他core cache中的cache line里的副本失效。線程實際上在爭奪lock持有的cache line的排他使用權。因此引入了樂觀Lock Coupling
而樂觀Lock Coupling可以顯著提高擴展性。其不再預防多個線程并發(fā)修改一個節(jié)點，至多給父子兩個節(jié)點加鎖，基本的思想是假設沒有沖突，用Version counter進行檢測操作期間是否有修改，必要時restart?！獦O大減少了在共享內存位置上的寫操作。
實現上，樂觀鎖用的是(寫)鎖+Version Counter
查找到一個節(jié)點，讀的時候無需獲得/釋放鎖，readLockOrRestart在得到當前節(jié)點的version前看鎖有沒有被占用，被占用就等待；然后檢查父親節(jié)點version是否改變，改變 restart
獲得Version前看鎖有沒有被占用，前綴不配，給父節(jié)點加寫鎖，當前節(jié)點升級寫鎖，分裂前綴；前綴匹配.....
如前文提到的Lock Coupling讀的時候每次都會加讀鎖——需要(物理地)寫到這個節(jié)點上，導致cache miss，而樂觀鎖 Coupling只要一種鎖就是寫鎖，避免這個問題
Read-Optimized Write Exclusion
樂觀Lock Coupling的缺點是所有的操作都可能restart，這對于讀操作來說是需要極力避免的。而ROWEX的優(yōu)點就是一定成功，不會被阻塞，也不會restart。
與Latch-Free相比，只需要寫的時候用少量的寫鎖來實現高擴展性是很劃算的。
主要思想：修改需要先獲得寫鎖，寫鎖不阻塞讀，讀也不用獲得鎖，不檢查版本，寫用原子性操作保證讀是一致的。
Lock-Free經常有cache line失效的問題(?)
實現上
允許并發(fā)的本地修改，訪問必須是原子的。C++ 11的std::atomic可以保證合適的內存屏障。
在原來的ART中節(jié)點內(Node4, Node16)是有序的，但是為了在讀的時候能夠并發(fā)的修改，在這里改成了無序存放（查找需要檢查所有的key，但這在SIMD指令中并沒有影響到性能）
節(jié)點的替換：節(jié)點滿了需要擴張到更大的節(jié)點；或節(jié)點不滿需要換成更小的節(jié)點
- 當前節(jié)點和父節(jié)點加鎖
- 創(chuàng)建一個相應的新節(jié)點，把數據從老節(jié)點中復制過來
- 父節(jié)點指向舊節(jié)點的指針換成新節(jié)點的位置（CaS 原子操作）
- 舊節(jié)點unlock并標記為廢棄，父節(jié)點unlock
writer等待鎖的時候發(fā)現這個節(jié)點已經被標記為廢棄了，需要restart。reader不用管廢不廢棄
路徑壓縮：
分成兩步：1)添加新節(jié)點（綠色） 2)修改前綴(藍色)
這兩步都是原子操作，第一步就是在創(chuàng)建新節(jié)點之后CaS修改父節(jié)點里的指針就好；第二步是修改藍色節(jié)點的前綴，這里的更新也是一個原子操作。
但是這兩個操作不能合并為一個原子操作，也就是其他線程會看到中間狀態(tài)。——為了解決這個問題，在每個節(jié)點前加了一個level（level的值是當前節(jié)點存的最后一個字符的位置，就像第一個藍色節(jié)點，它的level是2，是E和T在字符串中的位置）——通過level保證圖4中間的這個中間狀態(tài)（綠色的中間節(jié)點加上了，藍色節(jié)點中的前綴R還沒有刪除）就是安全的，直接跳過前綴（我覺得是因為已經知道了前面讀過的key的長度，當前的level又是前面長度+1，當然直接跳過前綴）。還有一種情況，一個線程已經看到了修改過前綴的藍色節(jié)點，但是不知道前面的綠色節(jié)點，這種情況也可以通過level解決（也是讀到的長度和當前l(fā)evel的關系）。
評估
三個方面
擴展性
單線程-20線程下的性能與 關鍵參數的變化(時鐘周期、指令數、L1 misses, L3 misses)
爭用（沖突）
通過設置Zipf parameter(數據的訪問頻率問題，越大沖突越多)
String
代碼的復雜度
總結與討論
又征伐了一遍Lock-Free
作者認為Lock-Free的ART性能肯定不如樂觀Lock Coupling ART和ROWEX ART。
