首頁 後端開發 php教程 程式設計技術快取寫法(三)

程式設計技術快取寫法(三)

Nov 30, 2016 am 09:27 AM

上次我們說了多層緩存,本章詳細介紹下記憶體緩存該如何設計。

一:分析設計

假設有個項目有一定並發量,要用到多級緩存,如下:

程式設計技術快取寫法(三)

在實際設計一個內存緩存前,我們需要考慮的問題:

1:內存與Redis的資料置換,盡可能在記憶體中提高資料命中率,減少下一級的壓力。

2:記憶體容量的限制,需要控制快取數量。

3:熱點資料更新不同,需要可設定單一key過期時間。

4:良好的快取過期刪除策略。

5:快取資料結構的複雜度盡可能的低。

關於置換及命中率:我們採用LRU演算法,因為它實作簡單,快取key命中率也很好。

LRU即是:把最近最少存取的資料給淘汰掉,經常被存取到即是熱點資料。

關於LRU資料結構:因為key優先權提升和key淘汰,所以需要順序結構。我看到大多實現,都採用鍊錶結構、

即:新資料插入到鍊錶頭部、被命中時的資料移動到頭部。 加入複雜度O(1) 移動和取得複雜度O(N)。

有沒複雜度更低的呢? 有Dictionary,複雜度為O(1),效能最好。 那如何保證快取的優先權提升呢?

二:O(1)LRU實作

我們定義個LRUCache類,建構參數maxKeySize 來控制快取最大數量。

使用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的实现。


本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

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

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

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

熱門話題

Java教學
1657
14
CakePHP 教程
1415
52
Laravel 教程
1309
25
PHP教程
1257
29
C# 教程
1230
24
使用正規表示式去除 PHP 數組中的重複值 使用正規表示式去除 PHP 數組中的重複值 Apr 26, 2024 pm 04:33 PM

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

程式設計是乾啥的,學了有什麼用 程式設計是乾啥的,學了有什麼用 Apr 28, 2024 pm 01:34 PM

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

釋放你內心的程式設計師:C 絕對初學者 釋放你內心的程式設計師:C 絕對初學者 Oct 11, 2024 pm 03:50 PM

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

使用 Python 解決問題:作為初學者,解鎖強大的解決方案 使用 Python 解決問題:作為初學者,解鎖強大的解決方案 Oct 11, 2024 pm 08:58 PM

Python 讓初學者能夠解決問題。

使用 Golang 建立基於瀏覽器的應用程式 使用 Golang 建立基於瀏覽器的應用程式 Apr 08, 2024 am 09:24 AM

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

透過 Go Get 快速方便地取得 Go 模組 透過 Go Get 快速方便地取得 Go 模組 Apr 07, 2024 pm 09:48 PM

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

C++ 程式設計謎題片段:激發思維,提升程式設計水平 C++ 程式設計謎題片段:激發思維,提升程式設計水平 Jun 01, 2024 pm 10:26 PM

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

編碼的關鍵:為初學者釋放 Python 的力量 編碼的關鍵:為初學者釋放 Python 的力量 Oct 11, 2024 pm 12:17 PM

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

See all articles