HubbleDotNet 分布式检索算法介绍 (一)

作者：eaglet

转载请注明出处

全文索引的分布式检索粗想想似乎很简单，感觉就是把多个接入点搜索出来的数据做个合并排序就可以，但如果想要做好，满足商业应用要求，这里面涉及到很多算法优化的问题，比如多路排序的优化，动态路由，翻页的优化，通讯的优化，分发复制，冗余和故障转移等等。从今天开始，我将逐步讲解HubbleDotNet 在分布式检索方面的众多算法考虑。

由于涉及的算法很多，无法在一篇全部阐述，我打算采用由浅入深的思路，先从比较简单的算法开始。本文将介绍翻页的优化技术。

目前支持分布式查询的开源搜索技术有很多。最常见的比如  solr . solr 实际上是把 lucene 做成了服务形式，其分布式查询在处理翻页时采用的方法如下：

假设每页为10条记录，3台机器做分布式查询（以下不特别说明，都按这个假设讨论)

如果我们要查第二页数据即第11-20 条记录，solr 的做法是分别向3个服务器查询前20条记录，然后对查询到的这20×3 = 60 条记录归并排序，找到这些记录中的第11-20条用于显示。

这个算法思路简单，但存在很大问题。

问题1：

每次翻页都要向每台索引服务器查询一遍

通常情况下，用户在搜索内容时都是顺序翻页的，即从第一页往下顺序翻的，这个算法无法设计缓存来减轻索引服务器的压力。

问题2：

越往后翻页，索引服务器的压力越大

如果我们是查第99页，即第991-1000 条记录，那么这个算法需要从三台机器分布读出1000条记录才能完成，对于每台机器的压力很大。

问题3：

越往后翻页，归并排序的压力越大。

大型搜索引擎往往是由上百台甚至上千台机器组成的分布式集群，如果按这个算法来进行翻页，假设1000台机器，查询第99页时，合并的服务器就会得到 1000 * 1000 = 100万条记录，

要对这100万条记录进行归并排序，对合并服务器来说压力过大。对系统的可伸缩性设计是一种极大的破坏。

HubbleDotNet 在做分布式查询的算法设计时，考虑到这些问题，下面我就谈谈hubbledotnet 采用怎样的算法来解决这些问题。

首先我们先讨论顺序翻页的问题

还是以上面的假设，我们有3台索引服务器。用户已经查询了第一页，即前10条记录。

对于前10条记录的查询，我们还是按照 solr 的方法，分布向3台服务器查询前10条记录。这时我们实际上已经有了30条记录。我们把这30条记录做一个缓存。当用户翻到第二页时，我们实际上只要得到整个系统中的前20条记录就可以，而我们手上已经有了30条记录，那么我们是否可以利用这30条记录呢？

这里存在两种情况：

第一种情况：整个系统的前20条记录全部包含在之前我们已经得到的这30条记录内。如果是这个情况，那么我们只要在合并服务器的缓存中把这个30条记录读出来，并取出第11-20 条记录就可以了。索引服务器没有任何压力。

比如 A,B,C 三台索引服务器。查第一页时，从这三台服务器得到的结果集分别是

A {10,9,8,7,6,5,4,3,2,1}

B {10,9,8,7,6,5,4,3,2,1}

C {10,9,8,7,6,5,4,3,2,1}

那么这个系统的前20条记录为

10,10,10,9,9,9,8,8,8,7,7,7,6,6,6,5,5,5,4,4

这种情况下，第11-20 条记录包含于前30条记录内，直接从缓存读取，不触发分布式查询。

第二种情况：整个系统的前20条记录部分包含在之前我们已经得到的这30条记录内。

比如 A,B,C 三台索引服务器。查第一页时，从这三台服务器得到的结果集分别是

A {18,17,1615,14,13,12,11,10,9}

B {10,9,8,7,6,5,4,3,2,1}

C {10,9,8,7,6,5,4,3,2,1}

那么根据这个结果集，我们只能得到前14条记录，即

18,17,1615,14,13,12,11,10,10,10,9,9,9

当我们要取第15条记录时，结果集A中已经全部取完，我们不知道结果集A的第11条记录是什么，所以我们无法确定第15条记录到底是结果集A的第11条记录，还是结果集B或C的第3条记录。

那么这个时候我们就需要发起查询了，但我们是不是必须要对所有的索引服务器按 sorl 的方法分别查前20条记录呢？这个是完全没有必要的。这个里面有个数学上的问题，其实很简单的原理，由于不是写论文，我还是以上面这个例子来说明，这样比较容易理解。当前情况下，我们已经得到了14条记录，我们需要得到20条记录，那么我们还差6条记录，那么就是所有结果集必须要贡献至少6条记录。

对于结果集A，由于已经查完了，所以我们需要向A服务器查询第11-16条记录，从而使结果集A可以贡献出6条记录。

而对于结果集B和C，当前剩余8条记录，不需要查询就可以贡献出6条记录。所以这种情况下，我们只需要向A再查询6条记录就可以满足要求。

由此可见这种算法的设计可以大大减轻对索引服务器查询的压力，而且合并服务器上也不会产生太多的数据，减轻了合并服务器的归并排序上的压力和内存的开销。

基本算法以及说完。我们再看看直接跳跃查询的问题

这种情况发生的概率较小，就是用户直接查询后面的页，这种情况下由于没有缓存数据，我们需要向所有服务器查询。这种情况下我们需要给一个余量，比如100台服务器，要得到前1000条记录，

那么平均每台只要10条记录就可以，但为了尽量保证一次分布式查询可以完成，我们给出一定余量，比如2倍的余量，就是每台服务器查询前20条记录，然后回到上面我们讨论的算法来处理，如果结果集全部包含，就直接返回，否则再发起一次查询。在实际应用中，这个余量多少受各个服务器返回结果集数据的分布规律决定。

写到这里，HubbleDotNet 的翻页的算法基本介绍完毕，上面的阐述其实还不够完备，还有一个小问题就是结果集容量问题，比如A如果总容量只有12条记录怎么办？这个问题其实也很容易解决，这里就不多讨论了，留给大家自己思考吧。

返回 HubbleDotNet开源全文搜索数据库项目--技术详解