|
|
|
|
|
# 10 | 索引拆分：大规模检索系统如何使用分布式技术加速检索？
|
|
|
|
|
|
|
|
|
|
|
|
你好，我是陈东。
|
|
|
|
|
|
|
|
|
|
|
|
在互联网行业中，分布式系统是一个非常重要的技术方向。我们熟悉的搜索引擎、广告引擎和推荐引擎，这些大规模的检索系统都采用了分布式技术。
|
|
|
|
|
|
|
|
|
|
|
|
分布式技术有什么优点呢？**分布式技术就是将大任务分解成多个子任务，使用多台服务器共同承担任务，让整体系统的服务能力相比于单机系统得到了大幅提升**。而且，在[第8讲](https://time.geekbang.org/column/article/222810)中我们就讲过，在索引构建的时候，我们可以使用分布式技术来提升索引构建的效率。
|
|
|
|
|
|
|
|
|
|
|
|
那今天，我们就来聊一聊，大规模检索系统中是如何使用分布式技术来加速检索的。
|
|
|
|
|
|
|
|
|
|
|
|
## 简单的分布式结构是什么样的？
|
|
|
|
|
|
|
|
|
|
|
|
一个完备的分布式系统会有复杂的服务管理机制，包括服务注册、服务发现、负载均衡、流量控制、远程调用和冗余备份等。在这里，我们先抛开分布式系统的实现细节，回归到它的本质，也就是从“让多台服务器共同承担任务”入手，来看一个简单的分布式检索系统是怎样工作的。
|
|
|
|
|
|
|
|
|
|
|
|
首先，我们需要一台接收请求的服务器，但是该服务器并不执行具体的查询工作，它只负责任务分发，我们把它叫作**分发服务器**。真正执行检索任务的是**多台索引服务器**，每台索引服务器上都保存着完整的倒排索引，它们都能完成检索的工作。
|
|
|
|
|
|
|
|
|
|
|
|
当分发服务器接到请求时，它会根据负载均衡机制，将当前查询请求发给某台较为空闲的索引服务器进行查询。具体的检索工作由该台索引服务器独立完成，并返回结果。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
简单的分布式检索系统
|
|
|
|
|
|
|
|
|
|
|
|
现在，分布式检索系统的结构你已经知道了，那它的效率怎么样呢？举个例子，如果一台索引服务器一秒钟能处理1000条请求，那我们同时使用10台索引服务器，整个系统一秒钟就能处理10000条请求了。也就是说，这样简单的分布式系统，就能大幅提升整个检索系统的处理能力。
|
|
|
|
|
|
|
|
|
|
|
|
但是，这种简单的分布式系统有一个问题：它仅能提升检索系统整体的“吞吐量”，而不能缩短一个查询的检索时间。也就是说，如果单机处理一个查询请求的耗时是1秒钟，那不管我们增加了多少台机器，单次查询的检索时间依然是1秒钟。所以，如果我们想要缩短检索时间，这样的分布式系统是无法发挥作用的。
|
|
|
|
|
|
|
|
|
|
|
|
那么，我们能否利用多台机器，来提升单次检索的效率呢？我们先来回顾一下，在前面讨论工业级的倒排索引时我们说过，对于存储在磁盘上的大规模索引数据，我们要尽可能地将数据加载到内存中，以此来减少磁盘访问次数，从而提升检索效率。
|
|
|
|
|
|
|
|
|
|
|
|
根据这个思路，当多台服务器的总内存量远远大于单机的内存时，我们可以把倒排索引拆分开，分散加载到每台服务器的内存中。这样，我们就可以避免或者减少磁盘访问，从而提升单次检索的效率了。
|
|
|
|
|
|
|
|
|
|
|
|
即使原来的索引都能加载到内存中，索引拆分依然可以帮助我们提升单次检索的效率。这是因为，检索时间和数据规模是正相关的。当索引拆分以后，每台服务器上加载的数据都会比全量数据少，那每台服务器上的单次查询所消耗的时间也就随之减少了。
|
|
|
|
|
|
|
|
|
|
|
|
因此，索引拆分是检索加速的一个重要优化方案，至于索引应该如何拆分，以及拆分后该如何检索，工业界也有很多不同的实现方法。你可以先自己想一想，然后我们再一起来看看，工业界一般都是怎么做的。
|
|
|
|
|
|
|
|
|
|
|
|
## 如何进行业务拆分？
|
|
|
|
|
|
|
|
|
|
|
|
首先，在工业界中一个最直接的索引拆分思路，是根据业务进行索引拆分。那具体该如何拆分呢？
|
|
|
|
|
|
|
|
|
|
|
|
我来举个例子。在图书管理系统中，有许多不同国籍的作家的作品。如果我们将它们分成国内作品和国外作品两大类，分别建立两个倒排索引，这就完成了索引拆分。索引拆分之后，我们可以使用不同的服务器加载不同的索引。在检索的时候，我们需要先判断检索的是国内作品还是国外作品，然后在检索界面上做好选择，这样系统就可以只在一个索引上查询了。如果我们不能确认是哪类作品，那也没关系，系统可以在两个索引中并行查找，然后将结果汇总。
|
|
|
|
|
|
|
|
|
|
|
|
你会看到，基于业务的拆分是一个实用的索引拆分方案，在许多应用场景中都可以使用。但是这种方案和业务的耦合性太强，需要根据不同的业务需求灵活调整。那我们有没有更通用的技术解决方案呢？你可以先想一下，然后我们一起来讨论。
|
|
|
|
|
|
|
|
|
|
|
|
## 如何基于文档进行拆分？
|
|
|
|
|
|
|
|
|
|
|
|
以搜索引擎为例，一个通用的方案是借鉴索引构建的拆分思路，将大规模文档集合随机划分为多个小规模的文档集合分别处理。这样我们就可以基于文档进行拆分，建立起多个倒排索引了。其中，每个倒排索引都是一个索引分片，它们分别由不同的索引服务器负责。每个索引分片只包含部分文档，所以它们的posting list都不会太长，这样单机的检索效率也就得到了提升。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
基于文档拆分索引
|
|
|
|
|
|
|
|
|
|
|
|
但是，这样拆分出来的任意一个单独的索引分片，它检索出来的结果都不完整，我们还需要合并操作才能得到最后的检索结果。因此，对于基于文档进行拆分的分布式方案，我们的检索流程可以总结为3个步骤：
|
|
|
|
|
|
|
|
|
|
|
|
1. 分发服务器接受查询请求，将请求发送给所有不同索引分片的索引服务器；
|
|
|
|
|
|
2. 每台索引服务器根据自己加载的索引分片进行检索，将查询结果返回分发服务器；
|
|
|
|
|
|
3. 分发服务器将所有返回的结果进行合并处理，再返回最终结果。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
基于文档拆分索引的检索过程
|
|
|
|
|
|
|
|
|
|
|
|
这种基于文档拆分的方案是随机划分的，所以我们可以不用关心业务细节。而且每个索引分片的大小都能足够相近，因此，这种拆分方式能很均匀地划分检索空间和分担检索负载。并且，如果我们将索引数据分成合适的份数，是有可能将所有数据都加载到内存中的。由于每个索引分片中的文档列表都不长，因此每台机器对于单个请求都能在更短的时间内返回，从而加速了检索效率。
|
|
|
|
|
|
|
|
|
|
|
|
但是，分片的数量也不宜过多。这是因为，一个查询请求会被复制到所有的索引分片上，如果分片过多的话，每台加载索引分片的服务器都要返回n个检索结果，这会带来成倍的网络传输开销。而且，分片越多，分发服务器需要合并的工作量也会越大，这会使得分发服务器成为瓶颈，造成性能下降。因此，对于索引分片数量，我们需要考虑系统的实际情况进行合理的设置。
|
|
|
|
|
|
|
|
|
|
|
|
## 如何基于关键词进行拆分？
|
|
|
|
|
|
|
|
|
|
|
|
在搜索引擎中，为了解决分片过多导致一次请求被复制成多次的问题，我们还可以使用另一种拆分方案，那就是基于关键词进行拆分。这种方案将词典划分成多个分片，分别加载到不同的索引服务器上。每台索引服务器上的词典都是不完整的，但是词典中关键词对应的文档列表都是完整的。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
基于关键词拆分索引
|
|
|
|
|
|
|
|
|
|
|
|
当用户查询时，如果只有一个关键词，那我们只需要查询存有这个关键词的一台索引服务器，就能得到完整的文档列表，而不需要给所有的索引服务器都发送请求；当用户同时查询两个关键词时，如果这两个关键词也同时属于一个索引分片的话，那系统依然只需要查询一台索引服务器即可。如果分别属于两个分片，那我们就需要发起两次查询，再由分发服务器进行结果合并。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
基于关键词拆分索引的检索过程
|
|
|
|
|
|
|
|
|
|
|
|
也就是说，在查询词少的情况下，如果能合理分片，我们就可以大幅降低请求复制的代价了。
|
|
|
|
|
|
|
|
|
|
|
|
但是这种切分方案也带来了很多复杂的管理问题，比如，如果查询词很多并且没有被划分到同一个分片中，那么请求依然会被多次复制。再比如，以及如果有的关键词是高频词，那么对应的文档列表会非常长，检索性能也会急剧下降。此外，还有新增文档的索引修改问题，系统热点查询负载均衡的问题等。
|
|
|
|
|
|
|
|
|
|
|
|
因此，除了少数的高性能检索场景有需求以外，一般我们还是基于文档进行索引拆分。这样，系统的扩展性和可运维性都会更好。
|
|
|
|
|
|
|
|
|
|
|
|
## 重点回顾
|
|
|
|
|
|
|
|
|
|
|
|
好了，今天的内容就先讲到这里。我们一起来总结一下，你要掌握的重点内容。
|
|
|
|
|
|
|
|
|
|
|
|
首先，利用分布式技术，我们可以将倒排索引进行索引拆分。索引拆分的好处是：一方面是能将更多的索引数据加载到内存中，降低磁盘访问次数，使得检索效率能得到大幅度的提升；另一方面是基于文档的拆分，能将一个查询请求复制成多份，由多台索引服务器并行完成，单次检索的时间也能得到缩短。
|
|
|
|
|
|
|
|
|
|
|
|
其次，除了搜索引擎，其他大规模数据检索引擎，如广告引擎、推荐引擎等也都使用了类似的索引拆分技术。只是由于它们处理的对象不是文档，因此对于拆分方式的命名也不同。
|
|
|
|
|
|
|
|
|
|
|
|
一般来说，根据处理对象将倒排索引进行拆分，每个索引分片都可能有完整的词典，但posting list不完整，这种拆分方案叫作**水平拆分**。如果是根据倒排索引中的关键词进行拆分，每个索引分片的词典都不完整，但是词典中的关键词对应的posting list是完整的，这种拆分方案叫作**垂直拆分**。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
水平拆分和垂直拆分
|
|
|
|
|
|
|
|
|
|
|
|
总之，**合理的索引拆分是分布式检索加速的重要手段，也是工业界的有效实践经验**。因此，我希望你能好好地理解今天的内容。
|
|
|
|
|
|
|
|
|
|
|
|
## 课堂讨论
|
|
|
|
|
|
|
|
|
|
|
|
为什么说基于文档拆分的方案会比基于关键词拆分的方案更好维护？你可以结合以下2个问题来考虑一下：
|
|
|
|
|
|
|
|
|
|
|
|
1. 当有新文档加入时，会影响多少台索引服务器？
|
|
|
|
|
|
2. 当某些关键词是热点，会被大量查询时，每台服务器的负载是否均衡？
|
|
|
|
|
|
|
|
|
|
|
|
欢迎在留言区畅所欲言，说出你的思考过程和最终答案。如果有收获，也欢迎把这篇文章分享给你的朋友。
|
|
|
|
|
|
|
