Go 緩衝系列之 - free-cache

我是一隻可愛的土撥鼠，專注於分享 Go 職場、招聘和求職，解 Gopher 之憂！歡迎關注我。

歡迎大家加入 Go 招聘交流羣，來這裏找志同道合的小夥伴！跟土撥鼠們一起交流學習。

一句話描述

https://github.com/coocood/freecache-Go 緩存庫，具有零 GC 開銷和高併發性能

簡介

freecache 介紹

使用 FreeCache，您可以在內存中緩存無限數量的對象，而不會增加延遲和降低吞吐量。

爲什麼選擇 freecache？

性能如何

下面基準測試與內置 Map 的比較結果，“Set” 性能比內置 Map 快約 2 倍，“Get” 性能比內置 Map 慢約 1/2 倍。由於它是單線程基準測試，因此在多線程環境中，FreeCache 應該比單鎖保護的內置 Map 快許多倍。

BenchmarkCacheSet    3000000               446 ns/op
BenchmarkMapSet      2000000               861 ns/op
BenchmarkCacheGet    3000000               517 ns/op
BenchmarkMapGet     10000000               212 ns/op

Example

package main

import (
 "fmt"
 "runtime/debug"

 "github.com/coocood/freecache"
)

func main() {
 // 緩存大小，100M
 cacheSize := 100 * 1024 * 1024
 cache := freecache.NewCache(cacheSize)
 debug.SetGCPercent(20)
 key := []byte("abc")
 val := []byte("def")
 expire := 60 // expire in 60 seconds
 // 設置KEY
 cache.Set(key, val, expire)
 got, err := cache.Get(key)
 if err != nil {
  fmt.Println(err)
 } else {
  fmt.Printf("%s\n", got)
 }
 fmt.Println("entry count ", cache.EntryCount())
 affected := cache.Del(key)
 fmt.Println("deleted key ", affected)
 fmt.Println("entry count ", cache.EntryCount())
}

freecache 有幾個特點：零 GC，接近 LRU 的淘汰算法，迭代器支持 我們將從源碼分析、核心的存儲結構來分析他是怎麼實現的

核心的存儲結構

package freecache

import (
 "sync"
)

const (
 segmentCount = 256
)

// Cache is a freecache instance.
type Cache struct {
 locks    [segmentCount]sync.Mutex
 segments [segmentCount]segment // 256個 segment， segment實際存儲數據的結構
 // segment 裏面有一個 環形數組，環形數組的大小按照 size/segmentCount 來確定
}

type segment struct {
 rb  RingBuf // 實際數據存儲的數組
 slotsData  []entryPtr // 數據索引地址，用於定位到具體的數據在數組中的位置
 ...
}

// entryPtr 索引
type entryPtr struct {
 offset   int64  // 數據在環形數組中的偏移量
 hash16   uint16  
 keyLen   uint16 
 reserved uint32
}

// RingBuf 存儲實際數據
type RingBuf struct {
 begin int64 
 end   int64 
 data  []byte
 index int 
}

// RingBuf 中的數據頭, 這個記錄的是
type entryHdr struct {
 accessTime uint32
 expireAt   uint32
 keyLen     uint16
 hash16     uint16
 valLen     uint32
 valCap     uint32
 deleted    bool
 slotId     uint8
 reserved   uint16
}

結構圖

圖片

流程分析

流程分析只分析了了 Set 和淘汰算法的實現

Set

  1. Set 數據是會先計算出 Key 對應的 hash 值，這個數據會在後面計算 segID 和 slotId 使用到

  2. 做一些數據合法的判斷

  3. 根據 slotId 找到 slot

  4. 根據 slot 和 hash16 獲取到在 Key 在 slot 中的 index

  5. 拿到 index 之後在 cache 的 RingBuf 中查找數據

  6. 找到的時候則需要根據新舊兩個數據長度判斷是否需要擴容

  7. 沒有找到則直接寫入新的數據

圖片

淘汰算法的實現

freecache 的淘汰算法有兩種實現：過期刪除、接近 LRU 的淘汰算法

過期刪除

freecache 的過期刪除並不是有一個後臺協程去刪除，而是在 Get 的時候纔會判斷，這樣可以減少鎖的搶佔

package freecache
// 發現是過期直接就返回ErrNotFound
if hdr.expireAt != 0 && hdr.expireAt <= now {
  seg.delEntryPtr(slotId, slot, idx)
  atomic.AddInt64(&seg.totalExpired, 1)
  err = ErrNotFound
  atomic.AddInt64(&seg.missCount, 1)
  return
}

接近 LRU 的淘汰算法

package freecache
// 如果過期
expired := oldHdr.expireAt != 0 && oldHdr.expireAt < now
// 近似LRU
leastRecentUsed := int64(oldHdr.accessTime)*atomic.LoadInt64(&seg.totalCount) <= atomic.LoadInt64(&seg.totalTime)
if expired || leastRecentUsed || consecutiveEvacuate > 5 {
    seg.delEntryPtrByOffset(oldHdr.slotId, oldHdr.hash16, oldOff)
if oldHdr.slotId == slotId {
    slotModified = true
}
consecutiveEvacuate = 0
atomic.AddInt64(&seg.totalTime, -int64(oldHdr.accessTime))
atomic.AddInt64(&seg.totalCount, -1)
seg.vacuumLen += oldEntryLen
if expired {
    atomic.AddInt64(&seg.totalExpired, 1)
} else {
    atomic.AddInt64(&seg.totalEvacuate, 1)
}

Doc

https://pkg.go.dev/github.com/coocood/freecache

比較

Benchmark

benchmark 數據可參考 https://github.com/allegro/bigcache-bench

相似的庫

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

猜你喜歡