Skip to main content

URL Shortener

Turn a long URL into a short code and back again. The whole problem is really one question: how do you generate a code that's short, doesn't collide, and doesn't require a lookup just to create it.

Requirements​

Functional

  • A caller submits a long URL and gets back a short code.
  • Visiting the short code redirects to the original long URL.
  • The same long URL submitted twice may produce two different short codes (no dedup requirement) - but a given short code must always resolve to the same long URL.
  • A short code should be reasonably short (six or seven characters is the usual target).

Non-functional

  • Generating a code must not require scanning existing codes for a collision under normal operation; a collision, if it happens, must be detected and retried.
  • Swapping the encoding scheme (base62 counter vs. a hash-based approach) must not require changing UrlShortenerService or UrlRepository.

Design​

UrlShortenerService owns the flow - generate a code, check it's free, store the mapping - but never owns the encoding itself. A CodeGenerator interface produces candidate codes; swapping a counter-based base62 generator for a hash-based one is a constructor argument, not a rewrite.

CallerUrlShortenerServiceCodeGeneratorUrlRepositoryshorten(longUrl)1nextCode()2exists(code)3nextCode() (retry)4save(code, longUrl)5
  1. 1The caller only supplies the long URL - never a code, never an encoding choice.
  2. 2The service asks the generator for a candidate without knowing how it was produced.
  3. 3The service checks the repository for a collision before committing to the candidate.
  4. 4On the rare collision, the service asks again - the generator has no idea a retry happened.
  5. 5Once a free code is found, the mapping is persisted and returned to the caller.

Collision handling lives entirely in the service's retry loop: it asks the generator for a code, asks the repository if it's taken, and only loops if both come back with a conflict - the generator itself never needs to know about collisions.

Class diagram​

«interface»CodeGenerator+ nextCode(): string«interface»UrlRepository+ exists(code): bool+ save(code, longUrl): void+ find(code): stringUrlShortenerService- generator: CodeGenerator- repo: UrlRepository+ shorten(longUrl): string+ resolve(code): stringBase62CounterGenerator- counter: long+ nextCode(): stringHashCodeGenerator+ nextCode(): stringInMemoryUrlRepository+ exists(code): bool+ save(code, longUrl): void+ find(code): string
implementsuses
UrlShortenerService asks a CodeGenerator for a candidate and a UrlRepository whether it's free, retrying only on collision.

Code​

import java.security.MessageDigest;
import java.util.*;
 
interface CodeGenerator {
String nextCode();
}
 
class Base62CounterGenerator implements CodeGenerator {
private static final String ALPHABET =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
private long counter = 1;
 
public synchronized String nextCode() {
long value = counter++;
StringBuilder sb = new StringBuilder();
while (value > 0) {
sb.append(ALPHABET.charAt((int) (value % 62)));
value /= 62;
}
return sb.reverse().toString();
}
}
 
class HashCodeGenerator implements CodeGenerator {
private final String longUrl;
private int salt = 0;
 
HashCodeGenerator(String longUrl) {
this.longUrl = longUrl;
}
 
public String nextCode() {
try {
MessageDigest digest = MessageDigest.getInstance("SHA-256");
byte[] hash = digest.digest((longUrl + salt++).getBytes());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 6; i++) {
sb.append(String.format("%02x", hash[i]));
}
return sb.substring(0, 7);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
 
interface UrlRepository {
boolean exists(String code);
void save(String code, String longUrl);
String find(String code);
}
 
class InMemoryUrlRepository implements UrlRepository {
private final Map<String, String> codeToUrl = new HashMap<>();
 
public boolean exists(String code) {
return codeToUrl.containsKey(code);
}
 
public void save(String code, String longUrl) {
codeToUrl.put(code, longUrl);
}
 
public String find(String code) {
return codeToUrl.get(code);
}
}
 
class UrlShortenerService {
private final CodeGenerator generator;
private final UrlRepository repo;
 
UrlShortenerService(CodeGenerator generator, UrlRepository repo) {
this.generator = generator;
this.repo = repo;
}
 
String shorten(String longUrl) {
String code;
do {
code = generator.nextCode();
} while (repo.exists(code));
repo.save(code, longUrl);
return code;
}
 
String resolve(String code) {
String longUrl = repo.find(code);
if (longUrl == null) throw new NoSuchElementException("Unknown code: " + code);
return longUrl;
}
}

Design decisions​

  • CodeGenerator is a Strategy, not a static method on the service. A counter-based base62 generator and a hash-of-the-URL generator have completely different collision profiles (the counter one, correctly implemented, never collides; the hash-based one occasionally does) - keeping generation behind an interface means the service's retry logic works for either without caring which is plugged in.
  • Collision checking happens in the service, not inside the generator. A generator's only job is "produce a candidate code." Whether that candidate is already taken is a question about the repository's current state, which the generator has no business knowing about - so the retry loop belongs one layer up.
  • UrlRepository is an interface even though this page only shows an in-memory map. Swapping in a real key-value store later means implementing one interface, not hunting down every place the service touched a HashMap directly.
  • What's missing for a real system: a counter-based generator needs the counter itself to be a distributed, monotonically increasing sequence (not a single in-process long) once there's more than one service instance, and a real deployment would put a cache in front of the repository, since redirects vastly outnumber new-URL submissions.

Common follow-ups​

  • How do you make the counter-based generator work across multiple service instances? The counter can't stay a single in-process value once there's more than one instance - it needs to become a distributed, monotonically increasing sequence, such as a database sequence or pre-allocated ranges handed to each instance, which the page's own gap analysis calls out.
  • Why doesn't HashCodeGenerator need its own retry-avoidance logic? Because the service's retry loop already handles collisions generically - the generator's only obligation is to produce a different candidate when asked again, via its incrementing salt. Whether a candidate was already taken is entirely the repository's and service's concern.
  • How would you add expiry to short URLs? An expiresAt field on whatever the repository stores per code, checked in resolve() before returning the long URL - this only touches UrlRepository's implementation and UrlShortenerService.resolve, nothing about CodeGenerator, since expiry has nothing to do with how a code was generated.
  • Redirects vastly outnumber new-URL submissions - where would a cache go? In front of UrlRepository.find, most cleanly as a decorator implementing the same interface (a caching repository that checks a fast cache before delegating to the real one). UrlShortenerService wouldn't change at all, since it only depends on the interface.

Check yourself

Question 1 of 4

Why is CodeGenerator an interface instead of a static method with a flag for "use hashing"?

0%0 of 154 pages studied