实时倒排索引
在线服务运行过程中，用户一般都会不断地执行添加、删除和更新操作。Vearch中的倒排索引（InvertedList）作为IVFPQ的一个核心数据结构，必须支持实时更新的特性，才能满足用户实时更新的需求。具体的要求为：支持动态地向倒排索引中添加、删除和更新索引，并且不能影响同时正在使用倒排索引的搜索（读）请求。
Faiss的倒排索引天生不支持实时更新，所以不能直接使用。Vearch在Faiss的倒排索引基础上，开发了一个实时倒排索引，以满足用户实时更新的需求。
说明：本文主要介绍实时倒排索引实时添加的功能，关于索引的实时更新和删除可以参考文章“Inplace-update和索引compaction”，这里不再赘述。
Vearch实时倒排索引是在Vearch系统本身的单线程更新机制，再结合以下两种技术，以支持实时更新的特性。
- 基于原子计数器的bucket长度更新。
- 基于延迟释放的Bucket动态扩展。
Vearch实时倒排索引分为多个bucket，每个bucket都有一个原子计数器记录当前bucket的长度。更新线程添加索引时，所有操作执行完之后，才更新原子计数器。搜索线程读取索引时，首先读取原子计数器，拿到bucket当前的长度，然后只读取小于等于长度的索引。这样，搜索请求如果拿到最新的计数器值，那么新增的索引就立马生效了；如果拿到旧的计数器值，也不会出问题，只是新增的索引要在下次搜索请求时生效。因此，实时添加索引的问题得到解决。
不断往Bucket中插入索引后，bucket初始化分配的内存可能就不足，需要分配更大的内存空间。但，这又引出另外一个问题，怎么在搜索请求还在读取原有内存区域时候，用新分配内存空间替换原有的内存空间。
接下来具体介绍延迟释放在Bucket动态扩展中的应用，参见图1。bucket空间不足后，实时倒排索引会分配一块现有空间2倍大小的新内存空间。然后拷贝旧空间中的所有索引到新空间。设置bucket的地址为新空间的地址。此时，新的内存空间已经生效，所有的读、写都在新内存空间进行。但在更新bucket地址为新地址前一瞬间，可能存在搜索请求拿到旧的内存地址，因此新内存地址生效后，还不能立即释放旧内存地址。Vearch实时倒排索引会等待一小段时间（默认1秒）之后，再释放旧的内存地址。
显然上面提到的延迟释放是基于一个假设，就是搜索请求都是很快的，一般都是在毫秒级就能完成。如果搜索耗时较长的话，可以适当增加延迟释放的等待时间。
