日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
教你打造高性能的Go緩存庫(kù)

我在看一些優(yōu)秀的開(kāi)源庫(kù)的時(shí)候看到一個(gè)有意思的緩存庫(kù) fastcache，在它的介紹主要有以下幾點(diǎn)特點(diǎn)：

創(chuàng)新互聯(lián)主要從事成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)高縣,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18982081108

  • 讀寫數(shù)據(jù)要快，即使在并發(fā)下;
  • 即使在數(shù) GB 的緩存中，也要保持很好的性能，以及盡可能減少 GC 次數(shù);
  • 設(shè)計(jì)盡可能簡(jiǎn)單;

本文會(huì)通過(guò)模仿它寫一個(gè)簡(jiǎn)單的緩存庫(kù)，從而研究其內(nèi)核是如何實(shí)現(xiàn)這樣的目標(biāo)的。希望各位能有所收獲。

設(shè)計(jì)思想

在項(xiàng)目中，我們經(jīng)常會(huì)用到 Go 緩存庫(kù)比如說(shuō) patrickmn/go-cache庫(kù)。但很多緩存庫(kù)其實(shí)都是用一個(gè)簡(jiǎn)單的 Map 來(lái)存放數(shù)據(jù)，這些庫(kù)在使用的時(shí)候，當(dāng)并發(fā)低，數(shù)據(jù)量少的時(shí)候是沒(méi)有問(wèn)題的，但是在數(shù)據(jù)量比較大并發(fā)比較高的時(shí)候會(huì)延長(zhǎng) GC 時(shí)間，增加內(nèi)存分配次數(shù)。

比如，我們使用一個(gè)簡(jiǎn)單的例子：

 
 
 
 
    
  
  
  
  
  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.

在這個(gè)例子中，預(yù)分配了大小是10億(1e9) 的 map，然后我們通過(guò) gctrace 輸出一下 GC 情況：

做實(shí)驗(yàn)的環(huán)境是 Linux，機(jī)器配置是 16C 8G ，想要更深入理解 GC，可以看這篇：《 Go 語(yǔ)言 GC 實(shí)現(xiàn)原理及源碼分析 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 ：程序啟動(dòng)以來(lái)第10次GC  
    5. 
  
  
  
  
  5. @20.963s：距離程序啟動(dòng)到現(xiàn)在的時(shí)間  
    6. 
  
  
  
  
  6. 19%：當(dāng)目前為止，GC 的標(biāo)記工作所用的CPU時(shí)間占總CPU的百分比 
    7.

垃圾回收的時(shí)間

 
 
 
 
    
  
  
  
  
  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 ：程序啟動(dòng)以來(lái)第10次GC 
    6. 
  
  
  
  
  6. @20.963s：距離程序啟動(dòng)到現(xiàn)在的時(shí)間 
    7. 
  
  
  
  
  7. 19%：當(dāng)目前為止，GC 的標(biāo)記工作所用的CPU時(shí)間占總CPU的百分比 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. 垃圾回收的時(shí)間 
    10. 
  
  
  
  
  10. 0.011 ms：標(biāo)記開(kāi)始 STW 時(shí)間 
    11. 
  
  
  
  
  11. 1844 ms：并發(fā)標(biāo)記時(shí)間 
    12. 
  
  
  
  
  12. 0.004 ms：標(biāo)記終止 STW 時(shí)間 
    13. 
  
  
  
  
  13.  
    14. 
  
  
  
  
  14. 垃圾回收占用cpu時(shí)間 
    15. 
  
  
  
  
  15. 0.18 ms：標(biāo)記開(kāi)始 STW 時(shí)間 
    16. 
  
  
  
  
  16. 0 ms：mutator assists占用的時(shí)間 
    17. 
  
  
  
  
  17. 7373 ms：標(biāo)記線程占用的時(shí)間 
    18. 
  
  
  
  
  18. 22057 ms：idle mark workers占用的時(shí)間 
    19. 
  
  
  
  
  19. 0.076 ms：標(biāo)記終止 STW 時(shí)間 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. 內(nèi)存 
    22. 
  
  
  
  
  22. 73984 MB：標(biāo)記開(kāi)始前堆占用大小 
    23. 
  
  
  
  
  23. 73984 MB：標(biāo)記結(jié)束后堆占用大小 
    24. 
  
  
  
  
  24. 73984 MB：標(biāo)記完成后存活堆的大小 
    25. 
  
  
  
  
  25. 147968 MB goal：標(biāo)記完成后正在使用的堆內(nèi)存的目標(biāo)大小 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. 16 P：使用了多少處理器 
    28.

可以從上面的輸出看到每次 GC 處理的時(shí)間非常的長(zhǎng)，占用的 CPU 資源也非常多。那么造成這樣的原因是什么呢?

string 實(shí)際上底層數(shù)據(jù)結(jié)構(gòu)是由兩部分組成，其中包含指向字節(jié)數(shù)組的指針和數(shù)組的大?。?/p>

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

由于 StringHeader中包含指針，所以每次 GC 的時(shí)候都會(huì)掃描每個(gè)指針，那么在這個(gè)巨大的 map中是包含了非常多的指針的，所以造成了巨大的資源消耗。

在上面的例子 map a 中數(shù)據(jù)大概是這樣存儲(chǔ)：

一個(gè) map 中里面有多個(gè) bucket ，bucket 里面有一個(gè) bmap 數(shù)組用來(lái)存放數(shù)據(jù)，但是由于 key 和 value 都是 string 類型的，所以在 GC 的時(shí)候還需要根據(jù) StringHeader中的 Data指針掃描 string 數(shù)據(jù)。

對(duì)于這種情況，如果所有的 string 字節(jié)都在一個(gè)單一內(nèi)存片段中，我們就可以通過(guò)偏移來(lái)追蹤某個(gè)字符串在這段內(nèi)存中的開(kāi)始和結(jié)束位置。通過(guò)追蹤偏移，我們不在需要在我們大數(shù)組中存儲(chǔ)指針，GC 也不在會(huì)被困擾。如下：

如同上面所示，如果我們將字符串中的字節(jié)數(shù)據(jù)拷貝到一個(gè)連續(xù)的字節(jié)數(shù)組 chunks 中，并為這個(gè)字節(jié)數(shù)組提前分配好內(nèi)存，并且僅存儲(chǔ)字符串在數(shù)組中的偏移而不是指針。

除了上面所說(shuō)的優(yōu)化內(nèi)容以外，還有其他的方法嗎?

其實(shí)我們還可以直接從系統(tǒng) OS 中調(diào)用 mmap syscall 進(jìn)行內(nèi)存分配，這樣 GC 就永遠(yuǎn)不會(huì)對(duì)這塊內(nèi)存進(jìn)行內(nèi)存管理，因此也就不會(huì)掃描到它。如下：

 
 
 
 
    
  
  
  
  
  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.

通過(guò)系統(tǒng)調(diào)用直接向 OS 申請(qǐng)了 13bytes 的內(nèi)存，然后將一個(gè)字符串寫入到申請(qǐng)的內(nèi)存數(shù)組中。

所以我們也可以通過(guò)提前向 OS 申請(qǐng)一塊內(nèi)存，而不是用的時(shí)候才申請(qǐng)內(nèi)存，減少頻繁的內(nèi)存分配從而達(dá)到提高性能的目的。

源碼實(shí)戰(zhàn)

API

我們?cè)陂_(kāi)發(fā)前先把這個(gè)庫(kù)的 API 定義一下：

func New

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

創(chuàng)建一個(gè) Cache 結(jié)構(gòu)體，傳入預(yù)設(shè)的緩存大小，單位是字節(jié)。

func (*Cache) Get

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

獲取 Cache 中的值，傳入的參數(shù)是 byte 數(shù)組。

func (*Cache) Set

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

設(shè)置鍵值對(duì)到緩存中，k 是鍵，v 是值，參數(shù)都是 byte 數(shù)組。

結(jié)構(gòu)體

 

 
 
 
 
    
  
  
  
  
  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.  // 二維數(shù)組，存放數(shù)據(jù)的地方，是一個(gè)環(huán)形鏈表 
    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 被重寫的次數(shù)，用來(lái)校驗(yàn)環(huán)形鏈表中數(shù)據(jù)有效性 
    21. 
  
  
  
  
  21.  gen uint64 
    22. 
  
  
  
  
  22. } 
    23.

通過(guò)我們上面的分析，可以看到，實(shí)際上真正存放數(shù)據(jù)的地方是 chunks 二維數(shù)組，在實(shí)現(xiàn)上是通過(guò) m 字段來(lái)映射索引路徑，根據(jù) chunks 和 gen 兩個(gè)字段來(lái)構(gòu)建一個(gè)環(huán)形鏈表，環(huán)形鏈表每轉(zhuǎn)一圈 gen 就會(huì)加一。

初始化

 

 
 
 
 
    
  
  
  
  
  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.  // 算出每個(gè)桶的大小 
    7. 
  
  
  
  
  7.  maxBucketBytes := uint64((maxBytes + bucketsCount - 1) / bucketsCount) 
    8. 
  
  
  
  
  8.  for i := range c.buckets[:] { 
    9. 
  
  
  
  
  9.     // 對(duì)桶進(jìn)行初始化 
    10. 
  
  
  
  
  10.   c.buckets[i].Init(maxBucketBytes) 
    11. 
  
  
  
  
  11.  } 
    12. 
  
  
  
  
  12.  return &c 
    13. 
  
  
  
  
  13. } 
    14.

我們會(huì)設(shè)置一個(gè) New 函數(shù)來(lái)初始化我們 Cache 結(jié)構(gòu)體，在 Cache 結(jié)構(gòu)體中會(huì)將緩存的數(shù)據(jù)大小平均分配到每個(gè)桶中，然后對(duì)每個(gè)桶進(jìn)行初始化。

 
 
 
 
    
  
  
  
  
  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.   // 我們這里限制每個(gè)桶最大的大小是 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 中每個(gè) Chunk 大小為 64 KB，計(jì)算 chunk 數(shù)量 
    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 結(jié)構(gòu)體 
    18. 
  
  
  
  
  18.  b.Reset() 
    19. 
  
  
  
  
  19. } 
    20.

在這里會(huì)將桶里面的內(nèi)存按 chunk 進(jìn)行分配，每個(gè) chunk 占用內(nèi)存約為 64 KB。在最后會(huì)調(diào)用 bucket 的 Reset 方法對(duì) bucket 結(jié)構(gòu)體進(jìn)行初始化。

 
 
 
 
    
  
  
  
  
  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 中的內(nèi)存歸還到緩存中 
    7. 
  
  
  
  
  7.   putChunk(chunks[i]) 
    8. 
  
  
  
  
  8.   chunks[i] = nil 
    9. 
  
  
  
  
  9.  } 
    10. 
  
  
  
  
  10.  // 刪除索引字典中所有的數(shù)據(jù) 
    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 方法十分簡(jiǎn)單，主要就是清空 chunks 數(shù)組、刪除索引字典中所有的數(shù)據(jù)以及重置索引 idx 和 gen 的值。

在上面這個(gè)方法中有一個(gè) putChunk ，其實(shí)這個(gè)就是直接操作我們提前向 OS 申請(qǐng)好的內(nèi)存，相應(yīng)的還有一個(gè) 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 內(nèi)存 
    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.         // 循環(huán)遍歷 data 數(shù)據(jù) 
    18. 
  
  
  
  
  18.   for len(data) > 0 { 
    19. 
  
  
  
  
  19.    //將從系統(tǒng)分配的內(nèi)存分為 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 獲取最后一個(gè)元素 
    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.

初次調(diào)用 getChunk 函數(shù)時(shí)會(huì)使用系統(tǒng)調(diào)用分配 64MB 的內(nèi)存，然后循環(huán)將內(nèi)存切成 1024 份，每份 64KB 放入到 freeChunks 空閑列表中。然后獲取每次都獲取 freeChunks 空閑列表最后一個(gè)元素 64KB 內(nèi)存返回。需要注意的是 getChunk 會(huì)下下面將要介紹到的 Cache 的 set 方法中使用到，所以需要考慮到并發(fā)問(wèn)題，所以在這里加了鎖。

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 函數(shù)就是將內(nèi)存數(shù)據(jù)還回到 freeChunks 空閑列表中，會(huì)在 bucket 的 Reset 方法中被調(diào)用。

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 方法里面會(huì)根據(jù) k 的值做一個(gè) hash，然后取模映射到 buckets 桶中，這里用的 hash 庫(kù)是 cespare/xxhash。

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

 
 
 
 
    
  
  
  
  
  1. func (b *bucket) Set(k, v []byte, h uint64) { 
    2. 
  
  
  
  
  2.  // 限定 k v 大小不能超過(guò) 2bytes 
    3. 
  
  
  
  
  3.  if len(k) >= (1<<16) || len(v) >= (1<<16) { 
    4. 
  
  
  
  
  4.   return 
    5. 
  
  
  
  
  5.  } 
    6. 
  
  
  
  
  6.  // 4個(gè)byte 設(shè)置每條數(shù)據(jù)的數(shù)據(jù)頭 
    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.  // 校驗(yàn)一下大小 
    14. 
  
  
  
  
  14.  if kvLen >= chunkSize { 
    15. 
  
  
  
  
  15.   return 
    16. 
  
  
  
  
  16.  } 
    17. 
  
  
  
  
  17.  
    18. 
  
  
  
  
  18.  b.mu.Lock() 
    19. 
  
  
  
  
  19.  // 當(dāng)前索引位置 
    20. 
  
  
  
  
  20.  idx := b.idx 
    21. 
  
  
  
  
  21.  // 存放完數(shù)據(jù)后索引的位置 
    22. 
  
  
  
  
  22.  idxNew := idx + kvLen 
    23. 
  
  
  
  
  23.  // 根據(jù)索引找到在 chunks 的位置 
    24. 
  
  
  
  
  24.  chunkIdx := idx / chunkSize 
    25. 
  
  
  
  
  25.  chunkIdxNew := idxNew / chunkSize 
    26. 
  
  
  
  
  26.  // 新的索引是否超過(guò)當(dāng)前索引 
    27. 
  
  
  
  
  27.  // 因?yàn)檫€有chunkIdx等于chunkIdxNew情況，所以需要先判斷一下 
    28. 
  
  
  
  
  28.  if chunkIdxNew > chunkIdx { 
    29. 
  
  
  
  
  29.   // 校驗(yàn)是否新索引已到chunks數(shù)組的邊界 
    30. 
  
  
  
  
  30.   // 已到邊界，那么循環(huán)鏈表從頭開(kāi)始 
    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.    // 當(dāng) gen 等于 1<
  
  
  
  
  37.    // 也就是用來(lái)限定 gen 的邊界為1<
  
  
  
  
  38.    if b.gen&((1<
  
  
  
  
  39.     b.gen++ 
    40. 
  
  
  
  
  40.    } 
    41. 
  
  
  
  
  41.   } else { 
    42. 
  
  
  
  
  42.    // 未到 chunks數(shù)組的邊界,從下一個(gè)chunk開(kāi)始 
    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.  // 將數(shù)據(jù) 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.  // 因?yàn)?nbsp;idx 不能超過(guò)bucketSizeBits，所以用一個(gè) uint64 同時(shí)表示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. 在這段代碼開(kāi)頭實(shí)際上我會(huì)限制鍵值的大小不能超過(guò) 2bytes;
  2. 然后將 2bytes 大小長(zhǎng)度的鍵值封裝到 4bytes 的 kvLenBuf 作為數(shù)據(jù)頭，數(shù)據(jù)頭和鍵值的總長(zhǎng)度是不能超過(guò)一個(gè) chunk 長(zhǎng)度，也就是 64 * 1024;
  3. 然后計(jì)算出原索引 chunkIdx 和新索引 chunkIdxNew，用來(lái)判斷這次添加的數(shù)據(jù)加上原來(lái)的數(shù)據(jù)有沒(méi)有超過(guò)一個(gè) chunk 長(zhǎng)度;
  4. 根據(jù)新的索引找到對(duì)應(yīng)的 chunks 中的位置，然后將鍵值以及 kvLenBuf 追加到 chunk 后面;
  5. 設(shè)置新的 idx 以及 m 字典對(duì)應(yīng)的值，m 字典中存放的是 gen 和 idx 通過(guò)取與的放置存放。

在 Set 一個(gè)鍵值對(duì)會(huì)有 4bytes 的 kvLenBuf 作為數(shù)據(jù)頭，后面的數(shù)據(jù)會(huì)接著 key 和 value ，在 kvLenBuf 中，前兩個(gè) byte 分別代表了 key 長(zhǎng)度的低位和高位;后兩個(gè) byte 分別代表了 value 長(zhǎng)度的低位和高位，數(shù)據(jù)圖大致如下：

下面舉個(gè)例子來(lái)看看是是如何利用 chunks 這個(gè)二維數(shù)組來(lái)實(shí)現(xiàn)環(huán)形鏈表的。

我們?cè)?bucket 的 Init 方法中會(huì)根據(jù)傳入 maxBytes 桶字節(jié)數(shù)來(lái)設(shè)置 chunks 的長(zhǎng)度大小，由于每個(gè) chunk 大小都是 64 * 1024bytes，那么我們?cè)O(shè)置 3 * 64 * 1024bytes 大小的桶，那么 chunks 數(shù)組長(zhǎng)度就為 3。

如果當(dāng)前算出 chunkIdx 在 chunks 數(shù)組為 1 的位置，并且在 chunks[1] 的位置中，還剩下 6bytes 未被使用，那么有如下幾種情況：

現(xiàn)在假設(shè)放入的鍵值長(zhǎng)度都是 1byte，那么在 chunks[1] 的位置中剩下的 6bytes 剛好可以放下;

現(xiàn)在假設(shè)放入的鍵值長(zhǎng)度超過(guò)了 1byte，那么在 chunks[1] 的位置中剩下的位置就放不下，只能放入到 chunks[2] 的位置中。

如果當(dāng)前算出 chunkIdx 在 chunks 數(shù)組為 2 的位置，并且現(xiàn)在 Set 一個(gè)鍵值，經(jīng)過(guò)計(jì)算 chunkIdxNew 為 3，已經(jīng)超過(guò)了 chunks 數(shù)組長(zhǎng)度，那么會(huì)將索引重置，重新將數(shù)據(jù)從 chunks[0] 開(kāi)始放置，并將 gen 加一，表示已經(jīng)跑完一圈了。

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 方法是一樣的，首先是要找到對(duì)應(yīng)的桶的位置，然后才去桶里面拿數(shù)據(jù)。需要注意的是，這里的 dst 可以從外部傳入一個(gè)切片，以達(dá)到減少重復(fù)分配返回值。

 
 
 
 
    
  
  
  
  
  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.   // 這里說(shuō)明chunks還沒(méi)被寫滿 
    12. 
  
  
  
  
  12.   if gen == bGen && idx < b.idx || 
    13. 
  
  
  
  
  13.    // 這里說(shuō)明chunks已被寫滿，并且當(dāng)前數(shù)據(jù)沒(méi)有被覆蓋 
    14. 
  
  
  
  
  14.    gen+1 == bGen && idx >= b.idx || 
    15. 
  
  
  
  
  15.    // 這里是邊界條件gen已是最大，并且chunks已被寫滿bGen從1開(kāi)始，，并且當(dāng)前數(shù)據(jù)沒(méi)有被覆蓋 
    16. 
  
  
  
  
  16.    gen == maxGen && bGen == 1 && idx >= b.idx { 
    17. 
  
  
  
  
  17.    chunkIdx := idx / chunkSize 
    18. 
  
  
  
  
  18.    // chunk 索引位置不能超過(guò) chunks 數(shù)組長(zhǎng)度 
    19. 
  
  
  
  
  19.    if chunkIdx >= uint64(len(b.chunks)) { 
    20. 
  
  
  
  
  20.     goto end 
    21. 
  
  
  
  
  21.    } 
    22. 
  
  
  
  
  22.    // 找到數(shù)據(jù)所在的 chunk 
    23. 
  
  
  
  
  23.    chunk := b.chunks[chunkIdx] 
    24. 
  
  
  
  
  24.    // 通過(guò)取模找到該key 對(duì)應(yīng)的數(shù)據(jù)在 chunk 中的位置 
    25. 
  
  
  
  
  25.    idx %= chunkSize 
    26. 
  
  
  
  
  26.    if idx+4 >= chunkSize { 
    27. 
  
  
  
  
  27.     goto end 
    28. 
  
  
  
  
  28.    } 
    29. 
  
  
  
  
  29.    // 前 4bytes 是數(shù)據(jù)頭 
    30. 
  
  
  
  
  30.    kvLenBuf := chunk[idx : idx+4] 
    31. 
  
  
  
  
  31.    // 通過(guò)數(shù)據(jù)頭算出鍵值的長(zhǎng)度 
    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.    // 如果鍵值是一致的，表示找到該數(shù)據(jù) 
    39. 
  
  
  
  
  39.    if string(k) == string(chunk[idx:idx+keyLen]) { 
    40. 
  
  
  
  
  40.     idx += keyLen 
    41. 
  
  
  
  
  41.     // 返回該鍵對(duì)應(yīng)的值 
    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 方法主要是考慮環(huán)形鏈表的邊界問(wèn)題。我們?cè)?Set 方法中會(huì)將每一個(gè) key 對(duì)應(yīng)的 gen 和 idx 索引存放到 m 字典中，所以我們通過(guò) hash 獲取 m 字典的值之后通過(guò)位運(yùn)算就可以獲取到 gen 和 idx 索引。

找到 gen 和 idx 索引之后就是邊界條件的判斷了，用一個(gè) if 條件來(lái)進(jìn)行判斷：

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

這里是判斷如果是在環(huán)形鏈表的同一次循環(huán)中，那么 key 對(duì)應(yīng)的索引應(yīng)該小于當(dāng)前桶的索引;

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

這里表示當(dāng)前桶已經(jīng)進(jìn)入到下一個(gè)循環(huán)中，所以需要判斷 key 對(duì)應(yīng)的索引是不是大于當(dāng)前索引，以表示當(dāng)前 key 對(duì)應(yīng)的值沒(méi)有被覆蓋;

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

因?yàn)?gen 和 idx 索引要塞到 uint64 類型的字段中，所以留給 gen 的最大值只有 maxGen = 1<< 24 -1，超過(guò)了 maxGen 會(huì)讓 gen 從 1 開(kāi)始。所以這里如果 key 對(duì)應(yīng) gen 等于 maxGen ，那么當(dāng)前的 bGen 應(yīng)該等于 1，并且 key 對(duì)應(yīng)的索引還應(yīng)該大于當(dāng)前 idx，這樣才這個(gè)鍵值對(duì)才不會(huì)被覆蓋。

判斷完邊界條件之后就會(huì)找到對(duì)應(yīng)的 chunk ，然后取模后找到數(shù)據(jù)位置，通過(guò)偏移量找到并取出值。

Benchmark

下面我上一下過(guò)后的 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.

上面的測(cè)試是 GoCache、BigCache、Map、sync.Map 的情況。下面是本篇文章中所開(kāi)發(fā)的緩存庫(kù)的測(cè)試：

 
 
 
 
    
  
  
  
  
  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.

可以看到內(nèi)存分配是幾乎就不存在，操作速度在上面的庫(kù)中也是佼佼者的存在。

總結(jié)

在本文中根據(jù)其他緩存庫(kù)，并分析了如果用 Map 作為緩存所存在的問(wèn)題，然后引出存在這個(gè)問(wèn)題的原因，并提出解決方案;在我們的緩存庫(kù)中，第一是通過(guò)使用索引加內(nèi)存塊的方式來(lái)存放緩存數(shù)據(jù)，再來(lái)是通過(guò) OS 系統(tǒng)調(diào)用來(lái)進(jìn)行內(nèi)存分配讓我們的緩存數(shù)據(jù)塊脫離了 GC 的控制，從而做到降低 GC 頻率提高并發(fā)的目的。

其實(shí)不只是緩存庫(kù)，在我們的項(xiàng)目中當(dāng)遇到需要使用大量的帶指針的數(shù)據(jù)結(jié)構(gòu)并需要長(zhǎng)時(shí)間保持引用的時(shí)候，也是需要注意這樣做可能會(huì)引發(fā) GC 問(wèn)題，從而給系統(tǒng)帶來(lái)隱患。


網(wǎng)站標(biāo)題：教你打造高性能的Go緩存庫(kù)
瀏覽路徑：http://m.5511xx.com/article/cdjgpec.html