UUID: почему “уникальный” это на самом деле про вероятность
Разбирался тут, откуда у UUIDv4, самой популярной 4-й версии, берётся “уникальность”, и оказалось интереснее, чем казалось.
UUID (Universally Unique Identifier, “универсальный уникальный идентификатор”) — это просто 128-битное число, записанное как 32 hex-символа через дефисы для читаемости. Выглядит это так:
Сами дефисы и группы — просто визуальное удобство, никакой отдельной структуры в них нет. У v4 122 бита случайны, 6 фиксированы (обозначающие версию/вариант) — например, четверка сразу после второго дефиса всегда означает “версия 4”.
Никакого хеширования при его генерации — это результат работы специального генератора случайных чисел.
“Уникальность” здесь — не теорема, а оценка вероятности через классическую задачу о Днях Рождения:
Уже для 23 человек получаем вероятность ‘коллизии’ выше 50% (Дня Рождения в один день хотя бы у одной пары людей).
Теперь для UUID:
– количество “дней в году”: 2^122 (именно столько случайных бит, остальные 6 фиксированы)
– количество “людей” — число сгенерированных ID: n
Из-за огромного количества вариантов (2^122), тут 23 уже не хватит для коллизии: чтобы получить вероятность коллизии в 50% на таком большом пространстве, нужно сгенерировать n~2⁶¹ UUID (это больше миллиона триллионов) ❗️
На практике это оказывается, по сути, невозможным — в том же смысле, в каком невозможно случайно угадать чужой приватный ключ (скорее в лотерею джекпот выиграешь 😀)
Самое интересное — откуда берётся сама случайность.
Ядро операционной системы (ОС) собирает энтропию, она же “случайность внешнего мира” (джиттер прерываний, тепловой шум в транзисторах, микро-колебания силы тока в процессоре), но её мало и она медленная (не так много событий за единицу времени, а генерировать нужно много ID). Поэтому её “растягивают” через CSPRNG (cryptographically secure pseudorandom number generator) — детерминированный алгоритм (ChaCha20 в Linux, AES-CTR в других системах), который по сути своей не случаен, но выдаёт последовательность чисел, которую невозможно отличить от случайной за разумное время вычислений — так называемое computational indistinguishability.
Мой математический бекграунд потребовал разобраться, а есть ли тут вообще формальное доказательство 🤓 И тут есть нюанс.
Формальные доказательства такого рода существуют — например, Blum, Blum, Shub (1986) построили генератор, для которого можно математически доказать: если найдётся способ отличить его вывод от случайного, то тем же способом можно решить задачу факторизации большого числа. Красивая штука — но такой генератор слишком медленный для реального использования, это скорее демонстрация того, что подобное доказательство в принципе возможно.
А вот у ChaCha20 и AES — то, что реально реализовано в ОС и генерирует UUID — такого чистого сведения к одной понятной математической задаче нет. Их надёжность держится на другом основании: ~40 лет попыток взлома лучшими криптоаналитиками мира, ни одна из которых не увенчалась успехом.
То есть в криптографии в принципе нет ни одного алгоритма с абсолютным доказательством “это невозможно взломать” — есть два разных вида уверенности:
- либо чистое математическое сведение к нерешённой задаче (факторизация, но такие генераторы медленные),
- либо эмпирическая устойчивость к криптоанализу (быстрые алгоритмы вроде ChaCha20, которые реально используются).
Индустрия выбрала второй путь — не потому что математика не важна, а потому что для быстрых алгоритмов такого изящного сведения пока просто не существует.
Так что “уникальность” UUID — это, по сути, очень хорошая случайность, чья надёжность держится не на теореме, а на репутации, проверенной десятилетиями попыток её разрушить.
@faangiscalling
Разбирался тут, откуда у UUIDv4, самой популярной 4-й версии, берётся “уникальность”, и оказалось интереснее, чем казалось.
UUID (Universally Unique Identifier, “универсальный уникальный идентификатор”) — это просто 128-битное число, записанное как 32 hex-символа через дефисы для читаемости. Выглядит это так:
f47ac10b-58cc-4372-a567-0e02b2c3d479
Сами дефисы и группы — просто визуальное удобство, никакой отдельной структуры в них нет. У v4 122 бита случайны, 6 фиксированы (обозначающие версию/вариант) — например, четверка сразу после второго дефиса всегда означает “версия 4”.
Никакого хеширования при его генерации — это результат работы специального генератора случайных чисел.
“Уникальность” здесь — не теорема, а оценка вероятности через классическую задачу о Днях Рождения:
В группе из N человек какова вероятность, что хотя бы у двух из них День Рождения в один день?
Уже для 23 человек получаем вероятность ‘коллизии’ выше 50% (Дня Рождения в один день хотя бы у одной пары людей).
Теперь для UUID:
– количество “дней в году”: 2^122 (именно столько случайных бит, остальные 6 фиксированы)
– количество “людей” — число сгенерированных ID: n
Из-за огромного количества вариантов (2^122), тут 23 уже не хватит для коллизии: чтобы получить вероятность коллизии в 50% на таком большом пространстве, нужно сгенерировать n~2⁶¹ UUID (это больше миллиона триллионов) ❗️
На практике это оказывается, по сути, невозможным — в том же смысле, в каком невозможно случайно угадать чужой приватный ключ (скорее в лотерею джекпот выиграешь 😀)
Самое интересное — откуда берётся сама случайность.
Ядро операционной системы (ОС) собирает энтропию, она же “случайность внешнего мира” (джиттер прерываний, тепловой шум в транзисторах, микро-колебания силы тока в процессоре), но её мало и она медленная (не так много событий за единицу времени, а генерировать нужно много ID). Поэтому её “растягивают” через CSPRNG (cryptographically secure pseudorandom number generator) — детерминированный алгоритм (ChaCha20 в Linux, AES-CTR в других системах), который по сути своей не случаен, но выдаёт последовательность чисел, которую невозможно отличить от случайной за разумное время вычислений — так называемое computational indistinguishability.
Мой математический бекграунд потребовал разобраться, а есть ли тут вообще формальное доказательство 🤓 И тут есть нюанс.
Формальные доказательства такого рода существуют — например, Blum, Blum, Shub (1986) построили генератор, для которого можно математически доказать: если найдётся способ отличить его вывод от случайного, то тем же способом можно решить задачу факторизации большого числа. Красивая штука — но такой генератор слишком медленный для реального использования, это скорее демонстрация того, что подобное доказательство в принципе возможно.
А вот у ChaCha20 и AES — то, что реально реализовано в ОС и генерирует UUID — такого чистого сведения к одной понятной математической задаче нет. Их надёжность держится на другом основании: ~40 лет попыток взлома лучшими криптоаналитиками мира, ни одна из которых не увенчалась успехом.
То есть в криптографии в принципе нет ни одного алгоритма с абсолютным доказательством “это невозможно взломать” — есть два разных вида уверенности:
- либо чистое математическое сведение к нерешённой задаче (факторизация, но такие генераторы медленные),
- либо эмпирическая устойчивость к криптоанализу (быстрые алгоритмы вроде ChaCha20, которые реально используются).
Индустрия выбрала второй путь — не потому что математика не важна, а потому что для быстрых алгоритмов такого изящного сведения пока просто не существует.
Так что “уникальность” UUID — это, по сути, очень хорошая случайность, чья надёжность держится не на теореме, а на репутации, проверенной десятилетиями попыток её разрушить.
@faangiscalling
👍3❤2🔥1
DSA, system design и behavioral для финального рывка
Я завершил собирать свою 'боевую' библиотеку для финального рывка подготовки.
Приехали вот только что:
- новая книга Остина МакДоналда из Меты про подготовку к бихейву like a pro. Она неожиданно оказалось цветной внутри, с красивыми акварельными иллюстрациями 😍
- второй том Алекса Ху по system design. Формат подрос как и количество деталей в самой книге, выглядит скорее как v2.0, чем просто второй том. Но формат уже менее travel-friendly
- паттерны решения DSA/LeetCode снова от Алекса. Захотел попробовать альтернативу моей любимой EPIP с глубоким погружением в алгоритмы. У Алекса как и в system design книге много очень схем и картинок, книга-кандидат в refresher перед интервью как один из сценариев.
Посмотрю их в деле, расскажу вам.
@faangiscalling
Я завершил собирать свою 'боевую' библиотеку для финального рывка подготовки.
Приехали вот только что:
- новая книга Остина МакДоналда из Меты про подготовку к бихейву like a pro. Она неожиданно оказалось цветной внутри, с красивыми акварельными иллюстрациями 😍
- второй том Алекса Ху по system design. Формат подрос как и количество деталей в самой книге, выглядит скорее как v2.0, чем просто второй том. Но формат уже менее travel-friendly
- паттерны решения DSA/LeetCode снова от Алекса. Захотел попробовать альтернативу моей любимой EPIP с глубоким погружением в алгоритмы. У Алекса как и в system design книге много очень схем и картинок, книга-кандидат в refresher перед интервью как один из сценариев.
Посмотрю их в деле, расскажу вам.
@faangiscalling
👍2🔥1🙏1
Snowflake ID: как Twitter решил проблему генерации уникальных ID в распределённой системе 🪪
Раньше писал про UUID — уникальный ID без центрального сервера, но случайный и не сортируется по времени в классической версии v4.
Twitter хотел одновременно:
– генерировать ID на сотнях серверов независимо
– гарантировать уникальность
– обходиться без центральной БД
– получать ID, отсортированные времени с определенной точностью
– уложиться в 64 бита для уменьшения размера индексов, кеша
Главный челлендж здесь — разрешить конфликт между уникальностью, распределённостью и упорядоченностью по времени.
Так в 2010 году появился snowflake (не связан с хранилищем для аналитики Snowflake, а просто отражение концепции, что snowflake, то есть снежинка по-русски, никогда не повторяется, они все разные, что и ждешь от генератора ID).
Идея: один 64-битный ID с определенной структурой, решающей челлендж:
⁃ 1 резервный бит
⁃ timestamp (41 бит)
⁃ worker ID (10 бит)
⁃ sequence (12 бит)
Timestamp — миллисекунды с эпохи Twitter (с 2010 года, а не 1970 как у UNIX), в старших битах → дает простое числовое сравнение ID = сортировка по времени с точностью до миллисекунды. Этой длины в 41 бит хватит почти на 70 лет
Worker ID — какой датацентр (5 бит) и какой сервер (еще 5 бит) создал ID, по сути номер “воркера” (0 - 1023).
Sequence — номер ID внутри текущей миллисекунды у конкретного "воркера", каждую миллисекунду обнуляется (0 - 4095)
Два "воркера" создают ID независимо и эти ID никогда не пересекаются:
Какое максимальное количество ID можно генерировать в секунду?
12 бит sequence = 4096 ID с одного "воркера" за 1 миллисекунду → ~4 млн ID с одного “воркера” за 1 секунду (1000 миллисекунд)→ ~4 млрд ID на 1024 “воркерах” за секунду. Более чем достаточно для Twitter и для других практических ситуаций.
Сама идея «timestamp внутри ID» не нова — сила snowflake в удачной комбинации: distributed generation + uniqueness + temporal ordering + 64-bit integer.
Отсюда пошли Sonyflake, Instagram-style ID и другие «flake»-форматы, а позже — ULID и UUIDv7, развивающие ту же идею.
Так что хороший system design — это не всегда новый алгоритм. Иногда это просто удачно разложить требования по битам. 🙂
@faangiscalling
Раньше писал про UUID — уникальный ID без центрального сервера, но случайный и не сортируется по времени в классической версии v4.
Twitter хотел одновременно:
– генерировать ID на сотнях серверов независимо
– гарантировать уникальность
– обходиться без центральной БД
– получать ID, отсортированные времени с определенной точностью
– уложиться в 64 бита для уменьшения размера индексов, кеша
Главный челлендж здесь — разрешить конфликт между уникальностью, распределённостью и упорядоченностью по времени.
Так в 2010 году появился snowflake (не связан с хранилищем для аналитики Snowflake, а просто отражение концепции, что snowflake, то есть снежинка по-русски, никогда не повторяется, они все разные, что и ждешь от генератора ID).
Идея: один 64-битный ID с определенной структурой, решающей челлендж:
⁃ 1 резервный бит
⁃ timestamp (41 бит)
⁃ worker ID (10 бит)
⁃ sequence (12 бит)
Timestamp — миллисекунды с эпохи Twitter (с 2010 года, а не 1970 как у UNIX), в старших битах → дает простое числовое сравнение ID = сортировка по времени с точностью до миллисекунды. Этой длины в 41 бит хватит почти на 70 лет
Worker ID — какой датацентр (5 бит) и какой сервер (еще 5 бит) создал ID, по сути номер “воркера” (0 - 1023).
Sequence — номер ID внутри текущей миллисекунды у конкретного "воркера", каждую миллисекунду обнуляется (0 - 4095)
Два "воркера" создают ID независимо и эти ID никогда не пересекаются:
timestamp | worker 17 | sequence 42
timestamp | worker 18 | sequence 7
Какое максимальное количество ID можно генерировать в секунду?
12 бит sequence = 4096 ID с одного "воркера" за 1 миллисекунду → ~4 млн ID с одного “воркера” за 1 секунду (1000 миллисекунд)→ ~4 млрд ID на 1024 “воркерах” за секунду. Более чем достаточно для Twitter и для других практических ситуаций.
Сама идея «timestamp внутри ID» не нова — сила snowflake в удачной комбинации: distributed generation + uniqueness + temporal ordering + 64-bit integer.
Отсюда пошли Sonyflake, Instagram-style ID и другие «flake»-форматы, а позже — ULID и UUIDv7, развивающие ту же идею.
Так что хороший system design — это не всегда новый алгоритм. Иногда это просто удачно разложить требования по битам. 🙂
@faangiscalling
👍5🙏1
Качество жизни: Франция или не Франция🇫🇷
Мой друг, который выбирает страну для релокации спросил меня вчера про Францию 🇫🇷 и про мои впечатления. И про свое желание релоцироваться с 'улучшением качества жизни'. Сравнивает с Лондоном 🇬🇧 и Дубаем 🇦🇪
По умолчанию он представлял себе в голове концепцию улучшения качества жизни как увеличение дохода.
Я объяснил ему, что концепция самой Франции 🇫🇷 про 'улучшение качества жизни' не столько про увеличение дохода, а сколько про увеличение:
- стабильности (почти нельзя уволить)
- вкусности (очень вкусные продукты)
- красоты (шато на каждом шагу, парки, горы, пляжи)
- свободного времени (отпуск 2 месяца, спокойные обеды по 1-2 часа)
- спортивных активностей (огромное количество оборудованных веломаршрутов, бегунов, скалолазов)
- культурных мероприятий (выставки всего и вся, парижский автосалон, фестивали вина, сыра, ретро-автомобилей, фейерверков, музыки, Роби Вильямсов и Леди Гаг)
- отдыха в красивых местах (полно недорогих кемпингов)
Если нужно именно увеличить доход/капитал, то это однозначно Лондон 🇬🇧
Если достаточно просто улучшить качество жизни и жить популярный сейчас формат slow life – bienvenue en France! 🇫🇷
@faangiscalling
Мой друг, который выбирает страну для релокации спросил меня вчера про Францию 🇫🇷 и про мои впечатления. И про свое желание релоцироваться с 'улучшением качества жизни'. Сравнивает с Лондоном 🇬🇧 и Дубаем 🇦🇪
По умолчанию он представлял себе в голове концепцию улучшения качества жизни как увеличение дохода.
Я объяснил ему, что концепция самой Франции 🇫🇷 про 'улучшение качества жизни' не столько про увеличение дохода, а сколько про увеличение:
- стабильности (почти нельзя уволить)
- вкусности (очень вкусные продукты)
- красоты (шато на каждом шагу, парки, горы, пляжи)
- свободного времени (отпуск 2 месяца, спокойные обеды по 1-2 часа)
- спортивных активностей (огромное количество оборудованных веломаршрутов, бегунов, скалолазов)
- культурных мероприятий (выставки всего и вся, парижский автосалон, фестивали вина, сыра, ретро-автомобилей, фейерверков, музыки, Роби Вильямсов и Леди Гаг)
- отдыха в красивых местах (полно недорогих кемпингов)
Если нужно именно увеличить доход/капитал, то это однозначно Лондон 🇬🇧
Если достаточно просто улучшить качество жизни и жить популярный сейчас формат slow life – bienvenue en France! 🇫🇷
@faangiscalling
👍4❤2🔥2