CPU Cache和Cache更新套路

Reading

出现的原因

十年CPU的频率不断提升，而受制于制造工艺和成本限制，目前计算机的内存主要是DRAM并且在访问速度上没有质的突破。因此，CPU的处理速度和内存的访问速度差距越来越大，甚至可以达到上万倍。

多级cache

随着科技发展，热点数据的体积越来越大，单纯的增加一级缓存大小的性价比已经很低了。因此，就慢慢出现了在一级缓存(L1 Cache)和内存之间又增加一层访问速度和成本都介于两者之间的二级缓存(L2 Cache)。此外，又由于程序指令和程序数据的行为和热点分布差异很大，因此L1 Cache也被划分成L1i(i for instruction)和L1d(d for data)两种专门用途的缓存

什么是Cache Line

Cache Line可以简单的理解为CPU Cache中的最小缓存单位。目前主流的CPU Cache的Cache Line大小都是64Bytes。假设我们有一个512字节的一级缓存，那么按照64B的缓存单位大小来算，这个一级缓存所能存放的缓存个数就是512/64 = 8个。具体参见下图。

还有另一种理解：

The minimum amount of cache which can be loaded or stored to memory

缓存关联性

缓存设计的一个关键决定是确保每个主存块(chunk)能够存储在任何一个缓存槽里，或者只是其中一些（译者注：此处一个槽位就是一个缓存行）。有三种方式将缓存槽映射到主存块中：

直接映射(Direct mapped cache) 每个内存块只能映射到一个特定的缓存槽。一个简单的方案是通过块索引chunk_index映射到对应的槽位(chunk_index % cache_slots)。被映射到同一内存槽上的两个内存块是不能同时换入缓存的。（译者注：chunk_index可以通过物理地址/缓存行字节计算得到）
N路组关联(N-way set associative cache) 每个内存块能够被映射到N路特定缓存槽中的任意一路。比如一个16路缓存，每个内存块能够被映射到16路不同的缓存槽。一般地，具有一定相同低bit位地址的内存块将共享16路缓存槽。（译者注：相同低位地址表明相距一定单元大小的连续内存）
完全关联(Fully associative cache) 每个内存块能够被映射到任意一个缓存槽。操作效果上相当于一个散列表。代价是搜索缓存行很慢。

一般输入的是N路关联的缓存。但是同样面对一个问题，如何获取对应内存的缓存行。

缓存更新的套路

有一种方案是先更新缓存，然后在更新数据库，这种方式是错误的。两个并发操作，一个更新，一个查询，更新操作先删除缓存，查询操作没有命中缓存，而是将老数据cache，然后更新操作更新了数据库，这样导致了数据库中的数据和缓存中的不一致，而且是长时间的不一致。

Cache Aside Pattern

失效：应用程序先从cache取数据，没有得到，则从数据库中取数据，成功后，放到缓存中。
命中：应用程序从cache中取数据，取到后返回。
更新：先把数据存到数据库中，成功后，再让缓存失效

还是上面的问题：首先，没有了删除cache数据的操作了，而是先更新了数据库中的数据，此时，缓存依然有效，所以，并发的查询操作拿的是没有更新的数据，但是，更新操作马上让缓存的失效了，后续的查询操作再把数据从数据库中拉出来。为什么不是写完数据库后更新缓存？主要是怕两个并发的写操作导致脏数据（缓存的数据和数据库的数据长时间不一致）。其实，Cache Aside还是有并发问题的

比如，一个是读操作，但是没有命中缓存，然后就到数据库中取数据，此时来了一个写操作，写完数据库后，让缓存失效，然后，之前的那个读操作再把老的数据放进去，所以，会造成脏数据。

但，这个case理论上会出现，不过，实际上出现的概率可能非常低，因为这个条件需要发生在读缓存时缓存失效，而且并发着有一个写操作。而实际上数据库的写操作会比读操作慢得多，而且还要锁表，而读操作必需在写操作前进入数据库操作，而又要晚于写操作更新缓存，所有的这些条件都具备的概率基本并不大

Read/Write Through Pattern。

与Cache Aside相比，可以理解为，应用认为后端就是一个单一的存储，而存储自己维护自己的Cache，下面的图中，lower memory可以理解磁盘，相当于内存是磁盘的缓存的逻辑。

Pasted image 20201123153456

Write Behind Caching Pattern 类似于linux中的page-cache的套路

伪共享导致的cache false-sharing

// 顺序访问
func BenchmarkMatrixCombination(b *testing.B) {
    matrixA := createMatrix(matrixLength)
    matrixB := createMatrix(matrixLength)

    for n := 0; n < b.N; n++ {
        for i := 0; i < matrixLength; i++ {
            for j := 0; j < matrixLength; j++ {
                matrixA[i][j] = matrixA[i][j] + matrixB[i][j]
            }
        }
    }
}

// 倒叙访问
// 性能大幅下降
func BenchmarkMatrixReversedCombination(b *testing.B) {
    matrixA := createMatrix(matrixLength)
    matrixB := createMatrix(matrixLength)

    for n := 0; n < b.N; n++ {
        for i := 0; i < matrixLength; i++ {
            for j := 0; j < matrixLength; j++ {
                matrixA[i][j] = matrixA[i][j] + matrixB[j][i]
            }
        }
    }
}
// 利用block来建立L1 cache
func BenchmarkMatrixReversedCombinationPerBlock(b *testing.B) {
    matrixA := createMatrix(matrixLength)
    matrixB := createMatrix(matrixLength)
    blockSize := 8

    for n := 0; n < b.N; n++ {
        for i := 0; i < matrixLength; i += blockSize {
            for j := 0; j < matrixLength; j += blockSize {
                for ii := i; ii < i+blockSize; ii++ {
                    for jj := j; jj < j+blockSize; jj++ {
                        matrixA[ii][jj] = matrixA[ii][jj] + matrixB[jj][ii]
                    }
                }
            }
        }
    }
}

// false-sharing
// https://taohuawu.club/cpu-caches-theory-and-application
type SimpleStruct struct {
    n int
}

// 两个变量靠的很近，位于两个核同一个缓存行中，那么一个go routine的改变var1, 那么另一个核上的缓存行会失效，另一个core读取var2的时候，看到var2失效了，会通过MESI协议获取新的缓存行。
func BenchmarkStructureFalseSharing(b *testing.B) {
    structA := SimpleStruct{}
    structB := SimpleStruct{}
    wg := sync.WaitGroup{}

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        wg.Add(2)
        go func() {
            for j := 0; j < M; j++ {
                structA.n += j
            }
            wg.Done()
        }()
        go func() {
            for j := 0; j < M; j++ {
                structB.n += j
            }
            wg.Done()
        }()
        wg.Wait()
    }
}

BruceChen7 / gitblog