返回 Qdrant 内部原理

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

Andrey Vasnetsov

·

2024年8月20日

数据结构 101

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

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

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

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

可变性

使用数据结构时最重大的挑战之一是确保可变性——在创建数据结构后更改其内容的能力，特别是快速更新操作。

考虑一个简单的例子：我们想按排序顺序遍历项目。如果不需要可变性，我们可以使用一个简单的数组并对其进行一次排序。这非常接近我们的理想场景。我们甚至可以将结构放在磁盘上——这对于数组来说微不足道。

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

为了处理这种情况，更复杂的结构，如B 树应运而生。B 树专为优化大型数据集的插入和读取操作而设计。然而，它们牺牲了数组读取的原始速度，以换取更好的插入性能。

这是一个基准测试，说明了 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 中，我们决定使用由Piotr Beling在ph crate 🦀中实现的基于指纹的最小完美哈希函数。根据我们的基准测试，使用完美哈希函数确实在哈希时间方面引入了一些开销，但它显著减少了整个操作的时间

即使哈希的绝对时间更高，但由于 PHF 保证没有冲突，整个操作的时间更短。当我们考虑磁盘读取时间（可能长达几毫秒（10^6 ns））时，差异甚至更显著。

对于ph::Function，PHF RAM 大小呈线性扩展：1万个元素为 3.46 kB，3.5亿个元素为 119MB。构建哈希函数所需的构建时间出奇地低，而且我们只需构建一次

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

碎片整理

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

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

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

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

Qdrant 可以通过载荷索引获取这些额外信息。

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

这种方法对于多租户系统尤其高效，在这种系统中，只有一小部分向量被主动用于搜索。此类部署的容量通常由热集的大小定义，而热集的大小远小于向量总数。

将相关向量分组可以优化热集的大小，避免缓存不相关的数据。以下基准数据比较了碎片整理和非碎片整理存储的 RPS（每秒请求数）

数据集大小： 200万个 768d 向量（~6Gb 原始数据），二进制量化，650Mb RAM 限制。所有基准测试都在最小 RAM 分配下进行，以展示磁盘缓存效率。

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

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

更新不可变数据结构

人们可能想知道，如果 Qdrant 中的一切都是不可变的，它是如何允许更新集合数据的。事实上，Qdrant API允许随时更改任何向量或载荷，因此从用户的角度来看，整个集合随时都是可变的。

正如所有像样的魔术表演一样，秘密令人失望地简单：并非 Qdrant 中的所有数据都是不可变的。在 Qdrant 中，存储被分为段，这些段可以是可变的或不可变的。新数据总是写入可变段，然后通过优化过程转换为不可变段。

如果我们需要更新不可变段或当前正在优化的段中的数据，我们不会原地更改数据，而是执行写时复制操作，将数据移动到可变段，并在那里更新。

原始段中的数据被标记为已删除，稍后由优化过程进行回收。

缺点及如何弥补

虽然不可变数据结构对于读密集型操作非常有用，但它们也伴随着权衡

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

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

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

结论

不可变数据结构虽然正确实现起来很棘手，但能显著提升性能，尤其对于读密集型系统（如搜索引擎）。它们使我们能够充分利用硬件优化，减少内存开销，并提高缓存性能。

在 Qdrant 中，结合完美哈希和碎片整理等技术带来了进一步的优势，使我们的向量搜索操作更快、更高效。虽然存在权衡，但 Qdrant 灵活的架构（包括基于段的存储）使我们能够兼顾两者的优点。