非死book Folly源代碼分析
Folly 是 非死book 的一個開源C++11組件庫，它提供了類似 Boost 庫和 STL 的功能，包括散列、字符串、向量、內存分配、位處理等，用于滿足大規模高性能的需求。
6月初，非死book 宣布將其內部使用的底層 C++ 組件庫 Folly 開源，本文嘗試對 Folly 庫中的幾個重要的數據結構代碼進行分析，包括一些實現細節的討論、特點和不足的分析，以及在工程上的應用。本文將首先分析 RWSpinlock.h 和 ThreadLocal.h 的源代碼。
RWSpinlock.h
顧名思義，RWSpinlock 就是使用自旋方式進行臨界區資源等待的讀寫鎖，它與 pthread_rwlock_t有三個比較重要的區別。
- 通常情況下等待鎖的線程不會主動讓出 CPU，而是循環中不斷地嘗試獲取鎖。
- 使用原子操作處理讀者計數或寫者狀態，避免 pthread_rwlock_t無論讀寫的加鎖解鎖都要在互斥鎖的保護下進行。
- 提供類似數據庫中”更新鎖”的機制，在盡量提供更高并發的情況下，避免死鎖。
表 1 讀寫鎖狀態相容矩陣
</li> </ul>RWSpinlock 實現中幾處值得關注的地方如下。
自旋鎖在鎖粒度較小的情況下，使用自選等待方式等鎖，可以避免較高的上下文切換代價。而為了自適應多次獲取鎖失敗的情況，可以主動讓出 CPU。Folly 的實現比較簡單，硬編碼為在自旋 1000 次后仍無法獲取鎖的情況下，以后的每次循環都調用 sched_yield 主動讓出 CPU 以調度其他線程上來運行（要研究更復雜的自適應鎖機制，可以參考 Solaris 內部實現的 Adaptive locks 或注 1 提到的論文）。但在獲取讀鎖次數遠大于寫鎖次數的情況下，RWSpinlock 的讀優先機制可能造成寫者的饑餓，而主動讓出 CPU 的機制則可能加重寫者的饑餓程度。因此 Folly 中同時實現了可配置為寫者優先的 RWTicketSpinLockT 鎖。
與通常對讀計數器加 1 的思路不同，RWSpinlock 使用 int32_t的高 30 位保存讀計數，而使用最低兩位保存 upgrade 和 write 標記。在加解讀鎖時直接對 int32_t的鎖狀態原子加減0×4，直接避開了對最低兩位的修改，執行原子加0×4后再根據原子操作前的最低兩位是否有效，來決定是否需要回滾(減 0×4)。在多數只獲取讀鎖的情況下，不需要回滾，一次 ATOMIC_ADD 即完成讀鎖的加解鎖。
圖 1 使用比 ATOMIC_CAS 更高效的 ATOMIC_ADD 處理讀鎖的加鎖和解鎖
Folly 中的 RWSpinlock 還提供了類似數據庫中“更新鎖”的 upgrade 鎖，用于對鎖保護對象先讀后改時避免死鎖的需求，它與讀寫鎖的狀態相容矩陣如表 1 所示。
Write/Read/Upgrade 三種鎖狀態除了可以和初始狀態進行加解鎖的雙向轉換外，也可以在某些鎖狀態之間進行轉換，即原子的釋放原來的鎖并獲取到新的鎖，鎖狀態轉換如圖 2 所示。
圖 2 鎖狀態轉換
可以看出，除讀寫狀態外，其他任意兩個狀態之間都是雙向的轉換，只有讀寫之間是單向轉換，即在持有寫鎖的情況下，可以降級為讀鎖，而在持有讀鎖 的情況下卻不能升級為寫鎖。原因很簡單，在兩個及以上線程都持有讀鎖，并嘗試獲取寫鎖的情況下，由于釋放讀鎖和獲取寫鎖必須原子性的完成，而要獲取寫鎖就 要等待其他線程釋放讀鎖，在這種情況下線程將進入死鎖狀態。
因此某些對鎖保護對象需要先讀取再決定是否修改的情況，只能在讀取之前就加上寫鎖， 而在讀取后需要修改的情況很少時，這種方式代價就比較大，因為它阻塞了其他線程獲取讀鎖。Upgrade 就應運而生，從相容性矩陣可以看到，Upgrade 鎖與讀鎖相容，而與其他 upgrade 和寫鎖不相容，線程在讀取數據之前可以先獲取 upgrade，讀取數據之后，如果決定需要修改， 就升級為寫鎖。
一個具體的使用示例如下，如圖 3 所示，考慮實現一個在結點上加鎖的B+tree。
圖 3 結點加鎖B+tree 查詢
查詢操作，按照如下操作順序從根節點開始加鎖和查詢：
1. 對父節點加讀鎖；
2. 獲取子節點的讀鎖；
3. 釋放父節點讀鎖。
繼續在當前節點上執行第二步，直到查詢到葉子節點。
更新操作，按照如下操作順序從根節點開始加鎖和查詢：
1. 對父節點加 upgrade 鎖；
2. 獲取子節點的 upgrade 鎖；
3. 判斷子節點如果可能需要分裂或合并，升級父子節點為寫鎖；
4. 執行子節點分裂或合并，并修改父節點內容；
5. 釋放父節點鎖；
6. 繼續在當前節點上執行第二步，直到葉子節點，對葉子節點執行插入/刪除/修改。
因此在B+tree 的應用中，由于索引節點的分裂合并操作比較少見，使用 upgrade 鎖，避免與讀鎖的競爭，只有在必要時才升級為寫鎖。
關于C++0x 中 atomic 對象中的 memory_order，RWSpinlock 使用 std::atomic 保存上面提到的讀鎖計數、寫鎖標記、 upgrade 鎖標記，使用了 fetch_add、fetch_and、fetch_or、compare_exchange_strong 這幾個原子操作函數來修改鎖狀態。作者在不同的場景下使用了三種不同的 memory_order，與作者溝通，他的解釋如下：
For example, unlock_shared () can be delayed to other memory_order_release (or memory_order_relaxed)， but not memory_order_acquire, which means it ok for the compiler (and machine) to reordering unlock_shared () from different threads.
</blockquote>但從 gcc4.6.3 中 std::atomic 的實現和生成的匯編代碼來看，上面提到的幾個原子操作函數，直接使用了 gcc 提供的幾個以__sync 開頭的內置原子操作，忽略掉了傳入的 memory_order 參數。而只有 store 函數的行為針對不同的 memory_order 只有是否增加 mfence 指令的差別。最后，筆者的建議是在性能影響不大的的情況下，直接使用 std::atomic 默認的高級別的 memory_order，因為通過分析復雜的原子操作指令優化時序，來決定 memory_order，收益可能不及它帶來的風險。
寫者優先的 RWTicketSpinLockT 鎖，提供寫鎖優先的調度機制，在有線程等待獲取寫鎖的情況下，不再授予讀鎖，避免在大量加讀鎖的場景下，寫鎖很難獲取的問題。使用了 gcc 內置的原子操作__sync_fetch_and_add 和__sync_bool_compare_and_swap 替代 std::atomic，并且也沒有用到其他C++0x 特性，使用舊版本 gcc 的項目可以使用這個鎖。
Folly 注重效率，因此 RWTicketSpinLockT 中也有幾處值得關注的細節。
- 在等待獲取鎖的自旋中使用 pause 指令，一方面可以降低 CPU 的功耗，另一方面還可以幫助 CPU 優化指令流效率，具體可以參考注 2 的 Intel 白皮書。 而在寫鎖不優先的情況下，由于 pause 帶來的延遲可能導致寫鎖更不容易被獲取，因此獲取非優先的寫鎖不使用 pause 指令。
- 使用 SSE 并行指令，對多個地址連續的整數一個指令完成++操作。
- 減少分支判斷。見源碼 try_lock_shared ()的 old.users = old.read。將 users 與 read 是否相等的邏輯延遲到 CAS 操作時順便判斷，盡管在加不上讀鎖的情況下，要多執行兩個自加和一個 CAS 操作，但在加讀鎖成功的多數情況下，省去了一次分支判斷。
- 使用__sync_fetch_and_add 代替 __sync_bool_compare_and_swap。RWTicketSpinLockT 使用了名為 Write、Read、User 的三個計數器用來保存讀鎖計數和寫鎖標記，方法比較巧妙。讀鎖需要在 user 等于 read 的情況下才可以加上，而寫鎖則需要滿足 user 等于 write，加解鎖邏輯如下。 </ul>
- StaticMeta 為全局唯一結構，主要包括各個線程管理結構組成的鏈表的頭指針和對象 ID 生成器，用于全局析構和遍歷所有線程的私有對象。
- ThreadEntry 為線程私有結構，每線程對應一個，主要包括線程線程私有對象的指針數組，管理所有線程私有對象的指針，通過 ID 獲取指定對象的指針。
- ElementWrapper 是線程私有對象管理器，每個對象實例對應一個，主要包括指向對象實例的指針和對象的析構方法。 </ul>
1. 通過對 read 和 user 原子加一，獲取讀鎖，同時封鎖了加寫鎖的條件。
2. 通過對 read 原子加一，獲取寫鎖，同時也就封鎖了加讀鎖的條件；這里通過先對 read 加一，封鎖了后續讀鎖的條件，然后再等待寫鎖的條件被滿足，實現了寫鎖優先的邏輯。
3. 通過對 write 原子加一，釋放讀鎖，同時恢復寫鎖的加鎖條件。
4. 通過對 read 和 write 原子加一，釋放寫鎖，同時恢復讀鎖的加鎖條件。
可以看出寫鎖的獲取和讀鎖的釋放可以避免使用 CAS，而用一個原子加即可實現。
ThreadLocal.h
在服務器編程中，通常會遇到需要為每個線程都分配不同對象的情況，如線程處理一個請求需要使用的臨時內存、遠程調用需要臨時構造的參數等等。在 需要的時候臨時構造，不僅要付出構造成本，還會有內存申請釋放的代價，而使用線程主函數的棧對象，每一層都要傳遞參數也讓代碼很不便維護。
Folly 中實現的 ThreadLocal.h 提供了對象的線程局部存儲和訪問，其功能與 pthread_getspecific 相似，提供了更方便友好的調用方式， 線程退出后自動析構本線程內所欲的私有對象，并且提供遍歷所有線程私有對象的接口。實現上使用了 GCC 內置特性，實現比 pthread 庫更快的線程私有對象訪問。
ThreadLocal 內存布局如圖 4 所示，主要由 StaticMeta、ThreadEntry 和 ElementWrapper 三者組成。
圖 4 ThreadLocal 內存布局
假設要管理的線程私有類型為T，初始化和訪問線程私有對象的流程如下。
1. ThreadLocalPtr 對象構造時即從 StaticMeta 為它管理的類型申請了唯一 ID。
2. 使用 TheadLocalPtr::get 方法通過 ID 從 ThreadEntry 管理的 ElementWrapper 數組中獲取一個 ElementWrapper 對象。
3. 如果 ElementWrapper 中T的指針為空，則構造一個T的對象，指針和析構方法保存在 ElementWrapper 對象中。
4. 如果 ElementWrapper 中的T指針不為空，則直接返回。
在 Folly 的實現中值得注意的是：ThreadEntry 對象在每個線程中有一個，使用 gcc 內置的 static __thread 方式聲明 ThreadEntry，即可實現同一個名字在不同線程訪問到的是不同對象，需要注意的是這種方式僅適用于 POD 類型。由于直接訪問對象，這種方式比調用 pthread 庫的 pthread_getspecific 函數調用方式效率要更高。
但由于 ThreadEntry 是 POD 類型，在線程退出時不能自動析構釋放它管理的線程私有對象，因此在 StaticMeta 構造時會申請一個 pthread_key_t注冊線程退出時的回調函數，在回調函數中遍歷當前線程 ThreadEntry 管理的所有私有對象，依次調用它們的析構方法。因此在 Folly 的實現中，對 pthread 庫函數僅僅使用了它在線程退出時調用回調函數的功能。
此外還有兩處細節值得借鑒。
●ThreadLocal 還區分了單個線程退出和整體析構情況下，傳給析構方法不同的參數，以便用戶在必要的情況下區別這兩種情況下析構方法的實現。
●提供了指定立即析構釋放當前線程私有對象的方法，而不必等待線程退出時才釋放，這一點在單元測試多個 case 的情況下可能會使測試變得比較方便。
注釋
注1: Adaptive Locks: Combining Transactions and Locks for Ef?cient Concurrency
注2: Using Spin-Loops on Intel? Pentium? 4 Processor and Intel? XeonTM Processor
注3: A Provably Correct Scalable Concurrent Skip
注4: Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects
注5: Doug Lea. ConcurrentSkipListMap. In java.util.concurrent
作者李凱，現任淘寶核心系統部存儲組技術專家，花名郁白。2007-2010年曾參與百度分布式文件系統研發，2010年至今參與淘寶 Oceanbase 項目研發。