⚠️ Alpha内测版本警告:此为早期内部构建版本,尚不完整且可能存在错误,欢迎大家提Issue反馈问题或建议。
Skip to content

DiskANN 系统 ​

1. 为什么需要 DiskANN ​

前面的 HNSW 和 Vamana 章节关注的是“怎样沿图找到候选”,没有讨论这些数据具体放在哪里。当数据规模继续增大时,图和原始向量可能无法全部放进内存,只能把体积较大的部分放到 SSD(固态硬盘)中。

SSD 的容量通常比内存大,但随机读取更慢。如果每展开一个节点都要单独等待一次 SSD 读取,查询延迟就会被一轮轮等待拉长。DiskANN 的做法说白了就是三招:能放内存的尽量放内存,内存快;必须放硬盘的,攒成一批一起读,别让硬盘来回跑;读回来之前,先用压缩过的小数据把候选粗排一遍。分工上,Vamana 的图负责带路,PQ 的压缩向量负责粗排,SSD 存完整数据。

2. 数据存储分工 ​

2.1 内存里的数据 ​

内存里放这三样:

  • PQ 码本和每个向量的 PQ 压缩表示;
  • 少量节点记录的内存副本(缓存);
  • 当前查询的候选和结果。

内存中的 PQ 压缩表示体积较小,用来估算已经发现的候选离查询向量有多近。PQ 不会先扫描全库,也不负责最终结果;编码和距离计算可参考 PQ 算法教程。

缓存的规矩很简单:内存里留了副本的点,直接用内存里的,不碰 SSD;没留副本的点,才去 SSD 读。留给谁?一般是离入口几步路以内的那批点(论文取 3 到 4 跳),因为搜索刚开始的那几步几乎每条查询都要走;也可以干脆统计谁被读得最多就留谁。这个范围不能放宽太多:多放宽一跳,要留的节点就涨得飞快。

2.2 SSD 节点记录 ​

SSD 上存的是每个节点的“完整档案”。读 SSD 有个特点:一次最少读一页,哪怕你只要一个字节,也得等一整页的时间。所以 DiskANN 干脆把每个节点的两样东西——邻居名单和完整向量——钉在同一页档案里:翻一次档案,既知道下一步往哪走(邻居名单),又顺手把这个点的真实距离记下来(完整向量)。每个节点最多 R 个邻居,每份档案多厚也就定死了。查询结束时,最终结果就在这些已经读过的真实距离里挑前 k 个,不用再碰 SSD。

DiskANN 内存与 SSD 存储分工

3. 索引怎样建出来 ​

3.1 建图流程 ​

本章只讨论一次性构建的索引,不涉及在线更新。

构建做四件事:

  1. 训练 PQ。 用数据集算出码本,再给每个向量写下压缩编码。
  2. 用 Vamana 建图。 沿用上一章的单层图,每个节点最多 R 条出边。
  3. 把节点写成 SSD 记录。 每个节点一条,格式见 2.2。
  4. 复制一批节点到缓存。 缓存范围见 2.1。

3.2 建图内存限制 ​

先把两件事分开:第 2 节说的是“查询的时候数据放不进内存”,这一节说的是“建图的时候内存就不够用”。本章示例的数据不大,图在内存里就能建完。真到了内存装不下的时候,论文的做法是把数据切成几片、每片各建一张图、最后把图拼到一起;本章不实现这一步,知道有这回事就行。

4. 查询流程 ​

4.1 基本概念 ​

  • 候选:搜索已经发现、可能接近查询向量的节点;
  • 展开:读取一个候选的完整记录,并沿它的邻接表发现更多节点;
  • top-k:最终返回的结果个数。

W 是一轮最多选多少个候选。L 是候选列表最多留多少个节点。

4.2 候选展开循环 ​

查询从图的入口节点开始,并重复下面的过程:

  1. 用 PQ 近似距离排列当前已经发现的候选;
  2. 按这个顺序跳过已经展开的候选,最多选择 W 个;
  3. 命中缓存的记录直接从内存取得,其余记录在同一轮从 SSD 读取;
  4. 用邻接表发现新候选,并记下全精度距离;
  5. 合并旧候选和新候选,按 PQ 近似距离只保留前 L 个;
  6. 保留列表里还有未展开的节点,就回到第 1 步;否则从已经展开的节点中按全精度距离取前 k 个。

DiskANN 一轮图搜索如何推进

看图时记住一点:同一个字母永远是同一个节点。③对应第 5 步——按 PQ 距离只留前 L 个,这决定的是“谁能留在候选名单里”,还不是最终排名。最终结果只看已经展开过的点(C、B)的真实距离;没挤进名单的 D、E、F 这轮就出局了,不会再被展开;A 虽然还留在名单里,但它已经展开过,不会再展开第二次。

4.3 结果与近似性 ​

真实距离只在展开过的点上算过;没被展开的点只是“没轮到”,并不能证明它们更远。所以最终结果可能错过真正的最近邻,DiskANN 仍然是近似搜索。

5. 教学实现 ​

配套 Notebook:src/ANN_alorithms/DiskANN系统.ipynb。

下面的实现复用上一章的 SimpleVamana 建图。

配套 notebook 在 src/ANN_alorithms 目录下运行,才能 from vamana import SimpleVamana。

5.1 数据与 Vamana 图 ​

示例只缓存入口和邻接表里的前三个邻居。

python
import numpy as np

from vamana import SimpleVamana


def make_dataset(seed=7, n_per_cluster=10, dimension=8):
    rng = np.random.default_rng(seed)
    coords = np.linspace(-27.5, 27.5, 12)
    centers = np.stack([coords, np.zeros(12)], axis=1)
    rows = []
    for center in centers:
        xy = rng.normal(loc=center, scale=0.8, size=(n_per_cluster, 2))
        derived = np.column_stack([
            xy[:, 0] * 0.35 + xy[:, 1] * 0.20,
            xy[:, 0] * -0.15 + xy[:, 1] * 0.40,
        ])
        noise = rng.normal(scale=0.15, size=(n_per_cluster, dimension - 4))
        rows.append(np.column_stack([xy, derived, noise]))
    return np.vstack(rows).astype(np.float32)


X = make_dataset()
vamana = SimpleVamana(R=10, L_build=24, alpha=1.1, seed=7).fit(X)
graph, entry = vamana.graph, vamana.entry
cache_nodes = {entry, *graph[entry][:3]}

5.2 查询模拟器 ​

DiskANNQuerySimulator.fit 训练 PQ,用字典保存每条 SSD 记录,并把缓存节点的记录留在内存。search 按第 4 节执行。SSD 读取数是一共读了多少条记录。读取轮数只统计发生过 SSD 读取的轮,全部命中缓存的轮不计。SSD 记录放在字典里,我们通过如下的方式进行耗时模拟的对比:读了 SSD 的每一轮先算 100,这一轮读出几条记录,每条再加 10,即 io_rounds × 100 + ssd_reads × 10。

python
class DiskANNQuerySimulator:
    """模拟 DiskANN 查询:内存中用 PQ 排列候选,按需读取 SSD 上的节点记录。"""

    def __init__(self, graph, entry, pq_subspaces=4, pq_centroids=8,
                 kmeans_iters=15, cache_nodes=()):
        self.graph = graph
        self.entry = entry
        self.pq_subspaces = pq_subspaces
        self.pq_centroids = pq_centroids
        self.kmeans_iters = kmeans_iters
        self.cache_nodes = set(cache_nodes)

    def _kmeans(self, data):
        init = np.linspace(0, len(data) - 1, self.pq_centroids, dtype=int)
        centers = data[init].copy()
        for _ in range(self.kmeans_iters):
            distances = ((data[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2)
            labels = np.argmin(distances, axis=1)
            for c in range(self.pq_centroids):
                members = data[labels == c]
                if len(members):
                    centers[c] = members.mean(axis=0)
        return centers

    def fit(self, X):
        X = np.asarray(X, dtype=np.float32)
        if X.shape[1] % self.pq_subspaces != 0:
            raise ValueError("向量维度必须能被 pq_subspaces 整除")
        self.sub_dim = X.shape[1] // self.pq_subspaces

        # 内存:每个子空间一个 PQ 码本,每个向量一行 PQ 编码。
        self.codebooks, codes = [], []
        for part in range(self.pq_subspaces):
            sub = X[:, part * self.sub_dim:(part + 1) * self.sub_dim]
            codebook = self._kmeans(sub)
            self.codebooks.append(codebook)
            distances = ((sub[:, None, :] - codebook[None, :, :]) ** 2).sum(axis=2)
            codes.append(np.argmin(distances, axis=1))
        self.pq_codes = np.column_stack(codes).astype(np.uint8)

        # SSD:每个节点一条记录,同时保存全精度向量和邻接表。
        self.ssd_records = {
            node: {"vector": X[node], "neighbors": list(neighbors)}
            for node, neighbors in enumerate(self.graph)
        }
        # 缓存:少量节点记录在内存中的副本。
        self.record_cache = {node: self.ssd_records[node] for node in self.cache_nodes}
        return self

    def _pq_distances(self, table, nodes):
        codes = self.pq_codes[np.asarray(nodes, dtype=int)]
        return table[np.arange(self.pq_subspaces), codes].sum(axis=1)

    def search(self, query, k=5, W=4, L=24):
        query = np.asarray(query, dtype=np.float32)
        # PQ 距离表:查询向量每一段到对应码本中各质心的距离。
        table = np.stack([
            ((query[p * self.sub_dim:(p + 1) * self.sub_dim] - self.codebooks[p]) ** 2).sum(axis=1)
            for p in range(self.pq_subspaces)
        ])
        candidates = {self.entry: self._pq_distances(table, [self.entry])[0]}
        seen = {self.entry}
        expanded, exact = set(), {}
        stats = {"ssd_reads": 0, "io_rounds": 0, "cache_hits": 0, "rounds": []}

        while True:
            # 按 PQ 近似距离排列,跳过已展开的候选,最多选 W 个。
            selected = sorted(
                (node for node in candidates if node not in expanded),
                key=lambda node: (candidates[node], node),
            )[:W]
            if not selected:
                break
            cached = [node for node in selected if node in self.record_cache]
            from_ssd = [node for node in selected if node not in self.record_cache]
            stats["cache_hits"] += len(cached)
            stats["ssd_reads"] += len(from_ssd)
            stats["io_rounds"] += int(bool(from_ssd))

            new = []
            for node in selected:
                if node in self.record_cache:
                    record = self.record_cache[node]
                else:
                    record = self.ssd_records[node]
                expanded.add(node)
                # 用全精度向量计算距离;邻接表带来新候选。
                exact[node] = float(np.linalg.norm(query - record["vector"]))
                neighbors = record["neighbors"]
                for neighbor, distance in zip(neighbors, self._pq_distances(table, neighbors)):
                    if neighbor not in seen:
                        seen.add(neighbor)
                        new.append(neighbor)
                    candidates[neighbor] = distance

            # 新旧候选合并后,按 PQ 近似距离只保留前 L 个。
            kept = sorted(candidates, key=lambda node: (candidates[node], node))[:L]
            candidates = {node: candidates[node] for node in kept}
            stats["rounds"].append({
                "selected": selected, "cached": cached, "ssd": from_ssd,
                "new": new, "kept": kept,
            })

        # 在展开过的节点中按全精度距离取前 k 个。
        stats["expanded_nodes"] = len(expanded)
        return sorted(exact, key=lambda node: (exact[node], node))[:k], stats

5.3 查看一次查询的轨迹 ​

这一节看一条查询的第 2 轮:选中了哪些候选,哪些在缓存里,哪些要读 SSD。W 是一轮最多选多少个候选,L 是候选列表最多留下多少个节点。这一轮仍是 W=2、L=6。

python
index = DiskANNQuerySimulator(graph, entry, cache_nodes=cache_nodes).fit(X)

query_rng = np.random.default_rng(7)
query_ids = [90, 0, 110, 20]
noise = query_rng.normal(scale=0.08, size=(len(query_ids), X.shape[1]))
queries = X[query_ids] + noise.astype(np.float32)

print(f"dataset: {X.shape[0]} vectors x {X.shape[1]} dimensions")
print(f"entry: {entry}; cached nodes: {len(cache_nodes)}")

运行结果:

text
dataset: 120 vectors x 8 dimensions
entry: 50; cached nodes: 4
python
result, stats = index.search(queries[0], k=3, W=2, L=6)
round_2 = stats["rounds"][1]
print("top-3:", result)
print("round 2 selected:", round_2["selected"])
print("cache hits:", round_2["cached"])
print("SSD reads:", round_2["ssd"])
print("new candidates:", round_2["new"])
print("kept after prune:", round_2["kept"])

运行结果:

text
top-3: [90, 98, 91]
round 2 selected: [62, 64]
cache hits: [62]
SSD reads: [64]
new candidates: [66, 63, 60, 69, 61, 79, 72]
kept after prune: [63, 72, 79, 66, 62, 60]

第 2 轮选中 62 和 64,62 命中缓存,64 从 SSD 读取。kept 按 PQ 距离只保留 L=6 个候选,64 在这次裁剪中被移出。64 展开时已记录到查询的全精度距离。查询结束后只从有这项记录的节点中选取 top-3,得到 [90, 98, 91]。

5.4 调整每轮选取上限 ​

先固定 L=6,把 W 依次设为 1、2、4。对 4 条查询取平均,查看每轮选取上限变化后,recall@5、SSD 读取条数、读取轮数和模拟耗时的变化。

python
def recall_at_k(X, query, result, k):
    truth = np.argsort(np.linalg.norm(X - query, axis=1), kind="stable")[:k]
    return len(set(result) & set(truth)) / k


print(f"查询数:{len(queries)}")
print("L:6")
print(" W  recall@5  SSD读取条数  读取轮数  模拟耗时")

for W in (1, 2, 4):
    recalls = []
    reads = []
    rounds = []
    for query in queries:
        result, stats = index.search(query, k=5, W=W, L=6)
        recalls.append(recall_at_k(X, query, result, k=5))
        reads.append(stats["ssd_reads"])
        rounds.append(stats["io_rounds"])

    avg_recall = np.mean(recalls)
    ssd_reads = np.mean(reads)
    io_rounds = np.mean(rounds)
    sim = io_rounds * 100 + ssd_reads * 10
    print(f"{W:2d}  {avg_recall:.3f}      {ssd_reads:5.2f}        {io_rounds:5.2f}   {sim:7.1f}")

运行结果:

text
查询数:4
L:6
 W  recall@5  SSD读取条数  读取轮数  模拟耗时
 1  0.600      10.00        10.00    1100.0
 2  0.750      11.75         6.50     767.5
 4  0.750      19.00         6.75     865.0
Wrecall@5SSD读取条数读取轮数模拟耗时
10.60010.0010.001100.0
20.75011.756.50767.5
40.75019.006.75865.0

W=2 和 W=4 的召回都是 0.750,W=1 是 0.600。三档里模拟耗时最低的是 W=2,为 767.5;W=4 升到 865.0。

5.5 调整列表保留上限 ​

候选列表允许留下更多节点时,召回能提高多少,SSD 读取条数、读取轮数和模拟耗时又会怎样变化?这里固定 W=2,让 L 依次取 4、8、12、24,查看这 4 条查询的平均 recall@5、SSD 读取条数、读取轮数和模拟耗时。

python
print(f"查询数:{len(queries)}")
print("W:2")
print(" L  recall@5  SSD读取条数  读取轮数  模拟耗时")

for L in (4, 8, 12, 24):
    recalls = []
    reads = []
    rounds = []
    for query in queries:
        result, stats = index.search(query, k=5, W=2, L=L)
        recalls.append(recall_at_k(X, query, result, k=5))
        reads.append(stats["ssd_reads"])
        rounds.append(stats["io_rounds"])

    avg_recall = np.mean(recalls)
    ssd_reads = np.mean(reads)
    io_rounds = np.mean(rounds)
    sim = io_rounds * 100 + ssd_reads * 10
    print(f"{L:2d}  {avg_recall:.3f}      {ssd_reads:5.2f}        {io_rounds:5.2f}   {sim:7.1f}")

运行结果:

text
查询数:4
W:2
 L  recall@5  SSD读取条数  读取轮数  模拟耗时
 4  0.600      10.50         6.25     730.0
 8  0.800      13.25         7.25     857.5
12  0.850      16.25         8.75    1037.5
24  1.000      27.25        14.00    1672.5
Lrecall@5SSD读取条数读取轮数模拟耗时
40.60010.506.25730.0
80.80013.257.25857.5
120.85016.258.751037.5
241.00027.2514.001672.5

增大 L 后,召回从 0.600 提高到 1.000,SSD 读取条数和读取轮数增加。模拟耗时从 730.0 增到 1672.5。

参考资料 ​

  1. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node(NeurIPS 2019)
  2. Microsoft DiskANN 官方仓库