Meilisearch 如何在不到一分钟内更新包含数百万向量嵌入的数据库
我们如何在向量存储中实现增量索引。

这是系列博客文章的第 4 部分 最初发布在 Clément Renault 的博客上。从 第 1 部分、 第 2 部分 和 第 3 部分 开始旅程。这篇博文假设您已经阅读了第 1 部分和第 2 部分。
在这篇博文中,我们将讨论如何在 Arroy 中实现增量索引。增量意味着当在树中插入或删除项目时,我们可以仅更新所需的部分,而不是重建所有内容。
在 Meilisearch,这至关重要,因为我们的用户通常会定期发送更新,并且他们的内容不断变化。从头开始重建所有内容成本非常高,并且不会带来良好的体验;这就是为什么我们在最新版本中已经花费了大量时间来使所有 数据结构支持增量索引,而 arroy 就是其中之一,我们必须也实现它!
理论
以下模式显示了在现有树中添加和删除文档时应该发生的高级视图。
作为提醒,arroy 是一个基于 LMDB 的向量存储,LMDB 是一种嵌入式事务性内存映射键值存储。它将您的向量存储在由三种节点组成的树中
- 拆分节点 - 存储有关哪些项目 ID 分布在其左侧和右侧之间的信息。
- 后代节点 - 存储多个项目 ID。
- 项目 - 单个向量。
对于以下示例,我们将考虑后代节点不能包含超过两个项目,并且 ID 越接近,项目在空间中越接近。例如,项目 1
接近项目 2
,但距离项目 10
更远。
在这里,我们尝试插入项目 2
和 7
并删除项目 3
和 11
。
按照我们在搜索中所做的,我们将要插入的项目拆分到左侧和右侧拆分节点之间。但是已删除的项目不再存在于数据库中!我们没有它们关联的向量,因此我们需要迭代所有叶节点以查找并删除它们。
幸运的是,由于我们使用了 Roaring 位图,因此此列表不会消耗太多内存,并且由于我们从不更新它,因此我们可以与每个线程共享它,而无需复制 🎉
请注意要插入的项目如何在左侧和右侧拆分节点之间平衡。在下一步中,我们将遵循相同的过程,并在拆分节点上拆分要插入的项目列表。
正是在这一步中,所有精彩的事情都发生了。从左到右
- 第一个后代节点删除了项目
3
,并添加了项目2
。 - 第二个后代节点变得太大,必须替换为新的拆分节点。
- 项目
8
变成一个后代,包含项目7
和8
。 - 在删除最后一个后代节点中的项目
10
后,我们将其替换为指向项目的直接链接,以减少树中节点的数量(并通过减少查找次数来缩短搜索时间)。
既然您已经了解了我们增量索引过程的所有步骤,我们仍然要记下发生的一些事情
- 在前三个步骤中,我们必须读取所有树节点,默认情况下,这等于数据库中项目的总数。
- 在最后一步中,我们必须写入四个新的树节点。以前我们会重写整个树。写入次数(数据库中最慢的操作)减少到最低限度。
- 该过程在单个树上工作,这意味着我们仍然可以多线程计算每棵树。
- ID 不再是顺序的,这与 并行写入树 中描述的 ID 生成策略不太吻合。
我们是如何修复 ID 生成的?
在索引过程开始时,我们需要收集所有现有的树 ID。
生成新节点所需的信息是
- 用于知道何时停止构建树的树节点总数。
- 我们想要重新使用的已用 ID 中的“漏洞”。这种碎片是在我们编辑树时产生的。
- 树中存在的最高 ID,用于生成下一个新 ID。
“简单”的想法是为树节点的总数设置一个计数器。我们可以递增计数器以生成新的 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)) } } }
实践中的性能
我还没有运行很多基准测试(我很想这样做,并且可能会在以后更新这篇文章),但是在我对几十万个项目的基准测试中,这是我得到的结果
- 平均而言,在索引了三批项目后,我们的速度提高了 10 倍以上。
- 我们之后观察到的小幅上升,使我们从 ~700 毫秒变为 ~3 秒,是由于随着项目数量的增加而创建新树造成的。
- 我希望这个基准测试能够代表最坏的情况
- 我的所有项目 ID 都是随机生成的,这意味着重复/更新非常少,但始终有新的插入和更多的写入。
- 我的向量也是使用均匀分布随机生成的,这意味着不应该像真实数据集那样存在集群。
此功能现在已在包含数百万文档的生产数据上使用,我们已经看到在不到一分钟的时间内在 200 万个项目的数据库中添加了 9000 个项目的数量级。
Meilisearch 是一款开源搜索引擎,使开发人员能够构建最先进的体验,同时享受简单直观的 DX。
有关 Meilisearch 的更多信息,您可以加入 Discord 上的社区或订阅 新闻通讯。您可以通过查看 路线图 和参与 产品讨论 来了解有关该产品的更多信息。