前段時(shí)間參加技術(shù)晉升答辯評(píng)審执虹，其中大部分人都林林總總的提到了一些對(duì)于緩存的使用，所以想系統(tǒng)性的梳理下java相關(guān)的緩存技術(shù)的整個(gè)技術(shù)體系和知識(shí)點(diǎn)猜丹。
緩存并不是互聯(lián)網(wǎng)的大流量和數(shù)據(jù)量興起后出現(xiàn)的械馆，其實(shí)從計(jì)算器系統(tǒng)建立之初緩存就一直存在耍攘，其目的就是為了彌補(bǔ)處理器和存儲(chǔ)器之前相差巨大的處理能力。這一篇主要將介紹計(jì)算機(jī)系統(tǒng)高速緩存和其和java相關(guān)的一些技術(shù)知識(shí)堪滨。

什么是高速緩存

對(duì)于一個(gè)一般的計(jì)算機(jī)系統(tǒng)來(lái)說(shuō)胯陋，其CPU通過(guò)總線接口聯(lián)接到主板的IO橋，通過(guò)IO橋建立的IO總線袱箱，再和主存儲(chǔ)器（內(nèi)存）以及其他存儲(chǔ)器（磁盤遏乔，網(wǎng)絡(luò)設(shè)備，圖形設(shè)備发笔，控制器等）進(jìn)行數(shù)據(jù)傳輸盟萨。
而所有的CPU計(jì)算，都要通過(guò)CPU的寄存器進(jìn)行數(shù)據(jù)讀寫了讨。但是CPU的寄存器空間又是及其有限的（4～8個(gè)字節(jié)）捻激，所以為了不讓CPU頻繁的等待制轰，所以在主存儲(chǔ)器和CPU的計(jì)算單元之間，又會(huì)存在多級(jí)高速緩存（集成在CPU中）胞谭，距離最近的叫L1高速緩存垃杖，再依次有L2，L3.丈屹。调俘。。這樣從CPU的寄存器到主內(nèi)存之間旺垒，每一層緩存的容量越來(lái)越大彩库，速度越來(lái)越慢，成本越來(lái)越底先蒋。

image.png

對(duì)于高速緩存來(lái)說(shuō)侧巨，因?yàn)橹噶詈蛿?shù)據(jù)的特性是不一樣的，指令是只讀的只會(huì)入棧出棧比較簡(jiǎn)單（緩存的寫比較復(fù)雜鞭达，后面會(huì)介紹）司忱，而數(shù)據(jù)會(huì)讀取也會(huì)更新，所以在靠近CPU的高速緩存會(huì)把指令和數(shù)據(jù)單獨(dú)存儲(chǔ)畴蹭，指令的叫做i-cache而數(shù)據(jù)叫做d-cache坦仍。
對(duì)于Core i7處理器的高速緩存和特性：

關(guān)于相聯(lián)度，塊大小和組數(shù)后面的存儲(chǔ)結(jié)構(gòu)中會(huì)介紹叨襟。因?yàn)镃PU最終還是集成電路繁扎，其中一次電路信號(hào)作為一個(gè)時(shí)鐘周期，而CPU會(huì)在這個(gè)周期內(nèi)通過(guò)流水線處理多個(gè)模式化的任務(wù)糊闽，所以所用的時(shí)鐘周期越短梳玫，造成CPU等待的時(shí)間越少。

高速緩存的存儲(chǔ)結(jié)構(gòu)

因?yàn)镃PU寄存器的容量很小右犹，所以計(jì)算機(jī)在運(yùn)行中需要高頻的讀寫高速緩存提澎，那么其讀寫效率就是非常重要的了。為了快速定位緩存念链，高速緩存也使用了非常精妙的方式來(lái)進(jìn)行設(shè)計(jì)盼忌。
一個(gè)計(jì)算機(jī)系統(tǒng)其存儲(chǔ)器地址有m位，那么將總共有個(gè)地址掂墓；高速緩存會(huì)被分割為獨(dú)立的個(gè)高速緩存組（cache set）谦纱；每個(gè)組包含E個(gè)高速緩存行（cache line）；每個(gè)行是有一個(gè)字節(jié)的數(shù)據(jù)塊（block）組成的君编，一個(gè)有效位（valid bit）代表這個(gè)行是否包含有效緩存跨嘉，還有個(gè)標(biāo)記位（tag bit）來(lái)唯一的標(biāo)示存儲(chǔ)在這個(gè)高速緩存行中的塊：

image.png

image.png

image.png

高速緩存的讀

理解了高速緩存的存儲(chǔ)結(jié)構(gòu)后，我們來(lái)看下高速緩存的讀取赋焕。
首先我們看下一次數(shù)據(jù)讀取的過(guò)程：

• 寄存器中未命中参歹，請(qǐng)求L1緩存
• L1緩存命中直接返回，未命中查詢L2緩存
• L2緩存命中直接返回隆判，未命中查詢L3緩存
• L3緩存命中直接返回犬庇，未命中查詢主內(nèi)存
  ……
• 主內(nèi)存命中僧界，返回L3緩存，并寫入
• 返回L2緩存并寫入
• 返回L1緩存并寫入
• 返回寄存器并寫入臭挽，進(jìn)行指令運(yùn)算

可以看到捂襟，每次k級(jí)緩存的查詢，當(dāng)不命中時(shí)都是查詢k+1級(jí)緩存欢峰，返回后寫入k級(jí)緩存葬荷。這樣就是逐級(jí)查詢和逐級(jí)寫入的過(guò)程。

我們?cè)賮?lái)了解關(guān)于緩存使用效率的局部性的概念：

• 時(shí)間局部性：同一個(gè)數(shù)據(jù)對(duì)象可能被多次使用纽帖。一段一個(gè)塊被放入緩存，那么如果后續(xù)能夠不斷的訪問(wèn)命中，那么它的時(shí)間局部性就更好碗啄。
• 空間局部性：因?yàn)橐粋€(gè)塊包含有連續(xù)的一段地址內(nèi)的字節(jié)淑履，那么我們希望在放入一個(gè)塊后，后面的訪問(wèn)也能不斷的命中塊中放入的其他字節(jié)數(shù)據(jù)室囊，那么它的空間局部性就更好雕崩。

其中為了得到更好的空間局部性，根據(jù)緩存中的塊總是寫入連續(xù)地址的特性融撞，所以我們?cè)诰帉懘a時(shí)如果能過(guò)在運(yùn)行中連續(xù)不斷的步長(zhǎng)為1的訪問(wèn)內(nèi)存地址晨逝，那么可能得到最佳的空間局部性；而當(dāng)我們?cè)L問(wèn)的步長(zhǎng)以及讀取的字節(jié)正好跨越了所有的行懦铺，造成每下一次訪問(wèn)都命中同一個(gè)行（也就是沖突不命中）捉貌，頻繁的使緩存刷入刷出，那么就得到最差的空間局部性冬念。
雖然高速緩存的緩存策略都是由系統(tǒng)所管理趁窃，似乎程序員沒(méi)有可以干涉的地方，但是如果能夠合理使用高速緩存的特性急前，我們還是能夠?qū)懗龈咝У拇a來(lái)醒陆。
一個(gè)實(shí)際的例子，我們需要給一個(gè)二維數(shù)組進(jìn)行求和裆针，首先我們使用行優(yōu)先的方式進(jìn)行計(jì)算：

    private int hitCache() {
        int[][] array = new int[2048][2048];
        int i, sum = 0;   h h
        int iBoundary = array[0].length;
        int jBoundary = array[1].length;

        for (i = 0; i < iBoundary; i += 64) {
            for (int j = 0; j < jBoundary; j++) {
                sum += array[i][j];
            }
        }

        return sum;
    }

我們?cè)偈褂昧袃?yōu)先的方式進(jìn)行計(jì)算：

    private int missCache() {
        int[][] array = new int[2048][2048];
        int i, sum = 0;
        int iBoundary = array[0].length;
        int jBoundary = array[1].length;

        for (i = 0; i < iBoundary; i += 64) {
            for (int j = 0; j < jBoundary; j++) {
                sum += array[j][i];
            }
        }

        return sum;
    }

編寫main函數(shù)運(yùn)行：

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        TestCache testCache = new TestCache();
        System.out.println(testCache.hitCache());
        System.out.println("hitCache: " + (System.currentTimeMillis() - start));
        start = System.currentTimeMillis();
        System.out.println(testCache.missCache());
        System.out.println("missCache: " + (System.currentTimeMillis() - start));
    }

基本上會(huì)有70%左右的性能差距：

0
hitCache: 9
0
missCache: 15

Process finished with exit code 0

從程序的角度講這兩段代碼的時(shí)間復(fù)雜度完全一致刨摩，都是，但為什么性能差距會(huì)如此之大呢世吨？
這是因?yàn)楦鶕?jù)高速緩存行存儲(chǔ)的策略澡刹，總是一次性將連續(xù)的一段地址字節(jié)載入。而對(duì)于二維數(shù)組來(lái)說(shuō)耘婚，在內(nèi)存里是根據(jù)行優(yōu)先的方式展開存儲(chǔ)的罢浇，也就是相鄰行的數(shù)據(jù)地址是連續(xù)的。因此，根據(jù)行優(yōu)先的訪問(wèn)方式會(huì)具有更好的空間局部性（循環(huán)每下一次要讀取的數(shù)據(jù)可能已經(jīng)被上次一的緩存加載寫入到了同一個(gè)塊中）嚷闭，從而取得良好的性能攒岛。
所以我們能夠利用高速緩存的空間局部性，連續(xù)的訪問(wèn)相鄰的地址（但正好跨越所有行的字節(jié)胞锰，會(huì)造成每次的沖突不命中）灾锯，從而提升每次緩存的加載使得下一次緩存命中的機(jī)率，從而提升系統(tǒng)性能嗅榕。

高速緩存的寫

當(dāng)CPU的計(jì)算單元完成計(jì)算后顺饮，可能需要修改某地址中的值，那么這是就涉及到高速緩存的寫入問(wèn)題誊册。相對(duì)于讀取领突，寫入要復(fù)雜很多，java虛擬機(jī)中也有很多地方和此技術(shù)特性強(qiáng)相關(guān)案怯。
高速緩存的寫可以簡(jiǎn)單抽象為以下兩種方式（實(shí)際情況可能復(fù)雜很多）：

• 直寫(write-through)
  每一級(jí)緩存馬上寫入下一級(jí)緩存中君旦，這樣實(shí)現(xiàn)簡(jiǎn)單，但是每次運(yùn)行都會(huì)造成CPU IO總線操作嘲碱，如果下一級(jí)緩存性能很低金砍，那么將造成長(zhǎng)時(shí)間的等待。
• 寫回(write-back)
  因?yàn)橹睂懣赡茉斐傻牡托阅苈缶猓圆⒉皇敲看味几孪乱患?jí)緩存恕稠，而是只更新自身就返回。直到塊將要退出時(shí)（例如不同地址命中相同組）扶欣，才寫入下一級(jí)鹅巍。這樣可能合并多次計(jì)算結(jié)果只寫入一次，同時(shí)計(jì)算單元也不用每次長(zhǎng)時(shí)間等待料祠。但是這種方式需要額外的一個(gè)標(biāo)識(shí)位來(lái)標(biāo)示出是否緩存已經(jīng)被更新了骆捧，也提升了復(fù)雜性（特別是多核CPU在多線程模式工作時(shí)）。

基于以上不同的特性髓绽，一般如果兩級(jí)緩存性能相差不大敛苇，例如L2，L3之間顺呕，是可以使用直寫方式的枫攀；而當(dāng)兩級(jí)緩存性能差距巨大，例如L3和主存株茶，那么回使用寫回的方式来涨。
對(duì)于java虛擬機(jī)來(lái)說(shuō)，因?yàn)楦咚倬彺娴膶懙拇鷥r(jià)很大忌卤，所以需要盡量減少寫入的操作扫夜，那么在代碼編譯到字節(jié)碼，或者動(dòng)態(tài)編譯的過(guò)程中驰徊，可能會(huì)合并多次處理笤闯，最終只寫入一次。
例如代碼：

int sum = 0;
int count() {
  int a = 0, b = 0, c = 0;
  sum = a + b;
  sum += c;
  return sum;
}

如果嚴(yán)格按照順序編譯執(zhí)行棍厂，那么sum將需要刷新兩次棧到主內(nèi)存中颗味，但是java虛擬機(jī)在這種情況下可能會(huì)合進(jìn)行指令重排，只在最后一次執(zhí)行中才進(jìn)行主內(nèi)存刷新指令牺弹。根據(jù)happens-before原則浦马，這樣在單線程模式下完全可以得到一致的結(jié)果。
我們?cè)賮?lái)到多核CPU的多線程執(zhí)行模式下张漂，因?yàn)槎嗑€程是基于同一個(gè)進(jìn)程晶默，那么每個(gè)線程都可以訪問(wèn)進(jìn)程內(nèi)的地址『皆埽回到高速緩存的實(shí)現(xiàn)模式磺陡，每個(gè)核的CPU都可能會(huì)有獨(dú)立的L1、L2緩存漠畜，那么在多線程讀寫的情況下币他，就可能同一個(gè)地址的字節(jié)被讀入不同核所對(duì)應(yīng)的高速緩存，而當(dāng)其中一個(gè)核更新了此緩存后憔狞，就會(huì)造成其他核緩存的數(shù)據(jù)一致性問(wèn)題蝴悉。
我們分兩種情況來(lái)考慮：

• 高速緩存和內(nèi)存采用直寫的方式：在這種情況下，當(dāng)其中一個(gè)核心寫入主內(nèi)存后瘾敢，CPU會(huì)根據(jù)自身的一致性協(xié)議（一般為MESI協(xié)議）拍冠，讓其他核心都嗅探到此次變化，從而標(biāo)記自身的緩存為失效簇抵，那么下一次訪問(wèn)就能夠從主內(nèi)存中得到最新的結(jié)果庆杜，從而保證一致性。
• 高速緩存和內(nèi)存采用回寫的方式：在這種情況下正压，高速緩存的一次更新可能并不會(huì)觸發(fā)主內(nèi)存的更新指令欣福，那么其他核中的緩存也就無(wú)法直到此次更新的發(fā)生，從而造成一致性問(wèn)題焦履。

MESI協(xié)議簡(jiǎn)介

image.png

狀態(tài)：
M（修改, Modified）: 本地處理器已經(jīng)修改緩存行, 即是臟行, 它的內(nèi)容與內(nèi)存中的內(nèi)容不一樣. 并且此cache只有本地一個(gè)拷貝（專有）拓劝。
E（專有, Exclusive）: 緩存行內(nèi)容和內(nèi)存中的一樣, 而且其它處理器都沒(méi)有這行數(shù)據(jù)。
S（共享, Shared）: 緩存行內(nèi)容和內(nèi)存中的一樣, 有可能其它處理器也存在此緩存行的拷貝嘉裤。
I（無(wú)效, Invalid）: 緩存行失效, 不能使用郑临。

從以上我們可以發(fā)現(xiàn)，因?yàn)镃PU自身已經(jīng)有一致性協(xié)議保證寫入主內(nèi)存的數(shù)據(jù)的多核一致性屑宠，所以我們只要保證每次修改高速緩存的值能夠被刷新到主內(nèi)存即可保證多線程模式下數(shù)據(jù)的一致性厢洞。
根據(jù)此需要，所有架構(gòu)的CPU都提供了略微不同的內(nèi)存屏障指令，其指令能夠?qū)⒕彺嫘袕?qiáng)制刷新到主內(nèi)存中躺翻，并預(yù)防其前后的指令重排丧叽。例如IA32的lock指令。
但是java虛擬機(jī)是需要能夠跨平臺(tái)運(yùn)行的公你，所以需要屏蔽不同系統(tǒng)間的指令區(qū)別踊淳，所以才誕生了JMM，JMM根據(jù)JSF-133建立了抽象的統(tǒng)一的內(nèi)存模型陕靠。主要將java內(nèi)存劃分為共享的主內(nèi)存（可以簡(jiǎn)單理解為堆內(nèi)存）以及各個(gè)線程之間隔離的棧內(nèi)存（可以簡(jiǎn)單認(rèn)為是寄存器迂尝，高速緩存以及緩存和指令集的處理集合）。
從JMM的角度看剪芥，不但存在高速緩存有寫回造成的不一致問(wèn)題垄开，同時(shí)還有多個(gè)棧和主內(nèi)存之間的不一致問(wèn)題。所以JMM將不同系統(tǒng)的內(nèi)存屏障指令抽象為以下幾種類型：

而在java虛擬機(jī)中，有多種情況都會(huì)涉及到關(guān)于對(duì)內(nèi)存屏障的使用寸认。

• volatile
  很多人都直到volatile修飾的變量具有原子性签财，全局可見(jiàn)性和防重排。而這些特性正是使用了內(nèi)存屏障來(lái)實(shí)現(xiàn)的偏塞。

1. 每個(gè)volatile的寫前插入StoreStore屏障
2. 每個(gè)volatile的寫后插入StoreLoad屏障
3. 每個(gè)volatile的讀后插入LoadLoad屏障
4. 每個(gè)volatile的讀后插入LoadStore屏障
   所以每個(gè)volatile變量的讀寫都會(huì)插入很多內(nèi)存屏障指令唱蒸，而且會(huì)造成高速緩存到主內(nèi)存的刷新，從而造成性能損耗灸叼。

• synchronized
  synchronized關(guān)鍵字用來(lái)處理多線程下資源競(jìng)爭(zhēng)的同步問(wèn)題神汹，也就是在同一個(gè)進(jìn)程內(nèi)，同一時(shí)間能夠有一個(gè)線程擁有被鎖定的資源古今。那么我們?cè)O(shè)想為了數(shù)據(jù)的一致性屁魏，在進(jìn)入鎖定前，為了方式別的線程對(duì)數(shù)據(jù)的修改捉腥，所以需要將此線程棧中的緩存都標(biāo)記為過(guò)期氓拼；而當(dāng)釋放鎖前，為了防止線程寫入的緩存并不能被其他線程訪問(wèn)到抵碟，所以需要將緩存中的內(nèi)容都強(qiáng)制刷新到主內(nèi)存中桃漾。
• final
  java所定義的final修飾的變量是不可變的，所以需要每次訪問(wèn)到的時(shí)候獲得的值都是一致的拟逮。
  所以為了避免在final變量初始化過(guò)程中撬统，其他線程訪問(wèn)到了其未完成初始化的值，需要在每個(gè)final變量的寫操作后插入StoreStore屏障敦迄，前面插入LoadLoad屏障恋追，從而保證不會(huì)有指令重排許造成的其他線程讀到中間狀態(tài)的情況出現(xiàn)凭迹。

好了，以上就是對(duì)JMM中根據(jù)高速緩存特性建立的內(nèi)存屏障的抽象以及使用的簡(jiǎn)單介紹苦囱。最后我們?cè)賮?lái)了解下關(guān)于高速緩存性能的一個(gè)有趣技術(shù)：

• MEM:BLCKING:使用分塊提高時(shí)間局部性
  此技術(shù)就是根據(jù)L1緩存的塊大行岢瘛（例如Core i7處理器的64B），將完整的信息正好設(shè)置為塊大小沿彭，從而使得每一個(gè)塊中都是獨(dú)立完整的信息朽砰，可以獨(dú)立的修改尖滚，訪問(wèn)和丟棄喉刘，從而提升性能。

而以高性能而著名的disraptor正是運(yùn)用了此技術(shù)漆弄。

• disraptor: https://github.com/disraptor/disraptor
  是一個(gè)高速消息隊(duì)列睦裳，其主要思想就是將接收的消息緩存在一個(gè)ringBuffer中，而分別有寫指針和讀指針進(jìn)行生產(chǎn)和消費(fèi)撼唾，從而最低程度的減少鎖沖突的發(fā)生廉邑。而ringBuffer中存儲(chǔ)的數(shù)據(jù)正是使用了64B的數(shù)據(jù)大小，這樣就是為了使得ringBuffer中的數(shù)據(jù)連續(xù)的分布于L1緩存的緩存行中倒谷，因?yàn)槠渲械膶懭氩僮魇欠浅６嗟闹朊桑@樣每個(gè)數(shù)據(jù)的讀取和修改只涉及到自身的行，沒(méi)有競(jìng)爭(zhēng)渤愁，從而提升性能牵祟。
  
  image.png

參考資料：
《深入理解計(jì)算機(jī)系統(tǒng)》
《java并發(fā)編程的藝術(shù)》
《深入理解java虛擬機(jī)》