設計問題: URL短縮サービス — bit.ly を設計する

# POST /api/v1/urls — URL短縮
# Request:
#   { "original_url": "https://www.example.com/very/long/path" }
# Response:
#   { "short_url": "https://bit.ly/abc1234", "expires_at": "2029-06-01T00:00:00Z" }
 
# GET /:short_code — リダイレクト
# Response: 302 Redirect to original_url
 
# GET /api/v1/urls/:short_code/stats — 統計取得
# Response: { "short_code": "abc1234", "click_count": 12345, "created_at": "..." }

# app/models/short_url.rb
class ShortUrl < ApplicationRecord
  validates :original_url, presence: true
  validates :short_code,   presence: true, uniqueness: true
  validates :expires_at,   presence: true
 
  scope :active,  -> { where('expires_at > ?', Time.current) }
  scope :expired, -> { where('expires_at <= ?', Time.current) }
 
  def expired?
    expires_at < Time.current
  end
end
 
# app/controllers/api/v1/urls_controller.rb
class Api::V1::UrlsController < ApplicationController
  before_action :authenticate_api_key!
  before_action :check_rate_limit!
 
  def create
    result = UrlShortenerService.call(
      original_url: params[:original_url],
      user_id: current_user.id
    )
    render json: result, status: :created
  rescue UrlShortenerService::InvalidUrlError => e
    render json: { error: e.message }, status: :unprocessable_entity
  end
end
 
# app/controllers/redirect_controller.rb
class RedirectController < ApplicationController
  def show
    original_url = UrlResolverService.resolve(params[:short_code])
    ClickTrackingJob.perform_later(params[:short_code])
    redirect_to original_url, status: :found, allow_other_host: true
  rescue UrlResolverService::NotFoundError
    render file: 'public/404.html', status: :not_found
  rescue UrlResolverService::ExpiredError
    render file: 'public/410.html', status: :gone
  end
end

def generate_by_hash(url)
  Digest::MD5.hexdigest(url)[0, 7]
end
 
# 問題点:
# 1. 同じURLから常に同じコードが生成される
#    → 2人が同じURLを短縮すると同じコードになり、統計が混在する
# 2. 衝突率: 7文字(16進)では 16^7 = 2.68億パターンしかない
#    → 100Mレコードで衝突が起きる確率が無視できない

# app/services/base62_encoder.rb
class Base62Encoder
  CHARS = ('0'..'9').to_a + ('a'..'z').to_a + ('A'..'Z').to_a
  BASE  = CHARS.length  # 62
 
  def self.encode(num)
    return CHARS[0] if num == 0
 
    result = []
    while num > 0
      result.unshift(CHARS[num % BASE])
      num /= BASE
    end
    result.join
  end
 
  def self.decode(str)
    str.chars.reduce(0) do |acc, char|
      acc * BASE + CHARS.index(char)
    end
  end
end
 
# Base62Encoder.encode(1)       #=> "1"
# Base62Encoder.encode(62)      #=> "10"
# Base62Encoder.encode(999999)  #=> "4c91"

# app/services/snowflake_id_generator.rb
# 41bit:タイムスタンプ | 10bit:ノードID | 12bit:シーケンス
class SnowflakeIdGenerator
  EPOCH     = 1_704_067_200_000  # 2024-01-01 00:00:00 UTC (ms)
  NODE_BITS = 10
  SEQ_BITS  = 12
  MAX_SEQ   = (1 << SEQ_BITS) - 1   # 4095
  MAX_NODE  = (1 << NODE_BITS) - 1  # 1023
 
  def initialize(node_id)
    raise ArgumentError unless (0..MAX_NODE).cover?(node_id)
    @node_id  = node_id
    @sequence = 0
    @last_ts  = -1
    @mutex    = Mutex.new
  end
 
  def next_id
    @mutex.synchronize do
      ts = current_ms
      if ts == @last_ts
        @sequence = (@sequence + 1) & MAX_SEQ
        ts = wait_for_next_ms(@last_ts) if @sequence == 0
      else
        @sequence = 0
      end
      @last_ts = ts
      ((ts - EPOCH) << (NODE_BITS + SEQ_BITS)) |
        (@node_id << SEQ_BITS) |
        @sequence
    end
  end
 
  private
 
  def current_ms = (Time.now.to_f * 1000).to_i
 
  def wait_for_next_ms(last)
    ts = current_ms
    ts <= last ? wait_for_next_ms(last) : ts
  end
end
 
GENERATOR = SnowflakeIdGenerator.new(ENV.fetch('NODE_ID').to_i)
short_code = Base62Encoder.encode(GENERATOR.next_id)
# => "2nK7xQp" のような7文字

// internal/shortcode/generator.go
package shortcode
 
import (
	"sync"
	"time"
)
 
const (
	epoch    = int64(1704067200000)
	nodeBits = 10
	seqBits  = 12
	maxSeq   = (1 << seqBits) - 1
)
 
type Generator struct {
	mu       sync.Mutex
	nodeID   int64
	sequence int64
	lastMs   int64
}
 
func NewGenerator(nodeID int64) *Generator {
	return &Generator{nodeID: nodeID}
}
 
func (g *Generator) Next() uint64 {
	g.mu.Lock()
	defer g.mu.Unlock()
 
	ms := time.Now().UnixMilli()
	if ms == g.lastMs {
		g.sequence = (g.sequence + 1) & maxSeq
		if g.sequence == 0 {
			for ms <= g.lastMs {
				ms = time.Now().UnixMilli()
			}
		}
	} else {
		g.sequence = 0
	}
	g.lastMs = ms
 
	return uint64((ms-epoch)<<(nodeBits+seqBits) | g.nodeID<<seqBits | g.sequence)
}
 
// internal/shortcode/base62.go
const chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 
func Encode(num uint64) string {
	if num == 0 {
		return string(chars[0])
	}
	var result []byte
	for num > 0 {
		result = append([]byte{chars[num%62]}, result...)
		num /= 62
	}
	return string(result)
}

-- short_urls テーブル（月単位パーティショニング）
CREATE TABLE short_urls (
  id           BIGSERIAL   PRIMARY KEY,
  short_code   VARCHAR(10) NOT NULL,
  original_url TEXT        NOT NULL,
  user_id      BIGINT      NOT NULL,
  click_count  BIGINT      NOT NULL DEFAULT 0,
  created_at   TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  expires_at   TIMESTAMPTZ NOT NULL,
  deleted_at   TIMESTAMPTZ,
  is_malicious BOOLEAN     NOT NULL DEFAULT FALSE
) PARTITION BY RANGE (created_at);
 
-- インデックス設計
CREATE UNIQUE INDEX idx_short_urls_short_code
  ON short_urls(short_code)
  WHERE deleted_at IS NULL;
 
CREATE INDEX idx_short_urls_user_id
  ON short_urls(user_id, created_at DESC);
 
CREATE INDEX idx_short_urls_expires_at
  ON short_urls(expires_at)
  WHERE expires_at < NOW();
 
-- 月単位パーティション（自動生成スクリプト推奨）
CREATE TABLE short_urls_2024_01 PARTITION OF short_urls
  FOR VALUES FROM ('2024-01-01') TO ('2024-02-01');
CREATE TABLE short_urls_2024_02 PARTITION OF short_urls
  FOR VALUES FROM ('2024-02-01') TO ('2024-03-01');

# app/services/url_resolver_service.rb
class UrlResolverService
  class NotFoundError < StandardError; end
  class ExpiredError  < StandardError; end
 
  HOT_THRESHOLD = 500   # 1分間のアクセス数
 
  def self.resolve(short_code)
    # 1. Redisキャッシュを確認
    cached = Rails.cache.read(cache_key(short_code))
    return handle_cached(short_code, cached) if cached
 
    # 2. キャッシュミス → DBから取得
    record = ShortUrl.find_by(short_code: short_code, deleted_at: nil)
    raise NotFoundError unless record
    raise ExpiredError  if record.expired?
 
    # 3. ホットURL判定でTTLを動的変更してキャッシュに書き込み
    ttl = calculate_ttl(short_code)
    Rails.cache.write(cache_key(short_code), {
      url:        record.original_url,
      expires_at: record.expires_at.to_i
    }, expires_in: ttl)
 
    record.original_url
  end
 
  private
 
  def self.handle_cached(short_code, cached)
    raise ExpiredError if cached[:expires_at] < Time.current.to_i
    increment_hot_counter(short_code)
    cached[:url]
  end
 
  def self.calculate_ttl(short_code)
    count = $redis.get("hot:#{short_code}").to_i
    count > HOT_THRESHOLD ? 24.hours : 1.hour
  end
 
  def self.increment_hot_counter(short_code)
    key = "hot:#{short_code}"
    $redis.multi do |tx|
      tx.incr(key)
      tx.expire(key, 60)
    end
  end
 
  def self.cache_key(short_code) = "url:v1:#{short_code}"
end

# lib/tasks/cache_warmup.rake
namespace :cache do
  desc "上位アクセスURLをキャッシュにプリロード（デプロイ直後のコールドスタート対策）"
  task warmup: :environment do
    puts "Starting cache warmup..."
 
    top_urls = ShortUrl.active
                       .order(click_count: :desc)
                       .limit(10_000)
                       .select(:short_code, :original_url, :expires_at)
 
    top_urls.each_slice(100) do |batch|
      batch.each do |record|
        Rails.cache.write(
          "url:v1:#{record.short_code}",
          { url: record.original_url, expires_at: record.expires_at.to_i },
          expires_in: 24.hours
        )
      end
      sleep(0.01)  # Redis過負荷防止
    end
 
    puts "Warmed up #{top_urls.size} URLs"
  end
end

# クリックカウントは非同期で更新（レイテンシ悪化を防ぐ）
class ClickTrackingJob < ApplicationJob
  queue_as :default
  sidekiq_options retry: 3
 
  def perform(short_code)
    ShortUrl.where(short_code: short_code)
            .update_all('click_count = click_count + 1')
  end
end

# app/services/rate_limiter.rb
class RateLimiter
  class TooManyRequestsError < StandardError; end
 
  # Fixed Window方式: シンプルだが窓の境界で2倍のリクエストが通る問題がある
  def self.check!(user_id, limit: 100, window: 60)
    key   = "rate:#{user_id}:#{Time.current.to_i / window}"
    count = $redis.incr(key)
    $redis.expire(key, window * 2) if count == 1
    raise TooManyRequestsError if count > limit
  end
 
  # Sliding Window方式（より正確、Redisの sorted set を利用）
  def self.check_sliding!(user_id, limit: 100, window: 60)
    key = "rate_sw:#{user_id}"
    now = Time.current.to_f
 
    results = $redis.multi do |tx|
      tx.zremrangebyscore(key, 0, now - window)
      tx.zadd(key, now, "#{now}-#{SecureRandom.hex(4)}")
      tx.zcard(key)
      tx.expire(key, window)
    end
 
    raise TooManyRequestsError if results[2] > limit
  end
end

# app/services/url_safety_checker.rb
class UrlSafetyChecker
  BLOCKED_DOMAINS = %w[evil.com malware.net phishing.org].freeze
 
  def self.safe?(url)
    uri = URI.parse(url)
 
    # 1. プロトコルチェック（http/httpsのみ）
    return false unless %w[http https].include?(uri.scheme)
 
    # 2. 内部IPアドレスをブロック（SSRF対策）
    return false if internal_ip?(uri.host)
 
    # 3. ブロックリスト照合
    return false if BLOCKED_DOMAINS.any? { |d| uri.host&.end_with?(d) }
 
    # 4. Google Safe Browsing API（本番実装）
    check_safe_browsing_api(url)
  rescue URI::InvalidURIError
    false
  end
 
  private
 
  def self.internal_ip?(host)
    return false unless host
    ip = IPAddr.new(host) rescue return(false)
    ip.private? || ip.loopback? || ip.link_local?
  end
 
  def self.check_safe_browsing_api(url)
    # Google Safe Browsing Lookup API v4 を使用
    # レスポンスの matches が空なら安全
    true
  end
end

CloudFront:
  オリジン: ALB
  キャッシュ: 302レスポンスはキャッシュしない
  WAF統合: レート制限、SQLインジェクション防御
  カスタムドメイン: ACM証明書
 
ALB:
  TargetGroup1: URL短縮 ECS × 3タスク（パス /api/*）
  TargetGroup2: リダイレクト ECS × 10タスク（パス /*）
 
ECS Fargate - URL短縮:
  CPU: 0.5vCPU / Memory: 1GB
  AutoScaling: CPU70%超で最大10タスク
  タスク定義: Rails + Puma（4ワーカー）
 
ECS Fargate - リダイレクト:
  CPU: 0.25vCPU / Memory: 512MB
  AutoScaling: CPU60%超で最大30タスク
  キャッシュヒット時はDBアクセスなし
 
Aurora PostgreSQL:
  構成: Writer 1台 + Reader 2台（Multi-AZ）
  インスタンス: db.r6g.xlarge（4vCPU, 32GB）
  バックアップ: 自動スナップショット35日保持
 
ElastiCache Redis Cluster:
  ノード: cache.r6g.xlarge × 3（Master1 + Replica2）
  メモリ: 32GB × 3 = 96GB（約15GB使用予定）
  クラスターモード: 有効（シャーディング）
 
SQS + Lambda（クリック集計）:
  バッチサイズ100でDBに集計書き込み
  リダイレクトのレイテンシからDB書き込みを分離

// internal/nodeid/allocator.go
// etcdでノードIDをECSタスク起動時に払い出し
package nodeid
 
import (
	"context"
	"fmt"
 
	clientv3 "go.etcd.io/etcd/client/v3"
)
 
type Allocator struct {
	client *clientv3.Client
}
 
func (a *Allocator) Acquire(ctx context.Context) (int64, error) {
	for id := int64(0); id < 1024; id++ {
		key  := fmt.Sprintf("/shorturl/nodes/%d", id)
		lease, _ := a.client.Grant(ctx, 30)
		txn := a.client.Txn(ctx).
			If(clientv3.Compare(clientv3.CreateRevision(key), "=", 0)).
			Then(clientv3.OpPut(key, "locked", clientv3.WithLease(lease.ID))).
			Commit()
 
		if resp, err := txn; err == nil && resp.Succeeded {
			go a.keepAlive(ctx, lease.ID)
			return id, nil
		}
	}
	return 0, fmt.Errorf("no available node IDs")
}
 
func (a *Allocator) keepAlive(ctx context.Context, leaseID clientv3.LeaseID) {
	ch, _ := a.client.KeepAlive(ctx, leaseID)
	for range ch {}
}

# app/middleware/metrics_middleware.rb
class MetricsMiddleware
  REDIRECT_LATENCY = Prometheus::Client::Histogram.new(
    :redirect_latency_seconds,
    docstring: 'Redirect latency in seconds',
    buckets: [0.005, 0.01, 0.025, 0.05, 0.1, 0.25, 0.5, 1.0]
  )
  CACHE_HITS   = Prometheus::Client::Counter.new(
    :cache_hits_total, docstring: 'Cache hits'
  )
  CACHE_MISSES = Prometheus::Client::Counter.new(
    :cache_misses_total, docstring: 'Cache misses'
  )
 
  def initialize(app)
    @app = app
  end
 
  def call(env)
    start    = Process.clock_gettime(Process::CLOCK_MONOTONIC)
    status, headers, body = @app.call(env)
    duration = Process.clock_gettime(Process::CLOCK_MONOTONIC) - start
    REDIRECT_LATENCY.observe(duration)
    [status, headers, body]
  end
end

# CloudWatch アラーム設定
アラーム一覧:
  RedirectLatencyP99:
    メトリクス: p99(redirect_latency_seconds)
    閾値: 100ms超
    アクション: PagerDuty通知
 
  CacheHitRateLow:
    メトリクス: cache_hits / (cache_hits + cache_misses)
    閾値: 90%未満
    アクション: Slack通知
 
  DBConnectionsHigh:
    メトリクス: RDS DatabaseConnections
    閾値: 最大接続数の80%超
    アクション: ECSタスクスケールダウン + Slack通知
 
  SQSQueueDepth:
    メトリクス: ApproximateNumberOfMessages
    閾値: 10,000件超（クリック集計の遅延）
    アクション: Lambda同時実行数を増やす