Meilisearch v1.14 发布啦 ✨ 在我们的博客上阅读更多内容

前往首页Meilisearch 的标志
返回文章
2024 年 4 月 4 日

Meilisearch 如何在不到一分钟内更新包含数百万向量嵌入的数据库

我们如何在向量存储中实现增量索引。

Tamo
Tamo引擎团队开发者@irevoire
How Meilisearch updates a database with millions of vector embeddings in under a minute

这是系列博客文章的第 4 部分 最初发布在 Clément Renault 的博客上。从 第 1 部分 第 2 部分 第 3 部分 开始旅程。这篇博文假设您已经阅读了第 1 部分和第 2 部分。

在这篇博文中,我们将讨论如何在 Arroy 中实现增量索引。增量意味着当在树中插入或删除项目时,我们可以仅更新所需的部分,而不是重建所有内容。

在 Meilisearch,这至关重要,因为我们的用户通常会定期发送更新,并且他们的内容不断变化。从头开始重建所有内容成本非常高,并且不会带来良好的体验;这就是为什么我们在最新版本中已经花费了大量时间来使所有 数据结构支持增量索引,而 arroy 就是其中之一,我们必须也实现它!

理论

以下模式显示了在现有树中添加和删除文档时应该发生的高级视图。

作为提醒,arroy 是一个基于 LMDB 的向量存储,LMDB 是一种嵌入式事务性内存映射键值存储。它将您的向量存储在由三种节点组成的树中

  • 拆分节点 - 存储有关哪些项目 ID 分布在其左侧和右侧之间的信息。
  • 后代节点 - 存储多个项目 ID。
  • 项目 - 单个向量。

对于以下示例,我们将考虑后代节点不能包含超过两个项目,并且 ID 越接近,项目在空间中越接近。例如,项目 1 接近项目 2,但距离项目 10 更远。

First step before inserting elements in the tree

在这里,我们尝试插入项目 27 并删除项目 311

按照我们在搜索中所做的,我们将要插入的项目拆分到左侧和右侧拆分节点之间。但是已删除的项目不再存在于数据库中!我们没有它们关联的向量,因此我们需要迭代所有叶节点以查找并删除它们。

幸运的是,由于我们使用了 Roaring 位图,因此此列表不会消耗太多内存,并且由于我们从不更新它,因此我们可以与每个线程共享它,而无需复制 🎉

Second step inserting element in the tree

请注意要插入的项目如何在左侧和右侧拆分节点之间平衡。在下一步中,我们将遵循相同的过程,并在拆分节点上拆分要插入的项目列表。

Third step inserting into elements in the tree

正是在这一步中,所有精彩的事情都发生了。从左到右

  • 第一个后代节点删除了项目 3,并添加了项目 2
  • 第二个后代节点变得太大,必须替换为新的拆分节点。
  • 项目 8 变成一个后代,包含项目 78
  • 在删除最后一个后代节点中的项目 10 后,我们将其替换为指向项目的直接链接,以减少树中节点的数量(并通过减少查找次数来缩短搜索时间)。

Last step inserting elements in the tree

既然您已经了解了我们增量索引过程的所有步骤,我们仍然要记下发生的一些事情

  • 在前三个步骤中,我们必须读取所有树节点,默认情况下,这等于数据库中项目的总数。
  • 在最后一步中,我们必须写入四个新的树节点。以前我们会重写整个树。写入次数(数据库中最慢的操作)减少到最低限度。
  • 该过程在单个树上工作,这意味着我们仍然可以多线程计算每棵树。
  • ID 不再是顺序的,这与 并行写入树 中描述的 ID 生成策略不太吻合。

我们是如何修复 ID 生成的?

在索引过程开始时,我们需要收集所有现有的树 ID。
生成新节点所需的信息是

  • 用于知道何时停止构建树的树节点总数。
  • 我们想要重新使用的已用 ID 中的“漏洞”。这种碎片是在我们编辑树时产生的。
  • 树中存在的最高 ID,用于生成下一个新 ID。

Selecting the next ID in the Roaring Bitmap

“简单”的想法是为树节点的总数设置一个计数器。我们可以递增计数器以生成新的 ID。最具挑战性的部分是选择一个线程之间共享的可用 ID,而没有大的互斥锁。

我花了一些时间才找到解决最后一点的方案;我实现了一个完整的复杂解决方案(150 行代码),但我最终在一个小时内 从头开始完全重写,以获得一个简单且更高效的解决方案。我们将看到在找到最终解决方案之前我们经历的所有想法。

共享可用 ID 的迭代器

首先也是最直接的想法是创建并共享可用 ID 的迭代器。

let mut available_ids = available_ids.into_iter();

roots.into_par_iter().for_each(|root| {
    // stuff
    let next_id = available_ids.next();
    // stuff
});

如果您熟悉 Rust,您会立即注意到 for_each 无法捕获 available_ids 上的可变引用,因为我们使用了 Rayon 的 into_par_iter 方法,该方法以多线程方式在迭代器上执行下一个方法。这意味着我们无法调用 .next()

通过使用互斥锁(互斥 的缩写),我们可以使其编译通过

let mut available_ids = Mutex::new(available_ids.into_iter());

roots.into_par_iter().for_each(|root| {
    // stuff
    let next_id = available_ids.lock().unwrap().next();
    // stuff
});

这是安全的,并且会产生正确的结果,但是由于所有线程都必须在锁上相互等待,因此无法很好地扩展。

让每个线程拥有自己的 ID 列表

当您需要删除锁时,常见的解决方案是预先拆分工作,以便每个线程都可以充分发挥其能力,而无需知道其他线程上发生了什么。这是我 最初实现的 解决方案。这个想法是将 Roaring 位图分解为与要更新的树一样多的小型 Roaring 位图。

以下函数可以将 Roaring 位图拆分为 n 个大小相等的子位图

pub fn split_ids_in(available: RoaringBitmap, n: usize) -> Vec<RoaringBitmap> {
    // Define the number of elements per sub-bitmap
    let chunk_size = available.len() / n as u64;
    let mut ret = Vec::new();

    let mut iter = available.into_iter();
    for _ in 0..(n - 1) {
        // Create a roaring bitmap of `chunk_size` elements from the iterator without consuming it
        let available: RoaringBitmap = iter.by_ref().take(chunk_size as usize).collect();
        ret.push(available);
    }
    // the last element is going to contain everything remaining
    ret.extend(iter);

    ret
}

有了这个可用的函数,然后就可以使用每个树一个位图来更新,并结合 Rayon 并行迭代器上的 zip 方法

let available_ids = split_ids_in(available_ids, roots.len());

roots.into_par_iter().zip(available_ids).for_each(|(root, available_ids)| {
    let mut available_ids = available_ids.into_iter();
    // stuff
    let next_id = available_ids.next();
    // Here, we can use the available_ids without any locks or inter-thread synchronization
    // stuff
});

当我们更新已经存在的根树时,这效果很好。但是稍后,我们可能想要从头开始创建新树,并且我们无法预先知道我们需要创建多少新树。这是一个问题,因为没有此信息,我们就不知道需要创建多少个子位图。

在这一点上,我看不到解决此问题的简单方法,但我假设我们很少创建大量新树,并且所有新树都将使用大量 ID。这意味着,将所有 ID 都提供给第一个新树可能可行(如果不进行生产监控,则很难 100% 确定)。

最终解决方案

以前的解决方案很复杂,甚至不能完美地工作。当我在浏览 Roaring 位图的文档时,我看到了 select 方法,并立即理解了如何使最初的方法可行。

此方法允许您以有效的方式按索引获取位图中的值。
例如,对于位图中的以下值:13、14、15、98、99、100

  • select(0) 返回 13
  • select(3) 返回 98
  • select(5) 返回 100
  • select(6) 返回 None

考虑到这一点,如果我们以只读方式与所有线程共享位图,并将位图中的索引作为原子数字共享,我们可以让多个线程同时获取可用 ID,而无需锁同步。

一旦 select 方法返回 None,这意味着我们可以停止从位图中选取 ID,而是使用旧方法从头开始简单地生成新 ID。
即使它超级快,调用 select 方法仍然需要一些时间,因此一旦线程从该方法获得 None 返回值,我们将更新一个原子布尔值,告知我们位图中是否还有值要查看。如果没有,我们可以跳过调用 select 并直接生成新 ID。

考虑到这一点,我们在第 2 部分中向您展示的酷炫的 ConcurrentNodeIds 结构变得稍微复杂了一些,但它仍然让我们在没有任何锁的情况下相当公平地生成 ID!

/// A concurrent ID generator that will never return the same ID twice.
pub struct ConcurrentNodeIds {
    /// The current tree node ID we should use if no other IDs are available.
    current: AtomicU32,
    /// The total number of tree node IDs used.
    used: AtomicU64,

    /// A list of IDs to exhaust before picking IDs from `current`.
    available: RoaringBitmap,
    /// The current Nth ID to select in the bitmap.
    select_in_bitmap: AtomicU32,
    /// Tells if you should look in the roaring bitmap or if all the IDs are already exhausted.
    look_into_bitmap: AtomicBool,
}

impl ConcurrentNodeIds {
    /// Creates an ID generator returning unique IDs, avoiding the specified used IDs.
    pub fn new(used: RoaringBitmap) -> ConcurrentNodeIds {
        let last_id = used.max().map_or(0, |id| id + 1);
        let used_ids = used.len();
        let available = RoaringBitmap::from_sorted_iter(0..last_id).unwrap() - used;

        ConcurrentNodeIds {
            current: AtomicU32::new(last_id),
            used: AtomicU64::new(used_ids),
            select_in_bitmap: AtomicU32::new(0),
            look_into_bitmap: AtomicBool::new(!available.is_empty()),
            available,
        }
    }

    /// Returns a new unique ID and increases the count of IDs used.
    pub fn next(&self) -> Result<u32> {
        if self.look_into_bitmap.load(Ordering::Relaxed) {
            let current = self.select_in_bitmap.fetch_add(1, Ordering::Relaxed);
            match self.available.select(current) {
                Some(id) => Ok(id),
                None => {
                    self.look_into_bitmap.store(false, Ordering::Relaxed);
                    Ok(self.current.fetch_add(1, Ordering::Relaxed))
                }
            }
        } else {
            Ok(self.current.fetch_add(1, Ordering::Relaxed))
        }
    }
}

实践中的性能

我还没有运行很多基准测试(我很想这样做,并且可能会在以后更新这篇文章),但是在我对几十万个项目的基准测试中,这是我得到的结果

Performance improvement showed on a graph

  • 平均而言,在索引了三批项目后,我们的速度提高了 10 倍以上。
  • 我们之后观察到的小幅上升,使我们从 ~700 毫秒变为 ~3 秒,是由于随着项目数量的增加而创建新树造成的。
  • 我希望这个基准测试能够代表最坏的情况
    • 我的所有项目 ID 都是随机生成的,这意味着重复/更新非常少,但始终有新的插入和更多的写入。
    • 我的向量也是使用均匀分布随机生成的,这意味着不应该像真实数据集那样存在集群。

此功能现在已在包含数百万文档的生产数据上使用,我们已经看到在不到一分钟的时间内在 200 万个项目的数据库中添加了 9000 个项目的数量级。


Meilisearch 是一款开源搜索引擎,使开发人员能够构建最先进的体验,同时享受简单直观的 DX。

有关 Meilisearch 的更多信息,您可以加入 Discord 上的社区或订阅 新闻通讯。您可以通过查看 路线图 和参与 产品讨论 来了解有关该产品的更多信息。

The 10 best AI enterprise search tools and platforms [2025]

10 大最佳人工智能企业搜索工具和平台 [2025 年]

了解当今市场上十大最佳人工智能企业搜索工具。了解它们在功能、能力、用例、定价等方面的比较情况。

Ilia Markov
Ilia Markov2025 年 4 月 15 日
Building the future of search with Meilisearch AI

使用 Meilisearch AI 构建搜索的未来

我们正在通过 Meilisearch AI 改变开发人员构建搜索的方式。不再有复杂的基础设施——只有开箱即用的强大、智能的搜索。

Quentin de Quelen
Quentin de Quelen2025 年 3 月 24 日
What are vector embeddings? A complete guide [2025]

什么是向量嵌入?完整指南 [2025 年]

了解您需要了解的有关向量嵌入的所有信息。了解它们是什么、不同类型、如何创建它们、应用等等。

Carolina Ferreira
Carolina Ferreira2025 年 3 月 20 日