摘要：前面了解存儲結(jié)構(gòu)對性能優(yōu)化是非常關(guān)鍵的，不管是數(shù)據(jù)庫，消息中間件，負載均衡器等性能優(yōu)化的道理都是相通的，比如說性能優(yōu)化，那么我們也需要從內(nèi)部的存儲和體系結(jié)構(gòu)出發(fā)，分析樹，塊緩存，算法，邏輯讀，，分析統(tǒng)計數(shù)據(jù)等，在分析邏輯讀的時候需要考慮訪問

了解存儲結(jié)構(gòu)對性能優(yōu)化是非常關(guān)鍵的，不管是數(shù)據(jù)庫，消息中間件，負載均衡器,api gateway等
性能優(yōu)化的道理都是相通的，比如說Oracle性能優(yōu)化，那么我們也需要從Oracle內(nèi)部的存儲和體系結(jié)構(gòu)出發(fā)，分析B*樹，塊緩存，JOIN算法，邏輯讀，Latch/Lock，分析統(tǒng)計數(shù)據(jù)等，在分析邏輯讀的時候需要考慮訪問的順序及存儲的順序，這里都涉及到如何最大化使用各層的Cache

本文主要介紹下cache的層次和java中可以優(yōu)化或關(guān)注的地方

現(xiàn)在計算機體系里，根據(jù)讀寫的速度，可以分為以下層次，這里遠程也可以根據(jù)讀寫速度再細分，比如Redis可以作為Mysql的上一級cache

不同的存儲訪問延時差別甚大，實現(xiàn)的細節(jié)也有很大的差別
比如下圖的SRAM和DRAM

如何利用好每一個層次的cache，對系統(tǒng)的性能至關(guān)重要，比如操作系統(tǒng)的Page Cache, Buffer Cache , Oracle的block cache,比如我們常用的java on/off-heap cache，Jedis/Memcached等。
因為篇幅有限，本文主要挑L0-L4進行具體介紹，以及我們設(shè)計程序的時候需要考慮到哪些問題以追求極致的性能。

L0-L4會涉及到JVM的內(nèi)存模型，大家可以先不關(guān)心這個，JMM是另外一個話題（涉及cpu 指令流水，store buffer,invalid message queue,memory barrier等）,這里不做介紹，下次找時間完整的寫一篇，順便學學JCStressTest

寄存器是存儲結(jié)構(gòu)里的L0緩存，寄存器速度是最快的，畢竟是直接跟ALU（Arithmetric Logic Uint in CPU）打交道的，不快能行嗎

下圖X86-64會有16個寄存器(更多的寄存器，可以將一部分函數(shù)調(diào)用的參數(shù)直接取寄存器，節(jié)約了棧上分配及訪問的時間),IA32只有8個

寄存器的優(yōu)化主要在編譯器或/JIT層面，比如X86-64有16個寄存器，可以將一部分函數(shù)調(diào)用的參數(shù)直接取寄存器，節(jié)約了棧上分配及訪問的時間等。
寄存器java程序員不用怎么care

首先看為啥要有L1-L3 cache,如圖所示，cpu的發(fā)展速度要遠高于DRAM，當出現(xiàn)數(shù)量級的差異的時候，就需要中間加一層cache，來緩沖這個數(shù)量級的差異帶來的巨大影響，這個也適用于上面的存儲層次

cpu cache是一個復(fù)雜的體系，這里先介紹基本的層次結(jié)構(gòu)，cache的映射方式，一致性協(xié)議等略過
大家先看下cpu cache的整體結(jié)構(gòu)

PS: QPI（quick path interconnect）實現(xiàn)芯片之間的快速互聯(lián),不占用內(nèi)存總線帶寬

Cache Line 是CPU Cache的最小緩存單位,一般大小是64個字節(jié)
完整的了解看 https://en.wikipedia.org/wiki...

好了，回到性能優(yōu)化的主題，我們java程序員，如何做到高效的使用CPU cache呢，或則，我們需要關(guān)心哪些地方會對性能產(chǎn)生較大影響。

如果某一個請求，有多個core處理，那么請求相關(guān)的cache line需要在多個core之間"copy"，其實這里也有一個zero copy的概念，就是在多個core之間的cache line zero copy(自己發(fā)明一個。。。)

為了達到這個目的，有下面幾個需要注意的地方

將請求綁定到某一個線程/進程

利用OS的soft cpu affinity或手動綁定，將某一個線程/進程綁定到固定的core

網(wǎng)絡(luò)io的tx/rx親緣性以及收發(fā)的core和處理的core的親緣性

java進程內(nèi)部，比如EventLoop的親緣性

這里核心的思路是解決各種親緣性，如cpu 親緣性, io 親緣性, 應(yīng)用的請求親緣性，netty的EventLoop親緣性, 目的還是讓請求或某個切面的請求盡量在同一個core處理，以最大化的利用cache，而且這個切面的一些共享數(shù)據(jù)都可以不用加鎖，最大化系統(tǒng)的并行程度

我們看看Google Maglev中是如何處理的
Maglev 是google的負載均衡器（類似于LVS,但是Maglev實現(xiàn)的更底層）
Maglev中根據(jù)連接的五元組（這里除了src ip,port dst ip,port外，還有protocal version）將packet hash到某一個packet thread處理(packet thread跟core綁定),然后再根據(jù)packet thread自己的緩存映射到service ip(假設(shè)之前已經(jīng)映射過),這里的優(yōu)勢是

packet不會在多個core之間交互，zero cache line copy

packet可以無鎖的使用或更新到service ip的映射

我們在設(shè)計數(shù)據(jù)結(jié)構(gòu)和算法時，除了算法理論的時間和空間復(fù)雜度，還要考慮集合是否緩存友好，比如ArrayList和LinkedList這兩種數(shù)據(jù)結(jié)構(gòu)，很多人認為LinkedList適合插入節(jié)點的場景，因為ArrayList需要arraycopy，其實是不一定的

下面是我的JMH測試數(shù)據(jù)(mbp i7 2.5G 單線程,java 1.8.0_65)

@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 2, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(1)
@State(Scope.Benchmark)
@Threads(1)
public class LinkedListTest {
    private int size = 10000;
    @Param({"1", "500", "1000", "5000"})
    private int offset;
    @Param({"true", "false"})
    private boolean arrayScanIndex;
    LinkedList linkedList = new LinkedList();
    ArrayList arrayList = new ArrayList(size + 1);

    public LinkedListTest() {
        for (int i = 0; i < size; i++) {
            linkedList.add(new Object());
        }
        for (int i = 0; i < size; i++) {
            arrayList.add(new Object());
        }
    }

    @Benchmark
    public void testLinkedList() {
        linkedList.add(offset, new Object());
        linkedList.remove(offset);
    }

    @Benchmark
    public void tetArrayList() {
        if (arrayScanIndex) {
            for (int i = 0; i < offset; i++) {
                arrayList.get(i);
            }
        }
        arrayList.add(offset, new Object());
        if (arrayScanIndex) {
            for (int i = 0; i < offset; i++) {
                arrayList.get(i);
            }
        }
        arrayList.remove(offset);
    }
}

上面開不開arrayScanIndex，對ArrayList性能基本沒有影響，因為一個cache line可以存多個array的節(jié)點對象，大致估下64/4=16，比如需要遍歷5000，那么5000/16=312個cache line的掃描，而且循環(huán)調(diào)用可以反復(fù)使用這些cache line，另外，ArrayList的elementData數(shù)組元素一定是連續(xù)分配的，所以arraycopy的時候可以最大化利用cache line

而LinkedList但是因為他的Node節(jié)點占用40個字節(jié)，item這里占用16個字節(jié)，那么遍歷5000個節(jié)點，需要5000*56/64=4375個cache line(粗略估計)，根據(jù)測試結(jié)果來看，前面的cache line已被換出，無法循環(huán)使用

只有在index非常小的時候，LinkedList才有優(yōu)勢,另外，ArrayList比LinkedList最壞情況好得多

這個例子不是說讓大家使用ArrayList，因為LinkedList可以用輔助結(jié)構(gòu)來加快index速度，而是說明一個問題，算法之外，考慮cache友好

在保持合理的抽象層度的同時，需要盡可能降低under lying數(shù)據(jù)的尋址次數(shù),從而減少cache的淘汰，提高cache hit
我們有時候?qū)慾ava對象，一層套一層，5，6層不算啥，a->b->c->d->data
我們用pointer chasing 來表示這種現(xiàn)象

下面我們來看兩個場景的測試結(jié)果
先設(shè)計幾個測試的類，分別是Level1,Level2,Level3,Level4,每個類在heap中占24個字節(jié)（64位機器）

//以Level3舉例
public class Level3 {
    public Level2 level2 = new Level2();

    public int get(){
        return level2.level1.x;
    }
}

@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 2, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 2, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(1)
@State(Scope.Benchmark)
@Threads(1)
public class PointerChasingTest {
    private int size = 10000;
    private int[] list0 = new int[size];
    private Level1[] list1 = new Level1[size];
    private Level2[] list2 = new Level2[size];
    private Level3[] list3 = new Level3[size];
    private Level4[] list4 = new Level4[size];

    public PointerChasingTest() {
        for (int i = 0; i < size; i++) {
            list0[i] = i;
        }
        for (int i = 0; i < size; i++) {
            list1[i] = new Level1();
        }

        for (int i = 0; i < size; i++) {
            list2[i] = new Level2();
        }

        for (int i = 0; i < size; i++) {
            list3[i] = new Level3();
        }

        for (int i = 0; i < size; i++) {
            list4[i] = new Level4();
        }
    }

    @Benchmark
    public void testLevel0() {
        for (int i = 0; i < size; i++) {
            if (list0[i] == i) {

            }
            ;
        }
    }

    @Benchmark
    public void testLevel1() {
        for (int i = 0; i < size; i++) {
            list1[i].get();
        }
    }

    @Benchmark
    public void testLevel2() {
        for (int i = 0; i < size; i++) {
            list2[i].get();
        }
    }

    @Benchmark
    public void testLevel3() {
        for (int i = 0; i < size; i++) {
            list3[i].get();
        }
    }

    @Benchmark
    public void testLevel4() {
        for (int i = 0; i < size; i++) {
            list4[i].get();
        }
    }

}

從測試結(jié)果可以看出，pointer chasing越深，性能越差
另外，原始類型比Object性能好幾個數(shù)量級，一個是原始類型沒有pointer chasing，另一個是一個cache line可以存儲的int要遠遠多余Object，Object在JVM中是臃腫的

大致畫了下pointer chasing的內(nèi)存分布圖

有沒有即有ArrayList這樣的面向Object的集合抽象，又有原始類型的性能？
有，java project Valhalla

This aims to “reboot the layout of data in memory” in order to reduce the amount of memory used fetching objects from memory compared to, for example, arithmetic calculations. Not all classes need mutability or polymorphism. To do this, the project explores value types, generic specialisation and enhanced volatiles, and more.
Value types would provide JVM infrastructure to work with immutable, reference-free objects. This will be essential when high performance is required, and pairs of numbers need to be returned. Using primitives avoids allocation, but an object to wrap around the pair gives the benefit of abstraction. This project looks to open the door to user-defined abstract data types that perform like primitives

我們知道，java對象在heap中是很臃腫的（所有才會用公司在保持api不變的同時，直接讀寫自己的raw data...），過于臃腫的對象，勢必需要更多的cache line，產(chǎn)生更多的cache 淘汰
簡單對比了下面兩個對象的效率,后者快2倍多，F(xiàn)atModel除了占用更多的內(nèi)存，需要掃描更多的cache line

public class FatModel {
    long a, b, c, d, e, f;

    public long get() {
        return a & b & c & d & e & f;
    }
}

public class ThinModel {
    byte a, b, c, d, e, f;

    public byte get() {
        return (byte) (a & b & c & d & e & f);
    }
}

//todo 測試二進制raw對象的query 性能
這里需要注意false sharing的場景，見下面章節(jié)

在設(shè)計無鎖高并發(fā)的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)時，都會用到CAS或volatile，為了支持更高的并行度，需要將CAS的變量細化成數(shù)組，分配給不同的core，每一個CAS變量負責一個區(qū)域或一個切面，那么在不同切面的請求，可以獨立的進行CAS并發(fā)控制。
然額，因為JVM對數(shù)組元素對象傾向于連續(xù)分配,會導(dǎo)致多個對象在同一個cache line, 導(dǎo)致不同切面的請求，實際上是對同一個cache line競爭，這種情況就是False Sharing
不管是False Sharing還是別的原因，多個core對同一個cache line的爭用(如lock xcmchg指令)會導(dǎo)致
對性能會產(chǎn)生較大影響
在我本機JMH 2*core線程測試AtomicLong和LongAdder，后者性能是前者10x，當然內(nèi)存占用也更多)

下圖解釋了False Sharing為什么會導(dǎo)致cache contention
解決Flase Sharing: 在對象中加cache line padding，使操作的對象在不同的cache line，從而減少cache contention

很多開源的高性能無鎖結(jié)構(gòu)都有這方面的處理，不如Disruptor,或則JDK自帶的LongAdder

我們測試一下

@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(1)
@State(Scope.Benchmark)
@Threads(16)
public class FalseSharingTest {
    private int threads = 16;
    private FalseSharing[] counters1 = new FalseSharing[threads];
    private FalseSharingPadding[] counters2 = new FalseSharingPadding[threads];
    public FalseSharingTest(){
        for(int i = 0 ; i < threads ; i++){
            counters1[i] = new FalseSharing();
        }
        for(int i = 0 ; i < threads ; i++){
            counters2[i] = new FalseSharingPadding();
        }
    }

    @Benchmark
    public void testFalseSharing(ThreadParams params){
        counters1[params.getThreadIndex()%threads].value=2;
    }

    @Benchmark
    public void testFalseSharingPadding(ThreadParams params){
        counters2[params.getThreadIndex()%threads].value=2;
    }
}

老生常談了，context switch會進行model switch（user->kernel）,再進行線程切換
Context Switch在OS里實現(xiàn)的比較heavy，本身切換的效率也比coroutine切換低很多
另外，頻繁context switch會導(dǎo)致cache hit下降（多個線程頻繁交互的使用cache）
如果線程需要充分利用cache，最好是non-blocking,降低csw,然后持有cpu盡量多的時間批量干活

內(nèi)存的話題太大，挑幾個介紹下

首先，大家可能平常經(jīng)常聽到一些詞，用戶態(tài)啊，內(nèi)核態(tài)啊，zero copy啊，但是又有點疑惑，底下到底是怎么搞的

我們先從虛擬地址，物理地址，進程的地址空間說起
todo:待補充細節(jié)

簡單來說，cache 和 buffer 定位如下

The page cache caches pages of files to optimize file I/O. The buffer cache caches disk blocks to optimize block I/O.

page cache
file cache,mmap,direct buffer…
buffer cache
metadata(permission…) , raw io , 其他非文件的運行時數(shù)據(jù)
2.4版本的內(nèi)核之前，文件的內(nèi)容也會在buffer存儲，也就是需要存儲2次，2.4版本之后，buffer不會再存儲再Cache中的內(nèi)容

//todo 補充更細粒度的內(nèi)存視圖

我們主要關(guān)心的是Page Cache,Buffer Cache對我們來說不需要重點去關(guān)注
1.Zero Copy

//todo mmap性能對比