Designing a URL Shortener: From Estimation to Short Code Generation
This article details the system design process for a URL shortener like Bitly, emphasizing initial estimations and common pitfalls. It covers architectural decisions for handling high read traffic, choosing between different short code generation strategies, and optimizing the read path with caching and appropriate HTTP redirects. The core focus is on practical trade-offs and deriving architectural choices from quantitative analysis.
Read original on Dev.to #systemdesignSystem Requirements and Initial Estimation
The design of a URL shortener primarily involves two operations: shortening a long URL and redirecting from a short URL to its original. Before diving into architecture, it's crucial to perform estimations for user activity (reads/writes), storage, and latency. The article models user behavior to derive read and write RPS, establishing a 10:1 read/write ratio. This ratio heavily influences subsequent design decisions, prioritizing optimizations for the read path. Storage estimations also reveal that a single, well-provisioned database can handle projected data volumes for years, negating the immediate need for sharding based on storage alone.
- Reads (clicks): 250M clicks/day, approximately 2,900 RPS.
- Writes (creating links): 25M creates/day, approximately 290 RPS.
- Storage: 1.37 TB/year for 9.1 billion records, fitting within a single database.
- Latency Target: 100-200 ms for redirects.
Core Architecture and Short Code Generation Strategies
The proposed architecture features stateless application servers behind a load balancer, utilizing Redis for caching hot redirects and a relational database for persistent storage and ID generation. A critical design challenge is generating unique, short codes. The article explores three approaches: hashing the long URL, generating random strings, and using a counter encoded in Base62. Hashing is identified as a "trap" because it deterministically maps the same long URL to the same short code, preventing per-request analytics, expiry, and ownership.
The Hashing Trap
Hashing the long URL ensures the same input always yields the same short code. However, this conflates multiple distinct requests for the same long URL, making it impossible to manage unique expiry times, track individual click analytics, or assign different ownership to each shorten request. Each request needs its own record, meaning the short code must be independent of the URL's content.
Between random strings and a Base62 counter, the latter is chosen for its guarantee of uniqueness by construction, eliminating collision retries. A 7-character Base62 code offers 3.5 trillion unique codes, sufficient for over 380 years at projected rates. For distributed counters, the article opts for the database's auto-increment feature due to the manageable write load (290 RPS), avoiding the complexity of ID ranges which would be an over-engineering for the given scale.
sequenceDiagram
participant C as Client
participant S as App Server
participant DB as Database
C->>S: POST /urls (longUrl, expiresAt)
S->>DB: nextval(url_seq)
DB-->>S: 125
S->>S: base62(125) = "21"
S->>DB: INSERT shortCode, longUrl, createdBy, createdAt, expiresAt
DB-->>S: OK
S-->>C: 201 shortUrl = sho.rt/21Optimizing the Read Path and Future Considerations
With a 10:1 read/write ratio, making the redirect path fast is paramount. This is achieved by indexing the short code (as a primary key) and caching hot `shortCode -> longUrl` mappings in Redis. A HTTP 302 redirect (temporary) is preferred over 301 (permanent) to ensure every click hits the server for accurate analytics. Future enhancements include addressing guessable sequential codes (e.g., via obfuscation), implementing background jobs for expiry cleanup, and defining cache eviction policies.