URL短縮サービスの設計

要件と規模の見積もり

まず何を作るかを固定します。機能要件は、(1)長いURLを渡すと短縮URLを返す、(2)短縮URLへアクセスすると元URLへリダイレクトする、の2つが中核です。付随して、任意の別名（カスタム別名）、有効期限、クリック数の計測を挙げますが、面接では中核2機能に集中し残りは「あれば良い」に落とします。非機能要件は、リダイレクトの低レイテンシ（体感を損なわない数十ミリ秒以内）、高可用性（リダイレクトが落ちるとリンクが全滅するため書き込みより読み取りの可用性が重い）、そして鍵の一意性です。

規模をフェルミ推定で桁まで詰めます。前提を「新規短縮が1日3,000万件、読み書き比は1対100」と置きます。書き込みQPSは 3,000万 ÷ 86,400秒 ≈ 350 URL/秒、平均に対しピークはその2〜3倍とみて約700〜1,000/秒。読み取りは比から約35,000リダイレクト/秒、ピークで約7万/秒です。この「読み取りが2桁上」という非対称性が設計全体を決めます。

ストレージも見積もります。1レコードは短縮鍵・元URL・作成日時・所有者などでおよそ500バイト。年間の新規は 3,000万 × 365 ≈ 110億件、7年で約770億件。容量は 770億 × 500バイト ≈ 38.5TB です。これは単一ノードに収まらず、水平分割（シャーディング）が前提になります。帯域は、書き込みが 350件/秒 × 500バイト ≈ 175KB/秒 と軽微。読み取りはリダイレクト応答自体は小さいものの、35,000/秒 × 数百バイト で数十MB/秒規模になり、ここでもキャッシュとレプリカで origin を守る必要が見えます。

大枠の設計

APIは2本に絞ります。作成は POST /api/v1/urls（本文に元URLと任意の別名・有効期限、応答に短縮鍵）。取得は GET /{key} で、302を返し Location ヘッダに元URLを載せます。データモデルは主キーを短縮鍵とする1テーブルが基本です。

全体構成は次の流れです。クライアントからのリクエストは、まずロードバランサで複数のアプリサーバーへ分散します（L4ロードバランサの内部の仕組みが土台です）。読み取り経路はキャッシュ優先で、外し（ミス）たときだけデータストアを引きます。書き込み経路は鍵採番サービスを経てストアへ書き込みます。地理的に離れたユーザーの初回アクセスは物理距離が支配的なので、静的な短縮ドメインをCDNのエッジに載せ、エッジでリダイレクトを完結させる構成も有効です。

リダイレクト処理の擬似コードは次のとおりです。読み取り偏重なので、キャッシュミス時のみ origin を叩く形が中心になります。

def redirect(key):
    url = cache.get(key)           # まずキャッシュ
    if url is None:
        url = db.get(key)          # ミスならストア（リードレプリカ）
        if url is None:
            return http_404()
        cache.set(key, url, ttl=3600)  # 次回のために載せる
    log_click_async(key)           # 計測は非同期で本流を止めない
    return http_302(location=url)

計測（log_click_async）を同期でやるとリダイレクトのレイテンシに計測の書き込みが乗ってしまうため、メッセージキューへ流して非同期集計にするのが定石です（メッセージキューの配信保証で at-least-once の重複をどう吸収するかを設計します）。

主要コンポーネントの深掘り

最重要の設計判断は短縮鍵の生成方式です。3方式を比較します。

まず鍵長を決めます。base62（0-9A-Za-z の62文字）で n 桁は 62 の n 乗を表現でき、62^7 ≈ 3.52兆。7年で約770億件という推定に対し、7桁で2桁分の余裕があります。6桁だと 62^6 ≈ 568億 で7年分（770億）に届かないため、7桁が最小の妥当解です。

本命は分散カウンタのbase62化です。単調増加する64ビット整数IDをbase62へ基数変換するだけで、衝突チェックが一切要らないのが決定的な利点です。難所は「採番をどう分散するか」で、単一カウンタは単一障害点かつ書き込みの直列化ボトルネックになります。定番は、採番専用サービスが各アプリサーバーへID範囲（例: 1,000個ずつ）をブロック単位で貸し出す方式です。各サーバーは貸与範囲内をローカルで消費するので、採番のためのネットワーク往復が1,000回に1回に減り、採番サービスが一時的に落ちても手持ちの範囲で採番を継続できます。連番が透ける弱点は、貸与ブロックの順序をシャッフルする、あるいはIDに可逆変換を1段かませて隠します。

ハッシュ切り詰めは、元URLのSHA-256などを取り先頭7桁分をbase62化する方式。推測されにくく同一URLが同じ鍵になる利点がある一方、鍵空間を切り詰める以上バースデーパラドックスにより衝突は避けられず、書き込みのたびに「既存鍵と衝突していないか」の読み取りが1回増えます。衝突時はソルトを足して再ハッシュするリトライが要り、書き込み経路が重くなります。

事前生成プールは、オフラインのバッチで未使用鍵を大量に作り置きし、書き込み時はプールから1つ払い出すだけにする方式。書き込み経路が最速になる反面、プールの枯渇監視と、同じ鍵を2人へ払い出さないための排他制御（在庫テーブルへの原子的な取得）が新たな運用対象になります。

次にリダイレクトのステータスコードです。302（Found、一時的リダイレクト）と301（Moved Permanently）で挙動が根本的に異なります。301はブラウザが恒久的な移動とみなしローカルにキャッシュするため、2回目以降はサーバーへリクエストが来ません。サーバー負荷は激減しますが、クリック数の計測ができなくなり、後から転送先を差し替えられなくなります。302はキャッシュされず毎回サーバーを経由するので、計測・差し替え・失効制御がすべて効きます。URL短縮サービスは計測が価値の一部なので既定は302、負荷削減を計測より優先する用途に限って301を選ぶ、という判断になります。

読み取り偏重を捌く要はキャッシュです。人気リンクへのアクセスは一部の鍵に集中する（ロングテールかつホットスポットあり）ため、LRUなどで追い出す方式のキャッシュがヒット率高く効きます。ホット鍵をキャッシュで受け止めれば origin のQPSは1桁以上下がります。TTLは失効・差し替えの反映遅延とのトレードオフで、数十分〜1時間程度から調整します。

ボトルネックとトレードオフ

横にスクロール

スケール時に最初に詰まるのは読み取りです。数万リダイレクト/秒を単一ストアで受けるのは非現実的なので、(1)前段キャッシュでヒットを吸収し、(2)ストアはリードレプリカを増やして読み取りを水平に広げます。レプリケーションは非同期が基本で、直後の読み取りが古いレプリカに当たると404を返しうる複製遅延（レプリカラグ）を許容します。URL短縮では「作成直後の1秒未満だけ稀に見えない」程度は実害が小さく、可用性と読み取りスループットを優先して結果整合を選ぶのが妥当です。ここはCAP定理の可用性側に倒す判断で、詳細はレプリケーションとシャーディングを参照してください。

書き込みとストレージのスケールは、38.5TBという推定からシャーディングが避けられません。分割キーは短縮鍵とし、鍵のハッシュでシャードを決めます。単純な「シャード数での剰余」はノード追加時にほぼ全鍵の再配置を招くため、再配置量を最小化するコンシステントハッシュを用います。分割設計の全体像はシャーディング戦略にまとまっています。

ストア自体は主キー（短縮鍵）による点引きが処理のほぼ全てで、範囲検索や結合をほとんど使いません。これはKey-Valueストアの得意分野そのものです。RDBでも実現できますが、単純なKVアクセスパターンに対しては、水平分割と高い読み取りスループットを素直に得られるKVストアが適合します。書き込みが多い設計では、追記中心で書き込みに強いLSMツリー系のストレージエンジンが選択肢になります。

残る論点は有効期限と削除です。expire_at を過ぎた鍵は、遅延削除（アクセス時に失効判定して404）と、バッチによる定期回収を併用します。即時に物理削除しないのは、削除I/Oを本流から外し、失効判定は安価な比較で済ませられるためです。可用性・整合性・スループットのどれを優先するかは要件で変わりますが、URL短縮は「読み取りの可用性と低レイテンシ最優先、整合性は結果整合で妥協」という重心が定石だと押さえておくとよいでしょう。より広いデータ基盤の設計はデータベース、配信最適化はネットワークの各トピックも参照してください。