java-blog

一．關于搜索引擎用戶查詢得出的結(jié)論：
（1）      用戶查詢有很大比例的重復性。有30％到40％的用戶查詢是重復查詢。
（2）       大多數(shù)重復的用戶查詢會在較短的間隔時間被再次重復訪問。
（3）       大多數(shù)用戶的查詢是短查詢，大約包含2－5個單詞。
（4）       用戶一般只查看返回結(jié)果的前三個頁面（前30個返回結(jié)果）。58％用戶只查看第一個頁面（TOP 10）,15%用戶查看第二個頁面，不超過12％的用戶會查看第三個頁面以后的檢索結(jié)果。
（5）       關于用戶查詢差異程度。有比較大的查詢程度，一百萬個用戶查詢中大約63.7%的用戶查詢只出現(xiàn)過一次。另外一方面，集中的重復查詢也非常集中：25個高頻查詢大約占總查詢的1.23%-1.5%.

二．CACHE的基本策略
（1）       LRU:最近最少使用策略
基本假設：最近很少被重復訪問的緩存記錄在最近的將來也不會被訪問。這是最簡單的一種CACHE策略。將用戶查詢按照最近使用時間進行排序，淘汰策略將最老的查詢淘汰出CACHE。

（2）       FBR:不僅考慮時間也考慮引用計數(shù)的問題。
FBR在LRU策略的基礎上將CACHE分為三個不同的部分：NEW,OLD,MIDDLE
NEW:存儲最近被訪問過的記錄；
OLD：存儲最近最少使用的一批記錄；
MIDDLE:存儲介于NEW和OLD之間的一批記錄；
引用計數(shù)的時候不考慮NEW區(qū)域的記錄，只考慮OLD和MIDDLE兩個區(qū)域的記錄引用計數(shù)增加，在替換記錄的時候從OLD區(qū)域選擇引用計數(shù)最少的那個記錄進行替換。

（3）       LRU/2：對于LRU的改進，計算第二次到最后一次被訪問總的LRU，將老的記錄淘汰。

（4）       SLRU:
CACHE被分為兩個部分：非保護區(qū)域和保護區(qū)域。每個區(qū)域的記錄都按照最近使用頻度由高到低排序，高端叫做MRU，低端叫做LRU。如果某個查詢沒有在CACHE找到，那么將這個查詢放入非保護區(qū)域的MRU端；如果某個查詢在CACHE命中，則把這個查詢記錄放到保護區(qū)的MRU端；如果保護區(qū)已滿，則把記錄從保護區(qū)放入非保護區(qū)的MRU，這樣保護區(qū)的記錄最少要被訪問兩次。淘汰的機制是將非保護區(qū)的LRU淘汰。

（5）       LandLord策略
將一個記錄增加到CACHE的時候，給予這個記錄一個值（DEADLINE）,如果需要淘汰記錄的時候，選擇CACHE里面DEADLINE最小的那個淘汰，同時將CACHE里面其它所有記錄減去這個被淘汰的記錄的DEADLINE值，如果一個記錄被命中，則將這個記錄的DEADLINE放大到一定值。

（6）       TSLRU：Topic based SLRU:與SLRU策略相同，不過不是按照查詢調(diào)整替換策略，而是按照查詢所屬主題進行調(diào)整。

（7）       TLRU: Topic based LRU
基本策略和LRU相同，區(qū)別在于保留查詢的主題（TOPIC）信息，對于某個查詢來說，不僅該主題的檢索結(jié)果進入CACHE，而且原先在CACHE里面的相同主題的查詢及其結(jié)果也調(diào)整時間，更新為最新進入CACHE。可以看作是主題LRU，而LRU是查詢LRU。

（8）       PDC (probability driven cache)：針對用戶的瀏覽行為建立概率模型，然后調(diào)整CACHE里面的記錄優(yōu)先級別，針對某個查詢，將用戶瀏覽數(shù)目比較多的文檔在CACHE里面的級別提高。

（9）       預取策略
         所謂預取，就是系統(tǒng)預測用戶在很短時間內(nèi)的行為，然后將該行為涉及到的數(shù)據(jù)預先存儲在CACHE里面。存在不同的預取策略，比如預取策略：因為一般用戶在查看完第一頁檢索結(jié)果后會翻看第二頁結(jié)果，所以將該用戶查詢的第二頁結(jié)果首先預取到CACHE里面，這樣可以減少存取時間。

（10）   二級CACHE
有兩級CACHE，一級是查詢結(jié)果CACHE，保留了原始查詢以及相關文件；第二級CACHE是倒排文檔列表CACHE，也就是查詢中某個單詞在索引中的倒排列表信息，這個CACHE主要減少了磁盤I/O時間。替換策略采取LRU，結(jié)果證明該方法提高30％的性能。

（11）   三級CACHE
是對二級CACHE的一種改進策略，除了二級CACHE里面保留的兩個CACHE，另外增加一個CACHE，這個CACHE記錄了兩個單詞查詢的倒排文檔交集記錄，這樣一個是省去了磁盤I/O時間，另外一個減少了計算交集的操作，有效的減少了計算量。

三．CACHE方法性能分析與比較
（1）       LRU適合存儲比較小的記錄效果才好。
（2）       中等大小的CACHE能夠滿足很大一部分重復用戶查詢。（大約20％的查詢能夠在中等大小CACHE找到）
（3）       將時間因素和命中次數(shù)結(jié)合起來的緩存策略好于只考慮時間因素的策略。實驗表明FBR/LRU2/SLUR性能總是好于LRU策略。
（4）       對于小CACHE來說，靜態(tài)CACHE策略要好于動態(tài)CACHE策略，命中率要高些。
（5）       對于LRU來說，大CACHE的重復命中率大約占30％。
（6）       對于大CACHE來說，TLRU略微好于LRU，但是差別不太大。對于小CACHE，結(jié)論正好相反。
（7）       隨著CACHE逐步增大，命中率逐漸增加，對于SLRU來說，其性能跟兩個分區(qū)劃分大小無關。
（8）       PDC的命中率高于LRU變形算法，大約有53％命中率，不過計算復雜度高。