检索技术核心 20 讲
陈东
前数禾科技 CTO,前奇虎 360 商业化资深总监
21492 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 29 讲
检索技术核心 20 讲
15
15
1.0x
00:00/00:00
登录|注册

09 | 索引更新:刚发布的文章就能被搜到,这是怎么做到的?

课堂讨论
设计思想
倒排索引更新方法
文章主题总结

该思维导图由 AI 生成,仅供参考

你好,我是陈东。
在前面的课程中,我们讲到,倒排索引是许多检索系统的核心实现方案。比如,搜索引擎对万亿级别网页的索引,就是使用倒排索引实现的。我们还讲到,对于超大规模的网页建立索引会非常耗时,工业界往往会使用分布式技术来并行处理。
对于发布较久的网页,搜索引擎可以有充足的时间来构建索引。但是一些新的网页和文章,往往发布了几分钟就可以被用户搜索到。这又是怎么做到的呢?今天,我们就来聊一聊这个问题。

工业界如何更新内存中的索引?

我们先来看这么一个问题:如果现在有一个小规模的倒排索引,它能完全加载在内存中。当有新文章进入内存的时候,倒排索引该如何更新呢?这个问题看似简单,但是实现起来却非常复杂。
我们能想到最直接的解决思路是,只要解析新文章有哪些关键词,然后将文章 ID 加入倒排表中关键词对应的文档列表即可。没错,在没有其他用户使用的情况下,这样的方法是可行的。但如果你有过一定的工程经验,你就会知道,在实际应用中,必然会有多个用户同时访问这个索引。
这个时候,如果我们直接更新倒排索引,就可能造成用户访问错误,甚至会引发程序崩溃。因此,一般来说,我们会对倒排表加上“读写锁”,然后再更新。但是,加上“锁”之后会带来频繁的读写锁切换,整个系统的检索效率会比无锁状态有所下降。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

工业界如何实现新发布文章快速被搜索到?本文介绍了两种主要的索引更新方案:双缓冲机制和全量索引结合增量索引。双缓冲机制通过在内存中同时保存两份索引,实现了无锁状态下的索引更新,提高了系统性能。全量索引结合增量索引方案周期性处理全部数据生成全量索引,同时将新数据建立增量索引,再将两者合并作为总结果输出,实现了实时更新。此外,文章还介绍了增量索引空间持续增长的处理方法,包括完全重建法、再合并法和滚动合并法。滚动合并法通过逐层合并不同层级的索引,避免了无谓的数据复制开销。在工业界中,这些方案为读者提供了实现快速搜索的技术思路和解决方案。文章还讲了一个重要的工业设计思想,即读写分离,将主要的数据检索放在一个只读的组件上,避免了读写同时发生的竞争状态和加锁。这些技术特点为读者提供了在工业界实现快速搜索的技术思路和解决方案。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《检索技术核心 20 讲》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(31)

  • 最新
  • 精选
  • 每天晒白牙
    第一时间看到这个思考题,我没啥思路,看了大家的留言和老师的回复,学到了,把老师的回复总结了起来 为什么在增量索引中,对于要删除的数据没有像 LSM 树那样一样在索引中直接做删除标记,而是额外增加一个删除列表? 1.倒排所以和 kv 存储还是有不一样的地方,倒排索引的 posting list 元素有很多,每个元素都做删除标记代价较大 2.一个文档可能存在多个 key,所以一个文档都要修改删除标记的话,读写很频繁,加班性能下降 3.加标记也没什么用处,因为在对 postlist 做合并的过程中,数据都是全部存在的,只有在最后和全量索引合并时才进行真正的删除操作,这样可能还没有把要删除的元素放到一个删除列表中,在最后做交集更高效

    作者回复: 总结得很认真。相信你学完这一课后,再去看es中的segment的处理就会很轻松了,比如segment的生成和合并,还有.del文件存储删除列表等。 此外,你还可以思考索引更新这一块,你们当前系统的实现方案是否合理,是否有优化空间等。

    2020-04-15
    15
  • Mq
    看不懂滚动合并机制,老师能结合具体数据分析下,例如我今天增加了几个网页,有倒排索引关键字的value都要加上这个网页,这个滚动合并的流程是咋样的。

    作者回复: 滚动合并机制的确是最复杂的一种。它的核心思想是“解决小索引和大索引合并的效率问题,避免大索引产生大量无谓的复制操作”。而解决方案则是“在小索引和大索引中间加入中索引进行过渡”。 这个设计方案其实会很常见。比如说在lsm树那一课,我说了“假设只有c0树和c1树”,而实际情况是c1树会非常大,合并效率会很低,因此lsm树的设计中就有着多棵不同大小的树。包括leveldb的实现,也会有着多层索引。因此,这是一个值得我们学习和掌握的方法。 至于你举的这个例子,结合文中的内容,使用滚动合并的流程是这样的: 1.今天增加的网页会先存在内存的增量索引中。 2.增量索引满了,要开始合并。 3.增量索引和当天的天级索引合并(天级索引不大,所以合并代价小)。 4.当天级索引达到了7天时,可以将多个天级索引合并,变成一个新的周级索引。 5.当有多个周级索引的时候,全量索引会和多个周级索引合并,生成一份新的全量索引。(不过,一般这一步会用重新生成全量索引来代替,你可以理解为为了保证系统的稳定性,需要定期进行索引重建。就像系统要进行定期重启一样)。

    2020-04-15
    3
    10
  • 对于结尾的问题:我在补偿一下,除了上面说的原因还有就是,一个文档 会有多个 key, 也不可能对文档包含的每个 key 进行文档标记

    作者回复: 综合你前一条一起回复,你说到了两个点上: 1.倒排索引和kv不一样,posting list元素很多,每个元素都加标记代价太大。 2.一个文档可能会影响多个key,因此每个文档都要修改标记的话,读写操作会很频繁,加锁性能下降。 此外,还有一点是,加上标记也没啥用,在posting list求交并的过程中,依然要全部留下来,等着最后和全量索引合并时才能真正删除。这样的话不如直接用一个delete list存着,最后求交集更高效。

    2020-04-15
    7
  • PhilZhang
    在滚动合并得例子中,如果此时有1个全量索引,5个周级索引,6个天级索引,1个增量索引,此时一次查询就要汇集1+5+6+1一共13个索引得结果是吧,另外为了保证读写分离,每个索引都要保存两份。不知道我的理解是否正确。

    作者回复: 我分两部分来说。 第一,关于要查询的索引数量问题,按你的计算方法,的确是要查13个索引。实际上,在现在集群能力比较强的情况下,我们可以根据自己的情况选择合适的粒度,比如说去掉周级索引,这样只需要全量索引+天级索引+增量索引就好了。因此是1+6+1共7个索引。 第二,关于索引副本数的问题。首先分布式系统是每个索引分片都会有多个副本的,增加并发度。副本数看具体情况而定。然后,关于读写分离的两份索引问题,增量索引在内存中使用double buffer,肯定是两份。全量索引和天级索引,由于是在磁盘上,因此在创建的时候会先在磁盘上创建一份,然后将老的删除。因此只会在创建的过程中会有双份,正常时间内只有一份。

    2020-05-14
    2
    6
  • 青鸟飞鱼
    还是有点疑惑,可能太笨了?双缓存情况下,假如更新的索引中id有1,3,5,7...,同时规定更新一个索引,AB读写指针交换一次。假如A开始为写指针,最后更新的结果为A(1,5...)B(3,7...)还是A(1,3,5,7....)B(1,3,5,7.…)

    作者回复: 都是1,3,5,7。 其实你只要理解,双缓存中,每个索引都是完整的全量索引就清楚了。 以你的例子来看,步骤如下: 1.一开始,索引A中是1,索引B中也是1。 2.当3加入时,是加入写索引B,这时B就是(1,3) 3.B切换成读索引,这时A变为写索引,这时我们可以将之前变化的数据3也加入到A中,这样A就也是(1,3)了。(当然你也可以完全重建索引更新A)。注意:这一步就是关键。 4.当5加入时,加入写索引A,这时A就是(1,3,5)。

    2020-04-28
    4
    6
  • Impressw
    学到了很多,最近正好遇到了频繁更新索引,为什么能实时被检索到,速度又不会变慢的问题,看了这篇文章茅塞顿开,不过还是想问下,在大规模数据索引,频繁更新,真的能保证实时的情况下,完成更新索引吗

    作者回复: 实际的系统的确就是这样实现的。当然,也需要控制一下索引切换(double buffer)或者索引合并(增量+全量)的频率。 在搜索引擎中,数据的实时更新可能还不够明显,但是在广告引擎和推荐引擎中,你会直观地感觉到,广告主修改了设置,或者你刚看过一篇文章,相关的反馈马上就发生了

    2020-05-13
    5
  • Joe Black
    请问下对于Double Buffer机制,当索引A处于只读,索引B可更新时,两者访问都可以不加锁;假设每次对索引A的读访问会耗费一定时间,当B更新完毕后,通过原子操作把当前索引设为B,但是我们必须等待所有对A的读操作都结束了才能同步更新A。那么这个等待该如何处理呢?不使用锁怎么样才能知道对A的读取都完成了呢?

    作者回复: 这是一个好问题。为了能便捷地判断是否索引a上的所有读操作都结束了,我们可以使用智能指针。当指向索引A的智能指针的引用计数为0,那么就说明索引A的访问都结束了。

    2020-06-06
    2
  • paulhaoyi
    合并的三种方法,感觉一二是三的特殊情况,分别是只有一层和两层的三。不知道这么理解对不对?

    作者回复: 不完全一样。 比如说滚动合并法中的第一层天级索引和增量索引的合并,其实也可以用再合并法来完成。 因此,第一种方法是基础,第二种方法是第一种的优化,第三种方法,是将索引进行组织,多次使用第二种方法(再合并法)。这样理解我觉得是OK的。

    2020-05-08
    2
  • 青鸟飞鱼
    双缓存机制有个疑问,假如A更新了一个数据1,B也需要更新数据1,这个如何保证呢?

    作者回复: 是这样,双缓存机制的设计理念是读写分离,一个索引只负责写,另一个索引只负责读。因此,不会存在你说的两个索引同时被写的情况。

    2020-04-21
    2
  • 兰柯一梦
    如果在doc的正排字段中做标记删除是不是也可以呢? 这样等各个索引进行合并的时候,看doc对应的正排的删除标记,如果是删除状态那边直接丢掉

    作者回复: 你的想法很好,其实是有可能的。本质上,你是复用了正排表,让它承载了删除列表的功能。在最后posting list合并的时候,通过查正排表完成过滤(其实就是加餐一中说的哈希表法:将删除列表变成了哈希表)。 在系统比较简单的时候,这样使用是OK的。不过当系统足够复杂的时候,我们需要将不同功能和数据进行合理的划分,倒排检索和正排查询有可能是两个不同的环节和模块(包括中间可能还有其他环节,比如抽取特征,打分计算等)。因此从这个角度出发,复杂系统才会抽象出删除列表这个对象,这样就可以不依赖于正排表,从而完成了系统架构的解耦设计。

    2020-04-16
    2
收起评论
显示
设置
留言
31
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部