論文解説: DiskANN — スケーラブルで高速なフィルタ付き近似最近傍探索

論文概要（Abstract）

DiskANNは、Microsoftが開発したSSDベースの近似最近傍探索（ANN）システムです。本論文は、DiskANNの最新拡張として「Scalable（10億件規模対応）」「Fast（SSD最適化）」「Fresh（リアルタイム更新）」「Filtered（メタデータフィルタリング）」の4つの特性を単一システムで提供する設計を解説しています。HNSWがメモリにグラフ全体を保持する必要があるのに対し、DiskANNはSSD上にグラフインデックスを格納し、メモリにはメタデータと近傍キャッシュのみを保持することで、メモリ使用量を1/20に削減しながら高いRecallを維持します。

この記事は Zenn記事: 2026年版ベクトルDB選定ガイド：pgvector・Qdrant・Pineconeを本番ベンチマークで比較の深掘りです。

情報源

arXiv ID: 2310.18164
URL: https://arxiv.org/abs/2310.18164
著者: Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri et al. (Microsoft Research)
発表年: 2023
分野: cs.DB, cs.DS, cs.IR

背景と動機（Background & Motivation）

RAG（Retrieval-Augmented Generation）パイプラインの実運用では、数億〜数十億件のベクトルに対するリアルタイム検索が求められます。しかし、HNSWのようなインメモリ型グラフインデックスは、10億件（768次元、float32）のデータに対して約3TBのメモリを必要とし、コスト面で現実的ではありません。

DiskANNは「SSDの大容量・低コスト」と「グラフベースANNの高精度」を両立させるアプローチで、この課題を解決します。NVMe SSD上にVamanaグラフを格納し、検索時のSSD読み取り回数を最小化する独自のレイアウト最適化により、メモリ64GB以下で10億件・QPS 1,000以上を達成しています。

主要な貢献（Key Contributions）

Vamanaグラフ: HNSWの多層構造に代わる単一層グラフ。SSDのシーケンシャルアクセスに最適化されたノード配置で、ランダムI/Oを最小化
Product Quantization (PQ) による距離近似: メモリ上にPQ圧縮されたベクトルを保持し、SSD上の原ベクトルへのアクセスを最小化する2段階検索
Fresh-DiskANN: ソフトデリートとバックグラウンドマージによる非同期更新。検索を止めずにデータの追加・削除が可能
Filtered-DiskANN: メタデータフィルタ付きANN検索。フィルタ述語ごとに小グラフ（stub）を事前構築し、高速なフィルタ付き検索を実現

技術的詳細（Technical Details）

Vamanaグラフの構築

Vamanaグラフは、各ノード（ベクトル）から最大 $R$ 個の近傍への有向エッジを持つグラフです。HNSWの多層構造とは異なり、単一層のグラフ構造を採用しています。

グラフ構築アルゴリズム:

  
def build_vamana(
    vectors: np.ndarray,  # shape: (N, D)
    R: int = 64,          # 最大次数
    L: int = 128,         # 構築時探索幅
    alpha: float = 1.2,   # プルーニングパラメータ
) -> dict[int, list[int]]:
    """Vamanaグラフの構築

    Args:
        vectors: ベクトルデータ (N, D)
        R: 最大次数（エッジ数上限）
        L: 構築時の探索幅
        alpha: RobustPruneのパラメータ

    Returns:
        隣接リスト {node_id: [neighbor_ids]}
    """
    N = len(vectors)
    graph = {i: [] for i in range(N)}

    # medoid（データセットの中心に最も近い点）をエントリポイントに設定
    medoid = find_medoid(vectors)

    # ランダム順でノードを挿入
    for i in np.random.permutation(N):
        # Greedy Search でL個の候補を探索
        candidates = greedy_search(graph, vectors, vectors[i], medoid, L)

        # RobustPrune で最大R個の近傍を選択
        neighbors = robust_prune(vectors, i, candidates, alpha, R)
        graph[i] = neighbors

        # 双方向エッジの追加（既存ノードの次数がRを超えたらプルーニング）
        for j in neighbors:
            graph[j].append(i)
            if len(graph[j]) > R:
                graph[j] = robust_prune(vectors, j, graph[j], alpha, R)

    return graph

RobustPruneアルゴリズム:

RobustPruneは、グラフの「到達可能性」を保証しつつ次数をRに制限する pruning アルゴリズムです。

\[\text{score}(p, q) = \alpha \cdot d(p, q) - d(q, r^*)\]

ここで、

$p$: 現在のノード
$q$: 候補ノード
$r^*$: 既に選択された最近傍ノード
$\alpha$: プルーニングの強度（$\alpha > 1$ で冗長なエッジを削減）
$d(\cdot, \cdot)$: 距離関数（L2またはコサイン距離）

$\alpha = 1.2$ が推奨値で、グラフの品質（Recall）とサイズ（メモリ・SSD使用量）のバランスが良いとされています。

SSDレイアウト最適化

DiskANNは、グラフのノードをSSD上で「検索パス順」に配置します。これにより、Greedy Searchの各ステップでアクセスするノードが物理的に近い位置に格納され、SSDのシーケンシャルリード性能を最大化します。

ノード格納フォーマット（1ノード = 1ページ）:

+-----------------+
| Node ID (8B)    |
| Vector (D×4B)   |  ← 768次元 × 4B = 3072B
| PQ Code (m×1B)  |  ← 圧縮ベクトル
| Neighbors (R×4B)|  ← 隣接ノードID
| Metadata        |  ← フィルタ用メタデータ
+-----------------+

2段階検索（PQ + SSD）

検索時、メモリ上のPQ圧縮ベクトルで候補を絞り込み、SSD上の原ベクトルで正確な距離を再計算します。

\[d_{PQ}(\mathbf{q}, \mathbf{x}) = \sum_{i=1}^{m} \|q^{(i)} - c_{k_i}^{(i)}\|^2\]

$\mathbf{q}$: クエリベクトル
$\mathbf{x}$: データベクトル（PQコード $[k_1, \ldots, k_m]$ で表現）
$c_{k_i}^{(i)}$: $i$ 番目のサブ量子化器の $k_i$ 番目のセントロイド
$m$: サブベクトル数（768次元 → $m = 32$ で各24次元）

検索フロー:

エントリポイントからGreedy Searchを開始
各ステップで、PQ距離で候補リストを管理（メモリ上、高速）
有望な候補に対してのみ、SSDからノードを読み取り正確な距離を計算
SSD読み取り回数を $O(\log N)$ に抑制

Filtered-DiskANN

フィルタ付きANN検索は、実務で極めて重要な機能です。例えば「category = ‘tech’ のベクトルのみから上位10件」のような検索です。

Stub Graph アプローチ:

各フィルタ値（例: category = ‘tech’）に対して、そのフィルタに該当するノードのみで構成されるサブグラフ（stub）のエントリポイントを事前計算します。

\[G_f = \{v \in V : \text{filter}(v) = f\}\]

検索時、フィルタ条件 $f$ に対応するエントリポイントからGreedy Searchを開始し、フィルタ条件を満たすノードのみを探索します。

フィルタ比率とRecallの関係:

フィルタ比率	Recall@10 (標準ANN)	Recall@10 (Filtered-DiskANN)
100% (フィルタなし)	0.95	0.95
10%	0.72	0.93
1%	0.45	0.88
0.1%	0.12	0.82

フィルタ比率が小さくなるほど、標準ANNのRecallが劇的に低下するのに対し、Filtered-DiskANNは安定した性能を維持します。

実装のポイント（Implementation）

DiskANNライブラリの使用

  
# pip install diskannpy
import diskannpy
import numpy as np

# データ準備（100万件、768次元）
vectors = np.random.randn(1_000_000, 768).astype(np.float32)

# インデックス構築
diskannpy.build_disk_index(
    data=vectors,
    metric="cosine",
    index_directory="./diskann_index",
    graph_degree=64,       # R: 最大次数
    search_list_size=128,  # L: 構築時探索幅
    max_occlusion_size=750,
    pq_disk_bytes=96,      # PQ圧縮後のバイト数
)

# 検索
index = diskannpy.StaticDiskIndex(
    index_directory="./diskann_index",
    num_threads=16,
    num_nodes_to_cache=100_000,  # メモリキャッシュするノード数
)

query = np.random.randn(768).astype(np.float32)
ids, distances = index.search(query, k_neighbors=10, complexity=128)

ハイパーパラメータの推奨値

パラメータ	小規模(~1M)	中規模(~100M)	大規模(~1B)
graph_degree (R)	32	64	96
search_list_size (L)	64	128	200
pq_disk_bytes	48	96	128
num_nodes_to_cache	50K	500K	5M
SSD要件	SATA SSD可	NVMe推奨	NVMe必須

よくある落とし穴

HDD環境での使用: DiskANNはSSDのランダムリード性能に依存。HDDでは10-100倍遅くなる
PQバイト数の過剰削減: pq_disk_bytes を小さくしすぎるとRecallが劇的に低下。768次元なら最低48バイト
キャッシュサイズの不足: 頻繁にアクセスされるハブノードをキャッシュしないとSSD I/Oが増大
フィルタ述語の数が多すぎる: 各フィルタ値にstubを作成するため、カーディナリティが高い列はメモリ消費が増大

Production Deployment Guide

AWS実装パターン（コスト最適化重視）

トラフィック量別の推奨構成:

規模	月間リクエスト	推奨構成	月額コスト	主要サービス
Small	~3,000 (100/日)	Serverless	$100-250	Lambda + EC2 (DiskANN) + S3
Medium	~30,000 (1,000/日)	Hybrid	$500-1,200	ECS Fargate + EC2 i3en (NVMe)
Large	300,000+ (10,000/日)	Container	$3,000-8,000	EKS + i3en.xlarge × 3 (NVMe cluster)

DiskANN特有の要件: NVMe SSDが必須。i3enインスタンスファミリー（ローカルNVMe SSD付き）が推奨。

Small構成の詳細（月額$100-250）:

EC2 i3en.large: 2 vCPU, 16GB RAM, 1.25TB NVMe SSD ($120/月)
Lambda: API Gateway + 検索エンドポイント ($20/月)
S3: インデックスバックアップ ($5/月)
CloudWatch: 監視 ($5/月)

Large構成の詳細（月額$3,000-8,000）:

EKS: コントロールプレーン ($72/月)
EC2 i3en.xlarge × 3: 4 vCPU, 32GB RAM, 2.5TB NVMe各 ($1,100/月)
ALB: ロードバランサ ($20/月)
S3: インデックスストレージ ($50/月)
CloudWatch + X-Ray: 監視 ($100/月)

コスト削減テクニック:

i3enインスタンスのReserved Instances (1年)で40%割引
DiskANNのPQ圧縮でSSD使用量を削減
S3にインデックスバックアップ、起動時にダウンロード（EBSより安価）
ノード間でデータをシャーディングし、各ノードのSSD使用量を均等化

コスト試算の注意事項:

上記は2026年2月時点のAWS ap-northeast-1（東京）リージョン料金に基づく概算値です
i3enインスタンスはローカルSSD付きのため、EBS費用は不要
最新料金は AWS料金計算ツールで確認してください

Terraformインフラコード

  
# --- EC2 i3en (DiskANN専用) ---
resource "aws_instance" "diskann" {
  ami           = data.aws_ami.ubuntu.id
  instance_type = "i3en.large"  # NVMe SSD付き
  subnet_id     = module.vpc.private_subnets[0]

  # NVMe SSDはインスタンスストア（自動マウント）
  # ephemeral_block_device は i3en では自動認識

  user_data = <<-EOF
    #!/bin/bash
    # NVMe SSDのフォーマットとマウント
    mkfs.xfs /dev/nvme1n1
    mkdir -p /data/diskann
    mount /dev/nvme1n1 /data/diskann
    echo '/dev/nvme1n1 /data/diskann xfs defaults,noatime 0 0' >> /etc/fstab

    # DiskANNのインストール
    pip install diskannpy
  EOF

  tags = {
    Name = "diskann-server"
    Env  = "production"
  }
}

# --- CloudWatch カスタムメトリクス ---
resource "aws_cloudwatch_metric_alarm" "diskann_latency" {
  alarm_name          = "diskann-search-latency-p99"
  comparison_operator = "GreaterThanThreshold"
  evaluation_periods  = 2
  metric_name         = "SearchLatencyP99"
  namespace           = "DiskANN"
  period              = 300
  statistic           = "Maximum"
  threshold           = 50  # 50ms
  alarm_description   = "DiskANN検索p99レイテンシ50ms超過"
}

# --- S3 インデックスバックアップ ---
resource "aws_s3_bucket" "diskann_backup" {
  bucket = "diskann-index-backup"
}

resource "aws_s3_bucket_lifecycle_configuration" "diskann" {
  bucket = aws_s3_bucket.diskann_backup.id

  rule {
    id     = "archive-old-indexes"
    status = "Enabled"

    transition {
      days          = 30
      storage_class = "GLACIER"
    }
  }
}

運用・監視設定

  
import boto3

cloudwatch = boto3.client('cloudwatch')

# DiskANN SSD I/O監視
cloudwatch.put_metric_alarm(
    AlarmName='diskann-ssd-iops',
    ComparisonOperator='GreaterThanThreshold',
    EvaluationPeriods=3,
    MetricName='VolumeReadOps',
    Namespace='AWS/EBS',
    Period=300,
    Statistic='Sum',
    Threshold=100000,  # 10万IOPS/5分
    AlarmDescription='DiskANN SSD I/Oが閾値超過'
)

コスト最適化チェックリスト

~100 req/日 → EC2 i3en.large ($100-250/月)
~1,000 req/日 → EC2 i3en.xlarge + レプリカ ($500-1,200/月)
10,000+ req/日 → EKS + i3en クラスタ ($3,000-8,000/月)
i3en Reserved Instances (1年コミット)で40%割引
PQ圧縮でSSD使用量を削減（768次元: 3072B → 96B）
S3にインデックスバックアップ（i3en再起動時に復元）
ノードキャッシュサイズの最適化（メモリ使用量とSSD I/Oのバランス）
graph_degree(R)を検索要件に応じて調整（32-96）
search_list_size(L)をRecall要件に応じて調整（64-200）
i3enのエフェメラルストレージは再起動で消失 → 起動時にS3からインデックス復元を自動化
CloudWatch カスタムメトリクスでSSD IOPS・レイテンシを監視
Filtered-DiskANNのstubメモリ消費を監視（フィルタカーディナリティに注意）
データパーティショニングで検索対象を限定
マルチテナント環境ではテナント別にstubグラフを構築
夜間バッチでインデックスの最適化（Compaction）を実行
Spot Instancesは使用不可（エフェメラルストレージのデータ消失リスク）
EBS io2 Block Expressも検討可能（永続性重視の場合、コスト増）
CloudWatch Anomaly Detectionで検索レイテンシ異常を自動検知
タグ戦略: env/project/teamでコスト可視化
メモリキャッシュヒット率を監視（80%以上を目標）

実験結果（Results）

BIGANN-1B（10億件、96次元）

システム	Recall@10	QPS	メモリ(GB)	SSD使用量
HNSW (hnswlib)	0.95	1,500	420	-
DiskANN	0.95	1,200	42	380 GB
メモリ削減	-	-	90%	-

MSTuring-1B（10億件、100次元）

設定	Recall@10	QPS	SSD reads/query
L=64, cache=1M	0.90	2,100	3.2
L=128, cache=5M	0.95	1,200	5.8
L=200, cache=10M	0.98	650	9.1

SSD読み取り回数（reads/query）が増えるとRecallは向上しますが、QPSは低下します。

実運用への応用（Practical Applications）

Zenn記事で紹介した「大規模フェーズ（100M+）」では、DiskANNのアプローチが非常に有効です。

HNSWとの使い分け:

メモリに余裕がある（100万件〜数千万件）: HNSW（pgvector, Qdrant）が最適。レイテンシ・QPSともに優位
メモリ制約がある（数億件〜数十億件）: DiskANN。メモリ1/10〜1/20で同等のRecallを達成
フィルタ付き検索が主要ユースケース: Filtered-DiskANNが最有力。フィルタ比率1%でもRecall 0.88を維持

pgvectorscaleとの関係: pgvectorscale（前述の記事参照）はDiskANNのアルゴリズムをPostgreSQL内に統合したものです。PostgreSQLを使い続けたい場合はpgvectorscale、最大性能を求める場合はネイティブDiskANNという使い分けが推奨されます。

まとめと今後の展望

DiskANNは「SSD × グラフインデックス × フィルタリング」の3つを統合した、大規模ベクトル検索の最有力ソリューションです。メモリ制約がある環境や10億件規模のデータセットで、HNSWに代わる実用的な選択肢を提供します。

今後の課題として、GPUアクセラレーション、マルチモーダルベクトル対応、およびクラウドネイティブな分散構成の最適化が挙げられています。MicrosoftはAzure Cosmos DB for NoSQLでDiskANNを統合しており、マネージドサービスとしての利用も進んでいます。

参考文献

arXiv: https://arxiv.org/abs/2310.18164
Code: https://github.com/microsoft/DiskANN (MIT License)
Related Zenn article: https://zenn.dev/0h_n0/articles/8c8bb192985b64

📄 論文解説: DiskANN — スケーラブルで高速なフィルタ付き近似最近傍探索

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

Vamanaグラフの構築

SSDレイアウト最適化

2段階検索（PQ + SSD）

Filtered-DiskANN

実装のポイント（Implementation）

DiskANNライブラリの使用

ハイパーパラメータの推奨値

よくある落とし穴

Production Deployment Guide

AWS実装パターン（コスト最適化重視）

Terraformインフラコード

運用・監視設定

コスト最適化チェックリスト

実験結果（Results）

BIGANN-1B（10億件、96次元）

MSTuring-1B（10億件、100次元）

実運用への応用（Practical Applications）

関連研究（Related Work）

まとめと今後の展望

参考文献

📄 論文解説: DiskANN — スケーラブルで高速なフィルタ付き近似最近傍探索

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

Vamanaグラフの構築

SSDレイアウト最適化

2段階検索（PQ + SSD）

Filtered-DiskANN

実装のポイント（Implementation）

DiskANNライブラリの使用

ハイパーパラメータの推奨値

よくある落とし穴

Production Deployment Guide

AWS実装パターン（コスト最適化重視）

Terraformインフラコード

運用・監視設定

コスト最適化チェックリスト

実験結果（Results）

BIGANN-1B（10億件、96次元）

MSTuring-1B（10億件、100次元）

実運用への応用（Practical Applications）

関連研究（Related Work）

まとめと今後の展望

参考文献

関連記事

📄 論文解説: Survey of Vector Database Management Systems

📄 論文解説: pgvectorscale — PostgreSQLをAIアプリケーション向けにスケールさせる拡張

✍️ Google Research解説: SOAR — ScaNNを加速する直交残差スピリングアルゴリズム