DataStax と OpenSearch コミュニティが、ロックフリーの並行グラフ構築によってベクトルインデックス構築のほぼ線形なスケーラビリティを実現した方法をご紹介します。
ベクトル検索は、セマンティック検索から RAG (Retrieval Augmented Generation) システムまで、現代の AI アプリケーションの基盤となっています。しかし、組織が数十億のベクトルにスケールするにつれて、インデックス構築が重大なボトルネックになります。HNSW (Hierarchical Navigable Small World) のような従来のグラフベースのベクトルインデックスはシングルスレッド構築に制限されており、開発者は高速な取り込みと最適な検索品質のどちらかを選択せざるを得ませんでした。
本日、OpenSearch 向け jVector プラグインの最新リリース が画期的な機能を導入したことをお知らせします。検索品質を維持しながら、ほぼ完璧な線形スケーラビリティを実現する 並行ロックフリーベクトルグラフ構築 です。
課題: グラフ構築がシングルスレッドだった理由
HNSW のようなグラフベースのベクトルインデックスは、ベクトル接続のナビゲート可能なネットワークを構築することで近似最近傍探索に優れています。各ノードは、最も「意味のある」接続、つまりベクトル空間の他の領域への最適なパスを提供するベクトルの、慎重に選別された近傍を維持します。
構築プロセスは以下のように動作します。
- ノードを段階的に追加 してグラフを動的に構築する
- 既存のノードを検索 して各新規追加に最適な近傍を見つける
- 双方向接続を確立 してナビゲート可能なパスを作成する
ここに根本的な課題があります。新しいノードを追加するたびに、最適な近傍を特定するために現在のグラフ状態を検索する必要があります。n 個のノードに対して、構築中に少なくとも O(n) 回の検索操作が必要であり、各検索は現在のグラフトポロジーに依存します。
並行性のパラドックス
2 つのノードを同時に追加しようとした場合に何が起こるか考えてみましょう。
Node₁ が検索を実行して候補近傍 K₁ を見つけ、Node₂ が検索を実行して候補近傍 K₂ を見つけます。
両方の追加が並行して行われるため、どちらのノードも相手の検索結果に現れません。
- Node₂ ∉ K₁ かつ Node₁ ∉ K₂
- 結果: 最適な接続の欠落
これは準最適なグラフトポロジーと検索再現率の低下につながります。これは本番のベクトル検索システムで最も避けたいことです。
解決策: スナップショットベースの調整
jVector の並行構築における画期的な点は、「スナップショットベースの調整」 と呼ばれるものにあります。これは真の並列処理を可能にしながら最適な接続性を確保するロックフリーのメカニズムです。
動作の仕組み
新しいノードを追加する際、jVector は 2 つの高速な操作を実行します。
- 進行中の挿入をキャプチャ: 現在追加中のノードのリストをクローン
- グラフ状態のスナップショット: 現在のグラフトポロジーの一貫したビューを取得
図 1: スナップショットベースの調整により、最適な接続を維持しながら並行ノード挿入が可能に
これにより、Node₁ の挿入が進行中に Node₂ が追加される場合でも、
- Node₂ の検索はグラフスナップショット と 進行中の挿入 (Node₁ を含む) の両方を参照
- これにより Node₁ と Node₂ が最適な接続を確立可能
- 最終的なグラフトポロジーは逐次構築と同じ品質を維持
ロックフリーの利点
実装の詳細に魔法があります。これらのスナップショット操作は以下を満たす必要があります。
- 超高速: ノード追加のたびに発生
- ロックフリー: 同期オーバーヘッドや競合なし
- メモリ効率: 並行操作のオーバーヘッドを最小化
調整オーバーヘッドがあると水平スケーラビリティが損なわれます。私たちのロックフリー実装は、複数スレッドにわたってほぼ完璧な線形スケーリングを実現しています。
スレッドローカルリソース管理: パフォーマンスの倍増器
効果的な並行性には、ロックの排除だけでなく、インテリジェントなリソース管理が必要です。
一時オブジェクト割り当ての排除
各スレッドは計算用の独自のスクラッチスペースを維持し、2 つの主要な利点を提供します。
- 同期ゼロ: スレッド間の調整が不要
- オブジェクト再利用: スクラッチスペースにより一時オブジェクト作成によるガベージコレクション圧力を防止
SIMD 最適化とハードウェア認識
ベクトル演算はパフォーマンスのために SIMD (Single Instruction, Multiple Data) 命令を多用します。しかし、SIMD コアはオペレーティングシステムが報告する仮想コアとは異なることがよくあります。
主な考慮事項は以下の通りです。
- SIMD レジスタ状態: より広いレジスタ (128 ビット、256 ビット、512 ビット) はコンテキストスイッチングのオーバーヘッドが高い
- ハードウェア固有のスレッドプール: 仮想コアではなく実際の SIMD コア数に合わせてスレッドをプロビジョニング
- コンテキストスイッチングの削減: スレッドローカル処理によりスレッドを計算集約型 SIMD ループ内に維持
このアプローチは通常、以下を実現します。
- 複数スレッドで 2〜4 倍のスケーリング向上
- キャッシュミスの 60〜80% 削減
- 持続的な SIMD 操作における コンテキストスイッチングオーバーヘッドの低減
- NUMA ノード間での メモリ帯域幅利用率の向上
ベンチマーク結果: 線形スケーラビリティの達成
ベンチマークは並行構築の劇的な影響を示しています。これらを検証する簡単な方法は、MacBook Pro でローカルに実行できる FormatBenchmarkConstructionWithRandomVectors JMH ベンチマークです。
- プロセッサ: Apple M3 チップ (3nm プロセス)
- CPU: 8 コア (4 パフォーマンス + 4 効率コア)
- メモリ: 18GB ユニファイドメモリ (100GB/s 帯域幅)
- SIMD: ARM Neon、128 ビットベクトルレジスタ
- キャッシュ: P コアあたり 128KB L1I + 64KB L1D、クラスタあたり 4MB L2
768 次元ベクトル、100,000 ドキュメントでのテストは顕著な改善を示しています。
構築時間の改善
| 構成 | 並行化前 | 並行化後 | 改善率 |
|---|---|---|---|
| jVector (非量子化) | 163,755 ms | 25,297 ms | 6.5 倍高速 |
| jVector (量子化) | 283,856 ms | 55,677 ms | 5.1 倍高速 |
| Lucene HNSW | 119,202 ms | 119,495 ms | 変化なし (ベースライン) |
SIMD ベクトル化を追加した場合
SIMD 最適化を追加すると、さらなるパフォーマンス向上が得られます。
| 構成 | 時間 (ms) | 総合改善率 |
|---|---|---|
| jVector (非量子化) | 20,207 | 8.1 倍高速 |
| jVector (量子化) | 33,536 | 8.5 倍高速 |
| Lucene HNSW | 80,124 | 1.5 倍高速 |
スケーラビリティ特性
AVX アーキテクチャでのより包括的なベンチマークは、ほぼ完璧な線形改善を示しています (SIMD コア = スレッドの場合)。
- シングルスレッド: ベースラインパフォーマンス
- 4 スレッド: 約 3.8 倍の改善
- 8 スレッド: 約 7.5 倍の改善
- 16 スレッド: 約 14.2 倍の改善
スケーリング効率はテストしたすべての構成で 90% 以上を維持しており、ロックフリー設計の有効性を示しています。
OpenSearch ユーザーへの実際の影響
これらの改善は本番環境での利点に直接つながります。
より高速なインデックス構築
- 数十億ベクトルのデータセット: インデックス構築時間が数日から数時間に短縮
- リアルタイム取り込み: ストリーミングベクトル更新のスループット向上
- リソース効率: バルク操作中の CPU 利用率向上
開発者体験の向上
- 短いイテレーションサイクル: ベクトル検索設定の実験が高速化
- シンプルなデプロイ: インデックス構築に必要なインフラストラクチャ要件の削減
- コスト効率の向上: 計算時間の短縮によりクラウドコストが低下
検索品質の維持
- 再現率の低下なし: 並行構築でもグラフトポロジー品質を維持
- 一貫したパフォーマンス: 検索レイテンシと精度は変わらず
- 本番環境対応: 包括的な検証を経た実戦テスト済みの実装
OpenSearch での実装
並行構築機能は jVector プラグインを通じて OpenSearch で即座に利用可能です。これらの改善を活用するには、以下の設定を使用します。
設定
{
"mappings": {
"properties": {
"vector_field": {
"type": "knn_vector",
"dimension": 768,
"method": {
"name": "disk_ann",
"engine": "jvector",
"space_type": "l2",
"parameters": {
"m": 32,
"ef_construction": 200
}
}
}
}
}
}
今後の予定: ベクトル検索の未来
並行グラフ構築は、ベクトルインデックス構築へのアプローチにおける根本的な転換を表しています。シングルスレッドのボトルネックを排除することで、新しい可能性が開かれます。
- ストリーミングベクトル更新: 高コストなオフライン再構築なしでのリアルタイムインデックス変更 (近日公開予定)
- ハイブリッド検索の最適化: より高速なインデックス構築によりさらなる実験が可能に
- エッジデプロイメント: 効率的な構築によりリソース制約のある環境でもベクトル検索が可能に
まとめ
OpenSearch における並行ベクトルグラフ構築は、単なるパフォーマンス改善にとどまりません。ベクトル検索インフラストラクチャにおける主要なスケーリング制限を取り除く根本的な進歩です。検索品質を維持しながらほぼ線形のスケーラビリティを実現することで、組織はより大規模で応答性の高いベクトル検索システムを構築できるようになります。
ロックフリーの調整、インテリジェントなリソース管理、ハードウェア認識の最適化の組み合わせにより、インデックス構築時間が桁違いに改善されます。OpenSearch コミュニティにとって、これは開発サイクルの短縮、インフラストラクチャコストの削減、そしてこれまで実現不可能だったスケールの課題に取り組む能力を意味します。
コミュニティの皆様にはこれらの改善をテストし、フィードバックを共有していただくことをお勧めします。ベクトル検索は急速に進化しており、並行構築のような貢献が OpenSearch をこの変革の最前線に維持するのに役立ちます。
ぜひお試しください: 並行構築機能を備えた jVector プラグインは現在利用可能です。インストールガイド をご確認いただき、OpenSearch コミュニティフォーラム でのディスカッションにご参加ください。
次のステップ: 私たちはすでに次世代の最適化に取り組んでおり、適応型グラフ構築や GPU アクセラレーションによるベクトル演算などが含まれます。Datastax と OpenSearch チームからの今後のアップデートにご期待ください。
参考文献
理論的基盤と関連研究に興味のある読者向けの参考資料です。
グラフベースのベクトル検索
- Malkov, Yu A., and D. A. Yashunin. "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs." IEEE TPAMI, 2018. (オリジナルの HNSW 論文)
- Subramanya, Suhas Jayaram, et al. "DiskANN: Fast accurate billion-point nearest neighbor search on a single node." NeurIPS, 2019. (Vamana アルゴリズムの基盤)
並行データ構造
- Michael, Maged M., and Michael L. Scott. "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms." PODC, 1996. (ロックフリーキューの基礎)
- Herlihy, Maurice, and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2020. (並行プログラミングの包括的リファレンス)
ベクトル量子化と圧縮
- Jégou, Hervé, Matthijs Douze, and Cordelia Schmid. "Product quantization for nearest neighbor search." IEEE TPAMI, 2011. (PQ 技術の基盤)
OpenSearch Project(OSS) の Publicationです。 OpenSearch Tokyo User Group : meetup.com/opensearch-project-tokyo/
Discussion