資訊專欄INFORMATION COLUMN
摘要：簡介概述緩存資源通常比較昂貴通常數(shù)據(jù)量較大時會竟可能從較少的緩存滿足盡可能多訪問這里有一種假設通常最近被訪問的數(shù)據(jù)那么它就有可能會被后續(xù)繼續(xù)訪問基于這種假設將所有的數(shù)據(jù)按訪問時間進行排序并按驅(qū)逐出舊數(shù)據(jù)那么存在緩存的數(shù)據(jù)就為熱點數(shù)據(jù)這樣既節(jié)
1. LRU簡介 1.1 概述
緩存資源通常比較昂貴,通常數(shù)據(jù)量較大時,會竟可能從較少的緩存滿足盡可能多訪問,這里有一種假設,通常最近被訪問的數(shù)據(jù),那么它就有可能會被后續(xù)繼續(xù)訪問,基于這種假設,將所有的數(shù)據(jù)按訪問時間進行排序,并按驅(qū)逐出舊數(shù)據(jù),那么存在緩存的數(shù)據(jù)就為熱點數(shù)據(jù),這樣既節(jié)省了內(nèi)存資源,又極大的滿足了訪問.LRU(Least recently used)算法就是基于這種假設的一直緩存置換算法.
1.2 算法流程假設緩存大小為4,而寫入順序為A B C D E D F.訪問順序分為寫入以及讀取兩種操作,寫入需要更新訪問時間,并且當數(shù)據(jù)到達最大緩存時需要逐出數(shù)據(jù),而讀取只會更新訪問時間,寫入置換算法流程如上圖所示.
當未到達緩存大小時,所有數(shù)據(jù)按寫入存儲,并記錄寫入次序.
寫入E時緩存已經(jīng)滿,且E的值不存在,需要逐出最久未訪問的數(shù)據(jù)A,此時緩存內(nèi)容為E D C B.
下一個寫入D, D在緩存中,直接更新D的訪問次序,此時緩存內(nèi)容為 D E C B
下一個寫入F, F不在緩存中,逐出緩存中的末尾C,此時緩存內(nèi)容為 F D E C
采用go,可以使用list加map實現(xiàn)LRU cache,具體思路為:
寫入時,先從map中查詢,如果能查詢,如果能查詢到值,則將該值的在List中移動到最前面.如果查詢不到值,則判斷當前map是否到達最大值,如果到達最大值則移除List最后面的值,同時刪除map中的值,如果map容量未達最大值,則寫入map,同時將值放在List最前面.
讀取時,從map中查詢,如果能查詢到值,則直接將List中該值移動到最前面,返回查詢結(jié)果.
為保證并發(fā)安全,需要引入讀寫鎖.
另外,存在讀取List中內(nèi)容反差map的情況,因為聲明一個容器對象同時保存key以及value, List中以及map中存儲的都是容器對象的引用.
引入原子對象對命中數(shù)以及未命中數(shù)等指標進行統(tǒng)計
完整代碼見: 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...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/61971.html
摘要：繼續(xù)看生成地址的方法由于這個方法里傳過來的是而不是對象，所以還需要再用查一遍，然后，再調(diào)用這個私有方法創(chuàng)建地址該方法可以分成部分在第塊中主要關注的是返回值。 作者：freewind 比原項目倉庫： Github地址：https://github.com/Bytom/bytom Gitee地址：https://gitee.com/BytomBlockc... 在比原的dashboard中...
摘要：在閱讀的源代碼的時候，發(fā)現(xiàn)其中的類正是一個線程安全的實現(xiàn)，代碼非常優(yōu)雅。至此一個線程安全的類就已經(jīng)全部實現(xiàn)，在中使用的緩存是，其實就是聚合多個實例，真正的邏輯都在類中。 緩存是計算機的每一個層次中都是一個非常重要的概念，緩存的存在可以大大提高軟件的運行速度。Least Recently Used(lru) cache 即最近最久未使用的緩存，多見與頁面置換算法，lru 緩存算法在緩存的...
摘要：劍指緩存實現(xiàn)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路緩存兩種功能獲取的對應，不存在返回版本版本設置緩存已滿，刪除最近最久未被使用的節(jié)點，添加新節(jié)點進緩存緩存未滿，節(jié)點存在，修改節(jié)點不存在，添加新節(jié)點進緩存解題思路由于緩存插入和刪除 劍指offer/LeetCode146/LintCode134_LRU緩存實現(xiàn) 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處[1] https://s...
摘要：酷庫，每天兩分鐘，了解一個流行庫。而直接將數(shù)據(jù)保存在程序變量中，最經(jīng)濟快捷。但是這樣就會帶來一些其他問題，比如緩存更新緩存過期等。用于在內(nèi)存中管理緩存數(shù)據(jù)，并且支持算法。可以讓程序不依賴任何外部數(shù)據(jù)庫實現(xiàn)緩存管理。 NPM酷庫，每天兩分鐘，了解一個流行NPM庫。 為了優(yōu)化程序性能，我們常常需要獎數(shù)據(jù)緩存起來，根據(jù)實際情況，我們可以將數(shù)據(jù)存儲到磁盤、數(shù)據(jù)庫、redis等。 但是有時候要緩...
閱讀 1867·2021-09-29 09:35
閱讀 2729·2021-09-22 15:25
閱讀 1984·2021-08-23 09:43
閱讀 2063·2019-08-30 15:54
閱讀 3361·2019-08-30 15:53
閱讀 2398·2019-08-30 13:50
閱讀 2409·2019-08-30 11:24
閱讀 2283·2019-08-29 15:37
