教你打造高性能的Go缓存库

我在看一些优秀的开源库的时候看到一个有意思的缓存库 fastcache，在它的介绍主要有以下几点特点：

创新互联主要从事成都网站建设、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务高县,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108

  • 读写数据要快，即使在并发下;
  • 即使在数 GB 的缓存中，也要保持很好的性能，以及尽可能减少 GC 次数;
  • 设计尽可能简单;

本文会通过模仿它写一个简单的缓存库，从而研究其内核是如何实现这样的目标的。希望各位能有所收获。

设计思想

在项目中，我们经常会用到 Go 缓存库比如说 patrickmn/go-cache库。但很多缓存库其实都是用一个简单的 Map 来存放数据，这些库在使用的时候，当并发低，数据量少的时候是没有问题的，但是在数据量比较大并发比较高的时候会延长 GC 时间，增加内存分配次数。

比如，我们使用一个简单的例子：

 
 
 
 
    
  
  
  
  
  1. func main() { 
    2. 
  
  
  
  
  2.  a := make(map[string]string, 1e9) 
    3. 
  
  
  
  
  3.  for i := 0; i < 10; i++ { 
    4. 
  
  
  
  
  4.   runtime.GC() 
    5. 
  
  
  
  
  5.  } 
    6. 
  
  
  
  
  6.  runtime.KeepAlive(a) 
    7. 
  
  
  
  
  7. } 
    8.

在这个例子中，预分配了大小是10亿(1e9) 的 map，然后我们通过 gctrace 输出一下 GC 情况：

做实验的环境是 Linux，机器配置是 16C 8G ，想要更深入理解 GC，可以看这篇：《 Go 语言 GC 实现原理及源码分析 https://www.luozhiyun.com/archives/475 》

 
 
 
 
    
  
  
  
  
  1. [root@localhost gotest]# GODEBUG=gctrace=1 go run main.go 
    2. 
  
  
  
  
  2. ... 
    3. 
  
  
  
  
  3. gc 6 @13.736s 17%: 0.010+1815+0.004 ms clock, 0.17+0/7254/21744+0.067 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    4. 
  
  
  
  
  4. gc 7 @15.551s 18%: 0.012+1796+0.005 ms clock, 0.20+0/7184/21537+0.082 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    5. 
  
  
  
  
  5. gc 8 @17.348s 19%: 0.008+1794+0.004 ms clock, 0.14+0/7176/21512+0.070 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    6. 
  
  
  
  
  6. gc 9 @19.143s 19%: 0.010+1819+0.005 ms clock, 0.16+0/7275/21745+0.085 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    7. 
  
  
  
  
  7. gc 10 @20.963s 19%: 0.011+1844+0.004 ms clock, 0.18+0/7373/22057+0.076 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    8.

上面展示了最后 5 次 GC 的情况，下面我们看看具体的含义是什么：

 
 
 
 
    
  
  
  
  
  1. gc 1 @0.004s 4%: 0.22+1.4+0.021 ms clock, 1.7+0.009/0.40/0.073+0.16 ms cpu, 4->5->1 MB, 5 MB goal, 8 P  
    2. 
  
  
  
  
  2. gc 10 @20.963s 19%: 0.011+1844+0.004 ms clock, 0.18+0/7373/22057+0.076 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    3. 
  
  
  
  
  3.  
    4. 
  
  
  
  
  4. gc 10 ：程序启动以来第10次GC  
    5. 
  
  
  
  
  5. @20.963s：距离程序启动到现在的时间  
    6. 
  
  
  
  
  6. 19%：当目前为止，GC 的标记工作所用的CPU时间占总CPU的百分比 
    7.

垃圾回收的时间

 
 
 
 
    
  
  
  
  
  1. gc 1 @0.004s 4%: 0.22+1.4+0.021 ms clock, 1.7+0.009/0.40/0.073+0.16 ms cpu, 4->5->1 MB, 5 MB goal, 8 P 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. gc 10 @20.963s 19%: 0.011+1844+0.004 ms clock, 0.18+0/7373/22057+0.076 ms cpu, 73984->73984->73984 MB, 147968 MB goal, 16 P (forced) 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. gc 10 ：程序启动以来第10次GC 
    6. 
  
  
  
  
  6. @20.963s：距离程序启动到现在的时间 
    7. 
  
  
  
  
  7. 19%：当目前为止，GC 的标记工作所用的CPU时间占总CPU的百分比 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. 垃圾回收的时间 
    10. 
  
  
  
  
  10. 0.011 ms：标记开始 STW 时间 
    11. 
  
  
  
  
  11. 1844 ms：并发标记时间 
    12. 
  
  
  
  
  12. 0.004 ms：标记终止 STW 时间 
    13. 
  
  
  
  
  13.  
    14. 
  
  
  
  
  14. 垃圾回收占用cpu时间 
    15. 
  
  
  
  
  15. 0.18 ms：标记开始 STW 时间 
    16. 
  
  
  
  
  16. 0 ms：mutator assists占用的时间 
    17. 
  
  
  
  
  17. 7373 ms：标记线程占用的时间 
    18. 
  
  
  
  
  18. 22057 ms：idle mark workers占用的时间 
    19. 
  
  
  
  
  19. 0.076 ms：标记终止 STW 时间 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. 内存 
    22. 
  
  
  
  
  22. 73984 MB：标记开始前堆占用大小 
    23. 
  
  
  
  
  23. 73984 MB：标记结束后堆占用大小 
    24. 
  
  
  
  
  24. 73984 MB：标记完成后存活堆的大小 
    25. 
  
  
  
  
  25. 147968 MB goal：标记完成后正在使用的堆内存的目标大小 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. 16 P：使用了多少处理器 
    28.

可以从上面的输出看到每次 GC 处理的时间非常的长，占用的 CPU 资源也非常多。那么造成这样的原因是什么呢?

string 实际上底层数据结构是由两部分组成，其中包含指向字节数组的指针和数组的大小：

 
 
 
 
    
  
  
  
  
  1. type StringHeader struct { 
    2. 
  
  
  
  
  2.  Data uintptr 
    3. 
  
  
  
  
  3.  Len  int 
    4. 
  
  
  
  
  4. } 
    5.

由于 StringHeader中包含指针，所以每次 GC 的时候都会扫描每个指针，那么在这个巨大的 map中是包含了非常多的指针的，所以造成了巨大的资源消耗。

在上面的例子 map a 中数据大概是这样存储：

一个 map 中里面有多个 bucket ，bucket 里面有一个 bmap 数组用来存放数据，但是由于 key 和 value 都是 string 类型的，所以在 GC 的时候还需要根据 StringHeader中的 Data指针扫描 string 数据。

对于这种情况，如果所有的 string 字节都在一个单一内存片段中，我们就可以通过偏移来追踪某个字符串在这段内存中的开始和结束位置。通过追踪偏移，我们不在需要在我们大数组中存储指针，GC 也不在会被困扰。如下：

如同上面所示，如果我们将字符串中的字节数据拷贝到一个连续的字节数组 chunks 中，并为这个字节数组提前分配好内存，并且仅存储字符串在数组中的偏移而不是指针。

除了上面所说的优化内容以外，还有其他的方法吗?

其实我们还可以直接从系统 OS 中调用 mmap syscall 进行内存分配，这样 GC 就永远不会对这块内存进行内存管理，因此也就不会扫描到它。如下：

 
 
 
 
    
  
  
  
  
  1. func main() { 
    2. 
  
  
  
  
  2.     test := "hello syscall" 
    3. 
  
  
  
  
  3.  data, _ := syscall.Mmap(-1, 0, 13, syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_ANON|syscall.MAP_PRIVATE) 
    4. 
  
  
  
  
  4.  p := (*[13]byte)(unsafe.Pointer(&data[0])) 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.  for i := 0; i < 13; i++ { 
    7. 
  
  
  
  
  7.   p[i] = test[i] 
    8. 
  
  
  
  
  8.  } 
    9. 
  
  
  
  
  9.  fmt.Println(string(p[:])) 
    10. 
  
  
  
  
  10. } 
    11.

通过系统调用直接向 OS 申请了 13bytes 的内存，然后将一个字符串写入到申请的内存数组中。

所以我们也可以通过提前向 OS 申请一块内存，而不是用的时候才申请内存，减少频繁的内存分配从而达到提高性能的目的。

源码实战

API

我们在开发前先把这个库的 API 定义一下：

func New

 
 
 
 
    
  
  
  
  
  1. func New(maxBytes int) *Cache 
    2.

创建一个 Cache 结构体，传入预设的缓存大小，单位是字节。

func (*Cache) Get

 
 
 
 
    
  
  
  
  
  1. func (c *Cache) Get(k []byte) []byte 
    2.

获取 Cache 中的值，传入的参数是 byte 数组。

func (*Cache) Set

 
 
 
 
    
  
  
  
  
  1. func (c *Cache) Set(k, v []byte) 
    2.

设置键值对到缓存中，k 是键，v 是值，参数都是 byte 数组。

结构体

 

 
 
 
 
    
  
  
  
  
  1. const bucketsCount = 512 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. type Cache struct { 
    4. 
  
  
  
  
  4.  buckets [bucketsCount]bucket 
    5. 
  
  
  
  
  5. } 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. type bucket struct { 
    8. 
  
  
  
  
  8.  // 读写锁 
    9. 
  
  
  
  
  9.  mu sync.RWMutex 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.  // 二维数组，存放数据的地方，是一个环形链表 
    12. 
  
  
  
  
  12.  chunks [][]byte 
    13. 
  
  
  
  
  13.  
    14. 
  
  
  
  
  14.  // 索引字典 
    15. 
  
  
  
  
  15.  m map[uint64]uint64 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17.  // 索引值 
    18. 
  
  
  
  
  18.  idx uint64 
    19. 
  
  
  
  
  19.  
    20. 
  
  
  
  
  20.  // chunks 被重写的次数，用来校验环形链表中数据有效性 
    21. 
  
  
  
  
  21.  gen uint64 
    22. 
  
  
  
  
  22. } 
    23.

通过我们上面的分析，可以看到，实际上真正存放数据的地方是 chunks 二维数组，在实现上是通过 m 字段来映射索引路径，根据 chunks 和 gen 两个字段来构建一个环形链表，环形链表每转一圈 gen 就会加一。

初始化

 

 
 
 
 
    
  
  
  
  
  1. func New(maxBytes int) *Cache { 
    2. 
  
  
  
  
  2.  if maxBytes <= 0 { 
    3. 
  
  
  
  
  3.   panic(fmt.Errorf("maxBytes must be greater than 0; got %d", maxBytes)) 
    4. 
  
  
  
  
  4.  } 
    5. 
  
  
  
  
  5.  var c Cache 
    6. 
  
  
  
  
  6.  // 算出每个桶的大小 
    7. 
  
  
  
  
  7.  maxBucketBytes := uint64((maxBytes + bucketsCount - 1) / bucketsCount) 
    8. 
  
  
  
  
  8.  for i := range c.buckets[:] { 
    9. 
  
  
  
  
  9.     // 对桶进行初始化 
    10. 
  
  
  
  
  10.   c.buckets[i].Init(maxBucketBytes) 
    11. 
  
  
  
  
  11.  } 
    12. 
  
  
  
  
  12.  return &c 
    13. 
  
  
  
  
  13. } 
    14.

我们会设置一个 New 函数来初始化我们 Cache 结构体，在 Cache 结构体中会将缓存的数据大小平均分配到每个桶中，然后对每个桶进行初始化。

 
 
 
 
    
  
  
  
  
  1. const bucketSizeBits = 40 
    2. 
  
  
  
  
  2. const maxBucketSize uint64 = 1 << bucketSizeBits 
    3. 
  
  
  
  
  3. const chunkSize = 64 * 1024 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. func (b *bucket) Init(maxBytes uint64) { 
    6. 
  
  
  
  
  6.  if maxBytes == 0 { 
    7. 
  
  
  
  
  7.   panic(fmt.Errorf("maxBytes cannot be zero")) 
    8. 
  
  
  
  
  8.  } 
    9. 
  
  
  
  
  9.   // 我们这里限制每个桶最大的大小是 1024 GB 
    10. 
  
  
  
  
  10.  if maxBytes >= maxBucketSize { 
    11. 
  
  
  
  
  11.   panic(fmt.Errorf("too big maxBytes=%d; should be smaller than %d", maxBytes, maxBucketSize)) 
    12. 
  
  
  
  
  12.  } 
    13. 
  
  
  
  
  13.  // 初始化 Chunks 中每个 Chunk 大小为 64 KB，计算 chunk 数量 
    14. 
  
  
  
  
  14.  maxChunks := (maxBytes + chunkSize - 1) / chunkSize 
    15. 
  
  
  
  
  15.  b.chunks = make([][]byte, maxChunks) 
    16. 
  
  
  
  
  16.  b.m = make(map[uint64]uint64) 
    17. 
  
  
  
  
  17.     // 初始化 bucket 结构体 
    18. 
  
  
  
  
  18.  b.Reset() 
    19. 
  
  
  
  
  19. } 
    20.

在这里会将桶里面的内存按 chunk 进行分配，每个 chunk 占用内存约为 64 KB。在最后会调用 bucket 的 Reset 方法对 bucket 结构体进行初始化。

 
 
 
 
    
  
  
  
  
  1. func (b *bucket) Reset() { 
    2. 
  
  
  
  
  2.  b.mu.Lock() 
    3. 
  
  
  
  
  3.  chunks := b.chunks 
    4. 
  
  
  
  
  4.  // 遍历 chunks 
    5. 
  
  
  
  
  5.  for i := range chunks { 
    6. 
  
  
  
  
  6.   // 将 chunk 中的内存归还到缓存中 
    7. 
  
  
  
  
  7.   putChunk(chunks[i]) 
    8. 
  
  
  
  
  8.   chunks[i] = nil 
    9. 
  
  
  
  
  9.  } 
    10. 
  
  
  
  
  10.  // 删除索引字典中所有的数据 
    11. 
  
  
  
  
  11.  bm := b.m 
    12. 
  
  
  
  
  12.  for k := range bm { 
    13. 
  
  
  
  
  13.   delete(bm, k) 
    14. 
  
  
  
  
  14.  } 
    15. 
  
  
  
  
  15.  b.idx = 0 
    16. 
  
  
  
  
  16.  b.gen = 1 
    17. 
  
  
  
  
  17.  b.mu.Unlock() 
    18. 
  
  
  
  
  18. } 
    19.

Reset 方法十分简单，主要就是清空 chunks 数组、删除索引字典中所有的数据以及重置索引 idx 和 gen 的值。

在上面这个方法中有一个 putChunk ，其实这个就是直接操作我们提前向 OS 申请好的内存，相应的还有一个 getChunk 方法。下面我们具体看看 Chunk 的操作。

Chunk 操作

getChunk

 

 
 
 
 
    
  
  
  
  
  1. const chunksPerAlloc = 1024 
    2. 
  
  
  
  
  2. const chunkSize = 64 * 1024 
    3. 
  
  
  
  
  3.  
    4. 
  
  
  
  
  4. var ( 
    5. 
  
  
  
  
  5.  freeChunks     []*[chunkSize]byte 
    6. 
  
  
  
  
  6.  freeChunksLock sync.Mutex 
    7. 
  
  
  
  
  7. ) 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. func getChunk() []byte { 
    10. 
  
  
  
  
  10.  freeChunksLock.Lock() 
    11. 
  
  
  
  
  11.  if len(freeChunks) == 0 { 
    12. 
  
  
  
  
  12.   // 分配  64 * 1024 * 1024 = 64 MB 内存 
    13. 
  
  
  
  
  13.   data, err := syscall.Mmap(-1, 0, chunkSize*chunksPerAlloc, syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_ANON|syscall.MAP_PRIVATE) 
    14. 
  
  
  
  
  14.   if err != nil { 
    15. 
  
  
  
  
  15.    panic(fmt.Errorf("cannot allocate %d bytes via mmap: %s", chunkSize*chunksPerAlloc, err)) 
    16. 
  
  
  
  
  16.   } 
    17. 
  
  
  
  
  17.         // 循环遍历 data 数据 
    18. 
  
  
  
  
  18.   for len(data) > 0 { 
    19. 
  
  
  
  
  19.    //将从系统分配的内存分为 64 * 1024 = 64 KB 大小，存放到 freeChunks中 
    20. 
  
  
  
  
  20.    p := (*[chunkSize]byte)(unsafe.Pointer(&data[0])) 
    21. 
  
  
  
  
  21.    freeChunks = append(freeChunks, p) 
    22. 
  
  
  
  
  22.    data = data[chunkSize:] 
    23. 
  
  
  
  
  23.   } 
    24. 
  
  
  
  
  24.  } 
    25. 
  
  
  
  
  25.  //从 freeChunks 获取最后一个元素 
    26. 
  
  
  
  
  26.  n := len(freeChunks) - 1 
    27. 
  
  
  
  
  27.  p := freeChunks[n] 
    28. 
  
  
  
  
  28.  freeChunks[n] = nil 
    29. 
  
  
  
  
  29.  freeChunks = freeChunks[:n] 
    30. 
  
  
  
  
  30.  freeChunksLock.Unlock() 
    31. 
  
  
  
  
  31.  return p[:] 
    32. 
  
  
  
  
  32. } 
    33.

初次调用 getChunk 函数时会使用系统调用分配 64MB 的内存，然后循环将内存切成 1024 份，每份 64KB 放入到 freeChunks 空闲列表中。然后获取每次都获取 freeChunks 空闲列表最后一个元素 64KB 内存返回。需要注意的是 getChunk 会下下面将要介绍到的 Cache 的 set 方法中使用到，所以需要考虑到并发问题，所以在这里加了锁。

putChunk

 

 
 
 
 
    
  
  
  
  
  1. func putChunk(chunk []byte) { 
    2. 
  
  
  
  
  2.  if chunk == nil { 
    3. 
  
  
  
  
  3.   return 
    4. 
  
  
  
  
  4.  } 
    5. 
  
  
  
  
  5.  chunk = chunk[:chunkSize] 
    6. 
  
  
  
  
  6.  p := (*[chunkSize]byte)(unsafe.Pointer(&chunk[0])) 
    7. 
  
  
  
  
  7.  
    8. 
  
  
  
  
  8.  freeChunksLock.Lock() 
    9. 
  
  
  
  
  9.  freeChunks = append(freeChunks, p) 
    10. 
  
  
  
  
  10.  freeChunksLock.Unlock() 
    11. 
  
  
  
  
  11. } 
    12.

putChunk 函数就是将内存数据还回到 freeChunks 空闲列表中，会在 bucket 的 Reset 方法中被调用。

Set

 

 
 
 
 
    
  
  
  
  
  1. const bucketsCount = 512 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. func (c *Cache) Set(k, v []byte) { 
    4. 
  
  
  
  
  4.  h := xxhash.Sum64(k) 
    5. 
  
  
  
  
  5.  idx := h % bucketsCount 
    6. 
  
  
  
  
  6.  c.buckets[idx].Set(k, v, h) 
    7. 
  
  
  
  
  7. } 
    8.

Set 方法里面会根据 k 的值做一个 hash，然后取模映射到 buckets 桶中，这里用的 hash 库是 cespare/xxhash。

最主要的还是 buckets 里面的 Set 方法：

 
 
 
 
    
  
  
  
  
  1. func (b *bucket) Set(k, v []byte, h uint64) { 
    2. 
  
  
  
  
  2.  // 限定 k v 大小不能超过 2bytes 
    3. 
  
  
  
  
  3.  if len(k) >= (1<<16) || len(v) >= (1<<16) { 
    4. 
  
  
  
  
  4.   return 
    5. 
  
  
  
  
  5.  } 
    6. 
  
  
  
  
  6.  // 4个byte 设置每条数据的数据头 
    7. 
  
  
  
  
  7.  var kvLenBuf [4]byte 
    8. 
  
  
  
  
  8.   kvLenBuf[0] = byte(uint16(len(k)) >> 8) 
    9. 
  
  
  
  
  9.  kvLenBuf[1] = byte(len(k)) 
    10. 
  
  
  
  
  10.  kvLenBuf[2] = byte(uint16(len(v)) >> 8) 
    11. 
  
  
  
  
  11.  kvLenBuf[3] = byte(len(v)) 
    12. 
  
  
  
  
  12.  kvLen := uint64(len(kvLenBuf) + len(k) + len(v)) 
    13. 
  
  
  
  
  13.  // 校验一下大小 
    14. 
  
  
  
  
  14.  if kvLen >= chunkSize { 
    15. 
  
  
  
  
  15.   return 
    16. 
  
  
  
  
  16.  } 
    17. 
  
  
  
  
  17.  
    18. 
  
  
  
  
  18.  b.mu.Lock() 
    19. 
  
  
  
  
  19.  // 当前索引位置 
    20. 
  
  
  
  
  20.  idx := b.idx 
    21. 
  
  
  
  
  21.  // 存放完数据后索引的位置 
    22. 
  
  
  
  
  22.  idxNew := idx + kvLen 
    23. 
  
  
  
  
  23.  // 根据索引找到在 chunks 的位置 
    24. 
  
  
  
  
  24.  chunkIdx := idx / chunkSize 
    25. 
  
  
  
  
  25.  chunkIdxNew := idxNew / chunkSize 
    26. 
  
  
  
  
  26.  // 新的索引是否超过当前索引 
    27. 
  
  
  
  
  27.  // 因为还有chunkIdx等于chunkIdxNew情况，所以需要先判断一下 
    28. 
  
  
  
  
  28.  if chunkIdxNew > chunkIdx { 
    29. 
  
  
  
  
  29.   // 校验是否新索引已到chunks数组的边界 
    30. 
  
  
  
  
  30.   // 已到边界，那么循环链表从头开始 
    31. 
  
  
  
  
  31.   if chunkIdxNew >= uint64(len(b.chunks)) { 
    32. 
  
  
  
  
  32.    idx = 0 
    33. 
  
  
  
  
  33.    idxNew = kvLen 
    34. 
  
  
  
  
  34.    chunkIdx = 0 
    35. 
  
  
  
  
  35.    b.gen++ 
    36. 
  
  
  
  
  36.    // 当 gen 等于 1<
  
  
  
  
  37.    // 也就是用来限定 gen 的边界为1<
  
  
  
  
  38.    if b.gen&((1<
  
  
  
  
  39.     b.gen++ 
    40. 
  
  
  
  
  40.    } 
    41. 
  
  
  
  
  41.   } else { 
    42. 
  
  
  
  
  42.    // 未到 chunks数组的边界,从下一个chunk开始 
    43. 
  
  
  
  
  43.    idx = chunkIdxNew * chunkSize 
    44. 
  
  
  
  
  44.    idxNew = idx + kvLen 
    45. 
  
  
  
  
  45.    chunkIdx = chunkIdxNew 
    46. 
  
  
  
  
  46.   } 
    47. 
  
  
  
  
  47.   // 重置 chunks[chunkIdx] 
    48. 
  
  
  
  
  48.   b.chunks[chunkIdx] = b.chunks[chunkIdx][:0] 
    49. 
  
  
  
  
  49.  } 
    50. 
  
  
  
  
  50.  chunk := b.chunks[chunkIdx] 
    51. 
  
  
  
  
  51.  if chunk == nil { 
    52. 
  
  
  
  
  52.   chunk = getChunk() 
    53. 
  
  
  
  
  53.   // 清空切片 
    54. 
  
  
  
  
  54.   chunk = chunk[:0] 
    55. 
  
  
  
  
  55.  } 
    56. 
  
  
  
  
  56.  // 将数据 append 到 chunk 中 
    57. 
  
  
  
  
  57.  chunk = append(chunk, kvLenBuf[:]...) 
    58. 
  
  
  
  
  58.  chunk = append(chunk, k...) 
    59. 
  
  
  
  
  59.  chunk = append(chunk, v...) 
    60. 
  
  
  
  
  60.  b.chunks[chunkIdx] = chunk 
    61. 
  
  
  
  
  61.  // 因为 idx 不能超过bucketSizeBits，所以用一个 uint64 同时表示gen和idx 
    62. 
  
  
  
  
  62.  // 所以高于bucketSizeBits位置表示gen 
    63. 
  
  
  
  
  63.  // 低于bucketSizeBits位置表示idx 
    64. 
  
  
  
  
  64.  b.m[h] = idx | (b.gen << bucketSizeBits) 
    65. 
  
  
  
  
  65.  b.idx = idxNew 
    66. 
  
  
  
  
  66.  b.mu.Unlock() 
    67. 
  
  
  
  
  67. } 
    68.
  1. 在这段代码开头实际上我会限制键值的大小不能超过 2bytes;
  2. 然后将 2bytes 大小长度的键值封装到 4bytes 的 kvLenBuf 作为数据头，数据头和键值的总长度是不能超过一个 chunk 长度，也就是 64 * 1024;
  3. 然后计算出原索引 chunkIdx 和新索引 chunkIdxNew，用来判断这次添加的数据加上原来的数据有没有超过一个 chunk 长度;
  4. 根据新的索引找到对应的 chunks 中的位置，然后将键值以及 kvLenBuf 追加到 chunk 后面;
  5. 设置新的 idx 以及 m 字典对应的值，m 字典中存放的是 gen 和 idx 通过取与的放置存放。

在 Set 一个键值对会有 4bytes 的 kvLenBuf 作为数据头，后面的数据会接着 key 和 value ，在 kvLenBuf 中，前两个 byte 分别代表了 key 长度的低位和高位;后两个 byte 分别代表了 value 长度的低位和高位，数据图大致如下：

下面举个例子来看看是是如何利用 chunks 这个二维数组来实现环形链表的。

我们在 bucket 的 Init 方法中会根据传入 maxBytes 桶字节数来设置 chunks 的长度大小，由于每个 chunk 大小都是 64 * 1024bytes，那么我们设置 3 * 64 * 1024bytes 大小的桶，那么 chunks 数组长度就为 3。

如果当前算出 chunkIdx 在 chunks 数组为 1 的位置，并且在 chunks[1] 的位置中，还剩下 6bytes 未被使用，那么有如下几种情况：

现在假设放入的键值长度都是 1byte，那么在 chunks[1] 的位置中剩下的 6bytes 刚好可以放下;

现在假设放入的键值长度超过了 1byte，那么在 chunks[1] 的位置中剩下的位置就放不下，只能放入到 chunks[2] 的位置中。

如果当前算出 chunkIdx 在 chunks 数组为 2 的位置，并且现在 Set 一个键值，经过计算 chunkIdxNew 为 3，已经超过了 chunks 数组长度，那么会将索引重置，重新将数据从 chunks[0] 开始放置，并将 gen 加一，表示已经跑完一圈了。

Get

 

 
 
 
 
    
  
  
  
  
  1. func (c *Cache) Get(dst, k []byte) []byte { 
    2. 
  
  
  
  
  2.    h := xxhash.Sum64(k) 
    3. 
  
  
  
  
  3.    idx := h % bucketsCount 
    4. 
  
  
  
  
  4.    dst, _ = c.buckets[idx].Get(dst, k, h, true) 
    5. 
  
  
  
  
  5.    return dst 
    6. 
  
  
  
  
  6. } 
    7.

这里和 Set 方法是一样的，首先是要找到对应的桶的位置，然后才去桶里面拿数据。需要注意的是，这里的 dst 可以从外部传入一个切片，以达到减少重复分配返回值。

 
 
 
 
    
  
  
  
  
  1. func (b *bucket) Get(dst, k []byte, h uint64,returnDst bool) ([]byte, bool) { 
    2. 
  
  
  
  
  2.  found := false 
    3. 
  
  
  
  
  3.  b.mu.RLock() 
    4. 
  
  
  
  
  4.  v := b.m[h] 
    5. 
  
  
  
  
  5.  bGen := b.gen & ((1 << genSizeBits) - 1) 
    6. 
  
  
  
  
  6.  if v > 0 { 
    7. 
  
  
  
  
  7.   // 高于bucketSizeBits位置表示gen 
    8. 
  
  
  
  
  8.   gen := v >> bucketSizeBits 
    9. 
  
  
  
  
  9.   // 低于bucketSizeBits位置表示idx 
    10. 
  
  
  
  
  10.   idx := v & ((1 << bucketSizeBits) - 1) 
    11. 
  
  
  
  
  11.   // 这里说明chunks还没被写满 
    12. 
  
  
  
  
  12.   if gen == bGen && idx < b.idx || 
    13. 
  
  
  
  
  13.    // 这里说明chunks已被写满，并且当前数据没有被覆盖 
    14. 
  
  
  
  
  14.    gen+1 == bGen && idx >= b.idx || 
    15. 
  
  
  
  
  15.    // 这里是边界条件gen已是最大，并且chunks已被写满bGen从1开始，，并且当前数据没有被覆盖 
    16. 
  
  
  
  
  16.    gen == maxGen && bGen == 1 && idx >= b.idx { 
    17. 
  
  
  
  
  17.    chunkIdx := idx / chunkSize 
    18. 
  
  
  
  
  18.    // chunk 索引位置不能超过 chunks 数组长度 
    19. 
  
  
  
  
  19.    if chunkIdx >= uint64(len(b.chunks)) { 
    20. 
  
  
  
  
  20.     goto end 
    21. 
  
  
  
  
  21.    } 
    22. 
  
  
  
  
  22.    // 找到数据所在的 chunk 
    23. 
  
  
  
  
  23.    chunk := b.chunks[chunkIdx] 
    24. 
  
  
  
  
  24.    // 通过取模找到该key 对应的数据在 chunk 中的位置 
    25. 
  
  
  
  
  25.    idx %= chunkSize 
    26. 
  
  
  
  
  26.    if idx+4 >= chunkSize { 
    27. 
  
  
  
  
  27.     goto end 
    28. 
  
  
  
  
  28.    } 
    29. 
  
  
  
  
  29.    // 前 4bytes 是数据头 
    30. 
  
  
  
  
  30.    kvLenBuf := chunk[idx : idx+4] 
    31. 
  
  
  
  
  31.    // 通过数据头算出键值的长度 
    32. 
  
  
  
  
  32.    keyLen := (uint64(kvLenBuf[0]) << 8) | uint64(kvLenBuf[1]) 
    33. 
  
  
  
  
  33.    valLen := (uint64(kvLenBuf[2]) << 8) | uint64(kvLenBuf[3]) 
    34. 
  
  
  
  
  34.    idx += 4 
    35. 
  
  
  
  
  35.    if idx+keyLen+valLen >= chunkSize { 
    36. 
  
  
  
  
  36.     goto end 
    37. 
  
  
  
  
  37.    } 
    38. 
  
  
  
  
  38.    // 如果键值是一致的，表示找到该数据 
    39. 
  
  
  
  
  39.    if string(k) == string(chunk[idx:idx+keyLen]) { 
    40. 
  
  
  
  
  40.     idx += keyLen 
    41. 
  
  
  
  
  41.     // 返回该键对应的值 
    42. 
  
  
  
  
  42.     if returnDst { 
    43. 
  
  
  
  
  43.      dst = append(dst, chunk[idx:idx+valLen]...) 
    44. 
  
  
  
  
  44.     } 
    45. 
  
  
  
  
  45.     found = true 
    46. 
  
  
  
  
  46.    } 
    47. 
  
  
  
  
  47.   } 
    48. 
  
  
  
  
  48.  } 
    49. 
  
  
  
  
  49. end: 
    50. 
  
  
  
  
  50.  b.mu.RUnlock() 
    51. 
  
  
  
  
  51.  return dst, found 
    52. 
  
  
  
  
  52. } 
    53.

Get 方法主要是考虑环形链表的边界问题。我们在 Set 方法中会将每一个 key 对应的 gen 和 idx 索引存放到 m 字典中，所以我们通过 hash 获取 m 字典的值之后通过位运算就可以获取到 gen 和 idx 索引。

找到 gen 和 idx 索引之后就是边界条件的判断了，用一个 if 条件来进行判断：

 
 
 
 
    
  
  
  
  
  1. gen == bGen && idx < b.idx 
    2.

这里是判断如果是在环形链表的同一次循环中，那么 key 对应的索引应该小于当前桶的索引;

 
 
 
 
    
  
  
  
  
  1. gen+1 == bGen && idx >= b.idx 
    2.

这里表示当前桶已经进入到下一个循环中，所以需要判断 key 对应的索引是不是大于当前索引，以表示当前 key 对应的值没有被覆盖;

 
 
 
 
    
  
  
  
  
  1. gen == maxGen && bGen == 1 && idx >= b.idx 
    2.

因为 gen 和 idx 索引要塞到 uint64 类型的字段中，所以留给 gen 的最大值只有 maxGen = 1<< 24 -1，超过了 maxGen 会让 gen 从 1 开始。所以这里如果 key 对应 gen 等于 maxGen ，那么当前的 bGen 应该等于 1，并且 key 对应的索引还应该大于当前 idx，这样才这个键值对才不会被覆盖。

判断完边界条件之后就会找到对应的 chunk ，然后取模后找到数据位置，通过偏移量找到并取出值。

Benchmark

下面我上一下过后的 Benchmark：

代码位置： https://github.com/devYun/mycache/blob/main/cache_timing_test.go

 
 
 
 
    
  
  
  
  
  1. GOMAXPROCS=4 go test -bench='Set|Get' -benchtime=10s 
    2. 
  
  
  
  
  2. goos: linux 
    3. 
  
  
  
  
  3. goarch: amd64 
    4. 
  
  
  
  
  4. pkg: gotest 
    5. 
  
  
  
  
  5. // GoCache 
    6. 
  
  
  
  
  6. BenchmarkGoCacheSet-4                836          14595822 ns/op           4.49 MB/s     2167340 B/op    65576 allocs/op 
    7. 
  
  
  
  
  7. BenchmarkGoCacheGet-4               3093           3619730 ns/op          18.11 MB/s        5194 B/op       23 allocs/op 
    8. 
  
  
  
  
  8. BenchmarkGoCacheSetGet-4             236          54379268 ns/op           2.41 MB/s     2345868 B/op    65679 allocs/op 
    9. 
  
  
  
  
  9. // BigCache 
    10. 
  
  
  
  
  10. BenchmarkBigCacheSet-4              1393          12763995 ns/op           5.13 MB/s     6691115 B/op        8 allocs/op 
    11. 
  
  
  
  
  11. BenchmarkBigCacheGet-4              2526           4342561 ns/op          15.09 MB/s      650870 B/op   131074 allocs/op 
    12. 
  
  
  
  
  12. BenchmarkBigCacheSetGet-4           1063          11180201 ns/op          11.72 MB/s     4778699 B/op   131081 allocs/op 
    13. 
  
  
  
  
  13. // standard map 
    14. 
  
  
  
  
  14. BenchmarkStdMapSet-4                1484           7299296 ns/op           8.98 MB/s      270603 B/op    65537 allocs/op 
    15. 
  
  
  
  
  15. BenchmarkStdMapGet-4                4278           2480523 ns/op          26.42 MB/s        2998 B/op       15 allocs/op 
    16. 
  
  
  
  
  16. BenchmarkStdMapSetGet-4              343          39367319 ns/op           3.33 MB/s      298764 B/op    65543 allocs/op 
    17. 
  
  
  
  
  17. // sync.map 
    18. 
  
  
  
  
  18. BenchmarkSyncMapSet-4                756          15951363 ns/op           4.11 MB/s     3420214 B/op   262320 allocs/op 
    19. 
  
  
  
  
  19. BenchmarkSyncMapGet-4              11826           1010283 ns/op          64.87 MB/s        1075 B/op       33 allocs/op 
    20. 
  
  
  
  
  20. BenchmarkSyncMapSetGet-4            1910           5507036 ns/op          23.80 MB/s     3412764 B/op   262213 allocs/op 
    21. 
  
  
  
  
  21. PASS 
    22. 
  
  
  
  
  22. ok      gotest  215.182s 
    23.

上面的测试是 GoCache、BigCache、Map、sync.Map 的情况。下面是本篇文章中所开发的缓存库的测试：

 
 
 
 
    
  
  
  
  
  1. // myCachce 
    2. 
  
  
  
  
  2. BenchmarkCacheSet-4                 4371           2723208 ns/op          24.07 MB/s        1306 B/op        2 allocs/op 
    3. 
  
  
  
  
  3. BenchmarkCacheGet-4                 6003           1884611 ns/op          34.77 MB/s         951 B/op        1 allocs/op 
    4. 
  
  
  
  
  4. BenchmarkCacheSetGet-4              2044           6611759 ns/op          19.82 MB/s        2797 B/op        5 allocs/op 
    5.

可以看到内存分配是几乎就不存在，操作速度在上面的库中也是佼佼者的存在。

总结

在本文中根据其他缓存库，并分析了如果用 Map 作为缓存所存在的问题，然后引出存在这个问题的原因，并提出解决方案;在我们的缓存库中，第一是通过使用索引加内存块的方式来存放缓存数据，再来是通过 OS 系统调用来进行内存分配让我们的缓存数据块脱离了 GC 的控制，从而做到降低 GC 频率提高并发的目的。

其实不只是缓存库，在我们的项目中当遇到需要使用大量的带指针的数据结构并需要长时间保持引用的时候，也是需要注意这样做可能会引发 GC 问题，从而给系统带来隐患。

文章题目：教你打造高性能的Go缓存库
标题路径：http://www.gawzjz.com/qtweb/news39/172289.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站导航知识

分类信息网

移动手机网站制作　　 　品牌网站建设公司　　 　成都微信公众号开发　　 　成都app制作　　 　娃娃鱼鱼苗　　 　雅安服务器托管　　 　成都网站建设　　 　重庆网站制作　　 　四川电信高防服务器托管　　 　app开发　　 　成都外贸网站建设　　 　手机网站建设　　 　成都网站设计　　 　微信开发　　 　服务器租用　　 　成都定制高级网站建设　　 　led无边发光字　　 　响应式网站建设方案　　 　小程序开发　　 　高端定制网站设计