How Short URLs Work: Theory, Design, and a Java Implementation

Introduction

We often receive spam SMS that contain short links, typically displayed as short URLs.

Short URLs are used because they are concise, look cleaner, enable easy statistics collection, and hide query parameters for security.

Short – essential for platforms with character limits such as SMS and micro‑blogs.

Neat – a compact link is more user‑friendly than a long query string.

Statistical – clicks can be tracked and analyzed.

Secure – underlying parameters are not exposed.

These reasons explain why most spam messages contain short URLs.

Short URL Basic Principle

The short‑URL workflow consists of the following steps:

A service maps a long URL to a short URL, e.g., www.baidu.com → www.t.cn/1 .

The short URL is embedded in the SMS or other content.

The user clicks the short URL, the browser follows a 301/302 redirect to the original long URL.

The target content is displayed.

This article focuses on the first step: converting a long URL into a short one.

Service Design

An ideal solution would be an algorithm that uniquely converts every long URL into a short URL and can reverse the process, but such a universal algorithm does not exist.

The practical approach is to use an ID generator (a “ticket dispenser”). Each new long URL receives an incremented number, which is then returned as a short URL, e.g., the first URL becomes www.x.cn/0, the second www.x.cn/1, and so on.

How to store the mapping?

The mapping must be persisted, typically in a relational database such as MySQL using an auto‑increment primary key.

How to guarantee one‑to‑one mapping?

Simple incremental IDs do not guarantee a unique short URL for identical long URLs; repeated requests for the same long URL will produce different short URLs. Achieving strict one‑to‑one mapping requires additional storage or caching strategies.

Short URL storage

Numeric IDs are often converted to a base‑32 representation to shorten the URL length. Storing the value as a decimal number reduces space usage and simplifies range queries while still allowing conversion to other bases.

High concurrency

Direct writes to MySQL become a bottleneck under high request volume. Common optimizations include:

Cache

Cache popular or recent long URLs in memory or a fast key‑value store like Redis. If a request hits the cache, the short URL can be returned without generating a new one.

Batch issuance

Instead of fetching a single ID for each request, retrieve a block of IDs (e.g., 10 000) from MySQL, allocate them in memory, and write back the block when it is nearly exhausted. This reduces the frequency of database access.

Distributed

A single ID generator is a single point of failure. A distributed design can assign non‑contiguous ranges to multiple services (e.g., one service issues numbers ending with 0, another with 1, etc.), allowing each node to operate independently without constant synchronization.

Implementation

The following Java utility demonstrates a simple short‑URL service that uses Redis for storage and caching instead of MySQL for brevity.

package util;

import redis.clients.jedis.Jedis;

/**
 * Created by pfliu on 2019/06/23.
 */
public class ShortUrlUtil {
    private static final String SHORT_URL_KEY = "SHORT_URL_KEY";
    private static final String LOCALHOST = "http://localhost:4444/";
    private static final String SHORT_LONG_PREFIX = "short_long_prefix_";
    private static final String CACHE_KEY_PREFIX = "cache_key_prefix_";
    private static final int CACHE_SECONDS = 1 * 60 * 60;

    private final String redisConfig;
    private final Jedis jedis;

    public ShortUrlUtil(String redisConfig) {
        this.redisConfig = redisConfig;
        this.jedis = new Jedis(this.redisConfig);
    }

    public String getShortUrl(String longUrl, Decimal decimal) {
        // Query cache
        String cache = jedis.get(CACHE_KEY_PREFIX + longUrl);
        if (cache != null) {
            return LOCALHOST + toOtherBaseString(Long.valueOf(cache), decimal.x);
        }
        // Auto‑increment
        long num = jedis.incr(SHORT_URL_KEY);
        // Persist mapping (could be MySQL)
        jedis.set(SHORT_LONG_PREFIX + num, longUrl);
        // Write cache
        jedis.setex(CACHE_KEY_PREFIX + longUrl, CACHE_SECONDS, String.valueOf(num));
        return LOCALHOST + toOtherBaseString(num, decimal.x);
    }

    /** Character set for base conversion */
    final static char[] digits = {
        '0','1','2','3','4','5','6','7','8','9',
        'A','B','C','D','E','F','G','H','I','J','K','L',
        'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
        'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

    /** Convert a decimal number to another base */
    private String toOtherBaseString(long n, int base) {
        long num = (n < 0) ? ((long)2 * 0x7fffffff) + n + 2 : n;
        char[] buf = new char[32];
        int charPos = 32;
        while ((num / base) > 0) {
            buf[--charPos] = digits[(int)(num % base)];
            num /= base;
        }
        buf[--charPos] = digits[(int)(num % base)];
        return new String(buf, charPos, (32 - charPos));
    }

    enum Decimal {
        D32(32), D64(64);
        int x;
        Decimal(int x) { this.x = x; }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            System.out.println(new ShortUrlUtil("localhost").getShortUrl("www.baidudu.com", Decimal.D32));
            System.out.println(new ShortUrlUtil("localhost").getShortUrl("www.baidu.com", Decimal.D64));
        }
    }
}