go實現LRU cache

Jackwoo 發布于2019-08-06 13:31 / 2612人閱讀

摘要：簡介概述緩存資源通常比較昂貴通常數據量較大時會竟可能從較少的緩存滿足盡可能多訪問這里有一種假設通常最近被訪問的數據那么它就有可能會被后續繼續訪問基于這種假設將所有的數據按訪問時間進行排序并按驅逐出舊數據那么存在緩存的數據就為熱點數據這樣既節

1. LRU簡介 1.1 概述

緩存資源通常比較昂貴,通常數據量較大時,會竟可能從較少的緩存滿足盡可能多訪問,這里有一種假設,通常最近被訪問的數據,那么它就有可能會被后續繼續訪問,基于這種假設,將所有的數據按訪問時間進行排序,并按驅逐出舊數據,那么存在緩存的數據就為熱點數據,這樣既節省了內存資源,又極大的滿足了訪問.LRU(Least recently used)算法就是基于這種假設的一直緩存置換算法.

1.2 算法流程

假設緩存大小為4,而寫入順序為A B C D E D F.訪問順序分為寫入以及讀取兩種操作,寫入需要更新訪問時間,并且當數據到達最大緩存時需要逐出數據,而讀取只會更新訪問時間,寫入置換算法流程如上圖所示.

當未到達緩存大小時,所有數據按寫入存儲,并記錄寫入次序.
寫入E時緩存已經滿,且E的值不存在,需要逐出最久未訪問的數據A,此時緩存內容為E D C B.
下一個寫入D, D在緩存中,直接更新D的訪問次序,此時緩存內容為 D E C B
下一個寫入F, F不在緩存中,逐出緩存中的末尾C,此時緩存內容為 F D E C

2 go實現 2.1思路

采用go,可以使用list加map實現LRU cache,具體思路為:
寫入時,先從map中查詢,如果能查詢,如果能查詢到值,則將該值的在List中移動到最前面.如果查詢不到值,則判斷當前map是否到達最大值,如果到達最大值則移除List最后面的值,同時刪除map中的值,如果map容量未達最大值,則寫入map,同時將值放在List最前面.

讀取時,從map中查詢,如果能查詢到值,則直接將List中該值移動到最前面,返回查詢結果.

為保證并發安全,需要引入讀寫鎖.
另外,存在讀取List中內容反差map的情況,因為聲明一個容器對象同時保存key以及value, List中以及map中存儲的都是容器對象的引用.
引入原子對象對命中數以及未命中數等指標進行統計

2.2 關鍵代碼

完整代碼見: https://github.com/g4zhuj/cache

Set(寫入操作)

func (c *MemCache) Set(key string, value interface{}) {
    c.mutex.Lock()
    defer c.mutex.Unlock()
    if c.cache == nil {
        c.cache = make(map[interface{}]*list.Element)
        c.cacheList = list.New()
    }

    //判斷是否在map中,如果在map中,則將value從list中移動到前面.
    if ele, ok := c.cache[key]; ok {
        c.cacheList.MoveToFront(ele)
        ele.Value.(*entry).value = value
        return
    }

    //如果不再map中,將值存到List最前面
    ele := c.cacheList.PushFront(&entry{key: key, value: value})
    c.cache[key] = ele
    //判斷是否到達容量限制,到達容量限制時刪除List中最后面的值.
    if c.maxItemSize != 0 && c.cacheList.Len() > c.maxItemSize {
        c.RemoveOldest()
    }
}

Get(讀取操作)

func (c *MemCache) Get(key string) (interface{}, bool) {
    c.mutex.RLock()
    defer c.mutex.RUnlock()
    c.gets.Add(1)
    //如果讀取到值,移動在List中位置,并返回value
    if ele, hit := c.cache[key]; hit {
        c.hits.Add(1)
        c.cacheList.MoveToFront(ele)
        return ele.Value.(*entry).value, true
    }
    return nil, false
}

3. 參考

https://en.wikipedia.org/wiki...

GPU云服務器云服務器 lru用c語言實現 LRU redis LRU LRU機制

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/61971.html

剝開比原看代碼12：比原是如何通過/create-account-receiver創建地址的？

摘要：繼續看生成地址的方法由于這個方法里傳過來的是而不是對象，所以還需要再用查一遍，然后，再調用這個私有方法創建地址該方法可以分成部分在第塊中主要關注的是返回值。作者：freewind 比原項目倉庫： Github地址：https://github.com/Bytom/bytom Gitee地址：https://gitee.com/BytomBlockc... 在比原的dashboard中...

oneasp 2019-06-27 18:34 評論0 收藏0
一個線程安全的 lrucache 實現 --- 讀 leveldb 源碼

摘要：在閱讀的源代碼的時候，發現其中的類正是一個線程安全的實現，代碼非常優雅。至此一個線程安全的類就已經全部實現，在中使用的緩存是，其實就是聚合多個實例，真正的邏輯都在類中。緩存是計算機的每一個層次中都是一個非常重要的概念，緩存的存在可以大大提高軟件的運行速度。Least Recently Used(lru) cache 即最近最久未使用的緩存，多見與頁面置換算法，lru 緩存算法在緩存的...

widuu 2019-08-06 13:30 評論0 收藏0
劍指offer/LeetCode146/LintCode134_LRU緩存實現

摘要：劍指緩存實現聲明文章均為本人技術筆記，轉載請注明出處解題思路緩存兩種功能獲取的對應，不存在返回版本版本設置緩存已滿，刪除最近最久未被使用的節點，添加新節點進緩存緩存未滿，節點存在，修改節點不存在，添加新節點進緩存解題思路由于緩存插入和刪除劍指offer/LeetCode146/LintCode134_LRU緩存實現聲明文章均為本人技術筆記，轉載請注明出處[1] https://s...

you_De 2019-08-14 18:08 評論0 收藏0
NPM酷庫：lru-cache 基于內存的緩存管理

摘要：酷庫，每天兩分鐘，了解一個流行庫。而直接將數據保存在程序變量中，最經濟快捷。但是這樣就會帶來一些其他問題，比如緩存更新緩存過期等。用于在內存中管理緩存數據，并且支持算法。可以讓程序不依賴任何外部數據庫實現緩存管理。 NPM酷庫，每天兩分鐘，了解一個流行NPM庫。為了優化程序性能，我們常常需要獎數據緩存起來，根據實際情況，我們可以將數據存儲到磁盤、數據庫、redis等。但是有時候要緩...

Yumenokanata 2019-08-06 13:29 評論0 收藏0