UD Day 11 アーキテクチャーの検討6(URLをどう保存するか)

UDでは、クライアントサイド(ブラウザ)で閲覧しているページのロードが終了した段階で、URLをキーとしたリクエスト(コメントを取得するためのリクエスト)をバックエンドのシステムに送出します。URL長の最大値は非常に大きいものになるため、このままではデータベースのキーとするには不適切です。
そのため、分散系のDBではよくある手法ですが、キーとしてURLのハッシュ値を用います。

ハッシュ値を用いる際に検討しておきたいのは、どの程度の確率でハッシュ値が同じになるか(衝突するか)です。これは、誕生日のパラドックスと言われます。

誕生日のパラドックス

異なるURLがたまたま同じハッシュ値になってしまうケースです。
数学的には誕生日攻撃と呼ばれるようです(異なる入力値が同一の関数を経て同じ結果になってしまうこと)。
上記リンクによると、衝突がおこなるまでの試行回数の期待値(birthday bound)は、nビットの数字において、2のn/2乗となるようです。

暗号アルゴリズムごとのbirthday bound

いくつかのアルゴリズムでどの程度のbirthday boundの値になるかを示したのが、上記の表になります。MD5の場合で1844京回となります。
世界中のウェブページについて投稿された場合に、どの程度であれば、衝突がなるべく少なくすることができるか。正確な計算はできませんが、この点を類推の上で、ハッシュアルゴリズムを選択しました。参考にしたリンクは、「参考リンク」の「URLのハッシュについての質問」のページです。ここでは、選択対象とそのロジックについては割愛します。

では、次に、これをDBで保存する際には、どういうデータ型を用いればよいでしょうか。Cassandra(ScyllaDB)のケースで以下の2つの方法が考えられます。
a. string型
stringで保存するには、16進数のまま、もしくは16進数をbase64,ascii85などに変換して保存できます。16進数の値をそのまま文字列として保管する場合40byte, base64に変換する場合、平均26.7byteになります(試行結果)。

b. blob型
バイナリーで保存する場合には、blob型を用いることが出来ます。
CQLでinsert、selectする場合にも特段問題なく利用できます。

実際に同じデータでどの程度のサイズの違いがあるかを試してみると、
a: 72,879,839
b: 52,626,907
となりました。データの効率性からすると、後者が良いようです。

以上の考察結果から、UDでは、ハッシュ変換したバイナリーデータをblob型でDBに保管する方法を選択しました。(続く)

参考リンク)
shortURL考察
誕生日のパラドックス
誕生日攻撃
URLのハッシュについての質問
SHA-1を保存する場合の方法、CHAR(40)かBINARY(20)。BINARYで正常な使用ができるのかは確認が必要。
UNHEX, char, binaryについて
PKにする場合は、BINARYは適切か
GUID/UUIDをPKに使う

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です