短縮URLサービス ── ハッシュ・一意性・スケール

扱うCS概念：ハッシュ関数、Base変換、KVストア、一貫性ハッシュ、冗長化

---

この章で何ができるようになるか：短縮URLサービスの設計で問われる選択肢（ハッシュ vs. カウンター、Base62 の理由、DB 選定、キャッシュ戦略）を根拠を持って説明できるようになる。

---

問題設定

https://www.example.com/articles/how-to-design-distributed-systems-2026 のような長いURLを https://sho.rt/aB3xQ に短縮するサービスを設計せよ。

要件の整理（面接でまず行うべき確認）

機能要件：
  - 長いURL → 短いURLへの変換（Write）
  - 短いURL → 長いURLへのリダイレクト（Read）
  - カスタムエイリアス（オプション）
  - 有効期限設定（オプション）

非機能要件：
  - 1日1億件の短縮リクエスト
  - 10億件の総URL数（5年間）
  - Read:Write = 100:1（リダイレクトが圧倒的多数）
  - レイテンシ：リダイレクトは100ms以下
  - 高可用性（99.9%以上）

ここまで聞いた時点で、どんな技術的判断が必要かが見えてくる。

---

素朴な解法とその限界

案1：MD5 ハッシュ

最初に思いつくのは MD5 だろう。URL を MD5 にかけると 128bit = 32文字の16進数が返ってくる。

import hashlib

def shorten(url: str) -> str:
    return hashlib.md5(url.encode()).hexdigest()[:7]
    # → "d415ab3" のような7文字

問題1：衝突

MD5 の最初の7文字だけ使うと、衝突確率が跳ね上がる。7文字（16進数）= $16^7 = 268,435,456$ 通り。10億URLに対して衝突が多発する。

問題2：同じURLに複数の短縮URLが作られない

MD5 は決定的（deterministic）なので、同じ URL を短縮すると毎回同じ値になる。これは UX 上の問題（ユーザーごとに異なる短縮URL を発行できない）と、攻撃者による URL 推測（入力URLがわかれば短縮URLが割れる）というセキュリティ問題を生む。

---

案2：ランダム文字列

import secrets
import string

def shorten() -> str:
    chars = string.ascii_letters + string.digits  # Base62
    return ''.join(secrets.choice(chars) for _ in range(7))

ランダムは予測不可能という点で改善された。しかし：

問題：一意性の保証

DB に保存する前に「既に使われていないか」を確認しなければならない。高負荷時にはこの確認→保存のあいだに別リクエストが同じ値を使ってしまう競合（race condition）が起きる。

---

CS概念の適用

Base62 を使う理由

短縮URL に求めるのは「短くて、URL に使えて、人が読み書きしやすい」文字セットだ。

Base16（hex）：0-9, a-f = 16種  → 長くなりすぎる
Base62        ：0-9, a-z, A-Z = 62種 → バランスが良い
Base64        ：Base62 + +/ = URL に使えない文字が含まれる

7文字 Base62 で表現できる空間：

$$62^7 = 3,521,614,606,208 \approx 3.5 \text{ 兆}$$

10億URLに対して十分な空間がある。

カウンター方式（推奨アプローチ）

ランダム生成の競合問題を解決する最もシンプルな方法は、単調増加するIDを Base62 に変換することだ。

def to_base62(n: int) -> str:
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    result = []
    while n > 0:
        result.append(chars[n % 62])
        n //= 62
    return ''.join(reversed(result)) or "0"

# ID = 1000000 → "4c92"（4文字）
# ID = 3521614606207 → "zzzzzzz"（7文字）

ID の生成は以下の3つのアプローチがある。

アプローチA：DB の auto-increment

CREATE TABLE urls (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    long_url TEXT NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    expires_at TIMESTAMP,
    INDEX idx_long_url (long_url(255))
);

• ✅ シンプル
• ❌ DB が単一障害点（SPOF）になる
• ❌ 水平スケールが難しい

アプローチB：分散IDジェネレーター（Snowflake方式）

Twitter が OSS 化した Snowflake アルゴリズムは、64bit整数を以下の構造で生成する。

| 1bit  | 41bit         | 10bit     | 12bit      |
| 符号  | タイムスタンプ | マシンID  | シーケンス |

class SnowflakeID:
    EPOCH = 1704067200000  # 2024-01-01 00:00:00 UTC

    def __init__(self, machine_id: int):
        self.machine_id = machine_id & 0x3FF  # 10bit
        self.sequence = 0
        self.last_timestamp = -1

    def generate(self) -> int:
        ts = int(time.time() * 1000) - self.EPOCH
        if ts == self.last_timestamp:
            self.sequence = (self.sequence + 1) & 0xFFF  # 12bit
            if self.sequence == 0:
                # 同じミリ秒に4096件を超えた → 次のミリ秒まで待つ
                while ts <= self.last_timestamp:
                    ts = int(time.time() * 1000) - self.EPOCH
        else:
            self.sequence = 0
        self.last_timestamp = ts
        return (ts << 22) | (self.machine_id << 12) | self.sequence

• ✅ 分散環境でも一意（マシンIDで名前空間が分かれる）
• ✅ 単調増加（時系列順にソートできる）
• ✅ DB 不要で高速
• ❌ マシンID の管理が必要（ZooKeeper などで調整）

アプローチC：レンジ分割（DB負荷を下げる中間策）

「IDサーバー」を2台用意し、それぞれ奇数・偶数のIDを払い出す。

Server1: 1, 3, 5, 7, ... (auto_increment_increment=2, auto_increment_offset=1)
Server2: 2, 4, 6, 8, ... (auto_increment_increment=2, auto_increment_offset=2)

完全分散ほど複雑にならず、単一障害点も排除できる。

---

アーキテクチャ全体

graph TD
    Client --> LB[ロードバランサー]
    LB --> API1[APIサーバー 1]
    LB --> API2[APIサーバー 2]
    LB --> API3[APIサーバー 3]

    API1 --> Cache[(Redis キャッシュ)]
    API2 --> Cache
    API3 --> Cache

    API1 --> DB[(MySQL / DynamoDB)]
    API2 --> DB
    API3 --> DB

    API1 --> IDGen[Snowflake IDサーバー]
    API2 --> IDGen
    API3 --> IDGen

    Cache -.->|キャッシュミス時| DB

Write フロー

1. クライアントが長URLを送信
2. 長URLが既に DB に存在するか確認（オプション：重複排除）
3. Snowflake IDを取得
4. IDをBase62変換 → 短縮キー
5. DB に（短縮キー, 長URL, 有効期限）を保存
6. 短縮URLをレスポンス

Read フロー（リダイレクト）

1. クライアントが短縮URLにアクセス
2. APIサーバーがキャッシュを確認
3. キャッシュヒット → 長URLにリダイレクト（301 or 302）
4. キャッシュミス → DBから取得 → キャッシュに書き込み → リダイレクト

301 vs 302 の選択

	301 Permanent	302 Found（Temporary）
ブラウザキャッシュ	✅ される（次回はサーバーに問い合わせない）	❌ されない
サーバー負荷	低い（2回目以降はブラウザが直接飛ぶ）	高い（毎回サーバーを経由）
クリック計測	❌ 計測できない	✅ 毎回計測できる
ユーザー体験	高速	やや遅い

分析機能が必要なら 302、そうでなければ 301。

---

データベース選定の考え方

graph LR
    A{データの性質} --> B[スキーマが固定的<br/>JOINが必要]
    A --> C[スキーマレス<br/>KVアクセスがメイン]
    B --> D[MySQL / PostgreSQL]
    C --> E[DynamoDB / Cassandra]
    D --> F[Read レプリカで<br/>スケールアウト]
    E --> G[シャーディングが<br/>ネイティブ対応]

短縮URLのユースケースは：

• アクセスパターンが単純（id → url の KV 参照）
• JOINが不要
• 書き込みより読み込みが100倍多い
• グローバルスケールが将来的に必要

これらの条件では DynamoDB や Cassandra のような NoSQL KV ストアが適している。

RDB を選ぶ場合は、Read レプリカを増やすことで読み込みスケールを確保するのが定石だ。

---

キャッシュ戦略

Read:Write = 100:1 の状況では、キャッシュの効果が絶大だ。

エビクションポリシーの選択

LRU（Least Recently Used）：最も長く使われていないものを削除
  → 短縮URLの典型的アクセスパターンに適合（バズったURLが一時的に大量アクセス）

LFU（Least Frequently Used）：最もアクセス頻度が低いものを削除
  → 長期間人気のあるURLを保持するのに向く

TTL：時間で自動削除
  → 有効期限付き短縮URLとの相性が良い

一般的な短縮URLサービスでは LRU + TTL の組み合わせ が使われる。

キャッシュサイズの見積もり

1日のリクエスト：1億件
20%のURLが80%のトラフィックを処理（冪乗則）
キャッシュ対象：1億 × 20% = 2000万件
1エントリのサイズ：~500バイト（URL + メタデータ）
必要キャッシュ：2000万 × 500B = 10GB

10GB は Redis 1インスタンスで十分に収まる。

---

実際のサービスでの実装例

Bitly

• カスタムドメイン対応のため、{ドメイン, パス} → 長URL のマッピングを持つ
• MySQL を中心とした構成（歴史的経緯）
• 2019年頃から Google Cloud（GCP）インフラに移行し、リンクデータを MySQL から Cloud Bigtable へ移行

TinyURL

• 具体的な内部実装は公開されていないが、一般的にはシーケンシャル ID の Base 変換や分散 ID ジェネレーターが使われていると推測されている

ℹ️ ソース注記: TinyURL の具体的な内部実装に関する公式な技術情報は公開されていません。上記は一般的なシステム設計の文脈での推測です。

Twitter の t.co

• ツイート内の全URLを自動的に短縮
• セキュリティスキャン（フィッシング・マルウェア判定）をリダイレクト前に実施
• 実装上は HTTP 200 + JavaScript（location.replace()）によるクライアントサイドリダイレクトを使用しており、これによりセキュリティチェックをサーバー側で介在させている

---

まとめ

設計判断	推奨選択肢	理由
ID生成	Snowflake方式	分散・単調増加・高速
エンコード	Base62 / 7文字	URL安全・3.5兆通りの空間
DB	DynamoDB / NoSQL	KVアクセス特化・水平スケール
キャッシュ	Redis + LRU + TTL	R:W=100:1の偏りを活用
リダイレクト	302（分析あり）/ 301（なし）	要件次第で使い分け
ID払出	専用IDサーバー2台	SPOF排除・シンプル

次章では、Amazon S3 が 1 日に数兆リクエストを処理するために、オブジェクトストレージとしてどんな設計をしているかを見ていく。

＋ － ⟳ ✕