Cloudflare で実装するハンドルネーム重複判定

X(旧 Twitter)、GitHub のようなハンドルネームのあるタイプのサービスでは、アカウント登録時に誰にも使用されていないハンドルネームを決める必要があると思います。この際、以下のように入力と同時にハンドルネームの使用可否が分かると、「登録がハンドルネームの重複ではじかれる」という良くない体験を回避でき嬉しいです。

しかし、現実的にはこのような機能は大半のサービスでは実装されていません。これは、全ユーザーの情報はサーバーしか持っていないため、入力のたびにサーバーへリクエストを飛ばすことになり、膨大なインフラコストがかかるためです。

最近、自分の開発した Touch Knot というサービスでは、Cuckoo Filter という確率的データ構造を用いたクライアントでの重複判定を Cloudflare 上のインフラで実現することで、低コストでハンドルネーム重複判定を実現しています。現状ユーザー数がそこまで多くないので断言はできないのですが、理屈上はユーザー数 100 万程度までは無料枠範囲内で実現できる想定です。

この記事では、Cuckoo Filter について解説し、Cloudflare Durable Object を利用した実装方法を紹介します。

Cuckoo Filter とは

偽陽性を許容する代わりに、全ての集合の要素を全て保持せずに集合に包含されているかの判定が可能な確率的データ構造です。今回の例で言うなら、集合を全ユーザーのハンドルネームの集合としています。2014 年に Cuckoo Filter: Practically Better Than Bloom という論文で発表されたものらしいです。

同様のデータ構造に Bloom filter というものもあり、こちらは Cassandra などの kvs でも活用されています。この発展形として生まれたのが Cuckoo filter で、パラメータを適切に設定してあげれば Bloom filter より少ないフィルターのサイズで偽陽性率低くすることができます。また、要素の削除にも対応可能です。ただ弱点がないわけではなく、集合サイズに対してフィルターのサイズが小さいと要素の追加にかかる計算量が増加し、最悪失敗する可能性があります。

仕組み

仕組み自体はシンプルで、集合の要素$x$に対してハッシュ値($h(x)$)とフィンガープリント($f(x)$)を基に格納先候補を 2 箇所存在するようにします。バケット配列と呼ばれる配列の、各格納先候補は片方は$h(x)$、もう片方は$h(x) \oplus f(x)$($\oplus$は xor)のインデックスのバケットとします。各バケットには複数のフィンガープリントを格納できるようになっています。この状態であれば、包含判定時には2か所を確認してどちらかにフィンガープリントがあれば包含されている、どちらにもなければ包含されていないと判定できます。

ただ、要素自体ではなくフィンガープリントしか格納していないため、同じバケットにフィンガープリントの一致する値が包含されていると偽陽性が発生します。フィンガープリントのサイズを大きくすれば偽陽性率は下がりますが、その分フィルターのサイズも大きくなりトレードオフが発生します。

また、要素の格納時に格納先候補 2 箇所がともに埋まっていた場合にも対応する必要があります。この場合には、既存のフィンガープリントのいずれかを別の格納先候補へ移動することで対応します。この際に格納先候補を$h(x)$と$h(x) \oplus f(x)$で決めているのが役に立ち、インデックス$i$にフィンガープリント$f(x)$が格納されているとき、$i \oplus f(x)$がもう片方の格納先候補となるため、高速に移動できます。ただ、当然もう片方の候補も埋まっている可能性もあり、その場合は再度移動を行う必要があるため、最悪永久に格納できず格納に失敗する可能性があるわけです。格納失敗の確率はバケット配列のサイズや各配列に格納するフィンガープリント数を大きくすることで下げられますが、当然その分フィルターのサイズも大きくなりトレードオフが発生します。

パラメータの検討方法

偽陽性率$\epsilon$はバケット当たりの要素数を$b$、フィンガープリントの bit 数を$f$として、以下の式で近似できます。

$$\epsilon \approx \dfrac{2b}{2^f}$$

2 バケット分のフィンガープリントと比較して、ランダムなフィンガープリントが一致する確率は$\dfrac{1}{2^f}$ なので、この式で近似される、というわけです。この式を基にすると、目標偽陽性率を設定した時、大抵の偽陽性率で$b=4$のときが最も$f$が小さくなるため、$b=4$が多くの場合採用されます。この場合、$f=10.5$で偽陽性率 1% となります。

この式の面白いところとして、集合の要素数やバケット配列のサイズは偽陽性率に一切影響しない点があります。極端な話、バケット配列のサイズが 1 でも偽陽性率は変わりません。ただし、「格納に成功した要素に対しては」という条件が入っている点が重要で、実際にバケット配列を1にすると挿入がほぼ成功しなくなります。また、$b$を小さくすることでも偽陽性率を下げられますが、こちらも挿入成功確率とのトレードオフがあります。

このため、Cuckoo Filter のパラメータを考える際には、挿入成功率も非常に重要な考慮すべき要素となります。と言っても、挿入成功率は超越方程式となってしまい代数的な解を出せません。そこで、負荷率という値を基にパラメータを考えます。バケット配列のサイズと集合のサイズを基に決まる負荷率$\alpha$がバケット当たりのフィンガープリント数$b$を基に決まる臨界負荷率$\alpha^*$を下回っているとき、実測上まず挿入失敗が起きないことが知られています。具体的な$\alpha$の計算式は、バケット配列のサイズ$m$、集合のサイズ$n$として以下です。

$$\alpha = \dfrac{n}{bm}$$

$b=4$のとき、実測値で臨界負荷率$\alpha^*=0.95$であることが知られているため、想定する集合サイズ$n$を基に、以下を満たすように$m$を設定すればよいです。

$$m \geqq \dfrac{n}{4 \times 0.95}$$

Touch Knot では、$b=4$、$f=12$とし、実際のユーザー数を基に上記の式を満たすように$m$を伸長させています。

この式で、集合サイズ(=ユーザー数)を 100万として計算すると、フィルターのサイズは約 1.6MB となります。若干大きいですが、描画に必要なデータではなくレイジーロード可能なものなので、この程度であればクライアント配信可能と言ってよいと思います。また、更にユーザー数が増えた場合にもクライアントでの偽陽性率が多少上がることを許容し、サーバー上で低偽陽性率の Cuckoo Filter を適用する2段構成とすることで耐えられそうとは思っています(こちらは未実装なので机上論になりますが)。

Cuckoo Filter によるクラアントサイド重複判定

ここまで説明した Cuckoo Filter を利用して、Touch Knot では以下のようなフローのハンドルネームの重複判定を行っています。サーバーで構築されたフィルタをロード時にクライアントで読み込み、ユーザー入力ごとに判定しています。多少ラグを許容すれば、CDN キャッシュも活用できるためかなり読み込みの負荷は軽減できます。

また、Cuckoo Filter は低確率ではあるものの偽陽性が発生しうるため、ハンドルネームが取得済みと判定された場合にはサーバーへリクエストを飛ばしているのがポイントです。これにより、特定のハンドルネームが誰も取得していないにもかかわらず取得済みと表示されてしまうのを回避できます。

Cloudflare 上でのフィルタ管理実装

ここまでクライアントでのフィルタの利用方法周りを説明してきましたが、サーバー上でのフィルタの構築も適切に行う必要があります。

というのも、Cuckoo Filter には分散構築ができないという非常に厄介な点があるためです。バケットからの追い出しなどがおきる関係で、2か所で構築されたフィルタをマージするようなことはできず、フィルタへの要素追加は1スレッドに集約する必要があります。ユーザーごとに1度しか発生しないかつ、極めて軽量なメモリで完結する処理なため1スレッドでも十分捌けはするのですが、分散処理を前提とした Cloudflare 上に構築するのが極めて困難になります。

また、ここまでの説明でしれっと「フィルタを伸長する」と言っていましたが、重い伸長処理をリクエストを受けつつ行えるようにするのもなかなかに難しいです。特に、Cloudflare ではリクエスト当たりの CPU 時間制約が厳しいため、Cloudflare 外で構築を行う必要があります。

これらの問題を Durable Objects と KV を活用することで回避する方法について説明していきます。

Durable Objects でのアカウント登録時のフィルタ更新

アカウント登録時のフィルタ更新処理を1箇所にまとめる必要がある点には、Durable Objects を用いることで対処しました。Durable Objects は基本的にステートを保持できない Cloudflare 上で、ステートフルな処理をするための機構です。一般的には Websocket を用いたサーバーサイド push などのために使用されるものです。

使い方は簡単で、DurableObjectクラスを継承したクラスを定義し、export するだけです。このクラスをキーごとにインスタンス化することができるようになります。そして、キーごとにどこかの Cloudflare エッジでクラスの各種状態を保持し、以降のキーに関連するリクエストをそのエッジへルーティングして処理してくれます。これにより、キーに対応した状態を引継ぎ、リクエストを処理できます。

Touch Knot では、フィルタを保持するための Durable Objects を定義し、フィルタの更新などを全てここで行うことで、Cloudflare 上で Cuckoo Filter の更新処理を実装しました。このようにすることで、整合性を保ちフィルタの更新を行えます。

また、Durable Object は上記のように本来 Websocket のような失われても致命的な影響の出ない要素を扱うためのものです。このため、ここでしかフィルタを保持しないのは危険と判断しました。そこで、Durable Object の Alarm と呼ばれる処理の実行を予約する機構を用いて、KV へのフィルタデータのバックアップを行っています。Alarm を用いると、「～分後にこの処理を行う」といった処理のスケジューリングを行うことができます。これを利用して、アカウント登録が行われた際に Alerm がなければフィルタデータを最終更新時刻と一緒に記録する処理を行う Alarm をセットするようにします。これにより、Durable Object のデータが失われても KV から復旧することが可能になります。

また、この KV のデータは、Durable Object 障害時のフォールバック先としても機能しており、Durable Object からのフィルタ取得に失敗した場合には KV 上のバックアップを使用するようにしています。R1 などではなく KV をバックアップ先としている理由は、フィルタのサイズがクライアント配信できる程度には小さく、フォールバック時のアクセス速度が圧倒的に R1 より KV の方が早いためです。

フィルタサイズの伸長

Cuckoo Filter の特徴である空間効率を最大限生かすには、ユーザーの増加に合わせたフィルタサイズの伸長が必要です。フィルタの再構築作業は非常に CPU を食いとても Cloudflare 上で実行できるものではありません。また、この作業自体は定期的に発生するものなため、極力無停止かつ安全に行えるようにしたいです。

そこで、KV と Durable Object を活用した、フィルタの入れ替えを実装しています。具体的には、D1 中のユーザー情報を基にフィルタを再構築し、KV へアップロードするスクリプトを用意します。そして、管理者用の API を呼び出し、Durable Object 上で値を KV から pull します。この際に、スクリプトでのフィルタ構築以降に登録されたユーザーデータを取り込むことで、整合性を維持します。

このような流れにすることで、無停止でのフィルタ更新が可能となります。また、このフローではフィルタ構築後、明示的な操作により反映する形になっています。そのため、反映前にフィルタに問題ないかテストでき、実際反映前にはランダムな実ハンドルネームでフィルタの動作を検証することで、フィルタ構築スクリプトにバグなどがあった場合でも気づきやすくしています。

対象データの機密性に関する注意点

今回は公開情報であるハンドルネームを対象としていたため問題ありませんが、扱うデータの機密性には注意する必要があります。

例えば、メールアドレスの重複判定を同様の仕組みで行ってしまうと、攻撃者がフィルタを利用して高速にメールアドレスの存在確認が行えるようになってしまいます。そのため、ユーザーがスパムメールやフィッシング攻撃の対象となってしまうことになりかねません。また、サーバー上での判定に使う場合も同様で、フィルタに存在する場合明確にサーバーの応答が速くなりタイミング攻撃によるメールアドレスの存在確認が可能となってしまいます。

このため、今回と同様の仕組みを実現する場合には、対象のデータが公開情報かの検討が必要になります。

まとめ

この記事では、Cuckoo Filter というデータ構造を利用して、ハンドルネームの重複判定をクライアントで行う手法を紹介しました。正直、オーバーエンジニアリング気味ではありますが、機会があれば是非活用していただける嬉しいです。

また、今回紹介した機能を組み込んでいる SNS アカウント共有アプリ Touch Knot もぜひ使ってみてほしいです。技術カンファレンスなどを想定した、スマホをタッチするだけで NFC で SNS アカウントを共有できるアプリになっています。アプリ自体は Android 専用ですが、受け取り側はアプリインストール不要で iOS でも問題ないです。