Meta における分散キャッシュの一貫性保証
元ネタは OSDI 25 に投稿された Meta による論文 Skybridge: Bounded Staleness for Distributed Caches です。Murat Demirbas によるブログ記事 ATC/OSDI’25 Technical Sessions で見つけました。
Meta は、ソーシャルグラフ等のデータを管理するために TAO というグラフデータベースを内製しています。TAO は MySQL をバックエンドに持つ read-through かつ write-through なキャッシュで、グラフの辺や点に関するクエリをサポートしています。TAO は世界中のリージョンにデプロイされており、保存されたデータは各リージョンのレプリカ（キャッシュと MySQL）に複製されています。
リージョン間のデータのレプリケーションは非同期的に行われます。よって、TAO のレプリカはユーザーが自身のデータを読み出す場合を除いて結果整合性（eventual consistency）しか保証していません。そのため、開発者は最新のデータを取得するためにリトライや分散ロックを実装する必要があり、複雑性や障害の温床になっていました。
結果整合性の問題は、書き込んだデータをいつ読み出せるのかが分からない点です。そこで、データの書き込みから最低でも2秒経過していればその値を十分高い確率で読み出せることを保証するために、Skybridge と呼ばれる新しいコンポーネントが導入されました。
クロスリージョンのレプリケーションにはレイテンシの問題がつきまといます。なので戦略としては、TiDB のように Raft 等の合意アルゴリズムを用いて強整合性を保証する（ただし最低3個のレプリカが必要）か、非同期レプリケーションを用いる（ただし結果整合性までしか保証できない）かのどちらかを採用するのが主流です。Skybridge は後者寄りの方法ながら、結果整合性の保証に定量的な基準を与えることを試みたユニークなものだと言えます。
クロスリージョンレプリケーション
TAOのアーキテクチャ。赤い実線は同期書き込み、赤い点線は非同期書き込み、青い実線は読み出しのパスを表します。
TAO において、異なるリージョンへのデータのレプリケーションは Wormhole という内製のコンポーネントを通じて行われます。Wormhole は Apache Kafka に似た Pub-Sub システムで、あるリージョンにおけるプライマリ MySQL シャードの更新内容を別のリージョンの TAO キャッシュに反映します。このとき、Wormhole は更新の順序を保持（インオーダー）しつつ、at-least once セマンティクスで送信します。
Meta の MySQL は、変更の他にハートビートと呼ばれるメッセージを500ミリ秒ごとにレプリケーション先へ送信します。ハートビートには時刻（hybrid-logical clock; HLC）が含まれており、どこまでレプリケーションが完了したかを記録するためのウォーターマークとして使うことができます。
一貫性レベルの変遷
TAO は元来、ユーザーからのリクエストを特定のキャッシュサーバーにルーティングすることで read-your-writes (RYW) 一貫性レベルを保証していました。しかし、なんらか理由でリクエストが別のサーバーにルーティングされたり、キャッシュがレプリケーションの完了前に揮発したりすると、古い結果が読み出されることがありました。また、リクエストのルーティングをユーザーごとに固定するアプローチには、スケーラビリティと可用性の点で問題がありました。
このような問題の解決を図ったものが、2016 年に導入された FlightTracker です。FlightTracker はユーザーが行った書き込みのメタデータをチケットとして管理し、読み出し時にチケットに対応するデータが含まれるようにすることで、各ユーザーごとに RYW を保証します。
しかし、FlightTracker は複数のユーザーによるリクエストに対しては強い一貫性を保証しません。例えば、Alice が Bob をあるチャットグループに招待したとき、Bob はレプリケーションが完了するまでの間、自身がグループに加入したことを認識できません。
Skybridge はこのようなケースにおいて、 Bob が Alice（別のユーザー）による書き込みをある一定の時間が経過した後であれば読み出せるようにするために導入されました。この一貫性レベルは bounded staleness と呼ばれており、Azure CosmosDB や Spanner などがサポートしています。
個人的には、FlightTracker の論文が発表された時点（2020年）で、旧 Facebook がクロスユーザーのリクエストに関する一貫性の保証を割り切って諦めていたのが印象的でした。Facebook スケールで一貫性の保証をしていないのだから、という理由で自分が関わっていたプロダクトでも同様の決断をしたこともあります。ですが結局、結果整合性を扱うのは難しすぎるということなのでしょう。
Bounded Staleness の保証
Skybridge は既存の RYW の保証に加えて、書き込みから2秒以上経過すれば異なるリージョンからのリクエストも最新のデータが取得できることを保証します。この2秒という閾値は、Wormhole がほとんどの場合に（99.993%）レプリケーションを完了でき、かつユーザビリティの観点からも問題が無い値として選ばれています。
現実的には、2秒の bounded staleness を100%保証することは不可能です。よって Skybridge の目的は、Wormhole レプリケーションの一時的なラグによって生じる一貫性のロスに対処し、bounded staleness の確度を高めることにあります。実際に Skybridge を用いることで、 TAO は2秒後にデータを読み出した際の一貫性を 99.99998% まで向上させることができました。
Skybridge を使わない staleness の判定
Skybridge がなくても、前述のハートビートを用いることでキャッシュが最新である（stale ではない）かどうかを判定することができます。
Bounded staleness の閾値を
以下の不等式が成り立つ場合に、キャッシュされたアイテムが最新であるといえます。
右辺は、レプリケーション先においてキャッシュ中のアイテムの更新が止まった最新の時刻を表します。特に
この判定方法の問題点は、キャッシュされたアイテムが古い（最新の値が反映されていない）のか、単に更新されていないだけなのかの判別がつかないことです。 レプリケーションが遅延すると、キャッシュの更新の有無にかかわらず、シャード中のすべてのアイテムが古いと判定されてしまいます。
Skybridge を用いた staleness の判定
Skybridge は上記の問題点に着目し、データをキャッシュするための既存のレプリケーションパス（Wormhole）に加えて、データの更新時刻を提供するための別のレプリケーションパスを導入することで、TAO シャードがキャッシュの staleness を確認できるようにしました。この Skybridge のレプリケーションは、順序と耐久性を保証する Wormhole とは異なり、更新時刻のレプリケーションをアウトオブオーダーで行いデータロスを許容することで、レプリケーションの遅延を緩和します。
Skybridge のシステムは、主に3つの要素によって構成されます。
- Skybridge (write)： データが TAO のプライマリに書き込まれた時刻を収集する。
- レプリケーションレイヤ：データの書き込み時刻を別のリージョンに送信する。
- Skybridge (read)： キャッシュの鮮度を判定するために、データの書き込み時刻を提供する。
Skybrige のアーキテクチャ。赤い実線は同期書き込み、赤い点線は非同期書き込み、青い実線は読み出しのパスを表します。
Skybridge (write) は、TAO writer の配下にある MySQL シャードに書き込まれたデータの書き込み時刻を収集し、時間スパンごとの書き込みウィンドウ（write window）という形式でレプリケーションレイヤに提供します。どの TAO writer がどの MySQL シャードを担当しているかを管理するために、TAO writer はリースを Skylease と呼ばれるコンポーネントに登録します。Skybridge はこのリースを用いることで、書き込み時刻のレプリケーションの失敗（ギャップ）を検知します。
レプリケーションレイヤは、書き込みウィンドウに含まれる各キャッシュキーと書き込み時刻の組（書き込みメタデータ； write metadata）を Skybridge (read) に転送します。この転送は pull-based です。すなわち、 Skybridge (read) が Skybridge (write) にリクエストを送信して書き込みメタデータを取得します。これにより、Skybridge (read) は直近の書き込みメタデータの取得を優先したり、失敗した際には別のソースからデータをフェッチしたりすることができます。
Skybridge (read) は、取得した書き込みメタデータをインデックスし、TAO の read tier に提供します。TAO の read tier は、取得したキャッシュが古いかどうかを以下の3ステップで検証します：
- ウォーターマークによって判定する（Skybridge を使わない staleness の判定と同様）
- Skybridge (read) から事前に取得したブルームフィルタによって判定する
- Skybridge (read) からキャッシュキーの書き込み時刻を取得して判定する
検証によってキャッシュが最新であると判定できたら、キャッシュされた値をそのまま返します。キャッシュが古いと判定された場合、もしくはレプリケーションのギャップによって判定ができなかった場合は、上流から最新の値を取得してキャッシュを更新します。
Skybridge (read) が保持できる書き込みメタデータのインデックスサイズはメモリ容量に依存しますが、通常は数分程度の期間のメタデータを保持できます。また、特定のシャードに対するレプリケーションのラグが大きい場合は、一時的に保持期間を延ばすこともできます。
可用性の担保
Skybridge は既存のシステムの可用性やパフォーマンスを極力損なわない形で導入されました。
TAO への書き込みが急増すると、Skylease からのリースの取得のためにブロックされる可能性があります。この問題を緩和するため、リースの取得にはレートリミットやサーキットブレーカーが設定されており、取得ができない場合にはそのまま書き込みが継続できるようになっています。また読み出しの際も、Skybridge への書き込み時刻の取得にレートリミットが設定されており、制限を超えた際にはキャッシュの新旧に関わらずデータが返されます。
これらの戦略はフェイルオープンです。Skybridge はシステムが不安定なとき、デフォルトで一貫性よりも可用性やパフォーマンスを優先します。ただし一貫性が優先されるべきシナリオでは、クライアントは TAO のリクエストに特定のフラグを設定し、bounded staleness が保証できないときにリクエストが失敗するようにします（フェイルクローズ）。
まとめ
Meta が複数リージョンに分散されたキャッシュの一貫性を高めるために導入した、Skybridge というコンポーネントについて紹介しました。キャッシュの取得をインオーダーで行っていることに起因する一貫性保証の課題を、アウトオブオーダーで書き込み時刻を伝播する別のレプリケーションパスによって緩和する手法でした。
書き込み時刻のロストを検知するために、リースやその管理コンポーネント（Skylease）を導入する必要があります。これにより、システムの複雑性の増加や、可用性やパフォーマンスの課題を注意深く解決しなくてはならない点などが懸念されます。
「S秒経過した後の一貫性を保証する」という bounded staleness の定義には、Freshness SLO との類似性が見られます。Skybridge には Freshness（鮮度）と可用性・パフォーマンスとの間にトレードオフがあるので、適切な運用ポリシーを定めるのは難しいように思えますが、検討してみるのも面白いでしょう。
-
PTP や GNSS アンテナを用いたより正確な時刻同期のシステムが Meta のデータセンターに導入されていますが、Skybridge の導入時点ではまだ検証段階のようです。 ↩︎
Discussion