新しいキーが必要なときはいつでも、すでに生成されたIDのいずれかを使用することができます。 この方法では、新しいリクエストが来るたびに、IDを作成したり、その一意性を確認したりする必要がないため、処理が速くなる可能性があります。

1文字を格納するのに1バイト必要なので、これらのキーをすべて

6 (文字) * 68.に格納することができます。7B (unique keys) ~= 412 GB.

★Availability & Reliability:

UGSのコピーを1つ持っていると、単一障害点になってしまいます。 そこで、UGSのレプリカを作成する必要があります。

各UGSサーバはkey-DBからいくつかのキーをキャッシュすることができます。 それは物事をスピードアップすることができます。 しかし、我々は注意しなければなりません。もし1つのサーバがすべてのキーを消費する前に死ぬと、我々はそれらのキーを失うことになります。

可用性を確保するためには、システム内の単一障害点を確実に取り除く必要があります。 データのレプリケーションは、単一障害点を除去し、バックアップを提供します。 データベースサーバーの信頼性を確保するために、複数のレプリケーションを保持することができます。

★DataStorage:

このシステムでは、何十億ものレコードを保存する必要があります。 私たちが保持する各オブジェクトは、おそらく 1 KB 未満です。 あるURLのデータは、他のデータとは関係ありません。 そこで、CassandraやDynamoDBなどのNoSQLデータベースを利用することができます。

★ スケーラビリティ：

何十億もの URL をサポートするには、データベースを分割して、データを異なる DB サーバーに保存する必要があります。

i) ハッシュ キーの最初の文字に基づいて、データベースを分割することができます。 A’で始まるキーをあるサーバーに、’B’を別のサーバーに置くことができます。 これは範囲ベースのパーティショニングと呼ばれます。

この方法の問題点は、不均衡なパーティショニングにつながる可能性があることです。 たとえば、「Z」で始まる単語はほとんどありません。一方、「E」で始まるURLは多すぎます。

頻繁に発生しない文字を1つのデータベースパーティションにまとめることができます。 データオブジェクトを格納するパーティションを決定するために、キーのハッシュを取ることができる。 ハッシュ関数がサーバー番号を生成し、そのサーバーにキーを格納することになる。 この処理により、よりランダムな分布にすることができる。 これはハッシュベースのパーティショニングです。

この方法でもパーティションに負荷がかかる場合は、Consistent Hashingを使用する必要があります。

★ Cache:

ユーザーが頻繁にアクセスするURLをキャッシュすることができます。 UGSサーバーは、データベースへの問い合わせを行う前に、キャッシュに目的のURLがあるかどうかをチェックすることができます。

キャッシュが一杯になるとどうなりますか? 使用されていない古いリンクを、より新しい、または人気のあるURLに置き換えることがあります。 私たちのシステムには、Least Recently Used (LRU) キャッシュ退去ポリシーを選択することができます。

★ ロードバランサー:

システムのさまざまな場所で、URL 短縮サーバー、データベース、キャッシュ サーバーの前にロード バランサー レイヤーを追加することができます。 このアプローチでは、LBは入ってくるリクエストをバックエンドサーバー間で均等に分配します。 LB のこのアプローチは実装が簡単である。

問題: サーバーが過負荷の場合、LB はこのアプローチではそのサーバーへの新しいリクエストの送信を停止しない。

★ 持続期間後のリンクの有効期限:

URL が有効期限に達した場合、リンクはどうなるでしょうか。

データストアで検索し、それらを削除することができます。 ここでの問題は、期限切れのリンクを検索してデータ ストアから削除することを選択した場合、データベースに大きな負担がかかることです。

別の方法をとることも可能です。 期限切れのリンクを定期的にゆっくりと削除すればよいのです。 一部のデッド リンクが長生きしても、ユーザーに返すべきではありません。

ユーザーが期限切れのリンクにアクセスしようとすると、リンクを削除してユーザーにエラーを返すことができます。 定期的なクリーンアップ プロセスを実行して、データベースから期限切れのリンクを削除することができます。

リンクを削除した後、再利用のためにデータベースに戻すことができます。

★ セキュリティ:

データベース内の各 URL にアクセス タイプ (public/private) を保存することができます。 ユーザーがアクセス権のない URL にアクセスしようとした場合、システムはエラー (HTTP 401) を送り返すことができます。