【Lucene3.0 初窥】索引创建(5)：索引数据池及内存数据细节

上接《索引创建 (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索引文件中详细提到。