关于数据库:干货分享｜Bitset-应用详解

作者：蔡宇东

编者按：
Milvus 2.0 带来了不少新性能。在这些新性能中，工夫旅行（time travel）、属性过滤和删除操作互相关联，因为这三个性能是通过一个独特的机制——Bitset 实现的。Milvus 研发工程师蔡宇东将为大家解析 Milvus 中 Bitset 的概念，并通过三个例子解释它是如何反对删除操作、工夫旅行和属性过滤的。

什么是 Bitset？

从 Milvus 0.7.0 版本开始，为了反对 Delete 性能，咱们引入了 Bitset，用于标记 segment 中的每行 entity 是否已被删除（若 Bitset 对应的 bit 位为 1，表明该行 entity 已被删除，该行 entity 在查问时不参加运算）。
在 Milvus 2.0 版本，咱们进一步扩大了 Bitset 的应用。Bitset 最根本的语义放弃不变——若对应的 bit 位为 1，表明该行 entity 不参加查问运算。但 Bitset 的应用不再局限于 Delete 操作，有 3 种操作会影响 Bitset，它们别离是:

1. 属性过滤
2. 数据删除
3. 工夫旅行

在 Milvus 中，Bitset 是如何计算的？

接下来，咱们用三个例子来阐明 Bitset 是如何计算的。
假如有 1 个 segment，咱们对这个 segment 顺次执行了 3 次 DML（data manipulation language）操作：

Order of DML events

• 在 ts = 100 时，执行插入操作，插入了 4 条 entity，它们的 primary_keys 别离为 [1, 2, 3, 4]；
• 在 ts = 200 时，执行第二次插入操作，插入另外 4 条 entity，它们的 primary_keys 别离为 [5, 6, 7, 8]；
• 在 ts = 300 时，执行 Delete 操作，删除了 2 条 entity，它们的 primary_key 别离为 [7, 8]。
• 同时假如在进行查问时，通过属性过滤失去的后果为 primary_key = [1, 3, 5, 7]。

案例一

Search with time_traval = 150
假如用户执行第一次查问，指定 time_travel = 150。Bitset 的计算过程如上图所示。
filter_bitset 初始状态为 [1, 0, 1, 0, 1, 0, 1, 0]（此时 bit 位为 1 示意无效），因为查问时指定的 time_travel = 150，该时刻 pk = [5, 6, 7, 8] 的 entity 还没有插入，所以 pk = [5, 6, 7, 8] 的 entity 在 Bitset 中对应 bit 位都要清零。计算失去 filter_bitset_2 = [1, 0, 1, 0, 0, 0, 0, 0]。又因为最终后果 bitset 中的 1 应该示意该行 entity 有效，所以须要对 filter_bitset_2 中所有 bit 位取反，失去 filter_bitset_3 = [0, 1, 0, 1, 1, 1, 1, 1]。
del_bitset 初始状态为 [0, 0, 0, 0, 0, 0, 1, 1]，思考查问时指定的 time_travel = 150，该时刻 delete 操作还没有执行，所以 Bitset 所有 bit 位都应该清零，示意所有的数据都是无效的。这样就失去了 del_bitset_2 = [0, 0, 0, 0, 0, 0, 0, 0]。
把 filter_bitset_3 和 del_bitset_2 进行 OR 操作，可失去最终 result_bitset = [0, 1, 0, 1, 1, 1, 1, 1]。
最终，咱们会用 result_bitset 去参加查问运算。

案例二

Search with time_traval = 250
假如用户执行第二次查问，指定 time_travel = 250。Bitset 的计算过程如上图所示。
与第一个案例一样，filter_bitset 初始状态应该是 [1, 0, 1, 0, 1, 0, 1, 0]。
当 ts = 250 时，所有 entity [1, 2, 3, 4, 5, 6, 7, 8] 曾经被插入到 Milvus 中。因而，filter_bitset_2 和之前 filter_bitset 的后果放弃不变。同样，咱们要对 filter_bitset_2 的所有 bit 位取反，失去 [0, 1, 0, 1, 0, 1, 0, 1]。
del_bitset 初始状态为 [0, 0, 0, 0, 0, 1, 1]。同样思考查问时指定的 time_travel = 250，该时刻 delete 操作还没有执行，所以 Bitset 所有 bit 位都应该清零，示意所有的数据都是无效的。因而，time travel 后的 del_bitset_2 = [0, 0, 0, 0, 0, 0, 0]。
把 filter_bitset_3 和 del_bitset_2 进行 OR 操作，可失去最终 result_bitset = [0, 1, 0, 1, 0, 1, 0, 1]。
最终只有 entities [1, 3, 5, 7] 会参加之后的查问运算。

案例三

假如用户执行第三次查问，指定 time_travel = 350。那么，Bitset 的计算过程是什么样的？参考上方两个案例进行思考。

预报

不久之前，咱们还介绍了 Milvus 2.0 中的数据删除设计。
在接下来的文章中，咱们将持续介绍 Milvus 2.0 中数据压缩、动静负载平衡等性能背地的逻辑，欢送大家持续关注！

Milvus 我的项目地址：https://github.com/milvus-io/…
Milvus 主页及文档地址：https://milvus.io/
Milvus Slack Channel：milvusio.slack.com