1、學位論文題目：大規模可擴展索引技術的研究和系統實現姓 名：學 號：院 系：信息科學技術學院專 業：計算機系統結構研究方向：搜索引擎與Web信息挖掘導 師：教授二八年 五月版權聲明任何收存和保管本論文各種版本的單位和個人，未經本論文作者同意，不得將本論文轉借他人，亦不得隨意復制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權之問題，將可能承擔法律責任。71 / 71文檔可自由編輯打印摘 要隨著互聯網的發展，原始的數據庫系統無法滿足大數據量相關性檢索的需求。從而基于倒排表的索引系統越來越多的應用在各項服務中。但是索引系統和數據庫系統一樣，有著較為復雜的內部邏輯和外部行為，如何創建我們需要的索

2、引系統，如何優化我們的索引系統，是困擾很多索引系統構建者和使用者的難題。本文的研究范疇是用于信息檢索的索引系統，通過一個真實的索引系統Paradise索引系統，本文從三個方面進行分析和研究：對索引系統進行功能模塊上的分析；對索引系統開發和使用中的性能問題的研究和分析；對一個實際系統的系統實現的詳細。具體為：1) 索引系統的模塊分析本文詳細分析了作為一個復雜系統的索引系統，其創建和使用都受到很多條件的制約。本文分析了索引系統的常見的需求，比如如何對原始的文檔集合進行分析，如何設計索引內部文檔的表示能力，索引如何創建，如何存儲等，劃分了一系列基本的功能模塊。2) 索引系統的性能分析因為索引系統的目

3、的是快速的響應檢索需求，所以效率問題一直是索引技術的核心問題。在模塊功能分析的基礎之上，本文進一步分析了索引創建和檢索中常見的性能問題，提出了基本的解決方案。同時，對于如何對索引系統進行整體的和局部的量化分析，引入了DQ法則，嘗試給出一個指導實踐的經驗公式。3) Paradise索引系統的實現分析對于問題的分析，需要一個具體的系統進行實踐。在深入研究天網搜索引擎已有的索引系統和相關索引系統基礎上，同時在大量閱讀了相關專業文獻之后，我們進行了分析和研究，設計實現了863課題支持的Paradise項目的索引系統。本文以系統的基本模塊和重要接口為核心，分析了系統的基本框架能力以及如何進一步對系統進行

4、擴充。關鍵詞：信息檢索，索引系統，索引優化，倒排表The research and implementation of Large Scale and Extensible Indexing SystemAbstract Along with the rapid development of Internet, the database system is not suitable for the large dataset in information retrieval task. The indexing system is used more and more in lots of w

5、eb applications. As the database system, indexing system have its own difficulty in internal logic and external behavior. How to build our own indexing system and how to optimize it is difficult for the indexing system developer and user.The research of this thesis is indexing system used for inform

6、ation retrieval. This thesis will present three aspect of indexing system through one real system Paradise indexing system. (1) To modularize the indexing system basing on the function point of view; (2) To analyze the optimization problems in the develop and use of indexing system; (3) To analyze t

7、he implementation of the indexing system.(1) Modularizing the indexing systemDue to the complexity of the indexing system, the construction and the usage of it is restricted by lots of conditions. In this thesis, common questions existed in the system are presented, corresponding solutions are offer

8、ed. Such as the analysis of the raw document set, the representation of the indexing and how to build, how to store etc.(2) Optimizing the indexing systemDue to the indexing system need quick-response to the retrieval, the efficiency problem is the key problem in the indexing technique. In this thes

9、is, the solutions to the common questions existed in the construction and retrieval of the index are offered. The quantitative analysis of the indexing system is also considered in this thesis. The DQ principle is employed to give the tested formulas interrelated.(3) Implementating the indexing syst

10、emIn the end of this thesis, one real system which is used in the Paradise project is designed and constructed. The basic modules and interface are explained, and how to expand the each module is also presentated.Key words: Information retrieval, Indexing System, Index Optimization, Inverted Lis目錄摘

11、要3Abstract4目錄5第一章 緒 論61.1 索引系統背景61.1.1 互聯網服務系統61.1.2 Data / Query 法則71.1.3 需求快速查詢的場景71.2 和數據庫系統的比較81.2.1 數據庫系統的能力81.2.2 索引系統和數據庫系統的異同81.3 索引系統的簡單用例91.3.1 索引系統基本模塊101.3.2 索引系統基本流程101.4 本文的主要工作111.4.1 本文的主要研究點111.4.2 本文的主要創新點111.5 本文組織結構11第二章 索引系統分析122.1 索引核心模塊分析122.1.1 分析模塊122.1.2 文檔表示模塊122.1.3 存儲模塊1

12、52.1.4 索引創建152.1.5 存儲鏡像的邏輯視圖182.1.6 索引檢索192.2 大規模索引專有模塊202.2.1 壓縮模塊202.2.2 緩存模塊262.3 動態索引282.3.1 版本控制292.3.2內存索引312.4 分布式索引312.4.1 可用性和可靠性與DQ法則322.4.2 索引切分和索引冗余342.4.3 針對可用性和效率的解決方案352.4本章小結35第三章 索引優化363.1 索引創建的優化363.1.1 創建時期內存壓縮363.1.2 動態索引二路歸并的塊合并時機373.1.3 大索引多路歸并方法383.2 索引檢索效率的優化393.2.1 檢索時效率分析39

13、3.2.2 使用塊狀壓縮和跳查來降低CPU使用393.2.3 使用緩存機制來降低IO433.3 索引常數443.3.1 單機的服務能力上限443.3.2 整體服務優化453.3.3 單機索引常數463.4 本章小結46第4章 Paradise索引系統框架484.1 系統目的484.1.1 面向搜索引擎服務484.1.2 可擴展性，可實驗性484.2 基本模塊詳細分析484.2.1 分析模塊494.2.2 文檔表述模塊504.2.3 存儲模塊514.2.4 壓縮模塊524.2.5 緩存模塊534.2.6 索引模塊544.3 索引創建流程用例分析574.4 索引提供的檢索接口用例分析59第五章 總

14、結和展望635.1 本文總結635.2 進一步工作63參考文獻65致謝68圖表 1互聯網服務系統示意圖9圖表 2 文檔集合和查詢集合12圖表 3 簡單索引流程13圖表 4對頁面進行分析16圖表 5 文檔倒排操作18圖表 6 倒排合并操作19圖表 7 in-place 合并20圖表 8 re-merge 合并21圖表 9 檢索過程22圖表 10 PForDelta壓縮26圖表 11 PForDelta 代碼示例27圖表 12 壓縮時間對比28圖表 13 解壓時間對比28圖表 14 壓縮后長度對比29圖表 15 Linux IO讀操作29圖表 16 三級緩存策略30圖表 17 索引創建和服務分離3

15、2圖表 18 版本控制33圖表 19 內存索引34圖表 20 索引數據切分35圖表 21索引數據冗余36圖表 22 索引數據切分且冗余36圖表 23 二路合并40圖表 24 哨兵位和定長壓縮數據44圖表 25 獨立跳查結構44圖表 26 使用跳查表進行求交45圖表 27 不適用跳查表進行求交46圖表 28 塊狀存儲46圖表 29分析模塊結構圖52圖表 30存儲模塊結構圖54圖表 31 壓縮模塊接口示意55第一章 緒 論1.1 索引系統背景索引技術現在是一種在網絡服務中很常用的技術。在很多的信息檢索服務中，都會在數據量相對較大和反應時間要求較短的情況下，考慮使用索引系統。其中現階段最常見的應用就

16、是搜索引擎系統。文獻2給出了索引系統的一個綜述，全面地描述了索引技術的基本問題和已有的解決方法。1.1.1 互聯網服務系統對于大規模的互聯網的服務系統，基本的系統構架都如圖所示。圖表 1互聯網服務系統示意圖l 服務機器會將用戶的請求（比如查詢請求），按照某種邏輯進行劃分，分配到對應的后臺機器上去。 l 后臺機器一般來說在數據結構，或者服務能力上是同構的。比如，每臺都有同構的數據庫表格，存儲的是單一一臺機器無法成功存儲的數據量。服務機器最終會接受后臺機器集群的結果，給以綜合計算，將最終用戶需要的信息返回。1.1.2 Data / Query 法則當需要對一個互聯網服務系統進行分析和評價的時候，我

17、們常常會陷入困境。因為和普通應用程序不同，我們很難對整體系統進行精確的算法分析，以及應用類似復雜度計算的分析手法。 我們面對的可能情況是： l 硬件級別上的異構：我們的服務機器和后臺機器可能是不同的硬件系統，擁有不同的計算能力 l 應用上的差異：對于前端服務機器來說，需要處理的問題一般是負載均衡，結果合并和過濾等計算密集型任務；后臺的機器則需要完成較多的數據讀取這類IO較為密集的任務。 在這樣的情況下，可以使用DQ法則來幫助我們分析系統問題。 DQ法則將計算機的所有計算能力（CPU速率，內存速率，IO速率，網絡速率等）都看作是底層的數據流（Data），而我們提供的服務是一個一個的查詢操作（Qu

18、ery），在這種情況下，每秒鐘可以處理查詢的條數和每條查詢需要處理的數據的乘積就是我們的系統的服務能力。 公式 1 而我們整個系統的數據流提供能力的總和，應該和上面的結果匹配。關于DQ法則的具體細節，請參考文獻33。1.1.3 需求快速查詢的場景 對于互聯網服務系統來說，其面對的數據量都是巨大的。這樣的話，進行快速的查詢和海量的數據就構成了矛盾。現在最常見的就是搜索引擎的檢索服務，需要在非常短的時間內（1秒左右），在非常大的數據量（億級別網頁，TB級別數據）中找到符合某一類要求（比如包含查詢字串）的結果。文獻7從信息檢索角度對基本的數據結構和算法進行分析。比如，我們需要查找“北京大學”相關的內

19、容，在互聯網上，相關的網頁集合可能非常的大。并且用戶得到一定的反饋之后，可能繼續進行檢索行為。因此，我們應該可以同時滿足在海量數據上的查找以及快速的反饋。1.2 和數據庫系統的比較數據庫系統非常廣泛的被應用于互聯網服務系統中，比如非常流行的 MySQL + php 的系統框架。同時，大規模的分布式數據庫系統也得到了廣泛的應用。索引系統和一般意義上的數據庫系統有著什么樣的不同呢？我們可以從其能力上進行對比。1.2.1 數據庫系統的能力 數據庫系統的能力可以被其查詢語言SQL所很好的描述，我們可以通過給出一個嚴謹的SQL語句來達到一個較為特定的目標。 Select STUDENT.NAME Fro

20、m STUDENT Where AGE Between 12 And 16;從例子我們可以看出，查詢者有一個非常明確的目標，從STUDENT表中找到所有年齡在12到16歲之間的STUDENT.NAME。對于這條語句的執行結果是：所有的符合要求的內容都會返回，使得查詢者的需求得到滿足。 另外一個較為讓人混淆的概念是數據庫中的索引，數據庫中的索引是一個邏輯意義上的索引結構，用來加快數據庫表的檢索速度而將一類數據建立了索引項，這些數據一般來說不保證在物理上相鄰。從某些方面來說它更像書籍的索引。1.2.2 索引系統和數據庫系統的異同而對于索引系統來說，他提供的檢索能力與數據庫系統是不同的。是基于“相關

21、性計算”得到的結果集合。所謂的“相關性”是說： 查詢和結果在某種程度上“相關”，比如查詢中的詞在結果中多次出現就是一種相關性。 一種最簡單的相關性模型就是向量空間模型（VSM），他認為查詢詞和文檔都是一些詞集合（bag-of-words），通過計算它們之間的向量夾角 可以得到他們之間的相似度。 對于VSM模型，舉例如下。文檔一 ： “北京 大學 南門”文檔二 ： “清華 大學 西門”查詢 ： “大學 南門”整體詞的集合：“北京 清華 大學 南門 西門”相似度（文檔一，查詢）= 向量夾角（(1, 0, 1, 1, 0), (0, 0, 1, 1, 0)）相似度（文檔二，查詢）= 向量夾角（(0,

22、 1, 1, 0, 1), (0, 0, 1, 1, 0)）這樣的計算結果，我們可以看到文檔一和查詢的相似度比較大。所以，對于索引來說，通過計算相關性的值來將索引文檔集合進行排序，返回給用戶相關性最高的文檔。但是對于用戶來說，查詢詞所代表的意義是不明確的和有歧義的。比如“病毒”，“Java”這些歧義查詢，以及“北大主頁”這種導航性查詢，“怎么治療感冒”這類信息型查詢等等。用戶只是通過一些模糊的概念來選擇查詢，根據不同的需求瀏覽相關文檔，進一步修正查詢詞，得到相關信息。對應于數據庫查詢的接口來說，這些“相關性”查詢很難轉換為規則的SQL等查詢語言；同時數據庫系統的一般行為是返回所有符合查詢邏輯的

23、結果，這對于海量的文檔集合來說，也是不合實際的。1.3 索引系統的簡單用例為了更加直觀的解釋索引系統的能力，我們可以構造一個簡單的用例來說明。假設我們有以下三篇文檔，和兩組查詢詞。我們的目標是在文檔集合中找到查詢詞出現的文檔集。圖表 2 文檔集合和查詢集合整個的過程是將文檔集合進行分析（Tokenize），建立索引，然后可以提供對索引文件的檢索。整個流程可以簡單的由下圖表示。圖表 3 簡單索引流程1.3.1 索引系統基本模塊通過上述的用例，我們可以觀察到索引系統可以劃分為一些基本的功能模塊，比如： 從原始文檔到可索引文檔的分析模塊，將索引進行存儲的模塊，索引建立的模塊以及索引檢索的模快。1.3

24、.2 索引系統基本流程索引的基本流程可以說有兩個大模塊，索引的建立和索引的檢索。索引的建立就是把原始的文檔集合經過分析后，創建索引鏡像；索引的檢索模塊是說對于用戶的檢索請求，在索引鏡像中找出相關的原始文檔集合。1.4 本文的主要工作本文的主要工作有以下幾點：1. 分析索引系統的功能和框架。2. 分析索引系統的系統優化。3. 給出一個索引系統的實現細節。1.4.1 本文的主要研究點本文的主要研究點是針對大規模索引，如何使其在數據上擁有可擴展能力，以及在代碼模塊上擁有可擴展可替換能力；以及如何進行一個實際的索引系統的設計和實現23, 26。1.4.2 本文的主要創新點對于大規模索引來說，如何對索引

25、系統的能力進行分析是一個較為困難的任務。本文提出使用DQ法則來對整個索引系統進行框架性的分析，同時對于單個索引機器的分析，嘗試性的給出了“索引常數”的概念，即通過一個經驗公式，嘗試對單個機器的在索引上的運算能力進行建模。1.5 本文組織結構本文的章節按照如下方式安排：第一章：即本節著重從背景和應用的角度說明了索引系統的基本理論。第二章：將會按照索引系統的功能劃分，詳細論述索引系統在系統級別上每個模塊的作用和行為。第三章：主要描述在實際過程中可能會遇到的性能的問題，以及如何去做優化。第四章：詳細的分析了天網的Paradise系統索引模塊的內容，每一個模塊的關鍵接口和流程都會進行描述，同時會通過兩

26、個用例來展示索引模塊的兩個主要能力。第五章：對本文的總結和進一步工作的展望。第二章 索引系統分析索引系統在功能上可以進行劃分，得到彼此相關的一些模塊，這些模塊有些是基本的索引系統必須的，而有些是為了特殊的性能要求才需要的，我們逐一對這些模塊進行分析。2.1 索引核心模塊分析核心模塊的意思是說這些模塊在所有的索引應用中都是必須的，主要包括了分析，文檔表示，存儲，索引，檢索幾個基本模塊。2.1.1 分析模塊 索引的分析模塊的主要作用是將外部的文檔格式轉換為一個單元（Token）的序列。其中單元（Token）是需要索引的最小的成分。Token一般由其字串，在文檔中的偏移信息，以及類型信息等組成。在分

27、析的過程中，可以識別出來一些需要的Token，或者進一步轉化一些Token的字串，如采用英文中的詞干提取（stemming）技術，以及過濾掉一些常用無意義的詞匯（stop words）。 對于分析后的信息，可以進一步建立索引的文檔表示。2.1.2 文檔表示模塊文檔表示是索引的最基本的模塊，它往往說明了索引的檢索粒度和能力。一般的索引系統都將文檔表示成為詞集合（bag-of-words）的方式，盡管像indri系統中出現了將文檔組織成為樹狀結構的情況26，但是卻沒有對應的檢索模塊。原因之一是像HTML這樣的標記性語言，它的結構信息很多是用來表示視覺的展示，而不是表達內容的相關性。圖表 4對頁面進

28、行分析我們可以看到，在這個網頁上有著通用的頁面信息（Page Attribute）。l 標題：“PKU: Search Engine and Web Mining Group” l 正文信息： 略 l 正文第一句： “The Search Engine and Web Mining (SEWM) Group” l 正文內鏈接文本信息： “Tianwang search engine” 和 “Web Infomall” l 鏈接信息： 左側的大量文本 從直覺上可以得知，上面的幾類文本在這個網頁中的重要性是不同的，需要分別標識用來給檢索模塊提供信息。對于文本的分類標識，可以從兩個方面考慮，域（Fi

29、eld）和附加信息（Payload）。域可以簡單的認為是一種前綴信息，我們將類別和文本組成了二元組<域，文本>來區別不同類型的文本。那么，上面的標題文本在詞集合的行為下就可以表示成為: l <Title : "PKU“> l <Title : "Search">l <Title : "Engine">l 域信息會有什么樣的用處呢？一個最簡單的方式是可以在檢索階段賦予標題域一個和正文域不同的權值。通常來說不同的域的權值的不同的重要性，權值較高的標題域表明在檢索階段，其中包含的信息更加有價值。而正文域

30、相對于標題域，其重要程度會遜色一些。附加信息可以認為是附加于文本出現位置的權值信息，比如我們可以認為正文第一句是比較重要的位置信息，那么我們給這種情況一個權值提升，可以是一個值或者是一個標記，從而得到：l <"PKU" : boost> l <"Search" : boost>l 這樣看來，域和附加信息似乎是相同的，可以替換的。但實際情況不是這樣，至少由于以下兩種情況使得域和附加信息是不能替換的因素。 1. 在索引中的存儲位置在2.1.5小節中，我們可以看到索引的邏輯表示，其中的boost信息即指附加信息字段。而域信息則是和文本詞

31、組成二元對，存儲于索引字典中的。 2. 在可求交性上在檢索過程中，往往需要對查詢進行布爾操作中的與操作（求交操作），這樣的情況下，我們查詢“PKU Search”的時候，標題中的“PKU”和正文第一句中的“Search”往往不應該參與運算。這是因為，標題域和正文域代表了不同的信息塊，除非是為了找到兩個查詢詞在一篇文檔中共現，否則可能牽涉到距離運算的求交不應該作用在兩個不同的域之上。而查詢“Tianwang search engine is one of the most famous search engine”的時候，正文中鏈接文本中的“Tianwang search engine”和正文中

32、的“ is one of the most famous search engine”應該參與有臨近關系的求交運算。 對于附加信息，可以給出“Web Archive”和“Web Infomall”進行求交的例子。后者作為錨文本，會得到一個較大的權值，但是同時它與沒有特殊權值的前者仍然同時屬于正文域，對他們的求交查詢可以正常的進行。我們可以這樣理解域和附加信息的區別：域中的元素在求交運算上都是滿足正交關系的，即對于兩個不同的域（比如標題和正文域）的求交是不太有意義的。而附加信息則不同，任何不同的附加信息，他們都可能在語義上想關聯，對他們的求交是合理的。綜合本節的內容，我們可以認為文檔表示的單元是

33、<域，詞，附加信息>三元組。2.1.3 存儲模塊 統一的存儲視圖，有了存儲模塊的話，我們的索引模塊就不用考慮創建的索引到底是存儲在內存中，或者磁盤等介質上。2.1.4 索引創建 索引的創建一般來說可以分為兩個步驟： 1. 將單個文檔進行倒排(reverse)，成為一個單文檔倒排表 圖表 5 文檔倒排操作倒排文檔的生成如圖所示，即提取出文檔對應的詞典，每一個詞對應其出現的位置信息。圖中的文檔中只有A出現了2次，其位置信息分別是1和3。2. 將倒排文檔按照某種方法進行合并，生成大倒排表。 圖表 6 倒排合并操作在圖表 6 倒排合并操作中，兩個單文檔的倒排表1和2通過某種合并方式，合并成

34、為倒排表3。同時，生成的倒排項加入了文檔編號。對于合并的方法來說，共有三種基本的索引創建方法： l in-placel re-mergel rebuild in-placein-place的意思是，索引的更新等操作，不會較大改變索引的結構，比如不會改變索引的詞典文件，更新的數據會插入對應的預留位置，當預留位置不足的時候，更新可以作為塊，在預留位置的末尾添加指向這個塊的信息。in-place比較適合少量更新的索引合并方式。 圖表 7 in-place 合并 re-mergere-merge的策略可以近似的考慮為多路歸并。 將所有的待合并的索引塊，按照詞進行合并操作。

35、圖表 8 re-merge 合并 rebuildre-build是一種大索引最常用的更新方式，將所有的原始文檔重新進行一次合并。在重建階段進行數據的更新。這樣的特點是框架簡單，程序比較穩定。2.1.5 存儲鏡像的邏輯視圖 我們可以將索引存儲看作三個部分： 1. 索引字典 索引字典的作用是通過索引詞來得到索引項的地址（在索引數據文件中的偏移），簡單來說，索引字典可以看作一個哈希表。<Term, Offset>+2. 索引數據 索引數據文件一般來說至少包含了索引詞出現的文檔編號列表，進一步來說可以包括索引詞在文檔中出現的位置信息和附加信息（Payload）。索引數據文件在

36、邏輯上可以表示為如下結構之一：<doc>+ <doc, payload><doc, freq, <position>+>+ <doc, freq, <position, payload>+>+ 其中Payload我們在2.1.2中進行了介紹。一般來說，索引數據文件可以存儲為一個文件，也可以存儲為不同的文件。我們在本文的以后章節可以看到，不同的存儲方式可能帶來不同的效果。索引系統對于索引數據的存儲最好不做假設，提供較為靈活的接口。3. 索引信息 在索引中我們還需要一些有用的信息，比如索引詞的相關信息（Term Info），索

37、引數據的相關信息，以及被索引數據的正排文件。 2.1.6 索引檢索 在1.2.2中我們提到了“相關性”，索引的檢索就是按照某種相關性對文檔進行打分，按照得分的順序返回給用戶。 簡單來說：當我們進行一次查詢的時候，我們會給出一個查詢字串。該查詢字串經過查詢分析后，將其切分為索引詞集合。接著我們需要一個布爾操作得到對應的結果文檔集合，然后評分機制會對文檔進行評分，使得結果集合有序。 圖表 9 檢索過程查詢分析過程將原始的查詢串分析成為可用于布爾操作的樹狀結構。可能會進行查詢分類，以及查詢擴展的操作。 比如查詢詞：“北京大學南門”，可能會被分析為“北京大學” and “南門”兩個查詢詞

38、；而“北大” and “南門”則是有效的查詢擴展。我們則可以生成一顆簡單的查詢樹： and / or 南門 / 北大 北京大學 布爾查詢過程對于查詢詞生成的布爾樹，我們可以進行布爾查詢操作，還是用上面的例子，在這樣的情況下，可以找到同時出現“北大”和“南門”以及“北京大學”和“南門”的文檔。我們對于查詢構造一定量的命中結果集合（比如2000篇文檔），然后在這個結果集合中開始查詢評分的過程。 查詢評分過程查詢評分需要使用索引中存儲的數據信息用來計算查詢和文檔的相似度，在獲得了一系列相關信息后（索引詞的tf，idf，對應文檔的長度信息，權重信息等）后，我們使用一些檢索

39、模型，例如向量空間模型，概率模型，語言模型等計算模型對這些信息進行計算求得對應的相關性的值。最終使得結果集合中的文檔有序返回。 在系統中布爾查詢過程和評分過程往往不是獨立的兩個過程，可以交錯進行。2.2 大規模索引專有模塊2.2.1 壓縮模塊原因： 對于大規模的索引來說，特別是對于較大的索引鏡像（不論是內存的還是硬盤的），壓縮算法的特性都會給以索引效率極大的影響9, 10, 11, 12, 13。 對象： 整數壓縮。索引數據基本上是由整數構成。一般來說，一個壓縮算法的三種特性可能會影響到索引： l 壓縮時效率：將原始數據轉換為壓縮數據的效率 l 解壓時效率：將壓縮數據恢復為原始數據的效率 l

40、壓縮率：壓縮數據大小/原始數據大小 當壓縮時效率和解壓時效率相差很大的時候，我們稱該壓縮算法為非對稱壓縮算法。非對稱壓縮算法在桌面應用程序中可能用處有限，因為一個壓縮緩慢但解壓迅速或者壓縮迅速但是解壓緩慢的程序會讓用戶感到困惑。對于索引創建的時候，壓縮時效率高的壓縮算法可以較快的完成壓縮流程，使得創建實踐較短。但是往往在實踐中，索引創建的瓶頸并不是壓縮操作，而是文檔的倒排操作和歸并時的IO操作。所以，壓縮時效率不會作為選擇索引壓縮算法的關鍵因素。在索引檢索階段，解壓時效率比較高的算法可以使得索引有著較快的響應速度。索引作為一個實時性要求比較高的系統，解壓時效率較為重要。壓縮率也是一個重要的考察

41、因素。對于大規模索引系統來說，索引鏡像不可能全部的載入內存中，因此，在檢索階段，對于不存在于內存中的待解壓數據，需要IO操作將其從外存中載入。由于外存速率和內存速率有著數量級的差異，較高的壓縮率可以使得平均載入內存的數據量變小；同時，內存中也可以緩存更多的索引鏡像塊，減少IO的次數。因此，壓縮率也是影響檢索時效率的一個關鍵的因素。下面給出一些常見的壓縮算法。 Var-Byte :這是最常見的一種壓縮算法，在索引系統中被大規模采用。在近兩年，新的算法推出，在壓縮率和解壓時間全面超越了var-byte算法，動搖了var-byte算法的地位。但是該算法簡單直接，對于需要數據少，數據分布

42、不集中的待壓縮數據來說，還是很有效的算法。 該算法可以簡單描述如下：input : numberif number < 128 : 使用一個byte存儲else if number < 128 * 128 : 使用兩個byte存儲，第一個byte最高位設為1else if number < 128 * 128 * 128 使用三個byte存儲，前兩個byte的最高位設為1比如：兩個數字35和145的壓縮結果如下 35 : 00100011 145 : 10000通過算法描述，我們可以看到，var-byte的優點就是極為簡單，按照和128的冪的比較來分配壓縮后的字節數，通過判斷

43、最高位是否為0來判斷解壓末尾。屬于 byte-align壓縮算法（壓縮按照byte對齊）。其缺點是解壓算法中有太多的判斷語句，同時對于較小的數字壓縮率一般（至少是一個byte長度）。 Rice / Golomb: 該算法被認為是實踐中壓縮率較高的算法之一，我們可以通過下面的算法描述來了解原始的Rice算法。 input : number4 avg = total(number4) / 4 b = 2log(avg) for i from 1 to 4 : unary (numberi - 1) / b store (numberi - 1) % b 假設輸入4各數字33，143

44、，112，161時，結果如下： 33 = 0*64+33 = 0 100001 143 = 2*64+15 = 110 001111 112 = 1*64+48 = 10 110000 161 = 2*64+33 = 110 100001 算法首先求得一個局部的數字b，使得其為小于4個數字平均值的最大的2的冪。然后將原始的數字分別取除數和取余數，按照不同的方法進行存儲。Rice和var-byte算法的不同之處在于，他在壓縮之前進行了簡單的統計，了解了4個數據的大概分布，這樣通過存儲共有數據信息，減少了數據的壓縮后存儲空間。Rice是bit-aligh壓縮算法的代表。原始的Colomb算法和Ri

45、ce算法的不同之處是，他取得平均值的0.69倍后再求b。 Simple9 / Simple16該算法是最近出現的較為有效的塊壓縮算法之一。塊壓縮算法的特點是將多個數字同時壓縮和解壓，將壓縮后的數據分為控制位和數據位，控制位記錄一些統計信息，數據位記錄對應的壓縮數據。對于Simple9來說，一個Word（32bit）被切分為兩個部分，4bit的控制位和28bit的數據位。4個bit位用來表示數據位中的9種情況，如下所示。 | 4 bit | 28 bit | | 控制位 | 數據位 | 同時9種可能的壓縮情況為： - 1 28-bit number - 2 14-bit numbe

46、rs - 3 9-bit numbers (1 bit 無效) - 4 7-bit numbers - 5 5-bit numbers (3 bits 無效) - 7 4-bit numbers - 9 3-bit numbers (1 bit 無效) - 14 2-bit numbers - 28 1-bit numbersSimple9的限制是壓縮的數據不能超過28bit長，對于索引壓縮來說，由于存在全局編號和局部編號的映射，不會出現超過范圍的數字。 Simple16則是針對64位字的（64bit）的壓縮算法，思路和Simple9類似。 PForDelta PForDelt

47、a是現有壓縮算法里較為杰出的方法，它在壓縮率和解壓時間上都有相對較好的能力。其算法思路是：將一批數據（比如128個數）進行了統計，找到90%的數據的位數范圍，將它們按位壓縮。將剩余10%的異常數據的數據位置進行記錄，然后對他們單獨存儲。 數字數字異常樁數字異常異常異常異常圖表 10 PForDelta壓縮如圖所示，在原始的異常數字的地方插入異常樁（表明這里是一個異常），然后在整個壓縮數據的末尾，將異常信息進行存儲。PForDelta的算法在實際的使用中，有非常好的解壓速率，一般認為其符合了現代計算機的流水線工藝即解壓過程中沒有判斷語句，不會打斷CPU的流水線；同時每次128個數據是在CPU緩存

48、的容忍范圍內。從而得到了優于其他算法的效果。 圖表 11 PForDelta 代碼示例 我們可以從上面圖中的代碼片段看到，PForDelta算法的解壓縮的核心代碼部分沒有任何條件判斷語句。對比與Var-Byte算法，由于Var-Byte中的128是一個較小的數，無論怎樣安排判斷語句的順序，都會造成CPU流水線的預測失誤，從而造成較大的性能損失。對比試驗結果我們設計出一組試驗，主要用來比較最近的兩個算法Simple9和PForDelta與最常見的壓縮算法Var-Byte的比較。實驗按照以下的方法進行：(1) 每次產生某一區間（橫坐標軸）的隨機數字100M個(2) 所有的操作均為內存

49、操作，不考慮IO時間(3) 單進程，CPU 2.4G，內存1G對于圖表 12 壓縮時間對比和圖表 13 解壓時間對比中的縱坐標軸為時間(ms)，對于圖表 14 壓縮后長度對比中的縱坐標為字節數(byte)。圖表 12 壓縮時間對比圖表 13 解壓時間對比圖表 14 壓縮后長度對比我們從實驗中可以看到，PForDelta有著較好的特性：不對稱壓縮（壓縮時間較長，解壓時間較短）可以給以檢索階段以較短的反應時間（索引創建時的效率一般要求不高）；較高的壓縮率可以大大減小索引鏡像的大小，使得對IO的壓力大大降低。所以，在現代大規模索引中，PForDelta以及改良的PForDelta算法可以進行廣泛的應

50、用，從各個方面提高索引性能。2.2.2 緩存模塊我們首先了解一下Linux文件緩存的原理。Linux文件系統（VFS）的緩沖區策略對文件的讀取本身進行了基本的緩存操作。基本的方法就是系統對IO建立一個緩存區緩存（Buffer cache），將用戶態程序對數據的讀取都限制在對緩存區的讀寫上，從而大大的降低了系統對IO的訪問頻度。Linux系統對緩沖區的管理一般來說是使用經過地址轉換的哈希表，按照一個固定大小的倍數或冪進行緩存（比如512字節的倍數，可以通過修改內核重新制定大小）。對于任何的文件讀取來說，系統都會向緩存區緩存請求對應的數據塊，如果緩存區緩存沒有對應的數據，系統就會訪問IO將數據讀入

51、緩存區，然后再拷貝到用戶空間。同理，用戶對于IO的寫操作也按照類似的行為進行，首先寫到緩存區緩存中，再由系統定時寫回到實際設備中。 圖表 15 Linux IO讀操作直接使用系統緩存是一種較為簡單的方法，在這種情況下，我們可以得到性能往往超過沒有經過調優的自己實現的緩存策略。但是Linux系統緩存本身對與索引系統來說，對應較高的性能要求是不足夠的。l 靜態緩存的需求：對于檢索日志進行分析，大量的數據請求都集中在少量的數據區域上，我們可以將這些內容作為靜態緩存。 l 內核態到用戶態數據復制：使用系統緩存的問題是，無法直接使用系統緩存的數據（無法直接操作），需要將緩存中數據進行一次數據拷貝（見上圖

52、）。我們可以通過一個簡單的試驗來測試Linux文件緩存的效率。通過反復將一個文件讀入多次，可以得到，在一臺3G主頻CPU，1G內存的普通機器上，Linux的文件Cache完全命中的時候擁有每秒1G的速率，如果加上內存分配的開銷，則會在500M每秒上下。在已有的文獻中1, 13, 14, 15, 16, 17，緩存可以劃分為三種，即三級緩存策略： 圖表 16 三級緩存策略我們在2.1.5中可以看到，索引中存儲了不同類型的信息（文檔號，位置偏移量，附加信息）等。同時，在2.1.6中我們可以看到，索引的檢索模塊一般的行為會對文檔號部分進行順序的訪問，而對位置偏移等信息采用跳躍式的訪問，所以我們可以針

53、對它們的行為上的差別，給出不同的緩存策略。對于文檔號列表，需要預讀大量的數據，而對于其余信息，可以在計算時讀取，盡量減少無用數據的拷貝。對于一次求交操作，數據讀取行為是： l 將需要求交的索引詞的的文檔號信息進行讀取，可以預估需要使用的量，比如對于兩個常見的索引詞的求交（比如“中國”“人民”），我們一般不需要取出所有的文檔號列表就可以完成這一次計算。 l 在文檔求交結束后，我們得到了需要進行計算的信息后，再去取對應的位置偏移信息和附加信息。 因此，我們對于上面兩種操作模式采用不同的緩存策略，對于文檔號信息，我們可以使用自己構造的緩存空間和緩存策略；對于其余信息，我們可以交給Linux的系統緩存

54、來處理。 Linux系統本身提供了繞過系統緩存的方式，使用直接IO（DirectIO）讀寫構造自己的緩存空間，即直接將讀取的數據放入用戶態空間。這樣的話，我們在使用緩存的時候，相比與使用系統緩存，一般會減少了兩個操作：1 內存分配操作（在用戶態空間分配） 2 內存拷貝操作（將內核態的緩存空間拷貝到用戶態）。索引的緩存是只讀緩存，我們不需要對其進行修改，不需要處理臟數據寫回等問題，索引緩存的調度相對來說較為簡單，通常的LRU算法都可以有效的工作。 緩存可以對系統有多大的性能提升呢？在上面的一系列文獻中作了不同的試驗進行驗證。其中給出了的較好試驗結果表明，在緩存了磁盤索引大概30%的情況下，就可以

55、達到90%左右的緩存命中。這樣的話，大量緩慢的磁盤IO就可以被避免，我們將在3.3節進一步討論性能方面的內容。2.3 動態索引 在很多的系統中，需要動態索引的需求6, 8, 21，比如： 1. 快速更新：例如新聞，博客等實效性很強的數據，需要很快的進行檢索。用戶往往希望看到最近的內容（比如最近一小時），超過一天的數據對用戶來說，意義會大大降低。所以，當我們獲取了最新的數據的時候，如何快速更新，是一個非常重要的問題。 2. 不間斷服務：對于靜態索引來說，如果需要實現不間斷服務，應該采用創建和檢索數據分離，數據更新創建后，進行數據切換的方式。對于較大的數據量索引更新來說，這樣的方式是可取的，但是對于少量快速的數據更新來說，這樣的數據切換方式會有較高的復雜性。 我們通過借鑒數據庫中版本控制的方式，使用類似“讀者-寫者”方式實現動態索引。 圖表 17 索引創建和服務分離2.3.1 版本