上接《 索引創建 (2)：DocumentWriter處理流程三 》

?

1.4 索引數據池存儲細節

?

倒排索引(token->posting list)表的數據信息在內存中并不是直接存儲在postingsHash中的，而是存放在三大數據緩沖池中 —— CharBlockPool，ByteBlockPool，IntBlockPool 。 這三個池均都由若干個固定長度的buffer數組構成。DocumentsWriter對它們進行管理和維護(包括分配新的塊或者回收不用的塊的操作)，以達到節省內存和提高效率的作用。

?

◆ 三大索引數據池

?

1、 token字符數據緩沖池—— CharBlockPool

?

? ? CharBlockPool 用于存儲token的字符串信息。比如 token="lucene"。其在內存中的表示其實就是多個buffer[]組成的緩沖池buffers[][]。緩沖池初始大小為10*16384個 字符空間，每一次可擴展1.5倍。

    final class CharBlockPool {
  //緩沖池buffers，初始化時緩沖池由10個buffer數組組成，每一個buffer的大小為固定16384（2^14）
  public char[][] buffers = new char[10][];
  //緩沖池中buffer的數量
  int numBuffer;
  //目前我們所使用的第bufferUpto號buffer數組,初始值-1表示緩沖池還沒有開辟任何buffer容量
  int bufferUpto = -1;  
  //表示當前buffer中可以使用的位置序號
  public int charUpto = DocumentsWriter.CHAR_BLOCK_SIZE;            
  //表示當前緩沖池中可以使用的buffer數組
  public char[] buffer; 
  //表示當前buffer頭位置的偏移 
  public int charOffset = -DocumentsWriter.CHAR_BLOCK_SIZE;    
  
  final private DocumentsWriter docWriter;

  public CharBlockPool(DocumentsWriter docWriter) {
    this.docWriter = docWriter;
  }
  //回收緩沖池
  public void reset() {
	//通過DocumentWriter回收緩沖池的全部buffer數組
    docWriter.recycleCharBlocks(buffers, 1+bufferUpto);
    bufferUpto = -1;
    charUpto = DocumentsWriter.CHAR_BLOCK_SIZE;
    charOffset = -DocumentsWriter.CHAR_BLOCK_SIZE;
  }
  //在緩沖池中開辟新的buffer
  public void nextBuffer() {
	//當前開辟的buffer數量已經達到了緩沖池buffers允許的最大buffer量。
    if (1+bufferUpto == buffers.length) {
    	//擴大1.5倍緩沖池buffers容量，也就是最大允許的buffer數量擴大1.5倍
        char[][] newBuffers = new char[(int) (buffers.length*1.5)][];
        //拷貝原緩沖池數據
        System.arraycopy(buffers, 0, newBuffers, 0, buffers.length);
        buffers = newBuffers;
    }
    //則通過DocumentWriter分配一個新的buffer數組
    buffer = buffers[1+bufferUpto] = docWriter.getCharBlock();
    bufferUpto++;
    charUpto = 0;
    charOffset += DocumentsWriter.CHAR_BLOCK_SIZE;
  }
}
  

?

2、 token的docID，詞頻和位置信息緩沖池—— ByteBlockPool

?

??? ByteBlockPool 用于存儲token所在的文檔，詞頻和位置信息。其內存結構與CharBlockPool相同，也是一個buffers[][]二維數組。但是ByteBlockPool緩沖池中的buffer采用了分片(slice)分配方式。每片(slice)的大小由nextLevelArray和levelSizeArray來確定。

    //表示當前層的下一層是第幾層，第9層的以后所有層都是第9層，也就是說最大的slice容量為200
final static int[] nextLevelArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 9};
//表示該層的大小，也就是slice的容量
final static int[] levelSizeArray = {5, 14, 20, 30, 40, 40, 80, 80, 120, 200};
//第一個開辟的slice的初始層次為0，初始容量為5
final static int FIRST_LEVEL_SIZE = levelSizeArray[0];
  

舉個例子說明上面的層次與slice開辟的空間大小的關系。假如在buffer中開辟第一個slice，那么這個slice初始為第0層，容量為levelSizeArray[0]=5 bytes。那么下一個slice的大小怎么確定呢？當前已經開辟的slice在第0層，那么下一個slice就是在第nextLevelArray[0]層，即第1層。其大小為levelSizeArray[1]=14bytes。依次類推：第三個slice的大小為20bytes.... 第九個slice以后的大小全部都是200bytes。

?

我們下面來看看ByteBlockPool分片分配的源代碼：

    final class ByteBlockPool {

  //在buffer中開辟一個指定大小的slice片
  public int newSlice(final int size) {
	//buffer[]的大小為BYTE_BLOCK_SIZE=32768（2^15）
    //如果buffer中空閑空間不夠slice的大小，則開辟一個新的buffer
    if (byteUpto > DocumentsWriter.BYTE_BLOCK_SIZE-size)
        nextBuffer();
    //存儲本次創建的slice在buffer中的初始位置
    final int upto = byteUpto;
    //存儲buffer中空閑區域的初始位置
    byteUpto += size;
    //slice與slice之間的分割標志，即塊以16結束
    buffer[byteUpto-1] = 16;
    return upto;
  }


  //在buffer中分配一個新的片(slice),此方法僅僅在upto已經是當前塊的結尾的時候方才調用來分配新片。
  public int allocSlice(final byte[] slice, final int upto) {

    //可根據上一個slice的結束符來得到要分批的新slice所在的層數，以確定slice的大小
    //從而我們可以推斷，每個層次的slice都有不同的結束符，第1層為16，第2層位17，第3層18，依次類推。
    final int level = slice[upto] & 15;
    //獲得新的層數，從而得到新的片的大小
    final int newLevel = nextLevelArray[level];
    final int newSize = levelSizeArray[newLevel];
    //如果buffer中空閑空間不夠slice的大小，則開辟一個新的buffer
    if (byteUpto > DocumentsWriter.BYTE_BLOCK_SIZE-newSize)
      nextBuffer();
    
    final int newUpto = byteUpto;
    final int offset = newUpto + byteOffset;
    byteUpto += newSize;

    //將上一個slice的倒數第2-4個字節復制到新slice中的前3個字節，然后把新開辟的slice的初始位置記錄在上一個slice的最后四個字節中
    //具體的做法我們將用下面細節中例子詳細闡明
    buffer[newUpto] = slice[upto-3];
    buffer[newUpto+1] = slice[upto-2];
    buffer[newUpto+2] = slice[upto-1];
    slice[upto-3] = (byte) (offset >>> 24);
    slice[upto-2] = (byte) (offset >>> 16);
    slice[upto-1] = (byte) (offset >>> 8);
    slice[upto] = (byte) offset;
        
    // 在新slice的結尾寫入新的結束符，結束符和層次的關系就是(endbyte = 16 | level)
    buffer[byteUpto-1] = (byte) (16|newLevel);
    // 返回新slice可以使用的容量在buffer中的初始位置序號
    // newUpto+3 是因為新slice的前三個字節存儲了上一個slice的倒數2-4個字節中的數據。
    return newUpto+3;
  }
}
  

?

3、 ByteBlockPool 片地址信息緩沖池—— IntBlockPool

?

?????? IntBlockPool的職責就是用來記錄ByteBlockPool中slice在buffer中的位置序號。每一個token都會有兩種信息同時存儲在ByteBlockPool的slice中。也就是說每一次ByteBlockPool都會同時分配兩個相同大小的slice，一個用來存儲docID+詞頻；另一個用來存儲位置信息。而這兩個塊的初始位置序號都會同時記錄在IntBlockPool中的。

?

?????? IntBlockPool在內存中的結構與CharBlockPool完全一樣，這里就不詳細介紹了。

?

◆ 索引存儲的數據細節

?

在《 索引創建(4)：DocumentWriter 處理流程三 》中，我們對存儲在三大數據池中的數據格式還沒有深刻的了解。在這里，我們要詳細探究倒排索引表中的數據信息是如何存儲在這些數據池中的？這些重要信息包括：token字符串、所在文檔詞頻、所在文檔的docID、所在文檔的位置。

?

我們用一個例子來說明整個過程:

DOC1:??? lucene lucene lucene lucene lucene term .?

DOC2:??? lucene lucene lucene lucene lucene term term.

DOC3:??? term term term lucene lucene lucene lucene lucene.

DOC4:??? term

然后我們一個一個token的加入倒排索引，觀察PostingList結構和三大數據池的變化

?

1、加入DOC1中的第一個lucene (docID=0, postion=0)

????? 由于lucene是第一個token，索引中原來沒有這個詞，因此會在CharBlockPool中的buffer[]上分配6個char來存放"lucene"字符串，并將CharBlockPool中分配的6個char空間的首地址偏移記錄在P.testStart中。

?

????? 在ByteBlockPool中分配兩個slice，每個slice最初大小為5，以byte=16結束。第一個slice用來存放docID+freq信息，第二個slice用來存放position信息。但是有兩點要注意一下：

????? (1) 當前token的docID+freq并不會立刻寫進第一個slice。只是在內存中進行freq++而已。直到處理下一篇文檔DOC2中出現了相同的token的時候，才會把上一篇DOC1中該token的docID+freq寫入(因為在當前DOC1文檔中，是否后面還會繼續加入相同token，只有當前文檔結束以后才好統計詞頻)。

?????? (2) 當前token的position信息表明了token所在文檔的詞語位置。但是存入ByteBlockPool的第二個slice中的數據時經過差值存儲技術(該技術涉及到存儲優化，將在后續中講到)的。也就是說假如當前token的position值：curPos=1。而在上一次出現了相同的token的position值：lastPos=0(這個值記錄在P.lastPosition中)。則當前token記錄在ByteBlockPool的position數據為：prox=(curPos-lastPos)<<1=2。

??????? 這兩點要明確，后面不再過多講述。如果是第一次出現的token，則存儲在ByteBlockPool第二個slice的prox值為：0<<1=0

?

??????? 在IntBlockPool中分配兩個int空間，一個存儲ByteBlockPool第一個slice的位置，目前值為0。因為當前沒有docid+freq信息寫入。第二個存儲ByteBlockPool的第二個slice的初始位置+1，即值為6。因為第5個位置寫入了當前token的prox信息。所以IntBlockPool中存放的是下一個要寫入的位置。

?

??????? 加入第一個lucene之后，要注意p.lastPosition記錄了此次token的position值。一遍一下次加入相同的token的時候，方便差值存儲下一個position值。

?

?

2、加入DOC1中的第二個lucene (docID=0, postion=1)

?

倒排索引結構postingHash中已經有了lucene，因此第二次加入的lucene將不會在CharBlockPool中重新分配空間。而只是讓freq++(但還是不寫入ByteBlockPool，因為還沒有進入下一篇DOC)。并且在ByteBlockPool第二個slice中的IntBlockPool[1]=6位置上加入第二個lucene的prox=(position-lastPosition)<<1=2。然后讓IntBlockPool[1]++。指向下一次prox信息記錄的空閑空間。最后lastPosition=1。記錄下此次加入相同token的位置。

?

3、繼續加入DOC1中的后續token，直到加入完第四個lucene (docID=0, position=3)

?

?

4、加入DOC1中第五個Lucene(docID=0, position=4)

?

此時我們發現，在加入第四個Lucene之后。IntBlockPool[1]=9指向了ByteBlockPool的第二slice結束符16。說明ByteBlockPool開辟的片已經不夠用了。此時會調用ByteBlockPool.allocSlice()方法，分配一個新的slice，容量大小為14(levelSizeArray[1])。然后將原來slice中連同結束位在內的四個byte作為指針(下圖綠色部分)，指向新的slice的地址(下圖第10個位置)。即把6,7,8三個位置上的值記錄在10,11,12上，第9個位置上原來的分隔符16賦值為新slice的初始地址10。新加入的第5個lucene的prox將賦值在第13個位置上。

?

很顯然，下圖綠色部分的內容實際上就是新開辟的slice的初始地址。目前的緩存數據很小，只需要最后一個byte就可以存儲。如果新開辟的slice初始位置數據很大，怎可能就需要4個byte了。比如，綠色部分存儲的值為[0,0,1,1]，則表示的值為100000001=257。即新開辟的slice初始位置在buffer[257]上。

?

5、加入DOC1中第一個 term (docID=0, position=5)

?

此時添加的"term"是一個新詞，因此在postingHash中需要開辟一個新的PostingList用于存放"term"的相關信息。而且同時在CharBlockPool、IntBlockPool、ByteBlockPool中都開辟了新的空間(過程與第一次加入“lucene”相同)。另外、term的prox=position<<1=10(“term"第一個加入的新詞，因此沒有lastPosition)。

?

?

6、加入DOC2中第一個 lucene (docID=1, position=0)

?

????? 此時，當出現了DOC2中的lucene的時候，說明DOC1的所有”lucene“都處理完了，這個時候就可以把DOC1中"lucene"的詞頻和docID(在此之前一直都存放在內存中"lucene"的PostingList對象中)全部寫入ByteBlockPool中的IntBlockPool[0]所指的位置了(注意到下圖紅色箭頭標注ByteBlockPool的第一個slice中的數據)。

?

???? PostingList的很多數據都發生了改變。其中docFreq=1開始記錄在新的文檔中”lucene“的頻率。lastDocCode是DOC2文檔號將要存儲在ByteBlockPool中的數據(lastDocCode=docID<<1)。

?

???? IntBlockPool也發生了變化，指向ByteBlockPool中存儲"lucene"的兩個slice的地址偏移也發生了變化。其中IntBlockPool[0]指向了新的偏移位置2。也就說其他文檔出現lucene的時候，這個位置可以存儲DOC2文檔的lucene的DocCode+freq。

?

????? ByteBlockPool在"lucene"的第一個slice中存儲了DocCode和Freq(這里存儲的不是docID，而是DocCode=docID<<1)。

?

?

7、隨后添加DOC2中的四個“lucene”后，開始 加入DOC2中第一個“term” (docID=1, position=5)

?

DOC2文檔的前五個"lucene"的prox已經寫入了ByteBlockPool的14-18位置，值為{0,2,2,2,2}。

當開始加入DOC2的第一個"term"的時候，情況和上面第一次加入“lucene”的一樣(參見第6點)。會將DOC1中的"term"的docID(docCode=0<<1=0)+freq寫入ByteBlockPool的第24，25的位置上。而當前DOC2的"term"的prox=position<<1=10(因為在DOC2中"term"還是第一次出現)寫入第30個位置上。

8、加入DOC3的第一個"term" (docID=2, position=0)

?

此時需要把DOC2的“term”的docID+freq寫入第26、27位置上。并將當前DOC的"term"的prox=possion<<1=0寫入第32個位置。注意寫入DOC2的docID數據值應該是docCode=docID<<1=1<<1=2

?

?

9、加入DOC3的第二個"term" (docID=2, position=1)

?

發現ByteBlockPool在IntBlockPool[3]=33處位置上的數據位slice分隔符16，說明當前"term"的第二個slice已滿，需要分配一個新的slice。這個過程與"lucene"(上面第4點)相同。新擴大的slice的層次為2，大小為14，結束符為17。而且需要將原slice的最后四位(30-33)變成指針位(指向34)，其中30-32位移動到34-36位處。

?

當前DOC3的第二個"term"的prox=position-lastPosition=1<<1=2，寫入第37號位置。

?

?

10、隨后加入DOC3的第一個"lucene" (docID=2, position=3) ，直到加入DOC3的第四個"lucene" (docID=2, position=6)

?

此時在加入DOC3的第一個"lucene"的時候就已經把DOC2中"lucene"的docID+freq寫入第2、3個位置上，注意docCode=docID<<1=1<<1=2。然后將當前DOC3的第一個"lucene"到第四個"lucene"的prox={6，2，2，2}全部寫入第19-22個位置上。

?

11、加入DOC3的第五個"lucene" (docID=2, position=7)

?

此時ByteBlockPool在IntBlockPool[1]=23的位置上數據是分隔符17，表明"lucene"用于存儲position的第二個slice已經用完，需要重新分配一個新的slice: 層次為3，大小為20，結束符為18，即下圖從48到67的位置。原來slice的20-23的位置變成了指針位(指向新slice的48)，20-22的數據移動到了48-50位上，而且當前DOC3的第五個"lucene"的prox=2記錄到了第51個位置上。

?

12、加入DOC4的第一個"term" (docID=3, position=0)

?

此時加入DOC4的第一個"term"，使得ByteBlockPool在IntBlockPool[2]=28的位置上寫入DOC3的"term"的docID=2，freq=3。但是ByteBlockPool在第28個位置上的值為分隔符16，表明"term"的第一個slice用完，需要分配一個新的slice：層次為2，大小為14，結束符為17，即從68到81的位置。從25到28的四個byte組成一個int指針指向新分配的slice的首地址68。將25-27上的原數據賦值給68-70中，然后將DOC3的"term"的docCode=docID<<1=4和freq=3寫入第71,72的地址上。

?

然后將當前DOC4的"term"的prox=position<<1=0寫入第39的位置上。

?

?

總結

?

????? 經過對Doc1和Doc2建立索引過程中的PostingList和CharBlockPool、IntBlockPool、ByteBlockPool的數據變化我們可以很清楚的看出。Lucene的倒排索引結構在內存中并不是我們想象的那樣：每個token對應一個DocID+Freq的鏈表結構。

?????? 在Lucene中，每個token以字符串作為關鍵字唯一的定位到postingHash這張哈希表中。而哈希表的每個元素都是PostingList對象，PostingList并不是表示docID+freq的鏈表結構。其作用就是為了定位到token信息所存儲的三大數據池中的位置(textStart、byteStart、intStart)以及記錄上一次同一個token加入倒排索引的信息。真正每個token對應的posting結構記錄在ByteBlockPool中。我們來看看下面的圖(DOC1-DOC4的"lucene"和"term"的倒排索引結構)。

?

?

????? 此外，Lucene的docID是用docCode=docID<<1來存儲的，而position是用prox=(position-lastPosition)<<1來存儲的。至于為什么這樣儲存，是考慮到數據的壓縮以降低倒排索引表所消耗的空間代價，具體詳見Lucene的壓縮儲存技術。

?

????? Lucene的這種倒排索引的內存組織結構，非常適合在磁盤中存儲。關于這一點，我們將要在以后Lucene索引文件中詳細提到。

?

?

?

?

【Lucene3.0 初窺】索引創建(5)：索引數據池及內存數據細節