Milvus数据管理：删除的实现原理

本文将主要讲述 Milvus 是怎么实现删除功能的。删除是许多用户期待已久的功能，这次终于在 Milvus 0.7.0 版本中发布。区别于直接调用 FAISS 的 remove_ids 接口，为了让删除更加高效，并能够支持更多索引类型，我们做了全新的设计。

在 FAISS 中，删除 ID 和它对应的向量需要遍历所有数据以决定哪些向量需要删除

https://github.com/facebookresearch/faiss/wiki/Special-operations-on-indexes#removing-elements-from-an-index，频繁操作会极大地影响系统性能，更无法做到删除和查询并发执行。如果是已经落盘的数据，则需要把数据文件加载进内存进行删除，再重新落盘，代价非常大。这个方案自然无法运用在生产环境。此外，FAISS 目前只在 IndexFlat, IndexIVFFlat, IDMap 这三种索引类型上支持删除，而 Milvus 的目标是不仅让 FAISS 的所有 CPU 与 GPU 索引支持删除，在未来还能陆续扩展到其他对接的 ANNS 库中。所以，我们必须自己设计删除功能。

在上一篇文章 Milvus 如何实现数据动态更新与查询 中，我们了解到数据从导入直至落盘的全部过程。在这里我们先回顾一下其中的一些基本概念。Memory manager 管理所有 insert buffer，其中每个 MemTable 对应一个 Collection（在 Milvus 0.7.0 中 Table 被更名为 Collection），插入到内存中的数据会被自动切分成多个 MemTableFile，在 flush（落盘）时每个 MemTableFile 会被序列化成一个原始文件。这个架构在设计删除功能时依然保持。

我们将删除 API 定义为删除一个 Collection 内所有与传入的 Entity ID 对应的数据。设计删除功能时，我们首先把删除分为两个场景：第一种是删除依然还在 insert buffer 中的数据，第二种是删除已经落盘的数据。第一种场景比较直观，我们可以通过 ID 找到对应 MemTableFile，然后在内存中直接将数据删除（图一）。因为删除不能与插入数据同时进行，并且因为存在上篇文章中提及的落盘时将 MemTableFile从Mutable 转为 Immutable 状态的机制，删除操作只会在 Mutable buffer 中进行，所以删除操作也不会与落盘操作发生冲突，从而保证了数据的一致性。

（图一）

第二种场景相对更加复杂，也更加常见，因为大多数情况下数据停留在 insert buffer 中的时间都会很短，在短时间内就会落盘。将那些已经落盘的数据加载上来进行硬删除的方案效率太低，所以我们采用了另一种更高效的方案：软删除；不真正删除落盘的数据，而是另外存一份文件记录被删除的 ID。在进行需要读取数据的操作，例如搜索时，过滤掉那些已记录的被删除 ID。

而涉及到具体实现，我们就需要考虑几点问题。在 Milvus 中，数据只有落盘才可见，或者说可以搜到。因此，删除已经落盘的数据不需要在调用 delete API 时进行，而是将它放在下一次落盘的时候进行。能够这样做的原因是已经落盘的数据文件不会再有新增数据，所以软删除不会对已落盘的数据有任何影响。调用删除 API 时，对于还在 insert buffer 未落盘的数据，直接删除就可以；对于已经落盘的数据，则需要在内存中记录被删除数据的 ID。在落盘时，将被删除的 ID 写入 DEL 文件以用于记录对应 Segment 里哪些 Entity 被删除。落盘完成后，这些修改才可见。具体过程如图二所示。在 0.7.0 版本之前，我们只有 auto-flush（自动落盘）的机制。每隔 1 秒，后台线程会序列化 insert buffer 中的数据。在我们这次设计中，我们决定添加主动 flush 接口。这样，在调用 delete 接口后，用户可以选择再调用 flush，保证新增的数据可见，被删除的数据不会再被搜到。

（图二）

第二个问题是 Milvus 的原始文件和索引文件是两个独立的文件，在元数据中也是两行独立的记录。当删除某个 ID 时，我们需要找到 ID 对应的原始数据文件和索引文件，并且一起记录。于是，我们引入 segment 概念，一个 segment 包含原始文件（原始文件又包括原始向量文件和 ID 文件），索引文件，和记录被删除 ID 的 DEL 文件。segment 作为数据的基本读写和搜索单元，一个 Collection（图三）由多个 segment 组成，在磁盘上则是一个 Collection 文件夹下有多个 segment 文件夹。因为我们的元数据基于关系型数据库（SQLite 和 MySQL），记录 segment 内的关系非常简单，删除操作也不再需要对原始文件和索引文件做分别的处理。

（图三）

第三个问题则是，在搜索时，具体如何过滤已经被删除的数据。实际上，DEL 文件记录的 ID 是其在 segment 内存储数据的的 offset（偏移位）。由于已落盘的 segment 不会有新增的数据，所以 offset 也不会改变。DEL 文件在内存中的数据结构是一个 bitmap，其中的 active bit 代表被删除的 offset。我们对 FAISS 也进行了相应的修改：在 FAISS 中进行搜索时，会过滤掉 active bit 对应的向量，不再参与距离计算（图四）。在 FAISS 中具体的修改在此不做详述。

（图四）

最后一个问题属于优化：对落盘的文件进行删除时，需要首先找到被删的 ID 具体存在于 Collection 中的哪一个 segment，再记录它的 offset。最暴力的方法当然是将每一个 segment 中的 ID 都暴搜一遍。我们想到的优化方法是在每个 segment 内添加一个 bloom filter（布隆过滤器）。Bloom filter 是一种随机数据结构，用于判断一个元素是否存在于一个集合中。因此，我们可以只加载每个 segment 的 bloom filter，只有 bloom filter 判断被删的 ID 在当前 segment 中，我们才在该 segment 内寻找其对应的 offset，否则我们就可以忽略此 segment（图五）。我们选择 bloom filter 的原因是因为相比其他数据结构，例如哈希表，它用的空间更小，并且查询效率非常高。虽然 bloom filter 有一定概率存在 false positive（错误判断元素存在），但因为这个概率可以自己调节，我们可以将需要搜索的 segment 降到理想数量。Bloom filter 也需要支持删除，否则已被删除的 Entity ID 依然会在 bloom filter 中找到，导致误判率增加。因此，实现的时候，我们使用的是支持删除的 counting bloom filter。在这篇文章，我们不会对 bloom filter 的详细原理做太多介绍，感兴趣的读者可以参阅https://en.wikipedia.org/wiki/Bloom_filter。

（图五）

对应删除的实现，我们已经介绍的差不多了。大家已经知道，对于已经落盘的数据，我们采用的是软删除法。当被删除的数据越来越多的时候，为了清理这些被删除的数据，我们需要另外一个功能：Compact，能够将被软删除的数据真正删掉。Compact 做的事情除了删除数据外，如果 Segment 已经建了索引，也会将旧索引文件删除并且在后台重建索引。目前，用户只能手动调用 Compact 接口，实现数据的整理。未来我们希望能引入检查机制，例如当检查到删除的数据量超过一定阈值或者删除后的数据分布产生了一定变化，能够自动 Compact。

至此，我们已经基本概括了关于删除相关的功能和实现中的一些设计思想。当然，这部分还有很多的优化空间，我们也非常欢迎大家提出更多意见~