Почему UUID практически никогда не совпадают (даже без проверки)

Стандартный случайный UUID генерируется независимо любым количеством полностью нескоординированных систем, без какого-либо центрального органа, выдающего следующий доступный идентификатор, и без всякой проверки по какому-либо списку уже используемых идентификаторов — и тем не менее совпадения практически, для всех практических целей, никогда не происходят. Это по-настоящему смелое утверждение, целиком опирающееся на вероятность, а не на координацию, и понимание того, почему оно справедливо, требует того же самого фрагмента контринтуитивной математики, который объясняет куда более знаменитую головоломку: как мало людей должно оказаться в комнате, чтобы у двоих из них, скорее всего, совпал день рождения.

Классический парадокс дней рождения спрашивает, сколько людей должно собраться в комнате, прежде чем шанс на то, что у двоих из них совпадёт день рождения, превысит 50%, и ответ — всего 23 человека против 365 возможных дней рождения — удивляет большинство людей, которые интуитивно ожидают, что число будет намного ближе к 365. Причина, по которой настоящий ответ настолько меньше, в том, что значимое сравнение — не «совпадает ли чей-то конкретный день рождения с моим», а «совпадает ли день рождения у какой-либо пары из всех возможных пар в комнате», а число возможных пар растёт намного быстрее, чем число людей: уже при 23 людях существует 253 различные пары, и каждая из них — независимая возможность совпадения. Именно этот математический паттерн — число возможностей для сравнения растёт квадратично, тогда как число элементов растёт лишь линейно — называется задачей о днях рождения, и он напрямую применим к любой ситуации, включающей случайные значения, взятые из фиксированного пространства и проверяемые на дубликаты, а UUID сюда прекрасно вписываются.

Стандартный случайный UUID (версии 4) берёт значения из пространства в 122 по-настоящему случайных бита — горстка из 128 бит целиком зафиксирована самой спецификацией формата для обозначения версии, — а значит общее число возможных значений составляет 2 в степени 122, почти непостижимо огромное число. Применение того же рассуждения из парадокса дней рождения, что использовалось в примере с 365 днями, но масштабированного до этого гораздо большего пространства, даёт точку, в которой совпадение становится вероятным: потребовалось бы сгенерировать примерно 2,7 квинтиллиона UUID, прежде чем вероятность совпадения хотя бы двух из них поднимется примерно до 50% — для сравнения, это больше UUID, чем оценочное количество песчинок на всех пляжах Земли. Одной системе или даже большому количеству систем вместе, генерирующих UUID с любой реалистичной для реального мира скоростью, потребовалось бы время, во много раз превышающее возраст Вселенной, чтобы приблизиться к этому порогу, и именно это является настоящим математическим основанием для того, чтобы относиться к совпадениям UUID как к тому, что на практике не нужно проверять.

UUID версии 7, стандартизированный сравнительно недавно специально для того, чтобы создавать идентификаторы, сортирующиеся примерно в хронологическом порядке, достигает этого, размещая временную метку с точностью до миллисекунды в старших битах идентификатора, вместо того чтобы заполнять всё значение случайными данными, как это делает версия 4. Может показаться, что это должно ослаблять гарантию устойчивости к совпадениям, поскольку часть значения теперь предсказуема, а не случайна, — но оставшиеся биты по-прежнему заполняются тем же количеством по-настоящему случайных данных, что и раньше, и поскольку двум UUID, сгенерированным в одну и ту же миллисекунду, всё равно нужно, чтобы их случайный остаток случайно совпал в точности, практическая устойчивость к совпадениям остаётся сравнимой с версией 4 при любой реалистичной скорости генерации. То, что на самом деле меняет v7, — это другое, не связанное с этим свойство — порядок сортировки, а вовсе не обсуждаемая здесь математика совпадений, и эти два аспекта стоит держать концептуально раздельно: уникальность берётся из самого размера случайного пространства, тогда как возможность сортировки — из того, где внутри значения расположена временная метка.

Поскольку вероятность совпадения по-настоящему, а не просто на словах, ничтожна, системы могут генерировать уникальные идентификаторы совершенно независимо друг от друга — мобильное приложение, работающее офлайн без сетевого подключения, бессерверная функция, которая запускается и исчезает за миллисекунды, тысяча параллельных экземпляров микросервиса, работающих одновременно, — без какой-либо координации между ними и без центрального реестра, отслеживающего уже выданные идентификаторы, и при этом иметь математически обоснованное ожидание, что никакие два из этих идентификаторов никогда не совпадут. Это именно то свойство, которое централизованно выдаваемый последовательный идентификатор никогда не смог бы предложить без общего координирующего органа, замедляющего всё вокруг, и именно в этом вся причина, по которой случайные UUID стали стандартным выбором для распределённых систем, которым нужны идентификаторы в темпе, за которым не могла бы угнаться никакая процедура координации.