質問の歴史
語彙検索から意味検索への移行は、過去10年間でデータインフラストラクチャの要件を根本的に変化させました。初期の情報検索は逆インデックスとTF-IDFスコアに依存していましたが、現代のマルチモーダルAIシステムは通常1000次元を超える高次元ベクトル空間での近接検索を必要とします。このシフトは、トランスフォーマーベースのモデルの普及によって激化し、伝統的なデータベースが効率的にブルートフォーススキャンできない数十億の密なエンベディングを生成しています。課題は単純なストレージから、地理的に分散したノード間での近似最近傍グラフの維持に進化し、トランザクションソースシステムとの整合性を保つ必要があります。
問題
ベクトルデータベースはCAP定理に基づくユニークな制約に直面し、正確なk最近傍計算にはデータセットに関するグローバルな知識が必要であるため、パーティション耐性と低遅延は10億ベクトル規模では相反するものになります。高次元エンベディングは significant なメモリを消費し、float32を使用して1024次元の場合は1ベクトルあたり4KBもかかり、エッジの展開を複雑にするデータの重力の問題が発生します。さらに、「次元の呪い」により、ツリーに基づく空間インデックスは無効になり、HNSWのようなグラフベースのアルゴリズムが必要であり、これは段階的に更新するのが高価です。PostgreSQLの可変トランザクションデータと不変のベクトルインデックス間の整合性を維持することは、デュアルライティング異常を引き起こし、インデックスのクロスリージョン複製はエンベディングペイロードサイズによる帯域幅コストを悪化させます。
解決策
階層的にナビゲート可能な小世界グラフを利用したセルベースアーキテクチャは、サブ10msのクエリを可能にし、メモリフットプリントを90%削減します。地域ベクトルセルは、Apache Kafkaストリームを介してエンベディングを取り込み、Debezium CDCコネクタを使用して、真実のソースデータベースがインデックス構築オーバーヘッドから分離されることを保証します。動的シャーディングは、ローカリティ感受性ハッシングを用いてクエリを特定のパーティションにルーティングし、検索空間を数十億から数百万の候補に最小化します。最終的には整合性のあるモデルは、ベクトルのバージョニングとソフトデリートトンボストーンを使用して、ブロックなしのインデックス更新を可能にし、Raftコンセンサスがセル間でメタデータの変更を調整し、ホットクエリパスを中央集約しません。
問題の説明
グローバルなビジュアルコマースプラットフォーム「LuxeSearch」は、ファッションと家具カテゴリで4億の製品SKUを維持しており、ユーザーが写真をアップロードして同一または補完的なアイテムを見つけるための視覚的類似性検索を必要としています。レガシーのElasticsearchインフラストラクチャは、768次元のCLIPエンベディングにわたるコサイン類似度計算の計算負荷のために崩壊し、ピークトラフィック中に800msの遅延スパイクが発生しました。さらに、製品メタデータの更新は、フラッシュセール中に秒間50,000のトランザクションで発生し、同時更新が検索操作と衝突した際にインデックスが崩壊し、収益損失が1時間あたり2百万ドルを超えました。
解決策1: モノリシックグローバルクラスター
最初の提案は、us-east-1に単一のMilvusクラスターを展開し、クエリ結果セットのためのグローバルCDNエッジキャッシングを使用しました。このアプローチは、強力な整合性保証を提供し、単一のインデックス状態を維持することによって運用のオーバーヘッドを簡素化しました。しかし、APACユーザーのためのクロスリージョンの遅延は180msを超え、50ms未満のモバイルアプリの要件を満たさず、ホリデーショッピングシーズン中のダウンタイムコストが指数関数的に増加するリスクが受け入れられなくなりました。
解決策2: 夜間バッチ地域インデックス
別のアーキテクチャは、S3スナップショットからの夜間バッチジョブを介して再構築された地域FAISSインデックスを提案しました。これにより、ローカルCPU推論を通じて5ms未満のクエリ遅延が実現され、検索中のネットワーク往復が排除されました。残念ながら、24時間のデータの古さにより、「ゴースト製品」が売り切れた後の視覚検索結果に現れるという顧客の苦情が発生し、インデックス再構築に必要な6時間のメンテナンスウィンドウは99.99%の稼働率SLAに違反しました。
選択された解決策
チームは、クエリボリュームによって上位10%の製品を含むホットインデックス用のRedisを使用した自律的なベクトルセルを実装し、コールドデータ用のS3に保存されたメモリマップされたHNSWグラフでバックアップしました。Debeziumは、PostgreSQLの変更をKafkaにキャプチャし、セグメントローカルのインデックスビルダーにフィードし、アウトボックスパターンを使用して段階的にHNSWの更新を実施します。製品量子化により、768次元のfloat32ベクトルを98% recall@10の精度で96バイトのコードに圧縮します。このソリューションは、500ms以内で読み取り-書き込みセマンティクスを持つ調整可能な整合性を提供し、クエリブロッキングなしで秒間100Kのエンベディング更新を処理し、全12のグローバルリージョンで8msのp99遅延を維持します。
結果
運用開始から6ヶ月後、このアーキテクチャは99.97%の可用性を達成し、日々5000万のビジュアル検索をサポートし、インフラコストをモノリシックな提案と比較して40%削減しました。recall@10メトリックは99.2%に安定し、ビジネス要件を超え、システムは手動の介入やキャッシュスタンピードなしでブラックフライデー中の300%のトラフィックスパイクを無事に処理しました。
高次元空間においてユークリッド距離が無効になる理由と、これがインデックス選択にどのように影響するか。
100次元を超える高次元空間では、最近傍と最遠の隣人の比率が1に収束します。これは、ハイパースフィアの表面に体積が集中するため、ユークリッド距離が統計的に区別できなくなり、空間的に意味を持たなくなるためです。この現象は、検索ブランチを効果的に剪定するために意味のある距離の差異に依存するkdツリーやRツリーなどのツリーに基づく空間分割を無効にします。したがって、相対的な隣接接続を通じて近接をナビゲートする必要があるため、HNSWやFAISS IVFインデックスのようなグラフベースの手法が必要になりますが、これらは大幅に多くのメモリと複雑な段階的メンテナンス手続きを必要とします。
トランザクションデータベースとベクトルインデックスの両方を原子的に更新する必要がある場合、デュアルライティング問題をどのように扱いますか？
デュアルライティング問題は、OLTPストアとベクトルデータベース間で分散トランザクションが失敗し、検索結果が削除された項目を返したり、新しいエンベディングを見逃したりするために、部分的コミット状態が原因で発生します。サブ10msのレイテンシ要件を損なう2フェーズコミットプロトコルを実装する代わりに、アーキテクトはPostgreSQLがビジネスデータの変更と同じACIDトランザクション内でアウトボックステーブルに書き込むトランザクショナルアウトボックスパターンを採用すべきです。Debeziumはこのアウトボックスを読み取り、非同期的にKafkaに公開し、ベクトルインデックスビルダーに対して正確に1回のみ配信を保証します。ベクトルエントリには単調バージョン番号が含まれ、検索APIはOLTPメタデータストアに対して結果をフィルタリングして古いバージョンを除外し、一貫性の欠如を効果的にマスクし、クエリをブロックしません。
段階的更新中のグラフベースのANNインデックスのメモリへの影響はどのようになりますか？また、書き込み増幅をどのように緩和しますか？
HNSWや類似のグラフ構造は、エッジ挿入中にロックまたはコピーオンライトメカニズムを必要とし、1つのベクトルを追加すると、階層的ナビゲーションの特性を維持するために数百のエッジの再接続を引き起こすため、著しい書き込み増幅を引き起こします。メモリ制約のある環境では、これによりページフォルトやガーベジコレクションの圧力が生じ、作業セットがDRAM容量を超えるとクエリのレイテンシが予測不可能に低下します。緩和戦略には、ホットグラフレイヤがメモリに存在し、コールドレイヤが永続メモリまたは高速NVMe SSDに存在する階層ストレージの使用、低トラフィック期間中に非同期的にマージされるマイクロセグメントに更新をバッチ化すること、圧縮ベクトルがグラフのトポロジーを決定する量子ビジョンに基づくグラフ構築を行い、生のベクトルは最終の再ランク付け時にのみ取得される方式を採用し、メモリの消費を70%削減しつつ目標のリコールメトリックを維持します。