java-blog

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

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

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

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

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

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

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

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

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

（9）       預(yù)取策略
         所謂預(yù)取，就是系統(tǒng)預(yù)測用戶在很短時(shí)間內(nèi)的行為，然后將該行為涉及到的數(shù)據(jù)預(yù)先存儲(chǔ)在CACHE里面。存在不同的預(yù)取策略，比如預(yù)取策略：因?yàn)橐话阌脩粼诓榭赐甑谝豁摍z索結(jié)果后會(huì)翻看第二頁結(jié)果，所以將該用戶查詢的第二頁結(jié)果首先預(yù)取到CACHE里面，這樣可以減少存取時(shí)間。

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

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

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