一個星期前，我寫了關于SQL Server里閂鎖（Latches）和自旋鎖（Spinlocks）的文章。2個同步原語（synchronization PRimitives）是用來保護SQL Server里的共享數據結構，例如緩存池里的頁（通過閂鎖（Latches）），鎖管理器哈希表里的鎖（通過自旋鎖（Spinlock））。接下里你會看到越來越多的全新同步原語（synchronization primitives），即所謂的無鎖數據結構（Lock-Free Data Structures）。那也是SQL Server 2014里建立內存中OLTP的一個基礎，因此在今天的文章里我會給你快速概況介紹下無鎖數據結構，還有它們提供了什么。

無鎖算法通過非阻塞算法保護共享數據結構。在以前的關于閂鎖（Latches）和自旋鎖（Spinlock）文章里你已看到，當它們不能獲得閂鎖或自旋鎖時，其他的線程會阻塞。當一個線程等待閂鎖，SQL Server把線程放入掛起（SUSPENDED）狀態，如果一個線程等待自旋鎖，這個線程會在CPU上積極自旋。2個方法都會導致阻塞情形，這就是我們想通過非阻塞算法（Non-Blocking Algorithm）避免的。維基百科對非阻塞算法有個漂亮解釋：

“Anon-blocking algorithmensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm islock-freeif there is guaranteed system-wide progress regardless of scheduling.”

來看下中文字幕：

非阻塞算法保證為共享資源競爭的線程，不會通過互斥讓它們的執行無限期暫停。如果有不管調度的系統級進程，非阻塞算法是無鎖的。

從這個解釋里得出的最重要的結論是一個線程不會被另一個線程阻塞。這是可能的，因為沒有傳統的鎖是用做線程本身同步的。我們來看一個具體的例子：

讓我們一步一步來分析這個代碼。首先，函數compare_and_swap的實現是通過一個直接在CPU級別上的原子硬件指令（atomic hardware instruction）——CMPXCHG來實現。我想演示下在CMPXCHG里實現什么樣的邏輯：你比較值與一個期望值，如果它們一樣的話，老的值會賦予新的值。因為CHPXCHG的整個邏輯是在CPU本身上作為一個原子單元實現的，沒有其他線程可以中斷這個匯編運算碼的執行。

為了存儲自旋鎖本身的狀態，名為lock的變量被使用。因此線程在整個循環里自旋轉，直到自旋轉鎖同步變量被解鎖。如果這個發生的話，線程可以鎖住同步變量，最后會進入在線程安全方式的臨界區（critical section）。這又是自旋鎖的簡單演示（非線程安全）——事實上事情比這個難，且復雜很多。

這個傳統方法的最大問題是，在線程同步里涉及到共享資源：自旋轉鎖同步變量lock。如果一個線程把持自旋鎖，且掛起了，當其他線程嘗試獲取自旋鎖就會卡在當型循環里。你可以通過引入無鎖代碼技術避免這個問題。

如你所見，Foo方法的實現已經完全改變了。不是嘗試去獲得自旋鎖，實現方法在原子加進行前，只是檢查是否有其它線程修改共享變量（原先是通過自旋鎖受保護）。這就是說沒有用到了共享資源，線程之間也不會彼此阻塞。這就是無鎖數據結構（Lock-Free Data Structures）和非阻塞算法（Non-Blocking Algorithm）的主要思路。

在SQL Server 2014里的內存中OLTP也使用同樣的方法來構建BW-TREE映射表的頁改變。因此就不會涉及到鎖，閂鎖和自旋鎖。如果內存中OLTP看到在映射表里的頁地址以in個改變，這就是說另一個線程已經開始在那頁上的修改——但還未完成（在CPU上同時有其它線程被調度）。在內存中OLTP里各個線程是相互合作來工作。因此如果線程看到映射表里的修改，就完成這個”掛起“操作是可能的——例如頁分裂。

一個內存中OLTP的頁分裂包含多個原子操作。因此一個線程可以開始一個頁分裂，另一個線程可以最后完成這個頁分裂。在以后的文章里我會討論這些頁分裂的更多信息，實現BW-TREE里改變，讓這個復雜方法成為可能。

在今天的文章里我向你介紹了無鎖數據結構背后的主要思路。這個主要思路是在線程本身嘗試執行一個原子操作前，檢查是否有其它線程完成一個操作。因此不需要通過像自旋鎖的同步原語來保護臨界區。自SQL Server 2014起，無鎖數據結構和非阻塞算法的思路已被內存中的OLTP使用。

感謝關注！