Skip to content

Latest commit

 

History

History
363 lines (230 loc) · 17.1 KB

README.md

File metadata and controls

363 lines (230 loc) · 17.1 KB
Raw

Descartes（笛卡尔向量数据库）

重要说明

  • 笛卡尔（Descartes）是零一万物（01.AI）基于 RAG 的初步尝试。为了让各界关注 Descartes 的朋友尽早体验它的能力，零一万物即日起开放搜索内核 Binary 给大家使用，并提供免费商用。如需申请免费商用授权，请填写表单。

  • 开放搜索内核 Binary 和发布现有 README 是第一阶段工作，近期会按序发布更多相关工具和技术内容，敬请期待。同时，零一万物会持续专注研发和分享，为开发者带来更好的技术和体验。

  • Descartes 将用在近期即将正式亮相的 AI 产品中，未来也会基于需求情况，以友好地方式提供体验服务。

[ 返回顶部 ⬆️ ]

项目简介

Descartes 是零一万物自研的向量数据库，其搜索内核通过全导航图、自适应邻居选择、两级量化等技术，既能保证超高精度（大于 99%），又能实现超高性能（千万数据量毫秒级响应）。

优势

  • 超高精度：基于多层缩略图和坐标系实现层间导航和图上方位导航，以及图连通性保障，实现精度大于 99%。相同性能下，精度大幅领先业内水平。

  • 超高性能：高效的边选择和裁剪技术，千万数据量毫秒级响应。

功能

  • 支持原始图和量化图。

  • 支持流式构建，纯内存模式。后续将根据使用需求，可能考虑开放全量构建。

  • 支持单精度浮点数。近期会开放支持更多数据类型（例如，双精度浮点数、int16 和 int8 向量类型）。

  • 支持欧式和 Angular。近期会开放支持更多度量（例如，点积和汉明距离）。

[ 返回顶部 ⬆️ ]

快速上手

系统要求

  • Linux：Ubuntu 22.04 或更高版本

  • gcc: 11.4.0

  • cpuinfo flags：avx512f、fma 和 avx512bw

索引配置

注意

  • 由于涉及性能调优的参数较多，本次暂时开放部分参数。后续将根据使用需求，考虑开放更多参数或支持自动调参。

  • 如果不太熟悉参数配置，性能表现可能无法达到最优。如需获取快速技术支持，欢迎联系 [email protected]。

# vector type: float
vector.global.vector_type = float

# dimension of vector:must less than maximum value of uint16_t
vector.global.dimension = 128

# metric type: l2, square_l2, ip
vector.global.metric_type = square_l2

# maximum document count
vector.global.max_doc_cnt = 1000000

# index directory
vector.global.index_dir = /home/ubuntu/indexes

# build result count:optional, default is 400
vector.fng.build.build_res_cnt = 500

# maximum neighbor count:optional, default is 64, can't bigger than 255
vector.fng.build.max_neighbor_cnt = 32

# search result count:optional, default is 400
vector.fng.search.search_res_cnt = 40

vector.pqg.pq.subquantizer_cnt = 128

接口说明

class GraphIndex {
public:
    GraphIndex() = default;
    virtual ~GraphIndex() = default;

public:
    // index init from config file
    virtual int Init(const std::string &configFilePath) = 0;
    
    // add vector to index
    virtual int AddVector(const void *vector, size_t bytes, uint64_t key) = 0;
    
    // search vector in index with context
    virtual int Search(const void *vector, size_t bytes, SearchContext &context) = 0;
    
    // refine the index. Will quantize the index if  quantize is true
    virtual int RefineIndex(bool quantize) = 0;
    
    // dump index
    virtual int Dump() = 0;
    
    virtual uint32_t GetCurrentDocCnt() const = 0;
};

// create index
std::shared_ptr<GraphIndex> CreateGraphIndex();

使用示例

#include <vector>
#include <string>
#include <assert.h>

#include "descartes_index.h"

using namespace descartes;

int main()
{
    auto index = CreateGraphIndex();
    std::string file("./cfg");
    assert(index->Init(file) == 0);
    int dims = 128;
    int cnt = 100000;
    std::vector<float> vecs(dims * cnt);
    for (size_t i = 0; i < vecs.size(); ++i) {
        vecs[i] = i;
    }


    for (int i = 0; i <cnt; ++i) {
        int ret = index->AddVector(vecs.data() + i * dims, sizeof(float) * dims, i);
        assert(ret == 0);
    }
    assert(index->RefineIndex(false) == 0);

    SearchContext ctx;
    ctx.topk = 10;
    ctx.searchResCnt = 20;
    for (size_t i = 0; i < 100; ++i) {
        int ret = index->Search(vecs.data() + i * dims, sizeof(float) * dims, ctx);
        assert(ret == 0);         
    }
    assert(index->Dump() == 0);
}

[ 返回顶部 ⬆️ ]

性能评测

  • 当前，ANN-Benchmarks 是全球范围内最权威和常用的向量检索技术性能评测榜单之一。

  • 本次测试零一万物严格还原 ANN-Benchmarks 官方测试条件，包括使用了相同的硬件（AWS 的 r6i.16xlarge）及参数（并发为 31 且禁用了超线程 ），在离线状态下完成。如需还原 ANN-Benchmarks 测试，参阅还原步骤。

  • 本次测试时间为 2024 年 3 月 1 日。

召回与 QPS 结果对比

从 ANN-Benchmarks 测试结果可以看出，Descartes 登顶 6 份数据集评测第一名，比之前榜单上同业第一名有显著性能提升，部分数据集上的性能提升甚至超过 2 倍以上。

本次测试 6 份评测数据集涵盖 6 大数据集：glove-25-angular、glove-100-angular、sift-128-euclidean、nytimes-256-angular、fashion-mnist-784-euclidean、gist-960-euclidean。

其中，横坐标代表召回，纵坐标代表 QPS（每秒内处理的请求数）。曲线位置越偏右上角意味着算法性能越好。可以看出，Descartes 在 6 项数据集评测中都处于最高位。

  • glove-25-angular 数据集

  • glove-100-angular 数据集

  • sift-128-euclidean 数据集

  • nytimes-256-angular 数据集

  • fashion-mnist-784-euclidean 数据集

  • gist-960-euclidean 数据集

QPS 结果对比

  • QPS 是衡量信息检索系统（例如，搜索引擎或数据库）查询处理能力的重要指标。

  • 在原榜单 TOP1 基础上，Descartes 搜索内核实现了显著性能提升，部分数据集上的性能提升超过 2 倍以上，在 gist-960-euclidean 数据集维度更大幅领先榜单原 TOP1 286%。

  • 下图是 90% 召回时 QPS 对比。

[ 返回顶部 ⬆️ ]

技术特性

Descartes 搜索内核在处理复杂查询、提高检索效率以及优化数据存储方面相比业界拥有显著的比较优势。

RAG 向量检索主要解决的问题 Descartes 技术特性 业界现状
减少检索考察的候选集
（通过建立某种索引结构）		 全导航图

自研图上坐标系导航，既能保证超高精度（大于 99%），又能实现超高性能（千万数据量下毫秒级响应）。		 通过哈希、KD-Tree、VP-Tree 或随机等方式，导航效果不够精确，裁剪力度不够。
（同上） 自适应邻居选择

首创自适应邻居选择策略，较大提升了 RAG 向量检索性能。		 没有或者简单的边选择，容易陷入局部最优，潜力挖掘不充分。
降低单个向量计算的复杂度 两级量化

相比于传统 PQ 查表，性能大幅提升 2-3 倍。		 简单 PQ 量化，在量化本身，以及索引存储上没有特别处理，无法更进一步发挥硬件能力。

全导航图

向量数据库中最核心的技术是「向量检索技术」。随着向量检索技术的不断发展，实践已经证明「基于图的最近邻算法」在检索的精度和性能上脱颖而出，成为了向量检索的主流技术。

因此，零一万物自研了「全导航图」，其本质也是图算法的一种。全局多层缩略图导航技术，图上坐标系导航，既能保证超高精度，又能实现超高性能。

如上图所示，「全导航图」由 2 层次导航组成：

  • 第 1 层次导航：与 HNSW 一样，类似传统的跳表思想，通过逐层缩略全局图来实现导航效果。

  • 第 2 层次导航：体现在每一层图上，通过以每个节点为坐标原点，其邻居通过坐标系来分组存储，考虑不同的数据分布情况，根据配置可以有不同的分组方式。例如：

    • Layer 2：检索时从 Layer 2 的红色点作为入口点开始检索，查询向量 q 参照红色节点建立的坐标系可以快速定位需要考察的邻居组，从而过滤掉大量不必要的计算。

    • Layer 1：在当前层没有更近的节点时，检索进入下一层（Layer 1）继续遍历。

    • Layer 0：在进入到 Layer 0 后，检索逻辑和上层图稍有不同。上层图的目标是找好 Layer 0 上的入口点，加速检索的收敛，而在 Layer 0 的目标是找到真实的最近邻。考虑到一些特殊情况（例如，和你不在一个组内的节点也可能是你最终的最近邻），因此需要做一些额外处理。所以，先在全局最近的节点周边探测，往外扩后可以继续参考坐标系来定位需要计算的邻居组。

自适应邻居选择

零一万物自研的「自适应邻居选择策略」，突破了以往全依赖真实 topk 或固定边选择策略的局限，使每个节点可以根据自身及邻居的分布特征，动态地选取最佳邻居边，更快收敛接近目标向量。

  • 通常图构建好以后，我们用一个节点其邻居边与这个节点真实的 topk 的重合度来描述图的质量。

  • 但实践表明，如果我们以真实 topk 作为邻居边，不仅构建的时间代价巨大，而且检索效果也不是很理想，反而 RNG 类算法具有更好的检索性能，这是因为他们普遍加入了「邻居边选择策略」。

  • 目前主流的「邻居边选择策略」有两类：基于「边长短」来决定边保留（例如，HNSW、NSG、NGT 等）或根据「角度」来决定是否保留边（例如，NSSG）。

  • 从本质上讲，这两种方法都是让图的延展性更好，从而获得更佳的检索性能，但他们普遍的一个问题是没有考虑每个节点及其邻居的分布，一刀切地采用相同策略。

  • 在实践中，向量空间必然存在各种不同的空间分布。例如，有的密集分布在一起，这时需要加大边间隔选择；有的偏向明显，这时不能只选择某个集中方向的邻居边。

  • 因此，零一万物自研「自适应邻居边选择」策略，让每个节点能够根据自身和邻居的相对分布，来决策应该选择哪些邻居作为最终的邻居边，既能保证足够延展性，避免陷入局部最优；又能根据边强度裁剪多余边，避免向量被反复探测。

[ 返回顶部 ⬆️ ]

连通性保障

  • 通常而言，在较大向量数据集上，构建好的图难免会有孤立的节点。例如，整个向量空间被切分为了很多互相不联通的子图，甚至很多节点根本没有入边，成为真正的孤点。

  • 如果不对图做任何处理，相互割裂的子图，必然导致检索性能很差，检索精度也无法保障。

  • 因此，零一万物开发了图的连通性保障策略，从全局入口点开始，遍历所有节点。当发现有孤立点时，会从图上建立一条边到孤立点，同时保障被替换的点的入度必须满足一定的阈值，否则容易导致按下葫芦浮起瓢，最终无法实现连通性保障。

冗余邻居消除

  • 在连通性保障措施后，图相对就比较完整了，但还存在一个问题：里面存在较多的冗余信息，即对一个节点而言，「它的邻居边」和「它邻居的邻居边」有大量重合。

  • 在检索的过程中，如果检索路径遍历这个节点和它的一个邻居节点，由于这两个节点的邻居边存在较大重复，因此，最终遍历两个节点考察的向量数其实没有太多扩展。此时，为了更高的召回，需要考察更多的节点，会导致性能恶化。

  • 为了消除冗余邻居，零一万物根据邻居边相对于当前节点的强度，来裁剪冗余边。例如，假设有 V1、V2 和 V3 三个节点，通过 V1 的邻居表能遍历到 V2。

    • 如果 V3 同时是 V1 和 V2 的邻居，那么没有必要让 V1 和 V2 都保留作为 V3 的邻居。

    • 如果 V3 离 V2 更近，由于通过 V2 可以遍历到 V3，那么在 V1 邻居表中，可以直接裁剪 V3，而裁掉的 V3 空缺可以填入更有用的邻居边。这样既不会破坏连通性，也能降低 V1 和 V2 的信息冗余度。

索引结构优化

  • 传统图方法在索引结构上都没有特意布局，大多算法只是简单利用 prefetch 指令来提升性能。

  • 为了充分利用硬件特性，零一万物根据检索过程的 workload，按照访问的顺序排列索引结构，尽可能让缓存命中率提升，让消耗的内存带宽都能物尽其用。各种数据结构的大小都贴近 2 的指数幂大小，从而让乘法操作转化为移位操作。

  • 内存尽可能按缓存行大小对齐，防止跨越缓存行导致多余的访问。

  • 多层图的全局入口点使用全局向量空间的质心，减少随机选择可能造成的过度偏离，避免增加无谓的计算量。以入口点为基础重新排列向量布局，使得经常访问的向量能够在缓存中命中，从而进一步提升缓存命中率。

两级量化

零一万物通过两层量化，将 float 类型量化到 int8，大幅减少检索过程中需要的带宽和计算量。

同时，列式存储充分利用 avx512 的单指令多数据特性，进一步发挥硬件能力。相比传统 PQ 查表，性能得到大幅提升到 2-3 倍。

索引构建优化

  • 当前，业内有 2 类常见索引构建方法：

    • 第 1 类：类似 HNSW 的传统流式构建向量索引。每次构建相当于一次查找过程，随着图中向量不断增加，索引构建会越来越慢，根本原因是每次向量的加入都是一次全新的独立过程，导致了很多重复计算。

    • 第 2 类：nn-descent 方法。通过不断地迭代，较好地共享了之前的计算结果，但在多线程的并发度上有些瑕疵，大量的上锁和内存拷贝导致效率没有充分发挥。

  • 为了加快构建速度，零一万物研发了全量迭代方法来构建索引，通过标记邻居边状态，并充分利用好局部性原理，大幅提高了索引的并发构建效率。

[ 返回顶部 ⬆️ ]

选型考量

零一万物在研发 Descartes 搜索内核时，学习和参考了多种经典思路。

  • HNSW。在设计全导航图的第一层时，零一万物参考了 HNSW 的思路。为了更好地提升导航效果，Descartes 同时在「入口点选择节点图层的投影」和「邻居边选择」采用了不同的策略，并增加了连通性保障、冗余邻居消除等方法，大幅提高了检索效果。

  • NGT。在早期研究阶段，零一万物参考过 NGT 的思路，但在实际测试过程中，但发现它有不少问题。例如，由于它是树 + 图的组合方式，邻居表可能无限膨胀，这会造成建索引时对内存需求过大、且构建十分耗时，导致 gist-960-euclidean 数据集无法在 ANN-Benchmarks 运行环境上稳定地建出索引。

  • ScaNN。Google 推出 ScaNN 时，它的关键词是一种新的量化方式（各项特异量化），擅长解决 MIPS 问题。考虑到工程实现的有效性，零一万物选择了更高效的两级量化方式。

[ 返回顶部 ⬆️ ]

更多资源

[ 返回顶部 ⬆️ ]