Комментарии 104
48 бит на время
Им проблем unixtime мало?
так ничего страшного при переполнении не произойдёт же.
Если не ошибаюсь, (2^48−1)÷(1000×60×60×24×365) это примерно 8925 лет с 1970. Потомки в 10895 году будут нас немножко ненавидеть (если не придумают раньше какой-нибудь новый стандарт или не перезагрузят цивилизацию).
а с чего они будут ненавидеть-то?
основные цели нового стандарта UUID: уникальность и локальность (чтобы эффективно работали b-tree индексы или партицирование).
первое обеспечивается случайной частью, второе — таймстампом в начале.
переполнение не мешает ни тому, ни другому.
да, использовать UUID для сравнения дат (больше-меньше) не получится, но я считаю такое использование плохой идеей: стандартов формирования UUID больше одного, лучше не полагаться на «кишки» любого UUID.
я наоборот предлагал урезать временной период до переполнения чтобы снизить вероятность коллизий за счёт увеличения количества изменяемых бит — или случайных (расширить ширину случайного поля), или псевдослучайных (увеличить точность таймстампа).
в [почти] принятом же стандарте старшие 4 бита будут равны нулю больше 400 лет
Как раз на днях тестировал UUIDv7 в контексте использования в Snowflake. Всё работает, как и ожидалось - partition pruning улучшается радикально. Особенно по сравнению с UUIDv4, который, по сути, всегда вызывает full scan.
Пример того, как его можно сгенерировать на Python:
import random
import time
import uuid
def uuid7(unix_ts_ms: int = None):
"""
UUIDv7 description: https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-03#section-5.2
UUIDv7 example: https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-03#appendix-B.2
"""
if unix_ts_ms is None:
unix_ts_ms = time.time_ns() // 1000000
ver = 7
variant = 2
rand_a = random.getrandbits(12)
rand_b = random.getrandbits(62)
# Offsets:
#
# unix_ts_ms = 128 - 48 = 80
# ver = 80 - 4 = 76
# rand_a = 76 - 12 = 64
# variant = 64 - 2 = 62
# rand_b = 62 - 62 = 0
return uuid.UUID(int=(unix_ts_ms << 80) + (ver << 76) + (rand_a << 64) + (variant << 62) + rand_b)
Ваш код не учитывает отбрасывание дополнительных секунд с времени.
В UNIX-времени изначально не существует дополнительных секунд и отбрасывать здесь нечего, не?
Отнюдь. UTC часы добавляют эти секунды. Это делается при чем в ручном режиме, умные дядьки выбирают дату, потом придумывают и назначают другую. А есть часы UT1 которые без поправки лип секунд, начиная с 1980 (внезапно) года.
Именно такие стоят на спутниках GPS. Вот как получить эти часы -- я в душе не чаю :-(. Собственно интересно как авторы стандарта это видят? По табличке когда вводились лип секунды сверять? :-)
Конкретно в Python на Windows и Unix это, похоже, не проблема. Документация говорит следующее:
Return the time in seconds since the epoch as a floating point number. The specific date of the epoch and the handling of leap seconds is platform dependent. On Windows and most Unix systems, the epoch is January 1, 1970, 00:00:00 (UTC) and leap seconds are not counted towards the time in seconds since the epoch. This is commonly referred to as Unix time. To find out what the epoch is on a given platform, look at
gmtime(0).
Про другие платформы стоит подумать в будущем. Действительно, любопытная история.
На википедии написано:
> Unix time number increases continuously into the next day during the leap second and then at the end of the leap second jumps back by 1 (returning to the start of the next day). For example, this is what happened on strictly conforming POSIX.1 systems at the end of 1998:
Не понимаю почему они так в стандарте написали про лип-секунды. Словно надо что-то делать, но что делать не написали. Почему нельзя было написать просто "Unix-time" ?
Если же хочется заиспользовать правильные часы, есть таймзоны `right/*`: www.ucolick.org/~sla/leapsecs/right+gps.html
$ TZ=UTC date; TZ=right/UTC date
Mon Apr 4 16:46:45 UTC 2022
Mon Apr 4 16:46:18 UTC 2022
А в традиционной unix-tz такое невозможно:
$ TZ=right/UTC date -d @1483228826
Sat Dec 31 23:59:60 UTC 2016
Честно говоря, я окончательно запутался. Вот тут https://stackoverflow.com/questions/16539436/unix-time-and-leap-seconds говорят, что POSIX Time не включает лип-секунды, и по этому это не совсем UTC. Я совсем запутался, но если кто знающий пояснит -- буду рад.
Еще одна статья по теме, но я ее пока не читал:
http://www.madore.org/~david/computers/unix-leap-seconds.html
Я, возможно, ошибаюсь, но ваш код не учитывает, что все UUID'ы, сгенерированные в пределах одной миллисекунды, должны иметь одинаковые случайные 9 бит.
Откуда такое требование? Проект стандарта говорит прямо противоположное: Random data for each new UUIDv7 generated
В частности, это необходимо для обеспечения "неугадываемости" "соседних" UUID, если известен какой-либо UUID.
Я из вашей статьи взял. Есть 2 (11 и 12 бит) сегмента с таким описанием:
Сегмент счетчика, инициализируемый псевдослучайным значением каждую миллисекунду
И ещё сегмент (50 бит):
Псевдослучайное значение, сгенерированное отдельно для каждого UUID
Т.е. для первых двух сегментов инициализируем каждую миллисекунду, для третьего генерим для каждого UUID.
Да, там ещё для первых двух происходит инкремент, насколько я понял, но этого в коде выше тоже нет.
Ну да, один-два бита (опционально) защищают от переполнения счетчика. Но зачем для этого аж 9 битов? Два защитных бита гарантируют, что даже в самом худшем случае 75% счетчика, инициализируемого случайным числом, свободны. Кстати, альтернативой защитным битам является инкремент таймстемпа, и судя по переписке с разработчиком это очень просто реализовать
Ваша таблица говорит о том, что указанные два сегмента должны быть одинаковыми для всех UUID, сгенерированных в пределах одной миллисекунды.
Вернее, это значение инкрементируется при каждой генерации в рамках миллисекунды, но оно явно не должно быть каждый раз рандомным, как у господина@wildraidв его коде выше.
То есть, метод генерации должен иметь state в виде последнего инкрементированного значения, если я правильно понимаю.
А про 9 бит я ошибся спросонья. Я имел в виду указанные 11 + 12 бит. Но, возможно, я крепко запутался, заранее извините.
А как они выглядят? как uuid4, но с семёрочкой?
те же 128 бит, текстовое представление то же.
альтернативная (более компактная) запись рассматривается, но в стандарт не вошла (в статье это есть).
ИМХО особого смысла в альтернативной записи нет, экономия не настолько велика чтобы оправдать сломанную совместимость. вот если правда UUID с длиной более 128 бит получат распространение, то можно подумать и об альтернативной записи.
надо же, достаточно близко к тому, что предлагал я
https://github.com/uuid6/uuid6-ietf-draft/issues/34
я доволен )
А какова вероятность генерации коллизии с разных машин в одну и туже миллисекунду?
я делал табличку с вероятностью коллизий:
https://docs.google.com/spreadsheets/d/1fUykRMW5v48FfpSKRPSvewyzUHywjxPlB6FjXvHa5Jg/edit#gid=0
можете сделать копию и поиграться. в случае генерации миллиона uuid в секунду, вероятность столкнуться с коллизией за год ≈0.17%.
многовато, конечно, я предлагал способы существенно снизить вероятность коллизий. впрочем, для большинства применений этого вполне достаточно.
на первом листе там немного другой подход: сколько uuid в секунду мы можем генерировать чтобы вероятность столкнуться с коллизиями за 50 лет была не больше одной миллиардной. получается ≈20к uuid в секунду.
Стоит иметь ввиду, что вероятность коллизий в случае рандома по началу крайне мала и только со временем, по мере насыщения, начинает расти. Если взять полные 128 бит рандома, то вероятность за четверть века получить хотя бы одну коллизию всего 0.1%:
При этом в первый год вероятность коллизии в 500 раз меньше:
Кроме того, если рандому плевать когда были сгенерированы идентификаторы, то всем схемам с таймштампами уже не плевать и поэтому любые неравномерности в частоте генерации идентификаторов повышают риск коллизии.
Вообще да, хотелось бы увидеть расчеты на которые опираются авторы спеки. Почему именно такие длины полей являются оптимальными?
а что значит «оптимальными»? исходили больше из удобства (таймстамп длиной в целое число байт) и совместимости (128 бит на весь uuid, из которых 6 зарезервированы под вариант/версию)
Исходили вовсе не из "удобства".
Во-первых, были внешние ограничения (общая длина, сегменты ver и var), необходимые для совместимости с RFC 4122. Иначе сложно пропихнуть стандарт через утверждающие инстанции. Также беспокоились за совместимость с имеющимся софтом, который оперирует 128-битовами UUID. По мне так оптимальная длина не 128, а 160 битов.
Во-вторых, длина таймстемпа 48 битов диктовалась необходимостью хранить миллисекунды (для синхронизации UUID из разных источников через интернет бОльшая точность смысла не имеет), а также привязкой к Unix-time (тоже для более гладкого прохождения через утверждающие инстанции) и желанием избежать быстрого переполнения таймстемпа.
В-третьих, длина счетчика определялась необходимостью сохранять десятки тысяч записей в миллисекунду при пиковых нагрузках. То есть, ориентировались на производительность СУБД.
В-четвертых, длина самого правого псевдослучайного сегмента (не менее 32 битов) определялась необходимостью затруднить угадывание близких UUID, сгенерированных в течение миллисекунды.
Для некоторых сегментов длина задана жестко (где необходимо), а для других - как довольно широкая "вилка" (где возможно).
Да, было выравнивание по границам байтов (для человекочитаемости сегментов в обычной кодировке), но большой роли это не играло. Плюс-минус несколько битов - это несущественно. Но в целом длины сегментов заданы весьма разумно (кроме 6 битов, потраченных впустую на ver и var).
Также беспокоились за совместимость с имеющимся софтом, который оперирует 128-битовами UUID.
я про совместимость и написал.
Во-вторых, длина таймстемпа 48 битов диктовалась необходимостью хранить миллисекунды (для синхронизации UUID из разных источников через интернет бОльшая точность смысла не имеет), а также привязкой к Unix-time (тоже для более гладкого прохождения через утверждающие инстанции) и желанием избежать быстрого переполнения таймстемпа.
нет.
- уже существующий с 2005 года uuid работает со стонаносекундной точностью, никаких проблем с этим не видно. вы правда думаете, что в 2022 году, рассматривая стандарт на тысячелетия вперёд, мы не можем себе позволить такую точность? так, сюрприз, если таймстамп с такой точностью и недоступен, то никто не мешает брать миллисекундную точность, и «разбавлять» рандомом;
- я уже замучился говорить, что для целей uuid (уникальность и локальность) ничего страшного в переполнении таймстампа нет;
- ладно, пусть мы решили использовать миллисекундную точность и обойтись без переполнения таймстампа на время актуальности стандарта, в этом случае 44 битов хватило бы до 2527 года, вы правда думаете, что через 500 лет сегодняшние rfc будут интересовать кого-то помимо историков?
Плюс-минус несколько битов — это несущественно
так в том-то и дело, что не так уж и мало. 6 бит у нас «украла» совместимость со старыми версиями uuid. 5 бит таймстампа будут нулевыми ещё больше двухсот лет. один бит теряется на защиту от переполнения счётчика. всё в сумме это уже выглядит «не очень» для обепечения глобальной уникальности (тот же ms называет uuid guid'ом). вместо того, чтобы озаботиться уникальностью здесь и сейчас, зачем-то обеспечили защиту от переполнения таймстампа на ближайшие почти десять тысяч лет.
я продолжаю считать свой вариант лучше окончательной версии:
- максимальное возможное число изменяемых бит (читай: минимизация вероятности коллизий) при сохранении совместимости с rfc 4122 (новый uuid гарантированно не пересекается с описанными в раннем стандарте);
- сохранение монотонности при сдвигах времени назад до 2.5 секунд (что автоматом решает и вопрос с високосной секундой);
- минимизация числа решений, отданных на откуп реализации, всего два момента, в которых допустимы вариации: (a) требуется строгая монотонность или нет, (b) доступен ли таймер с требуемой точностью.
итоговый стандарт же слишком «жидкий»: размер счётчика не определён (вроде бы нет даже рекомендуемого значения), а обозначены широкие пределы; зачем-то оставили рандомное приращение значения счётчика, хотя потребности в нём при наличии рандомной части я не вижу; невнятная обработка скачков времени/високосных секунд.
впрочем, я уже написал, итоговый стандарт не так уж плох, для большинства применений он отлично подойдёт.
просто мне хотелось пропихнуть стандарт не конфликтующий с rfc 4122, и при этом по всем существенным параметрам не хуже явного фаворита среди конкурентов — ulid: с меньшей вероятностью коллизий, с прописанной в стандарте непредсказуемостью генерируемых идентификаторов, с прописанной в стандарте обработкой скачков таймстампа при коррекции времени/високосных секундах.
вы правда думаете, что в 2022 году, рассматривая стандарт на тысячелетия вперёд, мы не можем себе позволить такую точность?
Мы можем позволить себе любую точность, хоть пикосекунды. Но проблема в том, что UUID, одновременно сгенерированные разными генераторами, придут по сети в базу данных с разбросом в миллисекунду и даже больше. Сколько будет идти сигнал вокруг Земли через тысячелетия? Столько же, сколько и сегодня, так как скорость света не изменяется со временем. UUID, сгенерированный раньше, может прийти позже. Когда UUID от разных генераторов будут приходить по сети вперемешку, вы заметите, что монотонность нарушается на миллисекунду. Это, кстати, аргумент в пользу генерации UUID в СУБД, и при этом можно обойтись хоть секундным таймстемпом при достаточном счетчике. Так какой же смысл делать более точный таймстемп? Лучше уж удлинить счетчик. Это позволит нагенерить больше UUID'ов в миллисекунду при пиковых нагрузках, чем такое же удлинение таймстемпа. Или можно удлинить псевдослучайную часть, чтобы снизить вероятность коллизий.
ничего страшного в переполнении таймстампа нет
Как-то я себе слабо представляю работу UUID после переполнения таймстемпа.
44 битов хватило бы до 2527 года
Согласен. Но "поезд уже ушел". И большинство авторов стандарта, а также тех, кто будет его утверждать, традиционно мыслят 8-битовыми байтами. Кто же их разубедит? А стандарт, тем не менее, нужен. Да, потеряли 4 бита, которые можно было бы использовать с большей пользой. Жизнь далека от идеала.
я продолжаю считать свой вариант лучше окончательной версии
Замечательно. Но, но Вашего варианта нет в IETF
Как-то я себе слабо представляю работу UUID после переполнения таймстемпа.
а в чём проблема? просто берём младшие N бит.
у нас же не стоит задача определить точное время по UUID, у нас стоит задача чтобы UUID, сгенерированные (в том числе и независимо) в близкие моменты времени, имели «соседние» значения.
даже переполняющийся раз в месяц таймстамп обеспечит гораздо лучшую локальность, чем сегодняшние стандарты UUID, в которых если и используется таймстамп, то хранится он так, что простая лексикографическая сортировка приводит по сути к случайному перемешиванию. я повторюсь, ms в своём sql server приступил к решению этой проблемы, но подстройка dbms под [частный] вариант uuid мне кажется «костылём».
Но проблема в том, что UUID, одновременно сгенерированные разными генераторами, придут по сети в базу данных с разбросом в миллисекунду. Сколько будет идти сигнал вокруг Земли через тысячелетия?
ну послушайте, за тысячелетия, надеюсь, человечество хотя бы солнечную систему освоит, давайте будем ещё ориентироваться на то сколько времени будет идти сигнал со спутника юпитера.
Лучше уж удлинить счетчик. Это позволит нагенерить больше UUID'ов в миллисекунду при пиковых нагрузках, чем такое же удлинение таймстемпа. Или можно удлинить псевдослучайную часть, чтобы снизить вероятность коллизий.
да, логика в ваших рассуждениях есть, в случае, когда генерация UUID не равномерно «размазана» по миллисекундному интервалу, а происходят микросекундные/субмикросекундные всплески, иметь таймстамп с высоким разрешением неоптимально.
но:
- это очень узкий класс применений (как минимум сейчас);
- проблема именно для таких применений решаема (практика загрубления таймстампа и подмешивания рандома уже широко распространена).
почему я выбрал 100нс? потому что удачно получилось целое число байт на таймстамп при минимальном числе неиспользуемых в ближайшем столетии бит слева. ну и то, что в прошлой версии uuid использовалось именно такое разрешение таймера, тоже, хоть и небольшой, но плюсик.
Жизнь далека от идеала.
Замечательно. Но, но его нет в IETF
да я разве спорю? первая реакция у меня была же «я доволен», стандарт в целом неплохой.
а в чём проблема? просто берём младшие N бит.у нас же не стоит задача определить точное время по UUID, у нас стоит задача чтобы UUID, сгенерированные (в том числе и независимо) в близкие моменты времени, имели «соседние» значения.
Да, современные СУБД это проглотят, как они проглатывают 4 версию UUID. Но более быстрый двоичный метод поиска требует сквозной, а не кусочной монотонности
Но более быстрый двоичный метод поиска требует сквозной, а не кусочной монотонности
не очень понял что вы имеете в виду, если честно.
вот смотрите, у нас огромная таблица с какими-то объектами, востребованность которых зависит от времени. ну пусть это будут посты в некоторой мега-социальной сети. каждый объект идентифицируется его uuid.
пришли пользователи и посмотрели миллион постов, 90% из которых были написаны в течении последних суток.
при использовании uuid v1, v4 и подобных обращение будет «размазано» по всему индексу, выделить горячую область невозможно (то есть для эффективного кэширования в памяти должен лежать индекс целиком).
а вот при использовании некоего сортируемого uuid горячая область выделится сама. и даже если раз в 200 лет происходит переполнение uuid, и в горячую область попали и сегодняшние посты, и посты двухсотлетней давности, и посты четырёхсотлетней давности, и посты шестисотлетней давности, то всё равно равно это горячая область будет на много порядков меньше всего индекса.
то же самое и партицированием, если у нас ключ партицирования несортируемый по времени, то эти 90% запросов за последние сутки размажутся по всем партициям, а если сортируемый — окажутся в одной. тут уже от задачи зависит выгодно это нам или нет.
не очень понял что вы имеете в виду, если честно.
что такое двоичный поиск я немножко знаю )
вопрос был какой сценарий использования вы имеете в виду.
класть данные в хранилище без обработки в порядке поступления и надеяться, что они будут отсортированными? не встречал такого, даже tsdb, которые ориентированы на получение отсортированных по времени данных, умеют работать с поступающими с нарушением порядка записями.
вопрос был какой сценарий использования вы имеете в виду
Сценарий - генерить местные UUID последовательно для каждой записи, которая кладется в таблицу базы данных. У записи может быть и второй UUID, сгенерированный там, откуда она родом, - для сверки. Двоичный поиск должен быть использован для поиска UUID в индексе.
честно говоря, я у меня после прочтения написанного вами так и не складывается целостная картинка.
сегодня чаще всего в СУБД используется b-tree индекс, и поиск по нему хоть и не может называться бинарным, но имеет ту же алгоритмическую сложность. что вы хотите улучшить и как именно?
ну послушайте, за тысячелетия, надеюсь, человечество хотя бы солнечную систему освоит, давайте будем ещё ориентироваться на то сколько времени будет идти сигнал со спутника юпитера.
Шутки шутками, но, например, пинг между Москвой и Токио около 280 миллисекунд. В одну сторону сигнал идет около 140 миллисекунд. Это очень немало для таймстемпа.
Можно, конечно, вычесть смещение на ожидаемое время прохождения сигнала из таймстемпа при передаче, чтобы на принимающей стороне таймстемп примерно соответствовал времени прихода сигнала.
Но лучше в каждой записи иметь два UUID: для передающей стороны и для принимающей стороны. Каждый из двух UUID со своим значением таймстемпа. Тогда поиск в базе данных на передающей стороне будет быстрее по первому таймстемпу, а поиск в базе данных на принимающей стороне будет быстрее по второму таймстемпу.
Кстати, стандарт предусматривает оба способа:6.1. Timestamp Granularity
...Implementations MAY alter the actual timestamp. Some examples included security considerations around providing a real clock value within a UUID, to correct inaccurate clocks or to handle leap seconds. This specification makes no requirement or guarantee about how close the clock value needs to be to actual time...
6.9. DBMS and Database Consideration
...In addition to UUIDs, additional identifiers MAY be used to ensure integrity and feedback.
Миллисекундная точность таймстемпа в стандарте примерно соответствует времени прохождения сигнала из соседнего помещения (оно зависит не только от расстояния), и поэтому делать более точный таймстемп нет никакого смысла.
Шутки шутками, да, но Вы так и не ответили на мой вопрос про бенчмарки - их проводили? Насколько быстрее начинает работать СУБД благодаря данным оптимизациям UUID? Потому что у меня есть предположение, что разница пренебрежимо мала и в реальных приложениях её никто никогда не заметит.
На самом деле разница колоссальная. См. бенчмарки здесь: https://github.com/Sofya2003/ULID-with-sequence в разделе Benchmarks of sequential UUID. Это, конечно, далеко не все бенчмарки, но вполне достаточно, чтобы понять общую картину. Бенчмарки версии 7 можно, видимо, поискать здесь: https://github.com/uuid6/prototypes
Ссылок там много, да. Но ни одна из них не сравнивает ULID vs UUIDv7, т.е. именно ту оптимизацию с перемещением случайной части в конец значения, которую Вы тут рекламируете.
Преимущество UUIDv7 перед ULID не только в бенчмарках. См. https://habr.com/ru/post/658855/comments/#comment_24230393 В будущем, при использовании двоичного поиска, UUIDv7 будут существенно опережать ULID. Пока же нынешние технологии поиска в СУБД, приспособленные скорее к UUIDv4, не дают UUIDv7 показать, на что они способны.
но Вы так и не ответили на мой вопрос про бенчмарки — их проводили?
даже на хабре было много статей, в которых исследовали этот вопрос, например:
https://habr.com/ru/post/265437/
https://habr.com/ru/company/ozontech/blog/564520/
а вот взгляд с совершенно иной точки зрения («серебряной пули не существует»):
https://habr.com/ru/post/654891/
Ближе всего средняя ссылка. Но:
Используемый там seq_uuid - это не UUIDv7.
Там нет бенчмарков показывающих разницу в скорости реализаций дополнений к постгресу
generate_ulid()иuuid_time_nextval().Статья не объясняет, за счёт чего между ними разница в полтора раза.
по последнему пункту, очевидно, это накладные расходы.
generate_ulid() — это pl/pgsql, а uuid_time_nextval() — plain C
по предпоследнему, если честно, я вас не понял. как же вы увидели разницу в полтора раза, если бенчмарков нет?
по первому пункту — это вообще не важно, проверялось «важна ли упорядочненность id». и да, первая статья на ту же саму тему.
В статье показан бенчмарк на скорость выполнения INSERT - и вот там разница в 1.5 раза. Скорость INSERT, в свою очередь, зависит не только от скорости обновления индекса, но и от скорости выполнения функций generate_ulid() и uuid_time_nextval() - и вот сравнения их скорости я в статье и не увидел. Грубо говоря, всегда есть вероятность, что тормозила именно generate_ulid(), а не вставка в индекс.
Грубо говоря, всегда есть вероятность, что тормозила именно generate_ulid(), а не вставка в индекс.ну да, 99.999%, что именно так оно и есть.
именно про это я и написал: «generate_ulid() — это pl/pgsql, а uuid_time_nextval() — plain C».
важно, что деградации скорости в зависимости от числа записей не было обнаружено, то есть сама идея упорядочненных UUID вполне имеет право на жизнь.
а значит лучше иметь стандарт, чем не иметь. в случае наличия rfc есть все шансы, что в postgresql, ms sql и ешё кучке баз появится нативная поддержка.
Это было важно в контексте той статьи. А в контексте текущей важно есть ли разница от микрооптимизации положения счётчика, отличающий ULID от UUIDv7, и подающейся как значительное преимущество UUIDv7.
Кстати, а в чём конкретно должна выражаться нативная поддержка? В новом типе индексом, специально заточенном под UUIDv7? Так вроде существующих индексов хватает и есть возможность вручную задать наиболее подходящий. В реализации функций вроде generate_ulid()? Так во-первых уже есть сторонние реализации, и во-вторых зачастую генерация происходит в приложении (а то и вообще в клиенте), так что я бы не сказал, что это прям критичная фича.
А в контексте текущей важно есть ли разница от микрооптимизации положения счётчика, отличающий ULID от UUIDv7, и подающейся как значительное преимущество UUIDv7.
эта ваши локальные с SergeyProkhorenko разборки, не более того )
основное преимущество — это будет стандарт, соответственно, поддержка будет повсеместной.
далее, уже в стандарте более чётко проговорено, как увеличивать значение UUID в рамках миллисекунды чтобы не получать повторяющиеся значения, я надеюсь, что будет проговорено и что делать в случае переполнения счётчика, «the generation will fail» из стандарта ulid меня категорически не устраивает.
далее, всё-таки встраивание в существующую инфраструктуру UUID имеет свои плюсы, уже встречались горячие головы, которые предлагалт использовать ULID как хранилище таймстампа. при хранении в бинарном формате ULID неотличим от UUID (с прицелом на это он и разрабатывался), с учётом того, что область значений ULID пересекается со всеми UUID, это, всё-таки, пусть и скорее гипотетичекий, но недостаток (приложение, ожидающее ULID, может встретить UUID и вытащить оттуда бессмысленный таймстамп).
ну и, наконец, я надеюсь, что к моменту принятия стандарта удастся отговорить от совсем уж странной идеи поддерживать таймстамп без переполнения на многие тысячи лет вперёд, это потенциально даст большую устойчивость к коллизиям, чем ULID.
во-вторых зачастую генерация происходит в приложении (а то и вообще в клиенте), так что я бы не сказал, что это прям критичная фича.
да, зачастую в клиенте, но далеко не всегда.
Это просто NIH-синдром — пропихивать собственное решение интереснее, чем чужое — это психологически понятно, но нельзя это всерьёз записывать в достоинства одному и недостатки другому.
не совсем так. ULID — достаточно удачный формат, но из-за пересечения области значений с UUID он вряд ли станет официальным стандартом.
если получится протолкнуть официальный стандарт не хуже UUID, то, ИМХО, мир станет чуточку лучше
а вот взгляд с совершенно иной точки зрения («серебряной пули не существует»):
Так там идет речь про вставку записей, а не про поиск. Скорость вставки записей - вовсе не проблема.
А что касается неприспособленности индексов баз данных к монотонным UUID, то поставщикам СУБД придется пересмотреть свои взгляды, потому что сбалансированное дерево с монотонными UUID как-то не очень хорошо формируется.
Скорость вставки записей — вовсе не проблема.
на да, настолько это было не проблемой, то кто-то сел и написал статью о том, как он с этой не проблемой боролся )
потому что сбалансированное дерево с монотонными UUID как-то не очень хорошо формируется.
с чего бы это? самобалансирующиеся b-tree известны уже с полстолетия как.
да и монотонные id используются повсеместно, все более-менее серьёзные СУБД умеют эффективно с ними работать.
проблема, если вы не читали внимательно, не в скорости как таковой, а в блокировках, накладываемых на ветвь дерева на время вставки. при высококонкурентном доступе в одну и ту же область дерева (вставка во много потоков как раз чего-то вроде обсуждаемого uuid v7) это может серьёзно осложнять жизнь.
Миллисекундная точность таймстемпа в стандарте примерно соответствует времени прохождения сигнала из соседнего помещения (оно зависит не только от расстояния)
на десятигигабитной и выше сети у меня получаются десятки микросекунд.
и вы не забывайте, что компьютеры стали многоядерными монстрами с numa и прочими прелестями, многопоточная неблокириющая генерация uuid в рамках одного хоста тоже полезна.
ну и да, младшие биты таймстампа высокого разрешения исторически используются в роли псевдослучайных чисел. разумеется, это не crng, но это вполне неплохой источник энтропии. увеличение разрешение таймстампа в ущерб случайной части не скажется сколько-либо заметно на устойчивости к коллизиям.
и да, в моём варианте высокая разрешающая способность таймстампа использовалась и для борьбы с переполнением счётчика тоже: если счётчик переполнился, то мы можем просто инкрементировать таймстамп, для большинства применений это вполне допустимо (и да, точность будет оставаться на порядки лучше, чем у изначально огрубленного до миллисекунд).
увеличение разрешение таймстампа в ущерб случайной части не скажется сколько-либо заметно на устойчивости к коллизиям.
Зато плохо скажется на скорости поиска: чем дальше последний разряд счетчика от левого края UUID, тем меньше возможность ускорить поиск
и да, в моём варианте высокая разрешающая способность таймстампа использовалась и для борьбы с переполнением счётчика тоже: если счётчик переполнился, то мы можем просто инкрементировать таймстамп
Идея инкремента таймстемпа замечательная. Но идея удлинения таймстемпа - нет. Инкремет миллисекундного таймстемпа дает гораздо более заметный выигрыш, чем инкремент 100-наносекундного, который при больших нагрузках придется делать столь часто, что 100-наносекундный таймстемп фактически превратится в миллисекундный.
Зато плохо скажется на скорости поиска: чем дальше последний разряд счетчика от левого края UUID, тем меньше возможность ускорить поиск
да хватит вам. чтобы сравнивать 128-битные значения процессору так и так придётся считать их из памяти, на это самые большие штрафы. а на каком там бите встретятся различия вообще практической роли не играет.
если не согласны — напишите опровергающий тест )
Инкремет миллисекундного таймстемпа дает гораздо более заметный выигрыш
почему?
чем инкремент 100-наносекундного, который при больших нагрузках придется делать столь часто, что 100-наносекундный таймстемп фактически превратится в миллисекундный.
если вам так мил миллисекундный таймстамп и не мил 100-наносекундный, что плохого в том, что второй превратится в первый? )))
да хватит вам. чтобы сравнивать 128-битные значения процессору так и так придётся считать их из памяти, на это самые большие штрафы. а на каком там бите встретятся различия вообще практической роли не играет.
если не согласны — напишите опровергающий тест )
Вот в памяти и будут потери. Тем более, что теперь базы данных перемещаются в память, а HDD повсеместно заменяются на SSD. Тесты можно писать на готовые технологии, а двоичный поиск в базе данных - пока только идея.
Инкремет миллисекундного таймстемпа дает гораздо более заметный выигрыш
почему?
Более длинный 100-нанносекундный таймстемп требует и делается за счет более короткого счетчика, чем миллисекундный. Поэтому инкремент 100-нанносекундного таймстемпа очиcтит более короткий счетчик, который быстрее переполняется.
если вам так мил миллисекундный таймстамп и не мил 100-наносекундный, что плохого в том, что второй превратится в первый? )))
То, что чрезвычайный режим переполнения счетчика и инкремента таймстемпа, становится обычным и отжирает значительные вычислительные ресурсы. Я понимаю, что при инкременте счетчика граница между таймстемпом и счетчиком становится размытой, но это не означает, что всё это удовольствие за бесплатно. А вот практической пользы от 100-наносекундного таймстемпа нет. Может быть, миллисекунда - это чрезмерное огрубление таймстемпа, и в одном датацентре данные из разных серверов с собственными генераторами UUID приходят с гораздо меньшей задержкой. Тогда можно подумать о какой-то промежуточной точности счетчика, например, 10 микросекунд.
Тесты можно писать на готовые технологии, а двоичный поиск в базе данных — пока только идея.
нет, почему. вы высказали идею, что сравнение 128-битных значений с различием левых битах будет быстрее.
я таки написал тест
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <sys/time.h>
unsigned gettimediff() {
static uint64_t last_time_us = 0;
struct timeval tv;
gettimeofday(&tv,NULL);
uint64_t current_time_us = 1000000 * tv.tv_sec + tv.tv_usec;
uint64_t time_diff_us = current_time_us-last_time_us;
last_time_us=current_time_us;
return time_diff_us;
}
int main() {
volatile char a[16][16]= {"1000" "0000" "0000" "0000",
"0100" "0000" "0000" "0000",
"0010" "0000" "0000" "0000",
"0001" "0000" "0000" "0000",
"0000" "1000" "0000" "0000",
"0000" "0100" "0000" "0000",
"0000" "0010" "0000" "0000",
"0000" "0001" "0000" "0000",
"0000" "0000" "1000" "0000",
"0000" "0000" "0100" "0000",
"0000" "0000" "0010" "0000",
"0000" "0000" "0001" "0000",
"0000" "0000" "0000" "1000",
"0000" "0000" "0000" "0100",
"0000" "0000" "0000" "0010",
"0000" "0000" "0000" "0001"};
volatile char b[16][16]= {"1000" "0000" "0000" "0000",
"0100" "0000" "0000" "0000",
"0010" "0000" "0000" "0000",
"0001" "0000" "0000" "0000",
"0000" "1000" "0000" "0000",
"0000" "0100" "0000" "0000",
"0000" "0010" "0000" "0000",
"0000" "0001" "0000" "0000",
"0000" "0000" "1000" "0000",
"0000" "0000" "0100" "0000",
"0000" "0000" "0010" "0000",
"0000" "0000" "0001" "0000",
"0000" "0000" "0000" "1000",
"0000" "0000" "0000" "0100",
"0000" "0000" "0000" "0010",
"0000" "0000" "0000" "0001"};
int r=0;
gettimediff();
for (uint64_t c=0; c<100000000LL; c++) {
r=memcmp((void *)a[0], (void *)b[0], 0);
}
printf("empty loop: %d\n\n", gettimediff());
for (int i=0; i<16; i++) {
printf("\t%4d", i+1);
}
for (int i=0; i<16; i++) {
printf("\n%d:", i+1);
for (int j=0; j<16; j++) {
for (uint64_t c=0; c<100000000LL; c++) {
r=memcmp((void *)a[i], (void *)b[j], 16);
}
printf("\t%d", gettimediff());
}
}
printf("\n\nsome useless number: %d\n", r);
}
в двух словах что делает программа: сравнивает 16-байтные (128-битные) объекты, в которых 15 нулей (ascii), и 1 единичка (тоже ascii) в первом, втором, и т.д. байте.
для каждого варианта сравнения измеряется время.
если бы ваша идея была верна, то, скажем, сравнение объекта с единицей в первом байте с объектом с единицей во втором, было бы быстрее, чем сравнение объекта с единицей в пятнадцатом байте с объектом с единицей в шестнадцатом байте (в первом случае различается уже первый байт, во втором только пятнадцатый)
xeon scalable первого поколения
epyc zen3
ryzen zen3
древний i5
как видим, ничего такого не наблюдается: кроме как на древнем i5 зависимости задержек от позиции единички вообще нет, а на i5 задержки хоть и меняются, но не укладываются в вашу теорию.
То, что чрезвычайный режим переполнения счетчика и инкремента таймстемпа, становится обычным и отжирает значительные вычислительные ресурсы. Я понимаю, что при инкременте счетчика граница между таймстемпом и счетчиком становится размытой, но это не означает, что всё это удовольствие за бесплатно.
вы шутите? само увеличение счётчика с таймстампом в моём предложении — это инкремент 64-битного числа, один такт на современных процессорах.
Тогда можно подумать о какой-то промежуточной точности счетчика, например, 10 микросекунд.
да, можно. но было пожелание, чтобы длина счётчика была целым числом октетов (а ещё лучше целым числом байт), в этой ситуации стонаносекундное разрешение с 56-битным счётчиком обеспечивают минимальную избыточность.
вариант с десятимикросекундным разрешением при длине счётчика в 49 бит, уверен, протолкнуть не получится.
я таки написал тест
Как программу напишете, так она и заработает. Вы же не используете преимущества, которые дает более короткий счетчик - и вот результат. Здесь можно использовать аналогию: в СУБД с поколоночным хранением поиск гораздо быстрее. Точно так же можно сначала искать по первому символу, затем по второму, затем по третьему и т.д., сужая область поиска.
но было пожелание, чтобы длина счётчика была целым числом октетов (а ещё лучше целым числом байт)
Это "пожелание" похоже на любовь к красивым автомобильным номерам, и столь же полезное. А потом, при внедрении Crockford's Base32 появится пожелание, чтобы длина счетчика в битах делилась нацело на 5? На этой глупости можно потерять десяток битов, которые отнюдь не лишние
Точно так же можно сначала искать по первому символу, затем по второму, затем по третьему и т.д., сужая область поиска.
ну примерно так и работает memcmp(). только так как функция эта весьма востребованная, в ней применена кучка оптимизаций. я привёл пример, ≈15 тактов процессора на сравнение двух 128-битных значений вне зависимости от того в каком байте различие.
даже если вручную удастся ещё немного оптимизировать, то особого эффекта это не даст, например, обращение к памяти в разы медленнее.
да и вообще, узкое место производительности нужно искать точно не в сравнении UUID )))
Тесты можно писать на готовые технологии, а двоичный поиск в базе данных — пока только идея.
«У нас есть ТАКИЕ приборы! Но мы вам о них не расскажем»
не обижайтесь, но без внятного описания идей и примеров кода эти разговоры — пустая маниловщина.
Просто в качестве примеров здесь приводится множество различных альтернатив, которыми вдохновлялись авторы.
Взять например ShardingID у Instagram. У него похожая структура (block id, whatever), но лишь 41 бит на миллисекунды, что дает им запас в 41 год. Всего значение занимает 64 бита, что аккуратно укладывается в тип bigint Postgres (и соответственно ровно в два раза короче чем UUID). При желании вместо Btree вы можете использовать компактные BRIN индексы. В общем, здесь технические причины сделать именно так сделали, мне предельно ясны. Парни явно не собираются хранить картинки вечность, учитывают особенности своей СУБД и прагматично относятся к требованиям по железу.
Uuidv7 отводит для unix time слот в 8925 лет. Пытаюсь представить какое тут может быть практическое применение (неужели считать миллисекунды со дня просветления Будды)? Иначе это лишние деньги на ветер железо.
Метаданные (как номер версии) удобны для обмена информацией в части протоколов. Но зачем их физически-то таскать в каждом значении? Не, я прекрасно понимаю почему их убрали из ULID, который делали с оглядкой на базы и обмен данными, освободив место для чего-то более осмысленного (снижающего вероятность коллизий, например). Вернуть обратно в UUIDv6(7,8), чтобы была возможность отличать один стандарт от другого, потому что кому-то хочется периодически выпускать новые RFC? Извините, платить за дополнительное железо ради такой прихоти нет ни какого желания.
В целом сложилось впечатление, что uuidv7 фокусируется больше на эстетической составляющей, отбросив многие технологические моменты своих прототипов. Получилось нечто совсем не свежее и с диким оверхедом. С другой стороны, это пока только draft и может быть все ещё переделают.
Кроме того, если рандому плевать когда были сгенерированы идентификаторы, то всем схемам с таймштампами уже не плевать и поэтому любые неравномерности в частоте генерации идентификаторов повышают риск коллизии.
это понятно, если локальность uuid не требуется, то uuid v7 (122 бита рандома) должен быть первым претендентом.
на первом листе там немного другой подход: сколько uuid в секунду мы можем генерировать чтобы вероятность столкнуться с коллизиями за 50 лет была не больше одной миллиардной. получается ≈20к uuid в секунду.
в расчёты вкралась ошибка, реальное количество почти на порядок меньше (≈3500)
А в чем прикол убирания дополнительных секунд (leap seconds) ?
Честно говоря, не понимаю, зачем нужен этот стандарт. Есть же ULID, и он более чем хорош. Недостатком ULID указано "26 character Base32 can contain 130 bits where this UUID is 128 resulting in a potential decode error on a base32 string" - но, простите, это же бред (а ещё в строке могли использовать символы вне Base32, а ещё их может быть не 26… и, кстати, в UUID ровно та же проблема) и типичный NIH-синдром с выискиванием фатальных недостатков.
Какие реальные проблемы решает новый стандарт, которые не решены в ULID?
- uild использует рандомные биты там, где в uuid из rfc 4122 находятся вариант/версия, в результате по идентификатору нельзя определить это uuid или ulid.
например, в ms sql применён хак для сортировки uuid, который не надо применять к ulid (тот уже сортируемый):
https://stackoverflow.com/questions/7810602/sql-server-guid-sort-algorithm-why - алгоритм генерации ulid в случае генерации более одного идентификатора в микросекунду даёт детерминированный результат, в некоторых случаях это может быть дополнительным вектором атаки;
- ulid — не rfc стандарт )
Это ведь отличие, а не проблема/недостаток, верно?
Он даёт монотонно возрастающий результат а не детерменированный - он добавляет случайное значение в заданном пользователем интервале: https://pkg.go.dev/github.com/oklog/ulid#Monotonic. По умолчанию данный интервал это 32 бита, так что на уязвимость это никак не тянет.
Смешно. И, кстати, поддержка ULID для разных БД уже есть.
Так что я возвращаюсь к своему изначальному вопросу: какие именно реальные проблемы есть в ULID, которые решает новый стандарт?
Вопрос правильный. Именно ULID'ы были основой для разработки стандарта в последние месяцы. Претензии к ULID следующие:
Это не стандарт (боятся использовать, и нет защиты соответствующих инвестиций)
На самом деле нет поддержки со стороны вендоров СУБД. Например, компания Postgres Professional давно знает, но не стала поддерживать ULID'ы
Раздел спецификации Monotonicity не является обязательным и не поддерживается со стороны разработчиков библиотек, за небольшим исключением
При использовании раздела спецификации Monotonicity:
легко угадать все близкие ULID в течение той же миллисекунды, что может быть небезопасным (реализация oklog частично решает эту проблему путем отступления от спецификации)
соседние ULID различаются лишь последними разрядами, что делает двоичный поиск UUID по старшим битам долгим
нет средств предотвращения переполнения счетчика при неудачной инициализации очень большим случайным значением
При наступлении дополнительной секунды риск переполнения счетчика возрастает ровно в 1000 раз
Не предусмотрено объединение ULID с метаданными (длинный идентификатор)
Наконец-то нормальный ответ, спасибо!
Давайте не будем. Полно RFC, которые на практике нарушаются, и полно "не стандартов", которые активно используются (в т.ч. ULID). Усилия, которые были потрачены на разработку и пропихивание UUIDv7 как RFC можно было заметно сэкономить, пропихивая в RFC ULID, если нужно было именно получить RFC.
Есть сторонние расширения. И для UUIDv7 тоже нет поддержки вендоров. (А если Вы скажете "пока нет" - так и для ULID так можно сказать.)
Обеспечить 100% гарантию монотонности и непредсказуемости (зная предыдущее значение) для неопределённого количества генерируемых в одну ms значений в рамках фиксированного количества бит - физически невозможно. Иными словами, тут обязательно будут какие-то trade-off. И вариант "не обеспечивать монотонность" в рамках ms - вполне приемлемый trade-off для многих приложений. Так что опциональность этой фичи, на мой взгляд, это достоинство, а не недостаток.
1. В целом - согласен. Но есть нюансы. Во-первых, данное отступление от спецификации - не является нарушением спецификации. Во-вторых, его можно внести в спецификацию, и это изменение даже будет обратно-совместимым. В общем, проблема есть, но она не критичная и решаемая, причём на уровне реализаций, без необходимости менять спеку.
2. В теории - всё верно. На практике - очень сомневаюсь, что это окажет сколь-либо заметное влияние на производительность БД. Кто-то проводит соответствующие бенчмарки, можно увидеть их результаты?
3. Во-первых, в ULID такое средство есть: в спеке чётко сказано, что при переполнении генерация ULID должна провалиться. Во-вторых, в UUIDv7 этих средств вообще нет - при генерировании чуть менее 17 млн. значений в одну ms случится переполнение, и я не увидел в спеке что в этой ситуации должно произойти.А точно не в 2 раза, а в 1000? И разве UUIDv7 в этом плане чем-то отличается?
Метаданные - в принципе странная фича, совершенно точно не являющаяся обязательной для уникальных ID, так что её отсутствие именно в спеке (ведь никто не мешает передать метаданные отдельно от любого ID, включая ULID) сложно считать недостатком.
Итого, резюмируя:
Недостаток "стандартизация и вендоры" проще и адекватнее решать пропихиванием одного из существующих решений, а не изобретением нового. Так что это не является ни недостатком ULID, ни достоинством UUIDv7. Это просто NIH-синдром - пропихивать собственное решение интереснее, чем чужое - это психологически понятно, но нельзя это всерьёз записывать в достоинства одному и недостатки другому.
Другой подход к реализации монотонности в UUIDv7 - не выглядит объективно лучшим или решающим какие-либо реальные проблемы. Он просто другой, вполне приемлемый. Т.е. снова NIH-синдром.
В UUIDv7 есть уникальная фича "метаданные". Довольно сомнительная, мягко говоря, и совершенно точно не оправдывающая создание нового стандарта.
Что я упустил?
4.3 в UUIDv7 этих средств вообще нет - при генерировании чуть менее 17 млн. значений в одну ms случится переполнение, и я не увидел в спеке что в этой ситуации должно произойти.
Стандарт допускает достаточно большое удлинение счетчика (вплоть до 42 бит) за счет псевдо-случайного сегмента, чтобы заведомо избежать переполнения счетчика при любых мыслимых технологиях. Ценой удлинения счетчика будет более низкая скорость поиска записей.
Если счетчик неудачно инициализируется единицами в старших разрядах, то всё равно самый старший бит счетчика всегда инициализируется нулем. Это означает, что по меньшей мере половина счетчика всегда свободна при его инициализации в начале миллисекунды.
Если всё же произойдет переполнение счетчика, то стандарт рекомендует тем, кому нужна монотонность любой ценой, приостановить генерацию UUID и ждать следующей миллисекунды. Стандарт не требует этого ото всех. Моя точка зрения, что приостановка генерации UUID чревата крахом приложения, и нужно пренебречь абсолютной монотонностью, заморозить счетчик и продолжать генерировать уникальные, но не возрастающие UUID. Современные СУБД на это отреагируют лишь небольшим снижением скорости поиска некоторых записей.
5. А точно не в 2 раза, а в 1000? И разве UUIDv7 в этом плане чем-то отличается?
Когда возникает дополнительная секунда, таймстемп замораживается (ведь в минуте не может быть 61-ой секунды, и минута не может повториться), и счетчик, рассчитанный на 1 миллисекунду, вынужден заполняться 1 секунду, то есть, ровно в 1000 раз дольше.
Стандарт требует, чтобы дополнительные секунды не прибавлялись. Это означает, что ни одна формальная секунда (UTC) не будет длиться две фактических секунды, и счетчик не будет работать с экстремальной нагрузкой.
------------------------------------------------
Ваша обида понятна. Я тоже прилагал безуспешные усилия, чтобы ULID'ы появились в PostgreSQL. Время показало, что этот путь не приведет к успеху. ULID'ы так и не стали мейнстримом, как бы этого не хотелось. Что-то не хватило влиятельных желающих "пропихнуть" их в широкое использование. Поэтому было грех не воспользоваться статусом стандарта. Я убежден, что усилия по разработке стандарта были полезны.
Да нет никакой обиды. Мне не нравится UUID по двум причинам: чисто эстетически, и потому, что "на глаз" фиг отличишь какой он там версии, а версий неудачных было слишком уж много, поэтому когда клиенты будут присылать UUID намного сложнее полагаться на то, что клиент не использовал одну из неудачных версий, штатные валидаторы обычно пропускают любой UUID… и в результате либо надо городить дополнительные проверки на его версию, либо ждать проблем. В результате совместимость нового формата с UUID для меня звучит как серьёзный недостаток, который должен чем-то весомым компенсироваться… а каких-либо реальных преимуществ пока не видно.
В любом случае, большое спасибо за развёрнутые ответы. Я лично продолжу продвигать ULID, а если будет требование работать с UUID - ну, значит придётся ручками проверять что это v4 или v7, в зависимости от требований к монотонности.
"на глаз" фиг отличишь какой он там версии
Справедливости ради, первая циферка в третьей группе символов однозначно определяет версию. Это не очень удобно, но выучить и отличать версии «на глаз» всё-таки реально
20f2cf91-7945-42c6-96f4-0444cc9e91d4
017ff62c-7500-70e6-8f41-f5154d136d02
если будет требование работать с UUID — ну, значит придётся ручками проверять что это v4 или v7,
интересно, какой это use case? обычно использование всех вариаций uuid предполагает, что нам неинтересно что там внутри.
Это очень простой use case: хочется решить ту архитектурную проблему, из-за которой вообще понадобилось что-то вроде UUID, и не хочется при этом получить проблемы, которыми славятся все остальные версии UUID.
нам неинтересно что там внутри
К сожалению, многие абстракции "протекают", и эта - не исключение. Да, в теории оно должно "просто работать", и нам не должно быть интересно, что там внутри. Но на практике нам это очень даже интересно - потому что оно отказывается "просто работать" и так и норовит подкинуть неожиданных проблем.
ну так всё-таки расскажите в каких случаях приложению требуется анализировать содержимое uuid
Это что, просьба LMGTFY? Почитайте хотя бы статью в русской вики, там всё неплохо описано.
нет, это вопрос именно к вам: в какой задаче вам потребовалось различать разные варианты uuid
А, понял. Всё просто: когда мне нужен уникальный ID, генерируемый клиентами, и я начинаю искать подходящий для этой цели формат, мне нужно только это - уникальный ID, без каких-либо дополнительных проблем "в нагрузку".
Мне не нужны коллизии из-за слишком маленькой случайной части или некорректно реализованных библиотек на клиентах, мне не нужны утечки приватных данных клиентов, и мне даже не хочется задумываться о том, какие ещё могут быть проблемы если клиент использует ту версию UUID, которую даже сам RFC не рекомендует использовать "в качестве учетных данных для безопасности" (и нет, мне не хочется в каждом месте где используется UUID задумываться: "а не используется ли этот UUID в качестве учетных данных для безопасности").
Мне, помимо уникальности, может быть нужна ещё какая-то дополнительная фича, вроде монотонности. И ради фичи я готов думать о том, какой формат её обеспечивает, а какой нет. А вот задумываться о том, грозят ли мне чем-то известные недостатки UUID разных версий в каждом месте каждого проекта, или конкретно здесь обойдётся - нет ни малейшего желания.
Иными словами, различать разные версии необходимо для того, чтобы не нарваться на неприятности и даже не тратить силы пытаясь понять, могут ли в принципе случиться эти неприятности конкретно с этой версией UUID конкретно в этом месте данного проекта.
Мне не нужны коллизии из-за слишком маленькой случайной части или некорректно реализованных библиотек на клиентах, мне не нужны утечки приватных данных клиентов, и мне даже не хочется задумываться о том, какие ещё могут быть проблемы если клиент использует ту версию UUID, которую даже сам RFC не рекомендует использовать "в качестве учетных данных для безопасности" (и нет, мне не хочется в каждом месте где используется UUID задумываться: "а не используется ли этот UUID в качестве учетных данных для безопасности").
понял про что вы.
но как ULID вас защитит от «некорректно реализованных библиотек на клиентах»?
и если вы постулируете использование UUID v7, то использование другой стороной иной версии UUID будет уже не на вашей совести )
Что же это за архитектура информационной системы, в которой клиенты могут прислать что угодно? Какой дистрибутив дали пользователям, пусть тем и пользуются. И в этом дистрибутиве должен быть жестко зашит генератор UUID. В противном случае могут прислать какую-нибудь ерунду без уникальности и монотонности, сгенерированную самопальным генератором, но семерка будет стоять, где положено по спецификации.
Если пользователям дозволено самим выбирать или мастерить генератор UUID, то, конечно, придется для "защиты от дурака" караулить UUID устаревших форматов, проверять полученные UUID на монотонность, лезть в их "потроха" и т.д. Но это неверный путь. Чем меньше "велосипедов", тем лучше. В идеале UUID должны генериться системным софтом (ОС, СУБД, браузер, брокер сообщений) и даже аппаратно.
Что же это за архитектура информационной системы, в которой клиенты могут прислать что угодно?
Клиент-серверная? :)
В противном случае могут прислать какую-нибудь ерунду без уникальности и монотонности, сгенерированную самопальным генератором, но семерка будет стоять, где положено по спецификации.
Могут, но это разные вещи - налажать нечаянно из-за недостаточной квалификации или внимательности, и специально отправлять некорректные данные с какой-то целью. Разные риски, разные последствия, разные методы противодействия.
Валидация версии UUID направлена против первой категории, и она вполне полезна в этом качестве, потому что лажи кругом намного больше, чем настолько целевых атак хакеров.
В идеале UUID должны
Но мы-то живём не в идеале.
Лично я писал статью на русской вики (точнее, переводил с английской), но тоже не понимаю, зачем что-то анализировать
потому, что "на глаз" фиг отличишь какой он там версии
а, дошло, вы про то, что ULID штатно использует Crockford's base32 и совсем не похож на каноническую запись UUID?
ну так если храним ULID в БД не в текстовом, а в бинарном представлении (uuid в postgresql или uniqueidentifier в ms sql), то это различие теряется.
и да, в следующую версию стандарта хотят добавить base32 и для UUID, так что ожидайте UUID v4 в base32 )))
Он даёт монотонно возрастающий результат а не детерменированный — он добавляет случайное значение в заданном пользователем интервале
в стандарте такого нет
поэтому когда клиенты будут присылать UUID намного сложнее полагаться на то, что клиент не использовал одну из неудачных версий
ну ровно так же вы не проверите, что клиент не использовал реализацию ULID без рандомизации идентификаторов внутри миллисекунды.
более того, вариант/версия UUID как раз хранятся в самом идентификаторе, так что при желании вы можете не принимать какой-нибудь UUID v1 (я не говорю, что мне нравится эта идея, но вы первый начали проверку использования клиентами неудачных версий)
А в чём может быть практическая необходимость определять версию UUID'а?
По свойствам похоже на xid
While preparing this specification the following 16 different implementations were analyzed for trends in total ID length, bit Layout, lexical formatting/encoding, timestamp type, timestamp format, timestamp accuracy, node format/components, collision handling and multi-timestamp tick generation sequencing.
- [ULID] by A. Feerasta
- [LexicalUUID] by Twitter
- [Snowflake] by Twitter
- [Flake] by Boundary
- [ShardingID] by Instagram
- [KSUID] by Segment
- [Elasticflake] by P. Pearcy
- [FlakeID] by T. Pawlak
- [Sonyflake] by Sony
- [orderedUuid] by IT. Cabrera
- [COMBGUID] by R. Tallent
- [SID] by A. Chilton
- [pushID] by Google
- [XID] by O. Poitrey
- [ObjectID] by MongoDB
- [CUID] by E. Elliott
я писал много раз, мне не нравится подобное использование uuid.
содержимое uuid — внутреннее дело генератора, пользователь не должен полагаться на какие-то свойства идентификатора помимо длины и уникальности.
цель нового стандарта — решить проблему с неоптимальностью индексирования/партицирования по uuid (отсутствие локальности — сгенерированные последовательно значения оказываются разбросаны по случайным областям), а не заменить собой timestamp.
Участники разработки стандарта поддержали идею использования инкремента таймстемпа как защиты от переполнения счетчика. Скорее всего эта идея появится в следующей версии стандарта.
Участники разработки стандарта обсуждают удлинение UUID с нынешних 128 бит и применение нескольких текстовых кодировок.
Но самое интересное - это обсуждение стандартизованного подробного описания UUID и каждого его сегмента в формате JSON с передачей этого описания как параметра в функции генерации и парсинга UUID и в описание поля типа UUID в таблице БД. Само описание UUID не задается жестко в стандарте, а выбирается разработчиком из доступных вариантов и при необходимости кастомизируется. Описание передается и хранится отдельно от каждого UUID, чтобы уменьшить потребление памяти и увеличить производительность.
Описание UUID в целом может содержать: идентификатор описания, кодировку UUID, последовательность сегментов UUID.
Описание сегмента UUID может содержать: тип сегмента (таймстемп, счетчик, идентификатор генератора, случайное значение, выравнивающие нулевые биты для текстовой кодировки и др.), длину сегмента, точность таймстемпа, наличие инициализируемого нулем старшего бита счетчика (остальные биты инициализируются случайным значением), источники данных о времени, о дополнительных секундах, об идентификаторе генератора, источник случайных значений.
Наряду с обычными сегментами UUID, необходимыми для уникальности, монотонности (сортируемости) и неугадываемости UUID, могут описываться и метаданные: тип сущности (имя таблицы), секция или сегмент таблицы БД, контрольная сумма и т.д.
Вот иллюстрация, которая может быть полезна:
Рабочая группа IETF приступила к работе над стандартом: https://datatracker.ietf.org/wg/uuidrev/about/
План: Mar 2023 Submit RFC4122bis to the IESG for publication as Proposed Standard
Это тот случай когда обсуждение интереснее чем статья :)
Обсуждение авторами на Гитхабе было еще интереснее (на английском). Это было потрясающее столкновение мнений, мозговой штурм для решения серьезных проблем и шлифовка нюансов. До стандарта материал дошел уже в виде сухой выжимки, из которой выпали мотивы и обоснования (см. на Гитхабе), но сохранились довольно разные точки зрения в виде допустимых вариантов. Так как мотивы и обоснования не попали в стандарт, то выбрать правильный вариант сложно. К такому высушенному, но очень либеральному стандарту хорошо бы иметь более однозначную спецификацию, удовлетворяющую типичным потребностям. Я ее опубликую, когда стандарт утвердят. Стандарт вызвал интерес среди ведущих российских IT-компаний. Недавно он перешел в статус In WG Last Call
Я совсем не понял насчёт кастомного сегмента. Сложил количество бит в таблице из статьи, получил ровно 128. Куда писать дополнительные данные? "Справа от UUID", это как? :)
В проекте стандарта написано:
DBMS vendors are encouraged to provide functionality to generate and store UUID formats defined by this specification for use as identifiers or left parts of identifiers such as, but not limited to, primary keys, surrogate keys for temporal databases, foreign keys included in polymorphic relationships, and keys for key-value pairs in JSON columns and key-value databases.
Это означает, что идентификатор, хранящийся в едином поле базы данных может состоять из двух сегментов: слева UUID длиной 128 битов, а справа опциональный сегмент, длину которого стандарт не регламентирует. Но, например, 64-разрядный PostgreSQL выравнивает все данные до 64 битов. Поэтому сегмент короче 64 бит не даст никакой экономии места, и имеет смысл делать опциональный сегмент (если он вообще необходим) длиной именно 64 бита. Центробанк, например, требует цеплять к UUID контрольную сумму. Если длина контрольной суммы 8 битов, то оставшиеся 56 битов можно использовать для хранения всяких метаданных.
Встречайте UUID нового поколения для ключей высоконагруженных систем