面接の問題でよくあるとされる。TinyURLのシステムデザインを考えていきます
仕様
URLを短縮変換する機能
短縮されたURLにアクセスして元のURLにリダイレクトする機能
アクセス数をだいたい見積もってみる
短縮変換 1回/1分
短縮URLにアクセス 100回/1分
機能をもう少し具体的にする
URLを短縮する機能とは元のURLを example.com/xxxxxxx のようにユニークなURLにマッピングすることである
URLの短縮についてざっとアーキテクチャを書いてみる
LB
アプリサーバーが水平スケールすることを見越して置いとく
アプリサーバー
example.com/xxxxxxx のxxxxxxxの部分を生成する。
Database
RDBを使用する。NoSQLにすれば水平スケールは容易になるが、今回ぐらいのアクセスならRDBでも全く問題なく捌けると判断
また今後アカウントの作成やアドミン機能での短縮URLの変更とかを考えたりするとRDBの方が簡単に運用できそうだと思った
短縮のURLの生成について
URLの長さ
短縮URLはMD5を使おうと思う。
8文字あれば32^8 = だいたい1兆通りくらいのURLを網羅できるので今回のケースでは十分そう。
ロジックについて
アプリサーバーにて元のURLから短縮後の文字列をhashの先頭8文字を取り出す。それをDatabaseに保存する
スキーマについて
多分こんな感じ
重複した場合にどうするか
テーブル上のhashにunique keyを貼っておけば後からきたhashにてついてはエラーが起きるのでリトライじにその時点でのunixタイムを加えた元のURLでもう一度hashを生成し直す。
元のURL複数に対して違うURLが生成されるが使用上問題ない気がする
短縮URLのリダイレクトについて
アプリサーバーがDBを参照してリダイレクト先のURLにユーザーをリダイレクトさせる。
スケールについて
もし短縮URLがtwitterでバズったらどうするか
想定1000回/秒 とするとその都度SQLにアクセスしてたら少し心もとない。アプリサーバーは水平スケールするとしてもDBサーバーがボトルネックとなりそう。
のでRedisを用意してアプリサーバーにはRedisを参照させるようにする。
Redisにはアクセス数の昇順に1000件程度保存させとけば良さそうな気はしている。(人気のURLは多いがロングテールなURLは都度DBに問い合わせても大丈夫な気がするので )
サイトそのものが人気になり短縮URLをたくさん発行する時
更新系の負荷につられて参照の遅延を防ぐため更新のDBを分ける。参照はSlaveを参照するため短縮URLに適応に少し時間をとった方が安全ではある。
URLの重複を完全に防ぐ
DBにオフラインで一意なURLを発行しておく
UnUsedHasTableとUsedHashTableを用意してアプリケーションサーバーはUnUsedHashTableをUsedHashTableに移動させて、元のURLとの対応するテーブルを更新するようにする。
ユーザーに返却するのはUnusedHashTableのUIDなので必ず一意なURLを提供することができDBチェックがいらなくなる。
その代わりUIDをオフラインで発行するサービスが必要になる。