小紅書は、兆レベルのソーシャルネットワーク関係の課題にどのように対処するのでしょうか?グラフストレージシステム REDtao が登場しました!

1. 背景

Xiaohongshu は主に若者向けの生活記録・共有プラットフォームです。ユーザーは日常生活を記録し、短いビデオ、写真、テキストを通じてライフスタイルを共有できます。 Xiaohongshu のソーシャルフィールドには、ユーザー、ノート、製品などのエンティティがあり、これらのエンティティ間にはさまざまな関係があります。たとえば、ユーザーとメモの間には、「所有」（公開）、「いいね！」、および「収集」などの 3 つの関係があり、また、「いいね！」や「収集」などの対応する逆の関係もあります。

写真

Xiaohongshu のソーシャル グラフ データは、エッジ数兆単位の規模に達しており、急速に成長しています。ユーザーが Xiaohongshu にログインすると、各ユーザーには友達、ファン、いいね、コレクション、その他の自分向けにカスタマイズされたコンテンツが表示されます。

写真

この情報は高度にパーソナライズされており、膨大なソーシャル関係データからユーザー関連情報をリアルタイムで読み取る必要があります。これは読み取りが中心のプロセスであり、読み取りのプレッシャーが非常に高くなります。

これまで、私たちはこのソーシャル グラフ データをすべて、成熟した MySQL データベースに保存していました。しかし、1 秒あたり 100 万リクエストの規模でも、MySQL の CPU 使用率は依然として 55% に達しました。ユーザー数と DAU が爆発的に増加しているため、MySQL データベースを継続的に拡張する必要があり、コストと安定性に対する大きなプレッシャーが生じています。これらの問題を解決するために、適切なオープンソースソリューションが存在しないことから、2021 年初頭に REDtao を 0 から 1 に開発する旅を始めました。

2.REDtaoのグラフモデルとAPI

業界の他のベンダーの実装を徹底的に調査したところ、ソーシャル属性が強い企業は基本的に自社開発のグラフ ストレージ システムを持っていることがわかりました。

Facebook は、「TAO」と呼ばれる特殊な分散型ソーシャル グラフ データベースを実装し、それをコア ストレージ システムとして使用しています。 Pinterest も Facebook と同様に同様のグラフ ストレージ システムを実装しています。 ByteDance は独自の ByteGraph を開発し、コアソーシャルグラフデータの保存に使用しています。 LinkedIn は KV 上にソーシャル グラフ サービスを構築しました。

当時のソーシャル グラフ データはすでに MySQL データベースに保存されており、規模も巨大であったこと、またソーシャル グラフ データ サービスは安定性に対する要件が非常に高い非常に重要なサービスであることを考慮すると、振り返ってみると、Facebook が直面した問題は、Memcache と MySQL にデータが保存されていた私たちの問題と似ていました。したがって、Facebook の Tao グラフ ストレージ システムを参照することは、私たちの実際の状況と既存の技術アーキテクチャにさらに一致しており、リスクも少なくなります。

ソーシャル グラフへのアクセスは主にエッジ関係クエリです。グラフ モデルは、関係を<キー、値>ペアとして表します。キーは (FromId、AssocType、ToId) の 3 つ組で、値は属性の JSON 形式です。たとえば、「ユーザー A」が「ユーザー B」の後に続く場合、REDtao にマップされるデータ ストレージ構造は次のようになります。

 <FromId:用户A的ID, AssocType：关注， ToId：用户B的ID> -> Value （属性的json字段）

ビジネス側のニーズを分析し、ビジネス側が使用できる 25 個のグラフ セマンティック API をカプセル化しました。これにより、追加、削除、変更、クエリのニーズが満たされ、ビジネス側の使用方法が収束しました。 Facebook の Tao と比較して、ソーシャル グラフに必要なグラフ セマンティクスも補足し、不正行為防止シナリオ用の追加のフィルタリング パラメータも提供します。同時に、キャッシュ レベルでは、キャッシュ内のさまざまなフィールドのローカル セカンダリ インデックスの構成をサポートしています。一般的な使用シナリオを以下に示します。

シナリオ 1:

Aをフォローしているすべての通常ユーザーを取得します（不正行為ユーザーは除外します）

 getAssocs(“被关注类型”, 用户A的ID, 分页偏移量, 最大返回值, 只返回正常用户，是否按照时间从新到旧)

シナリオ2:

A のフォロワー数を取得する（そして不正行為ユーザーを削除する）

 getAssocCount(“被关注类型”, 用户A的ID, 只返回正常用户)

3.REDtaoアーキテクチャ設計

REDtao のアーキテクチャ設計では、次の重要な要素が考慮されています。

写真

3.1 全体的なアーキテクチャ

全体的なアーキテクチャは、アクセス層、キャッシュ層、永続層の 3 つの層に分かれています。ビジネス関係者は REDtao SDK を通じてサービスにアクセスします。以下のように表示されます。

写真

このアーキテクチャでは、Facebook Tao とは異なり、キャッシュ レイヤーは独立した分散クラスターであり、下の永続化レイヤーから分離されています。キャッシュ層とその基礎となる永続層は、独立して拡張および縮小できます。キャッシュ シャードと MySQL シャードは 1 対 1 で対応する必要がないため、柔軟性が向上します。 MySQL クラスターは、プラグ可能かつ交換可能な永続ストレージにもなります。

読み取りプロセス:クライアントはルーターに読み取り要求を送信します。ルータは RPC 要求を受信すると、エッジ タイプに応じて対応する REDtao クラスタを選択し、トリプル (FromId、AssocType、ToId) に基づくコンシステント ハッシュを通じてシャードが配置されている Follower ノードを計算し、そのノードに要求を転送します。フォロワー ノードはリクエストを受信すると、まずローカル グラフ キャッシュを照会し、ヒットが見つかった場合は結果を直接返します。ヒットがない場合、リクエストはリーダーノードに転送されます。同様に、リーダー ノードはヒットした場合に返され、ヒットしなかった場合は基盤となる MySQL データベースにクエリが実行されます。

書き込みプロセス:クライアントはルーターに書き込み要求を送信し、読み取りプロセスと同様に、対応するフォロワー ノードに転送されます。フォロワー ノードは書き込み要求をリーダー ノードに転送し、リーダー ノードはそれを MySQL に転送します。 MySQL が書き込みが成功したことを返すと、リーダーはローカル グラフ キャッシュに対応するキーをクリアし、他のすべてのフォロワーと同期してキーをクリアし、データの最終的な一貫性を確保します。

3.2 高可用性

REDtao は、キャッシュ層と永続層という 2 つの独立した層に分かれています。すべてのレイヤーで高可用性が保証されます。

自社開発の分散キャッシュ:

当社は、グラフ セマンティクスを実装し、自動障害検出と回復、水平スケーリングをサポートする独自の分散キャッシュ クラスターを開発しました。

これは 2 層のキャッシュであり、各シャードにはリーダーと複数のフォロワーが存在します。すべてのリクエストは最初に外側のフォロワーに送信され、その後リーダーに転送されます。これの利点は、読み取り圧力が高いときにフォロワーを水平方向に拡張するだけで済むことです。シングルポイントリーダー書き込み方式により複雑さが軽減され、データの一貫性を実現しやすくなります。

レプリカに障害が発生した場合、システムは数秒以内に切り替わります。永続化レイヤーに障害が発生した場合でも、分散キャッシュ レイヤーは外部読み取りサービスを引き続き提供できます。

高可用性 MySQL クラスター:

MySQL Cluster は、独自開発のミドルウェアを通じてデータベースとテーブルのシャーディング ソリューションを実装し、MySQL の水平拡張をサポートします。各 MySQL データベースには複数のスレーブがあり、社内の他の MySQL 運用および保守ソリューションと一貫性を保ち、高可用性を確保します。

電流制限保護機能:

キャッシュの故障により大量の MySQL リクエストが発生し、MySQL がクラッシュするのを防ぐため、マスター ノードあたりの同時 MySQL リクエストの最大数を制限して MySQL を保護します。最大同時リクエスト制限に達すると、リクエストは一時停止され、既存のリクエストが処理されて返されるまで待機するか、待機タイムアウトに達してリクエストが拒否され、それ以上のリクエストが MySQL に送信されなくなります。現在の制限しきい値はオンラインで調整可能であり、対応する制限は MySQL クラスターのサイズに応じて調整されます。

クローラーや不正なユーザーが同じデータを頻繁に更新するのを防ぐために、REDtaoQueue を使用して、同じエッジへの書き込みまたはクエリのリクエストを順番に実行します。多数の同一リクエストの同時実行を制御するために、キューの長さが制限されます。すべてのリクエストを制御する単一のグローバル キューと比較して、各リクエストに基づくキューは、他の通常のリクエストに影響を与えることなく、単一のリクエストを効果的に制限できます。

3.3 究極のパフォーマンス

データ構造の設計は、REDtao の高性能を保証する上で重要です。 3 層ネストされたハッシュテーブル設計を採用しました。特定の開始点 from_id に基づいて REDtaoGraph の第 1 レベル HashTable を検索することにより、すべてのタイプで対応するアウトエッジ情報をすべて記録しました。次に、第 2 レベルの HashTable で、特定の type_id に従って、特定のタイプの AssocType の下にあるすべての出力エッジの数、インデックス、およびその他のメタデータを検索します。最後に、最後のレベルの HashTable では、AssocType の to_id を通じて最終的なエッジ情報が見つかります。作成時間、更新時間、バージョン、データ、REDtaoQueue を記録し、time_index は作成時間でソートされたリストに対応します。最後のレベルのハッシュテーブルとインデックスは、最新の 1000 個のエッジ情報を格納するように制限されており、スーパーポイントがメモリを占有しすぎるのを防ぎながら、最新のホット データのクエリ ヒット率と効率を向上させることに重点を置いています。 REDtaoQueue は、現在のリレーションの読み取りと書き込みをキューに入れるために使用され、最後のリクエストのメタデータのみを記録します。クエリまたは書き込みが発生するたびに、まず REDtaoAssoc がクエリされます。キャッシュが存在しない場合は、まず REDtaoQueue のみを含むオブジェクトが作成されます。キャッシュがすでに存在する場合、キューのメタデータが更新され、キューはキュー内の最後のリクエストとして設定され、実行を待機するために一時停止されます。

写真

この多層ハッシュ + スキップ リスト設計により、ポイント、エッジ、インデックス、および時系列リンク リスト間の関係を効率的に整理できます。メモリの適用と解放は同じスレッド上で完了します。

オンライン環境では、当社のシステムは 16 コアのクラウド ベンダー仮想マシンで最大 150 万件のクエリ要求/秒を実行でき、CPU 使用率はわずか 22.5% です。以下はオンライン クラスターの監視チャートです。単一マシンの QPS は 30,000 に達し、各 RPC 要求は 50 のクエリを集約します。

写真

写真

写真

3.4 ユーザビリティ

豊富なグラフセマンティクス API:

ビジネス関係者が使用できるように、REDtao に 25 個のグラフ セマンティック API をカプセル化し、追加、削除、変更、クエリのニーズに対応しています。ビジネス関係者は、SQL ステートメントを自分で記述しなくても対応する操作を実装できるため、使用方法がより簡単かつ集中的になります。

統合アクセス URL:

コミュニティのバックエンド データは大きすぎるため、さまざまなサービスと優先順位に応じて、複数の REDtao クラスターに分割します。ビジネス側がバックエンド クラスターの分割ロジックを意識することを防ぐために、統合アクセス レイヤーを実装しました。異なるビジネス パーティは、同じサービス URL を使用し、SDK を介してアクセス レイヤーにリクエストを送信するだけです。アクセス レイヤーは、さまざまなビジネス パーティからのグラフ セマンティック リクエストを受信し、エッジ タイプに応じて異なる REDtao クラスターにルーティングします。構成センターに加入することで、エッジのルーティング関係をリアルタイムに把握し、ビジネス関係者が使いやすい統一されたアクセス URL を実現します。

写真

3.5 データの一貫性

ソーシャル グラフ データとしては、データの一貫性が重要です。特定のシナリオでは、データの最終的な一貫性と強力な一貫性を厳密に保証する必要があります。この目的のため、私たちは以下の措置を講じました。

キャッシュ更新の競合の解決策:

REDtao は、書き込み要求ごとにグローバルに増分される一意のバージョン番号を生成します。 MySQL データを使用してローカル キャッシュを更新する場合は、バージョン番号を比較する必要があります。バージョン番号がキャッシュされたデータのバージョンよりも低い場合、競合を回避するために更新要求は拒否されます。

書き込み後の読み取り一貫性:

プロキシは、同じ fromId を持つ頂点またはエッジのリクエストを同じ読み取りキャッシュ ノードにルーティングして、読み取りデータの一貫性を確保します。

マスターノード異常シナリオ:

リーダー ノードは更新要求を受信すると、更新要求をキャッシュ無効化要求に変換し、他のフォロワーに非同期的に送信して、フォロワーのデータが最終的に一貫性を持つようにします。異常な状況では、リーダーによって送信されたキューがいっぱいになり、キャッシュ無効化要求が失われると、他のすべてのフォロワー キャッシュがクリアされます。リーダーが失敗した場合、新しく選出されたリーダーは他のフォロワーにもキャッシュをクリアするように通知します。さらに、リーダーは MySQL へのアクセス要求の数を制限するため、個々のシャードのキャッシュがクリアされても MySQL がクラッシュしないようになります。

少数の強力な整合性のあるリクエスト:

MySQL スレーブは読み取りサービスも提供しているため、強力な一貫性を必要とする少数の読み取り要求に対して、クライアントは要求に特別なフラグを追加することができ、REDtao はフラグを渡し、データベース プロキシ レイヤーはフラグに基づいて読み取り要求を MySQL マスター データベースに転送し、それによってデータの強力な一貫性を確保します。

3.6 マルチクラウド アクティブ-アクティブ

クロスクラウド マルチアクティビティは当社の重要な戦略であり、REDtao がサポートする重要な機能でもあります。 REDtao の全体的なクロスクラウド マルチアクティブ アーキテクチャは次のとおりです。

写真

これは、次の図に示す Facebook Tao のクロスクラウド マルチアクティブ実装とは異なります。

写真

Facebook のソリューションは、DTS レプリケーションを通じて実行される基礎となる MySQL マスター スレーブ レプリケーションに依存しています。 MySQL のネイティブ マスター スレーブ レプリケーションは独自の機能であり、DTS サービスには MySQL のマスター スレーブ レプリケーションは含まれません。このソリューションでは、MySQL と DTS にいくつかの変更を加える必要があります。前述したように、キャッシュ層と永続層は分離されており、異なるアーキテクチャを持っています。

したがって、REDtao のクロスクラウド マルチアクティブ アーキテクチャは、当社独自のシナリオに基づいた設計です。既存の MySQL 機能を変更せずに、クロスクラウド マルチアクティブ機能を実装します。

1)永続性レイヤー MySQL のネイティブ マスター/スレーブ バイナリログ同期を使用して、他のクラウド上のスレーブ データベースにデータを複製します。他のクラウドからの書き込み要求と、強力な一貫性を必要とする少数の読み取り要求は、プライマリ データベースに転送されます。通常の読み取り要求では、この領域の MySQL データベースが読み取られ、読み取り要求のレイテンシ要件が満たされます。

2)キャッシュ レイヤーのデータ一貫性は、MySQL DTS サブスクリプション サービスを通じて実現されます。このサービスは、binlog を無効化キャッシュ要求に変換し、この領域の REDtao キャッシュ レイヤー内の古いデータをクリーンアップします。読み取り要求はこの領域内の任意の MySQL データベースをランダムに読み取るため、DTS サブスクリプションは遅延サブスクリプション機能を使用して、ログが最も遅い binlog 同期を持つノードから読み取られるようにし、この領域内の DTS 無効化キャッシュ要求と読み取りキャッシュ ミス要求間の競合を回避して、データの不整合を回避します。

3.7 クラウドネイティブ

REDtao のクラウド ネイティブ機能は、主に、弾力的なスケーリング、マルチ AZ およびリージョン データ分散のサポート、異なるクラウド ベンダー間の製品移行に反映されています。 REDtao は、弾力的な拡張と縮小、自動障害検出、回復のサポートを念頭に置いて設計されました。

Kubernetes クラウドネイティブ テクノロジーがますます成熟するにつれて、私たちは k8s の機能を活用してデプロイメントを仮想マシンから分離し、クラウドネイティブをさらに進め、異なるクラウド ベンダー間でのデプロイメントと移行を容易にする方法についても考えています。 REDtao は、Kubernetes クラスター上で実行される Operator を実装し、より迅速な展開、容量拡張、および障害が発生したマシンの交換を可能にします。 k8s にクラスター シャードの割り当てを認識させ、異なるホスト上の同じシャード下の Pod のスケジュールを制御するために、クラスター グループのシャード割り当ては k8s Operator によってレンダリングされ、DuplicateSet (Xiaohongshu が独自に開発した k8s リソース オブジェクト) の作成を制御します。 REDtao は、Operator によってレンダリングされたシャーディング情報に基づいて、マスター スレーブとクラスターを作成します。単一のポッド障害による再起動では、クラスター全体を再作成する必要なく、クラスターに再参加します。クラスターをアップグレードする場合、オペレーターはマスターとスレーブの割り当てを感知し、最初にスレーブ、次にマスターの順序を制御します。アップグレード中のオンライン操作への影響を軽減するために、シャード割り当て順にローリング アップグレードを実行します。

4. 旧サービスのスムーズなアップグレード

すべての変化は困難です。新しい REDtao の実装は簡単な部分にすぎませんでした。 Xiaohongshu のソーシャル グラフ データ サービスは長年にわたり MySQL 上で実行されており、さまざまなビジネスがその上で実行されています。いかなる小さな問題でも、Xiaohongshu のオンライン ユーザーに影響を及ぼします。そのため、サービスを中断することなく、既存のビジネスを REDtao に移行できるようにすることが大きな課題となっています。移行作業には 2 つの重要なポイントがあります。

● 古い大規模な MySQL クラスターは、優先度に応じて 4 つの REDtao クラスターに分割されました。この方法では、まず最も優先度の低いサービスを REDtao クラスターに移行し、その後、完全にグレー表示された後に優先度の高いクラスターを移行することができます。

● Tao Proxy SDK は、オリジナルの MySQL クラスタと REDtao クラスタの二重書き込みと二重読み取り、およびデータ検証と比較をサポートするために特別に開発されました。

移行にあたっては、まず優先度の低いデータを DTS サービス経由で MySQL から REDtao クラスターに移行し、ビジネス側の SDK をアップグレードしました。 DTS サービスは増分データを同期し続けます。ビジネス SDK は、構成センターの構成変更をサブスクライブします。 Tao Proxy SDK が MySQL クラスターと REDtao クラスターを同時に読み書きできるように構成を変更し、DTS サービスをシャットダウンします。この時点で、MySQL クラスタの結果がユーザーに返されます。

DTS サービスが停止すると、新しい MySQL データが DTS を介して同期され、REDtao クラスターの新しく書き込まれたデータが同期された古いデータによって上書きされる可能性があります。そのため、DTS サービスをシャットダウンした後、デュアル書き込みが有効になっている時点から DTS サービスがシャットダウンされる時点までの binlog をツールを使用して読み取り、データを検証および修復します。

修復が完了すると、Tao Proxy SDK のデュアル読み取りによって両側の不整合なデータ量が表示され、不整合なデュアル書き込みレイテンシによる不整合なデータを含む要求が除外されます。グレースケールの期間の後、差分の数が基本的に 0 であることが確認されたため、Tao Proxy SDK の構成が新しい REDtao クラスターの読み取り/書き込みのみに変更されました。

最終的に、2022年初頭に小紅書のすべてのコアソーシャルグラフのエッジレベルデータ数兆の移行と正確性の検証を完了し、移行プロセス中に障害が発生することなく、移行サービス全体を感知できない状態にしました。

5. オンライン化の成果とメリット

当社のソーシャル グラフ データ アクセスでは、リクエストの 90% 以上が読み取りリクエストであり、ソーシャル グラフ データには非常に強い時間的局所性があります (つまり、最近更新されたデータに最も簡単にアクセスできます)。 REDtao がオンラインになった後、キャッシュ ヒット率は 90% を超え、MySQL の QPS は 70% 以上削減され、MySQL の CPU 使用率は大幅に削減されました。 MySQL レプリカの数を減らした後、全体のコストは 21.3% 削減されました。

写真

すべてのビジネス アクセス メソッドは、REDtao が提供する API インターフェイスに統合されています。移行プロセスでは、MySQL データベースにアクセスする古い不合理な方法や、特定のフィールドをカスタマイズして特別な意味を持たせるという不合理な慣行も管理し、REDtao を通じてデータ アクセスを標準化しました。

2022 年の初めと 2023 年の初めを比較すると、DAU の増加に伴い、ソーシャル グラフのリクエストが 250% 以上増加しました。これまでのMySQLの旧アーキテクチャであれば、リソースの拡張は基本的にリクエストの増加率に比例し、少なくともリソースコストを1倍（数万コア）拡張する必要がありました。 90% のキャッシュ ヒット率を誇る REDtao システムのおかげで、リクエストが 2.5 倍に増加しても、全体的なコストは実際には 14.7% (コア数千個) しか増加しませんでした。コストと安定性が大幅に向上しました。

6. まとめと今後の展望

比較的短期間で、私たちは独自のグラフ ストレージ システム REDtao を開発し、ソーシャル グラフ関係データの急速な増加の問題を解決しました。

REDtao は FaceBook Tao の論文を参考にして、全体的なアーキテクチャとクロスクラウドのマルチアクティブ性に多くの改善を加えています。当社のビジネス特性に適合し、より優れた柔軟性を提供する新しい高性能分散グラフ キャッシュを実装します。同時に、k8s 機能を使用してクラウド ネイティブをさらに実現します。

DAU が成長し続けるにつれて、数兆個のデータの規模も拡大し続け、私たちはより多くの技術的な課題に直面しています。現在、社内の OLTP グラフ シナリオは主に次の 3 つの部分に分かれています。

●ソーシャルグラフデータサービス：自社開発のグラフストレージシステムREDtaoは、ソーシャルシナリオにおける超大規模データの更新と関連する読み取りの問題を解決します。現在、数兆の関係が保存されています。

●リスク管理シナリオ：自社開発のグラフデータベース REDgraph を使用して、マルチホップのリアルタイムオンラインクエリに対応します。現在、数千億のポイントとエッジの関係が保存されており、2 ホップ以上のクエリを満たしています。 （REDgraphの紹介は次回の記事で紹介します）

●ソーシャルレコメンデーション：これは主に2ホップクエリです。全量のデータは毎日 Hive を通じてバッチでインポートされ、DTS サービスはほぼリアルタイムでデータを書き込み、更新します。これはオンライン シナリオであるため、レイテンシ要件は非常に高くなります。現在の REDgraph ではこのような高い要件を満たすことができないため、ビジネス側では主に REDkv をストレージに使用しています。

上記のシナリオでは、ビジネス ニーズに迅速に対応するために、REDtao、REDgraph、REDkv という 3 つの異なる自社開発ストレージ システムを使用しました。明らかに、3 つのストレージ システムと比較すると、これらのグラフ関連のシナリオを解決するには、統合されたアーキテクチャとシステムを使用する方が適切です。今後は、REDgraph と REDtao を統合データベース製品に統合し、業界トップのグラフ技術を生み出し、社内のより多くのシナリオを強化していきます。最後に、テクノロジーを徹底的に追求する志を同じくする学生の参加を歓迎します。

7. 著者について

香港：Xiaohongshuインフラストラクチャストレージグループ。グラフストレージシステムREDtaoと分散キャッシュの研究開発を担当。

Liu Bei : Xiaohongshu インフラストラクチャ ストレージ グループの責任者。REDkv / REDtao / REDtable / REDgraph の全体的なアーキテクチャと技術の進化を担当。

8. チームプロフィール

インフラストラクチャ ストレージ グループは、ストレージ製品の機能、パフォーマンス、コスト、安​​定性に関するビジネス要件を満たすために、Xiaohongshu のビジネス部門に安定した信頼性の高いストレージおよびデータベース サービスを提供します。

現在、自社開発の分散KV、分散キャッシュ、グラフストレージシステム、グラフデータベース、テーブルストレージを担当しています。発売されたストレージ製品は次のとおりです。

● REDkv: 分散型高性能KV

● REDtao: ワンホップクエリをサポートする高性能グラフストレージデータベース

● REDtable: スキーマセマンティクスとセカンダリインデックスを備えたテーブルストレージを提供します

● REDgraph: 2ホップ以上のグラフセマンティッククエリデータベース