Designing a URL shortener: generating short codes and handling collisions

# Designing a URL shortener: generating short codes and handling collisions Source: https://modernengineer.dev/en/library/url-shortener-collision-strategies > **Quick summary:** Random codes and truncated hashes can produce the same candidate code (a collision). A `UNIQUE(code)` constraint in the database plus a retry stops two URLs from being stored under the same code, and with 7 to 8 character random codes, retries are rare. That is enough for most systems. If you want codes that never collide at generation time, fully encode a unique ID (a sequence, pre-allocated ID ranges, Snowflake) in base62, then add a transformation if you do not want to reveal the order. Whatever you choose, `UNIQUE` should stay the final referee, because a misconfiguration or a custom alias can still create a duplicate. The URL shortener is a classic system design exercise. Storage is not the hard part: it is one `code → long_url` table. The hard question is how to generate short codes so two different URLs never get the same one. This piece starts from the first approach almost everyone thinks of, shows where it breaks, and only then moves to a better one. In the last few steps, a later step is not strictly better than the one before; it solves a different need, and I will say what that need is. I calculated the numbers and ran them with a small Python script. ## First: how big the code space is Most URL shorteners stick to URL-safe characters. Base62 is a good fit: 10 digits, 26 lowercase and 26 uppercase letters, all in the set of characters URLs do not need to escape ([RFC 3986, section 2.3](https://www.rfc-editor.org/rfc/rfc3986#section-2.3)). With length L there are 62 to the power L possible codes: | Length | Codes | | --- | --- | | 6 characters | about 56.8 billion (5.68 x 10^10) | | 7 characters | about 3.52 trillion (3.52 x 10^12) | | 8 characters | about 218 trillion (2.18 x 10^14) | These numbers assume case-sensitive codes and no excluded codes. If you block offensive strings, reserve prefixes or drop look-alike characters such as `0` and `O`, the real space is smaller. Looking at tens of billions, it is easy to think collisions are nothing to worry about. The first step below shows why that is wrong. ## Step 1: hash the URL and truncate The most natural idea: take MD5 or SHA-256 of the long URL, convert it to base62 and keep 6 to 8 characters. The same URL string always gives the same candidate code, which sounds like you get short codes and free deduplication at once. ### Why it falls short: truncated hashes collide sooner than intuition says For ordinary URLs (nobody crafting collisions on purpose), the chance that two different URLs give the same full hash is small enough to ignore. But a 6-character code is no longer a full hash. Once truncated, the value behaves like a random code in a small space, and the question to ask is not "does a new code match one particular code" but "among n generated codes, do any two match". That is the birthday problem: the number of pairs grows with the square of n, so the probability of at least one collision is about 1 - e^(-n(n-1)/2N), where N is the number of possible codes. | Length | n = 1 million | n = 100 million | | --- | --- | --- | | 6 characters | 99.98% | almost 100% | | 7 characters | 13.2% | almost 100% | | 8 characters | 0.23% | almost 100% | With 6-character codes, 1 million links almost certainly include at least one collision. To check this against a real hash, I took MD5 of 2 million URLs of the form `https://example.com/p/<i>`, converted the hash value to base62 and kept the last 6 base62 digits. The script counted 29 draws that hit an existing code. Under the uniform model, the expected number of colliding pairs is about 35. The two quantities are not identical (a code seen three times gives two hits but three pairs), but they are close enough to show that a truncated hash behaves like a random code. The experiment only illustrates collisions; it does not measure database performance. So a truncated hash does not avoid collisions. To use it, you have to handle collisions, and that exposes three more problems: - **How you truncate.** My experiment kept the last 6 base62 digits, which is the hash value modulo 62^6, so the distribution is close to uniform. Taking the first characters of the base62 string is not equivalent, because the leading digit is bounded by the size of the number. Cutting 6 characters straight from the MD5 hex string leaves a space of only 16^6, far smaller. - **Retrying on conflict.** If the candidate already belongs to a different URL, you have to change the input for the next attempt, for example hash `URL + attempt number`. Appending a fixed salt does not help, because `hash(URL + same salt)` always gives the same result and the retry loop runs forever. - **Deduplication is no longer automatic.** Say URL A takes code `x`, URL B also hashes to `x` and gets `y` after a retry. Next time B is submitted, it still hashes to `x`. The system has to check which URL `x` points to, then walk B's candidate sequence (`hash(B, 1)`, `hash(B, 2)`...) and compare stored URLs before it finds that B holds `y`. Deduplication still works, but it needs lookups and a stable retry rule; it is not free the way it first seemed. MD5 also no longer resists collisions someone crafts on purpose ([RFC 6151](https://www.rfc-editor.org/rfc/rfc6151#section-2)). If users can submit arbitrary URLs, do not rely on MD5's properties to guarantee anything. The takeaway from step 1: even with a hash, you still have to detect collisions and retry, just as with random codes. If you do not truly need a candidate code that is deterministic per URL, generating random codes directly lets you drop the hashing logic and the retry sequence. ## Step 2: random code, check first and then write Generate a random base62 code with a secure random generator. To avoid collisions, the first idea is to ask the database first: `SELECT` to see whether the code exists, and `INSERT` if it does not. ### Why it falls short: the gap between two statements There is a gap between `SELECT` and `INSERT`. Two requests running in parallel can both see the code as free and both insert. At low load you rarely see this bug, so it easily slips through testing and shows up in production. The extra `SELECT` also costs one more query for every new link.  *Step 2: without UNIQUE, the gap between SELECT and INSERT lets a duplicate through. The code is only an example.* What guarantees that two rows never claim the same code has to be a constraint the database enforces itself, not check logic in the application. ## Step 3: random code, UNIQUE and retry Put a `UNIQUE` constraint on the `code` column and let the database be the referee. The application no longer asks first; it inserts directly, and on conflict it generates another code and tries again. In PostgreSQL this fits in one statement: ```sql insert into short_urls (code, long_url) values ($1, $2) on conflict (code) do nothing returning id; ``` This is a parameterized query through your driver, with `$1` as the code and `$2` as the long URL. If no row comes back, the code was taken; the application generates another and runs it again ([PostgreSQL: INSERT](https://www.postgresql.org/docs/current/sql-insert.html)). The unique index stops duplicates even when many requests run in parallel.  *Step 3: the unique index decides who keeps the code; the loser draws another and retries.* Are retries expensive? The probability table in step 1 is about the whole history. The more practical question in operation is: once the table holds n codes, what is the chance that a new code collides? The answer is n/N: | Length | 100 million codes stored | 1 billion codes stored | | --- | --- | --- | | 6 characters | 0.18% | 1.76% | | 7 characters | 0.0028% | 0.028% | With 7-character codes and 1 billion codes stored, that works out to about 3 retries per 10,000 new links. Collisions will happen, but each one costs only one more insert. This is the approach I recommend for most systems: simple, no coordination between servers, and random codes from a secure generator do not let outsiders guess the next code. ### Should you add a Bloom filter to avoid hitting the database? A Bloom filter can say "this code is definitely not present" without touching the database, provided every stored code was added to the filter correctly ([Redis: Bloom filter](https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/)). It has false positives and no false negatives. But a negative answer does not reserve the code: two requests can both get "not present", so the insert still has to go through `UNIQUE`. Once you have dropped the `SELECT` as above, adding a Bloom filter may save nothing. ### Limits of step 3 This approach is good enough, but three points make some systems want to go further: - **It never guarantees no collision at generation time.** The retry rate grows linearly as the table fills. You can lengthen codes for new links without changing old ones, but you still have to watch that rate. - **Random guesses can hit.** Outsiders cannot predict the next code, but guessing randomly still hits an existing code with probability of roughly n/N. If links are private, use longer codes or access control rather than relying on short codes. - **UNIQUE only holds within one database.** If you later split data across independent databases, you need to make sure the same code is always checked in the same place (for example by routing on `hash(code)`), or divide the code space into ranges that do not overlap. ## Step 4: a unique ID encoded in base62 To remove the chance of collision entirely, stop drawing randomly. Take a unique integer and convert it to base62. Base conversion is one-to-one, so if IDs never repeat, codes never repeat. The simplest source of IDs is a database sequence: each new link takes the next value. ### When you need IDs without asking the issuer for every link A sequence means every link creation takes a number from the same database. Usually that is not a problem: `nextval()` can be called inside the `INSERT` itself, and sequences have a `CACHE` option to reduce the cost ([CREATE SEQUENCE](https://www.postgresql.org/docs/current/sql-createsequence.html)). I did not measure the sequence as a bottleneck. It only becomes a problem when you need to generate IDs in regions far apart, or you have measured ID issuance as the bottleneck. Then there are two ways to loosen it, and note that both only reduce requests for IDs, not writes of `code → long_url` to the database: - **Range allocation.** Each server reserves a block in advance, say 1,000 numbers, and hands them out from memory without asking the database for each link. If a server dies, the rest of its block is wasted, which is usually acceptable. - **Snowflake IDs.** Published by Twitter in 2010 ([original repository](https://github.com/twitter-archive/snowflake)). A 64-bit ID holds 41 bits of millisecond timestamp, 10 bits of machine ID (the original splits them into 5 datacenter and 5 worker bits) and a 12-bit sequence within a millisecond. Uniqueness holds only if each machine has its own ID and clocks never go backwards; the original refuses to generate IDs when the clock goes back and waits for the next millisecond when the sequence runs out ([IdWorker.scala](https://github.com/twitter-archive/snowflake/blob/snowflake-2010/src/main/scala/com/twitter/service/snowflake/IdWorker.scala)). Snowflake has a cost in length: a 63-bit number needs up to 11 base62 characters, while 7 base62 characters hold only about 41.7 bits. For shorter codes you have to redesign the bit layout (fewer timestamp bits, fewer machines, fewer IDs per millisecond). Do not truncate the encoded string and still treat it as unique, because truncating takes you back to step 1.  *Step 4: base conversion is one-to-one, but a 63-bit Snowflake ID needs 11 base62 characters.* ### Why it falls short: increasing codes are guessable Step 4 solves collisions but creates a new problem. Codes come from increasing IDs, so outsiders can walk through other people's links one by one and estimate how fast you create links. The difference between two IDs does not give the exact number of links, because PostgreSQL sequences can skip values on rollback or `ON CONFLICT` ([sequence functions](https://www.postgresql.org/docs/current/functions-sequence.html)), and Snowflake IDs also carry a timestamp and machine ID. But the trend still shows. ## Step 5: transform the ID to hide the order Keep the unique ID source from step 4, but transform it before it becomes a code: - **Apply a bijection to the ID, then encode in base62**, for example a Feistel network with a secret key. A bijection preserves uniqueness. But a bijection is not unguessable by nature: adding a constant modulo some number is also a bijection and trivial to reverse. How hard it is to guess depends on the specific design and on keeping the key secret. - **Use a library such as [Sqids](https://sqids.org/).** Sqids takes numbers and returns the code string directly; it is not a step before base62. According to the [Sqids FAQ](https://sqids.org/faq), codes can be decoded, it is not meant to protect sensitive data, and it supports a minimum length rather than guaranteeing a fixed one. It makes codes look non-sequential; it is not encryption. At this point you have codes that never collide by design and do not obviously reveal their order. The price is extra ID infrastructure; with a keyed transformation you also have to manage the key, while Sqids only changes how the ID is represented. If links truly need to be hard to guess, the long enough random codes of step 3 are still simpler and safer. ## Step 6: a pre-generated key pool This step does not fix a shortcoming of step 5. It changes when codes are generated and how they are distributed, and it can be combined with random codes or codes from IDs. The idea is to move code generation into a separate service (a key generation service). This service generates unused codes ahead of time and stores them in a pool. Each app server requests a batch, keeps it in memory and hands codes out. Code generation leaves the main request path, though fetching batches and writing to the database still cost something.  *Step 6: a pre-generated key pool. The database still keeps UNIQUE(code).* To avoid handing out a code twice, selecting and marking a batch must be atomic and durably recorded before the batch goes back to the server, and each code in a batch must be taken only once. Codes already handed to a server that dies are wasted. If the pool holds consecutive codes, shuffling the handout order does not hide the set of codes, because outsiders can still scan the whole range; the pool must hold deduplicated random codes or codes that went through the transformation from step 5. The price is one more service and one more piece of allocation state to run and monitor. It is only worth it when you have measured code generation or collision checks as a real bottleneck. ## Comparing the steps | Approach | Candidate codes can collide | Prevents storing duplicates | Guessable | Coordination between servers | | --- | --- | --- | --- | --- | | Truncated hash | Yes, per the birthday problem | Yes, with UNIQUE and retry | Anyone who knows the URL can compute the candidate | No, relies on UNIQUE | | Random, SELECT then INSERT (no UNIQUE) | Yes | No, duplicates slip through under concurrency | Next code is unpredictable | No | | Random + UNIQUE + retry | Yes, but rarely | Yes | Next code is unpredictable | No, relies on UNIQUE | | Unique ID + base62 | No, if IDs never repeat | Yes, keep UNIQUE anyway | Yes | Yes: sequence, ID ranges or machine IDs | | ID + transformation | No, if IDs never repeat | Yes, keep UNIQUE anyway | Harder, depends on the transformation and key | Same as above | | Pre-generated key pool | No, if batches are handed out correctly | Yes, keep UNIQUE anyway | Depends on what the pool holds | Yes, through the key service | ## Decisions that come with every step - **Returning the old code for the same long URL.** If you want this, store an extra column with a hash of the long URL and index it. The hash only finds candidates quickly; for exactness you must compare the original URL. Under concurrent load, two requests for the same URL can still create two codes if you only read first and write second; if that matters, put a unique index on the deduplication key itself. - **Custom codes chosen by users.** Keep them in the same table under the same `UNIQUE` constraint. If generated and custom codes share one space, a code generated from an ID can still hit an alias a user picked earlier. Separate the spaces (for example require aliases to be longer or include a distinct character) or handle conflicts for generated codes too. - **Keep UNIQUE at every step.** Even when the design guarantees no collisions, this constraint still catches mistakes you did not plan for, such as overlapping ID ranges or a custom alias clashing with a generated code. ## Which step to stop at For small and medium systems, step 3 with 7 to 8 character codes is usually enough. Move up to steps 4 and 5 when you need codes that never collide at generation time and already have ID infrastructure. Step 6 is only worth it when you have measured code generation as the bottleneck. I do not give a link-count threshold for moving between steps, because the n/N table describes collision odds, not throughput or database limits. ## Frequently asked questions ### Why not use the full MD5 or SHA-256 string as the code to avoid collisions? Because the point is a short code. A SHA-256 hex string is 64 characters long, the opposite of shortening. A full hash does not guarantee absolute uniqueness either, and MD5 no longer resists collisions someone crafts on purpose. The moment you truncate it, you are back to the same birthday problem as random codes, so you still need `UNIQUE`. ### How long should codes be at the start? With random codes and `UNIQUE`, 7 base62 characters give a per-insert retry chance of about 0.0028% with 100 million codes stored. If you want more headroom, or links that are harder to hit by guessing, choose 8 characters. ### Does Sqids make codes secure? No. Sqids makes IDs look non-sequential, but codes can be decoded and the Sqids docs say clearly not to use it to protect sensitive data. If links need to stay private, use long enough random codes or access control. ### Why not SELECT first and then INSERT? Because another request can insert the same code between the two statements. Let the unique index decide with `INSERT ... ON CONFLICT DO NOTHING RETURNING`, and retry if no row comes back.

insert into short_urls (code, long_url)
values ($1, $2)
on conflict (code) do nothing
returning id;

Read "Designing a URL shortener: generating short codes and handling collisions" on modernEngineer and apply it to this repo.
1. Call the content_get tool of the modernengineer MCP server with locale "en", slug "url-shortener-collision-strategies". If MCP is not connected or access is refused, read the page https://modernengineer.dev/en/library/url-shortener-collision-strategies instead.
2. Summarize the main steps of the piece and point out which apply to this repo.
3. Propose concrete changes and ask me before editing any file.

claude mcp add --transport http modernengineer \
  https://api.modernengineer.dev/mcp \
  --header "Authorization: Bearer <API key>"