倒排索引是搜索引擎的核心技术，主要于解决海量数据下的快速检索问题。同数据库技术中索引原理一样，在搜索引擎中创建了倒排索引后，查询性能非常好，但是数据的快速/大量更新却是个棘手的问题。在实际应用中，往往优先保证检索性能而牺牲了更新的时效性。
本文主要介绍了我们是如何在保证检索性能情况下，通过底层数据结构的优化，实现实时倒排索引更新，即在文档更新后毫秒级内即可通过索引查询出来。
假设一个用户查询“java工程师”（即查询query），我们需要返回所有包含“java工程师”相关的文档（doc）。直观反应就是把所有的文档遍历一遍，在每个doc中查找，并判断其是否包含该query中所有的词，后返回包含该query的所有doc集合。文档集合比较小的时候，该实现方法是可行的，但如果候选文档集合大小为几千万、几亿（甚至几百亿：如Google），该实现方案就会面临比较大的问题：遍历全部文档做查询匹配，耗时可能是几秒、几十秒甚至更高，对一个在线服务来说是不可接受的。因为搜索服务是需要立刻返回结果，需要一秒内或几十毫秒就给用户呈现搜索结果，让用户感受不到计算延迟。为了解决这个问题，搜索引擎采用了“倒排索引”的技术来实现在海量文档中快速查询。
倒排索引（英语：Inverted index），也常被称为反向索引，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中常用的数据结构。
有两种不同的倒排索引（反向索引）形式：
- 一条记录的水平反向索引，包含每个引用单词的文档的列表。
- 一个单词的水平反向索引，又包含每个单词在一个文档中的位置。
第二种的形式倒排索引提供了更多的兼容性（比如短语搜索）和计算能力，但是需要更多的时间和空间来创建。为了简化、清晰的说明问题，这里我们只讨论种倒排索引形式，也是主要的索引形式。
以如下需要被索引的文本为例：\displaystyle T_{0}=}"it\quad is\quad what\quad it\quad is
"a": {2} "banana": {2} "is": {, 1, 2} "it": {, 1, 2} "what": {, 1}
再假设检索query = “what is it"，我们获取3个词（“what”, “is”, “it”）对应的反向索引，将3个文档ID集合进行求交，即可得到检索需要的目标结果集，检索条件"what", “is” 和 “it” 将对应这个集合（文档数量编号从零开始）:{\displaystyle \{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}}{0,1}∩{0,1,2}∩{0,1,2}={0,1}反向索引的方法，需要事先为文档建立索引，然后利用索引来查找要检索的字符串。虽然事先建立索引需要花费时间，但是该方案的突出优点是即使文档的数量增加，检索速度也不会大幅下降。反向索引的数据结构是典型的搜索引擎检索算法重要的组成部分，对检索系统性能至关重要。一般来说，搜索引擎包括两个部分，离线构建倒排索引和在线检索。其中在线检索部分，加载倒排索引文件后，接收查询query，将query转换成一个个单词，对各单词对应的倒排集合进行求交运算，后得到目标文档集合。关于检索部分相关技术也非常丰富非常有意思，后续文章再进行介绍，本文主要介绍倒排索引。前文中描述的索引构建方法是对输入数据进行批量构建处理，在构建完成后生成倒排索引文件，索引文件加载到内存再进行检索。在信息检索领域中，这被称为"静态索引"（Offline Index Construction），静态索引的优点明显：支持磁盘文件存储，节省空间、检索效率高，可以支持很大的索引量等。但其也存在缺点：创建完索引、数据装入时就已经定型，不能进行新增、修改等操作。
在互联网环境中，搜索引擎需要处理的文档集合往往都是动态集合，初始索引构建完成后，仍然会有新文档不断进入系统，而且原有文档集合中的部分文档也可能会有删除或修改需求。这要求文档集索引构建完成后，也要能对新的文档更新进行支持，让新增文档迅速被索引和检索到，即动态索引。此问题常见于电商领域或生活服务领域里，如商品的上下架、服务内容的更新等，都会引发索引的动态更新问题。因此，我们需要采取一些策略和方法来解决该类型的问题，提高索引的实时性。1） 周期性对文档进行全量重建索引。全量文档重建索引需要时间比较长，适用于对文档更新时效性要求不是很强，另外新文档检索不到也没有很大影响的场景，优点是比较简单且节省空间，全网搜索引擎一般会采用这个策略。
2） 基于主索引（静态索引）的前提下，构建辅助索引（动态索引），用于储存新文档，维护于内存中，当辅助索引达到一定的内存占用时，写入磁盘与主索引进行合并。五八是生活服务类场景，帖子（文档）的更新和新增很频繁，并且用户对时效性要求很高，期望更新能快速生效。所以我们采用的是第二种动态更新策略。五八搜索是基于内部自研的搜索引擎实现，其索引构建系统整体如下图所示。
在离线阶段，批量获取所有的文档并进行数据分片，通过索引程序”indexer“，生成静态倒排索引文件，然后把倒排索引文件推送给在线检索程序去加载。检索程序加载倒排文件后，对外提供检索服务。同时，在检索服务内部，启动了一个文档接收线程（启动一个服务端口）和一个动态索引更新线程，索引更新线程取到更新文档，在内存中创建增量倒排索引。增量倒排索引是在内存中建立的倒排索引，增量倒排索引的结构与全量静态倒排索引基本一致，主要差异是索引大小不同。静态倒排索引结构如下图所示。倒排索引结构看似复杂，但经过梳理后可简单分为三个部分，部分是meta信息，第二部分是文档ID列表（docid数组），第三部分是词在文档内部出现的位置信息。设计成三个部分分开存储可以获取更高的检索性能且节省空间：文档ID列表以数组形式存储访问效率高，对CPU cache line友好。另外，位置信息单独存放，是因为大部分情况下位置信息都不会访问到，只有在求交完成后做相关性计算时才会用到，召回计算阶段不需要位置信息，所以单独存放需要用到时再去访问效率更高。另外相同类型数据连续存放可以做索引压缩，节省空间、提升cache hit。如前所叙，该索引结构采用了固定长度的数组方式进行存储，它的问题是一旦构建完成后不能再新增元素。为了解决这个问题，引入了增量索引来支持新增/更新文档。增量索引和全量的静态倒排索引结构本质是一样的，增量索引也是累积一段时间数据后触发小批量构建，相当于一个小的静态索引。为了让新增文档能被快速检索到，小批量构建索引的时间间隔需要比较短，我们内部配置通常是3秒。也就是说每3秒会建一个增量索引段，但这样的话内存中就会有很多小的增量索引。为了解决增量索引量太多的问题引入了索引段合并策略，小的索引段是3秒，每个索引段的数目大是1，超过大数目就会往下一个索引段合并，下一个索引段是15分钟段。当15分钟段超过大数目会往6小时段合并。6小时段往天段合并，天段往月段合并，月段往段合并，段不会再合并（各个段的时间大小是可以自由配置）。各个索引数据段的合并过程如下图所示。静态倒排索引是对初始文档集合建立的索引结构，一般存储在磁盘文件中，而动态索引是对新增数据实时建立的倒排索引，一般存储在内存中。当有新文档进入索引系统时，对其进行解析并将解析结果加入到动态索引中。而为了实现倒排索引的动态更新，还需要另外一个数据结构辅助，即删除文档列表。删除文档列表是由已经被删除的文档数据形成的一个文档ID列表。在每个倒排索引数据段上，都有一个删除列表用来记录本段中哪些文档ID被删除了。当一篇文档内容被更改，实现过程是旧文档先被删除，然后系统再增加一篇新的文档。通过这种间接的方式，实现对内容更改的支持。另外，如果一个文档被删除，也只是在删除列表中增加该文档的ID，并不会在倒排索引中真正删除，即标记删除。倒排索引按文档量大小分段，增加数据时不断产生小的增量数据段，小段不断往大段合并，整体策略清晰完整。但还存在更新延迟问题，在实时性要求特别高的场景下，无法满足需求。上文提到动态索引实现的策略是，每隔一小段时间（配置是3秒）构建一个增量索引，但在构建增量索引的过程中，这个索引段是无法参与检索的，存在3秒的检索时间延迟，当增量的索引建完后才能参与检索。这是业界比较标准的做法，即读写分离。搜索引擎被设计主要用于查询服务，即读，典型的是场景是一次写完（构建倒排索引），后面全部用于读，大部分的性能优化或者数据结构设计目的都是服用于查询。所以一开始设计倒排数据结构，就不适用于并发读写。随着搜索内核（索引和检索模块）应用的业务越来越多，特别是五八云搜接入了大量特色各异的搜索业务，有一部分业务对索引更新速度要求很高，对3秒钟的检索更新延迟无法接受，如广告的投放、扣费等场景。鉴于此类需求，我们重新设计了动态索引数据结构，使其能够支持实时更新和检索，新增一篇文档立刻可以被检索到，即一边更新倒排索引结构，同时支持其他线程并发查询。我们重新设计了3秒段（即写入段）的索引结构，使其在不加锁情况下支持读写并发（加锁会造成检索性能不可接受）。每个新文档被索引后，立刻就可以被检索到，解决了延迟3秒的等待问题。同时其他段的索引结构不变，各个索引段的合并逻辑保持不变，整个索引更新过程仍然清晰完整。核心实现了倒排列表、单值正排字段、多值正排字段、跳表4个核心数据结构。其中跳表的实现在redis和leveldb中都有，在这里不再介绍，感兴趣的同学可以直接看下相关源码。索引中使用跳表，主要是做字符串到term对应倒排表的查找过程。
由于设计的实时索引只服务于小数据段，所以一开始就设定该段的大文档量为64K。超过64K或者时间段到期就重新新增一个实时索引段，旧的实时索引段就不再接受更新，开始合并过程。这样设计的原因有两个，一是实时索引段太大影响检索性能；二是64K可以用2个字节表示，节省docid字段的存储空间。实时索引倒排结构设计
实时索引的倒排数据结构如下图所示，每个term（即词）的倒排结构是一个链表，链表中每个元素是一个指针，指向的是一个数组的首地址，而数组中存储的才是真正的倒排数据，即docid 列表。链表中每个节点对应的数组，其长度并不相同：个数组大小为4，第二个数组大小为8，呈二倍关系，以此类推。假如完全使用链表记录实时更新文档中term对应的docid列表，每个docid均为一个链表节点；查询时需要对多个term对应的倒排链进行求交集运算，链表的访问过程CPU cache line很不友好，在线查询性能会很差，同时较多的next指针也会造成很大的空间浪费。而数组在查询时的运算性能较好，节省空间。考虑到空间和性能的平衡，采用链表和数组二者结合的方式，上层使用链表进行动态扩展，下层使用数组存储真正的docid信息，则可以获得较低的空间占用率和较好的查询性能。为什么个节点对应的数组大小默认为4？请看下面表格，这是统计一个线上典型的业务，3秒钟内平均新增的文档量是204个，包含的term个数是28284，88.7%的term的倒排链（doc list）长度不大于4，95%的term的倒排链（doc list）长度不大于8。所以首节点数组大小设置为4，88.7%的情况下可满足业务需求。若组数size设置太大，在绝大多数情况下会造成数组空间浪费；若数组size设置太小，则会生成较多的链表节点，造成指针空间浪费。所以，首节点数组大小折中取4，即可大致满足需求。若默认大小的数组不够使用，则可按照大小翻倍的策略动态的进行数组扩充。
| doc list长度 |
term 数目均值 |
term占比 |
| (0, 4] |
25091.1 |
88.7% |
| (4, 6] |
1242.1 |
4.3% |
| (6, 8] |
567.9 |
2% |
| (8, 10] |
323.2 |
1.1% |
| (10, 100] |
1003.68 |
3.5% |
| (100, 500] |
55.7 |
0.2% |
| (500, 1000] |
0.28 |
0% |
| (1000, +) |
0.0003 |
0% |
该数据结构为什么可以实现读写同时访问不用加锁？这主要是由倒排索引的特性决定。前面提到倒排索引数据结构只有新增，没有更新或者删除（更新和删除都是采用标记删除的方式）。也就是说，每当有新的数据写入时，只会在链表尾部增加链表节点，或在链表尾结点关联的数组中增加数组元素（数组填满时需要增加新的链表节点和数组，数组未填满则直接在数组中写入元素）。以增加链表节点为例：写线程申请链表节点空间并写入数据，后进行一次指针赋值，将新节点链入到链表尾部，该指针赋值操作可以不需要加锁，读写可以并发执行。整个流程中读线程均可正常操作，无需读写互斥。
考虑到这样一种情况，如果在新增一个文档X的过程中，文档中的termA写入了倒排索引，而 termB还没有完成写入操作。此时如果有查询，倒排链求交后的结果集包含X，此时召回文档X可能是错误的，因为处于X文档写入的中间状态，并没有完全写完。为了解决这个问题，增加了一个整形正排字段MAXID，该变量值是完成文档写入后再更新，即增加1，当查询出来的文档id大于MAXID值，说明是召回了正在更新中的文档，将其过滤掉。实时索引正排结构设计
下面再介绍下正排数值字段的数据结构设计。在只读段中，单值的正排字段只需用一个固定大小的数组表示即可。在写段中，如果直接使用数组，则会存在更新问题：若初始设置的数组太小，新增文档则会频繁的重新申请空间；若初始设置的数组太大，在大部分场景下就会导致空间浪费。所以采用了下图所示的”动态数组“的来解决该问题。采用两级数组的方式来支持正排的更新/写入，级数组不存储真正的正排值，只存储第二级数组的指针/地址，第二级数组才真正存储正排值。每级数组包含是256个元素，级数组在初始化时直接分配；第二级数组则在使用中进行动态分配，超过256个元素时才分配第二个二级数组。每次分配的小单位是256，这样做方便采用内存池管理，但会存在一定的内存浪费。同前文的倒排链表一样，该正排结构也只在尾部进行数据写入，不会更改中间位置，所以不需要读写加锁。上述的正排字段为简单的正排结构，主要用于单值的正排字段场景。对于多值正排字段，稍微复杂了点，因为存储的数组元素是变长，一开始不确定大小，需要对在单值正排字段的格式上稍作变化，多值正排字段结构如下图所示，原理基本一样，相信技术同学看图应该就可以明白是怎么回事。实时索引结构重构完成后，进行了如下的测试验证：更新写入单个文档并进行查询操作，将文档发送后与检索到的时间间隔定义为更新延迟。采用线上数据进行实测，99.9%的文档更新延迟在20毫秒内。考虑到文档需要进行各种预处理和分词，以及网络、队列等消耗，这个更新延迟也在正常范围内。
在检索性能上经过4轮优化，终做到和旧版基本一致。导流对比数据如下表所示：
| 类型 |
QPS |
处理时长(ms) |
队列等待(ms) |
大于125ms |
| 旧版本 |
1067.285 |
1.031 |
0.036 |
0.008 |
| 新版本 |
1067.282 |
1.045 |
0.035 |
0.008 |
| (新-旧) * /旧 |
0.00% |
1.36% |
-2.78% |
0.00% |
在更新速率方面统计数据如下(单线程索引更新）：
| 类型 |
新增文档速率 |
删除速率 |
| 旧版本 |
442.66 |
148.23 |
| 新版本 |
414.17 |
140.87 |
| (新-旧) * /旧 |
-6.44% |
-4.96% |
另外，从内存占用量新版本有百分之几的降低。虚拟内存VIRT占用平均值降低了约3.4%， 从73.9G降低至 71.4G；常驻物理内存RSS占用平均值降低了约6.1%， 从21.46G降低至20.15G；索引文件内存映射SHR共享内存占用平均值降低约 2.97%， 从14.3G降低至13.9G。从CPU使用量上看也基本平稳，无明显变化。整体上，在保证其他功能和性能基本相同的前提下，索引更新时效性得到了极大提升，达到了初设计目标。
- https://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95
-
https://www.jianshu.com/p/98611430535b
卢克，五八同城架构师，对搜索技术有浓厚兴趣，专注索引擎领域十年。目前团队正在招聘搜索研发工程师，算法和工程皆可，欢迎自荐或者推荐: luke@58.com