日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Mango?Cache緩存管理庫TinyLFU源碼解析_Golang

作者：司司sama ? 更新時間： 2022-11-02 編程語言

介紹

據官方所述,mango Cache是對Guava Cache基于go的部分實現,同時mangoCache參考了Caffeine以及go-tinylfu.

支持以下緩存管理策略:

  • LRU
  • Segmented LRU(默認)
  • TinyLFU(實驗性)

本文將從源碼對其進行解析,重點將放在loadingCache(一種可以自定義如何載入新內存的cache)上面.

整體架構

mango Cache的主體功能由localCache結構體(local.go)實現,

type localCache struct {
    cache cache // 真正存放數據的地方
    expireAfterAccess time.Duration //用戶自定義的過期以及刷新時間
    expireAfterWrite  time.Duration
    refreshAfterWrite time.Duration
    policyName        string    //緩存管理策略
    onInsertion Func //鉤子函數
    onRemoval   Func
    loader   LoaderFunc //自定義加載和重載函數
    reloader Reloader
    stats    StatsCounter //狀態管理器
    cap int //緩存容量
    // 訪問時的緩存管理策略
    accessQueue policy
    // 寫入時的緩存管理策略,只有在expireAfterWrite或refreshAfterWrite被設置以后才啟用
    writeQueue policy
    // 用于processEntries的事件隊列
    events chan entryEvent
    // 記錄距離上一次寫期間發生的讀次數,用于判斷是否進行清掃
    readCount int32
    // 用于關閉由localCache創建的協程
    closing int32
    closeWG sync.WaitGroup
}

真正存儲數據的結構體是cache(policy.go),所有緩存數據都存儲在其中

type cache struct {
    size int64                  // 緩存大小
    segs [segmentCount]sync.Map // 分片sync.map, map[key]*entry
}

entry是存放一個緩存數據的單元

type entry struct {
   hash uint64  //key的hash值
   accessTime int64 
   writeTime int64 
   invalidated int32 //是否有效
   loading     int32 //是否處于載入中狀態
   key   Key
   value atomic.Value // 存儲的值
   // 下面的屬性只被緩存管理策略操作,所以不需要原子性的訪問
   accessList *list.Element //此entry目前所在的訪問鏈表中的位置
   writeList *list.Element  //此entry目前所在的寫入鏈表中的位置
   listID uint8             //此entry目前所在的緩存段(SLRU)
}

localCache使用事件隊列來管理并發讀寫事件,事件隊列是一個chan,其中流轉著entryEvent(即數據以及對應的緩存事件),localCache通過processEntries協程來處理各種讀寫事件.之后將詳細講解mango Cache是如何進行讀寫操作的.

localCache的write、access等操作底層是通過操作cache、accessQueue以及writeQueue從而實現的,而localCache還會負責清掃過期數據的工作.

前面提到了mango Cache支持諸如LRU、SLRU以及TinyLFU等緩存管理策略,其在localCache中即為accessQueue以及writeQueue,負責對緩存的淘汰準入等操作.

初始化流程

mango Cache提供了兩種cache---普通Cache以及LoadingCache,這兩者都是接口,而localCache實現了這兩個接口,由于LoadingCache繼承了普通Cache,因此本文只講解LoadingCache.

func NewLoadingCache(loader LoaderFunc, options ...Option) LoadingCache {
    c := newLocalCache()
    c.loader = loader
    for _, opt := range options {
        opt(c)
    }
    c.init()
    return c
}

NewLoadingCache函數先初始化一個LoadingCache,然后根據用戶傳入的自定義載入函數和一些配置來初始化LoadingCache.配置包括注冊插入或者刪除時觸發的鉤子函數以及過期時間等等.然后調用localCache.init.

func (c *localCache) init() {
    c.accessQueue = newPolicy(c.policyName)
    c.accessQueue.init(&c.cache, c.cap)
    if c.expireAfterWrite > 0 || c.refreshAfterWrite > 0 {
        c.writeQueue = &recencyQueue{}
    } else {
        c.writeQueue = discardingQueue{}
    }
    c.writeQueue.init(&c.cache, c.cap)
    c.events = make(chan entryEvent, chanBufSize)
    c.closeWG.Add(1)
    go c.processEntries()
}

localCache.init會根據用戶傳入的緩存管理策略名字來初始化accessQueue然后根據是否有寫過期和寫刷新配置來決定是否初始化寫入隊列.接著創建事件隊列并開啟事件處理協程.到此為止,cache啟動完成.

讀流程

LoadingCache的Get操作可以通過key獲取緩存值,其流程為:

先從主緩存中查詢entry

若未查詢到entry,則記錄miss并且調用用戶自定義的load方法加載緩存值并返回

若查詢到entry,先檢查是否過期

  • 若過期且沒有設置loader則直接向事件處理協程發送eventDelete
  • 若過期但設置了loader,則異步更新entry值

若沒有過期則更新訪問時間并向事件處理協程發送eventAccess然后記錄命中

最后返回entry

func (c *localCache) Get(k Key) (Value, error) {
    en := c.cache.get(k, sum(k)) //計算key的hash并查詢該key
    if en == nil {
        c.stats.RecordMisses(1)
        return c.load(k)
    }
    // 檢查entry是否需要更新
    now := currentTime()
    if c.isExpired(en, now) {
        if c.loader == nil {    //如果沒有設置加載器則直接刪除該entry
            c.sendEvent(eventDelete, en)
        } else {
            //對于loadingCache,我們不刪除這個entry
            //而是把它暫時留在緩存中,所以用戶依舊可以讀取到舊的緩存值
            c.setEntryAccessTime(en, now)
            c.refreshAsync(en)
        }
        c.stats.RecordMisses(1)
    } else {
        c.setEntryAccessTime(en, now)
        c.sendEvent(eventAccess, en)
        c.stats.RecordHits(1)
    }
    return en.getValue(), nil
}

需要注意一下這里的refreshAsync函數:

func (c *localCache) refreshAsync(en *entry) bool {
    if en.setLoading(true) {
        // 如果此entry沒有在加載
        if c.reloader == nil {
            go c.refresh(en)
        } else {
            c.reload(en)
        }
        return true
    }
    return false
}

如果沒有用戶設置的重載器,就異步執行refresh,refresh函數實際上就是對entry進行加載.

而如果有重載器那么就同步執行用戶自定義的reload函數.

寫流程

loadingCache的Put操作與Get操作類似,流程如下:

先去主緩存查詢key是否存在,若查詢到對應的entry,那么直接更新entry

若沒有查詢到對應的entry,說明其不存在,因此根據key,value初始化一個新entry

如果緩存容量足夠,則讓主緩存存儲該entry,此時會再次檢查主存中是否有該entry(解決并發問題)

  • 若cen不為空,說明主緩存中已經存在該entry,直接修改該entry即可
  • 若cen為空,說明主緩存中還不存在該entry,那么就會在主緩存中存儲該entry

最后向事件處理協程發送eventWrite事件

func (c *localCache) Put(k Key, v Value) {
   h := sum(k)
   en := c.cache.get(k, h)
   now := currentTime()
   if en == nil {
      en = newEntry(k, v, h)
      c.setEntryWriteTime(en, now)
      c.setEntryAccessTime(en, now)
       // 直接將新value添加進緩存(在緩存容量足夠的時候)
      if c.cap == 0 || c.cache.len() < c.cap {
         cen := c.cache.getOrSet(en)
         if cen != nil {
            cen.setValue(v)
            c.setEntryWriteTime(cen, now)
            en = cen
         }
      }
   } else {
      // 更新entry
      en.setValue(v)
      c.setEntryWriteTime(en, now)
   }
   c.sendEvent(eventWrite, en)
}
//當entry在緩存中存在,則返回該entry,否則存儲該entry
func (c *cache) getOrSet(v *entry) *entry {
    seg := c.segment(v.hash)
    en, ok := seg.LoadOrStore(v.key, v)
    if ok {
        return en.(*entry)
    }
    atomic.AddInt64(&c.size, 1)
    return nil
}

事件處理機制

主流程

mango Cache通過entryEvent chan以及processEntries協程來處理并發讀寫事務

緩存事件一共四個,分別為寫入、訪問、刪除以及關閉.每個業務協程通過向localCache的events chan發送entryEvent通知事件處理協程,進而實現并發讀寫.

而processEntries協程內,會不斷從events chan內取出entryEvent并執行對應的操作,在write、access以及delete操作后會執行清理工作(具體清掃工作由expireEntries函數執行)

type event uint8
const (
    eventWrite event = iota
    eventAccess
    eventDelete
    eventClose
)
type entryEvent struct {
    entry *entry
    event event
}
func (c *localCache) processEntries() {
    defer c.closeWG.Done()
    for e := range c.events {
        switch e.event {
        case eventWrite:          //寫入事務
            c.write(e.entry)
            c.postWriteCleanup()  //清理操作
        case eventAccess:         //訪問事務
            c.access(e.entry)
            c.postReadCleanup()   //清理操作
        case eventDelete:
            if e.entry == nil {   //InvalidateAll函數中使用
                c.removeAll()
            } else {
                c.remove(e.entry) //移除單個entry
            }
            c.postReadCleanup()   //清理操作
        case eventClose:
            if c.reloader != nil {
                // 停止所有refresh工作
                c.reloader.Close()
            }
            c.removeAll()
            return
        }
    }
}

write

由于事件處理機制對于access、delete和write的操作類似,因此這里只講解較為復雜的write操作:

首先通過調用底層訪問隊列以及寫入隊列的write方法

觸發用戶自定義的鉤子函數

如果write方法返回值不為空,說明有entry被驅逐,

因此需要從寫入隊列將其刪除,同時記錄驅逐并觸發用戶自定義的鉤子函數

func (c *localCache) write(en *entry) {
    ren := c.accessQueue.write(en)
    c.writeQueue.write(en)
    if c.onInsertion != nil {
        c.onInsertion(en.key, en.getValue())
    }
    if ren != nil { //有entry被驅逐出了緩存
        c.writeQueue.remove(ren)
        c.stats.RecordEviction()
        if c.onRemoval != nil {
            c.onRemoval(ren.key, ren.getValue())
        }
    }
}

后面將詳細講述底層訪問隊列以及緩存管理是如何實現的.

清理工作

前面講到過每次進行完write、access以及delete操作后會執行清理工作.具體地,write操作會觸發postWriteCleanup而access和delete操作會觸發postReadCleanup.

postReadCleanup會根據當前距離上一次寫的read操作次數是否達到清理工作閾值來決定是否清理,這個閾值是64,也就是說每隔64次read操作就會觸發一次清理工作

而postWriteCleanup將在每一次write操作之后觸發

真正的清理工作由expireEntries函數完成,它一次清理工作最多只會清理16個entry避免了對事件處理的長時間阻塞.

func (c *localCache) postReadCleanup() {
    if atomic.AddInt32(&c.readCount, 1) > drainThreshold {
        atomic.StoreInt32(&c.readCount, 0)
        c.expireEntries()
    }
}
// 在添加完entry以后再執行
func (c *localCache) postWriteCleanup() {
    atomic.StoreInt32(&c.readCount, 0)
    c.expireEntries()
}
//清理工作函數
func (c *localCache) expireEntries() {
    remain := drainMax
    now := currentTime()
    if c.expireAfterAccess > 0 {
        expiry := now.Add(-c.expireAfterAccess).UnixNano()
        c.accessQueue.iterate(func(en *entry) bool {
            if remain == 0 || en.getAccessTime() >= expiry {
                // 找到了第一個沒有過期的entry或者清理entry數足夠了
                return false
            }
            c.remove(en)
            c.stats.RecordEviction()
            remain--
            return remain > 0
        })
    }
    if remain > 0 && c.expireAfterWrite > 0 {
        ...
    }
    if remain > 0 && c.loader != nil && c.refreshAfterWrite > 0 {
        ...
    }
}

緩存管理

localCache在初始化過程中也初始化了緩存管理策略,由于localCache的writeQueue默認使用LRU緩存淘汰策略,而accessQueue支持LRU、SLRU以及TinyLFU三種緩存淘汰策略,本節將著重講解accessQueue.

什么是LRU?

LRU是Least Recently Used的縮寫,即最近最少使用.在mango Cache中LRU依靠go SDK自帶的List(雙向鏈表)實現,新緩存條目會被插入List頭部,如果List內元素達到容量上限則刪除List尾部的元素,此元素也正是最近最少使用的元素.LRU可以使得主緩存內的緩存條目永遠是最近被訪問的,不是最近訪問的元素將被淘汰.

如果一個不是經常使用的數據，偶爾或者周期性的被使用,那么該數據會被加到LRU鏈表頭部,而這種不經常使用的數據,放在鏈表頭部,占用了空間;一直等到LRU淘汰完,才會被剔除鏈表;如果這種數據一次性過多,那么鏈表數據都是這種無用的數據,從而會導致緩存命中率低下,影響系統性能.

什么是SLRU?

Segmented LRU(SLRU)是一種LRU的改進,主要把在一個時間窗口內命中至少2次的記錄和命中1次的單獨存放,這樣就可以把短期內較頻繁的緩存元素區分開來.具體做法上,SLRU包含2個固定尺寸的LRU,一個叫Probation段(A1),一個叫Protection段(A2).新記錄總是插入到A1中,當A1的記錄被再次訪問,就把它移到A2,當A2滿了需要驅逐記錄時,會把驅逐記錄插入到A1中.

在mango Cache的實現中,Protection段與Probation段大小比為4:1.

SLRU是mango Cache的默認緩存管理策略

什么是TinyLFU?

TinyLFU是一種空間利用率很高的新的數據結構,可以在較大訪問量的場景下近似的替代LFU的數據統計部分(meta-data),其采用類似布隆過濾器的位計數器來實現對每個key的訪問次數的粗略統計.(由于哈希沖突的存在,位計數器的結果將偏大)

對于較為靜態的訪問分布,各種的緩存管理策略的差異是微不足道的,而對于偏倚較大的負載場景,TinyLFU體現出了較大的優勢.即便是使用了TinyLFU準入策略進行優化的LRU也獲得了較大的提升.

如果想要詳細了解TinyLFU請閱讀論文TinyLFU: A Highly Efficient Cache Admission Policy 以及一種簡略實現講解LRU、LFU、TinyLFU緩存算法

mango Cache中的TinyLFU

mango Cache的實現中,實際上是實現了改進版的TinyLFU也就是Window-TinyLFU,這個緩存數據結構也在論文中有講解,簡而言之就是緩存由window Cache、doorKeeper(布隆過濾器)、counter以及SLRU組成.主緩存使用SLRU驅逐策略和TinyLFU準入策略,window Cache僅使用LRU驅逐策略無準入策略.

主緩存中的SLRU策略的A1和A2區域被靜態劃分開來,80%空間被分配給熱點元素(A2),被驅逐者則從20%的非熱項(A1)中選取.任何到來的元素總是允許進入window Cache, window Cache的淘汰元素有機會進入主緩存,如果在經過TinyLFU準入策略檢驗后被主緩存接受,那么該元素將進入主緩存,此時Window-TinyLFU的淘汰者就是主緩存的淘汰者(從A1段選出),否則該元素將被window Cache淘汰.

type tinyLFU struct {
    filter  bloomFilter    // doorkeeper
    counter countMinSketch // 4bit計數器
    additions int   //目前采樣數量
    samples   int   //采樣窗口大小
    lru  lruCache   //window Cache
    slru slruCache  //主緩存
}

接下來本文將詳細講述mango Cache中tinyLFU的具體實現

counter

counter是實現TinyLFU的重點,對于訪問次數的粗略統計就是通過此數據結構實現的.

const sketchDepth = 4   //hash次數
type countMinSketch struct {
    counters []uint64
    mask     uint32
}

可以看到, counter由一個uint64類型的數組和一個mask組成, 因為我們使用的是4次hash的4bit計數器,因此數組的每個元素實際上是4個計數器,可以通過位操作來實現訪問.

counter的初始化

func (c *countMinSketch) init(width int) {
    size := nextPowerOfTwo(uint32(width)) >> 2 //size = (width * 4 * 4) bits / 64
    if size < 1 {
        size = 1
    }
    c.mask = size - 1
    if len(c.counters) == int(size) {
        c.clear()
    } else {
        c.counters = make([]uint64, size)
    }
}

我們通過傳入的width確定需要的計數器數量(size大小)

counter的使用

counter最關鍵的操作就是按hash增加計數器值以及根據hash估算該hash的計數器值:

func (c *countMinSketch) add(h uint64) {
    h1, h2 := uint32(h), uint32(h>>32)
    for i := uint32(0); i < sketchDepth; i++ {  //這里使用折疊法求得hash值
        idx, off := c.position(h1 + i*h2)
        c.inc(idx, (16*i)+off)
    }
}
// 根據給定hash值返回對應計數器中最小的那個計數器值
func (c *countMinSketch) estimate(h uint64) uint8 {
    h1, h2 := uint32(h), uint32(h>>32)
    var min uint8 = 0xFF
    for i := uint32(0); i < sketchDepth; i++ {
        idx, off := c.position(h1 + i*h2)
        count := c.val(idx, (16*i)+off)
        if count < min {
            min = count
        }
    }
    return min
}

里面的position、val以及inc函數都是對應的位操作,有興趣的話可以進一步研究下.

需要注意的是estimate函數用于求給定hash對應計數器中最小計數器的值,這是因為有哈希碰撞的情況,因此計數器的值始終會大于等于真實的訪問次數,因此這里采用多次hash取其中最小值的方法來減少誤差.

同時,為了保證計數器的時效性,counter實現了新鮮度機制,將在一定條件下觸發reset:

//將每個計數器的值減半
func (c *countMinSketch) reset() {
    for i, v := range c.counters {
        if v != 0 {
            c.counters[i] = (v >> 1) & 0x7777777777777777
        }
    }
}

lruCache

lruCache是LRU的實現,在mango Cache中是一個鏈表.

type lruCache struct {
    cache *cache
    cap   int
    ls    list.List
}
func (l *lruCache) init(c *cache, cap int) {
    l.cache = c
    l.cap = cap
    l.ls.Init()
}

slruCache

slruCache是SLRU的實現,在mango Cache中由兩個鏈表組成.

const (
    protectedRatio = 0.8
)
type slruCache struct {
    cache *cache
    probationCap int
    probationLs  list.List
    protectedCap int
    protectedLs  list.List
}
func (l *slruCache) init(c *cache, cap int) {
    l.cache = c
    l.protectedCap = int(float64(cap) * protectedRatio)
    l.probationCap = cap - l.protectedCap
    l.probationLs.Init()
    l.protectedLs.Init()
}

slruCache中,值得注意的點是它的寫入策略:

func (l *slruCache) write(en *entry) *entry {
    if en.accessList != nil {
        // entry已存在,直接修改該entry
        l.markAccess(en)
        return nil
    }
    // 嘗試將新entry加入probation段
    cen := l.cache.getOrSet(en)
    if cen == nil {
        en.listID = probationSegment    //將其加入probation段
        en.accessList = l.probationLs.PushFront(en)
    } else {
        // 該entry已存在,直接修改它的值
        cen.setValue(en.getValue())
        cen.setWriteTime(en.getWriteTime())
        if cen.accessList == nil {
            //該entry已載入緩存但是還沒有注冊到SLRU管理的鏈表中
            cen.listID = probationSegment
            cen.accessList = l.probationLs.PushFront(cen)
        } else {
            l.markAccess(cen)
        }
    }
    // probation段超出容量但list并沒有超出容量
    if l.probationCap > 0 && l.probationLs.Len() > l.probationCap &&
        l.length() > (l.probationCap+l.protectedCap) {
        // 移除并返回probation段尾部的entry
        en = getEntry(l.probationLs.Back())
        return l.remove(en)
    }
    return nil
}
//記錄訪問情況
func (l *slruCache) markAccess(en *entry) {
    if en.listID == protectedSegment {
        // entry位于在protected段
        l.protectedLs.MoveToFront(en.accessList)
        return
    }
    // 若entry位于probation段,則將其提升至protected段
    en.listID = protectedSegment
    l.probationLs.Remove(en.accessList)
    en.accessList = l.protectedLs.PushFront(en)
    if l.protectedCap > 0 && l.protectedLs.Len() > l.protectedCap {
        // protected段超出容量限制,則淘汰其尾部的entry將其加入probation段
        en = getEntry(l.protectedLs.Back())
        en.listID = probationSegment
        l.protectedLs.Remove(en.accessList)
        en.accessList = l.probationLs.PushFront(en)
    }
}

這樣一來,就實現了SLRU的緩存管理策略.

filter

filter是一個布隆過濾器,這里不展開講解其實現細節,只需要了解布隆過濾器可以通過key的hash來確定這個key是否在filter中,并且其只占用非常小的內存.如果想要詳細了解布隆過濾器,可以參考這篇文章:布隆過濾器

type bloomFilter struct {
    numHashes uint32   // 每個元素使用的hash數量
    bitsMask  uint32   // 位向量大小
    bits      []uint64 // 過濾器位向量
}
//根據給定的插入元素數量以及假陽性率初始化布隆過濾器
func (f *bloomFilter) init(ins int, fpp float64) {
    ln2 := math.Log(2.0)
    factor := -math.Log(fpp) / (ln2 * ln2)
    numBits := nextPowerOfTwo(uint32(float64(ins) * factor))
    if numBits == 0 {
        numBits = 1
    }
    f.bitsMask = numBits - 1
    if ins == 0 {
        f.numHashes = 1
    } else {
        f.numHashes = uint32(ln2 * float64(numBits) / float64(ins))
    }
    size := int(numBits+63) / 64
    if len(f.bits) != size {
        f.bits = make([]uint64, size)
    } else {
        f.reset()
    }
}

TinyLFU的初始化

前面介紹了TinyLFU的各個組件,接下來將詳細講解TinyLFU是如何進行緩存管理的.

const (                                 //entry所處的緩存段
    admissionWindow uint8 = iota        
    probationSegment
    protectedSegment
)
const (
    samplesMultiplier        = 8        //采樣窗口大小乘數
    insertionsMultiplier     = 2        //doorkeeper大小乘數
    countersMultiplier       = 1        //計數器大小乘數
    falsePositiveProbability = 0.1      //假陽性率
    admissionRatio           = 0.01     //window Cache占比
)
func (l *tinyLFU) init(c *cache, cap int) {
    if cap > 0 {
        // 只在容量有上限時開啟doorkeeper
        l.samples = samplesMultiplier * cap     //采樣窗口大小
        l.filter.init(insertionsMultiplier*cap, falsePositiveProbability)   //doorkeeper初始化
        l.counter.init(countersMultiplier * cap)    //計數器初始化
    }
    lruCap := int(float64(cap) * admissionRatio) 
    l.lru.init(c, lruCap)               //window Cache初始化
    l.slru.init(c, cap-lruCap)          //SLRU主存初始化
}

TinyLFU寫入

TinyLFU的寫入流程如下

首先寫入window Cache

如果window Cache出現被淘汰的candidate,則將從SLRU中選取一個victim(如果SLRU未滿,則不會產生victim,此時直接將candidate插入SLRU)

在計數器中查詢candidate和victim的訪問次數

  • 若candidate的訪問次數較大,則將其插入SLRU,淘汰victim
  • 否則將candidate淘汰

根據此流程,我們可以發現被插入SLRU的entry的訪問次數一定是較大的,而我們通過計數器實現了對entry訪問次數的保存,這樣就結合了LRU以及LFU的優點并且沒有占用過多的內存,這正是TinyLFU最大的優勢所在.

func (l *tinyLFU) write(en *entry) *entry {
    if l.lru.cap <= 0 {             //若容量無限,則直接對SLRU寫入
        return l.slru.write(en)
    }
    l.increase(en.hash)             //entry訪問次數+1
    candidate := l.lru.write(en)    //window Cache中被淘汰的entry
    if candidate == nil {
        return nil
    }
    victim := l.slru.victim()       //SLRU中下一個將被淘汰的entry
    if victim == nil {
        return l.slru.write(candidate)
    }
    candidateFreq := l.estimate(candidate.hash)
    victimFreq := l.estimate(victim.hash)
    if candidateFreq > victimFreq {
        return l.slru.write(candidate)
    }
    return candidate
}

TinyLFU訪問

TinyLFU的訪問很簡單,只是根據entry所在的緩存段分別調用對應的access函數實現訪問

func (l *tinyLFU) access(en *entry) {
    l.increase(en.hash)
    if en.listID == admissionWindow {
        l.lru.access(en)
    } else {
        l.slru.access(en)
    }
}

增加entry的訪問次數

write函數中通過increase可以對entry的訪問次數+1,下面分析一下increase函數:

func (l *tinyLFU) increase(h uint64) {
    if l.samples <= 0 {
        return
    }
    l.additions++
    if l.additions >= l.samples {
        l.filter.reset()
        l.counter.reset()
        l.additions = 0
    }
    if l.filter.put(h) {
        l.counter.add(h)
    }
}

這里會判斷已采樣數量是否超出采樣窗口,若超出了則會重置doorkeeper和計數器.如果entry在doorkeeper中存在,那么filter.put(h)將返回true,此時會調用counter.add(h)來增加entry的訪問次數.

估計entry訪問次數

write函數中通過estimate可以查詢entry的訪問次數,下面分析一下estimate函數:

func (l *tinyLFU) estimate(h uint64) uint8 {
    freq := l.counter.estimate(h)
    if l.filter.contains(h) {
        freq++
    }
    return freq
}

已經在前面的章節中介紹過counter.estimate(),其根據hash值返回對應元素的計數器中最小的值以減少哈希碰撞的影響.這里需要注意的是l.filter.contains(h),它將在doorkeeper中查找該hash值是否存在,若存在需要將估計值+1(因為doorkeeper中的值也算訪問次數)

總結

Mango Cache中還有統計模塊來記錄緩存的各方面運行狀態(命中率,緩存驅逐等等),由于不是核心內容,因此就不在本文進行贅述了.

Mango Cache最值得學習的點就是事件處理機制和TinyLFU緩存管理策略,希望讀者可以好好體會在并發狀態下,如何實現安全且高效的緩存操作并借助TinyLFU實現較高的緩存命中率.

原文鏈接：https://juejin.cn/post/7140529912020434952

欄目分類
最近更新