5 つのハード ベクトル検索の問題と Apache Cassandra でのそれらの解決方法

検索拡張生成 (RAG) がどのように機能するかという理由から、ベクトル検索は生成 AI ツールの重要なコンポーネントです。フレアLLM が幻覚を回避しながら、カスタマイズされた最新の情報を組み込むのに役立ちます。同時に、ベクトル検索は製品ではなく機能です。ベクトルは単独ではなくデータの残りの部分に関連するため、ベクトルをクエリする必要があり、残りのデータを同期するためのパイプラインを構築する必要はありません。これを行うには、ベクトル ストアを使用してデータを作成します。

2023 年にはベクター検索製品やプロジェクトが爆発的に増加しており、その中から選択することが真剣な取り組みとなっています。オプションを調査するときは、次の難しい問題と、それらを解決するためのさまざまなアプローチを考慮する必要があります。ここでは、これらの課題について説明し、DataStax Astra DB および Apache Cassandra のベクトル検索の実装のために DataStax がどのように課題に取り組んだかについて説明します。

コンテンツの概要

• 次元の呪い
• 問題 1: スケールアウト
• 問題 2: 効率的なガベージ コレクション
• サイドバー: クラウド アプリケーションのワークロード
• 問題 3: 同時実行性
• 問題4: ディスクの有効活用
• 問題 5: 構成可能性
• まとめ

次元の呪い

これらの困難な問題の中心には、研究者が「次元の呪い」これが実際に意味するのは、次のような 2 次元または 3 次元空間での正確なベクトル検索に機能するアルゴリズムであるということです。 KDの木、ベクトルの次元が数十、数百、あるいは数千に達するとバラバラになります。その結果、高次元ベクトルを使用した完全な類似性検索には近道はありません。対数時間の結果を取得するには、近似最近傍 (ANN) アルゴリズムを使用する必要がありますが、これには次の領域で課題が伴います。

問題 1: スケールアウト

多くのベクトル検索アルゴリズムは、単一マシンのメモリに収まるデータセット用に設計されており、これが現在でもテストされている唯一のシナリオです。アンベンチマーク。 (Ann-benchmarks では、テストが単一コアにさらに制限されています!) これは、100 万のドキュメントまたは行を含む学術的な作業には問題ないかもしれませんが、実際のワークロードを代表するとみなされるようになってから、何年も経ちました。

他のドメインと同様に、スケールアウトにはレプリケーションとパーティショニングの両方が必要であり、また、デッド レプリカの交換やネットワーク分割後のレプリカの修復などを処理するサブシステムも必要です。

これは私たちにとって簡単なことでした。スケールアウト レプリケーションは Cassandra の基本であり、それを Cassandra-5.0 の新機能 SAI (Storage-Attached Indexing – を参照) と組み合わせることで、 CEP-7それがどのように機能するかについて、そしてSAI ドキュメント使用方法については)、ベクトル検索実装により、無料で効果的に強力なスケールアウト機能が提供されました。

問題 2: 効率的なガベージ コレクション

「ガベージ コレクション」とは、インデックスから古い情報を削除すること、つまり削除された行をクリーンアップし、インデックス付きベクトル値が変更された行を処理することを意味します。これは言及する価値がないように思えるかもしれません – これはリレーショナル データベースの世界では 40 年間にわたって多かれ少なかれ解決されてきた問題です – しかし、ベクトル インデックスはユニークです。

重要な問題は、低遅延の検索と高い再現率の結果の両方を提供する、私たちが知っているすべてのアルゴリズムがグラフベースであることです。他にも多数のベクトル インデックス付けアルゴリズムが利用可能です。フェイスそれらの多くは実装されていますが、それらはすべて構築が遅すぎるか、検索が遅すぎるか、または汎用ソリューションとしては (場合によっては 3 つすべてが) 再現率が低すぎるかのいずれかです。これが、私が知っているすべての実動ベクトル データベースがグラフベースのインデックスを使用している理由です。その中で最も単純なものが HNSW です。階層型ナビゲーション可能なスモールワールド グラフは、 2016年にユーリー・マルコフらによって導入された;この紙は非常に読みやすいので、強くお勧めします。 HNSW については以下で詳しく説明します。

グラフ インデックスの課題は、行やドキュメントが変更されたときに古い (ベクトルに関連付けられた) ノードを単純に削除できないことです。これを数回以上行うと、グラフはクエリ ベクトルとより類似性の高い領域に BFS (幅優先検索) を向けるという目的を実行できなくなります。

したがって、このガベージ コレクションを実行するには、ある時点でインデックスを再構築する必要がありますが、いつ、どのように整理するのでしょうか?変更が行われたときに常にすべてを再構築すると、実行される物理書き込みが大幅に増加します。これは書き込み増幅と呼ばれます。一方、再構築しない場合は、クエリ時に古い行をフィルタリングして除外する追加の作業 (「読み取り増幅」) を実行することになります。

これは、Cassandra が長年取り組んできたもう 1 つの問題領域です。 SAI インデックスはメイン ストレージのライフサイクルに関連付けられているため、Cassandra にも参加します圧縮、ストレージ ユニットを対数的に増加させて、読み取りと書き込みの健全なバランスを提供します。

サイドバー: クラウド アプリケーションのワークロード

DataStax Astra DB は、Apache Cassandra 上に構築され、クラウド アプリケーション ワークロード用のプラットフォームを提供します。

これは、次のようなワークロードを意味します。

• 1 秒あたり数千から数百万のリクエストを同時に大量に実行し、通常はそれぞれ数行ずつ取得します。これが、たとえ資金的に余裕があったとしても、Snowflake 上で Netflix を実行できなかった理由です。Snowflake や同様の分析システムは、それぞれが数秒から数分、あるいはそれ以上実行される少数の同時リクエストのみを処理するように設計されています。

  
  

• メモリよりも大きい データセットが 1 台のマシンのメモリに収まる場合、使用するツールはほとんど問題になりません。 Sqlite、MongoDB、MySQL – それらはすべて正常に動作します。そうでない場合、事態はさらに困難になります。そして悪いニュースは、ベクトル埋め込みは通常数 KB、または一般的なデータベース ドキュメントよりも約 1 桁大きいため、比較的すぐにメモリを超えるサイズに到達してしまうことです。

  
  

• アプリケーションの中核 データがそれほど重要ではない、または実際の記録ソースから再構築できるため、データが失われても気にしないのであれば、やはり、どのツールを使用するかは関係ありません。 Cassandra や Astra DB などのデータベースは、何があってもデータの可用性と耐久性を維持できるように構築されています。

問題 3: 同時実行性

上でも言いましたが、よく知られているのは、アンベンチマーク比較により、すべてのアルゴリズムが単一のコアに制限されます。これは競争の場を平準化する一方で、過去 20 年間にわたるハードウェアの改善の主要な源を利用できる人たちを不利な立場に陥らせることにもなります。

関連する問題は、ann-benchmarks が一度に 1 種類の操作しか実行しないことです。最初にインデックスを構築し、次にインデックスをクエリします。検索に挟まれた更新の処理はオプションであり、おそらくハンディキャップになる可能性があります。更新に対処する必要がないことがわかっている場合は、人工的なベンチマークで適切に見える、単純化するための多くの仮定を立てることができます。

インデックスに対して複数の同時操作を実行できること、またはインデックスの構築後に更新できることを重視している場合は、インデックスがどのように機能するのか、どのようなトレードオフが関係しているのかを理解するために、もう少し詳しく調べる必要があります。

まず、私が知っている汎用ベクトル データベースはすべて、グラフベースのインデックスを使用しています。これは、最初のベクトルが挿入されるとすぐにグラフ インデックスのクエリを開始できるためです。他のほとんどのオプションでは、クエリを実行する前にインデックス全体を構築するか、少なくともデータの予備スキャンを実行して統計的プロパティを学習する必要があります。

ただし、グラフ インデックス カテゴリ内にも重要な実装の詳細がまだあります。たとえば、最初は、MongoDB Elastic や Solr と同じように、Lucene の HNSW インデックス実装を使用することで時間を節約できるのではないかと考えました。しかし、Lucene が提供するのはシングルスレッドの非同時インデックス構築のみであることがすぐにわかりました。つまり、構築中にクエリを実行したり (これがこのデータ構造を使用する主な理由の 1 つです!)、複数のスレッドで同時に構築することもできません。

HNSW の論文では、きめ細かいロック手法が機能する可能性があることを示唆していますが、私たちはさらに改良を加えて、ノンブロッキング インデックスを構築しました。これはオープンソース化されていますJベクトル。

JVector は、同時更新を少なくとも 32 スレッドまで線形に拡張します。このグラフは x 軸と y 軸の両方で対数スケールになっており、スレッド数が 2 倍になるとビルド時間が半分になることがわかります。

さらに重要なことは、JVector のノンブロッキング同時実行性は、検索と更新を組み合わせることで、より現実的なワークロードにメリットをもたらします。以下は、さまざまなデータセットにおける Astra DB のパフォーマンス (JVector を使用) と Pinecone の比較です。 Astra DB は、静的データセットの場合は Pinecone よりも約 10% 高速ですが、新しいデータのインデックス作成も 8 倍から 15 倍高速です。より高いスループットとより低いレイテンシに関する推奨事項に基づいて、Pinecone を使用した利用可能な最適なポッド層 (ポッド タイプ: p2、ポッド サイズ: x8、レプリカあたり 2 つのポッド) を選択しました。 Pinecone は、これがどのような物理リソースに対応するかを明らかにしていません。 Astra DB 側では、デフォルトの PAYG デプロイメント モデルを選択しましたが、サーバーレスであるため、リソースの選択について心配する必要はありませんでした。テストは以下を使用して実行されました。 NoSQLベンチ。

Astra DB は、より高い再現率と精度を維持しながらこれを実行します ( F1 は再現率と精度の組み合わせです) :

問題4: ディスクの有効活用

から始めました。 HNSW グラフのインデックス作成アルゴリズムなぜなら、インデックスの構築、クエリの実行が速く、精度が高く、実装が簡単だからです。ただし、多くのメモリを必要とするというよく知られた欠点があります。

HNSW インデックスは一連のレイヤーであり、ベース レイヤーより上の各レイヤーのノード数は前のレイヤーの約 10% です。これにより、上位層がスキップ リストとして機能し、すべてのベクトルを含む下位層の右近傍を検索できるようになります。

ただし、この設計は、(すべてのグラフ インデックスに共通して) 「ディスク キャッシュが私たちを救ってくれる」と言い逃れることはできないことを意味します。これは、通常のデータベース クエリ ワークロードとは異なり、グラフ内のすべてのベクトルがほぼ等しい確率で、検索に関連していること。 (例外は上位層であり、キャッシュすることができます。)

Lucene を使用していた頃、64 GB の RAM を搭載した私のデスクトップ上で、Wikipedia 記事チャンクの 1 億ベクトル データセット (ディスク上に約 120 GB) を提供するプロファイルは次のようになります。

Cassandra は、ディスクからベクトルを読み取るのを待つことにほぼすべての時間を費やします。

この問題を解決するために、DiskANN と呼ばれるより高度なアルゴリズムを実装し、スタンドアロンの組み込みベクトル検索エンジンとしてオープンソース化しました。 Jベクトル。 (具体的には、JVector は、「フレッシュディスクANN簡単に説明すると、DiskANN は、HNSW よりも長いエッジを持つ単一レベルのグラフと、ベクトルと近傍ベクトルの最適化されたレイアウトを使用してディスク IOPS を削減し、ベクトルの圧縮表現をメモリ内に保持して類似性の計算を高速化します。これにより、Wikipedia ワークロードのスループットが 3 倍になります。

クライアント/サーバー コンポーネントを持たない純粋な組み込みシナリオでの HNSW と DiskANN の比較を次に示します。これは、Lucene (HNSW) および JVector (DiskANN) での Deep100M データセットの検索速度を測定します。 Lucene インデックスは、インデックスと生のベクトルを含めて 55 GB です。 JVector インデックスは 64GB です。検索は私の 24GB MacBook で実行されました。この MacBook には、RAM にインデックスを保持するのに必要なメモリの約 3 分の 1 が搭載されています。

問題 5: 構成可能性

データベース システムのコンテキストにおける構成可能性とは、一貫した方法でさまざまな機能をシームレスに統合する機能を指します。これは、ベクトル検索などの新しいカテゴリの機能の統合を議論する場合に特に重要です。おもちゃ以外のアプリケーションには、常に古典的な両方が必要ですクラッドデータベース機能と新しいベクトル検索が追加されました。

シンプルなことを考えてみましょうAIチャットボットAstra DB のサンプル アプリケーション。これは、ご覧のとおり純粋な RAG アプリケーションであり、ベクトル検索を使用して適切なドキュメントを LLM に表示し、ユーザーの質問に答えます。ただし、このような単純なデモでも、会話履歴を取得するために Astra DB に対して「通常の」非ベクトル クエリを実行する必要があります。これは、LLM が既に行った内容を「記憶」できるように、LLM へのすべてのリクエストにも含める必要があります。が行われました。したがって、主要なクエリには次のものが含まれます。

1. ユーザーの質問に最も関連するドキュメント (またはドキュメントの断片) を見つけます。
2. ユーザーの会話から最後の 20 件のメッセージを取得します

より現実的な使用例では、当社のソリューション エンジニアの 1 人が最近、製品カタログにセマンティック検索を追加したいと考えているアジアの企業と協力していましたが、用語ベースのマッチングも可能にしたいと考えていました。たとえば、ユーザーが [「赤」ボール バルブ] を検索する場合、ベクトル埋め込みが意味的にどれほど類似していても、説明が「赤」という用語に一致する項目に検索を制限したいと考えます。したがって、重要な新しいクエリは (セッション管理、注文履歴、ショッピング カートの更新などの従来の機能に加えて)、次のようになります。引用された用語をすべて含む製品に製品を制限し、ユーザーの検索に最も類似したものを見つけます。

この 2 番目の例は、アプリケーションが従来のクエリ機能とベクトル検索の両方を必要とするだけでなく、多くの場合、同じクエリ内でそれぞれの要素を使用できる必要があることを明らかにしています。

この若い分野における現在の最先端技術は、私がクラシック クエリと呼んでいるものを「通常の」データベースで実行し、ベクトル クエリをベクトル データベースで実行し、両方が有効な場合にその 2 つをアドホックにつなぎ合わせることです。同時に必要となります。これはエラーが発生しやすく、時間がかかり、コストがかかります。唯一の利点は、より良い解決策が見つかるまで実行できることです。

Astra DB では、Cassandra SAI 上に、より優れたソリューションを構築 (そしてオープンソース化) しました。 SAI では、Cassandra の安定版と圧縮のライフ サイクルにすべて関連付けられたカスタム インデックス タイプを作成できるため、開発者は Astra DB で簡単にブール述語、用語ベースの検索、およびベクトル検索をオーバーヘッドなしで組み合わせることができます。個別のシステムの管理と同期。これにより、生成 AI アプリケーションを構築する開発者は、より高度なクエリ機能を利用できるようになり、生産性が向上し、市場投入までの時間が短縮されます。

まとめ

ベクトル検索エンジンは、スケールアウト、ガベージ コレクション、同時実行性、ディスクの効果的な使用、構成可能性など、複数のアーキテクチャ上の課題を伴う重要な新しいデータベース機能です。 Astra DB のベクトル検索を構築する際に、Cassandra の機能を活用して、生成 AI アプリケーションの開発者にクラス最高のエクスペリエンスを提供することができたと信じています。 Astra DB の詳細については、こちらをご覧ください。または、ベクトル検索アルゴリズムを詳しく知りたい場合は、以下をチェックしてください。 Jベクトル。

- Jonathan Ellis 著、DataStax