Milvus存算分离系列-4: Delete之痛

前言：痛在何处

对于大多数数据库来说， “删除”相比于“新增”都是更痛，代价更高。原因如下：

1. delete要求“已知”，即需要知道要delete的目标是不是真的在数据集合中，所以delete实际上隐含了至少一次“查询”
2. delete要求更改“过去的数据”，这实际上对系统提出了“随机写/删”的要求，且不论随机写/删会不会给存储留下“洞”，仅是对存储设备本身的性能而言，随机操作的性能损失往往都在2个数量级有余。

以上两点，使得delete对于数据库的设计和实现都提出了额外的要求。

Milvus的Delete之痛

对于Milvus这种存算分离的向量数据库，删除操作的痛点比其他数据库更甚：

• 向量索引的节点删除代价极大， update in place肯定不可接受。

原地更新成本太高

• 存算分离的架构下，巨大的delete范围。由于milvus segment的生成/存储/使用的位置是分离的，分别是datanode, 对象存储和querynode。这就使得一个delete语句，其适用的范围不是某一个文件夹或者某一个bucket，而是整个计算节点群，即如果有任何一个潜在的delete segment没有正确地收到对应的delete语句，就有可能导致不可见的数据还是被查询出来。

Milvus delete的实现

单机层面的基本原则：delete mask

保持vector index的immutable属性，通过bitset掩码的方式来使得被删除的vector不可见。如下图，在vector index中node=2被delete mask标记为1, 即deleted。那么在vector index traverse的过程中，node2会被跳过，但该节点与其他节点的link仍然被作为检索的edge进行使用。

分布式层数据流

如上图所示，在milvus中，delete和insert一样，同样要双写存储和计算节点。在DataNode上，delete操作被存储为deltalogs然后upload到object storage上, 在QueryNode上，delete被delegator转发给所有“可能包含对应delete数据”的segment，在对应计算节点上生成对应的delete mask以供查询，从而保证delete的可见性。

疑问：为什么要广播delete

在前几篇文章中我们提到，milvus的查询request都是发给delegator再由delegator转发给其所管辖的segment的，之后再由delegator汇总查询结果返回给proxy。那么这里一个很自然的想法是，为什么不把delete mask只存在delegator上，然后在汇总查询结果的时候将deleted rows去除掉呢？这样就能避免广播delete造成的写放大问题，整个流程也会变得简单。

如此的确是能保证查询的正确性，但是却不能保证查询结果符合client需求，因为“汇总再删除”可能导致汇总的结果根本不足topk。如下图所示，client要求top2, 3个segment各自返回自己的top2，但问题是此时的delete mask中，12348都已经被置为1了，那么汇总后就只有pk5这一个结果。相比之下，如果delete mask广播到各个segment上，则不会出现这个问题。

top不满问题

遗留问题：如何保证时序正确性的delete

上文所介绍的主要是静态条件下delete问题，而在一个实时更新的系统中。“看到数据被删除”和“何时才能看到被删除”有很大的不同，后者对于delete的时序提出了更高的要求，这个问题我们会在后续的文章中展开讨论。

总结

本文从存算分离的视角出发，审视了milvus这一类架构下delete设计与实现的痛点，并介绍了针对这些痛点milvus采用的对策。