IT技术博客大学习 共学习 共进步

框计算垂直搜索之索引篇

搜索研发部官方博客 2011-06-21 13:38:58 浏览 3,062 次

阿拉丁的索引服务适用于所有需要文本或者半文本检索的资源,例如招聘资源需要能够在“职位名称”以及“公司名称”里检索出查询词:

因为阿拉丁内部资源比较多,所以在索引设计时需要考虑到不同资源的需求,这里面至少有两个因素需要考虑,一个是时效性,另一个是数据量。

时效性指的是一个资源的数据从修改到生效需要的时间,时效性高表示生效时间短,有的资源甚至需要立即生效;而生效时间长的资源也会分成很多档次,有小时级的,有天级的,甚至有更长时间的静态资源。数据量指的是一个资源的数据规模,从最小的数千条到千万级甚至亿级,不同数据量级别的资源会用不同的方式进行索引构建以及索引检索。以下简单列举了不同时效性和数据量条件下的索引方式:

时效性高 时效性低
数据量小 实时内存索引 周期性文件索引
数据量大 实时混合索引 分布式文件索引

实时索引需要实时支持索引的增加以及删除操作,更新操作可以看作是删除操作和增加操作的组合。对于数据量小的资源,可以将索引完全放入内存,在内存中建立倒排和用于屏蔽的bit vector,增加操作可以直接在索引拉链的末端添加新的doc_id,注意这里的doc_id是全局分配的,保证索引拉链按照doc_id的升序排序;删除操作比较简单,直接在bit vector里设置屏蔽位即可。对于数据量比较大的资源,由于索引无法完全放入内存,需要建立文件索引,但由于文件索引的紧致压缩的特点,无法实时地在倒排拉链中添加doc_id,在这种情况下,解决时效性问题可以有两种办法,一种是尽量缩短建索引时间,例如基于map-reduce的分布式建库技术可以将千万级别的建库时间缩短到10分钟以内,这种索引我们称为伪实时索引;另一种比较复杂的方式是混合索引,即索引的增量部分存于内存中,在检索时需要将内存索引和文件索引合并,这种方式在做检索时处理较复杂,所以在阿拉丁主要采用的还是伪实时索引方式处理大数据量、高时效性资源数据。

对时效性低的数据也有不同的处理方式,对于数据量比较小的资源,单机索引能完全涵盖,此时只需要周期性的构建索引然后进行索引切换就可以了;对于大数据量的资源,单机索引无法涵盖,索引必须分布到多台机器上,分布方式有按term切分以及按照doc_id切分两种方式,阿拉丁现在是按照doc_id进行切分,一个doc对应的所有term都会分布到同一台机器上。分布式索引的主要困难是检索流程比较复杂,需要将query分发到多台索引机上,然后对返回的多个结果进行整合,这里还要处理单台或多台索引机失效重查的情况。

最后简单谈一下阿拉丁的索引构建流程。对实时内存索引,增加、删除索引都是实时流,但是频繁索引修改会导致索引拉链碎片增多,需要有专门的任务定时整理索引拉链,一方面是清理碎片,紧致排列索引拉链;另一方面也需要对过长的拉链进行截断。对文件索引,使用分布式建库是个非常高效的方法,阿拉丁的文件索引建库主要是采用这种方式。文件索引由于是静态的,能够采用多种压缩算法进行处理,当然这种压缩并不一定是极致压缩,需要取得磁盘读取效率和CPU占用之间的平衡。另外,由于文件索引的读取效率相对于内存仍然很低,为尽量提高效率,阿拉丁主要采用了两种办法解决,一种是使用flash卡代替磁盘,尽量提高磁盘读取速率;另一种是使用缓存,缓存使用LRU算法,将最常访问的拉链放在内存中,检索时可以直接从内存中取数据,减少对磁盘的访问。

建议继续学习

  1. 由浅入深探究mysql索引结构原理、性能分析与优化 (阅读 16,121)
  2. 浅谈MySQL索引背后的数据结构及算法 (阅读 11,381)
  3. 由浅入深理解索引的实现(2) (阅读 7,521)
  4. HBase二级索引与Join (阅读 6,860)
  5. 如何建立合适的索引? (阅读 6,662)
  6. mysql查询中利用索引的机制 (阅读 6,581)
  7. InnODB和MyISAM索引统计集合 (阅读 6,081)
  8. Innodb 表和索引结构 (阅读 6,041)
  9. MySQL索引背后的数据结构及算法原理 (阅读 5,620)
  10. mysql索引浅析 (阅读 5,180)