Генерація коротких кодів: base62, хеш чи випадкові коди

Генерація коротких кодів зводиться до чотирьох варіантів: закодувати унікальний лічильник у base62, витягнути випадкові символи, обрізати хеш URL або роздавати діапазони ідентифікаторів від координатора. Лічильники ніколи не стикаються, але їх можна вгадати. Випадкові коди вгадати не можна, але вони потребують шляху повторної спроби. Хеш з обрізанням - найслабший із чотирьох, бо стикається раніше, ніж люди очікують, і не дає вам нічого, чого не дають інші.

Більшість вирішують числа, тож цей допис їх розбирає. 7-символьний код base62 має рівно 3 521 614 606 208 значень, а випадковий має 50% шансу принаймні однієї колізії після приблизно 2,2 мільйона посилань. Перший факт змушує 7 символів здаватися величезними. Другий - це межа парадоксу днів народження (birthday bound), і саме тому "трильйони можливостей" не означає "жодних колізій".

Якщо вам потрібна вся система навколо коду (зберігання, редиректи, кешування), почніть із матеріалу як створити скорочувач URL. Це наближення одного рішення з того розбору: звідки береться короткий код.

Кодування base62 для автоінкрементного ідентифікатора

Кодування base62 перетворює число на рядок із 62 символів 0-9, a-z, A-Z. Це та сама ідея, що й шістнадцяткова система, але з більшим алфавітом, і це найкоротша безпечна для URL текстова форма цілого числа, що уникає розділових знаків. Ідентифікатор 125 стає 21 (2 x 62 + 1), а 1 000 000 стає 4c92.

const ALPHABET =
  "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

export function encode(id: bigint): string {
  if (id === 0n) return ALPHABET[0];
  let out = "";
  while (id > 0n) {
    out = ALPHABET[Number(id % 62n)] + out;
    id /= 62n;
  }
  return out;
}

export function decode(code: string): bigint {
  let id = 0n;
  for (const ch of code) id = id * 62n + BigInt(ALPHABET.indexOf(ch));
  return id;
}

Сила в тому, що унікальність успадковується від бази даних. Рядок 41 000 000 отримує один код, і ніхто інший ніколи його не отримає. Немає циклу повторних спроб і пошуку перед вставкою. Коди також ростуть повільно: ідентифікатори менші за 62^6 дають коди з шести символів або менше, а перший 7-символьний код з'являється на ідентифікаторі 56 800 235 584.

Слабкість - розкриття. Код - це номер рядка під маскою, тож decode("4c92") повертає 1000000. Будь-хто може порахувати ваші посилання, оцінити ваше зростання з двох зразків з інтервалом у тиждень і перебрати кожен код по порядку. Для внутрішнього інструмента це нормально. Для публічного скорочувача це безкоштовний API для скрейпінгу, що важливо для ризиків відкритого редиректу та перерахування, розглянутих в іншому місці цього блогу.

Ви можете сховати порядок, не втрачаючи унікальності, пропустивши ідентифікатор через оборотну перестановку (звичний вибір - невелика мережа Фейстеля) перед кодуванням. Остерігайтеся ярликів. Множення на константу за модулем 62^7 виглядає перемішаним, але зберігає зростання останньої цифри, що показує швидкий тест. Перемішаний лічильник - це обфускація, а не секретність.

Випадкові коди: простір ключів, повторні спроби та межа парадоксу днів народження

Випадковий короткий код тягне кожен символ незалежно з алфавіту. Використовуйте криптографічне джерело та неупереджений вибір. randomInt(62) у Node виконує вибірку з відхиленням за вас, тоді як byte % 62 перекошує розподіл, бо 256 не кратне 62.

import { randomInt } from "node:crypto";

export function randomCode(length = 7): string {
  let out = "";
  for (let i = 0; i < length; i++) out += ALPHABET[randomInt(62)];
  return out;
}

Якої довжини має бути код? Простір ключів - 62^length, а парадокс днів народження каже, що серед n випадкових витягнень із N значень імовірність принаймні одного повтору становить приблизно 1 - e^(-n²/2N). Вона сягає 50% приблизно за sqrt(2N ln 2) витягнень. Парадокс днів народження контрінтуїтивний, бо кількість пар росте як квадрат n.

Остання колонка - це число, що має значення для експлуатації. Повтор серед усіх ваших посилань майже напевно трапиться у великому масштабі, але ваш код насправді стикається з єдиною вставкою, що потрапляє на зайняте місце, а цей шанс - просто links / keyspace. За 100 мільйонів посилань і 7 символів одна вставка приблизно з 35 000 стикається. Ви побачите це в продакшені, тож вам потрібен шлях повторної спроби, але він дешевий.

Обробка колізій: нехай вирішує база даних

Шаблон, що працює, - вставити й повторити, а не перевірити й вставити. Два запити можуть обидва перевірити, що aB3x9Qz вільний, а потім обидва його записати. Обмеження унікальності на стовпці коду закриває цю гонку, а невдала вставка - ваш сигнал витягнути знову.

export async function createWithRetry(
  tryInsert: (code: string) => Promise<boolean>, // false = unique violation
  attempts = 5,
): Promise<string> {
  for (let i = 0; i < attempts; i++) {
    const code = randomCode();
    if (await tryInsert(code)) return code;
  }
  throw new Error("could not allocate a short code");
}

Тут tryInsert виконує ваш INSERT і повертає false лише за помилки порушення унікальності, ніколи за інших збоїв. Якщо одна вставка стикається з імовірністю p, усі спроби зазнають невдачі з імовірністю p^attempts. У точці 100 млн посилань і 7 символів p дорівнює 2,84 x 10^-5, тож три невдачі поспіль - це близько 2,3 x 10^-14. Обмежуйте кількість спроб усе одно. Якщо ви колись побачите, що ліміт досягнуто, простір ключів майже заповнений або джерело випадковості зламане, і гучна помилка краща за нескінченний цикл.

Та сама дисципліна стосується ідемпотентності на кінцевій точці створення, бо повторений HTTP-запит не повинен створювати друге посилання. Цю половину розглядають ліміти запитів та ідемпотентність.

Хеш з обрізанням: чому він стикається раніше, ніж ви думаєте

Хешування URL виглядає привабливо, бо воно детерміноване: той самий URL завжди дає той самий код, тож можна пропустити пошук дублікатів. Ціна в тому, що в коду є лише обмежена кількість бітів. Взяття 32 бітів дайджесту дає 2^32 = 4 294 967 296 значень, а точка 50% колізії - близько 77 163 URL. Не мільярди. 7-символьний зріз base62 (близько 41,7 біта) підштовхує це приблизно до 2,2 мільйона, що дорівнює випадковому 7-символьному коду.

import { createHash } from "node:crypto";

export function hashCode(url: string, length = 7): string {
  const digest = createHash("sha256").update(url).digest();
  const n = digest.readBigUInt64BE(0) % 62n ** BigInt(length);
  return encode(n).padStart(length, "0");
}

Тож обрізання не ламає хеш. SHA-256 у порядку. Стійкість до колізій повних 256 бітів просто не переживає обрізання до 41 біта. Ви успадковуєте поведінку випадкових кодів, тож вам усе одно потрібен шлях повторної спроби, плюс правило, що робити при зіткненні (додати сіль і хешувати знову). А детермінованість працює проти вас: двоє клієнтів, що скорочують той самий URL, отримують той самий код, а отже й той самий потік кліків, якщо не підмішати ідентифікатор облікового запису. Я б пропустив хеш з обрізанням майже в усіх випадках. Якщо вам потрібна дедуплікація, шукайте URL за стовпцем хешу й усе одно генеруйте код іншим способом.

Діапазони лічильників та ідентифікатори в стилі Snowflake

Один автоінкрементний стовпець стає вузьким місцем, коли кілька записувачів у кількох регіонах потребують ідентифікаторів. Два шаблони уникають цього, не відмовляючись від унікальності.

Перший - діапазони лічильників. Координатор видає кожному екземпляру застосунку блок, скажімо 1000 ідентифікаторів, а екземпляр кодує їх локально без звернення до мережі на кожне посилання. Якщо екземпляр помирає, його невикористаний блок просто пропускається. Пропуски в просторі кодів на трильйони безпечні.

Другий - ідентифікатор у стилі Snowflake: мітка часу, ідентифікатор машини та послідовність у межах мілісекунди, упаковані в 64 біти. Вони сортуються за часом створення й не потребують координатора. Підступ для коротких посилань - довжина. 64-бітове значення сягає 18 446 744 073 709 551 615, а оскільки 62^10 = 839 299 365 868 340 224 менше за 2^64, потрібно до 11 символів base62. Це не дуже коротко. Ідентифікатори Snowflake краще пасують до ключів бази даних, ніж до публічних кодів, тож більшість скорочувачів тримають їх внутрішніми й використовують окремий, коротший код.

Обидва успадковують проблему послідовної вгадуваності, бо обидва впорядковані за побудовою. Обгорніть їх у перестановку або використовуйте лише один із них як внутрішній первинний ключ.

Власні коди та зарезервовані слова

Слаги-"візитівки" - єдине місце, де код обирає людина, і вони проходять через те саме обмеження унікальності, що й усе інше. Додаткова робота - валідація перед вставкою. Власну задню частину на кшталт /spring-sale треба перевірити за трьома пунктами.

• Зарезервовані слова. Шляхи, які вже використовує ваш застосунок або вебсередовище, ніколи не повинні бути доступними для заяви: api, admin, login, static, robots.txt, favicon.ico і .well-known. Скорочувач, що дозволяє комусь зареєструвати /login, побудував генератор фішингових сторінок.
• Колізії зі згенерованими кодами. Якщо користувач займає /aB3x9Qz, ваш випадковий генератор пізніше може створити той самий рядок. Обмеження унікальності це обробляє, доки власні та згенеровані коди ділять один простір імен.
• Регістр і візуальні двійники. Base62 чутливий до регістру, тож /Ab і /ab - різні посилання. Вирішіть, чи порівнюються власні слаги без урахування регістру, і розгляньте блокування пар, що відрізняються лише 0/O чи l/1. Бік брендингу охоплює посібник про vanity URL.

Випадкові 7-символьні коди також можуть скласти щось прикре. Пропускайте згенеровані коди через короткий список блокування й витягуйте знову при збігу. Це коштує майже нічого.

Перерахування, вгадуваність і приватність

Короткий код - це адреса. Це не секрет, і жодна довжина не перетворить його на секрет. Проте різниця між послідовним і випадковим велика. З послідовними кодами кожне вгадування потрапляє на живе посилання. З 10 мільйонами посилань, випадково розподілених по 62^7 значеннях, сліпе вгадування потрапляє на одне з імовірністю 10 000 000 / 3 521 614 606 208, близько 1 до 352 000. Сканеру потрібні сотні тисяч запитів на одну знахідку, що обмеження частоти запитів і виявлення ботів можуть покарати.

Якщо ціль має лишатися приватною, код має бути можливістю (capability). Це означає щонайменше 128 бітів випадковості, що в base62 становить 22 символи (62^22 - це близько 2^131; 21 символ дають лише близько 2^125). Йому також потрібна справжня перевірка доступу за ним. Настанова OWASP щодо небезпечних прямих посилань на об'єкти каже те саме: непередбачувані ідентифікатори допомагають, але засіб контролю - авторизація. Посилання із захистом паролем чи обмеженим терміном дії - для випадків, коли витік коду зашкодить. Контрольний список безпеки скорочувача URL перелічує засоби контролю, які варто поєднати з цим, а механіка роботи скорочувачів пояснює, чому сам код ніколи не може нести довіру.

Джерело випадковості важливе з тієї самої причини. Генератор з початковим значенням без криптографічної стійкості можна передбачити за кількома виходами, тож використовуйте CSPRNG платформи, як у фрагменті вище. Для готових альтернатив nanoid реалізує підхід неупередженого вибору з налаштовуваним алфавітом і довжиною.

Який підхід обрати

Обирайте за тим, що код має пережити.

• Внутрішній інструмент, малий обсяг: base62 автоінкрементного ідентифікатора. Просто, без колізій, а вгадуваність не має значення.
• Публічний скорочувач, одна база даних: випадкові 7-символьні коди з вставкою й повторною спробою. Я б почав тут. Таблиця вище показує, що шанси колізій лишаються крихітними роками, а перехід на 8 символів пізніше - це зміна в один рядок, що зберігає чинність кожного наявного посилання.
• Записи з кількох регіонів: діапазони лічильників або ідентифікатори Snowflake як внутрішній ключ, плюс перестановка чи випадковий код для того, що бачить публіка.
• Хеш з обрізанням: лише якщо вам потрібні детерміновані коди, і тоді сприймайте його як випадковий код з гіршою історією повторних спроб.

Що б ви не обрали, зберігайте код у стовпці з унікальним індексом і тримайте генерацію поза шляхом редиректу, де дворівневий кеш виконує справжню роботу (розбір про p95 затримку показує, як цей шлях виглядає після налаштування). Якщо ви не хочете володіти генерацією кодів, обробкою колізій і списками зарезервованих слів, API Elido приймає ціль і повертає коротке посилання, а власні задні частини валідуються за вас. Перегляньте плани, коли захочете спробувати.

Пов'язані публікації в блозі

• Як створити скорочувач URL - повна архітектура, яку цей допис наближає.
• Як працюють скорочувачі URL - концептуальний вступ.
• Що таке власна задня частина? - половина простору кодів, яку обирає людина.
• Стратегія кешування для редиректів URL - що відбувається після появи коду.
• Вразливості відкритого редиректу - чому код має відображатися на збережену ціль.
• Контрольний список безпеки скорочувача URL