检索技术核心20讲
陈东
奇虎360商业产品事业部资深总监
立即订阅
2315 人已学习
课程目录
已完结 29 讲
0/4登录后,你可以任选4讲全文学习。
课前必学 (2讲)
开篇词 | 学会检索,快人一步!
免费
导读 | 三步走策略,轻松搞定检索!
基础技术篇 (8讲)
01 | 线性结构检索:从数组和链表的原理初窥检索本质
02 | 非线性结构检索:数据频繁变化的情况下,如何高效检索?
03 | 哈希检索:如何根据用户ID快速查询用户信息?
04 | 状态检索:如何快速判断一个用户是否存在?
05 | 倒排索引:如何从海量数据中查询同时带有“极”和“客”的唐诗?
测一测 | 检索算法基础,你掌握了多少?
特别加餐 | 倒排检索加速(一):工业界如何利用跳表、哈希表、位图进行加速?
特别加餐 | 倒排检索加速(二):如何对联合查询进行加速?
进阶实战篇 (13讲)
06 | 数据库检索:如何使用B+树对海量磁盘数据建立索引?
07 | NoSQL检索:为什么日志系统主要用LSM树而非B+树?
08 | 索引构建:搜索引擎如何为万亿级别网站生成索引?
09 | 索引更新:刚发布的文章就能被搜到,这是怎么做到的?
10 | 索引拆分:大规模检索系统如何使用分布式技术加速检索?
11|精准Top K检索:搜索结果是怎么进行打分排序的?
12 | 非精准Top K检索:如何给检索结果的排序过程装上“加速器”?
13 | 空间检索(上):如何用Geohash实现“查找附近的人”功能?
14 | 空间检索(下):“查找最近的加油站”和“查找附近的人”有何不同?
15 | 最近邻检索(上):如何用局部敏感哈希快速过滤相似文章?
16 | 最近邻检索(下):如何用乘积量化实现“拍照识花”功能?
特别加餐 | 高性能检索系统中的设计漫谈
测一测 | 高性能检索系统的实战知识,你掌握了多少?
系统案例篇 (4讲)
17 | 存储系统:从检索技术角度剖析LevelDB的架构设计思想
18 | 搜索引擎:输入搜索词以后,搜索引擎是怎么工作的?
19 | 广告系统:广告引擎如何做到在0.1s内返回广告信息?
20 | 推荐引擎:没有搜索词,“头条”怎么找到你感兴趣的文章?
结束语 (2讲)
结束语 | 成长和进化,技术如此,我们亦如此
免费
结课测试 | 这些检索知识,你都掌握了吗?
检索技术核心20讲
15
15
1.0x
00:00/00:00
登录|注册

10 | 索引拆分:大规模检索系统如何使用分布式技术加速检索?

陈东 2020-04-17
你好,我是陈东。
在互联网行业中,分布式系统是一个非常重要的技术方向。我们熟悉的搜索引擎、广告引擎和推荐引擎,这些大规模的检索系统都采用了分布式技术。
分布式技术有什么优点呢?分布式技术就是将大任务分解成多个子任务,使用多台服务器共同承担任务,让整体系统的服务能力相比于单机系统得到了大幅提升。而且,在第 8 讲中我们就讲过,在索引构建的时候,我们可以使用分布式技术来提升索引构建的效率。
那今天,我们就来聊一聊,大规模检索系统中是如何使用分布式技术来加速检索的。

简单的分布式结构是什么样的?

一个完备的分布式系统会有复杂的服务管理机制,包括服务注册、服务发现、负载均衡、流量控制、远程调用和冗余备份等。在这里,我们先抛开分布式系统的实现细节,回归到它的本质,也就是从“让多台服务器共同承担任务”入手,来看一个简单的分布式检索系统是怎样工作的。
首先,我们需要一台接收请求的服务器,但是该服务器并不执行具体的查询工作,它只负责任务分发,我们把它叫作分发服务器。真正执行检索任务的是多台索引服务器,每台索引服务器上都保存着完整的倒排索引,它们都能完成检索的工作。
当分发服务器接到请求时,它会根据负载均衡机制,将当前查询请求发给某台较为空闲的索引服务器进行查询。具体的检索工作由该台索引服务器独立完成,并返回结果。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(14)

  • 无形
    先来回答老师的问题,基于文档拆分的方案,1,新增数据会落到某个具体的服务器,不需要考虑数据在所有检索服务器之间同步、不一致的问题,2,由于所有的检索服务器之间数据是均衡分布的,不存在服务器之间检索负载不均衡的问题

    索引水平拆分垂直拆分和数据库的水平拆分和垂直拆分是类似的
    我理解文档拆分是把数据对一个整体进行分片,对整体的查询变成了并行在分片上查询,缩短了查询时间,还有一个好处是新的文档被哈希到到某个分片上,对查询结果的影响被限定到这个具体的分片,不会影响所有分片
    关键词拆分也是把整体分片,对整体的查询变成了在单个分片上的查询,如果有热点数据会导致posting list过大,降低查询效率,这里能不能特殊处理,给热点数据指定专门的更高性能检索服务器,提升查询效率

    作者回复: 回答和总结得很仔细。
    关于基于关键词拆分,能否特殊处理热点的问题,当然是可以的。如果查询热点一直比较稳定的话,我们可以通过加缓存,加副本,升级机器等方案来优化。不过一般来说,升级机器这种方案用得比较少,因为这涉及到更多的运维团队的工作,不如增加查询缓存,或者增加副本机器等机器调度方案便捷。

    2020-04-23
    3
  • 学习爱好者
    按文档划分和按关键词划分,各有利弊
    按文档划分:
    1、一个关键词的所有文档分布在多个服务器上,缩短了每台服务器postlist的长度,提升了单台服务器的检索效率;
    2、但是检索对外时候需要检索多台服务器,合并检索结果,增加了分页检索实现的难度;

    按关键词划分
    1、每台服务器上含有这个关键词所有的文档,检索的时候,只要找到对应的服务器,检索一次就行,不用结果合并,分页控制也好实现;
    2、但是一个关键词的文档id列表放一块,提高了每次查询的检索成本,尤其是热点数据的检索时候,总要受不常用数据的拖累

    思考题

    我理解插入文档的时候,文档拆分和关键词拆分影响的都是一台服务器,热点数据检索的时候,关键词、文档拆分这种方式都是负载是均衡的,这也体现出按文档拆分的优势;

    作者回复: 总结得很好。尤其你还提到了分页检索,这的确也是一个难点。基于文档拆分的方式需要解决问题。
    至于思考题,在更新一个文档的时候,如果是基于关键词拆分的话,由于一篇文档中会有多个关键词,这些关键词可能是分布在不同的服务器上的,因此会影响多台服务器。
    至于热点查询问题,如果是基于文档拆分,那么负载会更容易均衡到多台服务器上,避免热点。如果真有热点发生时,也可以灵活地重新分片进行负载均衡。因此会比基于关键词拆分更灵活。

    2020-05-01
    2
  • 每天晒白牙
    # 提高的吞吐量而非检索效率
    简单的分布式检索系统是指每台索引服务器保存了全量的索引数据,然后加机器,这种方式只能提高系统整体的"吞吐量",而不能缩短检索时间从而加速检索效率

    # 通过拆分提高检索效率
    检索时间与数据规模正相关,所以采用索引拆分可以加入检索效率

    # 如何拆分?
    ## 基于文档拆分
    核心思想是把大规模的文档集合随机拆分成多个小规模文档集合,即建了多个倒排索引,但每个倒排索引就是一个索引分片,保存了部分数据,所以它的 postinglist 不会太长,可以提升单机的检索效率

    ## 基于文档拆分的检索流程
    - 分发服务器接受查询请求,然后将请求分发给其他索引服务器
    - 每台服务器根据自己加载的索引分片数据进行检索,再把结果返回给分发服务器
    - 分发服务器将所有返回结果进行合并,返回给客户端

    ## 基于文档拆分的优缺点
    优点
    1.基于随机划分,每个索引分片大小相近,在索引空间分配上是相对均衡的,而且每台索引服务器的负载也相对均衡
    2.通过设置合理的分片数,有可能把所有数据加载到内存中,同时因为每个索引分片数据不大,可以提升检索效率

    不足
    分片数不能设置太大
    因为客户端发过来的请求是先经过分发服务器的,然后转发给其他索引分片服务器,如果分片数过多,会设计很多网络 IO 操作,性能就会下降

    ## 基于关键词拆分
    通过关键词进行拆分是将不同的关键词放到不同的索引分片上,然后加载到不同的服务器上,这样的拆分方式可以达到每台索引服务器上的文档不是完整的,但关键词对应的列表是完整的

    ## 基于关键词拆分的检索流程
    客户端发来请求,如果只有一个关键词,那只需要查询改关键词所在的索引服务器就可以得到完整的文档列表,省去了分发造成的网络 IO
    如果是多个关键词,可能也会发生分发请求,然后分发服务器合并请求返回给客户端

    ## 基于关键词拆分的优缺点
    优点
    适合查询词少的情况,可以减少分发造成的网络 IO

    不足
    1.如果查询词比较多且没有被划分到一个分片中,也会分发请求,有网络 IO
    2.如果关键词是高频热点词,那它对应的文档列表会非常长,检索性能也会下降
    3.高频热点词所在服务器负载高,低频词所在服务器负载低,导致索引服务器负载不均衡
    4.如果有新增文档,会涉及到多台索引服务器修改

    # 思考题
    ## 为什么说基于文档拆分比关键词拆分更好维护?
    其实在上面分析两种方案的优缺点时已经介绍了,下面就简单总结下
    - 当有新文档加入时,最糟糕情况会修改所有的索引服务器
    - 遇到高频热点词,大量查询都打到了这个热点词所在的服务器上,导致该服务器负载很高,完成索引服务器的负载不均衡

    作者回复: 总结得很好。我觉得可以给你补两个问题。有精力的童鞋也都可以想想。
    1.如果索引是使用“全量索引+增量索引”,再基于文档拆分,那么一个新文档加入时,它是会加入到所有索引服务器的增量索引中,还是可以只加入到一台服务器的增量索引中?
    2.基于文档拆分,会造成查询请求被复制多份,那除了基于关键词拆分,我们使用业务拆分的方案是否也能避免这个问题?

    2020-04-17
    1
    2
  • 一步
    Redis Cluster 技术相当于按照关键词进行拆分,直接定位到 要查询的 key 在哪个 slot

    作者回复: 你举的这个例子很有意思。其实Redis cluster是一个kv存储,而不是一个倒排索引。对于kv,你既可以说它是按关键词拆分的,也可以说是按文档拆分的。

    当然,如果kv中的v是一个结果集合列表的话,这就是一个典型的基于关键词拆分的倒排索引了。在我们不需要进行多个关键词合并的场景下,这样的使用方案是很适合的。

    2020-04-17
    1
    1
  • 本来按照题目写了下答案,但感觉还不如跳出来回答这个问题,看着太像传统数据库横向拆分纵向拆分,然后引入中间件,然后就有手工分库分表那一坨解决方案。跳出这个思路,横向纵向分片只是分散数据到各个节点的手段,上层应该提供策略屏蔽这些手段的差异,针对具体的分片方式做优化,比如热点,那就针对这个分片多点副本。

    作者回复: 是的。后面抽象成了水平拆分和垂直拆分,其实就和数据库的拆分理念很相似了。包括业务拆分,其实也和分库很相似。因此,许多设计理念都是可以相互借鉴,融会贯通的。

    2020-04-17
    1
  • 那时刻
    尝试回答老师在回复里的问题。不明白的地方请老师指正。
    1.按文档拆分,新增加的文档可以只加到一台增量索引的机器上班,因为查询的时候有按照关键字的合并
    2.我觉得可以按照业务拆分来减少查询的复制,比如按照文档类型 军事,娱乐来把文档分区,这样查询关键字的时候,比如这个关键字属于军事类型就只去军事类型文档分区找就可以了。

    作者回复: 1.没错。如果使用了全量索引+增量索引机制的话,对于新增文档,其实只需要先分片到对应的索引服务器上,然后加入这台服务器的增量索引即可。
    2.业务拆分尽管和业务耦合紧密,不过它可以同时兼具文档拆分和关键词拆分的优点(也可以理解为,业务拆分可以在两个方向进行抽象,分别变成文档拆分和关键词拆分)。
    业务既能对文档进行分片,也能在查询时指定只去一个分片查询,而不是所有分片都查询。因此在一些简单的应用场合中也是可以考虑的。
    对应到数据库设计,就是分库的问题。

    2020-04-17
    1
  • 那时刻
    基于文档或关键字拆分,类似于数据库的分库分表操作。基于文档拆分的好处在于分摊网络和io的压力。

    作者回复: 是的。你会看到,数据库的分库分表其实也是一样的思路。因此,也希望大家能将一个技术进行横行对比,这样能更好地融会贯通,举一反三。

    2020-04-17
    1
  • yalinz
    思考了下老师提出的问题,又看了同学的评论,还是不觉得基于文档拆分一定比基于关键字拆分更有优势:
    1.在新得文档加入时,一般应该是有多个关键字的吧,也就是说有多个关键字的postinglist需要更新。但在水平拆分时因为postinglist是有序的,但postinglist大小不同,那么拆分时是直接平均分段截取postinglist来拆分的吗?这样的话对于新增的文档来说更新索引时可能对于关键字一,该文档就处于postinglist相对靠前的位置,对于关键字二可能就处于postinglist靠后的位置,也就是说拆分后新增一个文档的话并不一定能避免在多个分片上进行更新的问题?那么水平拆分在增加文档时有时同样需要更新多个分片的内容?对这块我有些疑问。
    而垂直拆分的话增加文档也同样需要更新多个分片,但每个postlinglist是完整的,数据较大,更新操作确实比水平拆分负担要大。

    作者回复: 关于基于文档的拆分,我们并不是先把完整的倒排索引建好,再对posting list进行分段拆分,这样做反而复杂了,而且会出现你说的许多分片都受影响的情况。
    你可以仔细看一下文章中描述基于文档拆分的文字和图示。你会发现,基于文档拆分的实现其实很简单,它是先将文档进行分片(比如说可以根据文档ID随机哈希划分),划分为多个小的文档集合,然后针对每个小的文档集合,独立创建索引。因此,当新增一个文档时,我们只需要使用同样的文档分片规则,将新文档分配到所属的文档集合中,然后仅更新这个文档集合对应的索引即可。这样,新增文档仅会影响一个索引分片,而不是影响所有的索引分片。

    2020-06-01
  • 朱月俊
    一切数据库都离不开增删查改,热点以及长尾数据。
    对于倒排索引,
    基于文档分库时,增加一份新doc,查询某个word,删除doc中的word,更新doc中的word,开销都不大。
    基于word分库时,增加一份新doc(可能包含多个word)会影响多个分片,删除doc中的word比较轻松,查一个word包含的docs(可能长尾数据,热点数据),开销异常情况下还是蛮大的,更新doc中的word,因为有多个word,也需要涉及多个分片。
    这样看来,基于文档更合适些。

    作者回复: 你提到了热点数据和长尾数据的问题,这是非常好的角度。从这个角度来看,基于word进行分库,会有两种比较大的开销:一种是这个word是热点,posting list特别长,那么查询开销就会很大;另一种是一个doc中的word很多,会涉及到多个分片的更新。因此基于word进行分库要处理的特殊情况会比较多,开销也大,不如基于文档拆分的方案可扩展性好。

    2020-05-28
  • paulhaoyi
    老师您好,请教一个问题,可能不一定和本章有关。我们做内容分发,需要再召回源拿出内容后,过滤用户读过的文章。由于量比较大,有些用户的阅读历史又很长,单独每个用户记录已读列表,不管是容量还是过滤性能都不太能接受。感觉这就是一个判断是否存在的问题。如果我用文章id做key,用户做的文档。建立倒排合适么?或者老师有什么好的方法建议?

    作者回复: 其实对于这种是否存在的过滤问题,第四讲中我提到过,可以使用bloomfilter来进行判断文章是否已读。这样在容量和查询性能上都不错。缺点就是可能会有一定的错误率。不过作为内容分发场景而言,错判的话,只是少分发一个内容而已,应该是可以接受的。
    如果不希望有错误率,那么可以使用加餐1中我提到过的roaring bitmap来进行查找。
    至于你说的用文章ID为key,用户作为posting list的方案,我的理解是这个也是可行的。但是其实它和以用户为key,文章为posting list的方案的存储空间是一样的。你可以画一个矩阵,每一行是一个用户,每一列是一个文章。那么这个矩阵横着就是以用户ID为key,以文章ID为posting list的倒排;竖着就变成了以文章ID为key,以用户ID为posting list的倒排,因此并不会省空间。

    2020-05-12
  • 时隐时现
    老师好,有个问题:
    第一种多副本全量索引架构,如果对全量索引进行更新且确保每个副本都一致?db副本可以借助paxos/raft协议实现,倒排索引适用这种协议吗?有现成的架构可以采用吗?

    作者回复: 这是一个好问题。如何保证分布式系统中的倒排索引的一致性。这就看应用具体的要求了。
    如果对于一致性要求不高的话,比如说搜索引擎,用户a搜索使用的是旧的全量索引,用户b搜索使用的是新的全量索引,其实这是没有任何问题的。因此这时候不需要特别处理。
    但如果是有强一致性要求的场景,那么可以使用分布式锁(Redis,zookeeper都可以,你可以了解一下),来保证所有的副本都一致后再切换服务。不过这肯定会损失性能。

    2020-05-07
  • Mq
    基于文档的方案在有新文档加入时只会影响到有文档的那台服务器,基于关键词的拆分会影响到有关键词的所有服务器。
    热点关键词问题我怎么觉得基于文档跟基于关键词的划分都有,并且基于文档划分的影响范围更大。因为基于文档的划分所有索引服务器都保存了完整的key,也就意味着热点key来了后会导致所有索引服务器负载高,基于热点key的划分还只会影响到热点key的那台服务器,也主要针对那些服务器加副本就可以了。

    作者回复: 对于热点的问题,如果所有的服务器的负载都同时上升,其实这是我们期望的事情,这时候没有服务器是“热点”,我们在运维时只要无差别扩容就行。
    相反,如果有的服务器查询负载很低,但有的服务器查询负载很高,那么这时候就存在“热点”问题了,我们需要针对特殊的一小撮服务器进行加副本扩容。但这时候可能其他服务器其实还是足够空闲的,这就造成了资源浪费。而且,如果第二天热点切换了的话,那我们是不是还要将原热点的副本下线,然后上线其他热点的副本?这样就会给运维带来很大的复杂性。

    2020-04-17
    1
  • _你说了不算
    老师,我们的广告投放引擎在数据检索这块就走了不少路,es过滤和内存过滤两种方式都用过,最终还是用了内存过滤,原因是后者服务器的cpu和内存状态更好,不知道是不是我们用es的姿势不对。最近引擎系统cpu一直报警,除了加机器,就是加机器,想请教下老师,有遇到过类似的这种情况吗?假如按照文章中提到的索引拆分的方式,具体的落地方案老师能不能指点一二?还有我们的数据是AE通过管理后台存在mysql的,那么mysql和es的数据一致性怎么处理?希望老师百忙中解答

    作者回复: 1.关于es的使用,的确是要了解了相关检索技术,已经了解了es以后,才能发挥出es的优势。如果你们想走这条路线的话,那需要多花点时间深入了解。
    2.你所谓的内存过滤,我的理解就是你们自研系统,在内存中建立索引处理。那么这样的话,你可以结合这个专栏的内容看看如何优化,比如说索引拆分,你们可以指定一个固定分片数,然后在离线环节就拆分好;然后结合全量索引+增量索引的机制,也能保证索引更新时的性能;还有倒排检索加速(参考两篇加餐),应该也是有帮助的。
    3.MySQL和es的数据同步问题,其实有许多工具可以做,比如说logstash等。而一致性问题,需要你进行监控和周期性检查,避免有错误。还可以进行周期性完整重建索引的方式,将之前可能已经造成的不一致进行修复。

    2020-04-17
  • pedro
    按照老师的思路大致可以理一下,当新的文档加入,势必会根据新文档的关键词再拆分,影响的服务器得根据具体场景来定,可能会影响多台服务器,而基于文档拆分会直接将新增文档加入到特定的服务器中,对于热点关键词,肯定会被频繁访问,一台服务器会不堪重负,而冷点关键词估计会在服务器中发霉,热点关键词可能需要多台服务器进行支持,并增加相应的网关进行负载均衡。
    那么根据文档拆分也会遇到热点文档的问题,也需要多服务器和负载均衡,那么请问老师具体的场景会怎么做呢?

    作者回复: 热点问题的确很常见。一个通用的解法就是为热点分片增加副本。
    此外,对于随机划分的文档拆分方案而言,由于随机的特性,它出现热点分片的概率相对较低,而且即使出现了,它也可以通过再次随机划分,或者有规划地划分来完成检索负载均衡的问题。
    而基于关键词划分的方案,因为还有一个“相关的关键词要被划分到同一个分片”的限制,因此在调整分片上能做的事情就很有限了。这也是它不如文档拆分更灵活的原因。

    2020-04-17
收起评论
14
返回
顶部