Build a URL Shortener: Short Code Generation

import { nanoid } from 'nanoid';
const shortCode = nanoid(7); // "V1StGXR"

// src/utils/base62.ts
 
const ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const BASE = BigInt(ALPHABET.length); // 62n
 
/**
 * Encode số nguyên dương thành Base62 string.
 *
 * Ví dụ: encode(123456789) → "8m0Kx"
 */
export function encode(num: bigint | number): string {
  let n = BigInt(num);
 
  if (n === 0n) return ALPHABET[0];
  if (n < 0n) throw new Error('Base62 encode requires a non-negative integer');
 
  let result = '';
  while (n > 0n) {
    result = ALPHABET[Number(n % BASE)] + result;
    n = n / BASE;
  }
 
  return result;
}
 
/**
 * Decode Base62 string về bigint.
 *
 * Ví dụ: decode("8m0Kx") → 123456789n
 */
export function decode(str: string): bigint {
  let result = 0n;
 
  for (const char of str) {
    const index = ALPHABET.indexOf(char);
    if (index === -1) {
      throw new Error(`Invalid Base62 character: "${char}"`);
    }
    result = result * BASE + BigInt(index);
  }
 
  return result;
}
 
/**
 * Encode với zero-padding đến fixed length.
 *
 * Ví dụ: encodePadded(42, 7) → "0000000G"
 */
export function encodePadded(num: bigint | number, length: number): string {
  const encoded = encode(num);
  if (encoded.length > length) {
    throw new Error(`Number too large for ${length}-character Base62 encoding`);
  }
  return encoded.padStart(length, ALPHABET[0]);
}

// src/utils/__tests__/base62.test.ts
 
import { describe, it, expect } from 'vitest';
import { encode, decode, encodePadded } from '../base62';
 
describe('Base62', () => {
  it('encode 0', () => {
    expect(encode(0)).toBe('0');
  });
 
  it('encode số nhỏ', () => {
    expect(encode(1)).toBe('1');
    expect(encode(9)).toBe('9');
    expect(encode(10)).toBe('a');
    expect(encode(35)).toBe('z');
    expect(encode(36)).toBe('A');
    expect(encode(61)).toBe('Z');
    expect(encode(62)).toBe('10');
  });
 
  it('encode số lớn', () => {
    expect(encode(123456789)).toBe('8m0Kx');
    expect(encode(BigInt('1000000000000'))).toBe('bLY2VLE');
  });
 
  it('round-trip chính xác', () => {
    const testValues = [0n, 1n, 61n, 62n, 123456789n, 999999999999n];
    for (const val of testValues) {
      expect(decode(encode(val))).toBe(val);
    }
  });
 
  it('pad đến fixed length', () => {
    expect(encodePadded(42, 7)).toBe('000000G');
    expect(encodePadded(42, 7).length).toBe(7);
  });
 
  it('reject số âm', () => {
    expect(() => encode(-1)).toThrow();
  });
 
  it('reject ký tự không hợp lệ', () => {
    expect(() => decode('abc-def')).toThrow('Invalid Base62 character');
  });
});

P(collision) ≈ 1 - e^(-k² / 2N)

k ≈ √(π × N / 2) ≈ 1.177 × √N

// src/services/codeGenerator.ts
 
import crypto from 'crypto';
 
const ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
 
export function generateRandomCode(length: number = 7): string {
  const bytes = crypto.randomBytes(length);
  let result = '';
 
  for (let i = 0; i < length; i++) {
    result += ALPHABET[bytes[i] % 62];
  }
 
  return result;
}

// src/services/counterCodeGenerator.ts
 
import { encode, encodePadded } from '../utils/base62';
 
/**
 * Counter-based generation dùng database sequence.
 *
 * Counter bắt đầu từ 100000 để đảm bảo minimum code length:
 * - encode(100000) = "q0U" (3 ký tự)
 * - encode(56800235584) = "1000000" (7 ký tự, overflow)
 */
export function encodeCounter(counter: bigint | number): string {
  return encode(counter);
}
 
// Trong Prisma schema, bạn dùng database sequence:
// model UrlCounter {
//   id    BigInt  @id @default(autoincrement())
// }
//
// Rồi: const { id } = await prisma.urlCounter.create({ data: {} });
//       const code = encodeCounter(id);

// src/services/hashCodeGenerator.ts
 
import crypto from 'crypto';
import { encode } from '../utils/base62';
 
/**
 * Generate short code bằng cách hash URL.
 * Cùng URL luôn tạo cùng code (trước khi truncation collision).
 */
export function generateHashCode(url: string, length: number = 7): string {
  const hash = crypto.createHash('sha256').update(url).digest();
 
  // Đọc 8 byte đầu thành BigInt
  const num = hash.readBigUInt64BE(0);
 
  // Encode sang Base62 rồi truncate
  const encoded = encode(num);
  return encoded.slice(0, length);
}

// ❌ ĐỪNG LÀM THẾ NÀY — race condition giữa check và insert
async function createUrl(originalUrl: string) {
  let code: string;
 
  do {
    code = generateRandomCode(7);
    const existing = await prisma.url.findUnique({ where: { shortCode: code } });
  } while (existing);
 
  // Request khác có thể đã insert code này giữa check và insert!
  return prisma.url.create({
    data: { originalUrl, shortCode: code },
  });
}

// src/services/urlService.ts
 
import { PrismaClient, Prisma } from '@prisma/client';
import { generateRandomCode } from './codeGenerator';
 
const prisma = new PrismaClient();
 
const MAX_RETRIES = 5;
 
interface CreateUrlOptions {
  originalUrl: string;
  customAlias?: string;
  expiresAt?: Date;
  userId?: string;
}
 
export async function createShortUrl(options: CreateUrlOptions): Promise<{
  shortCode: string;
  originalUrl: string;
  createdAt: Date;
}> {
  const { originalUrl, customAlias, expiresAt, userId } = options;
 
  // Nếu có custom alias, thử trực tiếp
  if (customAlias) {
    return createWithCustomAlias(originalUrl, customAlias, expiresAt, userId);
  }
 
  // Random generation với retry khi collision
  for (let attempt = 1; attempt <= MAX_RETRIES; attempt++) {
    try {
      const shortCode = generateRandomCode(7);
 
      const url = await prisma.url.create({
        data: {
          shortCode,
          originalUrl,
          expiresAt,
          userId,
        },
      });
 
      return {
        shortCode: url.shortCode,
        originalUrl: url.originalUrl,
        createdAt: url.createdAt,
      };
    } catch (error) {
      // P2002 = Unique constraint violation trong Prisma
      if (
        error instanceof Prisma.PrismaClientKnownRequestError &&
        error.code === 'P2002'
      ) {
        if (attempt === MAX_RETRIES) {
          throw new Error(
            `Failed to generate unique short code after ${MAX_RETRIES} attempts`
          );
        }
        // Retry với random code mới
        continue;
      }
 
      // Re-throw error không phải collision
      throw error;
    }
  }
 
  // TypeScript cần dòng này (không bao giờ chạy đến)
  throw new Error('Failed to generate short code');
}

P(single collision) = 100,000,000 / 3,521,614,606,208 ≈ 0.0028%
 
P(5 collision liên tiếp) = 0.0028%^5 ≈ 0 (gần như không thể)

// src/config/reservedWords.ts
 
/**
 * Từ không thể dùng làm custom alias.
 * Conflict với route hiện tại hoặc planned.
 */
export const RESERVED_WORDS = new Set([
  // API route
  'api',
  'graphql',
  'webhook',
  'webhooks',
 
  // Auth route
  'login',
  'logout',
  'register',
  'signup',
  'signin',
  'auth',
  'oauth',
  'callback',
 
  // Admin/system
  'admin',
  'dashboard',
  'settings',
  'account',
  'profile',
 
  // Health & monitoring
  'health',
  'healthz',
  'ready',
  'readyz',
  'status',
  'metrics',
  'ping',
 
  // Static/legal
  'about',
  'terms',
  'privacy',
  'help',
  'support',
  'contact',
  'docs',
  'blog',
 
  // Technical
  'static',
  'assets',
  'public',
  'favicon.ico',
  'robots.txt',
  'sitemap.xml',
  '.well-known',
 
  // Vanity phổ biến
  'app',
  'www',
  'mail',
  'ftp',
  'cdn',
  'dev',
  'staging',
  'test',
]);

// src/utils/validation.ts
 
import { RESERVED_WORDS } from '../config/reservedWords';
 
export interface ValidationResult {
  valid: boolean;
  error?: string;
}
 
/**
 * Validate custom alias.
 *
 * Rule:
 * - 3-30 ký tự
 * - Chỉ alphanumeric, hyphen, và underscore
 * - Không bắt đầu/kết thúc bằng hyphen/underscore
 * - Không phải reserved word
 * - Case-sensitive (MyResume ≠ myresume)
 */
export function validateCustomAlias(alias: string): ValidationResult {
  // Check length
  if (alias.length < 3) {
    return { valid: false, error: 'Custom alias phải ít nhất 3 ký tự' };
  }
  if (alias.length > 30) {
    return { valid: false, error: 'Custom alias tối đa 30 ký tự' };
  }
 
  // Check character set
  if (!/^[a-zA-Z0-9_-]+$/.test(alias)) {
    return {
      valid: false,
      error: 'Custom alias chỉ được chứa chữ cái, số, hyphen, và underscore',
    };
  }
 
  // Không special character ở đầu/cuối
  if (/^[-_]|[-_]$/.test(alias)) {
    return {
      valid: false,
      error: 'Custom alias không được bắt đầu/kết thúc bằng hyphen hoặc underscore',
    };
  }
 
  // Check reserved word (case-insensitive)
  if (RESERVED_WORDS.has(alias.toLowerCase())) {
    return { valid: false, error: `"${alias}" là reserved word và không thể sử dụng` };
  }
 
  return { valid: true };
}

// Trong src/services/urlService.ts
 
import { validateCustomAlias } from '../utils/validation';
 
async function createWithCustomAlias(
  originalUrl: string,
  alias: string,
  expiresAt?: Date,
  userId?: string
) {
  // Validate alias
  const validation = validateCustomAlias(alias);
  if (!validation.valid) {
    throw new AppError(400, validation.error!);
  }
 
  try {
    const url = await prisma.url.create({
      data: {
        shortCode: alias,
        originalUrl,
        isCustomAlias: true,
        expiresAt,
        userId,
      },
    });
 
    return {
      shortCode: url.shortCode,
      originalUrl: url.originalUrl,
      createdAt: url.createdAt,
    };
  } catch (error) {
    if (
      error instanceof Prisma.PrismaClientKnownRequestError &&
      error.code === 'P2002'
    ) {
      throw new AppError(409, `Custom alias "${alias}" đã bị chiếm`);
    }
    throw error;
  }
}

// prisma/schema.prisma
 
model Url {
  id            String    @id @default(uuid())
  shortCode     String    @unique @map("short_code")
  originalUrl   String    @map("original_url")
  isCustomAlias Boolean   @default(false) @map("is_custom_alias")
  expiresAt     DateTime? @map("expires_at")
  clickCount    Int       @default(0) @map("click_count")
  userId        String?   @map("user_id")
  createdAt     DateTime  @default(now()) @map("created_at")
  updatedAt     DateTime  @updatedAt @map("updated_at")
 
  user   User?   @relation(fields: [userId], references: [id])
  clicks Click[]
 
  @@index([userId])
  @@index([createdAt])
  @@map("urls")
}

// User A shorten https://example.com → abc1234
// User B shorten https://example.com → xyz5678
// Cùng URL, khác code

// src/services/urlService.ts
 
export async function createShortUrlWithDedup(options: CreateUrlOptions) {
  const { originalUrl, customAlias, expiresAt, userId } = options;
 
  // Bỏ qua dedup cho custom alias — user muốn code cụ thể
  if (!customAlias) {
    // Check user đã shorten URL này chưa
    const existing = await prisma.url.findFirst({
      where: {
        originalUrl,
        userId: userId ?? null,
        isCustomAlias: false,
        // Chỉ dedup URL active (chưa expire)
        OR: [
          { expiresAt: null },
          { expiresAt: { gt: new Date() } },
        ],
      },
    });
 
    if (existing) {
      return {
        shortCode: existing.shortCode,
        originalUrl: existing.originalUrl,
        createdAt: existing.createdAt,
        deduplicated: true,
      };
    }
  }
 
  // Không tìm thấy URL cũ — tạo mới
  return createShortUrl(options);
}

model Url {
  // ... field hiện tại
 
  @@index([originalUrl, userId])  // Fast dedup lookup
  @@map("urls")
}

// POST /api/shorten
// { "url": "https://example.com", "deduplicate": true }

// src/services/urlService.ts
 
import { PrismaClient, Prisma } from '@prisma/client';
import { generateRandomCode } from './codeGenerator';
import { validateCustomAlias } from '../utils/validation';
import { AppError } from '../middleware/errorHandler';
 
const prisma = new PrismaClient();
const MAX_RETRIES = 5;
 
interface CreateUrlOptions {
  originalUrl: string;
  customAlias?: string;
  expiresAt?: Date;
  userId?: string;
  deduplicate?: boolean;
}
 
interface CreateUrlResult {
  shortCode: string;
  originalUrl: string;
  createdAt: Date;
  isCustomAlias: boolean;
  deduplicated?: boolean;
}
 
export async function createShortUrl(
  options: CreateUrlOptions
): Promise<CreateUrlResult> {
  const { originalUrl, customAlias, expiresAt, userId, deduplicate } = options;
 
  // 1. Custom alias path
  if (customAlias) {
    const validation = validateCustomAlias(customAlias);
    if (!validation.valid) {
      throw new AppError(400, validation.error!);
    }
 
    try {
      const url = await prisma.url.create({
        data: {
          shortCode: customAlias,
          originalUrl,
          isCustomAlias: true,
          expiresAt,
          userId,
        },
      });
 
      return {
        shortCode: url.shortCode,
        originalUrl: url.originalUrl,
        createdAt: url.createdAt,
        isCustomAlias: true,
      };
    } catch (error) {
      if (
        error instanceof Prisma.PrismaClientKnownRequestError &&
        error.code === 'P2002'
      ) {
        throw new AppError(409, `Custom alias "${customAlias}" đã bị chiếm`);
      }
      throw error;
    }
  }
 
  // 2. Deduplication check (optional)
  if (deduplicate) {
    const existing = await prisma.url.findFirst({
      where: {
        originalUrl,
        userId: userId ?? null,
        isCustomAlias: false,
        OR: [{ expiresAt: null }, { expiresAt: { gt: new Date() } }],
      },
    });
 
    if (existing) {
      return {
        shortCode: existing.shortCode,
        originalUrl: existing.originalUrl,
        createdAt: existing.createdAt,
        isCustomAlias: false,
        deduplicated: true,
      };
    }
  }
 
  // 3. Random generation với collision retry
  for (let attempt = 1; attempt <= MAX_RETRIES; attempt++) {
    try {
      const shortCode = generateRandomCode(7);
 
      const url = await prisma.url.create({
        data: {
          shortCode,
          originalUrl,
          isCustomAlias: false,
          expiresAt,
          userId,
        },
      });
 
      return {
        shortCode: url.shortCode,
        originalUrl: url.originalUrl,
        createdAt: url.createdAt,
        isCustomAlias: false,
      };
    } catch (error) {
      if (
        error instanceof Prisma.PrismaClientKnownRequestError &&
        error.code === 'P2002'
      ) {
        if (attempt === MAX_RETRIES) {
          throw new AppError(
            503,
            'Không thể generate unique short code. Vui lòng thử lại.'
          );
        }
        continue;
      }
      throw error;
    }
  }
 
  throw new AppError(503, 'Không thể generate unique short code');
}
 
export async function getUrlByCode(shortCode: string) {
  const url = await prisma.url.findUnique({
    where: { shortCode },
  });
 
  if (!url) return null;
 
  // Check expiration
  if (url.expiresAt && url.expiresAt < new Date()) {
    return null;
  }
 
  return url;
}

// src/routes/urlRoutes.ts
 
import { Router, Request, Response } from 'express';
import { createShortUrl, getUrlByCode } from '../services/urlService';
import { AppError } from '../middleware/errorHandler';
 
const router = Router();
 
router.post('/api/shorten', async (req: Request, res: Response) => {
  const { url, customAlias, expiresAt, deduplicate } = req.body;
 
  if (!url || typeof url !== 'string') {
    throw new AppError(400, 'URL is required');
  }
 
  // Basic URL validation
  try {
    new URL(url);
  } catch {
    throw new AppError(400, 'Invalid URL format');
  }
 
  const result = await createShortUrl({
    originalUrl: url,
    customAlias,
    expiresAt: expiresAt ? new Date(expiresAt) : undefined,
    deduplicate: deduplicate ?? false,
    // userId từ auth middleware (Phase 7)
  });
 
  res.status(result.deduplicated ? 200 : 201).json({
    shortCode: result.shortCode,
    shortUrl: `${process.env.BASE_URL}/${result.shortCode}`,
    originalUrl: result.originalUrl,
    isCustomAlias: result.isCustomAlias,
    deduplicated: result.deduplicated ?? false,
    createdAt: result.createdAt,
  });
});
 
export default router;

// ❌ Sai — predictable, không uniform, không cryptographic
const code = Math.random().toString(36).substring(2, 9);
 
// ✅ Đúng — cryptographically random
const bytes = crypto.randomBytes(7);

// ❌ Sai — race condition
const exists = await db.findByCode(code);
if (!exists) {
  await db.insert(code); // Request khác có thể insert giữa check và insert
}
 
// ✅ Đúng — để database enforce uniqueness
try {
  await db.insert(code);
} catch (e) {
  if (isUniqueViolation(e)) retry();
}

// ❌ Sai — user tạo alias "api" và break API
app.post('/api/shorten', handler);
app.get('/:code', redirectHandler); // "api" match route này!
 
// ✅ Đúng — check reserved word trước khi tạo alias
if (RESERVED_WORDS.has(alias.toLowerCase())) {
  throw new AppError(400, 'Reserved word');
}

// ❌ Sai — user thấy code "1a" và thử "1b", "1c", v.v.
const code = encode(autoIncrementId);
 
// ✅ Tốt hơn — nếu dùng counter, ít nhất scramble bit
const scrambled = autoIncrementId ^ 0x5A5A5A5A5A5An; // XOR với secret
const code = encode(scrambled);

// ❌ Bug — "MyCode" và "mycode" có thể collision ở một số database
// PostgreSQL text comparison case-sensitive mặc định (tốt)
// Nhưng MySQL default collation case-insensitive (xấu)
 
// ✅ Đúng — explicit về case sensitivity trong schema
// PostgreSQL: text column case-sensitive mặc định ✓
// Nếu dùng MySQL: dùng utf8_bin collation