一種基於裝載因子的緩存數據預加載與替換方法
2023-10-08 08:32:24 1
一種基於裝載因子的緩存數據預加載與替換方法
【專利摘要】本發明公開了一種基於裝載因子的緩存數據預加載與替換方法，實現在海量數據模式下，對數據的快速預加載和替換。裝載因子直觀地說就是在Ri次對數據的讀請求中數據命中緩存的次數。該方法基於數據的整體分布因子來計算各個數據的裝載因子，根據數據的裝載因子來判斷該數據是否應該放在緩存中。因為裝載因子是表示數據命中緩存的次數，因此當裝載因子佔比數據讀取次數Ri超過一定閥值的時候，我們就可以認為該數據更適合預先裝載到緩存中，從而在系統初始化的時候採取加載該數據的策略。
【專利說明】 一種基於裝載因子的緩存數據預加載與替換方法
【技術領域】
[0001]本發明涉及一種基於海量數據環境的數據緩存方法，尤其涉及一種對海量數據實現快速緩存預加載和替換的方法。
【背景技術】
[0002]隨著企業的全球化及海量數據處理的需求不斷發展，證券、銀行等大型金融企業積累了海量的用戶數據，數據量和用戶數的劇增，給這些企業系統帶來了很大的壓力，高速增長的用戶請求以及海量的後臺數據給Web系統帶來了很多性能問題，導致整個系統響應緩慢，用戶體驗急劇下降。「要麼改進系統，要麼流失客戶。」正是工業界很多公司不得不面對的問題，如何有效減少用戶訪問延時，提高系統服務質量是一個迫切需要解決的難題。緩存技術被認為是一種有效的解決方案，它能有效緩解Web系統瓶頸、減少網絡數據傳輸以及提升系統的擴展性。
[0003]Web緩存技術可以極大的提高系統的響應速度，在近幾年的研究中，提出了很多種緩存方法，它們一般基於數據的一些特性，比如最近訪問時間、訪問次數、數據大小，數據加載成本以及數據修改時間等，通過對這些基礎的數據特徵分析採用不同的方法來確定緩存策略,試圖儘量減少各種成本度量,從而提高命中率,減少數據訪問延時和成本。
[0004]目前對於緩存技術的研究主要分為緩存預取方法和緩存替換方法兩方面，緩存預取是一種主動式的緩存技術。其基本思想是利用先前用戶訪問的模式和先驗知識，把用戶最有可能訪問的內容預先加載到緩存中。根據預取算法使用的用戶行為特徵信息不同，可以分為以下兩類:
[0005]一、基於多用戶的行為模式:利用所有或多個用戶的行為模式的特徵，不管當前請求的用戶是誰，都預取相同的數據，一個典型的例子是根據流行度緩存排在前10的數據。
[0006]二、基於單用戶的行為模式:這種模式基於對單個用戶的行為進行分析，並基於用戶的行為模式進行預測，一個典型的例子是利用馬爾可夫模型(Markov modeling)，其基本思想是根據用戶的訪問歷史建立一個馬爾可夫圖，並用該圖來預測用戶下一步的行為。
[0007]然而傳統的緩存方法要麼只是著眼於單個用戶的訪問習慣，基於當前用戶的行為模式進行預測，沒有從全盤考慮緩存性能，或者需要加載所有數據才能判斷哪些數據是需要緩存的，對於海量數據來說，加載所有數據是不可能的。因此傳統的緩存方法並不適合海量數據的應用服務。
【發明內容】
[0008]針對傳統緩存方法存在的問題，本發明提供了一種基於裝載因子的緩存數據預加載與替換方法，實現在海量數據模式下，對數據的快速預加載和替換。裝載因子直觀地說就是在Ri次對數據的讀請求中數據命中緩存的次數。該方法基於數據的整體分布因子來計算各個數據的裝載因子，根據數據的裝載因子來判斷該數據是否應該放在緩存中。因為裝載因子是表示數據命中緩存的次數，因此當裝載因子佔比數據讀取次數Ri超過一定閥值的時候，我們就可以認為該數據更適合預先裝載到緩存中，從而在系統初始化的時候採取加載該數據的策略。基於以上描述，給出數據定義如下:
[0009]R1:數據對象i的讀請求數；
[0010]P1:在Ri次讀請求中，數據對象i命中緩存的次數，即裝載因子；
[0011]λ:系統的數據分布因子，反應了系統整體的數據分布情況。
[0012]基於以上定義，裝載因子的數據預加載和替換方法步驟描述如下:
[0013]一、計算系統的數據分布因子λ，λ反應系統整體的數據分布，對於符合一定分布模型的系統，比如泊松分布的數據，λ可以從理論上計算得到，對於無法通過理論計算獲得λ，需要用資料庫統計算法得到；
[0014]二、數據預加載，系統啟動的時候，加載資料庫中的數據，並根據系統的數據分布因子計算該數據的裝載因子Pi,根據數據的裝載因子確定該數據是否應該預先加載到緩存
中，當I的時候，加載該數據到緩存中，否則該數據不預加載；
[0015]三、系統預加載後緩存數據採用惰性更新的方式，當用戶訪問某個數據的時候，重新計算該數據的裝載因子，根據新的裝載因子來判斷該數據是放到緩存中還是從緩存中移除；
[0016]四、當第三步有新的數據需要裝入緩存而緩存數據已滿的情況，則採用最近最少使用LRU方法替換緩存中的數據。
[0017]五、更新數據分布因子λ，當數據量比較少的時候，對於海量數據系統來說，分布因子λ不會有明顯的變化，但當數據累積到一定量後則會影響整個系統的數據分布，為了計算的準確性，需要隔一段時間(比如一天一次)重新計算下分布因子λ。然後再循環採用執行第三步~第五步的步驟，保持緩存中數據的時效性和命中率。
[0018]本發明具有如下技術效果:
[0019]1、本發明通過數據裝載因子可以直接通過計算對數據做出是否緩存的判斷，而無須等遍歷整個數據後再做出是否緩存的策略，從而使整個緩存系統在系統啟動的時候就有很高的命中率。
[0020]2、本發明採用惰性更新的方式，系統運行過程中緩存替換的開銷很小。
[0021]3、在系統的緩存達到動態平衡後，該方法也比傳統的緩存替換方法命中率要高，該方法會優先緩存「熱點」數據。
[0022]4、本發明更適用於海量的數據系統，在海量數據系統中，很多傳統的方法無法做出緩存決策，因為它們無法加載比對所有的數據。
【具體實施方式】
[0023]數據定義:
[0024]R1:數據對象i的讀請求數，
[0025]S1:數據對象i的緩存大小，
[0026]MT1:數據對象i從緩存中讀取的時延，
[0027]DT1:數據對象i未緩存的讀取時延，
[0028]λ:數據的分布特徵，[0029]Μ:總的可用緩存的大小，
[0030]η:總的數據個數。
[0031]則上述方法過程中的各參數計算公式如下:
【權利要求】
1.一種基於裝載因子對緩存數據進行預加載和替換的方法，其特徵在於，包括如下步驟: (1)計算系統的數據的分布情況，對於符合一定分布模型的系統，可以使用統計模型計算得到分布情況，對於無法找到合適的分布模型的數據，則通過使用資料庫統計算法得到； (2)在系統啟動時，根據數據的分布情況，計算需要加載的數據的裝載因子，一旦裝載因子(即緩存命中次數)佔數據訪問次數比例超過閥值，則將其加載到緩存，否則不預加載； (3)系統運行過程中採用惰性更新方法，當用戶訪問某個數據時，重新計算該數據的裝載因子，根據新的裝載因子決定是否需要將數據放到緩存中或是否需要從緩存中移除； (4)在第三步中有新的數據需要更新時，替換緩存中的數據； (5)對於數據量較少的系統不更新分布因子，但是在數據量增長後隔一定間隔更新一次裝載因子之後循環採用第三到第五步的策略，保持緩存中數據的時效性和命中率。
【文檔編號】G06F17/30GK103942315SQ201410166680
【公開日】2014年7月23日 申請日期:2014年4月22日 優先權日:2014年4月22日
【發明者】王新根, 王新宇 申請人:杭州邦盛金融信息技術有限公司