Comments 53
UUIDv7 в PostgreSQL 18
Описание несколько неточное, и даже вследствие этой неточности имхо противоречащее ранее написанному:
Он использует временную метку в формате Unix Epoch в качестве старших 48 бит, а оставшиеся 74 бита отводятся под случайные значения (ещё несколько битов занимают версия
UUIDи вариация/variant).
В реализации постгресса случайная часть сокращена до 62 бит, а 12 бит хоть и описываются как "sub-millisecond", на самом деле если и не являются, то вполне могут считаться самым что ни на есть вульгарным автоинкрементом (правда, не смотрел, действительно ли там плюсуют по единичку, или используется рандомное приращение в малом диапазоне, но сути это не меняет). Что уж никак не есть рандом. К слову, это описывается стандартом.
К тому же 4-битное поле версии располагается между штампом времени и этим 12-битным дополнением, но в рамках одного инстанса и одного пакета изменение версии нереально, так что его можно считать константой. И, рассматривая сортируемость, игнорировать.
12 бит хоть и описываются как "sub-millisecond", на самом деле если и не являются, то вполне могут считаться самым что ни на есть вульгарным автоинкрементом
Не надо домыслов. Субмиллисекунды совершенно честные. Для этого разработчик (Андрей Бородин) залез в самые глубинные потроха операционной системы и извлек то, о чем 99.9999% программистов не знают. Кстати, для маков не удалось достать 12 битов времени - там только 10, а 2 младших бита - рандомные. Честные субмиллисекунды, в отличие от счетчика, дают почти безупречную (но не гарантированную) монотонность идентификаторов, даже если идентификаторы генерятся на разных бэкендах.
Кстати, в переведенной статье ошибочно утверждается (вообще статья крайне неудачная), что "12-битная субмиллисекундная составляющая ... гарантирует монотонность всех UUIDv7, сгенерированных в рамках одного backend-процесса Postgres (одной сессии)". На самом деле все UUIDv7, сгенерерованные в рамках одного бэкенда будут гарантированно монотонными независимо от наличия или отсутствия субмиллисекундной составляющей. Монотонность гарантируется таймстемпом, а если при лавинообразной генерации точность таймстемпа недостаточна, то весь таймстемп начинает работать как счетчик - это особенность алгоритма в PostgreSQL 18.
Монотонность гарантируется таймстемпом, а если при лавинообразной генерации точность таймстемпа недостаточна, то весь таймстемп начинает работать как счетчик - это особенность алгоритма в PostgreSQL 18.
Минутку... не хотите ли вы сказать, что алгоритм получения timestamp гарантирует ко всему прочему ещё и уникальность? Причём вы же говорите именно о встроенном типе данных ("точность таймстемпа недостаточна" - это же о нём, а не о нём плюс 12 дополнительных битов), который вроде как имеет точность в микросекунду...
Да, на одном бэкенде алгоритм получения timestamp (включая его дополнительную 12-битную субмиллисекундную часть), который в критических режимах работает как счетчик, гарантирует уникальность (строго нулевая вероятность коллизий). В случае нескольких бэкендов вероятность коллизий не нулевая, но пренебрежимо мала.
Давайте пока оставим субмиллисекундную часть, которая существует только где-то в недрах сервера и пользователю недоступна (ведь недоступна же, правда?). точность формата штампа времени - микросекунда. И по вашим словам я понимаю так, что из-за особенностей реализации при массированной вставке записей в таблицу с полем автогенерации текущего штампа времени с микросекундной точностью (не UUID) вставляемые значения будут уникальны вне зависимости от каких-либо обстоятельств...
12-битная субмиллисекундная часть, конечно же, доступна пользователю, как и любой другой сегмент UUIDv7. Она обеспечивает точность приблизительно 250 наносекунд. Но если UUIDv7 не был сгенерирован в PostgreSQL, а пришел с клиента, то вместо субмиллисекундной части будет случайное значение. Поэтому функция uuid_extract_timestamp ( uuid ) работает только с первыми 48 битами таймстемпа, которые дают точность 1 миллисекунда (а не микросекунда, как Вы написали). Если нужно извлечь таймстемп с точностью 250 наносекунд, то придется делать собственную функцию. При этом не получится воспользоваться стандартным типом timestamptz, поскольку его точность всего 1 микросекунда.
Для справки: миллисекунда > микросекунда > наносекунда
И да, на одном бэкенде уникальность гарантирована.
Но если UUIDv7 не был сгенерирован в PostgreSQL, а пришел с клиента, то вместо субмиллисекундной части будет случайное значение.
А ведь в UUIDv7 определено поле variant. Почему бы его было не использовать чтобы однозначно отделить такие случаи?
Стандартом RFC 9562 определено другое назначение поля variant. Кроме того, стандарт вообще запрещает парсинг UUID без крайней необходимости, в том числе извлечение таймстемпа. И для этого есть очень веские причины, указанные в стандарте. Я бы вообще запретил использовать небезопасную функцию uuid_extract_timestamp ( uuid ) в промышленном программном коде. Для аналитики, поиска багов и т.п. - другое дело.
Стандартом RFC 9562 определено другое назначение поля variant.
Да, оно всегда "The 2-bit variant field as defined by Section 4.1, set to 0b10"
Но если UUIDv7 не был сгенерирован в PostgreSQL, а пришел с клиента, то вместо субмиллисекундной части будет случайное значение.
Вообще-то нет - клиент точно по такому же стандарту "Method 3" может сгенерировать правильный UUID (чем я сейчас и занимаюсь для Dlang)
Субмиллисекундный сегмент в UUIDv7, сгенерированном на клиенте, не имеет смысла. Время попадания идентификаторов с клиента на сервер больше миллисекунды. Для одного клиента это может быть миллисекунда, для другого две миллисекунды и т.п. Поэтому UUIDv7 с разных клиентов при интенсивной генерации будут приходить на сервер не в том порядке, в каком они были сгенерированы. Субмиллисекундная часть имеет смысл в случае генерации на одном сервере - разными микросервисами (как в СУБД, так и в серверных языках программирования).
а не микросекунда, как Вы написали
То есть ранее везде, где вы писали просто "таймстемп", вы на самом деле имели в виду не встроенный тип Постгресса, а именно компоненту штампа времени в составе UUIDv7?
Тут довольно прикольная вероятностная идея, что время разделяет данные на +\- одинаковые бакеты в четверть микросекунды. А случайные числа - их там около 60 бит - должны разделить на уникальные все UUID в мире, которые сгенерированы в эту четверть микросекунды.
Ну про залез в глубины и 99.9999% Вы как бы загнули, функцию gettimeofday и clock_gettime никто никуда не прятал, нужно просто открыть документацию на linux ядро и все
Было бы здорово ещё как-то вероятность коллизий оценить.
Тут можно поиграться. Для 3К айдишника в один момент времени, вероятность коллизии не превышает 1e-12
Вероятность коллизий UUIDv7, сгенерерованных в рамках одного бэкенда, строго равна нулю. Даже если бы в UUIDv7 не было случайной составляющей, а был только таймстемп, работающий в критических режимах как счетчик, коллизии были бы невозможны, как невозможны коллизии при автоинкременте в рамках одного бэкенда.
Вероятность коллизий UUIDv7, сгенерерованных несколькими бэкендами (при одновременной генерации на клиентах, при генерации несколькими микросервисами, при слиянии данных из разных таблиц) тоже можно сделать строго равной нулю, если сдвинуть таймстемпы на разных бэкендах на разные и достаточно большие интервалы. Для этого в функции uuidv7() есть параметр типа "интервал". Но никакой реальной необходимости в этом нет, так как UUIDv7, сгенерерованные несколькими бэкендами, не столкнутся даже без манипуляций с таймстемпами.
В остальных случаях вероятность коллизий ненулевая, но пренебрежимо мала. Достоверно оценить ее невозможно. Расчеты игнорируют то существенное обстоятельство, что в таблице с небольшим количеством строк возможность коллизий гораздо меньше, чем в таблице с огромным количеством строк. Формулы обычно исходят из того, что имеется потенциально бесконечно большая таблица, куда непрерывно добавляются строки вплоть до возникновения коллизии идентификаторов, и никакие строки не удаляются. Реальность, конечно, не имеет ничего общего с этой моделью.
Ни одного известного случая истинной коллизии UUID до сих пор не было. Хотя были случаи, когда из-за ошибок в алгоритме сталкивались копии одного и того же UUID.
Тогда формулы такие. Заполненность таблицы тут не имеет значения, ибо коллизия возможна только с тем же моментом времени.
А какова вероятность того, что в таблице окажутся UUIDv7 с одинаковым таймстемпом? Вы это явно упустили в своей формуле. Если вероятность такого события практически нулевая, то уже безразлично, какой длины случайная часть идентификатора - вероятность коллизии будет практически нулевой. Беда всех таких формул, что модель, на которой они основаны, не описывается. При попытке описать модель авторы формул столкнулись бы с тем, что их модель не соответствует реальности
Мысль на грани идиотии для исключения коллизии в случае многих бэкэндов: небольшую часть из 62 случайных бит разрешить отдавать под фиксированный id бэкэнда (уникальный для каждого из них). Тогда даже если каким-то чудом совпадут временная и случайная часть битов, гарантированно уникальная фиксированная часть обеспечит отсутствие коллизии. Да, теряем на размере случайной части, но, если не увлекаться и условные 6-8 бит позволить откусывать, то выглядит всё ещё не так страшно. Впрочем это, очевидно, будет уже не совсем UUIDv7)
Так было в UUIDv1 (см. сегмент node). Однако, если это требует централизованной координации, то это неудобно и не всегда возможно. Если же используется MAC-адрес, то это нарушает конфиденциальность. И, вдобавок, были реальные случаи совпадения MAC-адресов.
Так было в UUIDv1
Угу. Только там оно было, ЕМНИП, 48-битным куском ВМЕСТО рандомных бит, что уже действительно сильно на случайность и стойкость к подбору влияет. А вот оставить ощутимое количество рандомных бит и небольшое поле для предотвращения коллизий - такого там нет.
Ну и централизованная координация не так страшна, как кажется. По-крайней мере её можно автоматизировать и делать на уровне хотя бы того же конфига СУБД однократно при запуске инстанса. А дальше у нас во время работы бесплатно гарантия отсутствия коллизий в распределенной системе без всяких проверок.
И, вдобавок, были реальные случаи совпадения MAC-адресов.
Вот поэтому я за ручное распределение всегда. Если вы делаете подобные штуки для гарантий уникальности, то лучше потратить немного времени и вручную задать значение, чем полагаться на то, что оно автоматом окажется не совпадающим с другими.
В идеале еще туда бы идентификатор таблицы добавить, тогда по подвисшему в воздухе id можно будет сказать из какой он таблицы
Увы, единственный жизнеспособный вариант будет - использовать oid таблицы. А это уже 4 байта aka 32 бита. В противном случае получится решение, которое не подойдёт тем, у кого таблиц много/не будет иметь удобного-нативного способа напрямую соотнести таблицу с таким полем из UUID. Ну или мы возьмём много бит чтобы хватило всем и сильно на случайной части потеряем, облегчив подбор ключей перебором.
Да и смысл? Если вы записываете/выбираете значение, то вы и так уже знаете с какой таблицей вы работаете.
Этого не сделали исходя из принципа единственной ответственности. UUIDv7 минималистичен. Только ключ, и ничего более.
Есть и более практические соображения. Могут быть две таблицы, например, условно копии в разных схемах, в которых одни и те же UUIDv7 будут первичным ключом. Как понять, к какой из двух таблиц относится "подвисший в воздухе id"?
Тем не менее, есть два способа решения проблемы "подвисшего в воздухе id". Первый - отдельная таблица соответствия UUIDv7 имеющимся таблицам.
Второй способ - использование длинного идентификатора (например 160 бит), в старших разрядах которого будет UUIDv7, а в младших - ключ на таблицу метаданных (имя таблицы "подвисшего в воздухе id" и др.) и опционально контрольная сумма. Длинные идентификаторы, содержащие UUID, прямо предусмотрены стандартом RFC 9562. Но во втором способе придется хранить такие идентификаторы как строки, а не как бинарный тип UUID, что замедлит работу БД. К сожалению, в PostgreSQL нет типа данных "длинный UUID", а далекие от системного анализа разработчики считают, что и 128 бит - слишком много.
Вероятность коллизий UUIDv7, сгенерерованных несколькими бэкендами (при одновременной генерации на клиентах, при генерации несколькими микросервисами, при слиянии данных из разных таблиц) тоже можно сделать строго равной нулю, если сдвинуть таймстемпы на разных бэкендах на разные и достаточно большие интервалы.
Это как это КОНСТАНТА может обнулить вероятность коллизии? Коллизия без сдвига возникает при абсолютно одновременной генерации (чисто по компоненте штампа времени, конечно, без учёта рандомной составляющей), а при сдвиге - когда разность времени генерации абсолютно равна этому сдвигу.
Вероятность коллизий UUIDv7, сгенерерованных в рамках одного бэкенда
А тут по бэкендом имеется в виду один бэкенд-процесс или один сервер с Postgresql?
Но никакой реальной необходимости в этом нет, так как UUIDv7, сгенерерованные несколькими бэкендами, не столкнутся даже без манипуляций с таймстемпами.
Вы сначала пишете, что можно сделать вероятность коллизии UUIDv7 строго равной нулю, если сдвинуть временной интервал, а потом пишете, что UUIDv7, сгенерированные несколькими бэкендами и так гарантировано не столкнутся. Но тогда зачем трюк со сдвигом времени?
Стоит иметь ввиду, что при монотонных айдишниках ребалансировки b-tree происходят существенно чаще, чем при рандомных. А это не дешёвая операция.
Всё же при выборе типа идентификатора или ключа имеет смысл опираться не на противоречивые теоретические аргументы за и против, не имеющие численного выражения, а на бенчмарки. А бенчмарки говорят, что UUIDv7 и автоинкремент обеспечивают примерно одинаковый темп вставки и поиска записей, а UUIDv4 существенно им уступает.
См. статью UUID Benchmark War
Правда и бенчмарки тоже дают не полную картину. UUIDv7 по сравнению с автоинкрементом позволяют избавиться от лишних расчетов и таблиц при слиянии данных. Ведь при использовании автоинкремента необходима замена ключей. Но разницу так просто не посчитать
Бенчмарки отражают особенности текущей реализации, а не теоретический предел. В частности, для рандомных ключей нет смысла использовать самобалансирующиеся деревья. Тут что-нибудь типа radix-tree было бы эффективнее.
Однако, в популярных СУБД нет никаких radix-tree, а вот самобалансирующиеся B-деревья являются основным форматом индекса.
Тут что-нибудь типа radix-tree было бы эффективнее.
Я вот тут подумал, и понял что ничуть не эффективнее. Основную проблему случайных ключей - необходимость работы с кучей разных страниц - radix-tree вообще никак не решает.
Эффект от кеширования страниц "срабатывает" при каждой записи, а балансировка случается только при заполнении узла.
Стоит так же учитывать, что при MVCC кеширование страниц при записи может вообще не "срабатывать".
С чего бы? MVCC же про строки, а не про внутренную структуру индекса.
MVCC про изоляцию транзакций, из-за которой нельзя просто так брать и менять какую попало страницу.
Использовать MVCC для страниц индекса с целью изоляции транзакций - идея глупая. Вот была начальная версия страницы, назовём её версией 0. Первая транзакция создала версию 1, вторая транзакция независимо создала версию 2 (они попали на одну страницу, но работают с разными строками, а потому это допустимая ситуация). Ну и как теперь эти две версии объединять, когда транзакции будут зафиксированы?
Вот потому MVCC в Постгре и работает на уровне строк, а не страниц.
Получается можно еще и на столбце временнОй метки сэкономить?
Можно, но стандарт RFC 9562 не рекомендует, исходя из принципа единственной ответственности. Например, при использовании периодически изменяющегося параметра сдвига таймстемпа будут генериться прекрасные уникальные идентификаторы, используемые в качестве первичных ключей, но их уже нельзя будет использовать для извлечения реального таймстемпа
А зачем врайтить "рандомно" и "рандомных", если вполне посибл заврайтить "случайных" и "случайно"? И каждом бади сразу андерстендерно становится.
UUIDv7 в PostgreSQL 18