专栏首页Reinvent Data ScienceMilvus数据管理:删除的实现原理

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。

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

本文分享自微信公众号 - ZILLIZ(Zilliztech),作者:竺知茹

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Chat with Milvus #10 回顾- Milvus 性能指标

    - Milvus 的顾老师教你怎么看 Milvus 性能报告与如何达到最佳性能。

    ZILLIZ
  • 快速搭建对话机器人,就用这一招!

    问答系统是自然语言处理领域一个很经典的问题,它用于回答人们以自然语言形式提出的问题,有着广泛的应用。其经典应用场景包括:智能语音交互、在线客服、知识获取、情感类...

    ZILLIZ
  • 利用Doc2Vec和Milvus搭建相似文章召回服务

    上星期六很高兴请到了我们 Milvus 用户-松鼠,来与我们做了一期直播。想知道如何用 Doc2vec 和 Milvus 做相似文章推荐吗?欢迎点击视频看回放~

    ZILLIZ
  • 小程序批量删除云数据库里的数据

    一看我们就能知道这是写在云函数里的。所以我们批量删除数据库里的数据,必须是通过云函数来实现批量。

    编程小石头
  • 【精选】Jupyter Notebooks里的TensorFlow图可视化

    前言 前提:假设你熟悉Python,TensorFlow和Jupyter notebooks。 我们的目标只是可视化计算图。 TensorFlow操作形成计算图...

    量化投资与机器学习微信公众号
  • VS2015菜单栏重复删除

    只要选择工具栏自定义那个选项,在多余命令的下方,先删除几个外部命令,然后把空行删除,最后全部重置即可

    Enterprise_
  • 3分钟短文 | Linux 组删除 groupdel 用之前,注意一个细节

    在Linux中,组用于组织和管理用户帐户。组的主要目的是,可以在组内用户之间共享的给定资源,定义一组特权,例如读取,写入或执行权限(r-w-x)。

    程序员小助手
  • Mybatis源码分析之Mapper注册与绑定

    Mybatis 是一个「面向 sql」的持久层框架,它可实现动态拼装 sql,极其灵活,同时避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集,其插件...

    张乘辉
  • 我们体验了三款最热版自动驾驶系统,比拼结果竟然是……

    车云按:现如今,无人驾驶技术尚处于起步阶段。不过我们已经看到了像Waymo以及Uber这样的互联网科技公司在进行全无人驾驶技术方面的尝试。而主机厂通用在收购了C...

    企鹅号小编
  • “节流函数”提高性能

    浏览器中DOM操作比起非DOM交互需要更多的内存和CUP时间,连续的DOM操作有可能会导致浏览器挂起,甚至崩溃。尤其IE中的onresize事件。 高频率的更改...

    前端黑板报

扫码关注云+社区

领取腾讯云代金券