注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

断尘居

温柔的男人像海洋。

 
 
 
 
 

日志

 
 

Lucene索引过程分析(3)  

2011-12-22 16:51:31|  分类: Lucene |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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的关系如下图:

 

  评论这张
 
阅读(570)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017