Lucene学习总结之四：Lucene索引过程分析(3)

5、DocumentsWriter对CharBlockPool，ByteBlockPool，IntBlockPool的缓存管理

• 在索引的过程中，DocumentsWriter将词信息(term)存储在CharBlockPool中，将文档号(doc ID)，词频(freq)和位置(prox)信息存储在ByteBlockPool中。
• 在ByteBlockPool中，缓存是分块(slice)分配的，块(slice)是分层次的，层次越高，此层的块越大，每一层的块大小事相同的。
  • nextLevelArray表示的是当前层的下一层是第几层，可见第9层的下一层还是第9层，也就是说最高有9层。
  • levelSizeArray表示每一层的块大小，第一层是5个byte，第二层是14个byte以此类推。

ByteBlockPool类中有以下静态变量：

final static int[] nextLevelArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 9};
final static int[] levelSizeArray = {5, 14, 20, 30, 40, 40, 80, 80, 120, 200};

• 在ByteBlockPool中分配一个块的代码如下：

 

//此函数仅仅在upto已经是当前块的结尾的时候方才调用来分配新块。

public int allocSlice(final byte[] slice, final int upto) {

  //可根据块的结束符来得到块所在的层次。从而我们可以推断，每个层次的块都有不同的结束符，第1层为16，第2层位17，第3层18，依次类推。

  final int level = slice[upto] & 15;

  //从数组总得到下一个层次及下一层块的大小。

  final int newLevel = nextLevelArray[level];

  final int newSize = levelSizeArray[newLevel];

  // 如果当前缓存总量不够大，则从DocumentsWriter的freeByteBlocks中分配。

  if (byteUpto > DocumentsWriter.BYTE_BLOCK_SIZE-newSize)

    nextBuffer();

  final int newUpto = byteUpto;

  final int offset = newUpto + byteOffset;

  byteUpto += newSize;

  //当分配了新的块的时候，需要有一个指针从本块指向下一个块，使得读取此信息的时候，能够在此块读取结束后，到下一个块继续读取。

  //这个指针需要4个byte，在本块中，除了结束符所占用的一个byte之外，之前的三个byte的数据都应该移到新的块中，从而四个byte连起来形成一个指针。

  buffer[newUpto] = slice[upto-3];

  buffer[newUpto+1] = slice[upto-2];

  buffer[newUpto+2] = slice[upto-1];

  // 将偏移量(也即指针)写入到连同结束符在内的四个byte

  slice[upto-3] = (byte) (offset >>> 24);

  slice[upto-2] = (byte) (offset >>> 16);

  slice[upto-1] = (byte) (offset >>> 8);

  slice[upto] = (byte) offset;

  // 在新的块的结尾写入新的结束符，结束符和层次的关系就是(endbyte = 16 | level)

  buffer[byteUpto-1] = (byte) (16|newLevel);

  return newUpto+3;

}

• 在ByteBlockPool中，文档号和词频(freq)信息是应用或然跟随原则写到一个块中去的，而位置信息(prox)是写入到另一个块中去的，对于同一个词，这两块的偏移量保存在IntBlockPool中。因而在IntBlockPool中，每一个词都有两个int，第0个表示docid + freq在ByteBlockPool中的偏移量，第1个表示prox在ByteBlockPool中的偏移量。
• 在写入docid + freq信息的时候，调用termsHashPerField.writeVInt(0, p.lastDocCode)，第一个参数表示向此词的第0个偏移量写入；在写入prox信息的时候，调用termsHashPerField.writeVInt(1, (proxCode<<1)|1)，第一个参数表示向此词的第1个偏移量写入。
• CharBlockPool是按照出现的先后顺序保存词(term)
• 在TermsHashPerField中，有一个成员变量RawPostingList[] postingsHash，为每一个term分配了一个RawPostingList，将上述三个缓存关联起来。

 

abstract class RawPostingList {

  final static int BYTES_SIZE = DocumentsWriter.OBJECT_HEADER_BYTES + 3*DocumentsWriter.INT_NUM_BYTE;

  int textStart; //此词在CharBlockPool中的偏移量，由此可以知道是哪个词。

  int intStart; //此词在IntBlockPool中的偏移量，在指向的位置有两个int，一个是docid + freq信息的偏移量，一个是prox信息的偏移量。

  int byteStart; //此词在ByteBlockPool中的起始偏移量

}

static final class PostingList extends RawPostingList {

  int docFreq;                                    // 此词在此文档中出现的次数

  int lastDocID;                                  // 上次处理完的包含此词的文档号。

  int lastDocCode;                                // 文档号和词频按照或然跟随原则形成的编码

  int lastPosition;                               // 上次处理完的此词的位置

}

这里需要说明的是，在IntBlockPool中保存了两个在ByteBlockPool中的偏移量，而在RawPostingList的byteStart又保存了在ByteBlockPool中的偏移量，这两者有什么区别呢？

在IntBlockPool中保存的分别指向docid+freq及prox信息在ByteBlockPool中的偏移量是主要用来写入信息的，它记录的偏移量是下一个要写入的docid+freq或者prox在ByteBlockPool中的位置，随着信息的不断写入，IntBlockPool中的两个偏移量是不断改变的，始终指向下一个可以写入的位置。

RawPostingList中byteStart主要是用来读取docid及prox信息的，当索引过程基本结束，所有的信息都写入在缓存中了，那么如何找到此词对应的文档号偏移量及位置信息，然后写到索引文件中去呢？自然是通过RawPostingList找到byteStart，然后根据byteStart在ByteBlockPool中找到docid+freq及prox信息的起始位置，从起始位置开始的两个大小为5的块，第一个就是docid+freq信息的源头，第二个就是prox信息的源头，如果源头的块中包含了所有的信息，读出来就可以了，如果源头的块中有指针，则沿着指针寻找到下一个块，从而可以找到所有的信息。

• 下面举一个实例来表明如果进行缓存管理的：

此例子中，准备添加三个文件：

file01: common common common common common term

file02: common common common common common term term

file03: term term term common common common common common

file04: term

(1) 添加第一篇文档第一个common

• 在CharBlockPool中分配6个char来存放"common"字符串
• 在ByteBlockPool中分配两个块，每个块大小为5，以16结束，第一个块用来存放docid+freq信息，第二个块用来存放prox信息。此时docid+freq信息没有写入，docid+freq信息总是在下一篇文档的处理过程出现了"common"的时候方才写入，因为当一篇文档没有处理完毕的时候，freq也即词频是无法知道的。而prox信息存放0，是因为第一个common的位置为0，但是此0应该左移一位，最后一位置0表示没有payload存储，因而0<<1 + 0 = 0。
• 在IntBlockPool中分配两个int，一个指向第0个位置，是因为当前没有docid+freq信息写入，第二个指向第6个位置，是因为第5个位置写入了prox信息。所以IntBlockPool中存放的是下一个要写入的位置。

 

 

(2) 添加第四个common

• 在ByteBlockPool中，prox信息已经存放了4个，第一个0是代表第一个位置为0，后面不跟随payload。第二个2表示，位置增量(差值原则)为1，后面不跟随payload(或然跟随原则)，1<<1 + 0 =2。第三个第四个同第二个。

 

 

(3) 添加第五个common

• ByteBlockPool中，存放prox信息的块已经全部填满，必须重新分配新的块。
• 新的块层次为2，大小为14，在缓存的最后追加分配。
• 原块中连同结束位在内的四个byte作为指针(绿色部分)，指向新的块的其实地址，在此为10.
• 被指针占用的结束位之前的三位移到新的块中，也即6, 7, 8移到10, 11, 12处，13处是第五个common的prox信息。
• 指针的值并不都是四个byte的最后一位，当缓存很大的时候，指针的值也会很大。比如指针出现[0, 0, 0, -56]，最后一位为负，并不表示指向的负位置，而是最后一个byte的第一位为1，显示为有符号数为负，-56的二进制是11001000，和前三个byte拼称int，大小为200也即指向第200个位置。比如指针出现[0, 0, 1, 2]，其转换为二进制的int为100000010，大小为258，也即指向第258个位置。比如指针出现
  [0, 0, 1, -98]，转换为二进制的int为110011110，大小为414，也即指向第414个位置。

 

 

(4) 添加第一篇文档，第一个term

• CharBlockPool中分配了5个char来存放"term"
• ByteBlockPool中分配了两个块来分别存放docid+freq信息和prox信息。第一个块没有信息写入，第二个块写入了"term"的位置信息，即出现在第5个位置，并且后面没有payload，5<<1 + 0 = 10。
• IntBlockPool中分配了两个int来指向"term"的两个块中下一个写入的位置。

 

 

(5) 添加第二篇文档第一个common

• 第一篇文档的common的docid+freq信息写入。在第一篇文档中，"common"出现了5次，文档号为0，按照或然跟随原则，存放的信息为[docid<<1 + 0, 5] = [0, 5]，docid左移一位，最后一位为0表示freq大于1。
• 第二篇文档第一个common的位置信息也写入了，位置为0，0<<1 + 0 = 0。

 

 

(6) 添加第二篇文档第一个term

• 第一篇文档中的term的docid+freq信息写入，在第一篇文档中，"term"出现了1次，文档号为0，所以存储信息为[docid<<1 + 1] = [1]，文档号左移一位，最后一位为1表示freq为1。
• 第二篇文档第一个term的prox信息也写入了，在第5个位置，5<<1 + 0 = 10。
• 第二篇文档中的5个common的prox信息也写入了，分别为从14到18的[0, 2, 2, 2, 2]

 

 

(7) 添加第三篇文档的第一个term

• 第二篇文档的term的docid+freq信息写入，在第二篇文档中，文档号为1，"term"出现了2次，所以存储为[docid<<1 + 0, freq] = [2, 2]，存储在25, 26两个位置。
• 第二篇文档中两个term的位置信息也写入了，为30, 31的[10, 2]，也即出现在第5个，第6个位置，后面不跟随payload。
• 第三篇文档的第一个term的位置信息也写入了，在第0个位置，不跟payload，为32保存的[0]

 

 

(8) 添加第三篇文档第二个term

• term的位置信息已经填满了，必须分配新的块，层次为2，大小为14，结束符为17，也即图中34到47的位置。
• 30到33的四个byte组成一个int指针，指向第34个位置
• 原来30到32的三个prox信息移到34到36的位置。
• 在37处保存第三篇文档第二个term的位置信息，位置为1，不跟随payload，1<<1 + 0 = 2。

 

 

(9) 添加第三篇文档第四个common

• 第二篇文档中"common"的docid+freq信息写入，文档号为1，出现了5次，存储为[docid << 1 + 0, freq]，docid取差值为1，因而存储为 [2, 5]，即2，3的位置。
• 第三篇文档中前四个common的位置信息写入，即从19到22的[6, 2, 2, 2]，即出现在第3个，第4个，第5个，第6个位置。
• 第三篇文档中的第三个"term"的位置信息也写入，为38处的[2]。

 

 

(10) 添加第三篇文档的第五个common

• 虽然common已经分配了层次为2，大小为14的第二个块(从10到23)，不过还是用完了，需要在缓存的最后分配新的块，层次为3，大小为20，结束符为18，也即从48到67的位置。
• 从20到23的四个byte组成一个int指针指向新分配的块。
• 原来20到22的数据移到48至50的位置。
• 第三篇文档的第五个common的位置信息写入，为第51个位置的[2]，也即紧跟上个common，后面没有payload信息。

 

 

(11) 添加第四篇文档的第一个term

• 写入第三篇文档的term的docid+freq信息，文档号为2，出现了三次，存储为[docid<<1+0, freq]，docid取差值为1，因而存储为[2, 3]。
• 然而存储term的docid+freq信息的块已经满了，需要在缓存的最后追加新的块，层次为2，大小为14，结束符为17，即从68到81的位置。
• 从25到28的四个byte组成一个int指针指向新分配的块。
• 原来25到26的信息移到68, 69处，在70, 71处写入第三篇文档的docid+freq信息[2, 3]

 

 

(12) 最终PostingList， CharBlockPool， IntBlockPool，ByteBlockPool的关系如下图：

 

 

评论

4 楼 背着家走 2012-06-28  

parabellum_sky 写道

有些看不明白，看来还是功底不够啊～惭愧惭愧。继续努力！

其实 在前几篇 我已经开始力不从心了...

3 楼 qq85166724 2011-07-01  

        

2 楼 lianj_lee 2011-03-18  

好多地方没能明白!

1 楼 parabellum_sky 2010-07-12  

有些看不明白，看来还是功底不够啊～惭愧惭愧。继续努力！