koded

Posted on Jul 19

Designing a Collision-Resistant Deployment Naming Service

#algorithms #architecture #systemdesign #webdev

This started as a random thought while solving coding problems.

Imagine you're building something like Vercel or Render.

A user deploys a project called:

portfolio

If nobody has used it before, great.

portfolio

But if someone already owns it, you need something like:

portfolio-km82x

Simple enough.

Until you start asking questions.

What if two users deploy portfolio at the exact same time?
How do you stop collisions?
How do you make the suffix human-readable?
Should it always be five characters?
How do you avoid ugly strings like 111 or aaa?
What happens when there are already two million portfolio-* deployments?

That innocent problem suddenly becomes a mix of algorithms, probability, concurrency, and system design.

This is the approach I ended up with.

The Question

The rules for a valid suffix are highly specific:

Consist only of lowercase English letters (a-z) and digits (0-9).
The first and last characters must be lowercase letters.
The suffix length must be at least 4 characters.
No more than two consecutive digits may appear (e.g., ab12 is fine, ab123 is illegal).
No three consecutive identical characters may appear (e.g., aaa or 111 are illegal).
It cannot contain reserved substrings: admin, root, api, www.

Thinking About It

My first instinct was the obvious one.

Generate a random string.

Validate it.

If it fails, generate another.

Something like:

while True:
    suffix = random_string()
    if valid(suffix):
        break

The more I thought about it, the less I liked it.

If I already know the rules ahead of time, why generate invalid strings at all?

Instead, I flipped the problem around.

Rather than validating after generation, I made the generator incapable of producing illegal candidates.

Breaking the Problem Down

Before writing any code, I tried separating responsibilities.

Instead of one giant function, the solution naturally became four small pieces.

generate_suffix()
       ↓
   build_slug()
       ↓
try_insert_slug()
       ↓
retry if collision

Each function only knows one thing.

The generator knows nothing about the database.

The database knows nothing about suffix generation.

The retry loop coordinates everything.

That separation ended up making the implementation much simpler.

Architecture

One thing I wanted to avoid was this:

if slug not in database:
    database.insert(slug)

It looks innocent.

It also breaks the moment two threads execute it simultaneously.

Instead, I moved the uniqueness check inside the database itself.

Now the application never asks:

"Does this exist?"

It simply says:

"Try inserting this."

The database either accepts it or rejects it atomically.

Implementation

The Database Layer

To handle this purely in-memory without pulling in external infrastructure, we wrap our storage in an object that manages state via a thread lock (threading.Lock).

import threading
import secrets
from typing import Set

class InMemoryDatabase:
    def __init__(self):
        self._slug_records: Set[str] = set()
        self._lock = threading.Lock()

    def try_insert_slug(self, slug: str) -> bool:
        # Why this exists:
        # We acquire a lock so only ONE thread can execute this block at a time.
        # If the slug is taken, we signal a collision immediately.
        with self._lock:
            if slug in self._slug_records:
                return False  

            self._slug_records.add(slug)
            return True

The Generator & Retry Loop

def generate_slug(db: InMemoryDatabase, requested: str) -> str:
    LETTERS = "abcdefghijklmnopqrstuvwxyz"     
    DIGITS = "1234567890"                        
    BANNED_SUBSTRINGS = ["admin", "root", "api", "www"]

    # Try to claim the exact name requested immediately.
    if db.try_insert_slug(requested):
        return requested

    def generate_candidate_suffix(retries: int) -> str:
        suffix = []

        # Adaptive length:
        # If a namespace is crowded, scaling the length up based on retries 
        # expands the search space and keeps the retry rate low.
        length = 5 + (retries // 3) 

        for i in range(length):
            allowed = list(LETTERS + DIGITS)

            # Platform rule:
            # First and last characters must always be letters.
            if i == 0 or i == length - 1:
                allowed = list(LETTERS)

            # Lookback filtering:
            # 1. If the last two are identical, block a third.
            # 2. If the last two are digits, purge ALL digits from the pool.
            if len(suffix) >= 2 and suffix[-1] == suffix[-2]:
                if suffix[-1] in allowed: 
                    allowed.remove(suffix[-1])

            if len(suffix) >= 2 and suffix[-1].isdigit() and suffix[-2].isdigit():
                allowed = [c for c in allowed if not c.isdigit()]

            suffix.append(secrets.choice(allowed))

        return "".join(suffix)

    retries = 0
    while True:
        suf = generate_candidate_suffix(retries)

        # Guard rail against global blacklisted terms
        if any(banned in suf for banned in BANNED_SUBSTRINGS):
            retries += 1
            continue

        candidate = f"{requested}-{suf}"

        # Write-intent check:
        # Try to write it directly. If another thread beat us to this specific suffix, 
        # the database returns False, and we loop cleanly to try again.
        if db.try_insert_slug(candidate):
            return candidate

        retries += 1

Why This Works

There are three ideas carrying most of the solution.

1. Generate valid candidates

Instead of generating random strings and rejecting half of them, the generator filters its character pool while building the suffix. That removes entire classes of invalid states.

2. Let storage own uniqueness

The generator never worries about collisions. It creates candidates. The storage layer decides whether they're acceptable. This keeps both components independent.

3. Retry is cheap

A collision isn't an error. It's just another iteration. As the namespace becomes more crowded, the suffix length gradually increases, expanding the search space without changing the rest of the algorithm.

Things I'd Change In Production

Move uniqueness to a real database: Replace the in-memory set with a persistent storage engine using a proper UNIQUE index constraint on the slug column.
Make banned words configurable: Pull the BANNED_SUBSTRINGS list out of hardcoded arrays into an external config or cache layer so it can be updated dynamically.
Use a Base32 alphabet: Explicitly modify the character pool to use a Base32 variations index that excludes visually confusing symbols like 1, l, 0, and O to optimize readability.
Add rate limiting: Enforce API-level rate limiting on a per-user basis to prevent brute-force naming attacks from exhausting the namespace.
Add metrics & tracing: Emit performance telemetry capturing collision rates and the number of generation cycles per request to monitor namespace saturation over time.

Complexity

Step	Complexity
Lookup	`O(1)`
Generation	`O(k)` where $k$ is suffix length
Validation	`O(k)`
Insertion	`O(1)`
Overall	Expected `O(1)`

Note: The overall time complexity is an expected $O(1)$ because our adaptive suffix length ensures that even as the database grows, the probability of multiple sequential collisions drops exponentially.

Thoughts

This was one of those problems that looked tiny until I started pulling on the thread.

It began as "append a random suffix."

A few hours later I was thinking about:

concurrency
atomic writes
adaptive search spaces
cryptographically secure randomness
human-readable identifiers

Those are my favorite kinds of problems, the ones that quietly combine algorithms with real software engineering.

If nothing else, it reminded me that some of the most interesting engineering challenges aren't hidden inside binary trees or dynamic programming problems. They're hiding behind features we use every day without thinking about them.

DEV Community