Генерация коротких кодов: base62, хеш и случайные коды

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

Большая часть решения определяется числами, поэтому в этой статье мы их разбираем. 7-символьный код base62 имеет ровно 3 521 614 606 208 значений, а у случайного есть шанс 50% хотя бы на одну коллизию примерно после 2,2 миллиона ссылок. Первый факт заставляет 7 символов казаться огромными. Второй - граница парадокса дней рождения, и именно из-за неё «триллионы возможностей» не означают «никаких коллизий».

Если вам нужна вся система вокруг кода (хранение, редиректы, кэширование), начните со статьи как построить сервис сокращения 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^длина, а парадокс дней рождения говорит, что среди 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. В точке 100M ссылок и 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. Сторону брендинга освещает руководство по красивым URL.

Случайные 7-символьные коды могут также сложиться в нечто неудачное. Пропускайте сгенерированные коды через короткий чёрный список и выбирайте заново при совпадении. Это почти ничего не стоит.

Перечисление, угадываемость и приватность

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

Если место назначения должно оставаться приватным, код должен быть правом доступа. Это значит как минимум 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