Комментарии 68
(Если вас беспокоит возможность повтора случайных значений: выиграть джекпот в лотерее два раза подряд является гораздо более вероятным событием, чем повтор двух случайных 128-битных чисел)
Дело в том, что если клиент выиграет 2 раза подряд в лотерею, те кто устраивают лотерею не разорятся, а вот ваш проект если будет иметь 2 строки с одинаковым идентификатором - может принести печальные результаты.
Вероятность появления баги в коде, из за которого вы вставите 2 одинаковых значения, на несколько порядков выше, чем коллизия в генерации случайного uuid. Просто не забывайте создавать уникальные индексы на столбцы, которые должны содержать уникальные значения. Или объявляйте такие столбцы как primary key - тогда индекс создастся неявно.
Ага, вероятность коллизии uuid примерно такая же, как если высокоэнергетичная частица из космоса ударит в ячейку диска сервера и поменяет значение автоинкреметного id на уже существующее.
Что касается диска, то СХД сам исправит ошибку. А что касается UUID я уже не раз нарвался на его дублирование. Например, из-за совпадений UUID node в двух контейнерах. Причем проблема известная https://stackoverflow.com/questions/27971464/uuid-generated-randomly-is-having-duplicates
Естественно речь о генерации UUID на множестве хостов. С другой стороны, если уникальный ключ генерируется на одном хосте, то и UUID не нужен. Проще обычный serial использовать.
Интересная ссылка, спасибо. Но там комментаторы как раз и указывают на то, что намного вероятнее проблема в коде приложения, чем в самом механизме генерации UUID или коллизиях.
Примеры:
It could be that in your actual code, the UUIDs are getting mixed up at a later stage, e.g. due to a race condition somewhere in a higher-level layer.
But, say you generated a set of random numbers with virtual machine A. Then took a snapshot of A. Then sometime later, stopped A, resumed from the snap shot, and resumed generating random numbers
Instead, look for places where a UUID stored by one server could be clobbering one stored by another. Why does this only happen between 2 servers out of 50? That has something to do with the details of your environment and system that haven't been shared.
As stated above, the chances of a legit collision are impossibly small. A more likely possibly is if the values are ever transferred between objects in an improper way. For languages like Java that behave as pass by reference...
Можете поделиться своими историями про коллизии?
Upd 1: вижу ниже подобное обсуждение, мой вопрос неактуален
Как раз наоборот, видно, что из 50+ JVM автора, у двух одинаковый сегмент node. Вероятность такого при V4 близка к нулю. А при V1/V3 это обозначает лишь то, что у этих JVM совпали mac-адреса виртуальных сетевых адаптеров. Что, в принципе, обычное дело. Я даже на совпадение mac-адресов физических адаптеров нарывался.
У меня похожая история, только много разных поставщиков сообщений, многие из которых явно генерируют V1/V3.
V4, используемый в PotgreSQL по-умолчанию, сильно зависит от доступной энтропии. А с ней в контейнерах очень плохо. Особенно, если хостятся они тоже в VM. Поэтому вероятность поймать совпадающую энтропию при одновременном старте на разных ядрах двух контейнеров из одного и того же образа - не так уж мала.
Приводя в пример лотерею, ведь наверняка не учитывается, что попытка выиграть в неё будет делаться несколько миллионов раз в секунду? А вставка строки в таблицу, и соответственно, генерирование нового случайного ID, вполне может выполняться миллион раз в секунду. Так что мне кажется, некорректное это сравнение.
Согласно википедии, вам надо генерировать 1 миллиард случайных UUID'ов каждую секунду в течении 86 лет, чтобы схлопотать коллизию. Боюсь, у вас база раньше треснет...
На одном хосте - да. Но если речь о множестве хостов, то шансы на совпадения у них элемента node уже намного выше, особенно при контейнерной виртуализации. А уж генерация на двух хостах UUID в один момент времени имеет уже высокую вероятность.
Так как раз на разных хостах случайные uuid'ы и интересно генерировать - для горизонтального масштабирования хранилища. И в реальной практике их именно так и используют. Если бы вероятность коллизии из за этого существенно повышалась, от этой практики уже давным давно отказались бы. Но что то я об этом пока не слышал.
Я, в своей практике, на дубликаты тоже нарывался. Но, как показывало расследование этих инцидентов, во всех случаях это были "рукотворные" дубликаты. Кто-то руками написал insert с uuid'ом, взятым с другого хоста. Или кто то случайно залил бекап не на тот хост. Был даже случай, когда программист сам пытался генерировать uuid'ы с помощью инкрементации.
Вы не слышали, а я на это уже не раз нарывался. И не я один https://stackoverflow.com/questions/27971464/uuid-generated-randomly-is-having-duplicates
Почитал. Практически во всех ответах автору поста советуют поискать багу в коде. Хотелось бы увидеть более убедительное исследование, желательно с математическим обоснованием и, в идеале, бенчмарки со стабильным воспроизведением проблемы.
Плохо читали. Речь именно о том, что из множества JVM у автора в какой то паре формировался совпадающий node. А уже совпадение времени генерации сообщения на разных хостах - дело обычное.
Математическое обоснование - не придумали еще механизм формирования гарантированно разного node на разных виртуальных хостах. В пределах одного кластера k8s проблему решили. В пределах множества разных кластеров - нет.
И несколько раз в день стреляла коллизия? И всегда на одних и тех же 2х серваках? А на остальных не стреляла? Ну ну...
PS
Автору лучше посмотреть историю накатывания бекапов в базы. За сим откланяюсь :)))
Если речь об авторе топика по моей ссылке, то у него изначально совпали node на паре JVM, а он их и не пытался пересоздавать, отчего и получал коллизии постоянно.
Если же речь о моем опыте с множеством k8s кластеров, то не приписывайте мне слова кого-то постороннего. Нарвавшись на такие приколы несколько раз, я от использования только UUID, как уникального идентификатора просто отказался, добавляя к нему в составной уникальный ключ еще и мой внутренний уникальный идентификатор источника сообщений. Это проблему радикально решило и я доволен.
так вы можете написать свою функцию генерации uuid на основе своей ид ноды. Только вот при чем тут jvm к PostgreSQL, вы в приложении uuid генерили?
вы можете написать свою функцию генерации uuid
Я как раз не могу. Я могу только выкручиваться сам, получая сообщения от сторонних поставщиков информации с дублирующимися UUID.
Только вот при чем тут jvm к PostgreSQL
Потому что именно PostgreSQL выступает в качестве DWH.
В PostgreSQL есть смысл использовать UUID так же только в случае, когда он совсем не единственный поставщик информации для этой сущности. В противном случае serial всяко проще и удобней.
кстати, у mongo еще меньше байт в уникальном ObjectId(96). Удивительно, что нет постоянных дублей
Специально проверил. За этот год уже два дубля UUID в БД. Хотя сообщений еще меньше 10 млрд. Один раз задублировались белорусы с казахами, другой раз - РФ с белорусами.
у вас генератор случайных чисел сломался, почините
А с чего это Вы решили что все мои поставщики информации используют исключительно V4-V5? По моим наблюдениями, там и V1 прилетает.
Вы бы хоть почитали выше:
Если же кластеров несколько, то вероятность совпадения сегмента node в двух контейнерах разных кластеров не такая уж маленькая. Понятно, что тут сильная зависимость от версии UUID и способа генерации значения node. Но, в случае контейнеров из одного и того же образа, да еще и стартующих одновременно, например, каждый час, возможности тут довольно ограничены.
Откуда тут нормальная энтропия возьмется?
Кстати, еще несколько лет назад, даже в пределах одного кластера k8s могли подняться два контейнера в которых в UUID сегмент node совпадал. Пару лет назад эту багу поправили, но только для одного кластера. Если же кластеров несколько, то вероятность совпадения сегмента node в двух контейнерах разных кластеров не такая уж маленькая. Понятно, что тут сильная зависимость от версии UUID и способа генерации значения node. Но, в случае контейнеров из одного и того же образа, да еще и стартующих одновременно, например, каждый час, возможности тут довольно ограничены.
Погодите, если создать две абсолютно идентичные виртуальные машины, на них разве не могут генерироваться одинаковые случайные числа?
Ну, если речь о случайных числах в Java, то там вам придется запустить процессы в одно и то же время вплоть до наносекунд:
/**
* Creates a new random number generator. This constructor sets
* the seed of the random number generator to a value very likely
* to be distinct from any other invocation of this constructor.
*/
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}Если речь о случайных UUID'ах в Java, то там все несколько хитрее, используется SecureRandom:
/**
* Constructs a secure random number generator (RNG) implementing the
* default random number algorithm.
*
* <p> This constructor traverses the list of registered security Providers,
* starting with the most preferred Provider.
* A new {@code SecureRandom} object encapsulating the
* {@code SecureRandomSpi} implementation from the first
* Provider that supports a {@code SecureRandom} (RNG) algorithm is returned.
* If none of the Providers support a RNG algorithm,
* then an implementation-specific default is returned.
*
* <p> Note that the list of registered providers may be retrieved via
* the {@link Security#getProviders() Security.getProviders()} method.
*
* <p> See the {@code SecureRandom} section in the <a href=
* "{@docRoot}/../specs/security/standard-names.html#securerandom-number-generation-algorithms">
* Java Security Standard Algorithm Names Specification</a>
* for information about standard RNG algorithm names.
*/
public SecureRandom() {
/*
* This call to our superclass constructor will result in a call
* to our own {@code setSeed} method, which will return
* immediately when it is passed zero.
*/
super(0);
getDefaultPRNG(false, null);
this.threadSafe = getThreadSafe();
}Там уже все будет зависеть от сконфигурированного для JVM алгоритма:
Ну а если речь идет о случайных UUID в PostgresSQL (а в этом треде речь идет именно о нём), то обычно на виртуалках его и не разворачивают. И уж тем более раз в час не перезапускают. Ну и тем более, если вы в качестве первичных ключей используете рандомные uuid'ы, то вполне можно (и даже нужно) выдвинуть соответствующие требования к развертыванию инфраструктуры.
В общем да - признаю, если очень сильно постараться, то можно выстрелить себе прямо в коленную чашечку. А если не стараться, или даже предпринять минимальные усилия для того, чтобы не стрелять - то риск практически нулевой.
Так в виртуальной машине и время виртуальное?
По SecureRandom в Java вот интересную статью нашел:
https://blog.progwards.ru/uchimsya-pravilno-rabotat/
PS
Мне почему то казалось, что алгоритм по умолчанию это SHA1PRNG. Но я этот вопрос изучал на этапе Java 8 - возможно с тех пор что то изменилось.
Про настройку источника энтропии в виртуальных машинах можно почитать здесь. Но если в Linux алгоритм по умолчанию это NativePRNG, то "много" энтропии и не надо - только чтобы проинициализировать seed при старте java процесса.
Если сильно беспокоитесь насчет генерации уникальный UUID в виртуальной машине, можно принудительно сконфигурировать NativePRNG - этого должно быть достаточно. Если же паранойя спать не даёт, то настроить NativePRNGBlocking и поколдовать над источниками энтропии.
запустить процессы в одно и то же время вплоть до наносекунд
Так при одновременном запуске сразу нескольких контейнеров из одного образа именно это и происходит. Достаточно, чтобы на хосте k8s свободных ядер в этот момент было не меньше, чем контейнеров.
Отсюда же и проблемы с энтропией в контейнерах.
Вам пора церковь свидетелей uuid коллизии открывать! :)
А Вы не задумывались, для чего у UUID есть целых пять версий, причем четыре из них поддерживаются обсуждаемым PostgreSQL?
Я не силён в теологических спорах. Я привык оперировать математическими доказательствами и бенчмарками. Образование, знаете ли, сказывается.
Так сколько вы говорите версий uuid'ов может танцевать на булавочной головке?
И если бы вы знали, сколько всего странного и интересного происходит при старте java процесса. И сколько есть нюансов в вопросах измерения времени (особенно с System.nanoTime()). То вам бы стыдно стало от той чуши, что вы написали. Благо знаете вы мало, поэтому не стыдитесь.
UUID в PostgresSQL (а в этом треде речь идет именно о нём)
PostgreSQL лишь БД в которой сохраняются сообщения с UUID из разных источников. Сам он источником UUID выступает не часто. Все же sequence явно производительней и удобней. Доказательство этого утверждения я приводил уже выше.
Сам он источником UUID выступает не часто.
У вас, может и не часто. А у меня практически всегда.
Вот так примерно:
create extension if not exists "uuid-ossp" schema "public";
create table my_relation
(
id uuid not null default uuid_generate_v4(),
primary key (id)
);Не расстраивайтесь. У Вас еще будет возможность набраться опыта работы с распределенными гетерогенными системами и мультисервисными архитектурами.
В подавляющем большинстве случаев, распределенные транзакции в таких системах не допустимы. Поэтому присваивает идентификатор сообщению его источник еще до помещения сообщения в топик, а вовсе не БД после синка. БД все же хранилище информации, а не ее источник. БД может трансформировать данные, но уж никак не порождать новые.
Если для вас БД - чисто хранилище данных а uuid прилетают с клиентов - это чисто ваша проблема. Да, внешние клиенты id и захардкодить могут, кто ж им указ
А как БД может порождать, а не трансформировать данные?
Как у Вас работает маршрутизация и горизонтальное масштабирование, если идентификатор присваивается БД, а не источником сообщения?
при сильной OLTP нагрузке на запись - этот gen_random_uuid() будет узким местом.
Я использую где возможно для генерации суррогатных id hash функции от бизнес ключа.
Это еще и ооочень удобно тем что ты можешь зная бизнес ключ получить суррогатник не делая доп поиск по таблице.
этот gen_random_uuid() будет узким местом
ИМХО - запись на диск по любому дороже генерации UUID. Т.е. если вы дошли до того, что генерация uuid стала узким местом, то значит в вашем хранилище имеются более фундаментальные проблемы, чем генератор uuid. И, отказавшись от генерации uuid, вы с вероятностью 99% не уберете узкое место. Так как фундаментальные проблемы требуют фундаментальных решений - партиционирование, сегментирование, пересмотр структуры хранилища, переход на другую СУБД - в эту сторону вам придется посмотреть.
Зависит от диска и от способа генерации (псевдо)случайностей.
Я, наверное, уже лет 5 использую случайные UUID'ы в качестве первичных ключей. Пока на проблемы с производительностью не нарывался :)
ИМХО - вы ищите проблемы там, где их нет. Если для первичного ключа сравнивать производительность uuid с генерацией и bigserial, то bigserial гарантированно окажется дороже из за конкуренции за sequence. На проблемы с производительностью sequence'ов я пока тоже не нарывался, хотя sequence'ами пользуюсь более 20 лет ;)
Главный бонус uuid в качестве первичного ключа - возможность практически бесплатного сегментирования хранилища. Случайные uuid'ы, сгенерированные в разных базах остаются уникальными. bigserial вам, к сожалению, такого бонуса не дает.
PS
Пора перестать бояться, и начать генерировать случайные UUID'ы :)
Наверное единственный минус uuid - это размер.
gen_random_uuid - это open("/dev/urandom", O_RDONLY, 0) и чтение из него. Есть подозрение, что три системных вызова open()/read()/close() все же более ресурсоёмки, чем манипуляции с sequence в userspace.
Kогда же pg_strong_random() работает через OpenSSL RAND_bytes(), там то уж точно борьба за общий ресурс с evp_rand_lock()/evp_rand_unlock()
запись на диск дороже, но запись случается гораздо реже. Ну и все же главная причина - вторая.
hash вы можете сгенерировать, если у вас уже есть бизнес ключ. А если бизнес ключ генерируется при insert'е (что бывает в 99% случаев) - то у вас есть только 2 разумные альтернативы - sequence или случайный uuid. Как я уже писал выше, в высоко-конкурентной среде sequence гарантированно окажется дороже, так как за него будут конкурировать разные потоки.
PS
Ребят, еще раз - не ищите проблем там, где их нет. Поверьте моему опыту - реальные проблемы сами вас найдут. Вот с ними и боритесь ;)
зависит от сущности, это может быть, например, nft токен, который имеет адрес коллекции(20 байт), сеть(8 байт) и ид токена (256 байт). В таких случаях я предпочитаю создавать кастомный составной тип для ид и использовать его в качестве первичного ключа, но это может бить по производительности, если нам нужен суррогатный ключ - хэш хорошее решение.
Другое дело, если в сущности не ща что зацепиться, все не уникально или может меняться, тогда да, только суррогатный ключ
случайный uuid. Как я уже писал выше, в высоко-конкурентной среде sequence гарантированно окажется дороже
Даже mutex() окажется дешевле, чем генерация случайного или псевдослучайного числа. Тем более futex(). А с учетом времени, необходимого для обновления sequence, futex() даже в высоконагруженной системе только изредка будет приводить к переключению контекста из userspace.
Просто посмотрите исходники PostgreSQL, чтобы в этом убедиться.
Можно выполнить предгенерацию последовательных ключей, если время их генерации вносит существенный вклад
согласен+избавляет от возможности дубля через разные системы (если по какой-то причине запрос создания идет одновременно на 2х серверах)
значения, которые соседствуют в индексе, будут вставлены в совершенно разное время и находиться в совершенно разных местах в индексируемой таблице.
Так прямо и хочется спросить — ну и что? Вот возьмем для примера оракл. Там есть так называемые реверсивные индексы, в задачу которых входит разбросать похожие ключи по разным блокам на диске. Потому что последовательная их запись в таблицу приводит к блокировкам одних и тех же блоков и тормозам. Я упрощаю, но суть в том, что узкое место — вставка.
Если же ключи разбросать — вставка производится быстрее. Иными словами — описанная автором ситуация вовсе не обязательно является проблемой, как тут описано, а наоборот, может быть решением. Все зависит от того, какого сорта у нас нагрузка, и что мы оптимизируем.
Статья именно про это: оптимизировать нужно под конкретные условия, при этом хорошо понимая как работает выбранная СУБД. Для меня сюрпризом оказалось, что при index-only scans Postgres все равно обращается к индексированной таблице.
Для меня сюрпризом оказалось
Это еще что. Вы можете себе представить, чтобы оракл полез за select константа… в партиционированный индекс, причем надолго? А он смог… причем где-то на несколько сотен экземпляров СУБД нашлась ровно одна такая, у которой оказался такой извращенный план запроса. Остальные выбирали константу за константное время.
Статья именно про это:
Ну, будем считать, что я слегка придрался к конкретной фразе. В принципе-то по всему тексту вопросов нет, интересный случай в копилку
Неочевидные проблемы с UUID ключами в PostgreSQL