StringMint: generate unique, collision-free URL-safe strings in PHP
Posted under: Dev
tl;dr I built a small, zero-dependency PHP library called StringMint that generates short, URL-safe unique strings (think slugs, invite codes, referral links) without needing to run an existence check against your database. Instead of picking random characters and hoping, it walks a keyed permutation of the entire keyspace, driven by a counter, so every string is guaranteed unique the moment it’s generated (as long as you don’t change the secret key!). It’s on GitHub under MIT, pre-1.0 but stable enough that I’m already using it myself.
So what’s the problem?
I’ve got a couple of projects coming up that both need short, unique, URL-safe strings, potentially at real volume. Nothing exotic, the usual stuff: link slugs, invite codes, that sort of thing. And every time I’ve built this before, I’ve reached for the same lazy pattern: generate something random, SELECT 1 FROM table WHERE slug = ?, if it exists try again.
That works fine when your table’s mostly empty. The problem is it gets worse the more successful you are. If you’ve used 87.5% of your available combinations, roughly seven in eight random guesses will already be taken, so you’re burning a database round trip per guess, sometimes several, just to mint one string. At scale that’s not a minor inefficiency, it’s a slow creeping failure mode that only shows up once you’ve got real traffic and real data, which is exactly when you don’t want to be debugging it.
So this time I wanted to actually solve it properly rather than reach for the same pattern and hope I don’t hit the wall for a few years.
Why not nanoid, hashids or UUIDs?
There’s no shortage of libraries for generating short IDs, nanoid, hashids, plain UUIDs, and they’re all good at what they do, but none of them quite fit what I wanted:
- UUIDs are unique, but they’re long, ugly in a URL, and nowhere near “short.”
- nanoid and similar CSPRNG-based generators are exactly the random-then-hope approach above. Great when your keyspace is enormous relative to usage. Not great when you’re deliberately trying to keep strings short and therefore the keyspace small.
- hashids encodes an existing sequential ID rather than solving uniqueness itself, and it’s reversible/guessable by design, which is sometimes fine and sometimes exactly what you don’t want.
What I actually wanted was: pick the shortest string length that gives me a sane number of combinations, guarantee every generated string is unique with zero retries, and don’t leak anything about how many strings have been issued so far (no incrementing/sequential-looking output).
Don’t just sample the keyspace, walk it
The insight that got me here is pretty simple once you say it out loud: if you have a counter and a keyspace of a known size, you don’t need randomness to guarantee uniqueness, you need a bijection. A function that maps every counter value to a unique value in the keyspace, one-to-one, with no collisions possible, ever.
That’s exactly what a Feistel network gives you. It’s the same construction used in format-preserving encryption: split a value into two halves, run them through a keyed round function a few times, swap, repeat. The output is a scramble of the input, but it’s reversible and, crucially, every distinct input maps to a distinct output. No existence check required, because the maths itself guarantees it.
So StringMint’s default strategy (PermutationGenerator) does this:
- Atomically increment a persisted counter (
next(), one row per counter name + length). - Feed that counter value through a keyed Feistel permutation (HMAC-SHA256 under the hood, ~8 HMAC calls, microseconds) to get a pseudo-random-looking index in the same range, cycle-walking to handle keyspace sizes that aren’t a neat power of two.
- Base-encode that index into however many characters you asked for, using whatever alphabet you’ve configured.
The result looks completely random, reveals nothing about how many strings have been issued (string #4 and string #4,000,000 look equally arbitrary), and there is no retry loop, because there’s nothing to collide with. The only two “misses” that cost you a counter index are a reserved output (say, one that ends in a dot, which trips up some URL parsers) or an optional external existence check, if you’ve bolted one on for other reasons.
The secret and the counter’s name both feed into the permutation as a “tweak,” so two counters sharing a secret produce completely unrelated sequences. Change the secret, the alphabet, or the counter name after you’ve issued strings, though, and you’ll get collisions with what’s already out there, so those three are very deliberately a “set once, never touch” list.
Doing the maths so you don’t have to
The other half of the “maximize combinations” problem is choosing a length. Start too long and you’re wasting bytes in a VARCHAR column and a URL; start too short and you exhaust the pool embarrassingly fast. With the default 66-character URL-safe alphabet:
| Length | Combinations |
|---|---|
| 2 | 4,356 |
| 4 | ~19 million |
| 6 | ~82.6 billion |
| 8 | ~360 trillion |
| 10 | ~1.57 quintillion (max supported) |
(Credit where it’s due: I had Gemini crunch the actual combinatorics for me while building this, because doing 66^n arithmetic in my head at midnight is not a skill I possess.)
Rather than pick one length and commit, StringMint can auto-escalate: start at length 4, and when that length’s counter hits capacity it automatically bumps to length 5, then 6, and so on, up to a ceiling you configure. So you can start as short as is sane for your current scale and never have to be the person watching a dashboard for “we’re about to run out of slugs.”
There’s a hard ceiling of 2^62 combinations regardless of alphabet, which is the point past which PHP’s native 64-bit integers stop being a comfortable place to do this maths. If you’re hitting that ceiling, you have bigger problems than a string generator.
When you don’t want any of this
Not every use case has a database counter kicking around, sometimes you just need uniqueness for the lifetime of a process or a Redis-backed session. For that, StringMint also ships a much more conventional RandomGenerator: CSPRNG candidates checked against a pluggable ExistenceCheckerInterface, with exhaustion inferred after enough consecutive collisions. It’s the “normal” approach, included deliberately, because sometimes the counter-and-permutation machinery is more than the problem calls for.
Both strategies sit behind the same interface, so you can wire either one into your DI container and swap later without touching call sites.
Where it stands
It works against MySQL, PostgreSQL, SQL Server and SQLite out of the box (with a portable compare-and-swap fallback for anything else), has zero runtime dependencies, and is tested at PHPStan level 8. It’s pre-1.0, so I’m not promising the API won’t move, but the public method signatures are the bit I’m committing to keeping stable, and I’m already using it in my own upcoming projects, so it’s getting real dogfooding rather than living in the “theoretical usefulness” zone.
The other cool thing is that simply feeding it a different secret key generates an entirely new string order, so you can run multiple instances for different reasons within the same project and not have them share the same sequence (or run an identical sequence!).
Sound useful? Give it a try!
composer require chrismou/stringmintEverything is available on GitHub under the MIT licence, including some incredibly thorough documentation courtesy of Claude. If you find a case it doesn’t handle well, or have opinions on the API before I tag 1.0, I’d love to hear about it!