URL短縮サービスを設計しよう！ ─ ハッシュ設計とリダイレクトの仕組みを学ぶ！

URL短縮サービスの設計

概要

この記事は、「システム設計の面接試験」（Alex Xu 著）を読み学習した内容を個人学習用にまとめ直したものです。

本記事では、TinyURL のような URL短縮サービス の設計について解説します。

URL短縮サービスは、長いURLを短いURLに変換し、その短いURLへのアクセスを元のURLへリダイレクトする、一見シンプルなサービスです。しかし大規模に設計しようとすると、短縮URLの生成方法（ハッシュ・衝突回避・Base62変換）、リダイレクトの仕組み（301と302の使い分け）、読み取り負荷を支えるキャッシュ設計など、多くの論点が現れます。本記事ではそれらを順に整理していきます。

設計の要件

本記事では、Alex Xu の設計演習にならい、次の2つの機能を提供するURL短縮サービスを設計する。

• URL短縮: 長いURLが与えられたら、それをもとにずっと短いURLを生成して返す
• URLリダイレクト: 短縮URLへのアクセスが与えられたら、元の長いURLへリダイレクトする

そのうえで、以下の制約・前提のもとで設計する。

• 書き込み規模: 1日あたり 1億件（100 million）のURLが新たに生成される
• 短さ優先: 短縮URLは可能な限り短くする
• 使用可能な文字: 短縮URLには数字（0-9）とアルファベットの大文字・小文字（a-z・A-Z）を組み合わせて使える
• 削除・更新なし: 一度生成した短縮URLの削除・更新は行わない（新規生成と参照のみを対象とする）

最後に、実運用に耐えるサービスとするため、次の非機能要件も満たす必要がある。

• 高可用性（availability）: 一部に障害が起きてもサービスが応答し続ける
• スケーラビリティ（scalability）: トラフィックの増加に応じて負荷をさばける
• フォールトレランス（fault tolerance）: 障害が発生しても機能し続ける

概算見積もり

上記の要件、とくに「1日あたり1億件」を起点に、システムが支えるべき負荷とデータ量を概算しておく。設計に入る前に、どこにボトルネックが生じうるかを把握するためである。

• 書き込みの量（write QPS）: 1日は 24 × 3600 = 86,400 秒なので、1秒あたりの書き込み回数は 1億 ÷ 86,400秒 ≈ 1,160 件/秒 となる
• 読み込みの量（read QPS）: 短縮URLは一度作られて何度もアクセスされるため、読み込み（リダイレクト）のほうが書き込みよりずっと多い。読み書き比を 10:1 と仮定すると、読み込みは 1,160 × 10 ≈ 11,600 件/秒 になる
• ストレージの量: サービスを10年間運用すると、生成されるURLは 1億件/日 × 365日 × 10年 = 3,650億 件。1件あたり平均100バイトとすると、必要なストレージは 3,650億 件 × 100バイト = 36.5 TB と見積もれる

以上を整理すると次の通りである。

指標	概算値	前提
書き込みQPS	約 1,160 件/秒	1日1億件
読み込みQPS	約 11,600 件/秒	読み書き比 10:1
総レコード数（10年）	約 3,650億 件	1日1億件 × 10年
ストレージ（10年）	約 36.5 TB	1件あたり100バイト

特に読み込みが書き込みの約10倍である点は、以降の設計（リダイレクト経路やキャッシュ）を考えるうえで重要な前提になる。

サービスの構成

URL短縮という機能自体は、クライアント側のライブラリやCLIツールなど、さまざまな形で提供しうる。本記事では以下の構成とする。

• クライアント（ブラウザ）
• URL短縮サービス（HTTPサーバー）: 前述の2機能を REST API として公開する
• ストア: 「短縮URL → 元の長いURL」の対応を保持する

設計の要点

構成が決まったので、ここからは各要素の設計に入る。URL短縮サービスの設計では、主に次の3点が論点になる。本記事ではこれらを順に見ていく。

• APIエンドポイントの設計
• URLリダイレクトの仕組み（301と302の使い分け）
• 短縮URLの生成方法（ハッシュ・衝突回避・Base62変換）

まずは、クライアントとのやり取りの入り口となるAPIから設計する。

APIエンドポイントの設計

URL短縮サービスがクライアントに提供するAPIは、要件の2機能に対応して2つである。ここではREST APIとして設計する。

① URL短縮: 長いURLを渡すと、対応する短縮URLを返す。新しいリソースを作成する操作なので、HTTPメソッドは POST を使う。

POST /api/v1/data/shorten

項目	内容
リクエストボディ	{ "longUrl": "<長いURL>" }
レスポンス	生成された短縮URL（shortUrl）

② URLリダイレクト: 短縮URLへのアクセスを、元の長いURLへリダイレクトする。既存リソースの取得にあたるので、HTTPメソッドは GET を使う。

GET /api/v1/{shortUrl}

項目	内容
パスパラメータ	shortUrl（短縮URLの識別子）
レスポンス	元の長いURL（longUrl）を返し、そのURLへHTTPリダイレクトする

このように、APIは「短縮（POST）」と「リダイレクト（GET）」の2本だけとシンプルである。次は、②のリダイレクトが具体的にどう行われるか（HTTPステータスコード301と302の使い分け）を見ていく。

URLリダイレクトの仕組み

短縮URLにアクセスしたとき、サーバーはどのように元の長いURLへ転送するのか。基本の流れは次の通りである。

1. ユーザーがブラウザで短縮URL（例: https://tinyurl.com/abc123）にアクセスする
2. サーバーは短縮URLから元の長いURLを引き当て、リダイレクトを指示するHTTPレスポンス（ステータスコード 301 または 302）を返す。長いURLはレスポンスの Location ヘッダーに入れる
3. ブラウザは Location ヘッダーの長いURLへ自動的にアクセスし直す

301と302の使い分け

リダイレクトに使うHTTPステータスコードには 301 と 302 があり、性質が異なる。

ステータス	意味	ブラウザの挙動
301（Permanently Moved）	恒久的な移動	リダイレクト先をキャッシュする。以降、同じ短縮URLへのアクセスは短縮サービスを経由せず、直接長いURLへ向かう
302（Temporarily Moved）	一時的な移動	キャッシュしない。以降も毎回短縮サービスを経由してから長いURLへリダイレクトされる

どちらを選ぶかは、何を重視するかによる。

• サーバー負荷を減らしたい → 301: ブラウザがキャッシュするため、2回目以降のアクセスが短縮サービスに届かない。前述の概算のとおり読み込みは書き込みの約10倍と多いため、この負荷軽減効果は大きい
• アクセス解析をしたい → 302: すべてのアクセスが短縮サービスを経由するため、クリック数やクリック元（流入元）を計測しやすい。マーケティング用途では重要になる

つまり、301はパフォーマンス（負荷軽減）、302は分析のしやすさに向く。どちらが正解というものではなく、サービスの目的に応じて選択する。

短縮URLの生成方法

本記事の技術的な中心が、この短縮URLの生成である。短縮URLを https://tinyurl.com/{hashValue} の形とすると、必要なのは長いURLから hashValue を作る関数である。この関数は次の2つを満たす必要がある。

• 1つの長いURLは、1つの hashValue に対応する
• 1つの hashValue からは、元の長いURLを引き当てられる

短縮URLの長さ

まず hashValue の長さを決める。要件より、使える文字は数字（0-9）とアルファベット大小文字（a-z・A-Z）の 62種類 である。長さ n の文字列で表せる組み合わせは 62^n 通りなので、10年間で生成される 約3,650億件（前述の概算）をまかなえる最小の n を求める。

n	表現できるURL数（62^n）
1	62
2	3,844
3	238,328
4	約 1,477万
5	約 9.2億
6	約 568億
7	約 3.5兆

n = 6 では約568億で3,650億件に届かないが、n = 7 では約3.5兆となり十分にまかなえる。したがって短縮URLの長さは7文字とする。

以下、短縮URLを生成する2つの方法（ハッシュ + 衝突解決 と Base62変換）を見ていく。

方法1: ハッシュ + 衝突解決

長いURLを CRC32・MD5・SHA-1 などのハッシュ関数にかけ、その結果を短縮URLとして使う方法である。ただし、これらのハッシュ値は7文字より長いため、先頭7文字だけを取り出す。

実際にどのような値になるかを見ておく。長いURLを https://en.wikipedia.org/wiki/Systems_design としたときの各ハッシュ値は次の通りである（16進数表記）。

ハッシュ関数	ハッシュ値	長さ	先頭7文字
CRC32	5cb54054	8文字	5cb5405
MD5	5a62509a84df9ee03fe1230b9df8b84e	32文字	5a62509
SHA-1	0eeae7916c06853901d9ccbefbfcaf4de57ed85b	40文字	0eeae79

どの関数も出力は7文字より長く、いずれも先頭7文字を切り出せば目的の長さになる。

上の表は16進数（0-9・a-f の16種類）の表記なので、そのまま切り出すと16種類の文字しか使えません。62種類の文字を使い切るには、ハッシュ値を数値として扱い、後述のBase62に変換したうえで先頭7文字を取り出します。ここでは「ハッシュを取って先頭を切る」という考え方の説明に留めます。

問題は、先頭7文字に切り詰めることで別々の長いURLが同じ短縮URLになる「衝突」が起こりうる点である。衝突が起きたときは、次のように解決する。

• 生成した短縮URLがすでにDBに存在するかを調べ、存在すれば（衝突すれば）定義済みの文字列を付け足して再度ハッシュし、衝突しなくなるまで繰り返す
• 毎回DBへ存在確認を行うのはコストが高いため、ブルームフィルタを使って「存在しない」ことを高速に判定し、問い合わせを減らす手もある

ブルームフィルタは、ある要素が集合に含まれるかを少ないメモリで高速に判定するデータ構造です。「含まれない」判定は必ず正しいため、衝突チェックの多くをDBに問い合わせずに済ませられます。

方法2: Base62変換

もう1つは、数を別の基数（進数）で表し直す基数変換を使う方法である。

普段使う10進数は各桁の重みが10のべき乗（1, 10, 100, ...）だが、62進数では62のべき乗（1, 62, 3844, ...）になる。例えば 11157 という数は、62のべき乗を使うと次のように分解できる。

11157 = 2 × 62² + 55 × 62¹ + 59 × 62⁰
      → 各桁の値は [2, 55, 59]

ただし、ここで得られるのは各桁の値（0〜61）までである。55 という値をどの文字で書き表すかは、基数変換そのものからは決まらない。この文字の割り当てまで含めて取り決めたものが Base62 であり、本記事では次の対応を使う。

値	文字
0〜9	0〜9
10〜35	a〜z
36〜61	A〜Z

この対応表に各桁の値を当てはめると、文字列が決まる。

[2, 55, 59]
  → "2TX"   （2 → '2'、55 → 'T'、59 → 'X'）

つまり、10進数で 11157 と書かれる数を Base62 で書き直すと 2TX になる。数そのものが変わるわけではなく、書き表し方だけが変わる（10進数の 255 を16進数で ff と書くのと同じことである）。

この方法では、長いURLに対応づけた一意な数値をBase62で書き表し、それを短縮URLとする。

元の数値が一意であれば書き表したあとの文字列も一意になるため、方法1のような切り詰めが不要で、衝突が原理的に起きないのが大きな利点である。

Base62が決めているのは「数をどう書き表すか」までです。採用するには変換元となる一意な数値が必要ですが、URLは数値ではありません。そのため今回の設計に導入する場合は、まず長いURLを一意な数値へ変換する処理が別途必要になります。

2つの方法の比較

2つの方法にはそれぞれ長所と短所がある。整理すると次の通りである。

観点	ハッシュ + 衝突解決	Base62変換
短縮URLの長さ	固定（7文字）	固定でない（数値が大きくなるほど長くなる）
一意な数値の用意	不要	必要
衝突	起こりうる（解決処理が必要）	起きない（数値が一意なため）
次の短縮URLの推測	されにくい（推測されにくく安全）	数値が連番だと次の値を推測・列挙されやすい

ハッシュ方式は長さが固定で推測されにくい一方、衝突解決のコストがかかる。Base62方式は衝突しないが、一意な数値を用意する仕組みが別途必要になることと、連番の数値を使うと短縮URLが推測されやすいという弱点がある。どちらを採るかは、URLの推測されにくさ（セキュリティ）と実装の単純さのどちらを重視するかで決める。

詳細設計

ここまでで論点は出そろったので、最終的な設計案としてまとめる。

まず短縮URLの生成方式は、Base62変換を採用する。理由は、処理の流れが論理的に単純だからである。ハッシュ方式は「生成 → 存在確認 → 衝突していれば再生成」というループを持ち、何回繰り返せば終わるかが事前に決まらない。一方Base62方式は、一意な数値さえ用意できれば「採番 → 変換 → 保存」と一方向に進み、分岐もリトライも発生しない。1日1億件を書き込む前提では、この単純さがそのまま実装と運用のしやすさになる。

その代わり、短縮URLの長さが固定にならないことと、採番した数値が連番だと次の短縮URLを推測されやすいことは受け入れる。推測されては困る用途では、ハッシュ方式を選ぶか、採番する数値に連番以外の方式を使うことになる。

データモデル

ストアに保存するのは、短縮URLと長いURLの対応だけである。要件より削除・更新は行わないため、レコードは追加されるのみとなる。

カラム	内容
id	主キー。採番した一意な数値
shortURL	短縮URL（例: 2TX）。id をBase62で書き表したもの
longURL	元の長いURL

shortURL と id はBase62で相互に変換できるため、リダイレクト時は受け取った短縮URLを10進数に戻して id を求め、主キーで検索できる。shortURL を検索条件にする必要はない。

URL短縮の流れ

長いURLを受け取ってから短縮URLを返すまでの流れは次の通りである。変換に入る前に、その長いURLがすでに登録済みでないかを確認する。

1. 長いURLを受け取る
2. DBに同じ長いURLが登録済みかを確認する
3. 登録済みであれば、その短縮URLをそのまま返す（新たに採番しない）
4. 未登録であれば、一意な数値（ID）を採番する
5. そのIDをBase62で書き表し、短縮URLとする
6. id・shortURL・longURL をDBに保存し、短縮URLを返す

手順2を挟むのは、同じ長いURLに対して短縮URLがいくつも作られるのを防ぐためである。

手順4の「一意な数値の採番」は、前回の記事「auto_incrementが通用しない!?分散システムのユニークIDジェネレータを設計する！」で扱ったSnowflake方式などがそのまま使えます。分散環境で一意なIDを採番する方法については、そちらを参照してください。

URLリダイレクトの流れ

短縮URLへのアクセスを受けてから元のURLへ転送するまでの構成は次の通りである。## サービスの構成 で示した最小構成に、ロードバランサとキャッシュを加えた形になる。

1. ブラウザが短縮URLにアクセスすると、ロードバランサがいずれかのWebサーバーに振り分ける
2. Webサーバーはまずキャッシュに問い合わせ、あればその longURL を使う
3. なければDBから longURL を取得し、次回に備えてキャッシュに載せる
4. Location ヘッダーに longURL を入れ、301または302で応答する
5. DBにも存在しない場合は、不正な短縮URLとして扱う

キャッシュを置くのは、概算見積もりの通り読み込みが書き込みの約10倍（約11,600 QPS）あるためである。さらにこのサービスは要件上削除・更新を行わないので、一度キャッシュに載せた対応が古くなることがない。キャッシュの無効化を考えなくてよい点で、相性がよい。

ロードバランサを置くのは、非機能要件の高可用性とフォールトレランスのためである。Webサーバーが1台だけだと、そこが落ちた時点でサービス全体が止まる。複数台に増やして前段で振り分ければ、1台が落ちても残りで応答を続けられる。台数を増やして負荷をさばくスケーラビリティの入り口にもなる。

まとめ

URL短縮サービスの設計で掲げた「要件」と、それに応えた「設計」を整理する。

要件	設計上の対応
URL短縮とURLリダイレクトの2機能	短縮は POST、リダイレクトは GET の2エンドポイント
短縮URLは可能な限り短く / 使える文字は62種類	長さ7文字（62^7 ≈ 3.5兆 で10年分の約3,650億件をまかなえる）
1日1億件の書き込み（読み込みはその約10倍）	リダイレクト経路へのキャッシュの配置
削除・更新を行わない	追加のみのデータモデルと、無効化不要なキャッシュ運用
高可用性・フォールトレランス	Webサーバーの複数台構成と前段のロードバランサ

そのうえで、設計の中心となる論点は次の2つである。

• リダイレクトの方式: 301はブラウザがキャッシュするためサーバー負荷を減らせ、302は全アクセスが経由するためクリック計測ができる。目的に応じて選ぶ
• 短縮URLの生成方法: 次の2方式がある。推測されにくさを取るならハッシュ方式、処理の単純さを取るならBase62方式を選ぶ
  • ハッシュ + 衝突解決 → ハッシュ値の先頭7文字を使う。切り詰めにより衝突しうるため再ハッシュによる解決が必要で、存在確認の負荷はブルームフィルタで抑えられる
  • Base62変換 → 数を62文字で書き表す表現方法。一意な数値さえ用意できれば衝突は起きないが、その採番の仕組みが別途必要になる

参考文献

この記事は以下の情報を参考にして執筆しました。

• 「システム設計の面接試験」（Alex Xu 著 / インプレス）