Uuid что это такое
UUID версии 7, или как не потеряться во времени при создании идентификатора
В течение многих лет я противостоял засилью UUID как ключей в базах данных, но со временем и практикой до меня дошло. Они действительно удобны, когда речь идёт о распределённых системах. Генерировать новый идентификатор на разных концах планеты не так-то просто. Создание псевдослучайных идентификаторов решает эту проблему.
Хотя, подобные решения, не всегда хороши. В отличие от обыкновенных цифровых значений, которые легко кешировать и сортировать, UUID не так гибки в использовании. UUID версии 7 предназначен как раз для того, чтобы разобраться с подобными проблемами.
Добро пожаловать в мир отсортированных случайностей.
Сами по себе UUID это не просто набор случайных битов. Существует несколько вариантов их генерации. @AloneCoder в своей статье как генерируются UUID в подробностях описывает уже существующие форматы идентификаторов, версии с первой по пятую.
UUID в базах данных
Почему нам необходимо генерировать UUID, а не просто брать случайные данные? Ну, ответов может быть множество. Сохранение данных о хосте, который сгенерировал последовательность, сохранение времени и тому подобных значений, позволяет сделать UUID более информативными. Подобный подход можно использовать при создании распределённых вычислительных систем. Например, вместо того, чтобы грузить базу данных запросами с датой, можно просто выбрать те идентификаторы, которые содержат в себе эту дату.
Всё бы хорошо, но вот именно это и не очень-то просто. Выбирать даты из строковых значений UUID это та ещё свистопляска. Почему? Ну, давайте посмотрим на последовательность генерации UUIDv1.
Берутся младшие 32 бита текущей временной метки UTC. Это будут первые 4 байта (8 шестнадцатеричных символов) UUID [ TimeLow ].
Берутся средние 16 битов текущей временной метки UTC. Это будут следующие 2 байта (4 шестнадцатеричных символа) [ TimeMid ].
Следующие 2 байта (4 шестнадцатеричных символа) конкатенируют 4 бита версии UUID с оставшимися 12 старшими битами текущей временной метки UTC (в которой всего 60 битов) [ TimeHighAndVersion ].
Как всё замечательно запутано. На самом деле, распарсить дату из такого идентификатора достаточно просто, но парсинг это парсинг. Это не весело и нагружает процессор.
Герой дня
Основная разработка ведётся силами двух разработчиков: bradleypeabody и kyzer-davis. Хабрачеловеки и хабраалиены могут поучаствовать в обсуждении и написании формата на гитхабе https://github.com/uuid6/uuid6-ietf-draft/.
Пять дней назад эта спецификация вызвала оживлённую дискуссию на hackernews.
При разработке спецификаций, были рассмотрены следующие форматы генерации UUID:
И так, что же такого особого в UUIDv7 и чем он отличается от предыдущих версий?
Эта версия идентификатора бинарно-сортируемая. То есть, вам больше не нужно конвертировать значения UUID в какой-либо другой формат, чтобы понять какое из них больше и меньше.
Ну а нам-то какая разница? Можно же сделать select id, creation_date order by creation_date и жить себе спокойно.
Вы не поняли вопроса.
Тут дело не в том, как вам, программисту, удобнее делать SELECT. Вопрос в том, как база данных хранит индексы. Созданные последовательно, UUIDv4 будут выглядеть случайными. Соответственно, при записи значений этих индексов в базу данных, даже если значения были созданы в один и тот же промежуток времени, кластеризация будет нагружать индексы при записи.
Представьте, у вас есть высоконагруженная система. 100 серверов генерируют новые записи с UUID несколько раз в секунду, и всё это летит в Redis, которые грузит эти данные в Postgresql.
Ага. Вот тут вот жизнь с UUIDv7 становится проще. Значения индексов не настолько разбросаны и следить за ними намного проще.
Плюс, значения ключей можно очень просто и быстро отсортировать в бинарном формате. Возьмите первые 64 бита идентификатора, и сравните их как int64 с другим идентификатором, и вы уже знаете, какой был создан раньше.
Но, как же это работает?
Ок, в отношении самой даты — тут всё просто. Запишите число, как unix timestamp и у вас есть что-то бинарно-сортируемое. Только я вас прошу, не стоит записывать эту дату кусками, в разнобой. Просто и понятно, первые 36 битов содержат в себе одно число. Но, если вы пытаетесь записать миллисекунды, то всё становится сложнее.
Давайте поговорим о математике. О приближении и лимитах. Любимая тема, а? Давайте посмотрим на следующую запись секунды: 05,625. Пять целых, шестьсот двадцать пять секунд. Отбрасываем 5, поскольку это будет записано в unix timestamp.
Если вы будете сохранять это значение в float, то выглядеть это будет страшно, с бинарной точки зрения. А если мы применим немного матана? Для начала разложим единицу в следующий ряд.
Достаточно, просто, правда? Если сложить все числа в этом ряду, то вы получите единицу. А что если складывать не каждый? Ну, с этим можно что-то сделать. Давайте присвоим каждому числу из этого ряда один бит. Каждый бит будет показывать, если этот член присутствует в ряду или нет.
Берём нашу суб-секундную точность, 0,625 и начинаем записывать эту точность с помощью битов.
Первое число 1/2, то есть 0,5. Если наше значение точности больше этого числа, то выставляем битовое значение в 1 и вычитаем это число из нашего текущего значения точности. В итоге получаем, битовую последовательность 1 и 0,125 в остатке.
Что самое приятное, в этой системе, так это то, что если вы урезаете количество бит с конца, то вы будете терять точность, но всё-же сохраните более или менее приближенное значение.
Значение сохраняется, и при этом, вы можете играть с количеством битов, которые вы расходуете на его запись. И — что самое главное — подобная запись производит бинарно-сортируемые значения.
Более того, существует очень простой математический способ выполнения этой операции. Для того чтобы закодировать любое число, сделайте следующее:
Ну и, понятное дело, для того, чтобы раскодировать, нужно сделать обратное.
Что мы получаем в итоге? Возможность сохранения времени с суб-секундной точностью в бинарно-сортируемом формате.
А в случае коллизий?
Если вы генерируете значения на одном узле, то существует вероятность, что даже при наличии суб-секундной точности вы можете создать два идентификатора в один промежуток времени.
Для этого стандарт предусматривает наличие счётчика произвольной длинны, который должен монотонно увеличиваться, если даты совпадают.
И в дополнение, можно задать произвольное количество битов, которые будут идентифицировать компьютер, сгенерировавший значение. (Записывать MAC адрес в это поле не стоит, ибо уж слишком часто это вызывало вопросы с точки зрения безопасности).
Плюс, всё пространство, которое не используется для времени, счётчика и номера компьютера (порядка 54х бит) необходимо заполнять случайными значениями для предотвращения каких-либо совпадений на разных узлах.
Что такое UUID?
Например при переходе по url posts/1 мы получим саму статью. А с использованием uuid идентификатор поста будет что-то вроде этого posts/ac5fb2c6-e43a-48e3-a116-47fc719a69c5
2 ответа 2
Это защита от получения произвольных данных всякими парсерами.
Например, захотел я собрать все посты с другого сайта, пишу:
И через пару секунд получаю содержимое 1000 постов с того сайта.
Основное назначение UUID — это позволить распределённым системам уникально идентифицировать информацию без центра координации. Таким образом, любой может создать UUID и использовать его для идентификации чего-либо с приемлемым уровнем уверенности, что данный идентификатор непреднамеренно никогда не будет использован для чего-то ещё. Поэтому информация, помеченная с помощью UUID, может быть помещена позже в общую базу данных, без необходимости разрешения конфликта имен.
Например у вас работают две копии сайта. В каждом из них идет автоинкрементное добавление id++. И вот вдруг к вам поступила задача слить эти две базы в одну. Вы столкнетесь с тем, что и в одной и в другой базе есть одинаковые id. А вот с uuid таких проблем не возникнет
Или у вас большая высоконагруженная система. Для распределения нагрузки вы создаете кластер из нескольких серверов. На каждом из серверов идет интенсивное добавление информации, а синхронизация между ними идет не сразу, а с опозданием. С uuid не возникнет проблем с дублированием ключей при синхронизации
Двигаем биты — или как реализовать свой стандарт UUID
Я работаю над открытой реализацией предложенного стандарта идентификаторов UUIDv7. На данный момент спецификация существует в виде IETF черновика. Черновик уже пережил два переиздания, и мы постоянно обновляем спецификации. Но сам документ — это дело простое. Для того чтобы кто-то мог воспользоваться новыми UUIDv7, нам надо написать как можно больше открытых имплементаций на различных языках.
Мне выпала стезя писать клиент на Golang. И всё бы было достаточно просто, если бы не сам стандарт. Для создания UUIDv7 вам нужно будет постоянно двигать различные биты в разных направлениях.
В этой статье я расскажу, с чем столкнулся, помогая с разработкой на golang.
Работа над подобным проектом — эта та ещё веселуха. Черновик стандарта находится в разработке, и после того как мы пробуем сделать что-то одно, идём, пробуем и разбираемся, что же получилось в итоге.
Во-первых, если вы посмотрите на обсуждение в github, то читать придётся очень много. Каждый из участников пытается спокойно обосновать свою точку зрения, это спокойствие обычно заключается в том, что любой комментарий занимает от двух до пяти страниц текста. Все эти комментарии сопровождаются вдумчивым вступлением и очень осторожным объяснением того, почему автор предыдущего комментария — дурак.
Во-вторых, надо быть готовым воевать. Над стандартом сейчас активно работают три человека. Я подключился к процессу имплементации. И всё бы хорошо… Открываешь документ, начинаешь писать код, аккуратно выравниваешь все значения в памяти, коммитишь код, идёшь, проверяешь комментарии… И впадаешь в ступор. Там уже дерутся по поводу того, сколько бит должна занимать та-самая-фича, которую ты только что писал. Тяжело вздыхаешь и идёшь переписывать уже существующий код.
Иногда, после того как я писал код, ко мне приходили и спрашивали моего мнения. «Удобно ли тебе писалось?». Я наивно отвечал: «Да не очень, но ничего, написалось». В таком случае мне радостно отвечали: «Отлично! Мы пересмотрим стандарт в таком случае, чтобы сделать его проще!». Фейспалм.
Посему основными требованиями для проекта были:
Для начала быстрое введение в тему UUIDv7
Вместо генерирования случайных значений в идентификаторах — мы будем зашивать дату и время в сам идентификатор. Разница между UUIDv4 и v7 заключается в том, что последний является бинарно-сортируемым.
Огромное количество движков баз данных позволяет хранить UUID как первичный ключ в таблице. При создании новых записей в распределённых системах создание уникальных идентификаторов — это больная тема. Наш новый стандарт создаёт записи, которые можно отсортировать бинарно. При этом мы можем существенно ускорить и упростить сортировку значений в базах данных. Более того, это положительно отразится на индексах.
Итак, давайте посмотрим на то, с чем мы работаем:
Вот наш герой. Первые 36 бит занимает unix-timestamp. Само по себе это уже гарантирует бинарную совместимость. Мы решили сократить 64 бита ts до 36 бит. При этом мы сможем сохранять даты до 4147 года. Оставшиеся биты нам понадобятся для хранения субсекундной точности. В UUID нам важно сохранить как можно больше энтропии. Первые 28 бит полного unix-ts хранят в себе нули на следующие два тысячелетия, посему мы их отсеиваем.
Далее у нас есть два замечательных прикола, называющиеся «обратной совместимостью». Нам надо хранить значения полей ver и var для совместимости с UUIDv4.
Итак, как вы видите, ничего не равняется ни по каким границам байтов. Более того, значение в поле subsec разбито на две части полем ver. Жизнь была бы намного проще, если бы мы могли просто выровнять всё по байтам и сложить их вместе. Но увы. Придётся выкручиваться.
Давайте посмотрим, что же такое UUID?
Какую бы версию UUID мы ни реализовывали, в конечном счёте нам надо выдать 16 байт. А так как нам нужно что-то, что очень легко портируется, переносится и адаптируется, то было бы глупо хранить UUIDv7 в любом другом формате, кроме как массив байт.
В файле uuid_base.go мы описываем этот массив и создаём простые форматтеры, позволяющие выводить сам идентификатор в нескольких широко используемых форматах.
Разврат начинается, когда мы добираемся до самой процедуры генерации идентификатора. В файле uuid_v7.go вы можете найти функцию Next, которая, собственно говоря, и генерирует идентификатор. В текущей реализации пользователь может установить определённые параметры генерации, поэтому сами поля заполняются по-разному.
Если вы посмотрите на эту логику, то увидите, что нам постоянно нужно выставлять определённые биты в определённых позициях в этом массиве данных.
Мы могли создать массив из 128 бит в памяти, но это было бы ужасно расточительно и требовало дополнительной конвертации данных из массива в 128 бит в 16-ти байтовый массив. Вместо этого мы будем писать в память напрямую.
Для этого мы создадим побитовый индексатор, который позволяет получать определённый бит из массива напрямую:
Так как в будущем этот код будет использоваться для генерации UUID версий 6, 7 и 8, то мы пытаемся повторно использовать базовый код. Посему, так как мы не можем напрямую приводить тип UUIDv7 к массиву бит, нам придётся создать функцию, которая будет обращаться к аналогичной функции базового класса.
А после добро пожаловать в мир очень простой магии.
Преобразуем позицию текущего бита в позицию байта путём деления на 8 без остатка, после чего берём остаток, который по факту является позицией бита в байте.
Создаём байт, равный единице. В бинарном представлении у нас получается 0000 0001. Сдвигаем выставленный бит в позицию, которую нам надо получить, и делаем OR. Сравниваем результат с нулём, и у нас в руках нужный бит.
Описанные выше операции тривиальны и не занимают много времени на процессоре, экономя память.
Для выставления бита возьмём за базу тот же код:
Для того чтобы выставить бит, мы опять создаём байт с одним битом и сдвигаем выставленный бит налево, после чего делаем побитовое OR, что гарантирует результат с поднятым битом.
Для того чтобы этот бит опустить, мы делаем побитовое AND с NOT нашего числа.
Итого: мы можем без особых проблем манипулировать битами в памяти напрямую.
Осталось только создать пару вспомогательных функций, которые сделают жизнь легче.
Для начала в данном проекте нам потребуется пара индексаторов:
По факту длина нашего UUID равна 123 битам, а не 128. Пять бит уходят на поля var и ver. Поэтому, когда мы складываем биты вместе, нам нужно знать их «относительную позицию» от начала нашего идентификатора.
В дополнение, так как нам нужно складывать последовательности битов, давайте напишем функцию, которая позволяет добавить последовательность битов к идентификатору и возвращает положение курсора для последующей записи данных в массив.
Так как мы пользуемся нашими функциями для индексирования, то поля var и ver останутся незаполненными. Их надо будет забить статическими значениями после того, как генерация была завершена.
Со всем вышеописанным работа с битами в байтах напрямую становится проще.
Мы просто генерируем куски нашего идентификатора и собираем их в памяти с помощью одной функции.
Эта функция получает и возвращает значение u.currentPosition, которое позволяет следить за тем, куда мы пишем в данный момент.
Страшная работа по написанию битов в байты выглядит не так уж страшно.
Берём всё, упаковываем, тестируем, создаём релиз, отдаём ребятам «на попробовать». И после сидим и ждём, что будет дальше, и что мы будем менять. Так как переписывать придётся всё, то надо перестать париться о том, что какой-то код можно будет спасти, или о том, что какой-то код можно будет использовать ещё раз.
При этом мы используем 16 байт памяти и не двигаем наш конечный массив туда-сюда по памяти. Экономим память один к шестидесяти четырём, так как массив из 128 бит хранит каждый бит в одном байте из-за выравнивания, и конечный объём памяти на хранение одного идентификатора (128*8) будет равняться одному килобайту, что расточительно для того, что занимает 16 байт.
Весь код доступен по лицензии MIT, посему, если вам приходится работать с битами в golang, вы запросто можете копировать функции из bitsetter.go. Этот код может работать с массивами произвольной длины.
Единственным ограничением будет потенциальное переполнение счётчика битов. Но я очень надеюсь, что вам не придётся писать код для ворочанья битов в гигабайтах информации.
НЛО прилетело и оставило здесь промокоды для читателей нашего блога:
Как генерируются UUID
Вы наверняка уже использовали в своих проектах UUID и полагали, что они уникальны. Давайте рассмотрим основные аспекты реализации и разберёмся, почему UUID практически уникальны, поскольку существует мизерная возможность возникновения одинаковых значений.
Современную реализацию UUID можно проследить до RFC 4122, в котором описано пять разных подходов к генерированию этих идентификаторов. Мы рассмотрим каждый из них и пройдёмся по реализации версии 1 и версии 4.
Теория
UUID (universally unique IDentifier) — это 128-битное число, которое в разработке ПО используется в качестве уникального идентификатора элементов. Его классическое текстовое представление является серией из 32 шестнадцатеричных символов, разделённых дефисами на пять групп по схеме 8-4-4-4-12.
Информация о реализации UUID встроена в эту, казалось бы, случайную последовательность символов:
Значения на позициях M и N определяют соответственно версию и вариант UUID.
Версия
Номер версии определяется четырьмя старшими битами на позиции М. На сегодняшний день существуют такие версии:
Вариант
Это поле определяет шаблон информации, встроенной в UUID. Интерпретация всех остальных битов в UUID зависит от значения варианта.
Мы определяем его по первым 1-3 старшим битам на позиции N.
1 0 0 0 = 8
1 0 0 1 = 9
1 0 1 0 = A
1 0 1 1 = B
Так что если вы видите UUID с такими значениями на позиции N, то это идентификатор в варианте 1.
Версия 1 (время + уникальный или случайный идентификатор хоста)
В этом случае UUID генерируется так: к текущему времени добавляется какое-то идентифицирующее свойство устройства, которое генерирует UUID, чаще всего это MAC-адрес (также известный как ID узла).
Идентификатор получают с помощью конкатенации 48-битного МАС-адреса, 60-битной временной метки, 14-битной «уникализированной» тактовой последовательности, а также 6 битов, зарезервированных под версию и вариант UUID.
Тактовая последовательность — это просто значение, инкрементируемое при каждом изменении часов.
Временная метка, которая используется в этой версии, представляет собой количество 100-наносекундных интервалов с 15 октября 1582 года — даты возникновения григорианского календаря.
Возможно, вы знакомы с принятым в Unix-системах исчислением времени с начала эпохи. Это просто другая разновидность Нулевого дня. В сети есть сервисы, которые помогут вам преобразовать одно временное представление в другое, так что не будем на этом останавливаться.
Хотя эта реализация выглядит достаточно простой и надёжной, однако использование MAC-адреса машины, на которой генерируется идентификатор, не позволяет считать этот метод универсальным. Особенно, когда главным критерием является безопасность. Поэтому в некоторых реализациях вместо идентификатора узла используется 6 случайных байтов, взятых из криптографически защищённого генератора случайных чисел.
Сборка UUID версии 1 происходит так:
Поскольку эта реализация зависит от часов, нам нужно обрабатывать пограничные ситуации. Во-первых, для минимизации коррелирования между системами по умолчанию тактовая последовательность берётся как случайное число — так делается лишь один раз за весь жизненный цикл системы. Это даёт нам дополнительное преимущество: поддержку идентификаторов узлов, которые можно переносить между системами, поскольку начальное значение тактовой последовательности совершенно не зависит от идентификатора узла.
Помните, что главная цель использования тактовой последовательности — внести долю случайности в наше уравнение. Биты тактовой последовательности помогают расширить временную метку и учитывать ситуации, когда несколько UUID генерируются ещё до того, как изменяются процессорные часы. Так мы избегаем создания одинаковых идентификаторов, когда часы переводятся назад (устройство выключено) или меняется идентификатор узла. Если часы переведены назад, или могли быть переведены назад (например, пока система была отключена), и UUID-генератор не может убедиться, что идентификаторы сгенерированы с более поздними временными метками по сравнению с заданным значением часов, тогда нужно изменить тактовую последовательность. Если нам известно её предыдущее значение, его можно просто увеличить; в противном случае его нужно задать случайным образом или с помощью высококачественного ГПСЧ.
Версия 2 (безопасность распределённой вычислительной среды)
Главное отличие этой версии от предыдущей в том, что вместо «случайности» в виде младших битов тактовой последовательности здесь используется идентификатор, характерный для системы. Часто это просто идентификатор текущего пользователя. Версия 2 используется реже, она очень мало отличается от версии 1, так что идём дальше.
Версия 3 (имя + MD5-хэш)
Если нужны уникальные идентификаторы для информации, связанной с именами или наименованием, то для этого обычно используют UUID версии 3 или версии 5.
Они кодируют любые «именуемые» сущности (сайты, DNS, простой текст и т.д.) в UUID-значение. Самое важное — для одного и того же namespace или текста будет сгенерирован такой же UUID.
Обратите внимание, что namespace сам по себе является UUID.
В этой реализации UUID namespace преобразуется в строку байтов, конкатенированных с входным именем, затем хэшируется с помощью MD5, и получается 128 битов для UUID. Затем мы переписываем некоторые биты, чтобы точно воспроизвести информацию о версии и варианте, а остальное оставляем нетронутым.
Важно понимать, что ни namespace, ни входное имя не могут быть вычислены на основе UUID. Это необратимая операция. Единственное исключение — брутфорс, когда одно из значений (namespace или текст) уже известно атакующему.
При одних и тех же входных данных генерируемые UUID версий 3 и 5 будут детерминированными.
Версия 4 (ГПСЧ)
Самая простая реализация.
6 битов зарезервированы под версию и вариант, остаётся ещё 122 бита. В этой версии просто генерируется 128 случайных битов, а потом 6 из них заменяется данными о версии и варианте.
Такие UUID полностью зависят от качества ГПСЧ (генератора псевдослучайных чисел). Если его алгоритм слишком прост, или ему не хватает начальных значений, то вероятность повторения идентификаторов возрастает.
В современных языках чаще всего используются UUID версии 4.
Её реализация достаточно простая:
Версия 5 (имя + SHA-1-хэш)
Единственное отличие от версии 3 в том, что мы используем алгоритм хэширования SHA-1 вместо MD5. Эта версия предпочтительнее третьей (SHA-1 > MD5).
Практика
Одним из важных достоинств UUID является то, что их уникальность не зависит от центрального авторизующего органа или от координации между разными системами. Кто угодно может создать UUID с определённой уверенностью в том, что в обозримом будущем это значение больше никем не будет сгенерировано.
Это позволяет комбинировать в одной БД идентификаторы, созданные разными участниками, или перемещать идентификаторы между базами с ничтожной вероятностью коллизии.
UUID можно использовать в качестве первичных ключей в базах данных, в качестве уникальных имён загружаемых файлов, уникальных имён любых веб-источников. Для их генерирования вам не нужен центральный авторизующий орган. Но это обоюдоострое решение. Из-за отсутствия контролёра невозможно отслеживать сгенерированные UUID.
Есть и ещё несколько недостатков, которые нужно устранить. Неотъемлемая случайность повышает защищённость, однако она усложняет отладку. Кроме того, UUID может быть избыточным в некоторых ситуациях. Скажем, не имеет смысла использовать 128 битов для уникальной идентификации данных, общий размер которых меньше 128 битов.
Уникальность
Может показаться, что если у вас будет достаточно времени, то вы сможете повторить какое-то значение. Особенно в случае с версией 4. Но в реальности это не так. Если бы вы генерировали один миллиард UUID в секунду в течение 100 лет, то вероятность повторения одного из значений была бы около 50 %. Это с учётом того, что ГПСЧ обеспечивает достаточное количество энтропии (истинная случайность), иначе вероятность появления дубля будет выше. Более наглядный пример: если бы вы сгенерировали 10 триллионов UUID, то вероятность появления двух одинаковых значений равна 0,00000006 %.
А в случае с версией 1 часы обнулятся только в 3603 году. Так что если вы не планируете поддерживать работу своего сервиса ещё 1583 года, то вы в безопасности.
Впрочем, вероятность появления дубля остаётся, и в некоторых системах стараются это учитывать. Но в подавляющем большинстве случаев UUID можно считать полностью уникальными. Если вам нужно больше доказательств, вот простая визуализация вероятности коллизии на практике.