摘要：前面了解存儲結構對性能優化是非常關鍵的，不管是數據庫，消息中間件，負載均衡器等性能優化的道理都是相通的，比如說性能優化，那么我們也需要從內部的存儲和體系結構出發，分析樹，塊緩存，算法，邏輯讀，，分析統計數據等，在分析邏輯讀的時候需要考慮訪問

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

本文主要介紹下cache的層次和java中可以優化或關注的地方

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

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

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

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

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

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

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

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

cpu cache是一個復雜的體系，這里先介紹基本的層次結構，cache的映射方式，一致性協議等略過
大家先看下cpu cache的整體結構

PS: QPI（quick path interconnect）實現芯片之間的快速互聯,不占用內存總線帶寬

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

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

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

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

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

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

網絡io的tx/rx親緣性以及收發的core和處理的core的親緣性

java進程內部，比如EventLoop的親緣性

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

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

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

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

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

下面是我的JMH測試數據(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的節點對象，大致估下64/4=16，比如需要遍歷5000，那么5000/16=312個cache line的掃描，而且循環調用可以反復使用這些cache line，另外，ArrayList的elementData數組元素一定是連續分配的，所以arraycopy的時候可以最大化利用cache line

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

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

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

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

下面我們來看兩個場景的測試結果
先設計幾個測試的類，分別是Level1,Level2,Level3,Level4,每個類在heap中占24個字節（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();
        }
    }

}

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

大致畫了下pointer chasing的內存分布圖

有沒有即有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，產生更多的cache 淘汰
簡單對比了下面兩個對象的效率,后者快2倍多，FatModel除了占用更多的內存，需要掃描更多的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的場景，見下面章節

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

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

很多開源的高性能無鎖結構都有這方面的處理，不如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里實現的比較heavy，本身切換的效率也比coroutine切換低很多
另外，頻繁context switch會導致cache hit下降（多個線程頻繁交互的使用cache）
如果線程需要充分利用cache，最好是non-blocking,降低csw,然后持有cpu盡量多的時間批量干活

內存的話題太大，挑幾個介紹下

首先，大家可能平常經常聽到一些詞，用戶態啊，內核態啊，zero copy啊，但是又有點疑惑，底下到底是怎么搞的

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

簡單來說，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 , 其他非文件的運行時數據
2.4版本的內核之前，文件的內容也會在buffer存儲，也就是需要存儲2次，2.4版本之后，buffer不會再存儲再Cache中的內容

//todo 補充更細粒度的內存視圖

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

//todo mmap性能對比