[發明專利]緩存淘汰方法及系統

有效

• 申請號: 202110576609.3
• 申請日: 2021-05-26
• 公開（公告）號: CN113268440B
• 公開（公告）日: 2022-08-02
• 發明（設計）人: 蔡尚志;王盛
• 申請（專利權）人: 上海嗶哩嗶哩科技有限公司
• 主分類號: G06F12/123
• 分類號: G06F12/123
• 代理公司: 北京英特普羅知識產權代理有限公司 11015
• 代理人: 鄧小玲

本申請公開了一種緩存淘汰方法，該方法包括：設置第一隊列和第二隊列，其中，所述第一隊列用于維護緩存數據及每個所述數據對應的唯一編碼，所述第二隊列用于維護每個所述數據的所述編碼和每秒查詢率；接收所要查詢的數據的所述編碼；根據所述編碼向所述第一隊列發起查詢操作，并在未查詢到所述編碼時更新所述第一隊列和所述第二隊列，對所述第一隊列中的冷數據進行淘汰。本申請還公開了一種緩存淘汰系統、電子裝置和計算機可讀存儲介質。由此，能夠有效辨別隊列中的熱數據集、溫數據集和冷數據集，提高淘汰時的準確性，并且不需要大量的數據訪問就能淘汰歷史訪問記錄的緩存數據。

技術領域

本申請涉及數據處理技術領域，尤其涉及一種緩存淘汰方法、系統、電子裝置及計算機可讀存儲介質。

背景技術

緩存淘汰算法是一種為了充分利用緩存數據的淘汰算法。大部分操作系統為最大化頁面命中率，廣泛采用LRU(Least Recently Used，最近最少使用)淘汰算法。LRU淘汰算法維護一個隊列，Insert(插入)操作會將數據放到隊列頭部，而淘汰則從隊列尾部開始，并且Lookup(查詢)操作得到的Key(數據資源的唯一ID號)也會做更新，將Key轉移到隊列頭部。LRU-K淘汰算法中的中的K代表最近使用次數的閾值，是當該使用次數達到K次才進入LRU隊列中的一種淘汰算法。

當存在熱點數據時，LRU淘汰算法的效率很好，但偶發性的、周期性的批量插入操作會導致命中率急劇下降。而LRU-K淘汰算法雖然可以很好的解決偶發性的、周期性的批量插入操作所帶來的影響，但對K值的調整是繁瑣的過程，若K值太小則效果與LRU淘汰算法相似，太大則適應性差，需要大量的數據訪問才能將歷史訪問記錄(訪問頻次的計數)淘汰掉。另外，由于LRU-K淘汰算法中的K值是一個累加值，意味著不能做到快速適應流量的變化。

需要說明的是，上述內容并不用于限制申請保護范圍。

發明內容

本申請的主要目的在于提出一種緩存淘汰方法、系統、電子裝置及計算機可讀存儲介質，旨在解決如何有效進行緩存數據的淘汰且不需要大量的數據訪問的問題。

為實現上述目的，本申請實施例提供了一種緩存淘汰方法，所述方法包括：

設置第一隊列和第二隊列，其中，所述第一隊列用于維護緩存數據及每個所述數據對應的唯一編碼，所述第二隊列用于維護每個所述數據的所述編碼和每秒查詢率；

接收所要查詢的數據的所述編碼；及

根據所述編碼向所述第一隊列發起查詢操作，并在未查詢到所述編碼時更新所述第一隊列和所述第二隊列，對所述第一隊列中的冷數據進行淘汰。

可選地，所述更新所述第一隊列和所述第二隊列，對所述第一隊列中的冷數據進行淘汰包括：

查看所述編碼是否在所述第二隊列中；

當所述編碼不在所述第二隊列中時，將所述編碼插入所述第二隊列，且將所述編碼對應的當前每秒查詢率CQPS和上一次每秒查詢率PQPS均初始化為0。

可選地，所述更新所述第一隊列和所述第二隊列，對所述第一隊列中的冷數據進行淘汰還包括：

當所述編碼存在所述第二隊列中時，將所述編碼對應的所述PQPS賦值為已記錄的所述CQPS的值，并重新計算新的所述CQPS的值；

根據更新后的所述PQPS和所述CQPS的值判斷是否將所述編碼對應的所述數據保存到所述第一隊列中。

可選地，所述根據更新后的所述PQPS和所述CQPS的值判斷是否將所述編碼對應的所述數據保存到所述第一隊列中包括：

根據所述PQPS和所述CQPS的值以及預設的計算因子Factor計算所述編碼的每秒查詢率KQPS，其中KQPS＝CQPS*Factor+PQPS*(1-Factor)；