Free Online Developer Tools - ULID, UUID, NanoID, CUID, Snowflake ID, JWT Decoder, Base64, JSON Formatter & More

Меню инструментов

Калькулятор коллизий

Оценка вероятности коллизии ULID по скорости, числу узлов и длительности. Сначала граница дней рождения на 80 бит внутри миллисекунды, затем накопление по всему окну.

Калькулятор коллизий ULID

Оцените риск коллизии идентификаторов в вашей распределенной системе на основе объема генерации, количества машин и длительности работы.

Что такое коллизия ULID

ULID занимает 128 бит и записывается 26 символами Crockford Base32. Первые 48 бит - это метка времени Unix в миллисекундах. Остальные 80 бит случайны. Два ULID равны только когда совпали обе части, поэтому коллизия возможна лишь внутри одной общей миллисекунды.

Из-за этого огромный итог за месяцы обычно ни о чем не говорит. Парадокс дней рождения считается не по сумме за все время. Он считается по идентификаторам, попавшим в одну миллисекунду, а затем этот маленький шанс повторяется для каждой миллисекунды окна.

Формула на этой странице

Внутри одной миллисекунды n случайных 80-битных суффиксов берутся из пространства d = 2^80. Вероятность хотя бы одного повтора - это граница дней рождения. При умеренном n она около n(n-1) / 2^81, потому что 2 x 2^80 = 2^81. 2^80 равно 1 208 925 819 614 629 174 706 176.

Калькулятор использует близкую форму n^2 / 2^81 на миллисекунду. Она чуть выше, чем n(n-1) / 2^81. n - это число ID всего кластера за одну миллисекунду: скорость узла, переведенная в ID за миллисекунду, умноженная на число узлов. M - число миллисекунд в интервале. Год считается как 365,25 суток, месяц как 30,4375 суток: так устроена форма. Вероятность хотя бы одной коллизии за все окно около 1 - exp(-M x n^2 / 2^81). Если показатель меньше 10^-6, страница печатает сам показатель: 1 - exp(-x) тогда неотличим от x.

Модель предполагает, что скорость размазана равномерно и каждый узел выбирает суффикс независимо. Всплеск, который сваливает много ID в несколько миллисекунд, опаснее той же средней скорости: вероятность растет как n в квадрате.

Примеры с числами

Одна миллисекунда, 1 000 ID. По более точному числу пар: 1 000 x 999 / 2^81 = 4,13 x 10^-19. Порядка триллиона ID в ту же миллисекунду нужно, чтобы вероятность стала обычной. 2^40 - это около 1,1 x 10^12.

Значения формы по умолчанию: 100 ID в секунду на каждом из 10 узлов в течение 5 лет. Это 1 ID на миллисекунду на весь кластер (100 / 1 000 x 10). M равен 157 788 000 000 миллисекунд. Столько же и всего ID: 157 788 000 000. Накопленная вероятность около 6,53 x 10^-14, примерно 1 к 15 триллионам. При среднем одном ID на миллисекунду пары в большинстве миллисекунд нет, поэтому форма n^2 здесь слегка завышает риск.

Скорость, на которой число уже видно: 50 000 ID в каждую миллисекунду в течение суток. M равен 86 400 000. Показатель около 8,93 x 10^-8, примерно 1 к 11,2 миллиона. Это 50 миллионов ID в секунду. Такой темп бывает у кластера, а не у одного процесса.

Когда это нужно

  • Вы выбираете ULID первичным ключом и хотите число под свой объем, а не лозунг про 80 бит.
  • Нужно увидеть, что важны ID за миллисекунду, а не число строк в таблице.
  • Вы сравниваете эту модель со Snowflake, где коллизия - это ошибка координации, или с UUID v4, где парадокс дней рождения считается по всей истории сразу.

Типичные ошибки

  • Не подставляйте сумму за все время в одну формулу дней рождения. Это притворяется, будто все ID созданы в одну миллисекунду, и раздувает риск на много порядков.
  • Монотонный ULID - другая модель. Библиотеки, которые увеличивают случайное поле внутри одного процесса, не столкнутся сами с собой, пока 80-битный счетчик не обернется, а он не обернется. Риск остается только между процессами, которые не координируются.
  • Откат часов может повторить миллисекунду. Если случайное поле при этом сбрасывается, предположение о новом выборе уже неверно.
  • Страница не смотрит в базу. Одинаковый ввод всегда дает одну и ту же оценку.
  • Число узлов важно, только если эти узлы берут значения из одного 80-битного пространства в одну миллисекунду. Локальный монотонный счетчик процесса - не эта модель.

Чем отличаются модели коллизий

ФорматГде возможен повторЧто измерять
ULID (случайный суффикс)Та же миллисекунда и те же 80 случайных битID за миллисекунду, затем повтор по окну
UUID v4В любой момент всей историиСумму за все время против 122 случайных бит (около n^2 / 2^123)
SnowflakeТа же миллисекунда, тот же дата-центр, тот же worker, тот же sequenceСовпадение worker и переполнение sequence, а не случайную границу дней рождения
CUID2 (официальный, длина 24)В любой момент, без корзины по времениДлину. Буква плюс 23 символа base36 - около 124 бит

Вопросы

Почему ULID может столкнуться только внутри одной миллисекунды?

Первые 48 бит - это метка времени. Другая миллисекунда дает другой префикс, поэтому 80-битные суффиксы не сравниваются сквозь время. Равенство требует и префикса, и суффикса.

Откуда в формуле 2^81?

У случайного суффикса d = 2^80 значений. Первый член границы дней рождения - n(n-1) / (2d). 2d - это 2^81. Калькулятор использует n^2 / 2^81: та же идея, чуть консервативнее.

Вероятность 10^-14 уже безопасна?

Для идентификаторов да. Она намного ниже того, что имеет значение для ключа базы. Смотреть нужно, сколько ID делят одну миллисекунду. Среднее около 1 - это еще не режим коллизий. Десятки тысяч на миллисекунду, и так долго, делают показатель заметным, но он все еще мал.

Меняет ли монотонный ULID этот расчет?

Да. Монотонный генератор тратит случайные биты как счетчик внутри одного процесса и не повторит значение в ту же миллисекунду. Эта страница моделирует независимые случайные выборы. Считайте ей такую схему, а не счетчик на процесс.

Узнаю ли я, есть ли дубликат уже в таблице?

Нет. Это вероятность по скорости, числу узлов и длительности, которые вы вводите. Страница не подключается к базе, и введенное не загружается.

Связанные инструментыГенератор ULIDSnowflake IDГенератор CUID
Купите разработчику кофе для поддержки проекта