程式設計技術快取寫法(三)
上次我們說了多層緩存,本章詳細介紹下記憶體緩存該如何設計。
一:分析設計
假設有個項目有一定並發量,要用到多級緩存,如下:
在實際設計一個內存緩存前,我們需要考慮的問題:
1:內存與Redis的資料置換,盡可能在記憶體中提高資料命中率,減少下一級的壓力。
2:記憶體容量的限制,需要控制快取數量。
3:熱點資料更新不同,需要可設定單一key過期時間。
4:良好的快取過期刪除策略。
5:快取資料結構的複雜度盡可能的低。
關於置換及命中率:我們採用LRU演算法,因為它實作簡單,快取key命中率也很好。
LRU即是:把最近最少存取的資料給淘汰掉,經常被存取到即是熱點資料。
關於LRU資料結構:因為key優先權提升和key淘汰,所以需要順序結構。我看到大多實現,都採用鍊錶結構、
即:新資料插入到鍊錶頭部、被命中時的資料移動到頭部。 加入複雜度O(1) 移動和取得複雜度O(N)。
有沒複雜度更低的呢? 有Dictionary,複雜度為O(1),效能最好。 那如何保證快取的優先權提升呢?
二:O(1)LRU實作
我們定義個LRUCache
使用ConcurrentDictionary來作為我們的快取容器,並且可以確保線程安全。
public class LRUCache<TValue> : IEnumerable<KeyValuePair<string, TValue>> { private long ageToDiscard = 0; //淘汰的年龄起点 private long currentAge = 0; //当前缓存最新年龄 private int maxSize = 0; //缓存最大容量 private readonly ConcurrentDictionary<string, TrackValue> cache; public LRUCache(int maxKeySize) { cache = new ConcurrentDictionary<string, TrackValue>(); maxSize = maxKeySize; } }
上面定義了 ageToDiscard、currentAge 這2個自加值參數,作用是:標記快取清單中各個key的新舊程度。
核心實作步驟如下:
1:每次加入key時,currentAge自增並將currentAge值分配給這個快取值的Age,currentAge始終增加。
public void Add(string key, TValue value) { Adjust(key); var result = new TrackValue(this, value); cache.AddOrUpdate(key, result, (k, o) => result); } public class TrackValue { public readonly TValue Value; public long Age; public TrackValue(LRUCache<TValue> lv, TValue tv) { Age = Interlocked.Increment(ref lv.currentAge); Value = tv; } }
2:在添加時,如超過最大數量。檢查字典裡是否有ageToDiscard年齡的key,如沒有循環自增檢查,有則刪除、添加成功。
ageToDiscard+maxSize= currentAge ,這樣設計就能在O(1)下保證可以淘汰舊數據,而不是使用鍊錶移動。
public void Adjust(string key) { while (cache.Count >= maxSize) { long ageToDelete = Interlocked.Increment(ref ageToDiscard); var toDiscard = cache.FirstOrDefault(p => p.Value.Age == ageToDelete); if (toDiscard.Key == null) continue; TrackValue old; cache.TryRemove(toDiscard.Key, out old); } }
過期刪除策略
大多數情況下,LRU演算法對熱點資料命中率是很高的。 但如果突然大量的偶發性數據訪問,會讓記憶體存放大量冷數據,也就是快取污染。
會造成LRU無法命中熱點數據,導致快取系統命中率急遽下降。也可以使用LRU-K、2Q、MQ等變種演算法來提高命中率。
過期配置
1:我們透過設定、最大過期時間來盡量避免冷資料常駐記憶體。
2:大多數情況每個快取的時間要求不一致的,所以在增加單一key的過期時間。
private TimeSpan maxTime; public LRUCache(int maxKeySize,TimeSpan maxExpireTime){} //TrackValue增加创建时间和过期时间 public readonly DateTime CreateTime; public readonly TimeSpan ExpireTime;
刪除策略
1:關於key過期刪除,最好使用定時刪除了。 這樣可以最快釋放被佔用的內存,但很明顯,大量的定時器對CPU吃不消的。
2:所以我们采用惰性删除、在获取key的时检查是否过期,过期直接删除。
public Tuple<TrackValue, bool> CheckExpire(string key) { TrackValue result; if (cache.TryGetValue(key, out result)) { var age = DateTime.Now.Subtract(result.CreateTime); if (age >= maxTime || age >= result.ExpireTime) { TrackValue old; cache.TryRemove(key, out old); return Tuple.Create(default(TrackValue), false); } } return Tuple.Create(result, true); }
3:惰性删除虽然性能最好,对于冷数据来说,还是没解决缓存污染问题。 所以我们还需定期清理。
比如:开个线程,5分钟去遍历检查key一次。这个策略根据实际场景可配置。
public void Inspection() { foreach (var item in this) { CheckExpire(item.Key); } }
惰性删除+定期删除基本能满足我们需求了。
总结
如果继续完善下去,就是内存数据库的雏形,类似redis。
比如:增加删除key的通知,增加更多数据类型。 本篇也是参考了redis、Orleans的实现。

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

使用正規表示式從PHP數組中移除重複值的方法:使用正規表示式/(.*)(.+)/i匹配並取代重複項。遍歷數組元素,使用preg_match檢查匹配情況。如果匹配,請跳過值;否則,將其添加到無重複值的新數組中。

1、程式設計可用於開發各種軟體和應用程序,包括網站、手機應用程式、遊戲和數據分析工具等。它的應用領域非常廣泛,幾乎涵蓋了所有行業,包括科學研究、醫療保健、金融、教育、娛樂等。 2.學習程式設計可以幫助我們提升問題解決能力和邏輯思考能力。在程式設計過程中,我們需要分析和理解問題,找出解決方案,並將其轉換為程式碼。這種思維方式能夠培養我們的分析和抽象能力,提升我們解決實際問題的能力。

C語言是初學者學習程式設計的理想選擇,其優點包括效率、多功能性和可移植性。學習C語言需要:安裝C編譯器(如MinGW或Cygwin)了解變數、資料型別、條件語句和迴圈語句編寫包含主函數和printf()函數的第一個程式透過實戰案例(如計算平均數)練習C語言知識

使用Golang建立基於瀏覽器的應用程式Golang結合JavaScript建構了動態的前端體驗。安裝Golang:造訪https://golang.org/doc/install。設定Golang專案:建立一個名為main.go的檔案。使用GorillaWebToolkit:新增GorillaWebToolkit程式碼以處理HTTP請求。建立HTML模板:在templates子目錄中建立index.html,這是主模板。

透過GoGet,可以快速且方便地取得Go模組,步驟如下:在終端機中執行:goget[module-path],其中module-path為模組路徑。 GoGet會自動下載模組及其相依性。安裝的位置由GOPATH環境變數指定。

C++程式設計謎題涵蓋斐波那契數列、階乘、漢明距離、陣列最大值和最小值等演算法和資料結構概念,透過解決這些謎題,可以鞏固C++知識,提升演算法理解和程式設計技巧。

Python透過其易學性和強大功能,是初學者的理想程式設計入門語言。其基礎包括:變數:用於儲存資料(數字、字串、列表等)。資料型態:定義變數中資料的型態(整數、浮點數等)。運算符:用於數學運算和比較。控制流程:控製程式碼執行流程(條件語句、迴圈)。
