本文轉自公眾號"lunewcome"。
有很多“奇技淫巧”的高并發，但基礎知識的掌握程度決定了我們所寫代碼的并發程度，對基礎足夠了解才能寫出并發性能更高的程序，所以本文先總結一些基礎，然后再看一些具體例子。這個總結不是從頭開始的詳細介紹，另外影響并發性能的因素很多，想必這里說的也不是全部。
整數讀寫的原子性
計算機保證讀寫整數或指針是原子的，只要地址是按字長對齊的。要注意的是這里的原子性并不是“線程安全”什么的，而僅僅是指不會讀到“亂七八糟”的值，比如有10個線程并發地往整數變量a中寫0~9，那么只會讀到0~9中的某個值而不會是其它任何值。
程序員視角下的緩存
總有人擔心寫指令是先寫到緩存，經過某一段時間后再“刷”新到內存，而在這段時間內其它線程讀不到最新值；還有一些文章總結了很多底層的或硬件的東西，比如“write buffer”。其實從程序員的角度看只要記住這兩點：
1）利用緩存提高性能，例如避免偽共享，注意緩存行大小
2）不需要在意緩存更新問題，這是由硬件通過MESI協議保證的，我們只要記住一個線程執行完寫入指令后，其它線程再從內存讀時就能拿到最新值。
注意第二點，可能有人會說“既然如此，為什么多線程并發寫一個整數，結果仍然是一個非確定的值”？其它第二點并不等同于線程同步操作，它只是緩存和內存之間的一致性，并不是指多線程寫緩存/內存時的一致性/同步。
執行順序與內存屏障（內存柵）
有兩個地方可能“亂序執行”：一是編譯器可能優化調整指令順序，二是為了提高性能現代cpu幾乎都是亂序執行（弱內存序），如powerpc和arm，常用的x86（強內存序）也不保證讀寫完全有序。這是不能用doube-check實現單例模式的原因。為了保證順序性，在一些關鍵地方就必須加入內存屏障。屏障的作用就是當它之前的語句全部執行完后，才能執行它后面的語句。這方面也有很多比較底層的文章，但單純從程序員的角度看，只要理解概念然后就老實用c++11提供的接口吧，原因是：
1）硬件差異大，但并不需要所有人去了解并解決。
2）c++11的封裝的是各平臺下能實現的最高性能，沒必要自己弄一套。
偽共享
緩存失效是指整個緩存行失效，而不是其中的一部分，所以如果多個cpu/核的緩存中保存了同一緩存行，根據MESI協議，當某一個cpu/核寫該緩存行時其余cpu/核上的緩存行都將失效。這個描述包含“真共享”和偽共享，當各cpu/核讀寫同一變量時就是“真共享”，讀寫不同變量時就是偽共享。“真共享”是我自己造的詞，沒見別人這么叫過，應該是因為它比偽共享容易察覺的多，不需要多說。偽共享的直接結果就是“cache miss”，這對性能影響很大，所以在關鍵數據結構上需要格外注意。只有理解了偽共享，才能知道用shard_ptr來回拷貝并非想象的那么高性能，才能知道讀寫鎖不是描述的那么美好，等等。
下面是一些實踐總結。
map
c++中的std::map，std::unordered_map都不是線程安全的，在多線程環境下需要加鎖。加一把“大鎖”當然安全但性能很差。一種簡單有效的辦法是仿效JAVA中的分段鎖：定義多個map，每個都用一個mutex來保護讀寫。訪問時首先判斷key落在哪個段，再對該段的mutex加鎖，然后就能安全地訪問對應的map了。通過這種分段的方式的降低了沖突概率，提高了并發，簡單而且性能不差。我在實際中一般用32或64個段，還沒有發現有瓶頸問題。
使用原子操作實現map能得到更好的并發性能，但要自己去實現。最好先看看用原子操作實現一個list有多麻煩再決定要不要實現無鎖map。
vector（可變長數組）：Append-only
如何實現高并發、線程安全的vector？我實現過這樣一樣鏈表式的數組：每個數組都是等長的，寫滿后就申請一個新的并用指針鏈接到當前數組后面。這樣就形成了一個“鏈表式的數組”，特點是順序讀寫性能好但隨機讀性能稍差。鏈接用的指針需要用一個原子操作，保證申請完新數組并適當初始化后再加入到鏈表中。
RCU（Read，Copy Update）
RCU的概念很早就有，linux內核2.6版本實現了相應接口。它的大致思想是：Read是無鎖的但要標記讀的開始，寫時首先Copy原內容，在拷貝上完成Update操作后替換原內容；待所有的Read都不再引用原內容后，刪除原內容。
RCU的關鍵就在于如何知道所有的Read都不再引用原內容，2.6版本的實現思路是讀時開啟“禁止搶占”，這樣讀時就沒有上下文切換，所以當寫端發現所有cpu都有過一次上下文切換后，就能確定所有Read已經走出了保護區域，不再引用原內容。在更新的版本中，linux實現了分級RCU，能進一步提高并發，適應多cpu環境（成百上千個cpu的機器）。
操作系統要考慮的環境當然比應用程序復雜惡劣的多，而我們是可以用些取巧的辦法的：
1）我實際中實現過這樣一個雙buffer：一個用于讀，另一個用于寫，讀寫切換后再等待一段時間才刪除切換下來的buffer。這個雙buffer能工作的關鍵是“這段時間”比線上請求的耗時長得多，比如1~10s，而線上請求一般在ms級完成。
2）上面的vector也可以用類似思路實現，即容量時重新申請2倍大的空間，Copy原vector的內容，再切換兩個buffer的指針。這樣就能有很高的隨機讀性能，在不觸發擴容時寫性能也很高（大部分情況如此）。
brpc中的dbd（Doubly-Buffered-Data）
絕妙，是我第一次見到這個神奇操作時的感受，我實在驚嘆---真是想知道作者當初如何想到這樣巧妙的思路。直到我了解了RCU的實現，我猜測作者可能是受了RCU的啟發。和RCU類似，dbd也是適合讀多寫少的場景，并且也都要等待所有的讀完成。dbd也是一個雙buffer，和我的雙buffer不同的是：
1）定義thread local的mutex，每次讀buffer時先獲取該鎖
2）定義保證順序寫的mutex，寫時先獲取該鎖
3）寫操作切換buffer后，逐一去獲取1）中所有的thread local的mutex鎖，獲取后立即釋放。好玩的是這一步，請思考下為什么這樣就能保證所有讀都已經完成？
這和RCU是多么的相像！只不過一個是等待cpu一個是等待線程。
像我同事wonderfu一樣，致敬brpc。
thread local
最高的并發就是完全隔離，互不影響，thread local天生如此。實際上不僅brpc的dbd，我們熟知的tcmalloc和jemalloc也都使用了thread local特性，所以讓我們記住這高并發最后的利器吧。
最后，還有一項來自數據庫的技術：mvcc（Multiversion Concurrency Control），我平時還沒有用到，只是提一下就不細說了。
參考：
https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt
https://www.kernel.org/doc/Documentation/memory-barriers.txt
https://github.com/Apache/incubator-brpc/blob/master/docs/cn/lalb.md
