ストーリー

要件の整理

機能要件

interface URLShortenerRequirements {
  functional: {
    shortenURL: "長いURLを短いURLに変換する";
    redirect: "短いURLにアクセスすると元のURLにリダイレクト";
    customAlias: "カスタムエイリアスを指定可能（任意）";
    expiration: "有効期限を設定可能（任意）";
    analytics: "クリック数等の分析データ";
  };
  nonFunctional: {
    availability: "99.99%";
    redirectLatency: "p99 < 100ms";
    shortURLLength: "できるだけ短く（7文字程度）";
    scale: "1日1億リダイレクト";
  };
}

規模の見積もり

const URL_SHORTENER_SCALE = {
  // 書き込み: 1日100万URL作成
  writePerDay: 1_000_000,
  writeQPS: Math.ceil(1_000_000 / 86400), // ~12 QPS

  // 読み取り: 読み書き比率100:1
  readPerDay: 100_000_000,
  readQPS: Math.ceil(100_000_000 / 86400), // ~1157 QPS
  peakReadQPS: 1157 * 3,                    // ~3471 QPS

  // ストレージ: 1レコード500B x 1日100万 x 365日 x 10年
  storagePerRecord: 500,    // bytes
  total10Years: "1.8TB",

  // キャッシュ: 80/20ルール（20%のURLが80%のトラフィック）
  dailyCacheSize: "100_000_000 * 0.2 * 500B ≈ 10GB",
};

ハイレベル設計

クライアント
  │
  ▼
┌─────────────┐
│ ロードバランサー │
└──────┬──────┘
       │
       ▼
┌──────────────┐     ┌───────────┐
│ Webサーバー群  │────→│  キャッシュ  │
└──────┬───────┘     │  (Redis)   │
       │             └─────┬─────┘
       ▼                   │
┌──────────────┐          │
│  ID生成サービス │          │ キャッシュミス時
└──────┬───────┘          ▼
       │          ┌───────────┐
       └─────────→│ データベース  │
                  └───────────┘

詳細設計

短縮URLの生成アルゴリズム

// アプローチ1: Base62エンコーディング
class Base62Encoder {
  private readonly chars =
    '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';

  encode(id: bigint): string {
    let result = '';
    while (id > 0n) {
      result = this.chars[Number(id % 62n)] + result;
      id = id / 62n;
    }
    return result.padStart(7, '0');
  }

  // 62^7 = 約3.5兆通り → 十分な空間
  readonly capacity = 62n ** 7n; // 3,521,614,606,208
}

// アプローチ2: ハッシュ + 衝突解決
class HashBasedShortener {
  shorten(longURL: string): string {
    const hash = md5(longURL);           // 128bit hash
    const shortKey = base62(hash).slice(0, 7); // 先頭7文字
    // 衝突が発生したら末尾に追加文字列を付けてリハッシュ
    return shortKey;
  }
}

// アプローチ3: 分散ID生成器（推奨）
class DistributedIDGenerator {
  // Snowflake方式: タイムスタンプ + ワーカーID + シーケンス
  // 衝突なし、ソート可能、分散環境で一意
  generate(): bigint {
    const timestamp = BigInt(Date.now()) << 22n;
    const workerId = BigInt(this.workerId) << 12n;
    const sequence = BigInt(this.nextSequence());
    return timestamp | workerId | sequence;
  }
}

リダイレクトの最適化

// リダイレクト処理（p99 < 100ms を目指す）
class RedirectService {
  constructor(
    private cache: RedisClient,
    private db: Database,
  ) {}

  async redirect(shortKey: string): Promise<string | null> {
    // 1. キャッシュをチェック（1-2ms）
    const cached = await this.cache.get(`url:${shortKey}`);
    if (cached) {
      this.recordAnalytics(shortKey); // 非同期で記録
      return cached;
    }

    // 2. キャッシュミス → DBから取得（10-20ms）
    const record = await this.db.findByShortKey(shortKey);
    if (!record || record.isExpired()) {
      return null;
    }

    // 3. キャッシュに格納（次回から高速）
    await this.cache.set(`url:${shortKey}`, record.longURL, 'EX', 86400);

    this.recordAnalytics(shortKey);
    return record.longURL;
  }

  // 301 vs 302
  // 301 Permanent: ブラウザがキャッシュ → サーバー負荷減、分析不可
  // 302 Temporary: 毎回サーバーに来る → 分析可能、負荷増
  readonly statusCode = 302; // 分析のため302を選択
}

データベース設計

// URLマッピングテーブル
interface URLMapping {
  id: bigint;           // 主キー（自動採番またはSnowflake）
  shortKey: string;     // 短縮キー（インデックス、UNIQUE）
  longURL: string;      // 元のURL
  userId?: string;      // 作成者（任意）
  createdAt: Date;
  expiresAt?: Date;     // 有効期限（任意）
  clickCount: number;   // クリック数
}

// パーティショニング戦略
// shortKeyの先頭文字でレンジパーティション
// → 均等に分散され、特定キーの検索が効率的

トレードオフの整理

まとめ

チェックリスト

• URL短縮の規模見積もりができた
• 短縮キーの生成アルゴリズムを3つ比較できた
• リダイレクトの高速化戦略を理解した
• 301 vs 302のトレードオフを説明できる

次のステップへ

次は「リアルタイムチャットシステムの設計」を学びます。双方向通信、メッセージの配信保証、オンラインステータスなど、異なる設計課題に取り組みましょう。

推定読了時間: 30分