From Redis INCR to Leaf-Segment: Reliable Short-Link ID Generation

Problem Boundary and Workload

The article establishes that short-link systems must guarantee three independent properties: allocation uniqueness (no two allocated IDs collide), code uniqueness (no two resources share a short code in the same namespace), and creation readability (a successful creation response means the mapping is durable and readable by the jump path). Base62 encoding only addresses code representation; Leaf-segment only reduces remote allocation frequency; database, cache, replicas, and async messaging together determine readability.

Creation QPS (avg 500/s, peak 5,000/s) drives allocator, mapping writes, and segment prefetching; jump QPS (peak 200,000/s) drives caching, hotspot protection, and origin capacity. The two cannot be conflated.

Six-Character Base62: Capacity, Encoding, and Exhaustion

Using the fixed alphabet

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

, six characters with leading zeros yield M = 62^6 = 56,800,235,584 codes. Reserving 0 as a sentinel leaves M-1 allocatable IDs. Without leading zeros the space shrinks to 62^6 - 62^5 = 55,884,102,752; the two rules must not be mixed.

Capacity is consumed by the confirmed allocation boundary A = C + W + R where C = committed mappings, W = waste from retries/unknown outcomes, R = reserved but unused segments. At 500/s sustained, the space lasts ~3.6 years; at 5,000/s, ~131 days. Peak rates must not be used as averages. Base62 is not encryption; sequential IDs are enumerable, so short links used as credentials need additional entropy or auth.

Scheme Comparison: Failure Semantics Over Slogans

A table compares five schemes:

Database auto-increment/counter row : simple, coordinates with mapping write; risks: write scaling, recovery rollback, cross-shard.

Redis INCR : simple atomic increment; risks: async replication loss, failover/recovery rollback.

Segment (Leaf-segment) : local batch allocation, fewer remote calls; risks: allocation transaction, reserve exhaustion, waste, recovery.

Snowflake : no central storage per ID; risks: clock, worker lifecycle, bit width; usually cannot fit six chars.

Secure random codes : no sequence exposure; risks: collision retry, low occupancy requirement; unique index remains final arbiter.

Redis INCR typically causes skipped numbers (e.g., client retries after lost response) not duplicates. The real danger is authority rollback: a promoted replica may re-issue already allocated IDs. WAIT reduces the window but does not make Redis a strong CP system.

Segments are not inherently duplicate-free. If the allocation DB confirms a boundary advance but failover switches to a replica lacking that record, the new primary can re-issue overlapping ranges. All HA constraints protect this fact.

Minimal Production Architecture and Evolution Path

Four stages:

Stage A (Basic) : low creation volume, single DB handles mapping transaction, unique index, idempotency key, authoritative read path. No separate ID service, no Bloom filter.

Stage B (Segment) : per-ID allocation becomes measurable bottleneck. Adds transactional segment fetch, double buffer, bounded prefetch, capacity observability. No complex multi-active.

Stage C (High-Concurrency Jump) : origin and hotspots visible. Adds local cache, Redis, request merging, negative-cache governance. No full filter replication.

Stage D (HA/Multi-Region) : fault domain expands or capacity nears limit. Adds allocation authority recovery protocol, space isolation, drills, namespace extension. Rejects "automation equals safety" assumption.

Mapping Data Model: Uniqueness, Idempotency, Audit

MySQL 8.0/InnoDB schema uses ascii_bin collation to keep 00000A and 00000a distinct. Primary key id (internal), unique uk_code(code), unique uk_tenant_request(tenant_id, request_key), check id >= 1. Custom codes still generate internal ID with code_source='CUSTOM'; uk_code is final conflict judge for both generated and custom codes.

Idempotency: request_key is tenant-scoped. On conflict: no record → create; record with same request_hash → return original; record with different hash → 409. Hash must cover normalized target URL, TTL, visibility, jump policy. Concurrent creation decided by unique index, not SELECT-then-INSERT.

Target URL safety baseline: allow only explicit protocols (HTTPS, evaluated HTTP), limit length/control chars, store original and normalized values, rate-limit per tenant, record abuse status, implement SSRF protection if any server-side fetch occurs.

Segment Allocation: Same Transaction, No Rollback, No Fork

Two tables: shortlink_alloc (authoritative high-water mark with biz_tag, next_id, step) and shortlink_allocation_audit (each confirmed allocation with allocation_id, start_id, end_exclusive, allocator_instance). Audit supports recovery reconciliation; uniqueness still enforced by counter-row transaction.

Allocation uses left-closed right-open interval [start, endExclusive). Single transaction: SELECT ... FOR UPDATE, compute start = next_id, size = min(step, MAX - start), validate, UPDATE ... SET next_id = end WHERE next_id = start, insert audit row, commit. All statements same connection, same transaction, same primary writer. Forbidden: read from replica, split lock-read and update into separate auto-commits. Update must affect exactly one row else rollback.

Uncertain commit (DB committed but client lost response): two safe strategies — (1) allow waste: abandon unknown interval, re-request from provably non-rollback history; (2) idempotent allocation: attach unique allocation request ID, persist with interval in same transaction, retry reads committed record. Neither relies on "local lock still held" guesses.

Multiple business tags do not naturally share unique space. If tenant_a and tenant_b both start at 1 and map to same domain, they collide. Options: global pool, pre-partitioned disjoint integer ranges, or make domain+path prefix part of final namespace with unique constraint on that space.

Leaf-Segment Mapping: Borrow Mechanism, Don't Blindly Copy

Leaf's segment mode uses leaf_alloc with biz_tag, max_id, step. Key differences: this article stores next unallocated value ( next_id) while Leaf often stores segment end ( max_id); interval notation [start, end) vs Leaf's (max_id-step, max_id] — endpoints must be unified; double buffer current/standby vs Leaf's SegmentBuffer — this article never reuses published range objects; prefetch threshold by remaining seconds vs step/load threshold — production params derived from instance rate and tail latency; allocation audit is business extension, not in Leaf's base tables. When integrating Leaf, lock version/commit, verify DDL, boundary definition, step adjustment, thread model, dependencies. Do not apply this article's next_id SQL directly to leaf_alloc.max_id.

Double Buffer: Hide Normal I/O, Not Eliminate Failures

Instance maintains current (active immutable range), standby (confirmed next range), loading (in-flight load flag), retryAt (backoff timestamp), draining (stop accepting new creates). State machine: Empty → Loading → Ready → Backoff; standby becomes current on switch.

Immutable IdRange objects: each successful allocation creates new object; published objects never reset cursor. Java example uses AtomicLong cursor with tryNext() returning 0 when exhausted. Old requests holding previous range only consume its remaining IDs; ranges are non-overlapping at allocation time.

Control contract: nextId(deadline) checks draining/deadline, tries current, triggers prefetch on success, enters short critical section to re-check current, swaps standby if ready, else triggers load if not past retryAt, waits bounded or returns retryable error. loadSegment() atomically acquires loading permit, submits to dedicated bounded executor, allocates segment with independent timeout, on success publishes new immutable range and wakes waiters, on failure records classified error and retryAt, finally clears loading. Prefetch is service-level work, not per-user-request.

Prefetch threshold by remaining time: T_i = r_i / q_i (remaining IDs / peak rate). Trigger when r_trigger >= q_i * (L_allocation + L_backoff + J). Example: 500/s peak, step 100,000 → ~200s per segment. With 20,000 left in current and standby ready, buffer ~240s. This is stable-traffic estimate, not SLA; segments cannot be shared across instances.

Creation Readability: Cache and Replicas Must Honor Contract

Recommended read path: after mapping commit return 201; jump reads local cache → Redis → single-key request merge → bounded authoritative origin read. Authoritative read can be primary, replica with proven replication window coverage, or read-your-writes service. If jump reads only lagging replica, new links may incorrectly 404. Options: replica miss falls back to primary with timeout; new links routed to primary/consistent read for a defined window; write confirmed by jump-authoritative store before 201. Chosen window, max origin concurrency, timeout, degradation must be in contract and load-test acceptance.

Outbox in mapping transaction reliably drives cache updates, analytics, indexing, notifications. It solves "commit succeeded but notification lost", not creation-time read consistency. Cache write failure is acceptable if mapping committed and authoritative origin can find it.

Negative-cache race: attacker pre-visits enumerable codes creating negative entries; later real creation may 404 if only delete-on-create. Mitigations: short negative TTL with capacity cap; cache entries carry mapping version/creation time; create overwrites with version not just delete; bypass negative cache for recent segments; jump path verifies authoritative on negative hit within availability window. Strict immediate readability requires provable ordering, not just "delete cache after create".

Jump Concurrency: Protect Cache and Authoritative Store

Local cache for extreme hot links, Redis for shared hotspots; cache miss needs single-key request merge, DB origin concurrency limit, connection pool isolation, timeout. Request merge typically per-instance only. Cache TTL with jitter; values must carry business expiry to avoid outliving link. Immediate ban needs invalidation broadcast, short TTL, or strong verification path. Single Redis GET per jump — pipeline only helps when multiple independent commands.

Bloom filter not needed for deduplication (auto-increment + reversible encoding, unique index is final judge). Can reduce invalid origin traffic but only safe negative when all valid codes in same valid-version filter. Async filter writes, snapshot restores, version skew cause false negatives — un-synced filter only hint/load-shed, not authoritative 404. Full 56.8B codes at 1% false positive needs ~68G bits, plus impl/replica overhead; per-instance full replication not default.

Redirect strategy: mutable/revocable links prefer 302/307; 301/308 may be cached by clients/intermediaries hindering revocation. Explicitly allow only GET/HEAD or other methods. Log response code, hit layer, target domain, risk result; avoid high-cardinality labels (full URL, code, idempotency key).

Database Failover and Recovery: Authority Must Prove No Rollback

Scenario: primary advances boundary 100001→200001, instance A gets [100001,200001), issues some codes; advance not replicated to promoted replica; new primary re-issues overlapping range. Double buffer cannot fix. Production rules: confirmed allocations must pass durability/replication verification consistent with recovery target; promotion must confirm candidate contains all confirmed allocations and isolate old primary/write paths; if high-water mark cannot be proven, pause new segment requests — do not "try continue"; define failure policy for confirmed non-overlapping local ranges; backup restore cannot reset boundary from mapping table max ID (may miss allocated-but-unpersisted or in-memory IDs); add epoch field only helps if it participates in ID space partitioning or is enforced by persistence layer as write fence.

Failure runbook: (1) switch create service to read-only/reject, keep jump running; (2) isolate old primary/pods/pools; (3) collect alloc table, audit, HA confirmed positions, app logs; (4) verify candidate authority contains all confirmed allocations; (5) if unprovable, do not advance — use reserved space or manual recovery; (6) validate with concurrent segment fetch, immediate create+jump, audit interval reconciliation; (7) record incident window, discarded space, capacity budget. "Service port up" ≠ recoverable; high-water correctness is proof.

Kubernetes Probes: Ready = Safe to Allocate, Live = Process Progressing

Startup : accept create traffic only after first segment loaded, config and authority connection verified.

Ready : combines current/standby remaining time, recent load errors/backoff; add hysteresis to avoid threshold flapping.

Live : detects deadlock, event-loop stall, internal stall; transient DB unavailability should not trigger restart storm.

Graceful shutdown : set draining, stop new creates, wait in-flight to deadline; discard unused segments, do not return.

Scale-out : HPA cannot create safe segments during DB outage; new pods have no segments, HPA ≠ capacity reserve.

After restart, do not resume local disk cursor — snapshot may lag returned IDs; without full persistence and exclusive recovery protocol, reusing old segment is riskier than wasting it.

Migrating from Redis to Segment: Switching Allocation Authority

Can pause creates : (1) pause create entry, jump continues; (2) stop old Redis calls, drain in-flight/retries, isolate old service; (3) reconcile trusted Redis counter, allocated records, unknown commits, recovery info → safe high-water mark H; (4) initialize new pool > H, verify not past six-char limit; (5) canary verify create, idempotent retry, immediate jump; (6) keep old config banned; rollback must not re-enable lagging Redis counter. Mapping max ID only cross-check, cannot override IDs already issued but unpersisted, commit-unknown, or still held in instance memory.

Cannot pause creates : old and new systems must use disjoint integer ranges or different domain/path prefix namespaces. Old system rejects at its boundary, never crosses. Shadow validation only verifies isolated space correctness/performance, not "pick one of two independently generated codes".

Observability, Alerting, and Failure Acceptance

Key metrics: exhaustion prevention (current/standby remaining, per-instance estimated seconds, global remaining days); prefetch anomaly detection (allocation txn P50/P95/P99, failure classification, load duration, executor rejection, switch wait); waste quantification (confirmed allocated, mapping committed, unknown-commit discarded, publish discarded, unused reserve); user result validation (201 success rate, immediate jump success rate, error 404, primary origin fallback, negative-cache hit); audit recovery (allocation high-water, audit interval continuity, recovery drill results, fence rejections). Labels: instance, biz_tag, failure category — never code, full URL, request key (cardinality leak, PII). Alert on remaining time not percentage: low-traffic 5% may last long, high-traffic 30% may be seconds.

Mandatory fault matrix (11 scenarios): tiny segment contention (length 1/2/3, multi-thread switch) → no dup, no OOB, no permanent wait; stale reference recovery (barriers at range read and take) → no cross-generation allocation; commit ack loss (disconnect after COMMIT) → unconfirmed interval not published, retry non-overlapping; multi-instance segment fetch (concurrent record all confirmed) → pairwise disjoint in same namespace; prefetch failure (inject lock wait, net timeout, task reject) → bounded failure, backoff recovers, loading not stuck; pod hard kill (terminate after two segments) → new instance no reuse, waste observable; replica lag (jump immediately after commit) → 201 links no erroneous 404; negative-cache pre-seed (visit future code then create) → meets defined visibility contract; DB failover (promote lagging replica, isolate old primary) → reject unsafe allocation, not just service alive; boundary exhaustion (test M-1, M, last segment) → last number usable then explicit reject. Persistent unique index may mask allocator defects (dup ID rejected at insert, mapping still looks unique) — tests must record allocation results and confirmed intervals directly, not just final table.

Launch Gate

Allocation results unique, never exceed six-char boundary.

All confirmed intervals non-overlapping in same namespace.

Unknown commits never published autonomously.

Every 201 immediately jumpable on defined read path.

Allocation DB loss → service runs on known reserve then bounded reject.

Recovery, failover, deploy, restart never roll back boundary.

Capacity waste explainable, auditable, alertable.

Cache, filter, replica latency do not break defined contract.

References and Applicability

Redis replication and WAIT: async replication, acknowledged writes, failure loss boundaries.

Leaf official repo and technical articles: segment mode, double buffer, public schemas. Integrate using locked-version source and DDL.

MySQL 8.0 Locking Reads: transactional locking read semantics.

Capacity, cache, recovery strategies are engineering derivations. DB HA promises, segment step, pool sizing, performance results must be validated in target environment using Section 14 fault matrix before launch.