10 索引拆分：大规模检索系统如何使用分布式技术加速检索？
你好，我是陈东。
在互联网行业中，分布式系统是一个非常重要的技术方向。我们熟悉的搜索引擎、广告引擎和推荐引擎，这些大规模的检索系统都采用了分布式技术。
分布式技术有什么优点呢？分布式技术就是将大任务分解成多个子任务，使用多台服务器共同承担任务，让整体系统的服务能力相比于单机系统得到了大幅提升。而且，在第8讲中我们就讲过，在索引构建的时候，我们可以使用分布式技术来提升索引构建的效率。
那今天，我们就来聊一聊，大规模检索系统中是如何使用分布式技术来加速检索的。
简单的分布式结构是什么样的？
一个完备的分布式系统会有复杂的服务管理机制，包括服务注册、服务发现、负载均衡、流量控制、远程调用和冗余备份等。在这里，我们先抛开分布式系统的实现细节，回归到它的本质，也就是从“让多台服务器共同承担任务”入手，来看一个简单的分布式检索系统是怎样工作的。
首先，我们需要一台接收请求的服务器，但是该服务器并不执行具体的查询工作，它只负责任务分发，我们把它叫作分发服务器。真正执行检索任务的是多台索引服务器，每台索引服务器上都保存着完整的倒排索引，它们都能完成检索的工作。
当分发服务器接到请求时，它会根据负载均衡机制，将当前查询请求发给某台较为空闲的索引服务器进行查询。具体的检索工作由该台索引服务器独立完成，并返回结果。
简单的分布式检索系统
现在，分布式检索系统的结构你已经知道了，那它的效率怎么样呢？举个例子，如果一台索引服务器一秒钟能处理1000条请求，那我们同时使用10台索引服务器，整个系统一秒钟就能处理10000条请求了。也就是说，这样简单的分布式系统，就能大幅提升整个检索系统的处理能力。
但是，这种简单的分布式系统有一个问题：它仅能提升检索系统整体的“吞吐量”，而不能缩短一个查询的检索时间。也就是说，如果单机处理一个查询请求的耗时是1秒钟，那不管我们增加了多少台机器，单次查询的检索时间依然是1秒钟。所以，如果我们想要缩短检索时间，这样的分布式系统是无法发挥作用的。
那么，我们能否利用多台机器，来提升单次检索的效率呢？我们先来回顾一下，在前面讨论工业级的倒排索引时我们说过，对于存储在磁盘上的大规模索引数据，我们要尽可能地将数据加载到内存中，以此来减少磁盘访问次数，从而提升检索效率。
根据这个思路，当多台服务器的总内存量远远大于单机的内存时，我们可以把倒排索引拆分开，分散加载到每台服务器的内存中。这样，我们就可以避免或者减少磁盘访问，从而提升单次检索的效率了。
即使原来的索引都能加载到内存中，索引拆分依然可以帮助我们提升单次检索的效率。这是因为，检索时间和数据规模是正相关的。当索引拆分以后，每台服务器上加载的数据都会比全量数据少，那每台服务器上的单次查询所消耗的时间也就随之减少了。
因此，索引拆分是检索加速的一个重要优化方案，至于索引应该如何拆分，以及拆分后该如何检索，工业界也有很多不同的实现方法。你可以先自己想一想，然后我们再一起来看看，工业界一般都是怎么做的。
如何进行业务拆分？
首先，在工业界中一个最直接的索引拆分思路，是根据业务进行索引拆分。那具体该如何拆分呢？
我来举个例子。在图书管理系统中，有许多不同国籍的作家的作品。如果我们将它们分成国内作品和国外作品两大类，分别建立两个倒排索引，这就完成了索引拆分。索引拆分之后，我们可以使用不同的服务器加载不同的索引。在检索的时候，我们需要先判断检索的是国内作品还是国外作品，然后在检索界面上做好选择，这样系统就可以只在一个索引上查询了。如果我们不能确认是哪类作品，那也没关系，系统可以在两个索引中并行查找，然后将结果汇总。
你会看到，基于业务的拆分是一个实用的索引拆分方案，在许多应用场景中都可以使用。但是这种方案和业务的耦合性太强，需要根据不同的业务需求灵活调整。那我们有没有更通用的技术解决方案呢？你可以先想一下，然后我们一起来讨论。
如何基于文档进行拆分？
以搜索引擎为例，一个通用的方案是借鉴索引构建的拆分思路，将大规模文档集合随机划分为多个小规模的文档集合分别处理。这样我们就可以基于文档进行拆分，建立起多个倒排索引了。其中，每个倒排索引都是一个索引分片，它们分别由不同的索引服务器负责。每个索引分片只包含部分文档，所以它们的posting list都不会太长，这样单机的检索效率也就得到了提升。
基于文档拆分索引
但是，这样拆分出来的任意一个单独的索引分片，它检索出来的结果都不完整，我们还需要合并操作才能得到最后的检索结果。因此，对于基于文档进行拆分的分布式方案，我们的检索流程可以总结为3个步骤：
- 分发服务器接受查询请求，将请求发送给所有不同索引分片的索引服务器；
- 每台索引服务器根据自己加载的索引分片进行检索，将查询结果返回分发服务器；
- 分发服务器将所有返回的结果进行合并处理，再返回最终结果。
基于文档拆分索引的检索过程
这种基于文档拆分的方案是随机划分的，所以我们可以不用关心业务细节。而且每个索引分片的大小都能足够相近，因此，这种拆分方式能很均匀地划分检索空间和分担检索负载。并且，如果我们将索引数据分成合适的份数，是有可能将所有数据都加载到内存中的。由于每个索引分片中的文档列表都不长，因此每台机器对于单个请求都能在更短的时间内返回，从而加速了检索效率。
但是，分片的数量也不宜过多。这是因为，一个查询请求会被复制到所有的索引分片上，如果分片过多的话，每台加载索引分片的服务器都要返回n个检索结果，这会带来成倍的网络传输开销。而且，分片越多，分发服务器需要合并的工作量也会越大，这会使得分发服务器成为瓶颈，造成性能下降。因此，对于索引分片数量，我们需要考虑系统的实际情况进行合理的设置。
如何基于关键词进行拆分？
在搜索引擎中，为了解决分片过多导致一次请求被复制成多次的问题，我们还可以使用另一种拆分方案，那就是基于关键词进行拆分。这种方案将词典划分成多个分片，分别加载到不同的索引服务器上。每台索引服务器上的词典都是不完整的，但是词典中关键词对应的文档列表都是完整的。
基于关键词拆分索引
当用户查询时，如果只有一个关键词，那我们只需要查询存有这个关键词的一台索引服务器，就能得到完整的文档列表，而不需要给所有的索引服务器都发送请求；当用户同时查询两个关键词时，如果这两个关键词也同时属于一个索引分片的话，那系统依然只需要查询一台索引服务器即可。如果分别属于两个分片，那我们就需要发起两次查询，再由分发服务器进行结果合并。
基于关键词拆分索引的检索过程
也就是说，在查询词少的情况下，如果能合理分片，我们就可以大幅降低请求复制的代价了。
但是这种切分方案也带来了很多复杂的管理问题，比如，如果查询词很多并且没有被划分到同一个分片中，那么请求依然会被多次复制。再比如，以及如果有的关键词是高频词，那么对应的文档列表会非常长，检索性能也会急剧下降。此外，还有新增文档的索引修改问题，系统热点查询负载均衡的问题等。
因此，除了少数的高性能检索场景有需求以外，一般我们还是基于文档进行索引拆分。这样，系统的扩展性和可运维性都会更好。
重点回顾
好了，今天的内容就先讲到这里。我们一起来总结一下，你要掌握的重点内容。
首先，利用分布式技术，我们可以将倒排索引进行索引拆分。索引拆分的好处是：一方面是能将更多的索引数据加载到内存中，降低磁盘访问次数，使得检索效率能得到大幅度的提升；另一方面是基于文档的拆分，能将一个查询请求复制成多份，由多台索引服务器并行完成，单次检索的时间也能得到缩短。
其次，除了搜索引擎，其他大规模数据检索引擎，如广告引擎、推荐引擎等也都使用了类似的索引拆分技术。只是由于它们处理的对象不是文档，因此对于拆分方式的命名也不同。
一般来说，根据处理对象将倒排索引进行拆分，每个索引分片都可能有完整的词典，但posting list不完整，这种拆分方案叫作水平拆分。如果是根据倒排索引中的关键词进行拆分，每个索引分片的词典都不完整，但是词典中的关键词对应的posting list是完整的，这种拆分方案叫作垂直拆分。
水平拆分和垂直拆分
总之，合理的索引拆分是分布式检索加速的重要手段，也是工业界的有效实践经验。因此，我希望你能好好地理解今天的内容。
课堂讨论
为什么说基于文档拆分的方案会比基于关键词拆分的方案更好维护？你可以结合以下2个问题来考虑一下：
- 当有新文档加入时，会影响多少台索引服务器？
- 当某些关键词是热点，会被大量查询时，每台服务器的负载是否均衡？
欢迎在留言区畅所欲言，说出你的思考过程和最终答案。如果有收获，也欢迎把这篇文章分享给你的朋友。
- 无形 👍（4） 💬（1）
先来回答老师的问题，基于文档拆分的方案，1，新增数据会落到某个具体的服务器，不需要考虑数据在所有检索服务器之间同步、不一致的问题，2，由于所有的检索服务器之间数据是均衡分布的，不存在服务器之间检索负载不均衡的问题 索引水平拆分垂直拆分和数据库的水平拆分和垂直拆分是类似的 我理解文档拆分是把数据对一个整体进行分片，对整体的查询变成了并行在分片上查询，缩短了查询时间，还有一个好处是新的文档被哈希到到某个分片上，对查询结果的影响被限定到这个具体的分片，不会影响所有分片 关键词拆分也是把整体分片，对整体的查询变成了在单个分片上的查询，如果有热点数据会导致posting list过大，降低查询效率，这里能不能特殊处理，给热点数据指定专门的更高性能检索服务器，提升查询效率
2020-04-23 - 奕 👍（3） 💬（2）
Redis Cluster 技术相当于按照关键词进行拆分，直接定位到 要查询的 key 在哪个 slot
2020-04-17 - 每天晒白牙 👍（3） 💬（2）
# 提高的吞吐量而非检索效率 简单的分布式检索系统是指每台索引服务器保存了全量的索引数据，然后加机器，这种方式只能提高系统整体的"吞吐量"，而不能缩短检索时间从而加速检索效率 # 通过拆分提高检索效率 检索时间与数据规模正相关，所以采用索引拆分可以加入检索效率 # 如何拆分？ ## 基于文档拆分 核心思想是把大规模的文档集合随机拆分成多个小规模文档集合，即建了多个倒排索引，但每个倒排索引就是一个索引分片，保存了部分数据，所以它的 postinglist 不会太长，可以提升单机的检索效率 ## 基于文档拆分的检索流程 - 分发服务器接受查询请求，然后将请求分发给其他索引服务器 - 每台服务器根据自己加载的索引分片数据进行检索，再把结果返回给分发服务器 - 分发服务器将所有返回结果进行合并，返回给客户端 ## 基于文档拆分的优缺点 优点 1.基于随机划分，每个索引分片大小相近，在索引空间分配上是相对均衡的，而且每台索引服务器的负载也相对均衡 2.通过设置合理的分片数，有可能把所有数据加载到内存中，同时因为每个索引分片数据不大，可以提升检索效率 不足 分片数不能设置太大 因为客户端发过来的请求是先经过分发服务器的，然后转发给其他索引分片服务器，如果分片数过多，会设计很多网络 IO 操作，性能就会下降 ## 基于关键词拆分 通过关键词进行拆分是将不同的关键词放到不同的索引分片上，然后加载到不同的服务器上，这样的拆分方式可以达到每台索引服务器上的文档不是完整的，但关键词对应的列表是完整的 ## 基于关键词拆分的检索流程 客户端发来请求，如果只有一个关键词，那只需要查询改关键词所在的索引服务器就可以得到完整的文档列表，省去了分发造成的网络 IO 如果是多个关键词，可能也会发生分发请求，然后分发服务器合并请求返回给客户端 ## 基于关键词拆分的优缺点 优点 适合查询词少的情况，可以减少分发造成的网络 IO 不足 1.如果查询词比较多且没有被划分到一个分片中，也会分发请求，有网络 IO 2.如果关键词是高频热点词，那它对应的文档列表会非常长，检索性能也会下降 3.高频热点词所在服务器负载高，低频词所在服务器负载低，导致索引服务器负载不均衡 4.如果有新增文档，会涉及到多台索引服务器修改 # 思考题 ## 为什么说基于文档拆分比关键词拆分更好维护？ 其实在上面分析两种方案的优缺点时已经介绍了，下面就简单总结下 - 当有新文档加入时，最糟糕情况会修改所有的索引服务器 - 遇到高频热点词，大量查询都打到了这个热点词所在的服务器上，导致该服务器负载很高，完成索引服务器的负载不均衡
2020-04-17 - new life 👍（2） 💬（1）
按文档划分和按关键词划分，各有利弊 按文档划分: 1、一个关键词的所有文档分布在多个服务器上，缩短了每台服务器postlist的长度，提升了单台服务器的检索效率； 2、但是检索对外时候需要检索多台服务器，合并检索结果，增加了分页检索实现的难度； 按关键词划分 1、每台服务器上含有这个关键词所有的文档，检索的时候，只要找到对应的服务器，检索一次就行，不用结果合并，分页控制也好实现； 2、但是一个关键词的文档id列表放一块，提高了每次查询的检索成本，尤其是热点数据的检索时候，总要受不常用数据的拖累 思考题 我理解插入文档的时候，文档拆分和关键词拆分影响的都是一台服务器，热点数据检索的时候，关键词、文档拆分这种方式都是负载是均衡的，这也体现出按文档拆分的优势；
2020-05-01 - paulhaoyi 👍（1） 💬（1）
老师您好，请教一个问题，可能不一定和本章有关。我们做内容分发，需要再召回源拿出内容后，过滤用户读过的文章。由于量比较大，有些用户的阅读历史又很长，单独每个用户记录已读列表，不管是容量还是过滤性能都不太能接受。感觉这就是一个判断是否存在的问题。如果我用文章id做key，用户做的文档。建立倒排合适么？或者老师有什么好的方法建议？
2020-05-12 - 峰 👍（1） 💬（1）
本来按照题目写了下答案，但感觉还不如跳出来回答这个问题，看着太像传统数据库横向拆分纵向拆分，然后引入中间件，然后就有手工分库分表那一坨解决方案。跳出这个思路，横向纵向分片只是分散数据到各个节点的手段，上层应该提供策略屏蔽这些手段的差异，针对具体的分片方式做优化，比如热点，那就针对这个分片多点副本。
2020-04-17 - 那时刻 👍（1） 💬（1）
尝试回答老师在回复里的问题。不明白的地方请老师指正。 1.按文档拆分，新增加的文档可以只加到一台增量索引的机器上班，因为查询的时候有按照关键字的合并 2.我觉得可以按照业务拆分来减少查询的复制，比如按照文档类型 军事，娱乐来把文档分区，这样查询关键字的时候，比如这个关键字属于军事类型就只去军事类型文档分区找就可以了。
2020-04-17 - 那时刻 👍（1） 💬（1）
基于文档或关键字拆分，类似于数据库的分库分表操作。基于文档拆分的好处在于分摊网络和io的压力。
2020-04-17 - _你说了不算 👍（1） 💬（1）
老师，我们的广告投放引擎在数据检索这块就走了不少路，es过滤和内存过滤两种方式都用过，最终还是用了内存过滤，原因是后者服务器的cpu和内存状态更好，不知道是不是我们用es的姿势不对。最近引擎系统cpu一直报警，除了加机器，就是加机器，想请教下老师，有遇到过类似的这种情况吗？假如按照文章中提到的索引拆分的方式，具体的落地方案老师能不能指点一二？还有我们的数据是AE通过管理后台存在mysql的，那么mysql和es的数据一致性怎么处理？希望老师百忙中解答
2020-04-17 - Christmas 👍（0） 💬（1）
超大规模的数据量的情况下，感觉按照文档切分，会出现性能问题，分发服务器请求的查询服务器会过多，因为一般es也不建议shard数量很大。不知道业界超大规模额情况下，是按照文档切分的吗？
2021-03-12 - 趁早 👍（0） 💬（2）
连接的问题怎么处理，比如基于文档的水平拆分，每次查询都要遍历所有的分片，那分发服务需要跟每台分片保持实时的连接，这个开销也是很大的
2021-01-13 - 明翼 👍（0） 💬（1）
老师请教个问题我们有大量的pcap文件，然后通过四元组来进行pcap的查找，我们如果对四元组分别建四个hashmap作为索引，值为pcap文件的偏移量，这个办法会造成文件持久的可能太大，而且hashmap还不太好持久化，有什么好的思路吗？谢谢老师
2020-11-24 - 独酌相思解千愁 👍（0） 💬（1）
我的理解是，两者的区别就是分词典和分文档（就是这么直白）。当然不是把一个完整文档分城小片，然后路由到不同服务器上。最直观的感受就是，当有一个新文档来时，两者都要把文档路由到指定服务器上，但在索引更新时，安文档分的，就只用更新它所在服务器索引；而安词典分就需要更新所有可能的词典和其postinglist（他们可能分布在不同服务其上）。另外es集群应该就是文档分的吧。
2020-08-29 - yalinz 👍（0） 💬（1）
思考了下老师提出的问题，又看了同学的评论，还是不觉得基于文档拆分一定比基于关键字拆分更有优势： 1.在新得文档加入时，一般应该是有多个关键字的吧，也就是说有多个关键字的postinglist需要更新。但在水平拆分时因为postinglist是有序的，但postinglist大小不同，那么拆分时是直接平均分段截取postinglist来拆分的吗?这样的话对于新增的文档来说更新索引时可能对于关键字一，该文档就处于postinglist相对靠前的位置，对于关键字二可能就处于postinglist靠后的位置，也就是说拆分后新增一个文档的话并不一定能避免在多个分片上进行更新的问题？那么水平拆分在增加文档时有时同样需要更新多个分片的内容？对这块我有些疑问。 而垂直拆分的话增加文档也同样需要更新多个分片，但每个postlinglist是完整的，数据较大，更新操作确实比水平拆分负担要大。
2020-06-01 - 朱月俊 👍（0） 💬（1）
一切数据库都离不开增删查改，热点以及长尾数据。 对于倒排索引， 基于文档分库时，增加一份新doc，查询某个word，删除doc中的word，更新doc中的word，开销都不大。 基于word分库时，增加一份新doc(可能包含多个word)会影响多个分片，删除doc中的word比较轻松，查一个word包含的docs(可能长尾数据，热点数据)，开销异常情况下还是蛮大的，更新doc中的word，因为有多个word，也需要涉及多个分片。 这样看来，基于文档更合适些。
2020-05-28