URL-Shortener-Dienst mit hoher Last designen

1. Übersicht

URL-Shortener ist ein bekanntes System-Design-Problem. Die Logik beschränkt sich auf das Mapping eines Kurzcodes zu einer langen URL. Die Schwierigkeit liegt in der Skalierung: zehntausende Redirects pro Sekunde, plötzlich virale Links und die Anforderung, niemals einen doppelten Code zu generieren.

Dieser Artikel behandelt den gesamten Prozess: Anforderungen festlegen, Last abschätzen, Datenmodell, API, Code-Generierung, Caching und kritische Punkte. Nach dem Lesen hast du ein Design-Framework mit Spring-Boot-3-Code, den du selbst implementieren oder zu Interviews mitnehmen kannst.

2. Anforderungen

2.1. Funktionale Anforderungen

Link-Kurzcode aus langer URL erstellen. Benutzer können einen eigenen Alias setzen, z.B. /sale-2026.
Beim Zugriff auf Kurzlink wird auf die ursprüngliche URL weitergeleitet.
Links können ein Ablaufdatum (expires_at) haben und vom Eigentümer deaktiviert werden.
Klicks pro Link statistisch erfassen. Einige Sekunden Verzögerung sind akzeptabel.

2.2. Skalierung

Angenommen 100 Millionen neue Links monatlich und Read/Write-Verhältnis von 100:1.

Schreiben:   100M / (30 * 86400s)  ≈ 40 Links/s   (Peak ×10 ≈ 400/s)
Lesen:       40 × 100              ≈ 4.000 rps   (Peak ×10 ≈ 40.000 rps)
Speicher 5 Jahre: 6 Mrd Links × ~500 Byte ≈ 3 TB
Codespace 7 Zeichen base62: 62^7 ≈ 3,5 Billionen  (ausreichend für 6 Mrd)

Aus diesen Zahlen ergeben sich zwei Erkenntnisse. Erstens ist das System read-heavy, daher ist Caching zentral für das Design. Zweitens ist der Write-Durchsatz niedrig, daher reicht ein PostgreSQL-Primary aus, noch kein Sharding nötig.

2.3. Einschränkungen

Redirect mit p99 < 20 ms.
Kurzcodes sind eindeutig und nicht sequenziell vorhersehbar, um zu verhindern, dass andere private Links erraten.
System kann weiterhin Redirects ausführen, wenn Analytics oder Kafka ausfallen.

3. Datenmodell und API

Benötigte Dependencies (Versionen verwaltet durch Spring Boot):

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-jdbc</artifactId>
    </dependency>
    <dependency>
        <groupId>org.postgresql</groupId>
        <artifactId>postgresql</artifactId>
        <scope>runtime</scope>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.kafka</groupId>
        <artifactId>spring-kafka</artifactId>
    </dependency>
    <dependency>
        <groupId>com.github.ben-manes.caffeine</groupId>
        <artifactId>caffeine</artifactId>
    </dependency>
</dependencies>

PostgreSQL-Schema:

CREATE TABLE links (
    code        VARCHAR(16) PRIMARY KEY,
    long_url    TEXT        NOT NULL,
    owner_id    BIGINT,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
    expires_at  TIMESTAMPTZ,
    disabled    BOOLEAN     NOT NULL DEFAULT false
);
CREATE INDEX idx_links_owner ON links (owner_id, created_at DESC);

CREATE SEQUENCE link_id_seq START 1 INCREMENT BY 1000;

Erklärung der wichtigsten Entscheidungen:

code ist Primary Key. Die häufigste Query ist WHERE code = ?, daher nutzt sie direkt den Primary-Key-Index.
idx_links_owner unterstützt das “Meine Links”-Dashboard.
link_id_seq inkrementiert um 1000. Bei jedem Aufruf von nextval erhält die Anwendung einen ganzen Block von IDs (Abschnitt 4.2).

Zwei Haupt-APIs:

POST /api/links          {"url": "https://shop.vn/...", "alias": null}
  -> 201 {"code": "0bX3kQz", "shortUrl": "https://nonla.ly/0bX3kQz"}
  -> 409 wenn Alias bereits existiert

GET  /{code}
  -> 302 Location: https://shop.vn/...
  -> 404 wenn nicht existiert / abgelaufen / deaktiviert

Wichtig: Nutze 302, nicht 301. Browser cachen 301 dauerhaft. Dann verlierst du Click-Daten und kannst bereits verbreitete Links nicht deaktivieren.

4. Code-Generierung

4.1. Strategie wählen

Methode	Vorteil	Nachteil
URL-Hash (MD5 dann 7 Zeichen)	Kein Zustand nötig	Mögliche Kollisionen, muss erneut versuchen
Zufällig 7 Zeichen	Einfach	Je mehr Links, desto wahrscheinlicher Kollision, jede Erstellung muss DB prüfen
Counter + base62	Nie Kollision	Lässt Reihenfolge erkennen, braucht zentralisierte ID-Quelle

Dieser Artikel wählt die dritte Methode und behebt beide Nachteile. Um Reihenfolge zu verbergen, wird die ID durch eine Bijektion durchmischt. Um die Abhängigkeit von zentralisierter ID-Quelle zu verringern, werden IDs in Blöcken vergeben.

import java.math.BigInteger;

public final class ShortCode {
    private static final String ALPHABET =
            "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int LENGTH = 7;
    private static final BigInteger SPACE = BigInteger.valueOf(62).pow(LENGTH);
    // Ungerade, nicht teilbar durch 31 => teilerfremd zu 62^7
    private static final BigInteger MULTIPLIER = BigInteger.valueOf(1_580_030_173L);

    private ShortCode() {}

    public static String of(long id) {
        if (id < 0 || id >= SPACE.longValue()) {
            throw new IllegalArgumentException("ID außerhalb des Codespace: " + id);
        }
        long mixed = BigInteger.valueOf(id).multiply(MULTIPLIER).mod(SPACE).longValue();
        char[] out = new char[LENGTH];
        for (int i = LENGTH - 1; i >= 0; i--) {
            out[i] = ALPHABET.charAt((int) (mixed % 62));
            mixed /= 62;
        }
        return new String(out);
    }
}

Wie es funktioniert:

Die Multiplikation modulo id × MULTIPLIER mod 62^7 ist eine Bijektion, da MULTIPLIER teilerfremd zu 62^7 ist. Jede ID erzeugt exakt einen Code, und zwei verschiedene IDs erzeugen nie den gleichen Code.
Die Schleife konvertiert die Zahl zu base62 und füllt mit Nullen links auf, sodass der Code immer genau 7 Zeichen ist.
ID 1 und ID 2 produzieren unterschiedliche Codes schon beim zweiten Zeichen, daher ist es für andere schwer, den nächsten Link zu erraten.
BigInteger verhindert Integer-Overflow bei der Multiplikation. Bei 400 Schreib/s ist dieser Overhead vernachlässigbar.

Diese Methode macht Codes schwer zu erraten, aber nicht verschlüsselt. Wer MULTIPLIER kennt, kann es zurückrechnen. Wirklich private Links brauchen zusätzliche Authentifizierung.

4.2. IDs in Blöcken vergeben

Wenn du DB bei jeder ID abfragst, wird die Primary zum Bottleneck. Stattdessen holt sich jede Instance einen Block von 1000 IDs und verteilt sie in-memory:

import java.util.concurrent.locks.ReentrantLock;
import org.springframework.jdbc.core.JdbcTemplate;
import org.springframework.stereotype.Component;

@Component
public class IdBlockAllocator {
    private static final int BLOCK_SIZE = 1000; // muss INCREMENT BY entsprechen
    private final JdbcTemplate jdbc;
    private final ReentrantLock lock = new ReentrantLock();
    private long next;
    private long end;

    public IdBlockAllocator(JdbcTemplate jdbc) {
        this.jdbc = jdbc;
    }

    public long nextId() {
        lock.lock();
        try {
            if (next >= end) {
                Long start = jdbc.queryForObject("SELECT nextval('link_id_seq')", Long.class);
                next = start;
                end = start + BLOCK_SIZE;
            }
            return next++;
        } finally {
            lock.unlock();
        }
    }
}

Wichtige Punkte:

nextval ist atomar. Zwei Instances bekommen nie den gleichen Block, daher kein verteiltes Locking nötig.
Bei 400 Schreib/s kontaktiert jede Instance nur wenige Male pro Sekunde die DB.
Code nutzt ReentrantLock statt synchronized. Mit Java 21 werden virtuelle Threads an den Carrier Thread “gepinnt”, wenn sie auf I/O in einem synchronized-Block warten.
Instance-Neustarts verschwenden den Rest des Blocks. Der Codespace hat 3,5 Billionen Werte, dies ist akzeptabel.

5. Link-Erstellungsfluss

import java.net.URI;
import java.time.Duration;
import org.springframework.dao.DuplicateKeyException;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.jdbc.core.JdbcTemplate;
import org.springframework.stereotype.Service;

@Service
public class LinkWriteService {
    static final String KEY = "link:";
    private final JdbcTemplate jdbc;
    private final StringRedisTemplate redis;
    private final IdBlockAllocator allocator;

    public LinkWriteService(JdbcTemplate jdbc, StringRedisTemplate redis, IdBlockAllocator allocator) {
        this.jdbc = jdbc;
        this.redis = redis;
        this.allocator = allocator;
    }

    public String create(String longUrl, String alias, Long ownerId) {
        String scheme = URI.create(longUrl).getScheme();
        if (!"http".equals(scheme) && !"https".equals(scheme)) {
            throw new IllegalArgumentException("Nur http/https akzeptiert");
        }
        String code = (alias != null) ? alias : ShortCode.of(allocator.nextId());
        try {
            jdbc.update("INSERT INTO links(code, long_url, owner_id) VALUES (?, ?, ?)",
                    code, longUrl, ownerId);
        } catch (DuplicateKeyException e) {
            throw new AliasTakenException(code);
        }
        redis.opsForValue().set(KEY + code, longUrl, Duration.ofHours(24));
        return code;
    }
}

class AliasTakenException extends RuntimeException {
    AliasTakenException(String code) { super("Alias bereits vergeben: " + code); }
}

Der Verarbeitungsfluss hat vier Schritte:

Scheme validieren, um javascript: oder file: zu blockieren. Ohne diesen Schritt wird dein Service zum Malware-Verbreitungstool.
Code abrufen: eigengesetzten Alias verwenden oder Code generieren.
INSERT. Die Primary-Key-Constraint ist die letzte Verteidigungslinie gegen doppelte Codes.
Sofort in Redis schreiben (write-through), damit der erste Redirect nicht in die DB gehen muss.

In der Produktion sollten selbstgesetzte Alias andere Zeichen oder Längenvorgaben haben als Auto-generierte Codes, z.B. muss - enthalten sein oder mindestens 8 Zeichen. Ohne das könnte der Alias eines Benutzers einen Code “reservieren”, den der Generator später hätte erstellen können, was zu DuplicateKeyException führt – obwohl der Generator dies nicht darf.

6. Redirect-Fluss und mehrstufiges Caching

Bei 40.000 rps in Spitzenlast muss die Mehrzahl ohne DB verarbeitet werden. Wir nutzen drei Schichten: Caffeine in der JVM, gemeinsames Redis, dann PostgreSQL.

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import java.time.Duration;
import java.util.List;
import java.util.Optional;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.jdbc.core.JdbcTemplate;
import org.springframework.stereotype.Service;

@Service
public class LinkReadService {
    private static final String NOT_FOUND = ""; // Sentinel für Negative Cache
    private final Cache<String, String> local = Caffeine.newBuilder()
            .maximumSize(100_000)
            .expireAfterWrite(Duration.ofSeconds(30))
            .build();
    private final JdbcTemplate jdbc;
    private final StringRedisTemplate redis;

    public LinkReadService(JdbcTemplate jdbc, StringRedisTemplate redis) {
        this.jdbc = jdbc;
        this.redis = redis;
    }

    public Optional<String> resolve(String code) {
        String url = local.get(code, this::loadFromRedisOrDb);
        return url.isEmpty() ? Optional.empty() : Optional.of(url);
    }

    private String loadFromRedisOrDb(String code) {
        String key = LinkWriteService.KEY + code;
        String cached = redis.opsForValue().get(key);
        if (cached != null) return cached;

        List<String> rows = jdbc.queryForList("""
                SELECT long_url FROM links
                WHERE code = ? AND NOT disabled
                  AND (expires_at IS NULL OR expires_at > now())""", String.class, code);
        String url = rows.isEmpty() ? NOT_FOUND : rows.getFirst();
        redis.opsForValue().set(key, url, url.isEmpty() ? Duration.ofMinutes(5) : Duration.ofHours(24));
        return url;
    }
}

Wichtige Punkte:

local.get(code, loader) von Caffeine macht gleichzeitige Loads für den gleichen Schlüssel zu einer. Wenn 5.000 Requests nach einem fehlenden Code fragen, geht nur ein Thread zu Redis/DB. Die übrigen Threads warten auf das Ergebnis. Das ist die Cache-Stampede-Vermeidung auf Instance-Ebene.
Negative Caching: Nicht existierende Codes werden auch als leere Strings 5 Minuten lang gecacht. So können Bots, die Random-Codes scannen, die DB nicht überlasten.
Caffeine cached null nicht, daher nutzen wir das Sentinel "" statt null.

Der Controller gibt 302 zurück und pushed Click-Events zu Kafka:

import java.net.URI;
import java.util.Map;
import org.springframework.http.HttpStatus;
import org.springframework.http.ResponseEntity;
import org.springframework.kafka.core.KafkaTemplate;
import org.springframework.web.bind.annotation.*;

@RestController
public class LinkController {
    private final LinkWriteService writer;
    private final LinkReadService reader;
    private final KafkaTemplate<String, String> kafka;

    public LinkController(LinkWriteService writer, LinkReadService reader,
                          KafkaTemplate<String, String> kafka) {
        this.writer = writer;
        this.reader = reader;
        this.kafka = kafka;
    }

    public record CreateLinkRequest(String url, String alias) {}

    @PostMapping("/api/links")
    public ResponseEntity<Map<String, String>> create(@RequestBody CreateLinkRequest req) {
        String code = writer.create(req.url(), req.alias(), null);
        return ResponseEntity.status(HttpStatus.CREATED)
                .body(Map.of("code", code, "shortUrl", "https://nonla.ly/" + code));
    }

    @GetMapping("/{code:[0-9a-zA-Z-]{1,16}}")
    public ResponseEntity<Void> redirect(@PathVariable String code) {
        return reader.resolve(code)
                .map(url -> {
                    kafka.send("link-clicks", code, String.valueOf(System.currentTimeMillis()));
                    return ResponseEntity.status(HttpStatus.FOUND).location(URI.create(url)).<Void>build();
                })
                .orElse(ResponseEntity.notFound().build());
    }

    @ExceptionHandler(AliasTakenException.class)
    ResponseEntity<String> conflict(AliasTakenException e) {
        return ResponseEntity.status(HttpStatus.CONFLICT).body(e.getMessage());
    }
}

kafka.send ist asynchron, der Redirect muss nicht auf den Broker warten. Ein separater Consumer sammelt Events pro code einige Sekunden lang, dann batch-geschrieben zur Statistik-Tabelle. Producer-Konfiguration für niedrige Latenz:

spring.kafka.producer.acks=1
spring.kafka.producer.properties.linger.ms=20
spring.kafka.producer.properties.max.block.ms=50

max.block.ms=50 verhindert, dass der Redirect-Thread lange blockiert, wenn der Broker ausfällt, was der Anforderung “Analytics fehlgeschlagen, aber Redirects laufen weiter” entspricht. Wir akzeptieren einige verlorene Click-Events in diesem Fall.

7. Schwierige Punkte und Lösungen

7.1. Race Conditions

Zwei Nutzer setzen denselben Alias: Nicht zuerst SELECT dann INSERT. Beide könnten “nicht vorhanden” sehen und dann schreiben. Lass die DB Unique-Constraint entscheiden und fange DuplicateKeyException wie in Abschnitt 5 ab.
Mehrere Instances generieren Codes: Sequence vergibt Blöcke an jede Instance einzeln, keine Race Condition.

7.2. Konsistenz

Sofort nach Erstellung lesen: Wenn von Read-Replica gelesen wird, kann Replication-Lag zu 404 führen. Write-through zu Redis beim Erstellen versteckt diesen Lag.
Link deaktivieren: DB aktualisieren, dann Redis-Key löschen. Caffeine behält alte Werte bis zu 30s pro Instance. Für sofortige Blockierung (z.B. Phishing-Link) publish ein Invalidierungs-Event über Redis Pub/Sub oder Kafka, damit Instance-Caches gelöscht werden.
Ablauf: TTL des Cache sollte min(24h, expires_at - now) sein. Sonst redirect abgelaufene Links bis zu 24h länger.

7.3. Last-Spitzen

Hot Key: Ein viraler Link konzentriert den gesamten Traffic auf einen Redis-Shard. Caffeine lokal absorbiert die meiste Last. Jede Instance fragt Redis ungefähr einmal pro 30 Sekunden pro Key.
Kalt-Start: Neue Instance hat keine Caffeine-Daten, aber Load-Coalescing (Abschnitt 6) schützt Redis.
Spam beim Link-Erstellen: Rate-Limiting pro API-Key oder IP, z.B. Token-Bucket auf Redis, vor LinkWriteService.

8. Code-Generierungs-Tests

Die wichtigste Eigenschaft: Codes sind eindeutig, feste Länge und nicht sequenziell:

import static java.util.stream.Collectors.toSet;
import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

import java.util.Set;
import java.util.stream.LongStream;
import org.junit.jupiter.api.Test;

class ShortCodeTest {

    @Test
    void generatesCorrectLengthAndCharacters() {
        assertThat(ShortCode.of(1)).hasSize(7).matches("[0-9a-zA-Z]{7}");
    }

    @Test
    void noCollisionsInHundredThousandConsecutiveIds() {
        Set<String> codes = LongStream.range(0, 100_000).mapToObj(ShortCode::of).collect(toSet());
        assertThat(codes).hasSize(100_000);
    }

    @Test
    void consecutiveIdsDoNotProduceConsecutiveCodes() {
        assertThat(ShortCode.of(1).substring(0, 5)).isNotEqualTo(ShortCode.of(2).substring(0, 5));
    }

    @Test
    void rejectsIdOutsideCodespace() {
        assertThatThrownBy(() -> ShortCode.of(-1)).isInstanceOf(IllegalArgumentException.class);
    }
}

Der zweite Test prüft an einer Stichprobe, beweist nicht die Bijektivität. Die Bijektivität kommt aus Mathematik (gcd = 1). Der Test schützt nur davor, dass jemand MULTIPLIER versehentlich zu einer geraden Zahl ändert.

9. Häufige Fehler und wann nicht über-engineern

Wichtig: MULTIPLIER oder ALPHABET nach Release zu ändern führt zu Codes-Duplikaten zwischen neuen und alten IDs. Behandle sie als Konstanten.

Jeden Click direkt in links schreiben (UPDATE ... SET clicks = clicks + 1) erzeugt Row-Lock an viralen Links. Sammel über Kafka.
Caffeine unbegrenzt wachsen lassen führt zu OutOfMemoryError unter Bombardement mit zufälligen Codes.
Bei internen Produkten mit ein paar hundert Links täglich reicht eine PostgreSQL-Tabelle und ein Controller. Redis, Kafka und Block-basierte ID-Vergabe sind nur nötig bei echter Last.

10. Fazit

URL-Shortener unter hoher Last dreht sich um drei Entscheidungen. Code-Generierung via Counter mit Block-Vergabe und Bijektion, sodass Codes eindeutig aber schwer zu erraten sind. Mehrstufiges Caching mit Negative Caching und Load-Coalescing, um Hot Keys und Scanner-Bots zu handhaben. Alles Nicht-essenzielle (wie Click-Statistik) raus aus dem Redirect-Pfad über Kafka.

Beginne mit der Skalierungs-Abschätzung. Die Zahlen aus Abschnitt 2 sagen dir, wann jede Schicht nötig ist, statt alles von Tag eins zu bauen.