Design a URL Shortener

Difficulty: Intermediate

Question

Design a URL shortening service like bit.ly. How would you generate unique short URLs and handle billions of redirects?

Answer

Core requirements: 1. Given a long URL, generate a unique short URL 2. Given a short URL, redirect to the original long URL 3. Short URLs should be as short as possible 4. Analytics: track click counts, geographic data

Key design decisions: - Short code generation: Base62 encoding (a-z, A-Z, 0-9) with 7 characters gives 62^7 = 3.5 trillion combinations - Storage: SQL database with caching layer (Redis) - Read-heavy system: 100:1 read-to-write ratio, so optimize for reads - 301 (permanent) vs 302 (temporary) redirect affects caching and analytics

Code examples

URL Shortener Core Logic

// Approach 1: Counter + Base62 encoding
const BASE62 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';

function encodeBase62(num) {
  let encoded = '';
  while (num > 0) {
    encoded = BASE62[num % 62] + encoded;
    num = Math.floor(num / 62);
  }
  return encoded.padStart(7, 'a');
}

// Approach 2: MD5 hash + take first 7 chars
function hashApproach(longUrl) {
  const hash = md5(longUrl);
  return hash.substring(0, 7);
  // Handle collisions: append counter and rehash
}

// Approach 3: Pre-generated unique IDs
// Use a separate key generation service (KGS)
// that pre-generates unique 7-char codes
// and stores them in a database

// Database schema
// CREATE TABLE urls (
//   id BIGSERIAL PRIMARY KEY,
//   short_code VARCHAR(7) UNIQUE NOT NULL,
//   long_url TEXT NOT NULL,
//   user_id INT,
//   created_at TIMESTAMP DEFAULT NOW(),
//   expires_at TIMESTAMP,
//   click_count BIGINT DEFAULT 0
// );
// CREATE INDEX idx_short_code ON urls(short_code);

Base62 with auto-incrementing counter is simplest. Hash approach avoids sequential IDs but needs collision handling. Pre-generated keys scale best for distributed systems.

Redirect Flow with Caching

// Redirect endpoint
app.get('/:shortCode', async (req, res) => {
  const { shortCode } = req.params;

  // 1. Check Redis cache first
  let longUrl = await redis.get(`url:${shortCode}`);

  if (!longUrl) {
    // 2. Cache miss - query database
    const record = await db.query(
      'SELECT long_url FROM urls WHERE short_code = $1',
      [shortCode]
    );

    if (!record) return res.status(404).send('URL not found');

    longUrl = record.long_url;

    // 3. Populate cache (TTL: 24 hours)
    await redis.set(`url:${shortCode}`, longUrl, 'EX', 86400);
  }

  // 4. Async analytics (don't block redirect)
  analyticsQueue.push({
    shortCode,
    ip: req.ip,
    userAgent: req.headers['user-agent'],
    timestamp: Date.now()
  });

  // 5. 302 redirect (use 301 for permanent)
  res.redirect(302, longUrl);
});

// Cache hit ratio target: >90%
// Most popular URLs stay in cache
// LRU eviction for cache management

Redis caching handles the read-heavy load. Analytics are processed asynchronously via a queue so redirects remain fast. Use 302 for tracking clicks, 301 if caching is preferred.

Analytics & Click Tracking

// Analytics are processed asynchronously via a message queue
// to avoid slowing down the redirect response

// Analytics consumer (processes click events from queue)
async function processClickEvent(event) {
  const { shortCode, ip, userAgent, timestamp } = event;

  // 1. Increment click count (Redis for real-time)
  await redis.hincrby(`stats:${shortCode}`, 'clicks', 1);

  // 2. Store detailed analytics
  await db.analytics.create({
    shortCode,
    ip,
    country: await geoIp.lookup(ip),
    browser: parseUserAgent(userAgent).browser,
    os: parseUserAgent(userAgent).os,
    referrer: event.referrer || 'direct',
    timestamp: new Date(timestamp)
  });
}

// Analytics API
app.get('/api/analytics/:shortCode', auth, async (req, res) => {
  const { shortCode } = req.params;

  const [totalClicks, dailyClicks, topCountries, topBrowsers] = await Promise.all([
    redis.hget(`stats:${shortCode}`, 'clicks'),
    db.analytics.groupBy({
      where: { shortCode },
      by: ['date'],
      _count: true,
      orderBy: { date: 'desc' },
      take: 30
    }),
    db.analytics.groupBy({
      where: { shortCode },
      by: ['country'],
      _count: true,
      orderBy: { _count: { _all: 'desc' } },
      take: 10
    }),
    db.analytics.groupBy({
      where: { shortCode },
      by: ['browser'],
      _count: true
    })
  ]);

  res.json({ totalClicks, dailyClicks, topCountries, topBrowsers });
});

Analytics are decoupled from the redirect flow using a message queue. Click data is aggregated for dashboards showing daily trends, geographic distribution, and browser breakdown.

Key points

• 7 characters in Base62 gives 3.5 trillion unique URLs - more than enough for most services
• This is a read-heavy system (100:1 ratio) so Redis caching is critical for performance
• Use 302 redirects if you need analytics; 301 redirects get cached by browsers and skip your server

Concepts covered

Hashing, Base62 Encoding, Database Design, Caching, Redirection