检索技术核心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
登录|注册

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

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

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

我们先来看这么一个问题:如果现在有一个小规模的倒排索引,它能完全加载在内存中。当有新文章进入内存的时候,倒排索引该如何更新呢?这个问题看似简单,但是实现起来却非常复杂。
我们能想到最直接的解决思路是,只要解析新文章有哪些关键词,然后将文章 ID 加入倒排表中关键词对应的文档列表即可。没错,在没有其他用户使用的情况下,这样的方法是可行的。但如果你有过一定的工程经验,你就会知道,在实际应用中,必然会有多个用户同时访问这个索引。
这个时候,如果我们直接更新倒排索引,就可能造成用户访问错误,甚至会引发程序崩溃。因此,一般来说,我们会对倒排表加上“读写锁”,然后再更新。但是,加上“锁”之后会带来频繁的读写锁切换,整个系统的检索效率会比无锁状态有所下降。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(21)

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

    作者回复: 综合你前一条一起回复,你说到了两个点上:
    1.倒排索引和kv不一样,posting list元素很多,每个元素都加标记代价太大。
    2.一个文档可能会影响多个key,因此每个文档都要修改标记的话,读写操作会很频繁,加锁性能下降。

    此外,还有一点是,加上标记也没啥用,在posting list求交并的过程中,依然要全部留下来,等着最后和全量索引合并时才能真正删除。这样的话不如直接用一个delete list存着,最后求交集更高效。

    2020-04-15
    4
  • 青生先森
    还是有点疑惑,可能太笨了?双缓存情况下,假如更新的索引中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
    3
  • Mq
    看不懂滚动合并机制,老师能结合具体数据分析下,例如我今天增加了几个网页,有倒排索引关键字的value都要加上这个网页,这个滚动合并的流程是咋样的。

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

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

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

    2020-05-14
    1
    2
  • CBGSIMON
    针对第三种方案的理解:最终合并到全量的索引中还是要全量遍历,但设计了这样的层级后,就减少了这样的频率。
    小的和小的合并,等小的达到一定程度再和大的合并

    没看出第2个相对第1个优化在哪里?
    第2个不也是要重建全量索引么?如果不是重建,是在原来的全量索引上更新,那更新的时候又要加写锁吧?

    作者回复: 对于第三种方案(滚动合并法),你的理解没错,通过分层的设计,使得我们可以减少全量合并的频率。而且,在大多数系统的实现中,其实最后一层的全量合并并不会执行,而是使用完全重建的方式重新生成全量索引。

    对于第二种方法(再合并法)和第一种方法(完全重建法)的区别,其实就在于是否要从头开始对所有的文档进行处理。
    第一种方法(完全重建法),需要将所有文档分片,然后分别建立多个小的索引文件,再将这多个小索引文件合并成一个全量索引文件。
    而第二种方法(再合并法),它利用已有的全量索引文件,直接和增量索引进行合并就可以了。和第一种方法相比,这样就省去了多个小索引文件生成和合并的过程。因此会更优一些。至于加锁问题,其实并不会加锁。因为我们是生成一个新的全量索引文件,然后将旧的删除。而不是直接在旧的全量索引文件上更新。这其实也是很多系统的设计思路:不进行原地更新,而是生成新的,旧的删除。

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

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

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

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

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

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

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

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

    2020-04-16
    1
  • 范闲
    1.如果增加一个删除标记,相当于增量索引的每个内容都有这样一个标记,随着增量的数量变大,内存占用会更高。
    2.利用删除列表就不会有这样的问题,同样可以避免加锁。

    作者回复: 这两点都很好。
    的确posting list里每个元素都加标记,这个代价会远大于lsm这种只存一个元素kv的场景。
    此外,一个文档被删除,它可能会影响很多key和posting list,这个读写加锁代价不小。
    还有,即使使用double buffer实现增量索引,但是这个标记也没什么用。我们在增量索引中求交集和并集时,依然要保留所有的元素,这样和全量索引的结果合并时才不会出错。因此提前打上标记并不能加快检索效率。不如最后记录一个delete list,然后快速求交集处理掉。

    2020-04-15
    1
  • 流浪在寂寞古城
    目前还没接触过那么大的检索场景。索引的操作无非是增、删、改、查。看到滚动合并法,查询的时候是每一个索引都要去召回吗?如果是update,在天级索引加上这个doc,召回、合并索引的时候取时间最新的吗?

    作者回复: 1.如果使用滚动合并法,那么查询时需要同时查询多个不同的索引,并将索引结果合并。
    2.在进行索引合并的时候,有可能有数据被更新,然后该数据在天级索引和全量索引中都有。这种情况下,应该是天级索引优先级大于全量索引(即最新数据覆盖旧数据)。当然,如果你的系统对于update的操作的处理是删除旧数据,然后为新数据生成一个新文档的话,那么只需要支持简单的索引结果合并就好。

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

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

    2020-06-06
    1
  • 牛牛
    看到`双缓冲`的实现、感觉跟redis的rehash思想有点儿类似 ?
    redis 进行rehash的是启用 ht[1], 然后一步步在添加的过程中搬移原ht[0]的数据、同时标记搬移的位置, 等到数据搬移完成、就将 ht[1] 切为 ht[0], 同时释放ht[0], 申请新的ht[1] 为下次rehash做准备

    双缓冲是, 更新B索引、保证A索引只读, 更新完成后A/B互换, 损耗就是双倍内存消耗, 不适合大量数据场景(不过也是一种无锁设计)

    作者回复: 是的。你这是一个很好的例子。你会发现类似的设计其实很常见。掌握这种设计思想,相信会对你设计和实现高并发系统有所帮助。

    2020-05-07
  • 时隐时现
    老师好,有2个问题:
    1、删除列表的结构是什么样的?我理解的删除分2种,删除关键字和删除文档。前者只需要将对应的kv提取即可,代价很小。后者还是需要根据文档关键字遍历(二分查找)每个posting list,这一操作并不比打deleted标签小,只是在查询时可以优先读取delete list,这样省去了增量索引和全量索引的归并代价。
    2、滚动合并
    需要和磁盘上的天索引合并,此时天索引要不要加锁,如果有查询怎么办?莫非还要对天索引复制一份执行读写分离?

    作者回复: 1.在许多系统的设计中,是没有update操作的。删除文档中的关键字,其实等价于删除旧文档,生成新文档。
    因此,如果是这样设计的话,删除列表只需要存文档ID就好了。
    2.滚动合并也会遵循读写分离的原则,读一个旧的天级索引,生成一个新的天级索引。这样处理会比较简单高效。

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

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

    2020-04-15
  • 一步
    在滚动合并方案中,查询也要一级一级的进行查询, 先查增量索引---> 天级索引----> 周级索引---> 最后是权量索引。 这个的话查询的链路增加了好多,查询的效率会降低多少?

    作者回复: 这些是可以并行查找的。而不是串行。
    而且一般来说,以现在的机器处理能力,周级索引其实也可以不用的,这样也能减少系统复杂度。
    因此一般系统实现就是:
    增量索引+ 天级索引+全量索引 三个索引并行检索,再合并结果。

    2020-04-15
  • 一步
    为什么在增量索引的方案中,对于删除的数据,我们不是像 LSM 树一样在索引中直接做删除标记,而是额外增加一个删除列表?
    这个我认为 ,删除的数据相对全量的数据是非常少的,如果用删除标记,那么全部的数据都要进行标记,这样大量的没有删除的数据都会有个未删除的标志,极大的浪费空间资源

    作者回复: 在另一条下面统一回复你了。

    2020-04-15
  • 对这个问题,老师故意在文章里说的很含糊,只说了个记录删除列表的思路😜。
    lsm之所以可以和删除标记一起存,核心在于类似kv存,删除标记和对应的v是共享k的,所以要拿是会一起拿出来,就可以判断数据这个时候存在不存在,相当于拿到了值的变迁历史。
    而这个场景,删除文档,对文档集合而言,也可以添加个删除标记,但对于索引而言,它涉及到很多关键字的poslist里对它的指向,这要一个个都加上吗,如果删除的不多,显然还不如最后返回的时候做一个全局的deletelist判断。

    作者回复: 哈哈,的确说得没那么透,只说了“怎么做”,但没说“为什么”。因此才在课后讨论题让大家想想为什么。
    你说到了很重要的一点,kv只有一个值,但倒排表是一整个posting list,所以修改代价会大。
    另一方面,即便是使用double buffer技术对增量索引做无锁更新,但增量索引检索过程中,依然要把所有被删除的文档保留到最后,再和全量索引做合并。
    那既然所有的标记都要保留到最后一步,不如直接在最后一步用一个delete list来求交集更快,逻辑也清晰。

    2020-04-15
  • pedro
    按照索引的高性能选择,全量索性是只读的,而增量索引和删除项是可读可写的,所以不会选择在索引上添加删除项,会拉低系统效率。

    作者回复: 你很好地吸收了读写分离的思想。全量索引上肯定是不能加删除项的。不过可读写的增量索引上面能否加上删除标记呢?你可以想一想。
    提示:
    1.加的话是否有性能损失。
    2.不管有没有性能损失,加上后,求检索结果的过程是怎么样的?加上这个标记和单独记录一个删除列表相比有帮助么?
    你在思考以后,可以再看看我的回复。

    2020-04-15
  • 那时刻
    在滚动更新中,周索引往全量索引更新的时候,需要加锁操作么?

    作者回复: 这一步我没有画,不过你可以沿着前面天级索引和周级索引合并的思路思考一下,包括总结时我强调的“读写分离”去想想,我相信,你应该可以得到“不要加锁”这个结论的。

    这里我也补充一点,就是周级到全量索引的合并,其实由于隔的时间已经很久了,因此,很多时候我们会直接完全重建全量索引,一方面,重建时间是足够的,另一方面,也等于定期给系统“重启”,保证系统的稳定性和正确性。

    2020-04-15
收起评论
21
返回
顶部