🚀 Zilliz Cloudを無料で試す、完全管理型のMilvus—10倍の高速パフォーマンスを体験しよう!今すぐ試す>>

milvus-logo
LFAI
  • Home
  • Blog
  • Milvusベクターデータベースの類似性検索とは?

Milvusベクターデータベースの類似性検索とは?

  • Engineering
May 10, 2022
Yudong Cai

cover image カバー画像

この記事は蔡佑東が執筆し、アンジェラ・ニーが翻訳した。

中核となるベクトル実行エンジンとして、MilvusにとってのKnowhereは、スポーツカーにとってのエンジンのようなものだ。この記事では、Knowhereとは何か、Faissとどう違うのか、Knowhereのコードはどのような構造になっているのかを紹介する。

ジャンプ

Knowhereの概念

Knowhereは狭義には、システムの上位層でサービスにアクセスするための操作インターフェースであり、システムの下位層でFaissHnswlibAnnoyのようなベクトル類似検索ライブラリにアクセスするためのものである。さらに、Knowhereはヘテロジニアス・コンピューティングも担当している。具体的には、Knowhereはインデックス構築や検索要求をどのハードウェア(CPUやGPUなど)で実行するかを制御する。これがKnowhereの名前の由来である、どこで処理を実行するかを知っているということです。将来のリリースでは、DPUやTPUを含むより多くの種類のハードウェアがサポートされる予定です。

より広い意味では、KnowhereはFaissのようなサードパーティのインデックス・ライブラリも組み込んでいます。したがって全体として、KnowhereはMilvusベクトル・データベースの中核となるベクトル計算エンジンとして認識されています。

Knowhereのコンセプトから、Knowhereはデータ計算タスクのみを処理し、シャーディング、ロードバランス、ディザスタリカバリなどのタスクはKnowhereの作業範囲外であることがわかります。

Milvus 2.0.1以降、KnowhereはMilvusプロジェクトから独立しました。

MilvusアーキテクチャにおけるKnowhere

knowhere architecture Knowhereアーキテクチャ

Milvusの計算には主にベクトル演算とスカラー演算が含まれます。KnowhereはMilvusのベクトル演算のみを扱います。上の図はMilvusにおけるKnowhereアーキテクチャを示しています。

一番下の層はシステム・ハードウェアです。サードパーティのインデックス・ライブラリはハードウェアの上にあります。そして、KnowhereはCGOを介して最上層のインデックス・ノードやクエリ・ノードとやり取りします。

本記事では、アーキテクチャ図の青枠で囲んだ、より広い意味でのKnowhereについて説明します。

KnowhereとFaissの比較

KnowhereはFaissの機能をさらに拡張するだけでなく、パフォーマンスも最適化します。具体的には、Knowhereには次のような利点があります。

1.BitsetViewのサポート

当初、milvusでは「ソフト削除」の目的でビットセットが導入されました。ソフト削除されたベクトルはまだデータベースに存在しますが、ベクトルの類似性検索やクエリの際に計算されることはありません。ビットセットの各ビットはインデックス付きベクトルに対応する。あるベクトルがビットセットで "1 "とマークされた場合、このベクトルはソフト削除され、ベクトル検索に関与しないことを意味する。

bitset パラメータは、CPU および GPU インデックスを含む、Knowhere で公開されているすべての Faiss インデックス照会 API に追加されます。

bitsetがどのようにベクトル検索の汎用性を実現しているかについては、こちらをご覧ください。

2.バイナリ・ベクトルのインデックス作成におけるより多くの類似性メトリクスのサポート

Knowhereはハミング以外にも、JaccardTanimotoSuperstructureSubstructureをサポートしています。JaccardとTanimotoは2つのサンプルセット間の類似性を測定するために使用でき、SuperstructureとSubstructureは化学構造の類似性を測定するために使用できます。

3.AVX512命令セットのサポート

Faiss自体は、AArch64SSE4.2AVX2を含む複数の命令セットをサポートしています。KnowhereはAVX512を追加することでサポートする命令セットをさらに拡張し、AVX2と比較してインデックス構築とクエリの性能を20%から30%向上させることができます。

4.SIMD 命令の自動選択

Knowhere は、さまざまな SIMD 命令(SIMD SSE、AVX、AVX2、AVX512 など)を持つ幅広い CPU プロセッサー(オンプレミ スとクラウドの両方のプラットフォーム)で動作するように設計されています。したがって、1つのソフトウェアバイナリ(すなわちMilvus)が与えられた場合、どのCPUプロセッサ上でも適切なSIMD命令を自動的に呼び出すようにするにはどうすればよいかという課題があります。FaissはSIMD命令の自動選択をサポートしておらず、ユーザーはコンパイル時にSIMDフラグ(例えば"-msse4")を手動で指定する必要があります。ただし、Knowhere は Faiss のコードベースをリファクタリングして構築されています。SIMDアクセラレーションに依存する一般的な関数(類似度計算など)はファクタアウトされます。次に、各関数について4つのバージョン(すなわち、SSE、AVX、AVX2、AVX512)が実装され、それぞれが別々のソースファイルに入れられます。その後、ソースファイルは対応する SIMD フラグで個別にコンパイルされます。したがって、Knowhere は実行時に現在の CPU フラグに基づいて最適な SIMD 命令を自動的に選択し、フッキングを使用して適切な関数ポインタをリンクします。

5.その他の性能最適化

Knowhereのパフォーマンス最適化については、Milvus: A Purpose-Built Vector Data Management Systemを参照してください。

Knowhereコードを理解する

最初のセクションで述べたように、Knowhere はベクトル検索処理のみを行います。そのため、Knowhere はエンティティのベクトルフィールドのみを処理します(現在、コレクション内のエンティティのベクトルフィールドは 1 つしかサポートされていません)。インデックス構築とベクトル類似性検索も、セグメント内のベクトルフィールドを対象とします。データモデルについての理解を深めるには、こちらのブログをご覧ください。

entity fields エンティティフィールド

インデックス

インデックスは、元のベクトルデータから独立したデータ構造の一種です。インデックスの作成には、インデックスの作成、データの学習、データの挿入、インデックスの構築という4つのステップが必要である。

AIアプリケーションの一部では、データセットのトレーニングはベクトル検索とは別のプロセスである。この種のアプリケーションでは、まずデータセットのデータが学習され、類似検索のためにMilvusのようなベクトルデータベースに挿入される。sift1Mやsift1Bのようなオープンデータセットは、トレーニングとテストのためのデータを提供する。しかし、Knowhereでは学習用データと検索用データが混在しています。つまり、Knowhereはセグメント内のすべてのデータを学習し、学習したすべてのデータを挿入してインデックスを作成します。

Knowhere のコード構造

DataObjはKnowhereのすべてのデータ構造の基本クラスです。Size() はDataObjの唯一の仮想メソッドです。Index クラスは DataObj を継承し、"size_" というフィールドを持ちます。また、Index クラスにはSerialize()Load() の 2 つの仮想メソッドがあります。Indexから派生したVecIndexクラスは、全てのベクトル・インデックスの仮想基底クラスです。VecIndex はTrain(),Query(),GetStatistics(),ClearStatistics() などのメソッドを提供します。

base clase 基底クラス

他のインデックス・タイプは上図の右側にリストされている。

  • Faissインデックスには2つのサブクラスがあります:FaissBaseIndexは浮動小数点ベクトル上のすべてのインデックス用で、FaissBaseBinaryIndexはバイナリベクトル上のすべてのインデックス用です。
  • GPUIndexはすべてのFaiss GPUインデックスの基本クラスです。
  • OffsetBaseIndex はすべての自己開発インデックスの基本クラスです。インデックスファイルにはベクトルIDのみが格納されます。その結果、128 次元ベクトル用のインデックス・ファイル・サイズを 2 桁小さくすることができます。このタイプのインデックスをベクトルの類似性検索に使用する場合は、元のベクトルも考慮することを推奨する。

IDMAP IDMAP

技術的に言えば、IDMAPはインデックスではなく、ブルートフォース検索に使用される。ベクトルがベクトル・データベースに挿入されると、データの学習とインデックスの構築は必要ない。検索は挿入されたベクトルデータに対して直接行われる。

しかし、コードの一貫性を保つために、IDMAPはVecIndexクラスとそのすべての仮想インターフェースを継承している。IDMAPの使い方は他のインデックスと同じです。

IVF IVF

IVF(転置ファイル)インデックスは最も頻繁に使用されるインデックスです。IVFクラスはVecIndexとFaissBaseIndexから派生し、さらにIVFSQとIVFPQに拡張されています。GPUIVFはGPUIndexとIVFから派生したものです。GPUIVFはGPUIndexとIVFから派生し、さらにGPUIVFSQとGPUIVFPQに拡張されます。

IVFSQHybridはGPU上で粗い量子化によって実行されるハイブリッドインデックスを独自に開発したクラスです。バケット内の検索はCPUで実行されます。GPUの計算能力を活用することで、CPUとGPU間のメモリコピーの発生を抑えることができます。IVFSQHybridはGPUIVFSQと同じ再現率を持つが、性能は向上している。

バイナリ・インデックスの基本クラス構造は比較的単純です。BinaryIDMAPとBinaryIVFはFaissBaseBinaryIndexとVecIndexから派生している。

third-party index サードパーティインデックス

現在、Faiss以外のサードパーティインデックスは、ツリーベースのインデックスAnnoyとグラフベースのインデックスHNSWの2種類のみがサポートされています。これら 2 つの一般的でよく使用されるサードパーティ・インデックスは、どちらも VecIndex から派生したものです。

Knowhere へのインデックスの追加

Knowhere に新しいインデックスを追加する場合は、まず既存のインデックスを参照します:

  • 量子化ベースのインデックスを追加するには、IVF_FLAT を参照してください。
  • グラフベースのインデックスを追加するには、HNSW を参照してください。
  • ツリーベースのインデックスを追加するには、Annoyを参照してください。

既存のインデックスを参照した後、以下の手順に従って新しいインデックスを Knowhere に追加できます。

  1. IndexEnum に新しいインデックスの名前を追加します。データ型は文字列です。
  2. ファイルConfAdapter.cpp で、新しいインデックスにデータ検証チェックを追加します。検証チェックは、主にデータ学習とクエリのパラメータを検証するためのものです。
  3. 新しいインデックス用に新しいファイルを作成します。新しいインデックスの基底クラスには、VecIndexVecIndex の必要な仮想インタフェースを含める。
  4. 新しいインデックスのインデックス構築ロジックをVecIndexFactory::CreateVecIndex() に追加する。
  5. unittest ディレクトリの下に単体テストを追加します。

ディープ・ダイブ・シリーズについて

Milvus 2.0の一般提供の正式発表に伴い、Milvusのアーキテクチャとソースコードの詳細な解釈を提供するために、このMilvus Deep Diveブログシリーズを企画しました。このブログシリーズで扱うトピックは以下の通りです:

Like the article? Spread the word

続けて読む