作者 | 子札
來源 | 雲巔論劍
前言
所謂原子操作，就是要麼不做，要麼全做。在很多場景中，都有對原子操作的需求。在翻 aep 的 spec 文檔時，也發現了一個巧妙的方法。所以順便發散性地總結一下各種實現原子操作的方法，歡迎大家交流探討。
小粒度——指令
根據 intel 手冊卷三第八章的描述，x86 使用三種機制來實現原子操作：
- Guaranteed atomic operations。Guaranteed atomic operations 是指一些基本的讀寫內存操作，這些操作都是保證原子性的。一般來說，讀寫位於一個 cache line 中的數據是原子性的。
- bus lock，使用 LOCK# 信號和指令的 lock 前綴。鎖總線的方式很簡單，進行原子操作的 cpu 會在 bus 上 assert 一個 LOCK# 信號，此時其他 cpu 的操作都會被 block 住。
- cache lock，利用 cache 一致性協議（MESI 協議）來實現。如果要訪問的內存區域已經在當前 cpu 的 cache 中了，就會利用 cache 一致性協議來實現原子操作，否則會鎖總線。
Intel 早期 cpu（如 Intel386、Intel486、奔騰處理器）實現原子操作，是通過 bus lock 來實現的。這種實現的問題，是完全不相關的兩個 cpu 之間，也會相互競爭總線鎖，從而導致整體性能下降。在後來的 cpu 中，intel 對這一問題進行了優化。當要進行原子操作的內存已經被拉入 cache 中時，cpu 會使用 cache 一致性協議來保證原子性，這被稱為 cache lock。相比於 bus lock，cache lock 粒度更細，能獲得更好的性能。
x86 中，有些指令是自帶 lock 語義的，比如 XCHG，更新段描述符等等；另外一些指令可以手動加上 lock 前綴來實現 lock 語義，比如 BTS、BTR、CMPXCHG 指令。在這些指令中，最核心的當屬 CAS（Compare And Swap）指令了，它是實現各種鎖語義的核心指令。不同於自帶原子語義的 XCHG，CAS 操作要通過"lock CMPXCHG"這樣的形式來實現。一般而言，原子操作的數據長度不會超過 8 個字節，也不允許同時對兩個內存地址進行 CAS 操作（如果可以的話，免鎖雙向鏈表不是夢）。
原子操作中另一個繞不開的話題是 ABA 問題，水平有限，就不展開講了。簡單提一個例子，在 linux 內核的 slub 實現中，用上了一個宏 cmpxchg_double，這並不是同時對兩個內存地址進行 CAS 的黑魔法，而正是利用 CMPXCHG16B 指令解決 ABA 問題的宏函數，有興趣的可以深究一把。
大粒度
當原子操作的對象大小在 16 字節或者 8 字節以內時，一兩條指令就能實現原子操作。但是，當對象的大小較大時，實現原子操作的就需要其他方法了，比如加鎖和 COW。深究這兩種方法，可以發現，在本質上，它們還是將問題轉換成了 16 字節的原子操作。
加鎖
加鎖這個方式很好理解，只要一加鎖，整個臨界區的操作就可以被看作一個原子操作。
內核中提供了各種各樣的鎖，自旋鎖、讀寫鎖、seq 鎖、mutex、semaphore 等等，這些鎖對讀寫者的傾向各有不同，在是否允許睡眠上也有所不同。
簡單來說，自旋鎖和讀寫鎖的核心都是利用原子指令來 CAS 操縱一個 32 位/64 位的值，它們都不允許睡眠，但是讀寫鎖對於讀者做了優化，允許多個讀者同時讀取數據，而自旋鎖則對於讀寫操作沒有什麼偏向性。seq 基於自旋鎖實現，不允許睡眠，但是對寫者更為友好。mutex 和 semaphore 也是基於自旋鎖實現的，但是它們允許互斥區的操作陷入睡眠。
可以看到，加鎖這種方式，最核心的還是利用指令實現原子操作。
COW
針對大對象原子操作的另一種方式是 COW（copy on write）。
COW 的思想其實非常簡單，首先我們有一個指向這個大對象的指針，在需要原子性修改這個大對象的數據時，因為沒辦法做到 inplace 修改，所以就把這個對象的數據拷貝一份，在對象副本上修改，最後再原子性地修改指向這個對象的指針。可以看到，這裡最核心的地方是利用指令來實現指針的替換。
關於 COW，這裡舉一個 AEP 的例子。AEP 是一種存儲介質，這裡只需要知道它可以按字節尋址和數據在掉電後不消失即可。普通的磁盤，一般有扇區原子性的保證，也就是在將新數據寫入某個扇區的途中突然掉電的話，這個扇區上要麼完全沒有新數據，要麼新數據完全被寫下去了，不會出現一半新一半舊的狀態。扇區原子性的保證很重要，許多數據庫都依賴它，然而，AEP 這種存儲介質沒有這種保證，所以需要用軟件的方式來做這種保證，稱為 BTT。
BTT 的思路也很簡單，為了方便理解，後文我不引入 AEP 的術語來進行描述。
首先把整個存儲空間劃分成若干個 block，每個 block 有自己的物理塊號，然後再維護一個表來做邏輯塊號到物理塊號的轉換。給上層邏輯塊的數量略小於物理塊數量，這樣就會有一部分的物理塊沒有被映射，姑且稱為 free block。
比如下圖，4 個邏輯塊，5 個物理塊，其中 1 號塊是 free block。
接下來，在往一個邏輯塊上寫數據時，先找一個 free block，把數據寫上去，接下來去映射表中，將邏輯塊的映射修改該 free block。整個流程中，最關鍵的一步——修改映射關係——是原子性的。只要有這個保證，那麼就能夠提供 block 數據原子性更新的能力。
COW 的思想在很多地方都有，比如 qemu 的 qcow 鏡像快照，ext4 和 btrfs 在寫入數據時的 COW，linux 內核的 rcu 機制等等。此外，COW 最有名的使用場景莫過於 fork 的實現了，但是它只是單純的為了減少拷貝開銷，與原子性沒有太大關係。
COW 優化
COW 的方式，有個很麻煩的事情，就是每次都得原子性的去更新指針。那麼有沒有辦法去掉這個指針呢？有的。
這個是在 Intel 關於 AEP 的文檔上學到的另一種取巧的方式（注意，下面描述的例子和上文中的 BTT 沒有任何關係）。起因是這樣的：
AEP 的驅動使用一個稱為 index block 的結構來管理元數據，這個 index block 處於整個介質的起始位置，大小至少為 256 字節。有些操作會去更改它的多個字段的值，所以可能出現更改字段到一半的過程中掉電的情況，因此需要一種機制來保證更改過程是原子性的。
正常的 COW 方式，需要在起始位置處保留兩個 index block 大小的空間以及一個指針，其中一個 index block 作為備用。在修改 index block 的數據時，以 COW 的方式將全部的數據存儲在備用 index block 中，然後以 COW 的方式更改指針指向該備用 index block 中。
Intel 使用下面的機制來優化掉指針：
依然是兩個 index block，index block 中有一個稱為 seq 的字段。seq 是一個兩位的數，共有 4 個狀態。除去 00 狀態，還有 01、10、11 三個狀態，將這三個狀態視為一個循環，如下：
為了方便敘述，兩個 index block 分別命名為 blockA 和 blockB。
第一次寫入數據，寫入到 blockA 中，其上的 seq 為 01；
第二次寫入數據，寫入到 blockB 中，其上的 seq 為 10；
第三次寫入數據，寫入到 blockA 中，其上的 seq 為 11；
第四次寫入數據，寫入到 blockB 中，其上的 seq 為 01；
……
如此往復，在恢復時，只要讀取並比較兩個 index block 上的 seq 中哪個處於循環的前方，就能找到最新的那個 index block。這樣的優勢是顯而易見的，一是避免了額外的指針，或者說把指針固化到兩個 index block 中，避免了一個 8 字節指針對兩個 index block 對齊帶來的麻煩；二是少一次寫操作，提升了效率。
多對象
前面針對的都是一個個單個的對象，如果涉及到多個對象，要保證原子性就比較複雜了。比如，如果使用加解鎖的方式，就需要注意鎖的順序，防止死鎖的問題；如果是 COW 的方式，就需要注意中途失敗以後的把已替換的指針回滾回去的問題。從更大的格局來看，針對多個對象的原子操作，本質上就是進行一次事務操作。所以，這個問題的解法，參考事務的實現就好了。
寫日誌
事務的四大特徵 ACID，即原子性，一致性，隔離性和持久性，基本上是一個常識了，而原子性只是事務的一個特性。
寫日誌算是實現事務最通用的方式了，日誌一般分為 redo 和 undo 兩種日誌，為了加快恢復速度，一般還會引入檢查點（checkpoint）的概念。在文件系統和數據庫的實現中，基本上都能看到事務的身影。
寫日誌除了能保證原子性和一致性以外，還對磁盤這種外存設備很友好，因為寫日誌基本上都是順序的。在這一方面的典型案例，當屬日誌結構文件系統和 leveldb 的 LSM-tree 了。
leveldb 的原理想必不用再提了，它把對於 K-V 對的增刪改操作都變成一條條的日誌，然後持久化為磁盤上的一個個 SST，之後再觸發合併整理。這樣一來，基本上對於磁盤的所有操作都是順序的了。
日誌結構文件系統也是類似的思想，它將文件數據的增刪改操作直接變成日誌寫到磁盤裡面，文件的實際數據不需要單獨再存到某個地方，而是靠日誌恢復出來。這種做法對寫操作是非常友好的，但是讀方面的性能就有點差強人意了。
事務內存
事務通常是用於保證持久性數據一致性的。去掉持久性的要求，將事務的概念引入到對於內存對象的操控中，就有了事務內存的概念。
正如上文所說，對於多個對象的操作，加鎖和 COW 的方式，在使用時都比較麻煩。加鎖的方式要考慮加解鎖順序防止死鎖，中途失敗了還要按照特定的順序解鎖回滾；COW 也是一樣，雖然沒有死鎖的問題，但是在回滾上也是很麻煩的。另一個問題就是，針對不同的場景，加解鎖的順序要重新考慮，COW 的回滾也要重新考慮，不具有通用性。
事務內存機制則是為了解決這些問題而提出的，它把針對多個對象的原子操作抽象為一個事務，只要按照它提供的 api，以串行化的思路去編程就行了。不用考慮加解鎖的順序，也不必考慮回滾的問題，在遇到了某些 fatal error 時只要 abort 掉事務即可。這是一種通用的併發編程方式，簡化編碼的同時，還能保證併發的性能。
事實上，事務內存機制的內部實現，也是依賴於 COW 機制和加解鎖來實現的，更深一步，其實也是依賴於原子操作指令的。
總結
總結一下：
16 字節或 8 字節以內的內存數據，使用 cpu 的原子操作指令；
16 字節以上的數據，使用加鎖、COW 的方式，或者優化過的使用 seq 的 COW 方式，本質上還是依賴於原子指令；
針對多個對象的原子操作，引入事務或者事務內存的概念，實際上的實現要麼是寫日誌，要麼是依賴於 COW 或加鎖的方式，最終依賴於原子指令。
所以，萬變不離其宗，原子操作指令很關鍵。
參考文章：
https://pmem.io/documents/NVDIMM_Namespace_Spec.pdf
https://zhuanlan.zhihu.com/p/151425608
https://zh.wikipedia.org/wiki/%E8%BD%AF%E4%BB%B6%E4%BA%8B%E5%8A%A1%E5%86%85%E5%AD%98