[發明專利]一種基于裝載因子的緩存數據預加載與替換方法

有效

• 申請號: 201410166680.4
• 申請日: 2014-04-22
• 公開（公告）號: CN103942315B
• 公開（公告）日: 2017-03-22
• 發明（設計）人: 王新根;王新宇
• 申請（專利權）人: 杭州邦盛金融信息技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/0893
• 代理公司: 杭州求是專利事務所有限公司33200
• 代理人: 邱啟旺

技術領域

本發明涉及一種基于海量數據環境的數據緩存方法，尤其涉及一種對海量數據實現快速緩存預加載和替換的方法。

背景技術

隨著企業的全球化及海量數據處理的需求不斷發展，證券、銀行等大型金融企業積累了海量的用戶數據，數據量和用戶數的劇增，給這些企業系統帶來了很大的壓力，高速增長的用戶請求以及海量的后臺數據給Web系統帶來了很多性能問題，導致整個系統響應緩慢，用戶體驗急劇下降。“要么改進系統，要么流失客戶。”正是工業界很多公司不得不面對的問題，如何有效減少用戶訪問延時,提高系統服務質量是一個迫切需要解決的難題。緩存技術被認為是一種有效的解決方案，它能有效緩解Web系統瓶頸、減少網絡數據傳輸以及提升系統的擴展性。

Web緩存技術可以極大的提高系統的響應速度，在近幾年的研究中，提出了很多種緩存方法，它們一般基于數據的一些特性，比如最近訪問時間、訪問次數、數據大小，數據加載成本以及數據修改時間等，通過對這些基礎的數據特征分析采用不同的方法來確定緩存策略，試圖盡量減少各種成本度量，從而提高命中率，減少數據訪問延時和成本。

目前對于緩存技術的研究主要分為緩存預取方法和緩存替換方法兩方面，緩存預取是一種主動式的緩存技術。其基本思想是利用先前用戶訪問的模式和先驗知識，把用戶最有可能訪問的內容預先加載到緩存中。根據預取算法使用的用戶行為特征信息不同，可以分為以下兩類：

一、基于多用戶的行為模式：利用所有或多個用戶的行為模式的特征，不管當前請求的用戶是誰，都預取相同的數據，一個典型的例子是根據流行度緩存排在前10的數據。

二、基于單用戶的行為模式：這種模式基于對單個用戶的行為進行分析，并基于用戶的行為模式進行預測，一個典型的例子是利用馬爾可夫模型(Markov?modeling)，其基本思想是根據用戶的訪問歷史建立一個馬爾可夫圖，并用該圖來預測用戶下一步的行為。

然而傳統的緩存方法要么只是著眼于單個用戶的訪問習慣，基于當前用戶的行為模式進行預測，沒有從全盤考慮緩存性能，或者需要加載所有數據才能判斷哪些數據是需要緩存的，對于海量數據來說，加載所有數據是不可能的。因此傳統的緩存方法并不適合海量數據的應用服務。

發明內容

針對傳統緩存方法存在的問題，本發明提供了一種基于裝載因子的緩存數據預加載與替換方法，實現在海量數據模式下，對數據的快速預加載和替換。裝載因子直觀地說就是在R_i次對數據的讀請求中數據命中緩存的次數。該方法基于數據的整體分布因子來計算各個數據的裝載因子，根據數據的裝載因子來判斷該數據是否應該放在緩存中。因為裝載因子是表示數據命中緩存的次數，因此當裝載因子占比數據讀取次數R_i超過一定閥值的時候，我們就可以認為該數據更適合預先裝載到緩存中，從而在系統初始化的時候采取加載該數據的策略。基于以上描述，給出數據定義如下：

R_i：數據對象i的讀請求數；

P_i：在R_i次讀請求中，數據對象i命中緩存的次數，即裝載因子；

λ：系統的數據分布因子，反應了系統整體的數據分布情況。

基于以上定義，裝載因子的數據預加載和替換方法步驟描述如下：

一、計算系統的數據分布因子λ，λ反應系統整體的數據分布，對于符合一定分布模型的系統，比如泊松分布的數據，λ可以從理論上計算得到，對于無法通過理論計算獲得λ，需要用數據庫統計算法得到；

二、數據預加載，系統啟動的時候，加載數據庫中的數據，并根據系統的數據分布因子計算該數據的裝載因子P_i，根據數據的裝載因子確定該數據是否應該預先加載到緩存中，當的時候，加載該數據到緩存中，否則該數據不預加載；

三、系統預加載后緩存數據采用惰性更新的方式，當用戶訪問某個數據的時候，重新計算該數據的裝載因子，根據新的裝載因子來判斷該數據是放到緩存中還是從緩存中移除；

四、當第三步有新的數據需要裝入緩存而緩存數據已滿的情況，則采用最近最少使用LRU方法替換緩存中的數據。

五、更新數據分布因子λ，當數據量比較少的時候，對于海量數據系統來說，分布因子λ不會有明顯的變化，但當數據累積到一定量后則會影響整個系統的數據分布，為了計算的準確性，需要隔一段時間(比如一天一次)重新計算下分布因子λ。然后再循環采用執行第三步～第五步的步驟，保持緩存中數據的時效性和命中率。

本發明具有如下技術效果：