Vald: 大規模・分散・高速な近似近傍密ベクトル検索エンジンの紹介（OSS）

こんにちは、ヤフーでValdの開発をしている森本です。

近年、テキストをはじめとして画像・映像・音声などのさまざまなデータの増加によって情報検索の必要性が高まっています。

これらのデータは従来の検索エンジンで効率的に検索することは容易ではありません。現在、ディープラーニングをはじめとしたAI技術は急速に発展し、テキストや画像などのデータからベクトル表現を獲得できるようになっており、これらのベクトルを用いた検索技術の需要は日に日に重要度を増しています。

本日のアドベントカレンダーでは、ベクトル検索において用いられる、近似近傍探索(ANN: Approximately Nearest Neighbor)を実現するOSSであるValdをご紹介します。

なお、この記事はMediumに投稿した以下の記事を再編して日本語に訳したものです。（外部サイト）

• Vald. A highly scalable distributed fast approximate nearest neighbor dense vector search engine.
• A New World created by similar search: Cases where Vald can be used.
• A Super Easy Way to Try Similarity Search using Vald
• Publishing a Notebook with chiVe dataset

ANNとは

はじめにANNを説明するためにkNN(k-Nearest Neighbor)を紹介します。kNNについてはすでに多くの方々によって詳細な説明がなされていますので、ここでは簡単な説明にします。

kNNは最も類似した順番にk個のベクトルを見つけるアルゴリズムです。一般的にkNNでは正確にk個の類似ベクトルを得られますが、そのトレードオフとしてデータ数やベクトルの次元数の増加に伴って計算に多くの時間がかかります。

その問題を解決する手段として考案されたのがANNです。ANNは厳密に類似したベクトルを得られない可能性を許容して高速に類似のベクトルを検索できる手法です。

ANNにはさまざまな実装が存在しますが、ValdではANNのエンジンとしてヤフーで開発し、OSSとして公開するNGTを採用しています。

NGTについて

NGTはヤフーで研究開発が行われており、”Graph And Tree”という構造を用いたアルゴリズムで高速なANNを実現しています。詳細についてはこちらをはじめとして、Yahoo! JAPAN Tech BlogにNGTに関する記事がございますので、ご覧いただければと思います。

NGTはかつてNGTDというサーバ実装があり、RESTとgRPCのAPI機能を提供していました。

NGTは非常に高性能なANNを可能にしますが、インデックスをメモリ上に展開するという性質があり、多くのメモリが必要です。そのため、使用できるインデックスのサイズはハードウェアによって制限されてしまいます。

更に別の問題もあります。複数のサーバにインデックスを保持する場合、ベクトルのInsert、Delete、Update、Commit、Searchによる複雑なワークフローをユーザが正確に制御しなければなりません。特にCommit操作はインデックスをロックするためデータ量の増加に伴ってユーザアクションをブロックする頻度が上がっていきます。

これらの事情からNGT/NGTDにはシステム上の限界があることがわかり、分散環境におけるNGTDのプロジェクトがはじまりました。しかし、単に分散するだけでは運用コストの削減は難しく、これらの問題の解決にはなりませんでした。そこで私たちは既存のシステム全体を見直して、再設計をすることで改善を図りました。

そこで開発されたのが、分散型の近似近傍ベクトル検索エンジンであるValdです。

Valdのご紹介

ValdはKubernetesと親和性が高いマイクロサービスアーキテクチャに基づく、スケーラビリティの高い分散型の高速近似近傍ベクトル検索エンジンです。

ValdはGitHub上でOSSとして開発されており、どなたでも容易に貢献していただけます。

Valdはヤフーが扱う規模のビッグデータでのANNをサポートするために、性能要件だけでなく安定性や耐障害性など多くの要件を満たすように設計・開発・検証が実施されています。

クラウドネイティブ

• Valdは容易に使えるコンテナ環境を提供しています
• 大規模データをお持ちの方は、Kubernetes上で動作するValdをHelmやHelm-operatorを用いて簡単にデプロイできますので、詳細はドキュメントをご覧ください（外部サイト）
  • Helmによるデプロイ
  • HelmでのValdのパラメータ設定
  • Helm Operator
• スタンドアロンでの利用を検討している方は最小構成でのデプロイをご利用ください（外部サイト）
  • Kubernetesでの利用
  • Dockerでの利用

スケーラビリティ

• ValdはKubernetes上での動作を前提として設計しており、Kubernetesクラスタが許す限りの拡張性を持っています
• Valdのベクトル分散格納アルゴリズムはクラスタの計算リソースの利用率に応じて適切に格納します

柔軟なカスタマイズ

• すべてのValdのコンポーネントについて多くのパラメータをYAMLと環境変数で設定可能です
• Valdはドメインに基づいてうまく分割されたアーキテクチャで構成されているので、簡単にValdのコンポーネントをカスタマイズ可能です
• Ingress FilterとEgress Filterをサポートしています
• Ingress Filterでは、入力データを容易に前処理できます。例えば、TensorFlowで入力画像を特徴ベクトルに変換できます
• Egress Filterによって検索結果の出力データを加工できます。ANNの検索結果は近似であり、精度に問題がある場合があります。Egress Filterによって、検索結果を容易に修正できます

自動インデックス

• インデックスを自動的に外部ストレージにバックアップできます
• インデックスの自動復旧機能を提供します
• ベクトルの検索をブロックせずにインデックスのCommit操作を自動で実行します
• インデックスを自動的に最適化します

多言語サポート

• Go、 Python、 Java、 Node.js、 Clojureをサポートしています
• また、protocol bufferの定義ファイル(.proto)を用意しているので、多くの言語から利用可能です

近似近傍ベクトル検索のユースケース紹介

続いて、近似近傍ベクトル検索のユースケースをご紹介します。

画像 / 映像 / 音声

おそらく最もポピュラーな対象となるデータは画像、映像、音声だと思います。多くの研究が行われており、さまざまな実用も提案されています。

認識

画像認識を例にとって説明します。既知の画像を機械学習のモデルを用いてベクトル化し、そのベクトルをValdに登録します。上と同じ機械学習のモデルを使って未知の画像をベクトル化し、Valdで検索することで未知の画像を認識できます。顔画像を用いた顔認識がイメージしやすい例だと思います。

同様に映像データからシーンを認識したり、音声データから話者を認識するような使い方も可能です。

レコメンデーション

現代のECサイトや動画配信サービスなどでレコメンデーションは欠かせない技術です。例えば商品の関連性を考慮して商品画像から学習したモデルを用いて、ECサイトのユーザが閲覧している商品に基づいた推薦を行えます。同様に動画もシーンや出演者に基づいたモデルでの推薦が考えられます。

テキスト

画像 / 映像 / 音声と同様にテキストも、多くの場面で利用されているデータです。

検出

文章には書く人の癖が現れるため、そのような癖を特徴づけるようなベクトルを構成するように学習したモデルを用いることで似た文章やプログラムといったものを検索できます。これを応用すると盗作の検出ができます。

スペルチェック

単語や熟語をベクトル化してインデックスに登録します。調べたい単語や熟語をクエリとして検索し、スペルが正しければ検索クエリのベクトルと結果のベクトルは同一ですが、そうでない場合は、最も近いベクトルが正しいスペルの単語や熟語であることが期待できます。

文法チェック

スペルチェックと同様に、文法的に正しい文章と間違っている文章を両方ともベクトル化して登録し、チェックしたい文章をクエリとして検索します。入力が正しい文章であれば結果に文法的に正しい文章が多くなり、逆であれば文法的に間違っている文章が多く含まれます。

リアルタイム翻訳

機械翻訳があると、元の文章の言語が苦手な人でも意味を理解できる助けになります。2つ以上の言語間で同じ意味を持つ単語が近くなるようにモデルを学習し、そのモデルを使ってテキストをベクトル化することで翻訳をできます。

その他

マルウェア検出

ある未知のバイナリがマルウェア化そうでないかを判定するために、既知のマルウェアのバイナリを用いて学習したモデルを用いてベクトル化したデータに対して検索を実行します。もし、未知のバイナリがマルウェアであった場合、その類似度は高くなるはずです。

社会分析

現代は技術の発展により、さまざまな行動履歴や趣味・関心事など、多種多様なソーシャルデータが蓄積されています。それらのデータをベクトル化し検索することで、関連する友人やイベントの提案、コンテンツの推薦ができるようになります。

Valdによる近傍ベクトル探索

それでは、5分でValdをk3d上にデプロイしてみましょう。

準備

Valdのデプロイをはじめる前に、以下の4つのツールをインストールします。（外部サイト）

• Helm: https://helm.sh/docs/intro/install/
• jq: https://stedolan.github.io/jq/
• k3d: https://k3d.io/
• kubectl: https://kubernetes.io/docs/tasks/tools/install-kubectl/

macでHomebrewをお使いであれば以下のコマンドでインストールできます。

$ brew install helm
$ brew install jq
$ brew install k3d
$ brew install kubectl

本チュートリアルは以下のバージョンで動作確認をしております。

$ helm version
version.BuildInfo{Version:"v3.6.3", GitCommit:"d506314abfb5d21419df8c7e7e68012379db2354", GitTreeState:"dirty", GoVersion:"go1.16.5"}

$ jq --version
jq-1.6

$ k3d version
k3d version v4.4.7
k3s version v1.21.2-k3s1 (default)

$ kubectl version
Client Version: version.Info{Major:"1", Minor:"21", GitVersion:"v1.21.5", GitCommit:"aea7bbadd2fc0cd689de94a54e5b7b758869d691", GitTreeState:"clean", BuildDate:"2021-09-15T21:10:45Z", GoVersion:"go1.16.8", Compiler:"gc", Platform:"darwin/amd64"}
Server Version: version.Info{Major:"1", Minor:"20", GitVersion:"v1.20.9+k3s1", GitCommit:"e365bc712cb7906d77b56b77d33f4b58fca46f75", GitTreeState:"clean", BuildDate:"2021-07-22T20:31:10Z", GoVersion:"go1.15.14", Compiler:"gc", Platform:"linux/amd64"}

k3dクラスタの構築

k3dクラスタを下記コマンドで構築します。このコマンドで1サーバ+3エージェントができます。

$ k3d cluster create vald --api-port 6550 -p "8080:80@loadbalancer" --agents 3 --image=docker.io/rancher/k3s:v1.20.9-k3s1

kubectl cluster-infoの結果が正しいことを確認してください。

$ kubectl config use-context k3d-vald
$ kubectl cluster-info
Kubernetes master is running at https://0.0.0.0:6550
CoreDNS is running at https://0.0.0.0:6550/api/v1/namespaces/kube-system/services/kube-dns:dns/proxy
Metrics-server is running at https://0.0.0.0:6550/api/v1/namespaces/kube-system/services/https:metrics-server:/proxy

To further debug and diagnose cluster problems, use 'kubectl cluster-info dump'.

Valdクラスタの構築

Helmを用いたValdのデプロイ方法を紹介します。後述するデモで用いるvald-demoに同梱されている設定ファイルを利用します。

$ helm repo add vald https://vald.vdaas.org/charts
$ helm install vald-cluster vald/vald --values https://raw.githubusercontent.com/vdaas/vald-demo/main/chive/sample-values.yaml

以上でValdクラスタの構築が完了しました。

chiVeを用いたデモ

本節ではchiVeを用いて類似検索を実際に行ってみます。

vald-demo（外部サイト）

上記のリポジトリにあるchiVeディレクトリにjupyter notebookが含まれおり、全体としては以下の構成になっています。

chive
  - README.md
  - sample-values.yaml: Sample YAML for deploying Vald using Helm to run notebook.
  - tutorial.ipynb    : Example of using Vald with chiVe.
  - tutorial.md       : Example of using Vald with chiVe (with output cells)

このnotebookを実行することでGet Startedに沿ったValdによる類似検索が体験できます。

使い方

上記のnotebookをDocker上のJupyter Notebookで動かします。

$ git clone https://github.com/vdaas/vald-demo
$ cd vald-demo
$ docker run --user root -it -v $(pwd):/home/jovyan/work -p 8888:8888 -e UB_UID=root -e GRANT_SUDO=yes jupyter/datascience-notebook

初回の実行では、Docker imageのダウンロードに時間がかかる場合があります。

エラーが発生しなければ、Jupyter Notebookを利用できます。

このnotebookでは、Valdの基本的な操作であるInsert、Search、Update、DeleteをchiVeを通じて体験できます。また、類似検索による単語の推定など、応用的な使い方も併せて体験できます。

以下のコード例はnotebookに記載のものとは異なりますのでご注意ください。

Insert

InsertはValdにベクトルを登録するAPIです。ここではnp.random.rand(300)で生成した300次元のベクトルを登録しています。

なお、import文は省略しています。

code:

# create gRPC channel
channel = grpc.insecure_channel("localhost:8081")
# create stub
istub = insert_pb2_grpc.InsertStub(channel)

# Insert
sample = np.random.rand(300)
ivec = payload_pb2.Object.Vector(id="test", vector=sample)
icfg = payload_pb2.Insert.Config(skip_strict_exist_check=True)
ireq = payload_pb2.Insert.Request(vector=ivec, config=icfg)

istub.Insert(ireq)

output:

name: "vald-agent-ngt-0"
uuid: "test"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"

Search

SearchはValdに登録されているベクトルに対して類似検索を行うAPIです。以下の例ではInsertと同様にランダムに生成した300次元のベクトルを使用します。Insertではベクトルを1つ登録したので、検索すると結果として1つの値が返ってきます。距離についてはランダムなベクトルの値や距離関数(l2: l2ノルム、cos: コサイン距離など)で変化する可能性があります。

また、IDが異なる別のベクトルを登録することで、Valdで複数のベクトルに対して検索できます。ぜひお試しください。

code:

# create stub
sstub = search_pb2_grpc.SearchStub(channel)

# Search
svec = np.random.rand(300)
scfg = payload_pb2.Search.Config(num=10, radius=-1.0, epsilon=0.1, timeout=3000000000)
sreq = payload_pb2.Search.Request(vector=svec, config=scfg)

sstub.Search(sreq)

output:

results {
  id: "test"
  distance: 0.22659634053707123
}

Update

UpdateはValdに登録済みのベクトルを更新するためのAPIです。ここではtestというIDのベクトルを別のランダムなベクトルで更新しています。

code:

# create stub
ustub = update_pb2_grpc.UpdateStub(channel)

# Update
sample = np.random.rand(300)
uvec = payload_pb2.Object.Vector(id="test", vector=sample)
ucfg = payload_pb2.Update.Config(skip_strict_exist_check=True)
ureq = payload_pb2.Update.Request(vector=uvec, config=ucfg)

ustub.Update(ureq)

output:

name: "vald-agent-ngt-0"
uuid: "test"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"

Remove

RemoveはValdに登録済みのベクトルを削除するためのAPIです。以下の例ではtestというIDのベクトルを削除しています。

code:

# create stub
rstub = remove_pb2_grpc.RemoveStub(channel)

# Remove
rid = payload_pb2.Object.ID(id="test")
rcfg = payload_pb2.Remove.Config(skip_strict_exist_check=True)
rreq = payload_pb2.Remove.Request(id=rid, config=rcfg)

rstub.Remove(rreq)

output:

name: "vald-agent-ngt-0"
uuid: "test"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"
ips: "127.0.0.1"

まとめ

以上で、簡単ではありますがValdの紹介しました。もし、この記事でValdやベクトル検索に興味を持たれた方はぜひValdとベクトル検索のコミュニティを盛り上げるお手伝いをしていただけると嬉しいです。（外部サイト）

• Vald on GitHub
• Vald
• Join vald on Slack
• Medium
• Twitter

（この記事に関連する採用情報「【テックラボ】研究開発エンジニア」もぜひご覧ください）