目 錄 - 1 - 摘 要 . 2 第一章 背景介紹 . 3 維網(wǎng)和海量信息 . 3 索引擎概述 . 4 述 . 5 第二章 相關(guān)研究 . 6 換算法 . 6 搜索引擎中的應(yīng) 用 . 8 第三章 一種 通用 設(shè)計和實現(xiàn) . 9 用 設(shè)計目標(biāo) . 9 用性目標(biāo) . 9 效性要求 . 10 評測目標(biāo) . 10 用 設(shè)計 . 10 控器 . 11 次控制器 . 12 據(jù)存儲器 . 13 層 計的優(yōu)點 . 13 第四章 通用 搜索引擎檢索端應(yīng)用 . 15 驗環(huán)境 . 15 戶查詢?nèi)罩镜姆治?. 16 詢的總體分布 . 16 詢的時間局部性性質(zhì) . 18 戶查詢結(jié)果翻頁的考察 . 19 用 用結(jié)構(gòu)和配置 . 21 體結(jié)構(gòu) . 21 存配置 . 23 間分析 . 25 第五章 總結(jié)和進一步工作 . 28 參考文獻 . 29 致 謝 . 31 摘 要 - 2 - 摘 要 在處理 量信息的過程中，有兩個問題制約著性能的提高。一方面，由于信息量非常大，只能把所有數(shù)據(jù)存放在磁盤等相對慢速的設(shè)備上， 或者放在多臺不同的機器上 。 對于數(shù)據(jù)的讀取和保存只能從這些 慢速 設(shè)備或者 分布式的 機器上 獲得。另一方面，信息量的龐大也造成了 大量的計算，消耗大量計算時間 。 在很多 應(yīng)用中，存在著 引用 的局部性規(guī)律 ，即大量的操作需要訪問少量的數(shù)據(jù)。 本文工作包括： 1) 本文設(shè)計了一種通用的 緩存 (構(gòu) 。 其 主要 特點是通用性 ， 在各種應(yīng)用中 ，用戶可以自由地對該 容量，替換算法，數(shù)據(jù)項結(jié)構(gòu)，預(yù)取策略，體系結(jié)構(gòu)進行配置 。 同時 提供一個 模擬接口，用戶可以通過這個接口執(zhí)行模擬操作 ，對算法、容量進行評估 。 2) 分析 天網(wǎng) 用戶 查詢?nèi)罩荆l(fā)現(xiàn) 對于 用戶的查詢 ，無論是否考慮翻頁的情況，都 滿足類 布 ，這樣的具有比較強的局部性的分布形式 ， 提示我們?nèi)绻捎?構(gòu) 可以帶來很大的好處 。 3) 在 天網(wǎng) 搜索引擎中檢索模塊中加入這 種通用 塊 。 通過 選取適當(dāng)?shù)?小，替換算法，預(yù)取策略和層次結(jié)構(gòu)， 進一步提高搜 索引擎檢索端的性能 。 關(guān)鍵詞 ： 海量信息 緩存 技術(shù) 分布特征 搜索引擎 第一章 背景介紹 - 3 - 第一章 背景介紹 維網(wǎng) 和海量信息 萬維網(wǎng)（ 因特網(wǎng)（ 成功的應(yīng)用之一。 因特網(wǎng) 的前身是美國國防部高級研究計劃署的研究試驗性網(wǎng) 1983年 P 成為 議。 此后， 器和用戶快速增長。 1988年 的規(guī)模以指數(shù)增長，很多地區(qū)網(wǎng)絡(luò)開始加入，并且開始與加拿大、歐洲和太 平洋地區(qū)的網(wǎng)絡(luò)連接。 從而 萬維網(wǎng)起源于 1989年的歐洲粒子物理研究室（ 1989年 3月，由物理學(xué)家 1990年 9月，第一個文本原型正式運行。此后，許多的大專院校和業(yè)界公司紛紛加入到萬維網(wǎng)的研究中來，開發(fā)大量的基于萬維網(wǎng)的應(yīng)用程序。 在九十年代這短短幾年 時間 里，萬維網(wǎng)吸引了的大量的用戶和開發(fā)者，使得它不斷地完善和發(fā)展。 萬維網(wǎng)是一個分布式的信息系統(tǒng)，它由超文本 (超媒體 (成。 超文本一般由 文本信息和鏈接信息 組成 ，文本信息是供人們?yōu)g覽閱讀的，鏈接信息 又稱為超鏈接 (它們 是指向別的超文本信息的指針 ，可以指向萬維網(wǎng)上一個位置 。超媒體是超文本的擴展，包括在萬維網(wǎng)上的各種資源，包括視頻，音頻，圖像 等等。 在這樣一個系統(tǒng)中， 一方面， 用戶可以通過超鏈接的指引，非常容易地獲取分布在不同機器上的信息。 另一方面，各種不同地區(qū)，職業(yè) 的人們可以自由地把本地的信息放到這個系統(tǒng)中去。這樣，這個系統(tǒng)就成為一個全球區(qū)域的，包括大量信息的系統(tǒng)。根據(jù) 至到 2002年 4月，全球的網(wǎng)頁數(shù)已經(jīng)超過 20億 在中國，萬維網(wǎng)也以驚人的速度發(fā)展。萬維網(wǎng)于 1994年正式在中國建立， 2003年中國互聯(lián)網(wǎng)絡(luò)信息資源數(shù)量調(diào)查報告 顯示 ，截至 2003年底，中國的網(wǎng)頁總數(shù)已經(jīng)超過 3億，總字節(jié)數(shù)超過了 6T，總網(wǎng)站數(shù)達(dá)到 背景介紹 - 4 - 萬，網(wǎng)民數(shù)近 8000萬 這樣龐大的一個萬維網(wǎng)的規(guī)模，包含的信息是海量的。按照萬維網(wǎng)的這種發(fā)展速度，海量信息也是爆炸式的 增長的。 而 人工在如此大規(guī)模的信息中尋找有效信息是很困難的，低效 的。 我們需要采用一種方法 ，獲取這些海量信息并對它們進行一定程度的加工 ， 從而幫助人們 更 好 地 利 用 這 些 信 息 。 其 中 的 一 種 方 法 就 是 信 息 檢 索 的 方 法（ 稱 它的過程是這樣的：用戶給出一個查詢的請求（通常是 一組 關(guān)鍵字 或者一些問題 ），信息檢索系統(tǒng)給出系統(tǒng)中與該 查詢相關(guān)的結(jié)果。從而用戶就可以方便的從獲得的結(jié)果中提取有用的 信息。 索引擎概述 搜索引擎是信息檢索在萬維網(wǎng)上一種很好的應(yīng)用 。它的基本功能是：用戶給出查詢，搜索引擎返回給用戶和查詢相關(guān)的萬維網(wǎng)上的信息。由于在很多情況下，相關(guān)信息結(jié)果是大量的，因此系統(tǒng)需要對這些結(jié)果進行查詢相關(guān)性排序， 把更加相關(guān)更加有用的信息放在前面，便于用戶的瀏覽，最后返回 排序后的結(jié)果 。用戶可以通過搜索引擎，很容易地獲取他們所需要的萬維網(wǎng)上的信息，大大提高了利用信息的效率。 最早的萬維網(wǎng)的搜索引擎叫做 1994， 它建于 1994年， 當(dāng)時它只有 收集了 110000的網(wǎng)頁，每天對于它的查詢在 1500個左右。在以后的 10年里，搜索引擎有了大規(guī)模的發(fā)展， 截至 2003年底， 的網(wǎng)頁數(shù)已經(jīng)超 過了 40億 天 網(wǎng) 搜 索引 擎 天網(wǎng) 是 針對 中國 萬 維 網(wǎng) 上 豐 富 的信 息 資 源 而 開發(fā)的具有中文特色的搜索引 擎。本文的工作，就是在天網(wǎng)搜索引擎的基礎(chǔ)上完成 的。 搜索引擎的工作流程基本包括三個步驟： 1、 頁 的搜集：它的基本原理是先設(shè)定一個初始的 合 S，對于集合中的 每個 集器下載對應(yīng)的網(wǎng)頁，從 S 中刪除這個 描這個網(wǎng)頁，把這個網(wǎng)頁 向外 的鏈接中沒有被下載過的第一章 背景介紹 - 5 - 到 S 中，如此的循環(huán)操作，直至 S 集合為空。通過這一過程，我們獲取了 從初始 集合 S 出發(fā)的所有可達(dá)網(wǎng)頁。 2、 對 頁建立索引庫： 建立索引的目的是加快查詢的 速度。通常的是采取倒排表的技術(shù)，即對于每一個關(guān)鍵詞，建立這個關(guān)鍵詞出現(xiàn)的文檔號和位置號的列表。在檢索的時候，用戶輸入的關(guān)鍵詞就可以快速對應(yīng)到倒排文件的某一個關(guān)鍵詞 ，從而獲得結(jié)果 。 3、 檢索查詢：用戶輸入一系列關(guān)鍵詞，程序在倒排表中找到相應(yīng)的項，進行相關(guān)的運算 ，獲得結(jié)果的集合。然后根據(jù)網(wǎng)頁的重要程度以及網(wǎng)頁和查詢的相關(guān)程度 進行評測，給出結(jié)果的排序，然后根據(jù)這個排序返回給用戶結(jié)果頁面。 述 高速緩沖存儲器（ 在單機的物理結(jié)構(gòu)上，是處于 主存之間 的一種 存儲器，它的大小一般很小， 只有幾十到幾百 K， 存取速度在主存和 存器之間， 考慮到計算機在使用的過程中對數(shù)據(jù)塊的存取有很強的時間局部性和空間局部性，因此我們采用它來暫存常用的數(shù)據(jù)塊，以縮短存取的時間。 我們這里的 是一種和物理 想類似 的邏輯結(jié)構(gòu)，它的物理媒介是主存。在很多應(yīng)用程序中，對數(shù)據(jù)的使用有很強的局部性的特征。這里的數(shù)據(jù)包括：存儲在磁盤，磁帶等慢速設(shè)備上的數(shù)據(jù)；存在分布式系統(tǒng) 上的數(shù)據(jù)；需要經(jīng)過復(fù)雜操作和運算才能獲得的數(shù)據(jù)。 這些數(shù)據(jù)的一個共同特點是： 獲得這些數(shù)據(jù)都需要花費很長的時間，對于磁盤、磁帶上的數(shù)據(jù)， 需要很長的尋道時間 ； 對于其他機器上的數(shù)據(jù)，需要較長的網(wǎng)絡(luò)傳輸?shù)臅r間 ；對于復(fù)雜操作獲得數(shù)據(jù)，需要較長的 算時間?？紤]到如果這些應(yīng)用有一些局部性的規(guī)律，那么我們可以把 這些數(shù)據(jù)中可能 會比較常用 到 的保存在 以后的使用中，就可以避免上述的代價較大的三種操作。 可以有一定的替換策略，決定在一定的時候添加哪些內(nèi)容，替換出哪些內(nèi)容，這些操作使得內(nèi)存中存儲的總是最可能在近期被訪問到的。 第二章 相關(guān)研究 - 6 - 第二章 相關(guān)研究 換算法 為動態(tài)和靜態(tài)兩 種：靜態(tài)的 指在應(yīng)用程序真正使用數(shù)據(jù)之前，把一些數(shù)據(jù)填充到 ，當(dāng)真正需要使用 這些數(shù)據(jù) 的時候，就從 獲得，這些事先填充到 的數(shù)據(jù)是被預(yù)測會在以后的階段中 會 被頻繁使用的 。 動態(tài)的 指 ，在真正使用數(shù)據(jù)之前， 以是空的或者是滿的，但是在使用的過程中，當(dāng)某個數(shù)據(jù)被訪問，而它又滿足一定條件的時候，這個數(shù)據(jù)可以被加到 來。這里會產(chǎn)生的一個問題就是，當(dāng) 經(jīng)滿了，但是又需要有新的數(shù)據(jù)添加到 來的時候，我們需要替換掉一個或者一些 舊的數(shù)據(jù)（考慮數(shù)據(jù)不定長的情況），這時候我們丟棄哪些數(shù)據(jù)才是最合適的？ 在 想提出的幾十年來，提出了大量不同的替換算法，我們就描述一下這些替換算法。 者 稱為 0靜態(tài)的 是在開始 時填充 真正使用的時候，所有的未命中的數(shù)據(jù)都不允許加入就是沒有數(shù)據(jù)項被替換。 老的先進先出算法。當(dāng)某數(shù)據(jù)在 不存在，就采用其他方式（讀取或者計算）獲得該數(shù)據(jù)，然后把該數(shù)據(jù)加入到 需要替換的時候，先進入的數(shù)據(jù)先被丟棄 ，而不用考 慮數(shù)據(jù)的被使用的情況 。 算法選擇 最長時間沒 有被引用的數(shù)據(jù)丟棄。它主要考慮了數(shù)據(jù)訪問的時間局部性。它的主要思想是： 在近期被訪問的 數(shù)據(jù)更容易在不久的將來被訪問。這種算法是操作系統(tǒng)中 內(nèi)存和磁盤 間最 常用替換算法。 機算法。該算法不考慮數(shù)據(jù)的引用時間和引用頻率，而是隨機的選取一個塊丟棄 ，主要應(yīng)用于局部性并不明顯而 量又相對較大的場合 。 算法總是丟棄 最大的數(shù)據(jù)項。這種算法的思想第二章 相關(guān)研究 - 7 - 是讓 存儲 的數(shù)據(jù)項都是 比較小的，因此容量固定的 能 夠 存 儲 比 較 多 的 數(shù) 據(jù) 項 ， 從 而 提 高 數(shù) 據(jù) 項 的 命 中 率 996。 該算法采用訪問次數(shù)作為丟棄的主要依據(jù)。主要思想是：越多被訪問的數(shù)據(jù)就越容易在以后被再次訪問。方法 就是記錄每個數(shù)據(jù)項的訪問次數(shù)，在需要丟棄的時候丟棄訪問次數(shù)最少的數(shù)據(jù)項。 是 一個變種， 在考慮數(shù)據(jù)的訪問次數(shù)的同時，也考慮了時間局部性的影響 。 方法是 隨著時間的推移，以前訪問過的數(shù)據(jù)塊，乘上一個小于 1 參數(shù) ， 從而 不同時刻的訪問對數(shù)據(jù)項的權(quán)值 的貢獻 是不同的，越新近被訪問的， 對權(quán)值的貢獻就越大 ，越早被 訪問的，對數(shù)據(jù)項權(quán)值的貢獻就越小。 是 一個變種 ，它的記錄了該數(shù)據(jù)塊的最近 果只有訪問了 m 次 （ 查詢），查詢頻度越大，則兩次相鄰查詢之間的間隔越小，對數(shù)值之間呈比較好的線性關(guān)系。對于訪問頻度比較高的查詢，他們 的時間局部性比較好。 戶查詢結(jié)果翻頁 的考察 我們考察用戶更傾向 于查看返回結(jié)果的哪些頁面，以及考慮用戶第 四 章 通用 搜索引擎檢索端應(yīng)用 - 20 - 點翻頁的趨勢 。在搜索引擎中，我們很 難預(yù)測用戶可能的后續(xù)查詢，在 999中作者討論了 單個用戶查詢的一些模式，但這種模式的劃分只是涉及到用戶查詢的主題級的 信息，而不能夠比較確切的獲得用戶的 更進一步 意圖。但是， 比較明確的一點是， 當(dāng) 用戶輸入一組關(guān)鍵詞獲得結(jié)果以后，是很容易翻頁的 。 圖 5 給出了查詢的翻頁情況， 其中橫坐標(biāo)代表用戶翻的頁號，縱坐標(biāo)代表用戶所有查詢中，該頁號的查詢占總查詢的比例。 發(fā)現(xiàn)一半以上的查詢都是集中于第一個頁面的， 隨著頁面的推后，這種查詢的比例依次遞減 。 到第 10 頁以后，看得人就非常少了。 5 7 9 11 13 15 17 19 21 23 25 27 29頁號所占查詢比例圖 5 查詢的翻頁分布 圖 6 給出了翻下頁的可能情況。 橫坐標(biāo)代表頁號，縱坐標(biāo)代表翻下頁的可能性，其中的某一點 (x,y)就是表示對于某一組關(guān)鍵詞，如果翻了第 x 個頁面，那么 在一定的時間間隔內(nèi)（這里我們間隔設(shè)置為1000 個查詢）， 會翻第 (x+1)個頁面的可能性。 從圖中可以看出，當(dāng)x=1 的時候，這種可能性比較?。ù蠹s 20%），當(dāng) X 2 的時候，這種可能性就比較大了，即當(dāng)用戶翻到第 i（ 以后，繼續(xù)翻下一頁的可能性比較大。 第 四 章 通用 搜索引擎檢索端應(yīng)用 - 21 - 3 4 5 6 7 8 9圖 6 往后翻頁的可能性分布 這樣，我們就一定程度上預(yù)測了用戶翻頁的行為。我們可以采 取一定的預(yù)取策略，即在用戶翻第 i 個頁面（ i=2）的時候，我們可以先把第 i+1 個頁面取過來。 用 用 結(jié)構(gòu)和配置 體結(jié)構(gòu) 在原來的天網(wǎng)系統(tǒng)中，已經(jīng)采用了 技術(shù) ， 具體 方法是這樣的：當(dāng)用戶提交由一組關(guān)鍵詞組成的查詢的時候，系統(tǒng)就 判斷這個查詢對應(yīng)的記錄是否在 存在，如果不存在，則按照 講的方法把查詢遞交給服務(wù)結(jié)點，把服務(wù)結(jié)點返回結(jié)果的綜合的文檔號序列存到一個文件中，在 保存所存儲的序列在文件中的偏移值。如果已經(jīng)存在，就從 獲得這個存儲記錄 的偏移。然后，先從文檔號記錄文件中讀取文檔號，再根據(jù)文檔號在網(wǎng)頁數(shù)據(jù)庫中獲得網(wǎng)頁的信息，組織成頁面返回給用戶 單松巍 ,2000，如圖 示 。這樣的結(jié)構(gòu)對 容量要求比較小， 一個標(biāo)志的長度是一組查詢詞的最大長度，一個數(shù)據(jù)項的長度是一個指針的長度。 在 001中，是根據(jù) 用戶的查詢（包括了考慮用戶翻頁的輸入），產(chǎn)生結(jié)果頁面，然后直接把結(jié)果頁面緩存到 去，這樣的結(jié)構(gòu)會 有比較大的容量要求，一個標(biāo)志是一組查詢詞的最大長第 四 章 通用 搜索引擎檢索端應(yīng)用 - 22 - 度加上一個整型長度（存取頁號），一個數(shù)據(jù)項的長度是一個結(jié)果頁面的大小。 有的 用的體系結(jié)構(gòu) 新設(shè)計的 用的體系結(jié)構(gòu) 圖 7 兩種 構(gòu)的比較 用戶 遞交查詢 返回結(jié)果網(wǎng)頁 是否在 否 是 分布服務(wù)結(jié)點查詢 文件讀取文檔號序列 文檔號結(jié)果組合排序 讀取文檔信息 組織顯示頁面 用 戶 遞交查詢 返回結(jié)果 查詢 是否在 否 是 文件讀取文檔號序列 文檔號結(jié)果組合排序 組織顯示頁面 查詢 是否在 否 是 文檔數(shù)據(jù)庫讀取信息 分布服務(wù)結(jié)點查詢 第 四 章 通用 搜索引擎檢索端應(yīng)用 - 23 - 我們設(shè)計的結(jié)構(gòu) ， 是上述兩種方法的一個綜合。 改進后的情況如圖 示。 可以看到，在我們現(xiàn)在的結(jié)構(gòu)中，一共有兩 次 使用。 其中 儲的是包含翻頁號的查詢的結(jié)果網(wǎng)頁 ，在本系統(tǒng)里，單個結(jié)果頁面顯示結(jié)果數(shù)量是 10，所以這里就需要存儲 10 個相關(guān)網(wǎng)頁的信息 。 儲一個查詢對應(yīng)的結(jié)果文檔號序列在文件中存儲的偏移量，這就不考慮翻頁號，在 只儲存一個偏移，而在文件中存儲了所有 結(jié)果組成 的序列。 引入是為了 縮減讀取文檔號以及根據(jù)文檔號從文 檔 數(shù)據(jù)庫中獲得文檔信息 所帶來的時間消耗。 引入是為了縮減分布式的查詢和運算帶來的時間消耗。 另外，根據(jù)前面的分析，我們考慮預(yù)取策略是，當(dāng)一個查詢查詢翻到第 i 個 (i 2)頁面的時候，我們就模擬產(chǎn)生一個相同關(guān)鍵詞的第i+1 個頁面的查詢。很顯然，這個模擬查詢不需要經(jīng)過圖 全過程，只需要在 模擬就可以了，因為 儲的是一個查詢的所有文檔號信息 ， 不同的翻頁，對于它不產(chǎn)生影響 。 存配置 下面我們具體考慮兩個 該選擇的容量，替換 算法和預(yù)取策略。 通過通用 測試模塊日志的模擬，我們得到了一些數(shù)據(jù)結(jié)果。 在 使用 ，各個算法和容量大小 與命中率的關(guān)系 比較如圖 8 所示 。其中 a 是總體的情況，數(shù)據(jù)項的個數(shù)范圍是 0,32000， 據(jù)項的范圍是 0,2000?？梢钥吹?，當(dāng)數(shù)據(jù)項 比較少 的時候 效果比較好，而數(shù)據(jù)項比較大的時候 較好。因此， 比較好的一個替換算法，當(dāng)存取 2000 個查詢結(jié)果的時候，可以到達(dá) 20%的命中率。 存取 15000 個查 詢結(jié)果的時候，可以達(dá)到 30%的命中率。 在使用 ，各個算法和容量大小與命中率的關(guān)系比較如圖 9 所示。橫坐標(biāo)代表有多少數(shù)據(jù)項，縱坐標(biāo)代表命中率。這里由于每一個數(shù)據(jù)項所占的容量比較小，所以我們可以存儲比較多的數(shù)據(jù)項。可以看到，在存儲數(shù)據(jù)量比較大的時候，各種算法的效率相差并不大，綜合分析存取排序的代價， 以獲得比較好的結(jié)果。 第 四 章 通用 搜索引擎檢索端應(yīng)用 - 24 - 0000 20000 30000 體情況 00 1000 1500 2000 容量情況 圖 8 頁面內(nèi)容 命中率和容量關(guān)系 000 10000 15000 20000數(shù)據(jù)項數(shù)命中率 查詢文檔號命中結(jié)果和容量的關(guān)系 第 四 章 通用 搜索引擎檢索端應(yīng)用 - 25 - 下面我們考慮加入預(yù)取策略帶來的影響。我們的預(yù)取策略就是當(dāng)查詢一組關(guān)鍵詞，當(dāng)用戶翻第 i（ i 2）頁的時候，我們獲得第 i+1個頁面放入 據(jù)前面的分析，頁面結(jié)果 取 效果比較好，下面我們就用 法 比較是否采取預(yù)取策略帶來的影響。效果如圖 10 所示。我們發(fā)現(xiàn)，當(dāng)采取預(yù)取策略以后，命中率會有大幅度的提高，但是通過和圖 9 的比較發(fā)現(xiàn)和文檔號存儲 以 舊需要保留。 當(dāng)然，引入預(yù)取策略必然會降低系統(tǒng)總的吞吐率，但是搜索引擎檢索端所應(yīng)該主要考慮的應(yīng)該是響應(yīng)時間，即對用戶的返回結(jié)果的 快慢程度 ，命中率的提高，會減少系統(tǒng)的響應(yīng)時間 。 000 4000 6000 8000 10000數(shù)據(jù)項項數(shù)命中率沒有預(yù)取有預(yù)取圖 10 采用預(yù)取策略的效果 間分析 我 們下面分析使用 效率的影響。 當(dāng)不使用 時候，每一個查詢所耗費的時間是 ： t t t t1 讀 取 摘 要 組 織 頁 面查詢排序 (2) 這里，查詢排序 時間 就是通過對分布的子節(jié)點的查詢，獲得文檔結(jié)果集合，并根據(jù)相關(guān)度進行排序 所花費的總時間 。讀取摘要就是根據(jù)文檔結(jié)果號，從文檔數(shù)據(jù)庫中讀取相應(yīng)的摘要內(nèi)容 所花費的時間 ，這里也只有考慮一個頁面所能顯示個數(shù)的文檔摘要的讀取 。 組織頁面就是把相應(yīng)的內(nèi)容放入顯示頁面模板中去 所 花費的時間 ，所占用的時第 四 章 通用 搜索引擎檢索端應(yīng)用 - 26 - 間和前兩項相比比較少，所以忽略不計 。 001采用的方法縮減了查詢排序和讀取摘要兩方面的開銷，即變?yōu)椋?C a c h e 1t t t t )*t C a c h e2 插入讀取摘要查詢排序獲取1 ( 1 - 命 中 率 1 ） * ( 命中率1(3) 其中命中率 1 就是考慮了緩存結(jié)果頁面的命中率，t 獲取，讀取和插入 需要的時間。 單松巍 ,2000采用的方法，縮減的是 查詢排序 的開銷，它獲得的結(jié)果是： C a c h e 2t t t* t tC a c h 入查詢排序獲 取 2 讀 取 摘 要 ( 1 - 命 中 率 2 ） * （ ） 命 中 率 2 (4) 其中命中率 2 是緩存結(jié)果文檔號 命中率。 本方法采用了兩層 結(jié)構(gòu)，同時縮減了查詢排序和摘要讀取的時間，耗費的時間是： 41C a c h e 21( 1 t + * tC a c h eC a c h 插 入 C a c h e 2查詢排序插入獲 取 讀 取 摘 要獲取命 中 率 1 ) * ( ( 1 - 命 中 率 2 ) * ( ）+ 命 中 率 2 *+ 命中率(5) 各個變量的含義和 (1)(2)(3)中的含義是一樣的。 下面給出 通過統(tǒng)計 獲得的 各個部分的耗時 。其中， 插入時間和 獲得內(nèi)容的時間分別是以 以頁面存儲 命中率為 20%，文檔號 命中率為 60%作為示例?？梢缘玫?表 2 的分析結(jié)果。由于頁面存取 命中率比較低，所以只是采用頁面存儲 時間消耗會比較大，因為根據(jù)設(shè)定， 80%的查詢還需要通過原來的方式查詢各個索引節(jié)點的倒排文件。只存取文檔號的 需要訪問存放文檔號的文件，以及訪 問文檔數(shù)據(jù)庫獲得文檔的部分信息，即會經(jīng)過兩次 作，那么這里面消耗的時間也比較多。當(dāng)采用兩級 情況下，就會有比較少的時間代價，顯然它比只用以上的任何一種都好。 最后我們考慮一下使用預(yù)取策略以后的時間代價。從響應(yīng)時間第 四 章 通用 搜索引擎檢索端應(yīng)用 - 27 - 來看，由于頁面存取 命中率的大大提高，仍把數(shù)據(jù)代入 (5)， 變量 數(shù)值 (秒 ) 說明 詢 排 序 總 時 間 定 得 摘 要 時 間 10%) 入 頁 面 e 時 間 代 價 10%) 取 頁 面 信 息 時 間 代 價 60%) 入 文 檔 號 間 代 價 t 獲取(60%) 取 文 檔 號 的 時 間 代 價 用 均 用 時 001的 查 詢 平 均用時 單松巍 ,2000查 詢 的 平 均用時 文 查 詢 平 均 用 時 表 2 不同層次結(jié)構(gòu) 時間影響 獲得的時間性能會優(yōu)表 2 中 命中率為 40為例，可以得到 t= 此對于某一個用戶來說，返回結(jié)果的速度一般會變快。但是，由于對于將近 50%的第 2 頁及其以后的翻頁，我們都需要預(yù)取下一頁的結(jié)果 。 從吞吐率上考慮 ，對 100 萬個查詢，不采取預(yù)取總耗時是 00000=740000 秒 ， 而 采 取 預(yù) 取 策 略 總 耗 時 000000*(1+832000 秒。吞吐率反而降低了， 因此如果我們系統(tǒng)的負(fù)載比較大，即查詢 密度很高 的話，我們 采用預(yù)取策略 并不好。 第五章 總結(jié)和進一步工作 - 28 - 第五章 總結(jié)和進一步工作 本文的主要工作是設(shè)計了一個通用 模塊， 此模塊具有通用，高效和具有 自測試能力。它 在容量，替換算法，層次結(jié)構(gòu)，預(yù)取策略等方面，都可以由用戶 通過對配置文件的配置進行調(diào)節(jié) ，因此可以應(yīng)用于不同的場合。它采取了多層次的體系結(jié)構(gòu)，對用戶屏蔽了存儲的細(xì)節(jié)，也提高了并發(fā)度。 在分析了天網(wǎng)日志以后，證實了對于搜索引擎的查詢具有很強的局部性規(guī)律 ，另外獲得的一個啟發(fā)是當(dāng)用戶點擊某一個序號大于 1的結(jié)果頁面以后，就會很可能點擊它的后續(xù)頁面，因此我們決定了一個預(yù)取策略。 在應(yīng)用中，采取了兩層的 構(gòu)，分別存儲結(jié)果頁面和結(jié)果文檔號，盡量的減少存取和計算的開銷 。對于兩層 構(gòu)，發(fā)現(xiàn) 頁面結(jié)果 用 替換算法結(jié)果比較好，而文檔號 采用 能獲得比較好的結(jié)果。 下一步工作可以是把通用 通用性進一步提高，滿足分布式系統(tǒng)的要求，對于一個應(yīng)用的需求， 把結(jié)果緩存到不同的主機上。另外 ， 也可以把通用 塊 應(yīng)用于更多的方面 。 參 考 文 獻 - 29 - 參考文獻 . 003 M. N. J. L. W. . RL of 2003.