返回到 Qdrant 内部

Qdrant 内部结构：不可变数据结构

安德烈·瓦斯涅佐夫

·

2024年8月20日

数据结构 101

上过编程课程的人可能会记得，没有一种通用的数据结构。 一些结构擅长通过索引访问元素（如数组），而其他结构则在插入效率方面表现出色（如链表）。

然而，当我们从理论数据结构转向现实世界的系统，特别是在性能关键的领域如 向量搜索 时，情况变得更加复杂。 大O表示法 提供了一个良好的抽象，但它并不考虑现代硬件的现实：缓存未命中、内存布局、磁盘I/O以及其他影响实际性能的低级考虑因素。

从硬件效率的角度来看，理想的数据结构是一个可以在单个线程中顺序读取的连续字节数组。这个场景允许硬件优化，如预取、缓存和分支预测，发挥最佳效果。

然而，现实世界的用例需要更复杂的结构来执行各种操作，例如插入、删除和搜索。这些要求增加了复杂性并引入了性能权衡。

可变性

处理数据结构时最重要的挑战之一是确保可变性——在创建后能够更改数据结构的能力，特别是在快速更新操作中。

让我们考虑一个简单的例子：我们想要按排序顺序迭代项目。 在没有可变性要求的情况下，我们可以使用一个简单的数组并对其进行一次排序。 这非常接近我们的理想场景。我们甚至可以将结构放在磁盘上 - 对于一个数组来说这很简单。

然而，如果我们需要向这个数组中插入一个项，事情变得更加复杂。 向排序数组中插入需要移动插入点之后的所有元素，这会导致每次插入的时间复杂度为线性，对于许多应用来说这是不可接受的。

为了处理这种情况，更复杂的结构如 B-trees 开始发挥作用。B-trees 专门设计用于优化大型数据集的插入和读取操作。然而，它们牺牲了数组读取的原始速度，以获得更好的插入性能。

这是一个基准测试，展示了在Rust中遍历普通数组与BTreeSet之间的差异：

use std::collections::BTreeSet;
use rand::Rng;

fn main() {
    // Benchmark plain vector VS btree in a task of iteration over all elements
    let mut rand = rand::thread_rng();
    let vector: Vec<_> = (0..1000000).map(|_| rand.gen::<u64>()).collect();
    let btree: BTreeSet<_> = vector.iter().copied().collect();

    {
        let mut sum = 0;
        for el in vector {
            sum += el;
        }
    } // Elapsed: 850.924µs

    {
        let mut sum = 0;
        for el in btree {
            sum += el;
        }
    } // Elapsed: 5.213025ms, ~6x slower

}

向量数据库，如 Qdrant，必须处理各种各样的数据结构。如果我们能够使它们不可变，这将显著提高性能并优化内存使用。

不可变性如何提供帮助？

不可变优势的很大一部分来自于这样一个事实：在我们开始构建结构之前，我们已经知道需要放入结构中的确切数据。最简单的例子是一个排序数组：我们准确知道我们需要将多少元素放入数组中，因此可以一次性分配确切的内存量。

更复杂的数据结构可能需要在构建结构之前收集额外的统计数据。 与Qdrant相关的一个例子是 标量量化：为了选择合适的量化级别，我们必须了解数据的分布。

计算这种分布需要事先知道所有数据，但一旦我们拥有它，应用标量量化就是一个简单的操作。

让我们来看看一个非详尽的数据结构列表，以及通过使它们不可变可以获得的潜在改进：

有关HNSW中有效载荷感知连接的更多信息，请阅读我们的 上一篇文章。

这次，我们将重点关注Qdrant的最新新增功能：

• 具有完美哈希的不可变哈希映射
• 碎片化的矢量存储.

完美哈希

哈希表是几乎所有编程语言中最常用的数据结构之一，包括Rust。 它通过键提供对元素的快速访问，读取和写入操作的平均时间复杂度为O(1)。

然而，有一个假设需要满足，以便哈希表能够高效工作：哈希碰撞不应造成太多开销。 在哈希表中，每个键被映射到一个“桶”，即存储值的位置。 当不同的键映射到同一个桶时，就会发生碰撞。

在常规可变哈希表中，通过以下方式实现冲突的最小化：

• 增加桶的数量以降低碰撞的概率
• 使用链表或树来存储具有相同哈希值的多个元素

然而，这些策略有开销，如果我们考虑使用高延迟存储如磁盘，这些开销就变得更加显著。

确实，从磁盘的每次读取操作的速度比从RAM读取慢几个数量级，因此我们希望首次尝试就能知道数据的正确位置。

为了实现这一点，我们可以使用所谓的最小完美哈希函数（MPHF）。这种特殊类型的哈希函数是为给定的一组键专门构建的，它保证在使用最少数量的桶的同时不会发生冲突。

在Qdrant中，我们决定使用ph crate 🦀中由皮奥特·贝林实现的基于指纹的最小完美散列函数。 根据我们的基准测试，使用完美散列函数确实引入了一些散列时间的开销，但它显著减少了整个操作的时间：

尽管哈希的绝对时间更长，但整个操作的时间却更短，因为PHF保证没有碰撞。当我们考虑磁盘读取时间时，这种差异更为显著，可能达到几毫秒（10^6ns）。

PHF RAM大小与ph::Function成线性关系：10k元素时为3.46 kB，350M元素时为119MB。 构建哈希函数所需的时间出奇地短，我们只需要做一次：

在Qdrant中使用PHF可以最小化冷读取的延迟，这对于大规模多租户系统尤为重要。使用PHF，只需从磁盘读取一页即可获得数据的确切位置。

碎片整理

当你从磁盘读取数据时，你几乎从来不会读取单个字节。相反，你读取的是一个页面，这是一个固定大小的数据块。在许多系统中，页面大小是4KB，这意味着每个读取操作将读取4KB的数据，即使你只需要一个字节。

向量搜索，另一方面，需要读取大量小向量，这可能会产生较大的开销。特别是在我们使用二进制量化时，这一点尤其明显，即使是大型的OpenAI 1536维向量的大小也被压缩到192 字节。

这意味着，如果我们在搜索过程中访问的向量随机分布在磁盘上，我们每个向量将不得不读取4KB，这比实际数据大小多20倍。

然而，有一个简单的方法可以避免这种开销： 碎片整理。 如果我们知道一些关于数据的额外信息，我们可以将所有相关向量合并到一个单独的页面中。

这附加信息可以通过有效载荷索引获取。

通过指定负载索引，通常用于过滤，我们可以将所有具有相同负载的向量放在一起。 这样，读取单个页面时也会读取附近的向量，这些向量将用于搜索。

这种方法对于多租户系统特别有效，在这些系统中，只有一小部分向量被积极用于搜索。此类部署的容量通常由热子集的大小定义，热子集的大小远小于向量的总数。

将相关向量分组在一起可以通过避免缓存无关数据来优化热门子集的大小。以下基准数据比较了碎片整理和未碎片整理存储的RPS：

数据集大小： 2M 768d 向量 (~6Gb 原始数据)，二进制量化，650Mb RAM 限制。所有基准测试均在最小 RAM 分配下进行，以演示磁盘缓存效率。

正如您所见，最大影响体现在小租户规模上，碎片整理使我们能够实现100倍的RPS。当然，碎片整理在实际世界中的影响取决于特定的工作负载和热点子集的大小，但启用此功能可以显著提高Qdrant的性能。

请查阅有关如何在索引文档中启用碎片整理的更多详细信息。

更新不可变数据结构

人们可能会想知道，当一切都是不可变的时，Qdrant如何允许更新集合数据。确实，Qdrant API允许在任何时候更改任何向量或负载，因此从用户的角度来看，整个集合在任何时候都是可变的。

正如每个体面的魔术把戏通常发生的那样，秘密令人失望地简单：Qdrant中的数据并非都不可变。在Qdrant中，存储被划分为片段，这些片段可以是可变的或不可变的。新数据总是写入可变片段，随后通过优化过程将其转换为不可变片段。

如果我们需要更新不可变的或当前优化的区段中的数据，而不是就地更改数据，我们执行一次写时拷贝操作，将数据移动到可变区段，并在那里更新。

原始片段中的数据被标记为已删除，然后通过优化过程进行清理。

缺点及如何补偿

虽然不可变数据结构非常适合读操作密集的场景，但它们也有一些权衡：

• 更高的更新成本: 不可变结构在更新时效率较低。摊销时间复杂度可能与可变结构相同，但常数因子更高。
• 重建开销： 在某些情况下，我们可能需要为相同的数据重建索引或结构多次。
• 读密集型工作负载： 不可变性假设一个搜索密集型的工作负载，这对于搜索引擎来说是典型的，但并不是所有应用程序的情况。

在Qdrant中，我们通过允许用户根据他们的特定工作负载调整系统来缓解这些缺点。 例如，改变段的默认大小可能有助于减少重建索引的开销。

在极端情况下，多段存储可以作为单个段运行，当需要时回退到可变数据结构。

结论

不可变数据结构虽然实现起来比较复杂，但在性能上提供了显著的提升，尤其是在像搜索引擎这样的读重系统中。它们使我们能够充分利用硬件优化，减少内存开销，提高缓存性能。

在Qdrant中，完美哈希和碎片整理等技术的结合带来了更多好处，使我们的向量搜索操作更快、更高效。虽然有一些权衡，但Qdrant架构的灵活性——包括基于段的存储——使我们能够在两者之间取得最佳平衡。