YB161102-BB  DSQC 113

 目前提出的算法可以分為以下三類（第一類是重點要掌握的）：
 
（1）傳統替換算法及其直接演化，其代表算法有 ：①LRU（ Least Recently Used）算法：將最近最少使用的內容替換出Cache ；②LFU（ Lease Frequently Used）算法：將訪問次數最少的內容替換出Cache；③如果Cache中所有內容都是同一天被緩存的，則將最大的文檔替換出Cache，否則按LRU算法進行替換 。④FIFO( First In First Out)：遵循先入先出原則，若當前Cache被填滿，則替換最早進入Cache的那個。
 
（2）基于緩存內容關鍵特征的替換算法，其代表算法有：①Size替換算法：將最大的內容替換出Cache②LRU— MIN替換算法：該算法力圖使被替換的文檔個數最少。設待緩存文檔的大小為S，對Cache中緩存的大小至少是S的文檔，根據LRU算法進行替換；如果沒有大小至少為S的對象，則從大小至少為S/2的文檔中按照LRU算法進行替換；③LRU—Threshold替換算法：和LRU算法一致，只是大小超過一定閾值的文檔不能被緩存；④Lowest Lacency First替換算法：將訪問延遲最小的文檔替換出Cache。
 
（3）基于代價的替換算法，該類算法使用一個代價函數對Cache中的對象進行評估，最后根據代價值的大小決定替換對象。其代表算法有：①Hybrid算法：算法對Cache中的每一個對象賦予一個效用函數，將效用最小的對象替換出Cache；②Lowest Relative Value算法：將效用值最低的對象替換出Cache；③Least Normalized Cost Replacement（LCNR）算法：該算法使用一個關于文檔訪問頻次、傳輸時間和大小的推理函數來確定替換文檔；④Bolot等人 提出了一種基于文檔傳輸時間代價、大小、和上次訪問時間的權重推理函數來確定文檔替換；⑤Size—Adjust LRU（SLRU）算法：對緩存的對象按代價與大小的比率進行排序，并選取比率最小的對象進行替換。