1. 背景

推奨システム、画像検索、記事の重複排除などのシナリオでは、特徴データに基づく k 最近傍検索に対する幅広い需要があります。

• 非常に高い検索パフォーマンスを必要としながら、数億のエントリを持つインデックスの検索をサポートします。

• インデックスのバッチリアルタイム更新をサポートします。

• 柔軟な A/B テスト実験のために複数のモデルとバージョンをサポートします。

• 特定の基準を満たさないデータを除外するためのフィルターと期限切れデータの削除をサポートしています。

調査の結果、既存のソリューションには以下の問題があることがわかりました。

• 学術界には、成熟したオープンソースのANN検索ライブラリが既に存在します。しかし、これらの検索ライブラリは単一マシンエンジンとしてのみ存在し、レコメンデーションシステムにサービスを提供する、高性能で信頼性が高く、スケーラブルな分散コンポーネントとして機能することはできません。

• 業界では、ほとんどのコンポーネントが ANN 検索ライブラリのラッパーに過ぎず、スケーラビリティや高可用性の面でオンライン システムの要件を満たしていません。一方、実装が比較的成熟している少数の分散検索システムでは、機能面でビジネス開発に対応することが困難です。

• 更新メカニズムに関しては、多くのコンポーネントがオフライン更新のみ、またはオンラインインターフェース更新のみをサポートしているため、 WeChat側のインデックス更新要件（毎秒数千回から毎時数億回に及ぶ）を満たすことができません。そのため、準リアルタイム更新と大規模なオフライン更新の両方を処理できる分散システムが必要です。

上記の要件と既存コンポーネントの制限に基づき、WFSとChubbyを使用してSimSvrを設計・実装しました。これは、以下の特徴を持つ、高性能で機能豊富な特徴取得コンポーネントです。

• 分散型でスケーラブルなアーキテクチャは、数億のインデックスをサポートし、同時インデックス クエリを高速化して、数億のインデックスを10 ミリ秒以内に取得できるようにします。

• 高性能リコールエンジンは、優れたリコール性能を持つhnswlibをプライマリリコールエンジンとして採用しています。ほとんどのリクエストは2ミリ秒以内に取得できます。

• 包括的なデータ スケジューリングと動的ルーティング機能を統合したクラスター管理。

• 多様な更新メカニズムにより、タスクベースの更新と自動更新、完全更新と増分更新がサポートされ、インデックス更新は1 秒あたり数千回から1 時間あたり数億回に及びます。

• 読み取り/書き込み分離メカニズムにより、オンライン サービスの高パフォーマンス読み取りに影響を与えることなく、膨大なコンピューティング リソースを使用してオフラインでのインデックス構築を高速化できます。

• 軽量の埋め込みキー値ライブラリ、単一テーブル上の複数のインデックス、マルチバージョン インデックス、フィルター、期限切れの削除をサポートする豊富な機能を誇ります。

SimSvrは現在、WeChatの動画チャンネル、Discover、検索、WeChatセキュリティ、絵文字検索で広く利用されています。次のセクションでは、SimSvrの設計と、ビジネスアプリケーションから生じる課題をどのように解決するかについて説明します。

2. 検索エンジン

2.1 エンジンの選択

ANN問題は学界で広く研究されており、nmslib、hnswlib、faissといった成熟したオープンソースのANN検索ライブラリが既に存在します。SimSvrでは、パフォーマンスとクラスタストレージ容量が最も重要な考慮事項であるため、以下の2つの検索エンジンが選択されました。

• hnswlib は、ann ベンチマークで最高の検索性能を備えており、リコールと検索時間に関するオンライン サービスの高い要件を満たすことができます (リコール率は 90% を超え、1 ミリ秒以内にリコールを完了できます)。

• Faiss の IVFx_HNSWy + PQz アルゴリズムは、10 ～ 30 倍のベクトル圧縮をサポートしており、リソースが制限された条件 (64G のメモリを搭載したマシンに保存された数億のインデックス データ) での高次元および大規模データのインデックス要件を満たすことができます。

ANN検索エンジンのパフォーマンス比較

2.2 リソースを巧みに活用してデータ容量を 50% 増加します。

• hnswlib は、リソース使用量の観点から単一モデルのケースのみを考慮するスタンドアロン検索エンジンです。一方、SimSvr は、オンライン サービスを提供して、通常は複数のモデルに対応するコンポーネントです。

• SimSvr は、ほとんどのシナリオで読み取りと書き込みの分離を特徴としています。
  上記の特性に基づいて、hnswlib を導入した後、SimSvr が単一マシンのシナリオでより多くのモデル インデックスに対応できるようにリソースを統合しました。

• 極端な場合（ワーカー スレッド 80 個と、インデックスが 2,000 万個あるテーブル 10 個を例に挙げると）：

• ライブ ネットワークでの動作 (特定のライブ モジュール (インスタンス マシン 11 台、ワーカー スレッド 240 個) を例に挙げます)。

2.3 ドット積距離再現率を62.6%から97.8%に向上させる変革の旅

• HNSW アルゴリズムはコサイン距離では良好なパフォーマンスを発揮しますが、ドット積距離を含むデータセットではパフォーマンスが低下します。

• ドット積距離はメトリック空間内になく、三角不等式を満たさず、距離の比較は推移的ではありません。

• Wikipedia からの距離空間の定義:

• hnswlib のドキュメントでは、ドット積は非メトリック空間に属すると述べられています。

• 論文「非計量類似度グラフ」では、
  最大内積探索では、ドット積距離をコサイン距離計算に変換する方法が説明されており、これを単に ip2cos と呼びます。

ip2cos距離変換の理論的基礎に基づいて、Kankan VideoのリアルタイムDSSMモデルを使用して実際のリコールパフォーマンス（64次元、IP距離、100万のインデックス付きデータポイント、10,000クエリにかかる平均時間）を比較し、ip2cosの驚くべき効果を目の当たりにしました。

2.4 Faissを使用して2時間のトレーニング時間を節約し、再現率を30％向上させる方法

• Faissにバッチkmeansクラスタリング手法が追加され、良好なクラスタリング結果を維持しながらトレーニング速度を大幅に向上させました。IVFファミリーのクラスタのトレーニング時間は、主にデータからnlistクラスタ中心を学習する必要があることに起因します。数千万件のレコードを持つデータセットの場合、nlistのサイズは20万を超え、CPU上での従来のk-meansトレーニングは非常に時間がかかります。以下は、128次元、IP距離、1,000万データポイントの場合のバッチkmeansによるトレーニングの高速化効果を示しています。

結果は、同じ反復回数では、バッチ kmeans を使用しない方法ではトレーニングに時間がかかり、収束が悪く、結果としてリコールが低くなることを示しています。

3. 全体設計

3.1 データ構造 - 小さな目標を達成するにはどのような変更が必要ですか?

単一モジュールで複数のモデルを扱うニーズに応えるため、SimSvr は複数のモデルを管理するテーブルの概念を採用しています。さらに、数億個の HNSW インデックスを持つテーブルをサポートし、同時インデックス構築を高速化するために、単一のテーブルをデータ構造に基づいて複数のシャードに分割し、各シャードがテーブルデータの一部を処理します。
tablei のインデックスは shard0、shard1、...、shardn で構成され、完全なインデックスを形成します。一方、セクションの数によってテーブル レプリカの数が決まります (スケーラブルな読み取り機能、災害復旧などに使用できます)。
SimSvr では、shardi_sectj をコンテナーと呼びます。これは、SimSvr でのデータのスケジュールと読み込みの最小単位です。

3.2 システムアーキテクチャ - 数億のインデックスと5ミリ秒レベルの検索をどのようにサポートするか

SimSvrアーキテクチャ

• FeatureKV と同様に、SimSvr にも 3 つの外部依存関係があります。

• Chubby はメタデータ、ルーティング情報、ワーカー リソース情報などを保存するために使用されます。SimSvr のデータ コラボレーションと分散タスク実行はどちらも Chubby に依存しています。

• USER_FS: 生データを保存するビジネス側の分散ファイルシステム。WFS/HDFSが利用可能です。このファイルシステムのパスと情報は、テーブル/タスクのメタデータに保存されます。

• SimSvr_FS: 生成されたインデックス ファイルまたは生の増分データ ファイルを保存するために Simsvr によって使用される分散ファイル システム。

• ワーカー

• 外部の関係者に検索サービスを提供する役割を担います。Chubbyをポーリングしてインデックスの更新を確認し、インデックスをローカルマシンにロードしてサービスを提供します。

• 各ワーカーが担当するデータはマスターによってスケジュールされます。ワーカーは、マスターがChubbyに保存した割り当て情報に従ってデータのロード/アンロードを行います。

• ワーカーのデータはマスターから割り当てられ、その他の状態には変化がありません。そのため、ワーカーはスケールアップとスケールダウンが容易です。

• マスター

• データのスケジュール設定: テーブルのメタデータとワーカーのステータスに基づいて、割り当てられていないデータまたは失敗したワーカーのデータは、他の有効なワーカーにスケジュールされます。

• ルーティング テーブルの生成: ワーカーのデータ読み込みステータスと位置に基づいてクラスターのルーティング テーブルを生成します。

• データ更新の認識：テーブルの自動更新カタログを確認します。最大数のカタログが肥大化している場合は、トレーナーにインデックス構築のタスクを作成します。

• マスターは、Chubby が提供する分散ロックを使用して、データのスケジュールとルート生成の一意の実行を保証するステートレス サービスです。

• トレーナー

• テーブル インデックスの構築とリソースの再利用の管理を担当します。

• トレーナーは、テーブル内の1つのシャーディングに対して一度にインデックスを構築できます。したがって、テーブルに複数のシャーディングがある場合、トレーナーの数を増やすことで、同時インデックス構築を高速化できます。

• Trainer はステートレス サービスであり、通常は WeChat Yard システムに展開され、WeChat のアイドル マシン上のリソースを最大限に活用します。

• データは自動的に更新されます

• テーブルを作成するときに、fs という名前のディレクトリが指定されました。このディレクトリには、増分番号を持つ一連のディレクトリが含まれています。

• ビジネス側でインデックスを更新する必要がある場合、最新のデータはより大きな数値ディレクトリにダンプされます。

• マスターは、最も多くのディレクトリの更新を検出し、メタデータを更新します。

• トレーナーはメタデータの更新を検出し、インデックスの作成をトリガーします。

• ワーカーはインデックスをロードし、インデックスの更新を完了します。

• データタスクベースの更新

• インデックス作成タスクは、API 呼び出しを通じてビジネス側によって事前に作成されます。

• インデックス作成タスクでは、データの構成情報（ファイルシステム情報やパスなど）が指定されます。

• トレーナーは、テーブルのタスク シーケンスに従ってタスクを実行し、インデックスを構築します。

• ワーカーはインデックスをロードし、インデックスの更新を完了します。

3.3 データスケジューリング - 卵を複数のバスケットに入れる方法

• SimSvr は、各テーブルの作成時にシャードの数 n とセクションの数 m を指定するため、このテーブルにはマスターがスケジュールする n * m 個のコンテナーがあります。

• マスターは、ワーカーのヘルス状態とリソース使用率に基づいてデータをスケジュールし、ルーティング テーブルを生成します。

• ルーティング テーブルには増加するバージョン番号があり、これを使用してルートの変更を検出できます。

• ワーカーは定期的に Chubby をポーリングして、データのスケジュール状態と最新のルーティング テーブル情報を取得します。

• クライアントが最初のリクエストを行うと、最新のルーティング テーブル情報を取得してローカルにキャッシュするようにワーカーにランダムに要求します。

• クライアントがローカル ルーティング テーブルを持っている場合、テーブルのデータ分布に応じてバージョン番号を持つターゲット ワーカーに同時リクエストを送信し、最終的にすべてのシャーディングの結果をマージしてビジネス側に返します。

3.4 システム拡張 - バスケットがいっぱいになったらどうすればいいですか?

• SimSvrはテーブルをより細かく細分化されたデータスケジューリング単位に分割し、すべてのマシンでデータが同一で​​ある必要はありません。そのため、マシンを追加することでクラスターのストレージ容量を拡張できます。

• 単一のテーブルの場合、読み取り容量がボトルネックに達したときに、このテーブルの読み取りレプリカの数を個別に増やすことができます。

4. ほぼリアルタイムの増分更新の課題 - 10秒以内にインデックス更新を完了する

• データの一貫性と永続性

• ほとんどの分散ストレージ コンポーネントでは、データの一貫性を確保し、それをローカル マシンに永続化するために、Raft や Paxos などの一貫性プロトコルが使用されます。

• SimSvr の場合、各テーブルは複数のシャードに分割され、シャードの数が奇数になることは保証されません。

• 一貫性コンポーネントと追加のストレージ エンジンをワーカーに追加すると、全体的な構造が複雑になります。

• 最終的に、慎重に検討し、業務におけるバッチ増分更新の特性を考慮した上で、まずデータをファイルシステム（FS）に保存し、その後ワーカーがデータをプルしてロードするソリューションを選択しました。このソリューションでは、最大1000個のキーの挿入を10秒以内に完了でき、ビジネス要件を満たしています。

増分永続化

• 増分更新のパフォーマンス保証

• オンライン インデックスの構築は CPU を大量に消費するプロセスであるため、ライブ ネットワーク上の読み取りサービスに影響を与えないように、ワーカーは増分データ更新に少量の CPU リソースのみを提供します。

• 増分データの小さなバッチの場合、ワーカーはファイル システム (fs) に保存されているデータを直接ロードし、インデックスのオンライン挿入を直接実行できます。

• 増分データ量が大量である場合、読み取りサービスへの影響や更新の遅延を回避するために、SimSvr はトレーナー内で大量のデータをマージし、同時にインデックスを再構築します。その後、ワーカーは構築されたインデックスを直接ロードします。
  

増分更新

5. 豊富な機能

5.1 追加機能リポジトリのサポート

• 推薦システムでは、検索に使われるインデックスだけでなく、動画の特徴やユーザープロファイルなどの特徴データも含めたデータを同じモデルで生成することがよくあります。

• このタイプのデータにはクエリ機能のみが必要であり、正しいリコール効果を生み出すために同じモデルとバージョンによって生成されたインデックス ライブラリと対話します。

• SimSvr は、このアトミック更新機能に基づいて、モデルとともに更新され、クエリにのみ使用される機能データを保存するための追加の機能リポジトリをサポートし、企業のデータ同期と調整の手間を軽減します。

5.2 単一テーブル複数インデックスはアトミック更新をサポートする

• レコメンデーション システムでは、A/B テストが非常に一般的であり、複数のモデルでの実験を同時に実行する必要があることがよくあります。

• さらに、シナリオによっては、同じモデルが異なるインデックス データを生成する場合があり、オンラインで使用する場合は、同じモデルのインデックスが同時に有効になっている必要があります。

• 上記の両方のシナリオでは、複数のテーブルを使用して複数のモデルをサポートすると、インデックス更新の実効時間に差が生じ、サポートできなくなります。

• このような状況では、SimSvr は同じテーブル上の複数のインデックスのアトミック更新をサポートし、インデックスが同時に有効になることを保証します。

5.3 マルチバージョンインデックス

• ABTest シナリオでは、複数のモデル間の実験に加えて、同じモデルの異なるバージョンによる実験もあります。

• 同じモデル内で、バージョンの反復や異なるバージョンの実験を伴うシナリオが広く普及しています。

• このようなマルチバージョン インデックスをサポートするために複数のテーブルを使用することは、ビジネス ユーザーにとっても SimSvr 管理にとってもあまり合理的ではありません。

• SimSvr は同一テーブルのマルチバージョン管理をサポートしており、本番環境で複数のバージョンを同時に使用できます。企業は必要に応じてターゲットバージョンをリクエストすることで、柔軟な実験を行うことができます。

5.4 ブルーム フィルタ、しきい値フィルタなどをサポートします。

• ビデオ アカウントのシナリオでは、企業は SimSvr を使用してビデオをインデックスします。

• ユーザーの特性を想起に利用する場合、ユーザーがすでに視聴した多くの動画が想起されることが多く、ユーザーエクスペリエンスに影響を与えます。

• リコール結果を増やし、その結果をフィルタリングしても、ヘビーユーザーの場合は同じ問題が残り、不必要なパフォーマンスのオーバーヘッドも発生します。

• SimSvr は、フィルター ロジックを埋め込むことで hnswlib を変更し、検索プロセス中に特定の条件を満たすキーをリアルタイムでフィルターできるようにすることで、検索された結果の有効性を確保します。

5.5 期限切れファイルの削除をサポートします。

• 一部のレコメンデーションシステムでは、データの適時性が非常に重要です。不適切な状況や不適切な状況を避けるため、最適な想起期間を過ぎたデータは想起結果に表示されるべきではありません。

• SimSvr は有効期限付きのデータのインポートをサポートしており、ライブリコールプロセス中に期限切れのキーをリアルタイムで削除して、正確なリコール要件を実現できます。

6. 現在のネットワーク運用状況

• SimSvr は現在、8,000 を超える論理コアを使用して 160 を超えるモデル インデックスを展開しており、合計インデックスは 20 億を超える特徴ベクトルで構成されており、ビデオ アカウント、視聴、検索などの推奨サービスで広く使用されています。

• 検索エンジンはSimSvrを使用してWeChatミニプログラムから高品質の記事のベクターインデックスを構築し、高品質の検索結果の再現率を向上させました。新しいソリューションは、以前のソリューションと比較して、高品質の結果の再現率を7%向上させました。

• 検索では SimSvr を使用してビデオ フィンガープリントを取得し、類似ビデオの重複を排除します。単一テーブル インデックスは 1 億 7000 万 * 128 次元に達し、平均取得時間は 8 ミリ秒未満、1 日の取得量は 12 億 5000 万件です。

7. まとめ

レコメンデーションシステムの急速な発展に伴い、特徴検索はますます多様なシナリオで利用されるようになっています。基盤コンポーネントとして、数億ものインデックスをサポートする必要があるだけでなく、その機能はビジネス開発に合わせて継続的に適応していく必要があります。そこで、私たちはSimSvrを開発しました。これはFeatureKV特徴ストレージと連携し、ビデオチャンネル、「Discover」、「Search」などのレコメンデーションシステムで重要な役割を果たしています。