golang freecache 源碼分析

        go 的 cache 有很多實現,其中 freecache 號稱零 GC 開銷,是怎麼做到的呢?我們從源碼來進行分析,freecache 的地址爲:

https://github.com/coocood/freecache

        go 在一定程度消除了堆和棧的區別,因爲 go 在編譯的時候進行逃逸分析,來決定一個對象放棧上還是放堆上,不逃逸的對象放棧上,可能逃逸的放堆上。編譯參數加入 -gcflags '-m -l',開啓逃逸分析日誌。

逃逸場景

1, 指針逃逸

Go 可以返回局部變量指針,這其實是一個典型的變量逃逸案例

2 ,棧空間不足逃逸(空間開闢過大)

當棧空間不足以存放當前對象時或無法判斷當前切片長度時會將對象分配到堆中。

3, 動態類型逃逸(不確定長度大小)

4, 閉包引用對象逃逸

避免 gc 要從上面四個方面入手考慮,那麼 freecache 是怎麼做到的呢,先看下整體的數據結構:

cache 對象維護了兩個長度爲 256 的數組

type Cache struct {
  locks    [segmentCount]sync.Mutex  // 每個segment都有自己的同步控制鎖
  segments [segmentCount]segment     // 緩存劃分爲256個segment
}

整體思路是:

1,把 key 進行 hash 得到 64 位的 hash 值

// xxhash算法,算出64位哈希值
func hashFunc(data []byte) uint64 {
  return xxhash.Sum64(data)
}

2,按照最低的 8 位分 segment,剛好 256 個 segment

segID := hashVal & segmentAndOpVal
func (cache *Cache) Get(key []byte) (value []byte, err error) {
  // 1. 算出key的64位哈希值
  hashVal := hashFunc(key)
  // 2. 取低8位,得到segId
  segID := hashVal & segmentAndOpVal
  // 找到對應的segment,只對segment加鎖
  // 同個segment的操作是串行進行,不同segment的操作是並行進行的
  cache.locks[segID].Lock()
  value, _, err = cache.segments[segID].get(key, nil, hashVal, false)
  cache.locks[segID].Unlock()
  return
}

3,取右數第二個 8 位分 slot,剛好 256 個 slot

slotId := uint8(hashVal >> 8)

4, 取右數第三個、第四個 8 位最爲 hash16 值,用於初步過濾

hash16 := uint16(hashVal >> 16)

5,接着看下,如何定位 slot

  slot := seg.getSlot(slotId)
  idx, match := seg.lookup(slot, hash16, key)

看之前我們看下 segment 的數據結構

type segment struct {
  // 環形緩衝區RingBuf,由一個固定容量的切片實現
  rb            RingBuf
  segId         int
  _             uint32
  missCount     int64
  hitCount      int64
  entryCount    int64
  totalCount    int64
  totalTime     int64
  timer         Timer
  totalEvacuate int64
  totalExpired  int64
  overwrites    int64
  touched       int64
  vacuumLen     int64
  slotLens      [256]int32
  slotCap       int32 
    // entry索引切片,容量動態擴展
  slotsData     []entryPtr
}

其中 slotsData 存了 entryPtr,查找元素的過程如下:

首先在 slotsData 裏面根據 slotId 和 cap 來取切片

func (seg *segment) getSlot(slotId uint8) []entryPtr {
  slotOff := int32(slotId) * seg.slotCap
  return seg.slotsData[slotOff : slotOff+seg.slotLens[slotId] : slotOff+seg.slotCap]
}

然後通過 hash16 值和 key 來進行匹配

idx, match := seg.lookup(slot, hash16, key)

具體匹配過程如下

A,通過二分查找,粗匹配到 hash16 值相等的位置

func entryPtrIdx(slot []entryPtr, hash16 uint16) (idx int) {
  high := len(slot)
  for idx < high {
    mid := (idx + high) >> 1
    oldEntry := &slot[mid]
    if oldEntry.hash16 < hash16 {
      idx = mid + 1
    } else {
      high = mid
    }
  }
  return
}

B,然後通過 key 相等且 entryPtr 相等來做精確定位

func (seg *segment) lookup(slot []entryPtr, hash16 uint16, key []byte) (idx int, match bool) {
  idx = entryPtrIdx(slot, hash16)
  for idx < len(slot) {
    ptr := &slot[idx]
    if ptr.hash16 != hash16 {
      break
    }
    match = int(ptr.keyLen) == len(key) && seg.rb.EqualAt(key, ptr.offset+ENTRY_HDR_SIZE)
    if match {
      return
    }
    idx++
  }
  return
}

其中 entryPtr 定義如下

 type entryPtr struct {
  offset   int64  // entry offset in ring buffer
  hash16   uint16 // entries are ordered by hash16 in a slot.
  keyLen   uint16 // used to compare a key
  reserved uint32
}

其中 offset 定義了,數據的 key 和 value 在 ringbuffer 裏的偏移量

6,有了偏移量,我們就可以很方便地在 ringbuffer 裏存取數據

讀:

    matchedPtr := &slot[idx]
    seg.rb.ReadAt(hdrBuf[:], matchedPtr.offset)

寫:

      seg.rb.WriteAt(hdrBuf[:], matchedPtr.offset)
      seg.rb.WriteAt(value, matchedPtr.offset+ENTRY_HDR_SIZE+int64(hdr.keyLen))

7,最後看下 ringBuffer 的數據結構

// Ring buffer has a fixed size, when data exceeds the
// size, old data will be overwritten by new data.
// It only contains the data in the stream from begin to end
type RingBuf struct {
  begin int64 // beginning offset of the data stream.
  end   int64 // ending offset of the data stream.
  data  []byte
  index int //range from '0' to 'len(rb.data)-1'
}

本質是一個數組(一塊在棧上連續的內存)

總結:

        通過以上分析,我們可知,freecache,通過對 key 的 hash64 值的後 32 位巧妙利用來進行尋址,做初步定位,有效提高了查找效率,同時由於只分配了 256 個 segment 和 256 個 slots 指針,對於大量緩存機構體來說幾乎可以忽略,所以幾乎不會被 GC 掃描,可以認爲是 0GC 的,有效緩解了 GC 帶來的性能問題。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/fmdk5VBxPHyyVbdtkqwLvg