Design Considerations for a Short URL Service

Background

Short URL services map a long URL to a short key and retrieve the original URL on request; the design must address storage, key generation, capacity planning, concurrency, networking, and security.

Data Structure

A simple key‑value store is sufficient, where the key is the generated short URL (unique) and the value is the original URL.

Algorithm

Keys can be generated by incrementing a counter and encoding it in base‑36 (26 letters + 10 digits). Before creating a new key, the service checks for existing values to avoid duplicates; a set can be used for duplicate detection, though more efficient methods may exist.

Key and Value Length

The original URL length can be limited to 500 characters. A 5‑character key supports over 60 million URLs, while a 6‑character key supports over 2.1 billion.

Data Capacity

Estimate storage requirements; if a single machine can hold all data, use a single‑node deployment, otherwise shard the data based on key range or modulo, balancing load and scalability.

Sharding Strategy

Range‑based sharding simplifies scaling but may cause uneven load; modulo‑based sharding balances load but makes scaling harder. A hybrid approach can start with modulo sharding and switch to range sharding for overflow keys.

Interface Design

Define the API contract for input and output of the service.

Concurrent Read/Write and Storage

Options include an STL hash map with locking, double‑buffered memory for read/write separation, or external in‑memory stores such as Redis or Memcached; asynchronous Redis operations can improve concurrency.

Network

For moderate traffic, a single‑threaded non‑blocking event loop suffices; for higher loads, multiple Reactor loops can be employed, delegating request processing to worker reactors or thread pools.

Security

Mitigate abuse by validating URLs, limiting request rates per source, and possibly restricting malicious patterns.

Case Study

The service at http://t.im/ uses a simple incremental base‑36 scheme, demonstrating limited concurrency and basic validation.