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

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

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

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

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()
}

func (c *localCache) Get(k Key) (Value, error) {
    en := c.cache.get(k, sum(k)) //計(jì)算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 {    //如果沒有設(shè)置加載器則直接刪除該entry
            c.sendEvent(eventDelete, en)
        } else {
            //對于loadingCache,我們不刪除這個(gè)entry
            //而是把它暫時(shí)留在緩存中,所以用戶依舊可以讀取到舊的緩存值
            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
}

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
}

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添加進(jìn)緩存(在緩存容量足夠的時(shí)候)
      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)
}
//當(dāng)entry在緩存中存在,則返回該entry,否則存儲(chǔ)該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
}

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:          //寫入事務(wù)
            c.write(e.entry)
            c.postWriteCleanup()  //清理操作
        case eventAccess:         //訪問事務(wù)
            c.access(e.entry)
            c.postReadCleanup()   //清理操作
        case eventDelete:
            if e.entry == nil {   //InvalidateAll函數(shù)中使用
                c.removeAll()
            } else {
                c.remove(e.entry) //移除單個(gè)entry
            }
            c.postReadCleanup()   //清理操作
        case eventClose:
            if c.reloader != nil {
                // 停止所有refresh工作
                c.reloader.Close()
            }
            c.removeAll()
            return
        }
    }
}

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被驅(qū)逐出了緩存
        c.writeQueue.remove(ren)
        c.stats.RecordEviction()
        if c.onRemoval != nil {
            c.onRemoval(ren.key, ren.getValue())
        }
    }
}

func (c *localCache) postReadCleanup() {
    if atomic.AddInt32(&c.readCount, 1) > drainThreshold {
        atomic.StoreInt32(&c.readCount, 0)
        c.expireEntries()
    }
}
// 在添加完entry以后再執(zhí)行
func (c *localCache) postWriteCleanup() {
    atomic.StoreInt32(&c.readCount, 0)
    c.expireEntries()
}
//清理工作函數(shù)
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 {
                // 找到了第一個(gè)沒有過期的entry或者清理entry數(shù)足夠了
                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 {
        ...
    }
}

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

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

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)
    }
}

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)
    }
}
// 根據(jù)給定hash值返回對應(yīng)計(jì)數(shù)器中最小的那個(gè)計(jì)數(shù)器值
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
}

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

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()
}

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()
}

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)
    }
}

type bloomFilter struct {
    numHashes uint32   // 每個(gè)元素使用的hash數(shù)量
    bitsMask  uint32   // 位向量大小
    bits      []uint64 // 過濾器位向量
}
//根據(jù)給定的插入元素?cái)?shù)量以及假陽性率初始化布隆過濾器
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()
    }
}

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

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

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

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)
    }
}

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