設計短網址系統 — Base62 編碼、分散式 ID 生成與重導向架構 | 資料結構與演算法

// ─── Base62 編解碼器 ──────────────────────────────────────────

const BASE62_CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const BASE62_MAP = new Map<string, number>(
  BASE62_CHARS.split("").map((c, i) => [c, i])
);

/** 將 bigint 編碼為 Base62 字串 */
function toBase62(num: bigint): string {
  if (num === 0n) return "0";
  const base = 62n;
  const digits: string[] = [];
  let n = num;
  while (n > 0n) {
    digits.push(BASE62_CHARS[Number(n % base)]);
    n = n / base;
  }
  return digits.reverse().join("");
}

/** 將 Base62 字串解碼為 bigint */
function fromBase62(str: string): bigint {
  const base = 62n;
  let result = 0n;
  for (const ch of str) {
    const val = BASE62_MAP.get(ch);
    if (val === undefined) throw new Error(`無效的 Base62 字元：${ch}`);
    result = result * base + BigInt(val);
  }
  return result;
}

/** 補齊至固定長度（左補 '0'） */
function padBase62(str: string, length: number): string {
  return str.padStart(length, "0");
}

// ─── 測試 Base62 ─────────────────────────────────────────────

const testId = 123456789n;
const encoded = toBase62(testId);
const decoded = fromBase62(encoded);
console.log(`ID: ${testId} → Base62: "${encoded}" → 解碼: ${decoded}`);
console.log(`驗證: ${testId === decoded ? "通過" : "失敗"}`);
// 輸出：
//   ID: 123456789 → Base62: "8M0kX" → 解碼: 123456789
//   驗證: 通過

// 邊界值測試
for (const val of [0n, 1n, 61n, 62n, 3844n, BigInt(Number.MAX_SAFE_INTEGER)]) {
  const enc = toBase62(val);
  const dec = fromBase62(enc);
  console.log(`  ${val} → "${padBase62(enc, 7)}" → ${dec} [${val === dec ? "OK" : "FAIL"}]`);
}
// 輸出：
//   0 → "0000000" → 0 [OK]
//   1 → "0000001" → 1 [OK]
//   61 → "000000z" → 61 [OK]
//   62 → "0000010" → 62 [OK]
//   3844 → "0000100" → 3844 [OK]
//   9007199254740991 → "FfGNdXsE7" → 9007199254740991 [OK]

// ─── Snowflake ID 生成器 ──────────────────────────────────────

class SnowflakeGenerator {
  private readonly epoch: bigint;
  private readonly machineId: bigint;
  private sequence: bigint = 0n;
  private lastTimestamp: bigint = -1n;

  // 位元配置
  private static readonly MACHINE_BITS = 10n;
  private static readonly SEQUENCE_BITS = 12n;
  private static readonly MAX_SEQUENCE = (1n << 12n) - 1n;     // 4095
  private static readonly MAX_MACHINE_ID = (1n << 10n) - 1n;   // 1023

  constructor(machineId: number, epochMs: number = 1577836800000) {
    if (BigInt(machineId) > SnowflakeGenerator.MAX_MACHINE_ID) {
      throw new Error(`machineId 必須 < ${SnowflakeGenerator.MAX_MACHINE_ID}`);
    }
    this.machineId = BigInt(machineId);
    this.epoch = BigInt(epochMs); // 預設 2020-01-01
  }

  /** 產生下一個唯一 ID */
  generate(): bigint {
    let now = BigInt(Date.now());

    if (now === this.lastTimestamp) {
      // 同毫秒內遞增序列號
      this.sequence = (this.sequence + 1n) & SnowflakeGenerator.MAX_SEQUENCE;
      if (this.sequence === 0n) {
        // 序列號耗盡，等待下一毫秒
        while (now <= this.lastTimestamp) {
          now = BigInt(Date.now());
        }
      }
    } else {
      this.sequence = 0n;
    }

    this.lastTimestamp = now;

    // 組合 64 位 ID
    return (
      ((now - this.epoch) << (SnowflakeGenerator.MACHINE_BITS + SnowflakeGenerator.SEQUENCE_BITS)) |
      (this.machineId << SnowflakeGenerator.SEQUENCE_BITS) |
      this.sequence
    );
  }
}

// ─── 測試 Snowflake ──────────────────────────────────────────

const idGen = new SnowflakeGenerator(1); // 機器 ID = 1
const ids: bigint[] = [];

console.log("\n--- Snowflake ID 生成 ---");
for (let i = 0; i < 5; i++) {
  const id = idGen.generate();
  ids.push(id);
  const code = padBase62(toBase62(id), 7);
  console.log(`ID: ${id} → 短碼: "${code}"`);
}

// 唯一性驗證
const uniqueIds = new Set(ids.map(String));
console.log(`唯一性驗證：${uniqueIds.size === ids.length ? "全部唯一" : "有重複！"}`);
// 輸出：
//   ID: 832943816704000 → 短碼: "3yFxHe80"
//   ID: 832943816704001 → 短碼: "3yFxHe81"
//   ...
//   唯一性驗證：全部唯一

// ─── 資料模型 ─────────────────────────────────────────────────

interface UrlRecord {
  id: bigint;
  shortCode: string;
  longUrl: string;
  createdAt: Date;
  expiresAt?: Date;
  clickCount: number;
}

// ─── 資料存取層（模擬資料庫） ─────────────────────────────────

class UrlRepository {
  private db = new Map<string, UrlRecord>();           // shortCode → record
  private longUrlIndex = new Map<string, string>();    // longUrl → shortCode

  async findByShortCode(shortCode: string): Promise<UrlRecord | null> {
    return this.db.get(shortCode) ?? null;
  }

  async findByLongUrl(longUrl: string): Promise<string | null> {
    return this.longUrlIndex.get(longUrl) ?? null;
  }

  async save(record: UrlRecord): Promise<void> {
    this.db.set(record.shortCode, record);
    this.longUrlIndex.set(record.longUrl, record.shortCode);
  }

  async incrementClick(shortCode: string): Promise<void> {
    const record = this.db.get(shortCode);
    if (record) record.clickCount++;
  }

  async deleteExpired(): Promise<number> {
    const now = new Date();
    let deleted = 0;
    for (const [code, record] of this.db) {
      if (record.expiresAt && record.expiresAt < now) {
        this.db.delete(code);
        this.longUrlIndex.delete(record.longUrl);
        deleted++;
      }
    }
    return deleted;
  }
}

// ─── Redis 快取層（模擬） ─────────────────────────────────────

class CacheLayer {
  private cache = new Map<string, { value: string; expiresAt: number }>();

  async get(key: string): Promise<string | null> {
    const entry = this.cache.get(key);
    if (!entry) return null;
    if (Date.now() > entry.expiresAt) {
      this.cache.delete(key);
      return null;
    }
    return entry.value;
  }

  async set(key: string, value: string, ttlSeconds: number): Promise<void> {
    this.cache.set(key, {
      value,
      expiresAt: Date.now() + ttlSeconds * 1000,
    });
  }

  async del(key: string): Promise<void> {
    this.cache.delete(key);
  }

  cacheKey(shortCode: string): string {
    return `url:${shortCode}`;
  }
}

// ─── 核心服務層 ───────────────────────────────────────────────

interface ShortenOptions {
  customCode?: string;
  expiresInDays?: number;
}

interface ShortenResult {
  shortCode: string;
  shortUrl: string;
  longUrl: string;
  expiresAt?: Date;
  isNew: boolean;
}

class UrlShortenerService {
  private static readonly SHORT_CODE_LENGTH = 7;
  private static readonly CACHE_TTL = 86400; // 24 小時
  private static readonly BASE_URL = "https://short.ly";

  constructor(
    private readonly idGen: SnowflakeGenerator,
    private readonly repo: UrlRepository,
    private readonly cache: CacheLayer
  ) {}

  /** 建立短網址 */
  async shorten(longUrl: string, opts: ShortenOptions = {}): Promise<ShortenResult> {
    this.validateUrl(longUrl);

    // 自訂短碼
    if (opts.customCode) {
      return this.createCustomCode(longUrl, opts);
    }

    // 冪等性檢查：相同長 URL 是否已有短碼？
    const existing = await this.repo.findByLongUrl(longUrl);
    if (existing) {
      return {
        shortCode: existing,
        shortUrl: `${UrlShortenerService.BASE_URL}/${existing}`,
        longUrl,
        isNew: false,
      };
    }

    // 生成 Snowflake ID → Base62 短碼
    const id = this.idGen.generate();
    const shortCode = padBase62(toBase62(id), UrlShortenerService.SHORT_CODE_LENGTH);

    const expiresAt = opts.expiresInDays
      ? new Date(Date.now() + opts.expiresInDays * 86400000)
      : undefined;

    const record: UrlRecord = {
      id,
      shortCode,
      longUrl,
      createdAt: new Date(),
      expiresAt,
      clickCount: 0,
    };

    await this.repo.save(record);
    // 預熱快取
    await this.cache.set(
      this.cache.cacheKey(shortCode),
      longUrl,
      UrlShortenerService.CACHE_TTL
    );

    return {
      shortCode,
      shortUrl: `${UrlShortenerService.BASE_URL}/${shortCode}`,
      longUrl,
      expiresAt,
      isNew: true,
    };
  }

  /** 重導向解析：短碼 → 長 URL */
  async resolve(shortCode: string): Promise<string | null> {
    // 1. 查詢快取
    const cacheKey = this.cache.cacheKey(shortCode);
    const cached = await this.cache.get(cacheKey);
    if (cached) {
      // 非同步記錄點擊（不阻塞回應）
      this.repo.incrementClick(shortCode).catch(console.error);
      return cached;
    }

    // 2. 快取未命中 → 查詢資料庫
    const record = await this.repo.findByShortCode(shortCode);
    if (!record) return null;

    // 3. 檢查是否已過期
    if (record.expiresAt && record.expiresAt < new Date()) {
      return null;
    }

    // 4. 回寫快取並記錄點擊
    await this.cache.set(cacheKey, record.longUrl, UrlShortenerService.CACHE_TTL);
    this.repo.incrementClick(shortCode).catch(console.error);

    return record.longUrl;
  }

  /** 自訂短碼處理 */
  private async createCustomCode(
    longUrl: string,
    opts: ShortenOptions
  ): Promise<ShortenResult> {
    const customCode = opts.customCode!;

    // 驗證格式：只允許字母、數字、連字符，長度 3-20
    if (!/^[a-zA-Z0-9-]{3,20}$/.test(customCode)) {
      throw new Error("自訂短碼只允許字母、數字、連字符，長度 3-20");
    }

    // 檢查衝突
    const conflict = await this.repo.findByShortCode(customCode);
    if (conflict) {
      throw new Error(`短碼 "${customCode}" 已被使用`);
    }

    const id = this.idGen.generate();
    const expiresAt = opts.expiresInDays
      ? new Date(Date.now() + opts.expiresInDays * 86400000)
      : undefined;

    const record: UrlRecord = {
      id,
      shortCode: customCode,
      longUrl,
      createdAt: new Date(),
      expiresAt,
      clickCount: 0,
    };

    await this.repo.save(record);
    await this.cache.set(
      this.cache.cacheKey(customCode),
      longUrl,
      UrlShortenerService.CACHE_TTL
    );

    return {
      shortCode: customCode,
      shortUrl: `${UrlShortenerService.BASE_URL}/${customCode}`,
      longUrl,
      expiresAt,
      isNew: true,
    };
  }

  private validateUrl(url: string): void {
    try {
      const parsed = new URL(url);
      if (!["http:", "https:"].includes(parsed.protocol)) {
        throw new Error("只支援 HTTP/HTTPS 協定");
      }
    } catch {
      throw new Error(`無效的 URL 格式：${url}`);
    }
  }
}

// ─── 完整使用示範 ─────────────────────────────────────────────

async function demo(): Promise<void> {
  console.log("=== URL Shortener Demo ===\n");

  const idGen = new SnowflakeGenerator(1);
  const repo = new UrlRepository();
  const cache = new CacheLayer();
  const service = new UrlShortenerService(idGen, repo, cache);

  // 1. 建立短網址
  const result1 = await service.shorten(
    "https://www.example.com/very/long/path?query=value&more=params"
  );
  console.log(`建立短網址：${result1.shortUrl}`);
  console.log(`  原始 URL：${result1.longUrl}`);
  console.log(`  是否新建：${result1.isNew}`);

  // 2. 冪等性測試——相同 URL 回傳相同短碼
  const result2 = await service.shorten(
    "https://www.example.com/very/long/path?query=value&more=params"
  );
  console.log(`\n冪等性測試：${result2.shortUrl}`);
  console.log(`  短碼相同：${result1.shortCode === result2.shortCode}`);
  console.log(`  是否新建：${result2.isNew}`);

  // 3. 重導向解析
  const longUrl = await service.resolve(result1.shortCode);
  console.log(`\n解析短碼 "${result1.shortCode}"：`);
  console.log(`  → ${longUrl}`);

  // 4. 自訂短碼 + 過期設定
  const custom = await service.shorten("https://openai.com", {
    customCode: "openai",
    expiresInDays: 30,
  });
  console.log(`\n自訂短碼：${custom.shortUrl}`);
  console.log(`  過期時間：${custom.expiresAt?.toISOString()}`);

  // 5. 不存在的短碼
  const notFound = await service.resolve("xxxxxxx");
  console.log(`\n解析不存在的短碼：${notFound}`);
}

demo().catch(console.error);
// 輸出：
//   === URL Shortener Demo ===
//
//   建立短網址：https://short.ly/3yFxHe80
//     原始 URL：https://www.example.com/very/long/path?query=value&more=params
//     是否新建：true
//
//   冪等性測試：https://short.ly/3yFxHe80
//     短碼相同：true
//     是否新建：false
//
//   解析短碼 "3yFxHe80"：
//     → https://www.example.com/very/long/path?query=value&more=params
//
//   自訂短碼：https://short.ly/openai
//     過期時間：2026-08-26T...
//
//   解析不存在的短碼：null

// ============================================================
// URL Shortener — C++ 高效實作
// Base62 查表法 + Snowflake ID + 完整服務
// ============================================================

#include <iostream>
#include <string>
#include <unordered_map>
#include <optional>
#include <stdexcept>
#include <chrono>
#include <mutex>
#include <cstdint>
#include <vector>
#include <cassert>

// ─── Base62 編解碼（查表法，O(1) 反查）──────────────────────

namespace Base62 {

constexpr char CHARS[] =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
constexpr int BASE = 62;

// 靜態反查表（ASCII 0-127 → Base62 index，無效為 -1）
static int REVERSE[128];
static bool initialized = false;

void init() {
    if (initialized) return;
    for (int i = 0; i < 128; i++) REVERSE[i] = -1;
    for (int i = 0; i < BASE; i++) REVERSE[(unsigned char)CHARS[i]] = i;
    initialized = true;
}

// 編碼：uint64_t → Base62 字串（左補 0 至 padLen 長度）
std::string encode(uint64_t num, int padLen = 7) {
    init();
    if (num == 0) return std::string(padLen, '0');

    char buf[16];
    int pos = 15;
    buf[pos] = '\0';

    while (num > 0) {
        buf[--pos] = CHARS[num % BASE];
        num /= BASE;
    }

    std::string result(buf + pos);
    // 左補 '0' 至指定長度
    if ((int)result.size() < padLen) {
        result = std::string(padLen - result.size(), '0') + result;
    }
    return result;
}

// 解碼：Base62 字串 → uint64_t
uint64_t decode(const std::string& str) {
    init();
    uint64_t result = 0;
    for (char c : str) {
        if ((unsigned char)c >= 128 || REVERSE[(unsigned char)c] == -1) {
            throw std::invalid_argument(
                std::string("無效的 Base62 字元：") + c
            );
        }
        result = result * BASE + REVERSE[(unsigned char)c];
    }
    return result;
}

} // namespace Base62

// ─── Snowflake ID 生成器（執行緒安全）─────────────────────────

class SnowflakeGenerator {
public:
    static constexpr uint64_t EPOCH_MS = 1577836800000ULL; // 2020-01-01
    static constexpr int MACHINE_BITS  = 10;
    static constexpr int SEQUENCE_BITS = 12;
    static constexpr uint64_t MAX_SEQUENCE = (1ULL << SEQUENCE_BITS) - 1;
    static constexpr uint64_t MAX_MACHINE  = (1ULL << MACHINE_BITS) - 1;

    explicit SnowflakeGenerator(uint32_t machineId) {
        if (machineId > MAX_MACHINE) {
            throw std::invalid_argument("machineId 超出範圍（最大 1023）");
        }
        machineId_ = static_cast<uint64_t>(machineId);
        sequence_  = 0;
        lastMs_    = 0;
    }

    uint64_t generate() {
        std::lock_guard<std::mutex> lock(mu_);
        uint64_t now = currentMs();

        if (now == lastMs_) {
            sequence_ = (sequence_ + 1) & MAX_SEQUENCE;
            if (sequence_ == 0) {
                // 同毫秒序列號耗盡，自旋等待
                while (now <= lastMs_) now = currentMs();
            }
        } else {
            sequence_ = 0;
        }
        lastMs_ = now;

        return ((now - EPOCH_MS) << (MACHINE_BITS + SEQUENCE_BITS))
             | (machineId_ << SEQUENCE_BITS)
             | sequence_;
    }

private:
    uint64_t currentMs() const {
        using namespace std::chrono;
        return duration_cast<milliseconds>(
            system_clock::now().time_since_epoch()
        ).count();
    }

    uint64_t machineId_;
    uint64_t sequence_;
    uint64_t lastMs_;
    std::mutex mu_;
};

// ─── 資料模型 ─────────────────────────────────────────────────

struct UrlRecord {
    uint64_t    id;
    std::string shortCode;
    std::string longUrl;
    int64_t     createdAt;   // Unix 時間戳（秒）
    int64_t     expiresAt;   // 0 = 永不過期
    uint64_t    clickCount;
};

// ─── 短網址服務 ───────────────────────────────────────────────

class UrlShortenerService {
public:
    static constexpr int SHORT_CODE_LEN = 7;

    explicit UrlShortenerService(uint32_t machineId)
        : idGen_(machineId) {}

    // 建立短網址，回傳短碼
    std::string shorten(const std::string& longUrl, int expiresInDays = 0) {
        // 冪等性檢查
        {
            std::lock_guard<std::mutex> lock(mu_);
            auto it = longToShort_.find(longUrl);
            if (it != longToShort_.end()) return it->second;
        }

        uint64_t id = idGen_.generate();
        std::string shortCode = Base62::encode(id, SHORT_CODE_LEN);

        int64_t now = std::chrono::duration_cast<std::chrono::seconds>(
            std::chrono::system_clock::now().time_since_epoch()
        ).count();

        UrlRecord record{
            id, shortCode, longUrl, now,
            expiresInDays > 0 ? now + expiresInDays * 86400LL : 0LL,
            0ULL
        };

        {
            std::lock_guard<std::mutex> lock(mu_);
            db_[shortCode] = record;
            longToShort_[longUrl] = shortCode;
        }
        return shortCode;
    }

    // 解析短碼 → 長 URL
    std::optional<std::string> resolve(const std::string& shortCode) {
        std::lock_guard<std::mutex> lock(mu_);

        // 先查快取
        auto cit = cache_.find(shortCode);
        if (cit != cache_.end()) {
            db_[shortCode].clickCount++;
            return cit->second;
        }

        // 查資料庫
        auto it = db_.find(shortCode);
        if (it == db_.end()) return std::nullopt;

        auto& record = it->second;

        // 過期檢查
        if (record.expiresAt > 0) {
            int64_t now = std::chrono::duration_cast<std::chrono::seconds>(
                std::chrono::system_clock::now().time_since_epoch()
            ).count();
            if (now > record.expiresAt) return std::nullopt;
        }

        // 回寫快取
        cache_[shortCode] = record.longUrl;
        record.clickCount++;
        return record.longUrl;
    }

private:
    SnowflakeGenerator idGen_;
    mutable std::mutex mu_;

    std::unordered_map<std::string, UrlRecord>     db_;
    std::unordered_map<std::string, std::string>   longToShort_;
    std::unordered_map<std::string, std::string>   cache_;
};

// ─── 效能基準測試 ─────────────────────────────────────────────

void benchmarkBase62() {
    using namespace std::chrono;
    const int N = 1'000'000;

    // 編碼基準
    auto start = high_resolution_clock::now();
    std::string last;
    for (int i = 0; i < N; i++) {
        last = Base62::encode(static_cast<uint64_t>(i) * 1234567, 7);
    }
    auto end = high_resolution_clock::now();
    double ms = duration_cast<nanoseconds>(end - start).count() / 1e6;
    std::cout << "Base62 encode " << N << " 次：" << ms << " ms\n";

    // 解碼基準
    start = high_resolution_clock::now();
    uint64_t sum = 0;
    for (int i = 0; i < N; i++) {
        sum += Base62::decode(last);
    }
    end = high_resolution_clock::now();
    ms = duration_cast<nanoseconds>(end - start).count() / 1e6;
    std::cout << "Base62 decode " << N << " 次：" << ms << " ms\n\n";
}

// ─── 主程式 ───────────────────────────────────────────────────

int main() {
    std::cout << "=== URL Shortener C++ Demo ===\n\n";

    // 1. Base62 測試
    std::cout << "--- Base62 編解碼 ---\n";
    uint64_t testId = 123456789ULL;
    std::string enc = Base62::encode(testId, 7);
    uint64_t dec = Base62::decode(enc);
    std::cout << "ID: " << testId << " → \"" << enc
              << "\" → " << dec
              << " [" << (testId == dec ? "OK" : "FAIL") << "]\n\n";

    // 2. Snowflake 測試
    std::cout << "--- Snowflake ID ---\n";
    SnowflakeGenerator gen(1);
    for (int i = 0; i < 5; i++) {
        uint64_t id = gen.generate();
        std::string code = Base62::encode(id, 7);
        std::cout << "ID: " << id << " → \"" << code << "\"\n";
    }

    // 3. 完整服務測試
    std::cout << "\n--- URL Shortener 服務 ---\n";
    UrlShortenerService service(42);

    std::string url = "https://www.example.com/very/long/path?q=1";
    std::string code1 = service.shorten(url);
    std::cout << "縮短: \"" << code1 << "\"\n";

    std::string code2 = service.shorten(url);
    std::cout << "冪等: \"" << code2 << "\" ["
              << (code1 == code2 ? "相同" : "不同") << "]\n";

    auto resolved = service.resolve(code1);
    std::cout << "解析: " << (resolved ? *resolved : "(null)") << "\n";

    auto notFound = service.resolve("xxxxxxx");
    std::cout << "不存在: " << (notFound ? *notFound : "(null)") << "\n";

    // 4. 效能基準
    std::cout << "\n--- 效能基準 ---\n";
    benchmarkBase62();

    return 0;
}
// 輸出：
//   === URL Shortener C++ Demo ===
//
//   --- Base62 編解碼 ---
//   ID: 123456789 → "008M0kX" → 123456789 [OK]
//
//   --- Snowflake ID ---
//   ID: 832943816704000 → "3yFxHe80" ...
//
//   --- URL Shortener 服務 ---
//   縮短: "3yFxHe80"
//   冪等: "3yFxHe80" [相同]
//   解析: https://www.example.com/very/long/path?q=1
//   不存在: (null)
//
//   --- 效能基準 ---
//   Base62 encode 1000000 次：~12 ms
//   Base62 decode 1000000 次：~9 ms

-- 主表：短網址映射
CREATE TABLE url_mappings (
    id          BIGINT PRIMARY KEY,
    short_code  VARCHAR(10) NOT NULL UNIQUE,
    long_url    TEXT NOT NULL,
    user_id     BIGINT,
    created_at  TIMESTAMP DEFAULT NOW(),
    expires_at  TIMESTAMP,
    click_count BIGINT DEFAULT 0,
    is_custom   BOOLEAN DEFAULT FALSE,

    INDEX idx_short_code (short_code),
    INDEX idx_user_id (user_id),
    INDEX idx_expires_at (expires_at)
);

-- 點擊事件表（獨立存儲，可用 ClickHouse 替代）
CREATE TABLE click_events (
    id         BIGINT AUTO_INCREMENT PRIMARY KEY,
    short_code VARCHAR(10) NOT NULL,
    clicked_at TIMESTAMP DEFAULT NOW(),
    ip_hash    VARCHAR(64),
    country    VARCHAR(2),
    device     VARCHAR(20),
    referrer   VARCHAR(500),

    INDEX idx_short_code_time (short_code, clicked_at)
);