並發bug之源（一）-可見性
CPU三級快取
要聊可見性，這事兒還得從電腦的組成開始說起，我們都知道，電腦由CPU、記憶體、磁碟、顯示卡、外設等幾部分組成，對於我們程式設計師而言，寫程式碼主要關注CPU和記憶體兩部分。放幾張馬士兵老師的圖：
再說CPU，眾所周知，CPU同一時間點，只能執行一個執行緒，多個執行緒之間通過爭搶CPU資源獲得執行權，實現一種偽並發的效果。但這其實說的是上古CPU，那種單核CPU。現在的CPU，其實都是多核了。準確的說法，應該是一個核在同一時間點，只能執行一個執行緒。（題外話，這句話其實現在來說依然過時了，英特爾公司研發出的「超執行緒技術」，把一個物理核心模擬成兩個邏輯核心，允許在每個內核上運行多個執行緒，就是我們常聽到的什麼4核8執行緒，8核16執行緒CPU。還有最新的大小核架構，這裡不展開了）
CPU的運行速度是非常非常快的，大約是記憶體的100倍。什麼意思呢？如果CPU的一個計算單元，去訪問暫存器需要1ns，那麼訪問記憶體，就需要100ns。而且根據摩爾定律，CPU的速度每18個月就會翻倍，相當於每年增⻓ 60% 左右，記憶體的速度當然也會不斷增⻓，但是增⻓的速度遠小於 CPU，平均每年只增長7%左右。於是，CPU與記憶體性能的差距不斷拉大。
如果我們訪問記憶體中的一個數據A，那麼很有可能接下來會再次訪問到這個數據A，這叫時間局部性原理。要是CPU每次都是去記憶體取數據A，其實有99%的時間是等待浪費了。那麼我們該如何提高性能呢？編程思想萬變不離其宗，既然一個數據可能會被頻繁使用，而每次去記憶體取數據太慢，那就加快取好了。
現代CPU為了增加CPU讀寫記憶體性能，就在CPU和記憶體之間增加了多級cache，也稱高速快取L1、L2、L3，其中L3是多個核心共享的。這其實就是我們常聽說的，CPU三級快取。
CPU讀記憶體時首先從L1找起（這裡有個很細的細節，有的時候會直接去L2找，跳過L1），能找到直接返回，否則就要在L2中找，找不到就到L3中找，還找不到就去記憶體中找了（記憶體還沒有的話就去磁碟找）。找到之後，會把找到的數據放到L3、L2、L1里，下次再找，直接就在L1里找到了。
至於為什麼是三級快取，而不是兩級四級呢？其實很簡單，越往上，雖然存儲介質速度越快，但造價越高容量也越小；越往下，雖然存儲介質速度越慢，但造價越低容量也越大。三級快取，是一個工業實踐後，平衡經濟與效率的最佳方案。
快取行
這裡就有個問題了，如果CPU每次要取數據，都要走一遍上面這個流程，明顯效率也不高啊。比如我要訪問一個數組的數據，對數組做個遍歷，去拿第一數據，走一遍上面的流程，去拿第二個，又走一遍，這太麻煩了。也許我們平時使用redis等快取的時候，會覺得這麼做沒什麼毛病，但CPU是要追求極致的性能的，這點性能損耗就是不能接受的。（類似懶漢式，用到的時候才去查，然後放到快取里，第一次執行效率不高）
那麼我們想提高效率又該怎麼辦呢？
如果我們訪問記憶體中的一個數據A，還很有可能訪問與數據A相鄰的數據B、數據C，這叫空間局部性原理。那所幸我們在取A的時候，就把A周圍的數據一次都取回來，一次取一批數據。這解決方案又是一個編程思想，批處理。也可以說是餓漢式，提前把可能要用到的數據一起載入到CPU快取里。
既然是批處理，那就會有個問題，這個「一批」，多大合適呢？是 5 bytes，10 bytes，還是多少？很明顯，大了不合適，浪費快取空間，小了也不合適，快取命中率不高。所以同樣是經過大量工業實踐，最終確定了一個最佳大小，64 bytes（最常見的快取行大小，小部分cpu可能是別的大小）。我們把這一次讀取的 64 bytes 數據，稱之為 Cache Line（快取行）（也有文章稱之為快取段，快取塊的）。CPU每次從記憶體中讀取數據，會一次將 64 bytes 的數據一起讀回去，並放到三級快取中，大大提高了CPU讀取數據的性能。
快取一致性
到目前為止，為了儘可能的提高CPU的性能，我們引入了三級快取，引入了快取行，但還有一個問題沒有解決，那就是快取一致性問題。
最開始的時候我們就說了，執行緒和CPU的核，在同一時間點是一一對應的。如上圖， X 和 Y 在記憶體里是挨著的，在多核情況下，或者叫多執行緒情況下，如果左邊的核去獲取記憶體中的數據 X=0，右邊的去獲取數據 Y=0 ，因為快取行的存在，兩個核內的L1、L2快取里，都會快取 X 和 Y 的值。
這個時候我們想一下，如果在左邊的核里，我們將 X 的值給改成了1，右邊的核它不知道啊，右邊核的L1、L2里 X 的值還是0，這就會產生數據的不一致。這就是執行緒可見性的問題，當然即便不考慮快取行，兩個執行緒同時讀寫同一個數據，也會有可見性問題。所以一定要有一種機制，一個核將數據修改了，要通知其他核做相應的修改，這個機制我們就叫做快取一致性協議。快取一致性協議有好多種，每種CPU不一樣，其中最著名的是英特爾的MESI，其他廠商的CPU用的未必是這個。
注意，這是硬體級別的機制，和軟體層面無關，和 volatile 無關。以後要是有人和你聊快取一致性協議，跟 volatile 一起聊，你心裡一定要清楚，這事兒是不對的。
快取行填充的編程技巧
我們來看個小程式：
public class CacheLine {
static class T {
// long p1, p2, p3, p4, p5, p6, p7;
long x = 0L; // 8 bytes
// long p9, p10, p11, p12, p13, p14, p15;
}
static T[] arr = new T[2];
static {
arr[0] = new T();
arr[1] = new T();
}
public static void main(String[] args) throws InterruptedException {
CountDownLatch cdl = new CountDownLatch(2);
Thread t0 = new Thread(() -> {
for (long i = 0L; i < 10_0000_0000L; i++) {
arr[0].x = i;
}
cdl.countDown();
});
Thread t1 = new Thread(() -> {
for (long i = 0L; i < 10_0000_0000L; i++) {
arr[1].x = i;
}
cdl.countDown();
});
long nanoTime = System.nanoTime();
t0.start();
t1.start();
cdl.await();
System.out.println((System.nanoTime() - nanoTime) / 1000000);
}
}
我來解釋下這個小程式是幹什麼的，很簡單。有個靜態內部類 T，其中有一個 long 類型的成員變數 x，佔了8個bytes。然後我構建了一個 T 對象的 arr 數組，數組長度是2，數組裡面放了兩個 T 對象實例，數據準備完畢。現在我起了兩個執行緒，第一個執行緒將 arr 數組中的第一個 T 對象的成員變數 x 修改10億次。第二個執行緒將 arr 數組中的第二個 T 對象的成員變數 x 修改10億次。然後統計兩個執行緒改完共耗時多久。（注意下此處是兩個T對象，也就分別有兩個成員變數x，兩個執行緒改的x不是同一個）
看結果：
耗時1195毫秒。
現在我們修改下程式，將上面靜態內部類 T 中注釋掉的那兩行程式碼放開：
static class T {
long p1, p2, p3, p4, p5, p6, p7;
long x = 0L; // 8 bytes
long p9, p10, p11, p12, p13, p14, p15;
}
現在和之前的區別是，之前靜態內部類 T 中只有一個 long 類型的成員變數 x，佔了8個bytes。現在靜態內部類 T 中成員變數 x 前面有7個 long 類型的成員變數，共56個bytes，後面也有7個 long 類型的成員變數，共56個bytes，除此以外沒有差別。第二種修改後的情況下，T 對象內部大概是長這樣的：
我們再運行一下程式看結果：
耗時509毫秒！速度居然快了1倍，神奇不。第二種情況只是在 x 前後各放了56個bytes的數據，效率就提高，而沒放數據，效率就變低。大家想想這是為什麼呢？
我們想一下，在我們前後沒放 56 bytes 數據的時候，一個 x 占 8 bytes 空間，數組中有兩個 T 對象，那麼兩個 x 在記憶體中大概率是挨在一起的。而我們說由於快取行的存在，一個快取行是 64 bytes，裝兩個 8 bytes 肯定沒問題，兩個 x 也就大概率位於同一個快取行內。這就意味著，執行緒1在取其中一個 T1.x 的時候，會將整行數據都讀回來，執行緒2也是同理。兩個執行緒都會將整行數據讀到自己的L1、L2快取中。
那麼執行緒1在修改 T1.x 的時候，由於快取一致性協議，就要通知執行緒2，T1.x 已經被修改了，這肯定需要時間，效率就低了。當多執行緒修改互相獨立的變數時，如果這些變數共享同一個快取行，就會無意中影響彼此的性能，這被稱之為偽共享。
而當我在 x 的前後各加了 56 bytes 數據時，那麼兩個 x ，就絕對不會位於同一個快取行內了。
既然兩個 x 不會位於同一個快取行內，那麼兩個執行緒分別修改兩個 x ，每個 x 只會在自己執行緒的快取內，也就不會有快取一致性問題，也就不需要互相通知，效率就高了，避免了偽共享導致的性能損耗。這和程式語言沒關係，什麼語言測試都是如此，因為快取一致性協議是硬體級別的機制。
問個問題，我要是只在 x 前面加 56 bytes 的數據，後面不加行不行？貌似這樣兩個 x 也不會在同一快取行內啊？在這個demo小程式中是可以的，但如果我不是兩個 x ，而是一個 x，一個 y 呢？你只在x前面加 56 bytes 數據，y 依然有可能和 x 位於同一快取行，那一個執行緒修改 x ，一個執行緒修改 y ，就還是會有上面的問題了。所以，為了保證任何時候 x 都不會有這種問題，最好是在前後都加上 56 bytes 的數據，就可以保證萬無一失。我們把這個編程技巧叫做快取行填充，主要適用於頻繁寫的共享數據上。
（題外話，Java8 之前可以給變數前後分別填充7個long類型進行快取行填充，而 Java 8 中已經提供了官方的解決方案，Java 8 中新增了一個註解： @sun.misc.Contended。加上這個註解的欄位會自動補齊快取行，需要注意的是此註解默認是無效的，需要在 jvm 啟動時設置 -XX:-RestrictContended 才會生效。）
肯定有人要說了，這也太底層了太細節了，感覺沒必要啊，實際開發中真的有人這麼用嗎？
有一款開源軟體，叫Disruptor，是一個高性能的非同步處理框架，能夠在無鎖的情況下實現隊列的並發操作，號稱能夠在一個執行緒里每秒處理6百萬筆訂單，可以說是單機最快的MQ。Disruptor中的一個核心結構，就是環形緩衝區，RingBuffer。我們去看下它的源碼：
來，看到了什麼，知道這7個變數是幹啥的嗎，如果沒有上面的知識，你肯定看不懂，是不是就有人在實際開發中用到了呢。最上面的INITIAL_CURSOR_VALUE變數，就是環形緩衝區的指針起始位置。有人說不對啊，只有後面 56 bytes，沒有前面的 56 bytes 呀。別急，這個類叫 RingBuffer ，它的父類叫 RingBufferFields，RingBufferFields 還有個父類叫 RingBufferPad，點進去看看：
RingBuffer 的爺爺類里，還有7個long類型數據，佔了 56 bytes，所以INITIAL_CURSOR_VALUE變數的前面有 56 bytes 數據，後面也有 56 bytes 數據，所以這也是 Disruptor 性能非常高的原因之一。另一個原因是 Disruptor 底層用的是CAS自旋鎖，這個這次就不展開了，後面講原子性的時候再說。
