Quicksilver v2：グローバルに分散されたキーバリューストアの進化（パート2）

このコンテンツは自動機械翻訳サービスによる翻訳版であり、皆さまの便宜のために提供しています。原本の英語版と異なる誤り、省略、解釈の微妙な違いが含まれる場合があります。ご不明な点がある場合は、英語版原本をご確認ください。

Quicksilverとは？

Cloudflareは、125か国以上、330都市以上にサーバーを設置しています。これらのサーバーはすべて、Quicksilverを実行しています。Quicksilverは、多くのサービスの重要な設定情報を含むキーバリューデータベースであり、Cloudflareネットワークにヒットしたすべてのリクエストによって照会されます。

Quicksilverは、リクエストを処理しながら使用されるため、非常に高速に設計されています。現在、リクエストの90%に1ミリ秒未満で、リクエストの99.9%に7ミリ秒未満で応答しています。ほとんどのリクエストは数個のキーに対するものですが、中には数百またはそれ以上のキーに対するものもあります。

Quicksilverは現在、合計サイズが1.6TBである50億を超えるキーバリューペアを保有し、世界中で毎秒30億を超えるキーを配信しています。データセットが常に増大し、新しいユースケースが定期的に追加されるため、Quicksilverの高速性を維持することは、いくつかの独自の課題があります。

Quicksilverは、あらゆる場所のすべてのサーバーにすべてのキー値を保存するために使用されていましたが、すべてのサーバーで使用できるディスクスペースには明らかに限界があります。例えば、Quicksilverが使用するディスクスペースが多いほど、コンテンツキャッシュに残されるディスクスペースは少なくなります。また、特定のkey-valueを含むサーバーが追加されるたびに、そのkey-valueの保存コストも増加します。

これが、ディスクスペースの使用が、Quicksilverのチームが過去数年間にわたって展開してきた主な戦いとなっている理由です。長年にわたり多くのことが行われましたが、今では、ディスクスペースの制限を回避し、最終的にQuicksilverのスケールを向上させることができるアーキテクチャを作成できたと考えています。

^{Quicksilverデータベースのサイズは、過去1年間に50%増加し、約1.6TBとなりました}

先日お話した内容

話のパート1では、Quicksilver V1が世界中の各サーバーにすべてのキーと値のペアを保存した方法について説明しました。とてもシンプルでスピーディな設計に、非常にうまく機能し、それを始めることは素晴らしい経験でした。時間が経つにつれ、ディスクスペースの観点からは十分に拡張できないことが分かりました。

問題は、ディスクスペースが急速に枯渇し、完全なスケーラブルバージョンのQuicksilverを設計して実装するのに十分な時間がなかったことです。したがって、Quicksilver V1.5が最初に作成されたのです。V1と比較して、各サーバーで使用されるディスク領域が半分になっています。

このため、Quicksilverに新しいプロキシモードが導入されたのです。このモードでは、Quicksilverはこれ以上、すべてのデータセットを格納することはなく、キャッシュのみを格納します。すべてのキャッシュミスは、完全なデータセットでQuicksilverを実行する別のサーバーでルックアップされます。各サーバーはQuicksilverの約10のインスタンスを実行し、すべてが異なるkey-valueのセットを持つ異なるデータベースを持っています。完全なデータセットのレプリカを持つQuicksilverインスタンスと呼んでいます。

Quicksilver V1.5の場合、特定のサーバー上のこれらのインスタンスの半分は、プロキシモードでQuicksilverを実行するため、完全なデータセットを持つことはできなくなります。残りの半分はレプリカモードで動作します。一時はうまく機能していましたが、最終ソリューションとはなりませんでした。

この中間ソリューションの構築には、チームがQuicksilverのより分散型のバージョンを実行する経験を得ることができるという利点がありました。

問題

Quicksilver V1.5が完全にスケーラブルでなかった理由はいくつかあります。

まず、個々のインスタンスのサイズがあまり安定していませんでした。キースペースは、Quicksilverのチームではなく、Quicksilverを使用するチームによって所有されるものであり、こうしたチームによるQuicksilverの使用方法は頻繁に変更されます。さらに、ほとんどのインスタンスは時間の経過とともにサイズが拡大するものの、Quicksilverの使用がチームによって最適化されている場合など、実際に小さくなるインスタンスもあります。その結果、当初はうまくバランスが取れていたインスタンスの分割も、すぐにバランスが取れなくなりました。

第二に、各サーバーでキャッシュする必要があるキースペースを推定するために行われた分析では、3日間にアクセスされたすべてのキーを取ることで十分なキャッシュとなると仮定していました。結果として、この想定は大きくデプロイされました。この分析では、キースペースの約20％がキャッシュに必要と推定されましたが、完全に正確ではないことが判明しました。ほとんどのインスタンスではキャッシュヒット率が高く、キャッシュ内のキースペースが20%以下であるものの、一部のインスタンスではもっと高いヒット率が必要な場合もありました。

しかし、主な問題は、Quicksilverがネットワーク上で使用するディスクスペースを40%も削減しても、実際にはスケーラビリティが向上するわけではないということでした。Quicksilverに保存されているkey-valueの数は増加の一途をたどっています。それから、ディスク容量が再び不足し始めるまで、約2年しかかかりませんでした。

ソリューション

^{Quicksilverは、一握りの特殊なストレージサーバーを除いて、これ以上データセット全体を格納することはなく、キャッシュしか格納しません。キャッシュミスは、完全なデータセットを持つストレージサーバーのレプリカでルックアップされます。}

スケーラビリティの問題の解決策は、新たな洞察によってもたらされました。実を言うと、数多くのkey-valueは実際にはほとんど使用されることがありませんでした。これらをコールドキーと呼びます。コールドキーにはさまざまな理由があります。古くてクリーンアップがされていないもの、特定の地域または特定のデータセンターでのみ使用されているもの、非常に長い間使用されていない、あるいは全く使用されていないものもあります（A例として、一度も検索されないドメイン名や、アップロードされたものの使用されないスクリプトなど）があります。

当初、チームはデータセット全体をシャードに分割し、異なるデータセンターのサーバーに分散することで、スケーラビリティの問題を解決することを検討していました。しかし、完全なデータセットをシャーディングすると、多くの複雑さ、ケースケース、未知のものが追加されます。また、シャーディングはデータの局所性を最適化しません。たとえば、キースペースが4つのシャードに分割され、各サーバーがシャードを1つ取得する場合、そのサーバーはローカルデータベースからリクエストされたキーの25%しか提供できません。また、コールドキーがシャードに含まれることに変わりはなく、不必要にディスクスペースを占有します。

データ局所性に優れ、使用されないキーの保存を明示的に回避するもう1つのデータ構造は、キャッシュです。そのため、大きなディスクを持つ少数のサーバーのみがデータセット全体を維持し、その他のすべてのサーバーはキャッシュのみを持つという決定がありました。これはQuicksilver V1.5からの明らかな進化です。キャッシングはすでに小規模な規模で行われていたため、すべてのコンポーネントがすでに利用可能だったのです。キャッシュプロキシとデータセンター間検出メカニズムはすでに導入されていました。2021年から使われており、徹底的な攻撃テストが行われました。しかし、もう1つコンポーネントを追加する必要がありました。

全サーバーのすべてのインスタンスがレプリカを持ついくつかのストレージノードに接続すると、多すぎる接続で過負荷になるのではないかという懸念がありました。そこで、Quicksilverのリレーが追加されたのです。各インスタンスでは、Quicksilverがリレーモードで実行する各データセンター内でいくつかのサーバーが選択されます。リレーはストレージノードのレプリカへの接続を維持します。データセンター内のすべてのプロキシがこれらのリレーを検出し、すべてのキャッシュミスがレプリカに伝達されます。

この新しいアーキテクチャは非常にうまく機能しました。それでも、キャッシュヒット率には改善が必要でした。

未来をプリフェッチ

^{解決されたキャッシュミスはすべて、データセンター内の全サーバーによってプリフェッチされます。}

私たちは、同じデータセンター内の他のサーバーでキャッシュミスであるすべてのキーをプリフェッチすることで、キャッシュヒット率を向上させるという仮説を持っていました。そこで、分析が行われた結果、あるデータセンター内のあるサーバーでキャッシュミスとなったすべてのキーが、近い将来、同じデータセンター内の別のサーバーでもキャッシュミスになる可能性が非常に高いことがわかりました。そこで、リレーショナルで解決されたすべてのキャッシュミスを他のすべてのサーバーに分散するメカニズムが構築されました。

データセンター内のすべてのキャッシュミスは、リレーからリクエストすることで解決され、リレーはそのリクエストをストレージノード上のレプリカの1つに転送します。そこで、リレーが解決されたすべてのキャッシュミスのストリームを公開し、同じデータセンター内のすべてのQuicksilverプロキシが購読することで、プリフェッチングメカニズムを実装しました。その結果得られたキー値は、プロキシのローカルキャッシュに追加されました。

この戦略は、同じデータセンター内でのキャッシュミスから直接生じたkey-valueのみでキャッシュを埋めるため、リアクティブプリフェッチングと呼ばれます。これらのプリフェッチは、キャッシュミスに対する反応です。別のプリフェッチングの方法は、予測プリフェッチングと呼ばれ、アルゴリズムが、まだリクエストされていないキーが近い将来どのように要求されるかを予測しようとします。この予測を行うためのいくつかのアプローチを試しましたが、改善が見られなかったため、このアイデアは使用されなくなりました。

プリフェッチングを有効にした場合、キャッシュヒット率は約99.9%にまで上昇し、パフォーマンスが最低になりました。これが当社の目指す目標でした。しかし、より多くのネットワークにこれを展開する中で、この新しいアーキテクチャで発生しているテール遅延があまりにも高すぎたため、キャッシュヒット率をさらに高める必要があるチームがあることが判明しました。

このチームは、dnsv2というQuicksilverインスタンスを使用していました。これは、DNSクエリが提供されるインスタンスであるため、遅延に影響を受けやすいインスタンスです。内部のDNSクエリーの中には、Quicksilverへの複数のクエリーを必要とするものもあるため、QuicksilverへのDNS遅延が増大すると、それらのクエリーの遅延が増大します。これが、Quicksilverキャッシュにもう一つ改善が必要と判断された理由です。

^{レベル1のキャッシュヒット率は平均で99.9%以上。}

シャーディングへの回帰

^{キャッシュミスは、別のデータセンターのレプリカに行く前に、まずデータセンター全体のシャードキャッシュで検索されます。}

より高いキャッシュヒット率が必要とされたのも、キャッシュのパフォーマンスが最低になった例でもありました。キャッシュは、最後にアクセスされてからキー値がキャッシュに保存される日数と定義され、その後キャッシュから削除されます。キャッシュの分析によると、このインスタンスにはかなり長い保持時間が必要だったことがわかりました。しかし、保持時間が長くなると、キャッシュがより多くのディスクスペースを占めることにもなります。つまり、利用できなかったスペースがあるのです。

しかし、Quicksilver V1.5を実行している間に、キャッシュは一般的に、大規模なデータセンターと比べて、小規模なデータセンターではるかに優れたパフォーマンスを発揮するというパターンにすでに気づいていました。これをきっかけに、最終的な改善につながる仮説が生まれました。

その結果、サーバーが少ない小規模なデータセンターは、一般的にキャッシュに必要なディスク領域が少なくなることがわかりました。その逆もまた然りで、データセンター内のサーバーの数が多いほど、Quicksilverキャッシュも大きくなる必要があります。これは、大規模なデータセンターは一般的に多数の人口に対応するため、リクエストの多様性が大きいという事実によって簡単に説明できます。サーバーが増えるということは、データセンター内で利用できる総ディスク容量も増えることを意味します。このパターンを利用できるように、シャーディングの概念が再導入されました。

キースペースが複数のシャードに分割されていました。データセンターの各サーバーには、シャードの1つが割り当てられました。キースペースの一部について完全なデータセットを含むシャードではなく、その代わりにキャッシュを含んでいます。これらのキャッシュシャードは、データセンター内のすべてのキャッシュミスによって設定されます。これはすべて、シャーディングを使用して分散されるデータセンター全体のキャッシュを形成します。

上記のように、完全なデータセットをシャーディングすることで問題となるデータの局所性の問題は、サーバーごとのローカルなキャッシュを保持することで解決できます。シャードキャッシュは、ローカルキャッシュに追加されます。データセンター内のすべてのサーバーは、ローカルキャッシュとシャードキャッシュの1つの物理的シャードのキャッシュの両方を含んでいます。したがって、リクエストされた各キーは、まずサーバーのローカルキャッシュで検索され、その後、データセンター全体のシャードキャッシュが照会され、最後に両方のキャッシュがリクエストされたキーを逃した場合、ストレージノードの1つで検索されます。

キースペースは、まずキーのハッシュを範囲ごとに1024の論理シャードに分割し、個々のシャードに分割します。これらの論理的シャードはさらに範囲によって物理的シャードに分割されます。各サーバーは、サーバーのホスト名で同じプロセスを繰り返すことで、1つの物理シャードを割り当てます。

^{各サーバーは1つの物理シャードを含みます。物理シャードは、さまざまな論理シャードを含みます。ローカルシャードは、すべてのキーをハッシュ化した結果である順序付けられたセットの範囲を含みます。}

このアプローチには、キャッシュを他のサーバーにコピーする必要なく、シャーディング係数を2つの要因でスケールアップできるという利点があります。このようにシャーディング要因が増加すると、サーバーは、そのサーバーの以前の物理シャードが含まれていたキー空間のサブセットを含む、新しい物理シャードが自動的に割り当てられます。これが完了すると、キャッシュには必要なキャッシュのスーパーセットが含まれます。不要になったキーバリューは、時間の経過とともに削除されます。

^{物理シャードの数が2倍になった場合、サーバーは以前の物理シャードのサブセットである新しい物理シャードを自動的に取得するため、関連するキー値がキャッシュに保たれます。}

このアプローチなら、Quicksilverに存在するキーの数が増えても、必要に応じて、データを再配置する必要なく、シャード化されたキャッシュを簡単にスケールアップすることができます。また、シャードは、非常に大きなキースペースの均一なランダムサブセットを含んでいるという事実により、うまくバランスになっています。

物理的なキャッシュシャードに新しいキー値を追加することで、プリフェッチングメカニズムに便乗します。プリフェッチングメカニズムでは、解決されたキャッシュミスが全てデータセンター内の全てのサーバーに配信されます。特定のサーバー上の物理シャードのキースペースの一部であるキーは、その物理シャードの一部ではないキーよりも長くキャッシュに保存されます。

シャード化されたキャッシュがキースペース全体をシャーディングするよりも簡単であるもう一つの理由は、キャッシュで一部の手間を省くことができることです。たとえば、古いバージョンのkey-valueの検索（マルチバージョン同時実行制御に使用）はキャッシュシャードではサポートされません。以前のブログ記事で説明したように、これは、別のサーバー上でkey-valueを検索する際に、そのサーバーに新しいバージョンのデータベースがある場合、一貫性を保つために必要です。適切なバージョンが利用できない場合、ルックアップは常にストレージノードに戻ることができるため、キャッシュシャードでは必要ありません。

^{プロキシには、最近書き込まれたすべてのキー値を含む最近のキーウィンドウがあります。キャッシュシャードには、キャッシュされたキーバリューのみが存在します。ストレージレプリカにはすべてのkey-valueが含まれ、さらに最近書き込まれたkey-valueの複数のバージョンが含まれます。データベースのバージョン1000を持つプロキシで、key1がキャッシュミスになった場合、キャッシュシャード上のそのキーのバージョンはデータベースのバージョン1002で書かれているため、新しすぎます。つまり、プロキシのデータベースのバージョンと一貫性がありません。これが、リレーが代わりにレプリカからそのキーを取得する理由であり、これにより、以前の一貫性のあるバージョンを返すことができます。一方、キャッシュシャードのkey2は、プロキシのデータベースのバージョンよりもずっと下のインデックス994で書き込まれているため、利用できます。}

キャッシュシャードのKey-Valueが使用できない、非常に特殊なコーナーケースが1つだけあります。これは、キャッシュシャードのkey-valueが、その時点のプロキシデータベースのバージョンよりも新しいデータベースのバージョンで書かれた場合に起こります。これは、key-valueにおそらく正しいバージョンとは異なる値があることを意味します。一般的に、キャッシュシャードとプロキシデータベースのバージョンは非常に近接しているため、これはこの2つのデータベースのバージョン間に書き込まれたkey-valueにのみ起こり、非常にまれなことです。そのため、ストレージノードへのルックアップによる影響はキャッシュヒット率に顕著な影響はありません。

階層型ストレージ

まとめると、Quicksilver V2には3つのレベルのストレージがあります。

1. レベル1：最近アクセスされたKey-Valueを含む各サーバー上のローカルキャッシュ。
2. レベル2：しばらくの間アクセスされていないものの、アクセスされたことのあるキーバリューを含むデータセンター全体のシャードキャッシュです。
3. レベル3：ストレージノード上のレプリカで、一部のストレージノードに存在し、コールドキーのみでクエリされます。

結果

第2のキャッシュレイヤーを追加することで、データセンター内で解決できるキーの割合が大幅に向上しました。最低パフォーマンスのインスタンスは、キャッシュヒット率が99.99%よりも高くなっています。その他すべてのインスタンスのキャッシュヒット率は99.999%より高くなっています。

^{レベル1とレベル2の合計キャッシュヒット率は99.99%以上です。}

最後に

すべてのデータが各サーバーに保存されていた旧型のQuicksilver V1から、階層型キャッシングであるQuicksilver V2へと移行するまでには、かなりの年月がかかりました。毎秒数十億のリクエストに対応しながら、数十万のライブデータベースを中断なく移行するなど、多くの課題に直面しました。多くのコード変更が発表され、その結果、Quicksilverは大きく異なるアーキテクチャを使用することになりました。これらはすべて、お客様に対して透明性を確保しながら行われました。すべてが反復的に行われ、常に前のステップから学び、次のステップに進みました。そして常に、可能な限り、すべての変更を簡単に元に戻すことができるようにしています。これらは、複雑なシステムを安全に移行するための重要な戦略です。

このようなストーリーが好きな方は、当社のブログで他の開発ストーリーを投稿することにご注目ください。このような問題の解決に熱意があるのなら、当社は組織全体で複数の種類の役職を採用しています。

ありがとうございました

最後に、Quicksilverチームの他のメンバー、Aleksandr Matveev、Aleksei Srikov、Alex Dzyaba、Alexandra (Modi) Stana-Palade、Francois Stiennon、Geoffrey Plouviez、Ilya Polykovskiy、Manzur Mukhitdinov、 Voldymyr Dorokhov氏