認(rèn)識CPU Cache

CPU Cache概述

隨著CPU的頻率不斷提升，而內(nèi)存的訪問速度卻沒有質(zhì)的突破撕捍，為了彌補(bǔ)訪問內(nèi)存的速度慢拿穴，充分發(fā)揮CPU的計算資源，提高CPU整體吞吐量忧风，在CPU與內(nèi)存之間引入了一級Cache默色。隨著熱點數(shù)據(jù)體積越來越大，一級Cache L1已經(jīng)不滿足發(fā)展的要求狮腿，引入了二級Cache L2腿宰，三級Cache L3。（注：若無特別說明蚤霞，本文的Cache指CPU Cache，高速緩存）CPU Cache在存儲器層次結(jié)構(gòu)中的示意如下圖：

圖片描述

計算機(jī)早已進(jìn)入多核時代义钉，軟件也越來越多的支持多核運行昧绣。一個處理器對應(yīng)一個物理插槽，多處理器間通過QPI總線相連捶闸。一個處理器包含多個核夜畴，一個處理器間的多核共享L3 Cache。一個核包含寄存器删壮、L1 Cache贪绘、L2 Cache，下圖是Intel Sandy Bridge CPU架構(gòu)央碟，一個典型的NUMA多處理器結(jié)構(gòu)：

圖片描述

作為程序員税灌，需要理解計算機(jī)存儲器層次結(jié)構(gòu)，它對應(yīng)用程序的性能有巨大的影響亿虽。如果需要的程序是在CPU寄存器中的菱涤，指令執(zhí)行時1個周期內(nèi)就能訪問到他們。如果在CPU Cache中洛勉，需要1_{30個周期粘秆；如果在主存中，需要50}200個周期收毫；在磁盤上攻走，大概需要幾千萬個周期。充分利用它的結(jié)構(gòu)和機(jī)制此再，可以有效的提高程序的性能昔搂。

以我們常見的X86芯片為例，Cache的結(jié)構(gòu)下圖所示：整個Cache被分為S個組输拇，每個組是又由E行個最小的存儲單元——Cache Line所組成巩趁，而一個Cache Line中有B（B=64）個字節(jié)用來存儲數(shù)據(jù)，即每個Cache Line能存儲64個字節(jié)的數(shù)據(jù)，每個Cache Line又額外包含一個有效位(valid bit)议慰、t個標(biāo)記位(tag bit)蠢古，其中valid bit用來表示該緩存行是否有效；tag bit用來協(xié)助尋址别凹，唯一標(biāo)識存儲在CacheLine中的塊草讶；而Cache Line里的64個字節(jié)其實是對應(yīng)內(nèi)存地址中的數(shù)據(jù)拷貝。根據(jù)Cache的結(jié)構(gòu)題炉菲，我們可以推算出每一級Cache的大小為B×E×S堕战。

圖片描述

那么如何查看自己電腦CPU的Cache信息呢？

在windows下查看方式有多種方式拍霜，其中最直觀的是嘱丢，通過安裝CPU-Z軟件，直接顯示Cache信息祠饺，如下圖：

圖片描述

此外越驻，Windows下還有兩種方法：

①Windows API調(diào)用GetLogicalProcessorInfo。
②通過命令行系統(tǒng)內(nèi)部工具CoreInfo道偷。

如果是Linux系統(tǒng)缀旁， 可以使用下面的命令查看Cache信息：

ls /sys/devices/system/cpu/cpu0/cache/index0

圖片描述

還有l(wèi)scpu等命令也可以查看相關(guān)信息,如果是Mac系統(tǒng)，可以用sysctl machdep.cpu 命令查看cpu信息勺鸦。

如果我們用Java編程并巍，還可以通過CacheSize API方式來獲取Cache信息， CacheSize是一個谷歌的小項目换途，java語言通過它可以進(jìn)行訪問本機(jī)Cache的信息懊渡。示例代碼如下：

public static void main(String[] args) throws CacheNotFoundException {        CacheInfo info = CacheInfo.getInstance();         CacheLevelInfo l1Datainf = info.getCacheInformation(CacheLevel.L1, CacheType.DATA_CACHE);        System.out.println("第一級數(shù)據(jù)緩存信息："+l1Datainf.toString());         CacheLevelInfo l1Instrinf = info.getCacheInformation(CacheLevel.L1, CacheType.INSTRUCTION_CACHE);        System.out.println("第一級指令緩存信息："+l1Instrinf.toString());    }

打印輸出結(jié)果如下：

第一級數(shù)據(jù)緩存信息：CacheLevelInfo [cacheLevel=L1, cacheType=DATA_CACHE, cacheSets=64, cacheCoherencyLineSize=64, cachePhysicalLinePartitions=1, cacheWaysOfAssociativity=8, isFullyAssociative=false, isSelfInitializing=true, totalSizeInBytes=32768] 第一級指令緩存信息：CacheLevelInfo [cacheLevel=L1, cacheType=INSTRUCTION_CACHE, cacheSets=64, cacheCoherencyLineSize=64, cachePhysicalLinePartitions=1, cacheWaysOfAssociativity=8, isFullyAssociative=false, isSelfInitializing=true, totalSizeInBytes=32768]

還可以查詢L2、L3級緩存的信息军拟，這里不做示例距贷。從打印的信息和CPU-Z顯示的信息可以看出，本機(jī)的Cache信息是一致的吻谋，L1數(shù)據(jù)/指令緩存大小都為：C=B×E×S=64×8×64=32768字節(jié)=32KB忠蝗。

Cache Line偽共享及解決方案

Cache Line偽共享分析

說偽共享前，先看看Cache Line 在java編程中使用的場景漓拾。如果CPU訪問的內(nèi)存數(shù)據(jù)不在Cache中（一級阁最、二級、三級）骇两，這就產(chǎn)生了Cache Line miss問題速种，此時CPU不得不發(fā)出新的加載指令，從內(nèi)存中獲取數(shù)據(jù)低千。通過前面對Cache存儲層次的理解配阵，我們知道一旦CPU要從內(nèi)存中訪問數(shù)據(jù)就會產(chǎn)生一個較大的時延馏颂，程序性能顯著降低，所謂遠(yuǎn)水救不了近火棋傍。為此我們不得不提高Cache命中率救拉，也就是充分發(fā)揮局部性原理。

局部性包括時間局部性瘫拣、空間局部性亿絮。時間局部性：對于同一數(shù)據(jù)可能被多次使用，自第一次加載到Cache Line后麸拄，后面的訪問就可以多次從Cache Line中命中派昧，從而提高讀取速度（而不是從下層緩存讀取）拢切〉傥空間局部性：一個Cache Line有64字節(jié)塊，我們可以充分利用一次加載64字節(jié)的空間淮椰，把程序后續(xù)會訪問的數(shù)據(jù)五慈，一次性全部加載進(jìn)來，從而提高Cache Line命中率（而不是重新去尋址讀仁蛋）豺撑。

看個例子：內(nèi)存地址是連續(xù)的數(shù)組（利用空間局部性）烈疚，能一次被L1緩存加載完成黔牵。

如下代碼，長度為16的row和column數(shù)組爷肝，在Cache Line 64字節(jié)數(shù)據(jù)塊上內(nèi)存地址是連續(xù)的猾浦，能被一次加載到Cache Line中，所以在訪問數(shù)組時灯抛，Cache Line命中率高，性能發(fā)揮到極致。

public int run(int[] row, int[] column) {    int sum = 0;    for(int i = 0; i < 16; i++ ) {        sum += row[i] * column[i];    }    return sum;}

而上面例子中變量i則體現(xiàn)了時間局部性般甲，i作為計數(shù)器被頻繁操作杰标，一直存放在寄存器中，每次從寄存器訪問纵竖，而不是從主存甚至磁盤訪問漠烧。雖然連續(xù)緊湊的內(nèi)存分配帶來高性能，但并不代表它一直都能帶來高性能靡砌。如果把它放在多線程中將會發(fā)生什么呢已脓？如圖：

圖片描述

數(shù)據(jù)X、Y通殃、Z被加載到同一Cache Line中度液，線程A在Core1修改X，線程B在Core2上修改Y。根據(jù)MESI大法堕担，假設(shè)是Core1是第一個發(fā)起操作的CPU核已慢，Core1上的L1 Cache Line由S（共享）狀態(tài)變成M（修改，臟數(shù)據(jù)）狀態(tài)照宝，然后告知其他的CPU核蛇受，圖例則是Core2，引用同一地址的Cache Line已經(jīng)無效了厕鹃；當(dāng)Core2發(fā)起寫操作時兢仰，首先導(dǎo)致Core1將X寫回主存，Cache Line狀態(tài)由M變?yōu)镮（無效）剂碴，而后才是Core2從主存重新讀取該地址內(nèi)容把将，Cache Line狀態(tài)由I變成E（獨占），最后進(jìn)行修改Y操作忆矛， Cache Line從E變成M察蹲。可見多個線程操作在同一Cache Line上的不同數(shù)據(jù)催训，相互競爭同一Cache Line洽议，導(dǎo)致線程彼此牽制影響，變成了串行程序漫拭，降低了并發(fā)性亚兄。此時我們則需要將共享在多線程間的數(shù)據(jù)進(jìn)行隔離，使他們不在同一個Cache Line上采驻，從而提升多線程的性能审胚。

Cache Line偽共享處理方案

處理偽共享的兩種方式：

1. 增大數(shù)組元素的間隔使得不同線程存取的元素位于不同的cache line上。典型的空間換時間礼旅。（Linux cache機(jī)制與之相關(guān)）
2. 在每個線程中創(chuàng)建全局?jǐn)?shù)組各個元素的本地拷貝膳叨，然后結(jié)束后再寫回全局?jǐn)?shù)組。

在Java類中痘系，最優(yōu)化的設(shè)計是考慮清楚哪些變量是不變的菲嘴，哪些是經(jīng)常變化的，哪些變化是完全相互獨立的汰翠，哪些屬性一起變化龄坪。舉個例子：

public class Data{    long modifyTime;    boolean flag;    long createTime;    char key;    int value;}

假如業(yè)務(wù)場景中，上述的類滿足以下幾個特點：

1. 當(dāng)value變量改變時奴璃，modifyTime肯定會改變
2. createTime變量和key變量在創(chuàng)建后悉默，就不會再變化。
3. flag也經(jīng)常會變化苟穆，不過與modifyTime和value變量毫無關(guān)聯(lián)抄课。

當(dāng)上面的對象需要由多個線程同時的訪問時唱星，從Cache角度來說，就會有一些有趣的問題跟磨。當(dāng)我們沒有加任何措施時间聊，Data對象所有的變量極有可能被加載在L1緩存的一行Cache Line中。在高并發(fā)訪問下抵拘，會出現(xiàn)這種問題：

圖片描述

如上圖所示哎榴，每次value變更時，根據(jù)MESI協(xié)議僵蛛，對象其他CPU上相關(guān)的Cache Line全部被設(shè)置為失效尚蝌。其他的處理器想要訪問未變化的數(shù)據(jù)(key 和 createTime)時，必須從內(nèi)存中重新拉取數(shù)據(jù)充尉，增大了數(shù)據(jù)訪問的開銷飘言。

Padding 方式

正確的方式應(yīng)該將該對象屬性分組，將一起變化的放在一組驼侠，與其他屬性無關(guān)的屬性放到一組姿鸿，將不變的屬性放到一組。這樣當(dāng)每次對象變化時倒源，不會帶動所有的屬性重新加載緩存苛预，提升了讀取效率。在JDK1.8以前笋熬，我們一般是在屬性間增加長整型變量來分隔每一組屬性热某。被操作的每一組屬性占的字節(jié)數(shù)加上前后填充屬性所占的字節(jié)數(shù)，不小于一個cache line的字節(jié)數(shù)就可以達(dá)到要求：

public class DataPadding{    long a1,a2,a3,a4,a5,a6,a7,a8;//防止與前一個對象產(chǎn)生偽共享    int value;    long modifyTime;    long b1,b2,b3,b4,b5,b6,b7,b8;//防止不相關(guān)變量偽共享;    boolean flag;    long c1,c2,c3,c4,c5,c6,c7,c8;//    long createTime;    char key;    long d1,d2,d3,d4,d5,d6,d7,d8;//防止與下一個對象產(chǎn)生偽共享}

通過填充變量突诬，使不相關(guān)的變量分開

Contended注解方式

在JDK1.8中苫拍，新增了一種注解@sun.misc.Contended芜繁，來使各個變量在Cache line中分隔開旺隙。注意，jvm需要添加參數(shù)-XX:-RestrictContended才能開啟此功能
用時骏令，可以在類前或?qū)傩郧凹由洗俗⑨專?/p>

// 類前加上代表整個類的每個變量都會在單獨的cache line中@sun.misc.Contended@SuppressWarnings("restriction")public class ContendedData {    int value;    long modifyTime;    boolean flag;    long createTime;    char key;}或者這種：// 屬性前加上時需要加上組標(biāo)簽@SuppressWarnings("restriction")public class ContendedGroupData {    @sun.misc.Contended("group1")    int value;    @sun.misc.Contended("group1")    long modifyTime;    @sun.misc.Contended("group2")    boolean flag;    @sun.misc.Contended("group3")    long createTime;    @sun.misc.Contended("group3")    char key;}

采取上述措施圖示：

圖片描述

JDK1.8 ConcurrentHashMap的處理

java.util.concurrent.ConcurrentHashMap在這個如雷貫耳的Map中蔬捷，有一個很基本的操作問題，在并發(fā)條件下進(jìn)行++操作榔袋。因為++這個操作并不是原子的周拐，而且在連續(xù)的Atomic中，很容易產(chǎn)生偽共享（false sharing）凰兑。所以在其內(nèi)部有專門的數(shù)據(jù)結(jié)構(gòu)來保存long型的數(shù)據(jù):

 （openjdk\jdk\src\share\classes\java\util\concurrent\ConcurrentHashMap.java line:2506）：     /* ---------------- Counter support -------------- */     /**     * A padded cell for distributing counts.  Adapted from LongAdder     * and Striped64\.  See their internal docs for explanation.     */    @sun.misc.Contended static final class CounterCell {        volatile long value;        CounterCell(long x) { value = x; }    }

我們看到該類中妥粟，是通過@sun.misc.Contended達(dá)到防止false sharing的目的

JDK1.8 Thread 的處理

java.lang.Thread在java中，生成隨機(jī)數(shù)是和線程有著關(guān)聯(lián)吏够。而且在很多情況下勾给，多線程下產(chǎn)生隨機(jī)數(shù)的操作是很常見的滩报，JDK為了確保產(chǎn)生隨機(jī)數(shù)的操作不會產(chǎn)生false sharing ,把產(chǎn)生隨機(jī)數(shù)的三個相關(guān)值設(shè)為獨占cache line。

（openjdk\jdk\src\share\classes\java\lang\Thread.java line:2023）     // The following three initially uninitialized fields are exclusively    // managed by class java.util.concurrent.ThreadLocalRandom. These    // fields are used to build the high-performance PRNGs in the    // concurrent code, and we can not risk accidental false sharing.    // Hence, the fields are isolated with @Contended.     /** The current seed for a ThreadLocalRandom */    @sun.misc.Contended("tlr")    long threadLocalRandomSeed;     /** Probe hash value; nonzero if threadLocalRandomSeed initialized */    @sun.misc.Contended("tlr")    int threadLocalRandomProbe;     /** Secondary seed isolated from public ThreadLocalRandom sequence */    @sun.misc.Contended("tlr")    int threadLocalRandomSecondarySeed;

Java中對Cache line經(jīng)典設(shè)計

Disruptor框架

認(rèn)識Disruptor

LMAX是在英國注冊并受到FCA監(jiān)管的外匯黃金交易所播急。也是歐洲第一家也是唯一一家采用多邊交易設(shè)施Multilateral Trading Facility（MTF）擁有交易所牌照和經(jīng)紀(jì)商牌照的歐洲頂級金融公司脓钾。LMAX的零售金融交易平臺，是建立在JVM平臺上桩警，核心是一個業(yè)務(wù)邏輯處理器可训，它能夠在一個線程里每秒處理6百萬訂單。業(yè)務(wù)邏輯處理器的核心就是Disruptor（注捶枢，本文Disruptor基于當(dāng)前最新3.3.6版本）握截，這是一個Java實現(xiàn)的并發(fā)組件，能夠在無鎖的情況下實現(xiàn)網(wǎng)絡(luò)的Queue并發(fā)操作烂叔，它確保任何數(shù)據(jù)只由一個線程擁有以進(jìn)行寫訪問川蒙，從而消除寫爭用的設(shè)計， 這種設(shè)計被稱作“破壞者”长已，也是這樣命名這個框架的畜眨。

Disruptor是一個線程內(nèi)通信框架，用于線程里共享數(shù)據(jù)术瓮。與LinkedBlockingQueue類似康聂，提供了一個高速的生產(chǎn)者消費者模型，廣泛用于批量IO讀寫胞四，在硬盤讀寫相關(guān)的程序中應(yīng)用的十分廣泛恬汁，Apache旗下的HBase、Hive辜伟、Storm等框架都有在使用Disruptor氓侧。LMAX 創(chuàng)建Disruptor作為可靠消息架構(gòu)的一部分，并將它設(shè)計成一種在不同組件中共享數(shù)據(jù)非车冀疲快的方法约巷。Disruptor運行大致流程入下圖：

圖片描述

圖中左側(cè)（Input Disruptor部分）可以看作多生產(chǎn)者單消費者模式。外部多個線程作為多生產(chǎn)者并發(fā)請求業(yè)務(wù)邏輯處理器（Business Logic Processor）旱捧，這些請求的信息經(jīng)過Receiver存放在粉紅色的圓環(huán)中独郎，業(yè)務(wù)處理器則作為消費者從圓環(huán)中取得數(shù)據(jù)進(jìn)行處理。右側(cè)（Output Disruptor部分）則可看作單生產(chǎn)者多消費者模式枚赡。業(yè)務(wù)邏輯處理器作為單生產(chǎn)者氓癌，發(fā)布數(shù)據(jù)到粉紅色圓環(huán)中，Publisher作為多個消費者接受業(yè)務(wù)邏輯處理器的結(jié)果贫橙。這里兩處地方的數(shù)據(jù)共享都是通過那個粉紅色的圓環(huán)贪婉，它就是Disruptor的核心設(shè)計RingBuffer。

Disruptor特點

1. 無鎖機(jī)制卢肃。
2. 沒有CAS操作疲迂，避免了內(nèi)存屏障指令的耗時星压。
3. 避開了Cache line偽共享的問題，也是Disruptor部分主要關(guān)注的主題鬼譬。

Disruptor對偽共享的處理

RingBuffer類

RingBuffer類（即上節(jié)中粉紅色的圓環(huán)）的類關(guān)系圖如下：

圖片描述

通過源碼分析娜膘，RingBuffer的父類，RingBufferFields采用數(shù)組來實現(xiàn)存放線程間的共享數(shù)據(jù)优质。下圖竣贪，第57行，entries數(shù)組巩螃。

圖片描述

前面分析過數(shù)組比鏈表演怎、樹更具有緩存友好性，此處不做細(xì)表避乏。不使用LinkedBlockingQueue隊列爷耀，是基于無鎖機(jī)制的考慮。詳細(xì)分析可參考拍皮，并發(fā)編程網(wǎng)的翻譯歹叮。這里我們主要分析RingBuffer的繼承關(guān)系中的填充，解決緩存?zhèn)喂蚕韱栴}铆帽。如下圖：

圖片描述

圖片描述

依據(jù)JVM對象繼承關(guān)系中父類屬性與子類屬性咆耿，內(nèi)存地址連續(xù)排列布局，RingBufferPad的protected long p1,p2,p3,p4,p5,p6,p7;作為緩存前置填充爹橱，RingBuffer中的protected long p1,p2,p3,p4,p5,p6,p7;作為緩存后置填充萨螺。這樣任意線程訪問RingBuffer時，RingBuffer放在父類RingBufferFields的屬性愧驱，都是獨占一行Cache line不會產(chǎn)生偽共享問題慰技。如圖，RingBuffer的操作字段在RingBufferFields中组砚，使用rbf標(biāo)識：

圖片描述

按照一行緩存64字節(jié)計算吻商，前后填充56字節(jié)（7個long），中間大于等于8字節(jié)的內(nèi)容都能獨占一行Cache line惫确，此處rbf是大于8字節(jié)的手报。

Sequence類

Sequence類用來跟蹤RingBuffer和事件處理器的增長步數(shù)蚯舱，支持多個并發(fā)操作包括CAS指令和寫指令改化。同時使用了Padding方式來實現(xiàn)，如下為其類結(jié)構(gòu)圖及Padding的類枉昏。

Sequence里在volatile long value前后放置了7個long padding陈肛，來解決偽共享的問題。示意如圖兄裂，此處Value等于8字節(jié)：

也許讀者應(yīng)該會認(rèn)為這里的圖示比上面RingBuffer的圖示更好理解句旱，這里的操作屬性只有一個value阳藻，兩個圖相互結(jié)合就更能理解了。

Sequencer的實現(xiàn)

在RingBuffer構(gòu)造函數(shù)里面存在一個Sequencer接口谈撒，用來遍歷數(shù)據(jù)腥泥，在生產(chǎn)者和消費者之間傳遞數(shù)據(jù)。Sequencer有兩個實現(xiàn)類啃匿，單生產(chǎn)者模式的實現(xiàn)SingleProducerSequencer與多生產(chǎn)者模式的實現(xiàn)MultiProducerSequencer蛔外。它們的類結(jié)構(gòu)如圖：

單生產(chǎn)者是在Cache line中使用padding方式實現(xiàn)，源碼如下：

圖片描述

多生產(chǎn)者則是使用 sun.misc.Unsafe來實現(xiàn)的溯乒。如下圖：

圖片描述