Vector SetsがRedisの一部になりました
昨日、ついにVector SetsをRedisにマージしました。得られるものを詳しく説明したREADMEはこちらです。
https://github.com/redis/redis/blob/unstable/modules/vector-sets/README.md
この新しいデータ構造の目標を要約すると、Sorted Setsに似た新たな「Set風」のデータ型を作ることです。ただし、スコアとしてスカラー値を持つ代わりにベクトルを持ちます。Redisらしい方法で要素を追加・削除でき、Redisが実装する抽象データ構造の性質以外は何も気にせずに済みます。指定したクエリベクトルに似た要素（あるいは、すでにセット内にある要素に関連付けられたベクトルに似た要素）を問い合わせることもできます。とはいえ、その話は後ほど。まずは少し背景から説明します。
READMEのパスを見ると、実装は「modules」の中にあると分かります。しかし実際には、Vector SetsはモジュールではなくRedisコアの一部です。最初はモジュールとして開発しましたが、その後、Redis内部のモジュール性を促進するため、実装では引き続きModules APIを使うべきだと提案しました。これなら両方の利点があります。Redis 8以降のすべてのRedisインスタンスでVector Setsがネイティブなデータ型として利用できる一方、コアと実装の境界も明確です。
久しぶりのRedisの主要データ型
Redisで最後に追加された大きなデータ構造は、おそらくStreamsだったと思います。これも私が開発しました。その間に私は退職し、復帰し、フォークも起きました。それでも、新しいデータ型をRedisに導入する役目は私のようです :D それで構いません。プログラミングが好きなのと同じくらい、設計も大好きですから。ベクトルとベクトル類似性は概念的にはとてもシンプルなので、とてもシンプルなAPIに値する、と感じていました。それが私の目指したものです。Vector Setsはまだベータ機能ですが、ひとつ言えることがあります。APIは3分で覚えられると保証します。
ベクトル類似性を実装するうえでの基本要件として、HNSWをゼロから再実装することにしました（実装はhnsw.cで見られます）。これが中核のデータ構造になるため、GitHubから適当なコードを拾って満足するわけにはいかなかったのです。しかし論文を読み始めると、いくつか足りない部分があることが分かってきました。
そこで、以前HyperLogLogでいくつかの穴を埋める必要があったときのように（こちら: https://antirez.com/news/75）、新たなアルゴリズム上の課題がすでにいくつかありました。特に欲しかったのは次の2点です。
- ノードを本当に削除できること。Vector SetsではVADDで新しい要素を追加し、VREMで要素を削除できます。そして、メモリはできるだけ早く回収したかったのです。
- 要素を削除しても、HNSWグラフの連結性が保たれるようにすること。
このため、他のHNSW実装とはいくつか異なる点があります。トゥームストーンによる削除は使わず、ノードが削除された時点で実際にリンクを外し、代わりに有望な近傍ノードと再リンクします。そのために、私の実装ではリンクが相互的でなければならないよう設計しています。もはやベストエフォートの性質ではありません。これにより、挿入時に必要となる処理もかなり変わります。
HNSWにはもうひとつ、述語関数を使ってグラフを走査する機能も追加しました。これにより、指定した式に一致するノードを問い合わせられます。そのためには、貪欲なグラフ走査アルゴリズムをある程度変更する必要があります。訪問候補のノードを集め、結果セットも集めつつ、クエリの選択性が高すぎる場合に早期終了する条件も必要です。もちろん、グラフ全体の走査を引き起こしたくはありません。
HNSWの変更以外にも、より実用的で明白な要件がいくつかありました。
- すべてのベクトル類似性リクエストをスレッド化すること。Redisの世界では新しい話ですね。ただ、シングルスレッドかつ共有状態なしという設計は一般に良いものだと今でも考えていますが、ベクトルは特別です。他のRedisのデータ構造よりずっと遅いのです。さらに、スレッド化したVSIM（ベクトル類似性クエリを実行するコマンド）を実装しているとき、いくつかの工夫により書き込みの読み取り側と書き込み側を二つに分けられることも分かりました。近傍候補の収集をバックグラウンドで行い、実際の挿入はフォアグラウンドで実行できます。ただし、この分割はデフォルトではなく、VADDのCASオプションで明示的に有効化する必要があります。
- 量子化をサポートし、さらにデフォルトにしたいと考えました。そのためVector Setsには8ビット量子化とバイナリ量子化の両方が含まれています。次元削減のためのランダム射影もサポートしています。ただ、RPやバイナリ量子化も好きではあるものの、私にとっての決め手はint8量子化です。非常に高速で、FP32の25%のメモリしか使わず、埋め込みAIモデルで生成されたほとんどのベクトルでは、完全なベクトルの結果とほぼ同一です。
ちなみに最終結果は、とても高速な実装になったと思います。たとえば私のマシンでは、各要素が300コンポーネントの300万件のベクトルセットに対して、ノートPC上で毎秒5万〜6万件のVSIM（上位10件）を実行できます。ただし、ぜひ皆さん自身でベンチマークしてください。
また、Vector Setsはグラフとしてディスクにシリアライズされます。したがって、Redisの再起動後にメモリへ再ロードしても、挿入時間を払い直す必要はありません。100万要素ごとのロードは数秒で済み、メモリ内のHNSWに再追加する場合に必要な数分はかかりません。
インデックスではなくデータ構造
ここまで話してきたのはすべて低レベルな部分です。しかし私にとって、Vector Setsで最も興味深いのはデータモデルとそれを支えるAPIです。多くのデータベースでは、ベクトル類似性をある種のインデックスとして提供しています。しかし、ここはRedisです。Redisにあるものはデータ構造です。今回も例外ではありません。次のように追加します。
VADD mykey FP32 …blob of data… item1といった具合です。したがって、必要ならキーごとにひとつずつ、多数の小さなベクトルセットを持てます。ここで重要なのは、ベクトルをN個の異なるキーに分割し（挿入するアイテムなどをハッシュ化して、どのキーを選ぶか決める）、異なるキーに対する複数のVSIM呼び出しを単一の応答にまとめられることです。
VSIM word_embeddings_int8 ele "banana" WITHSCORES COUNT 4
1) "banana"
2) "0.9997616112232208"
3) "bananas"
4) "0.8758847117424011"
5) "pineapple"
6) "0.8288004100322723"
7) "mango"
8) "0.8179697692394257"異なるキーやインスタンスからそうした結果をいくつか取得すれば、スコア（1は同一、0は反対のベクトルを意味します）で並べ替えるだけです。
ですから、Vector Setsは異なるインスタンスで多数のベクトル（かなりのRAMを消費します）を扱うための、さまざまなパターンに組み合わせられると感じています。また、分割すれば書き込みは線形にスケールするのも興味深い点です。各サブセットは特定のキーにアクセスするため、複数の挿入を並列に実行できます。
いつものように、今はまだ明らかでない多くの利用パターンをRedisコミュニティが見つけてくれるでしょう。
フィルタリングの仕組み
フィルタリングについて言えば、スレッド化がRedisで一般的でなかったのなら、JSONはもっとそうでしょう。しかし今回初めて、ユーザー向けのRedis APIでJSONを直接公開する正当な理由を見つけました。
VGETATTR word_embeddings_int8 banana
{"len": 6}つまり、VSETATTR / VGETATTR（およびVADDでアイテムを追加する際にJSON属性を直接設定する同等のオプション）を使うことで、任意のアイテムに文字列を関連付けられます。
すると、次のようなことができます。
VSIM word_embeddings_int8 ele "banana" FILTER ".len == 3"
1) "yam"
2) "pea"
3) "fig"
4) "rum"
5) "ube"
6) "oat"
7) "nut"
8) "gum"
9) "soy"
10) "pua"フィルタ式はプログラミング言語ではありません。高水準プログラミング言語のif()文の中に書けるもの、つまり&&、||、明らかな演算子などです（もっといくつか追加することになると思いますが）。
詳細はドキュメントにあります。メモリ使用量の例や、個別機能の掘り下げた議論などもあります。近いうちにドキュメントを拡充したいと思っています。ひとまず、皆さんがVector Setsを本当に（本当に！）楽しんでくれることを願っています。バグを見つけたら、ぜひ知らせてください :)