5. Global counter + base62 (and random + verification)

Description

The previous lesson ended with a problem: the truncated hash collides, and at Enlace's scale there's no way to avoid it without adding verification. This lesson presents the strategy that by construction cannot collide: a global counter that goes 1, 2, 3, … and is converted into a short code with base62_encode. It's the simplest strategy to reason about —each new link takes the next number, and two different numbers give two different codes, period— and that's why it's the workhorse of many shorteners. By the end you'll be able to generate codes with a counter, run it, and —most important— name its two costs, because "doesn't collide" isn't "has no price".

And since the counter has those two costs, you'll also meet the third strategy, which sits between the hash and the counter: random + verification. Throw a random 7-character code, check whether the locker is free, and if it is, hand it to me; if not, throw another. It sounds like it would retry all the time, but the module's anchor —62⁷ is 587 times the 5-year demand— makes it almost never clash, and you'll measure it: with 6 billion codes already taken, the probability of a new one clashing is 0.17%. In the end you'll have the three strategies in hand, ready for lesson 7's decision table.

Connection to the module: this is the second generation lesson (after the hash in lesson 4). Together with lesson 4 it completes the three strategies; lesson 6 goes into the detail of the base62_encode/base62_decode we use here as a black box (here we use it, there we build it); lesson 7 compares them and decides. Pay attention to a topic that reappears in module 5: the global counter is a single coordination point —each write has to ask "the next number" from the same place—, and scaling that is, literally, the sharding problem you'll see later. Here we name it as a boundary; there it's resolved.

The butcher shop's ticket dispenser

You already know this machine. You walk into a busy butcher shop and there's a ticket dispenser: you press the button and a slip comes out with a number. Yours is 47; whoever comes in next takes 48; the next, 49. The machine never gives the same number twice —it keeps an internal counter that only goes up—, so it's impossible for two customers to have the same turn. That impossibility is the great virtue: you don't have to check a list of "turns already handed out" to avoid repeating; the machine's design guarantees it on its own.

The counter + base62 strategy is that dispenser. Enlace keeps a global counter —a number that only grows— and each new URL takes the next value: the first is 1, the second 2, the millionth 1,000,000. Since each number is handed out only once, two links never share a number, and therefore never share a code. No collisions, no need to verify, no retry loop. Compared to the hash from lesson 4, which needed to check each code against the existing ones, this is of a beautiful simplicity.

But the counter's number is big and ugly —1,000,000 isn't a "short code"—, so there's one more step: convert it to base62. This is where base62_encode comes in, the function lesson 6 builds in detail and that here we use as a box that already works. It converts the counter's number (in base 10) into a short base 62 string, using the 0-9a-zA-Z alphabet. The million becomes 4c92: four characters instead of seven digits. Base62 is simply a more compact way of writing the same number, just as "FF" in hexadecimal is a shorter way of writing 255. The counter guarantees uniqueness; base62 makes it short.

Worked example: from the counter to the code, run

Let's see the dispenser working. We use base62_encode as a black box (its implementation is lesson 6) and pass it counter values to see what codes come out:

# The global counter + base62, in action.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def base62_encode(n: int) -> str:
    """Converts an integer into its base62 string (detail in lesson 6)."""
    if n == 0:
        return ALPHABET[0]
    chars = []
    while n > 0:
        n, rem = divmod(n, 62)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))


# Each counter value gives a unique code:
for counter in [1, 2, 3, 100, 1000, 1_000_000, 1_000_001, 1_000_002]:
    print(f"  id={counter:>10,}  short_code = {base62_encode(counter):>7}")

What to expect. Running this with Python 3.14.0 gives:

  id=         1  short_code =       1
  id=         2  short_code =       2
  id=         3  short_code =       3
  id=       100  short_code =      1C
  id=     1,000  short_code =      g8
  id= 1,000,000  short_code =    4c92
  id= 1,000,001  short_code =    4c93
  id= 1,000,002  short_code =    4c94

Look at the beauty and the flaw on the same screen. The beauty: each number gives a distinct code, without exception, without having verified anything. 1,000,000 → 4c92, and you know with mathematical certainty that no other link will have 4c92, because no other link will take the number 1,000,000. Zero collisions, guaranteed by the dispenser's design.

The flaw is in the last three lines: 1,000,000 → 4c92, 1,000,001 → 4c93, 1,000,002 → 4c94. The codes are consecutive and predictable. If you receive the link enla.ce/4c93, you can try enla.ce/4c92 and enla.ce/4c94 and you'll reach the links created just before and just after yours, created by other people. That's the first cost of the counter, and we develop it next.

The first cost: guessable codes

That the codes are sequential isn't an aesthetic detail; it's a real privacy and business-security problem. Think of it from the attack: a competitor receives one of your links, say 4c92, and from there they can enumerate your entire database simply by incrementing the code: 4c93, 4c94, 4c95… Each one reveals a URL another user shortened, maybe a private URL, maybe their next launch. With hash or random this doesn't happen, because from one code you can't deduce the next. With a pure counter, the sequence is the map of your system.

There's a second leak in the same flaw: the counter reveals your business volume. If an observer shortens a URL today and receives the code representing the number 5,000,000, and tomorrow shortens another and receives 5,040,000, they can subtract and deduce that you created ~40,000 links in a day. For many companies, that growth rate is competitive information you wouldn't want to give away in every code.

The good news: the cost can be mitigated without abandoning the counter, and there are two classic techniques.

Start at a high offset. If the counter starts at 1, the first codes are 1, 2, 3 —very short and obviously sequential—. If instead you start the counter at a large number, the codes are born with 7 characters and don't give away an "I started from scratch". Let's see it:

# Start the counter at 62^6 so the codes are born with 7 chars.
offset = 62**6                       # 56,800,235,584
for i in range(3):
    n = offset + i
    print(f"  id={n:>15,}  short_code = {base62_encode(n)}")

What to expect. It gives:

  id= 56,800,235,584  short_code = 1000000
  id= 56,800,235,585  short_code = 1000001
  id= 56,800,235,586  short_code = 1000002

Now the codes have 7 characters from the first link (1000000 in base62). But notice: they're still consecutive (1000000, 1000001, 1000002). The offset resolves the brevity and the "started at zero", but not the enumeration: from 1000001 you keep guessing 1000000 and 1000002. To really break the sequence you need the second technique.

Permute the counter. Instead of encoding the counter directly, you first pass it through a function that scrambles the numbers reversibly —a bijective permutation of the range, like a small block cipher (for example, a Feistel-type scheme), or multiplying by a number coprime with the space size and taking the modulo—. The idea: the internal counter still goes 1, 2, 3, … (uniqueness guarantee intact), but the number you encode jumps all over the space unpredictably, so the counter's consecutive codes give base62 codes that don't resemble each other. It's the best of both worlds: guaranteed uniqueness from the counter, random appearance of the code. The cost is a bit of complexity and keeping the permutation's secret. Many serious shorteners use exactly this.

The second cost: the global counter is a single coordination point

The second cost is deeper and is a direct boundary with module 5. The butcher shop's dispenser works because there's only one: if there were two independent dispensers, both would hand out turn 48 and you'd have collisions again. The same with Enlace: for the counter to guarantee uniqueness, there has to be a single counter, and each write —the ~40 per second— has to go ask it "the next number". That single counter is a coordination point: all the writes serialize through it.

At 40 writes per second this isn't a problem; an atomic counter (for example, a Redis INCR or a PostgreSQL sequence) handles that with room to spare. But the moment Enlace grows and you want many servers generating codes in parallel, the single counter becomes a bottleneck and a single point of failure: if the counter component goes down, no one can create links, even if the rest of the system is healthy.

How do you scale a counter? By splitting it —which is exactly the topic of module 5—. The classic techniques: give each server a range of numbers (server A hands out from 1 to a million, B from a million to two million, so they never clash and neither asks the other for permission), or use a distributed ID generator that combines the machine's identifier with a timestamp and a local counter (the Snowflake-type scheme). Here we only name it as a boundary:

flowchart TD
    subgraph today["Today (40 writes/sec): one counter is enough"]
        W1["write"] --> C1["global counter<br/>(INCR / sequence)"]
    end
    subgraph tomorrow["On scaling: the counter splits — MODULE 5"]
        WA["server A"] --> RA["range 1..1M"]
        WB["server B"] --> RB["range 1M..2M"]
        WC["server C"] --> RC["range 2M..3M"]
    end

Keep the idea as a boundary: "scaling the counter" is "splitting the counter", and splitting things across machines is sharding —module 5—. Today, with a single counter, Enlace works; the cost appears on growth, and that's why it's a future cost to keep on the radar, not a blocker of today.

The third route: random + verification

Between the hash (collides) and the counter (guessable + coordination) there's a third strategy that borrows the best of each: generate a completely random 7-character code, and verify it doesn't exist before storing it. Since it's random, it's not sequential or guessable (it resolves the counter's first cost). Since each generation is independent, there's no need for a single global counter: any server can throw random codes without coordinating (it alleviates the counter's second cost). The price is that, like the hash, it can clash —two random throws can give the same code— and that's why it needs to verify against the store and retry if the locker is taken.

The question that decides whether this strategy is viable: how often does it clash, really? And this is where the module's anchor pays off. The space is 62⁷ = 3,521,614,606,208, enormous. We're going to measure the clash probability, first the "at least one collision when inserting k codes" one (the birthday again) and then the one that really matters in operation: "given that there are already N codes taken, what probability does ONE new one have of clashing?".

# How often does "random + verification" clash in the 62^7 space?
import math

m = 62**7                              # 3,521,614,606,208 holes


def birthday_prob(k, m):
    """Approx.: probability of AT LEAST one collision when inserting k codes."""
    return 1 - math.exp(-(k * k) / (2 * m))


print("P(at least 1 collision) when inserting k random codes:")
for k in (1_000_000, 100_000_000, 6_000_000_000):
    print(f"  k = {k:>15,}  ->  P = {birthday_prob(k, m):.6f}")

# What matters in operation: with N already taken, does ONE new one clash?
occupied = 6_000_000_000               # the worst case: 5 years of links
p_single = occupied / m
print(f"\nWith {occupied:,} of {m:,} taken:")
print(f"  P(a new code clashes) = {p_single:.6f} = {p_single:.4%}")
print(f"  expected retries      ~ {1/(1-p_single):.6f} per insertion")

What to expect. Running this with Python 3.14.0 gives:

P(at least 1 collision) when inserting k random codes:
  k =       1,000,000  ->  P = 0.132362
  k =     100,000,000  ->  P = 1.000000
  k =   6,000,000,000  ->  P = 1.000000

With 6,000,000,000 of 3,521,614,606,208 taken:
  P(a new code clashes) = 0.001704 = 0.1704%
  expected retries      ~ 1.001707 per insertion

You have to read the two blocks carefully, because they say different things and it's easy to confuse them. The first block says that over the whole life of the system there will be collisions for sure: when inserting 100 million or 6 billion random codes, the probability that at some point two coincide is practically 1. That confirms verification is mandatory —you can't throw at random and pray—. But that doesn't mean collisions are frequent: only that over billions of insertions, they'll occur.

The second block is the one that rules in operation, and it's reassuring: even at the worst moment —with the 6 billion codes already taken at the end of the 5 years—, a new random code has barely a 0.17% probability of clashing. That means that one in every ~587 insertions needs to retry, and the other 586 hit on the first try. The number of expected retries per insertion is 1.0017: practically one. In practice, you generate a code, try to store it (with the conditional "only if it doesn't exist" write from lesson 3), and in 99.83% of cases it works on the first try; in the rare case of a clash, you generate another and that's it. The giant 62⁷ space is what makes this cheap: since less than 0.2% of the space is used, almost any random code falls into an empty locker.

Notice the contrast with the hash from lesson 4. There, truncating to 16 bits gave 30% collisions because the space was tiny (65,536). Here, with the full 62⁷ space, the collision drops to 0.17% —the same mechanism (throwing into a space and clashing), but in a space 53 million times larger, so the clash is 175 times less frequent—. The lesson: the size of the space is almost everything; with 7 base62 characters, there's so much space that "random + verification" retries almost never.

Common mistakes

Encoding the counter from 1 and exposing one-character codes. What happens: someone launches Enlace with the counter at 1, and the first links are enla.ce/1, enla.ce/2, enla.ce/3. Besides screaming "this service is new and has three links", they're trivially enumerable and clash with reserved routes. Why it happens: the raw counter is encoded without thinking about how the first codes look. How to detect it: if your first link has a code of 1 or 2 characters, you're exposing the counter from zero. How to fix it: start the counter at a high offset (like 62⁶) so the codes are born with 7 characters, and —if you care about privacy— permute the counter so they're also not consecutive. The offset fixes the appearance; the permutation fixes the enumeration.

Believing that "random + verification" retries all the time. What happens: someone discards the random strategy thinking "it's going to clash constantly and do an extra query per attempt". They didn't do the math: with the 62⁷ space, the clash rate is 0.17% even with 6 billion taken, that is ~1 retry every 587 insertions. Why it happens: the intuition about collisions fails in both directions —it thinks the truncated hash doesn't clash (and it clashes a lot) and that random in a large space clashes a lot (and it barely clashes)—. How to detect it: if you reject a strategy for its collision rate without having computed it against the real size of the space, you're guessing. How to fix it: compute N_taken / space_size. For Enlace it gives 0.17%: cheap. The size of the space rules.

Forgetting that the global counter is a single point of failure. What happens: someone chooses the counter for its simplicity and its zero-collisions, and doesn't realize they've added a component through which every write must pass; the day that component saturates or goes down, no one can create links. Why it happens: they look at the advantage (guaranteed uniqueness) and not the structural dependency (central coordination). How to detect it: ask yourself "if the ID generator goes down, what stops working?". With a single global counter, the answer is "all the writes". How to fix it: at today's scale (40 writes/sec) the single counter is fine and you shouldn't over-engineer; but keep on the radar that scaling it is splitting it into ranges or using a distributed generator —the topic of module 5— and that random + verification avoids this single point from the start, in exchange for the verification per write.

Exercises

Exercise 1 — Encode a batch of the counter and detect the leak. Using base62_encode, encode the counter values 999,998, 999,999, and 1,000,000. Write the three codes and explain what information the sequence leaks to someone who receives only the middle link. Then say what changes if before encoding you add an offset of 62⁶.

for n in (999_998, 999_999, 1_000_000):
    print(n, base62_encode(n))
# 999998  4c90
# 999999  4c91
# 1000000 4c92

Exercise 2 — Recompute the retry rate for another scale. The clash rate of "random + verification" is N_taken / 62⁷. Compute the rate and the expected retries per insertion (a) when Enlace has 1 billion codes taken, and (b) in a hypothetical future with 3 quadrillion (3 × 10¹⁵) codes —more than the whole space—. What does case (b) tell you?

m = 62**7   # 3,521,614,606,208
for occupied in (1_000_000_000, 3_000_000_000_000_000):
    p = occupied / m
    print(occupied, f"{p:.4%}", f"{1/(1-p):.4f}" if p < 1 else "IMPOSSIBLE")
# 1,000,000,000          0.0284%   1.0003
# 3,000,000,000,000,000  85188%    -> p > 1: IMPOSSIBLE

Exercise 3 — Choose the correct mitigation for each concern. A team uses counter + base62 and raises three different concerns. For each, say which technique resolves it (offset, permutation, or splitting the counter into ranges) and why that one and not another. (a) "The first links have one-character codes, it looks amateur." (b) "A competitor is enumerating our links by incrementing the code." (c) "We want five servers to generate codes in parallel without asking the same place for the number."

Summary and next step

You met the two strategies that resolve the hash's collision problem, each in its own way. The global counter + base62 guarantees uniqueness by construction —like the ticket dispenser, two links never share a number— and you ran it: 1 → '1', 1,000,000 → '4c92', consecutives that give consecutive codes. But it has two costs: the codes are guessable (sequential: 4c92, 4c93, 4c94), mitigable with offset and permutation; and the counter is a single coordination point, whose scaling is splitting it into ranges —boundary with module 5—. The third route, random + verification, avoids the sequentiality and the central coordination in exchange for verifying each write, and you measured that this cost is minimal: with 6 billion codes taken, a new code clashes only 0.17% of the time (~1 retry every 587), because the 62⁷ space is gigantic against the demand.

Before moving on you should be able to: explain why the counter never collides (each number is handed out once); name its two costs and the mitigation of each one; explain why random + verification barely retries (0.17% with the 62⁷ space); and distinguish "there will be collisions over the whole life of the system" (true, that's why you verify) from "collisions are frequent" (false, 0.17%).

The three strategies share a piece we've used as a black box: base62_encode (and its inverse base62_decode). Lesson 6 opens that box: you implement the algorithm from the divmod against the base, run the round-trip base62_decode(base62_encode(n)) == n over hundreds of thousands of values to prove it's reversible, and reproduce with Python that 62⁷ = 3,521,614,606,208 covers the 6 billion with less than 0.2% used. It's the lesson where the module's numeric anchor is run in depth.

Resources

• Python documentation — the divmod function — the "quotient and remainder at once" operation that is the engine of base62_encode. Lesson 6 uses it to convert the counter's number to base 62; it's good to have it fresh.
• Redis documentation — the INCR command — a real atomic counter, exactly the "ticket dispenser" that guarantees two writes never receive the same number. Seeing that it's a single atomic operation explains why at 40 writes/sec the single counter is enough.
• PostgreSQL documentation — "Sequences" (CREATE SEQUENCE, nextval) — the relational alternative to the counter: a sequence that hands out monotonic numbers. Its section on CACHE and on why the numbers can have gaps is directly relevant to the coordination cost.
• Instagram Engineering — "Sharding & IDs" (the Snowflake-type scheme) — how a real system generates unique IDs without a single central counter, combining timestamp, shard id, and a local sequence. It's the concrete preview of how module 5 resolves the counter's single coordination point.