LINUXTALKS.CO

Уникальность (что б её) и коллизии

 , ,

L


0

1

Короче (если получится):

В настоящее время, для обеспечения уникальности неких «элементов», хранимых в базе данных, используется uuid V4.

И всё бы ничего, но, предполагается генерация этих uuid на разных инстансах. Что, не теоретически, а практически, точно приведёт к коллизиям (генерации разными инстансами одинаковых значений). Чтобы эти инстансы не зависили от некоего единственного провайдера uuid’ов, который в состоянии проверять, выдавал ли он ранее такой uuid или нет, появилась идея использовать «пространства имён» на основе даты и времени создания нового «элемента».

Вообще, понятно, что в самой таблице, хранящей данные «элементов», присутствует автоинкрементное поле «id», которое эту уникальность, конечно же, обеспечивает. Но вот беда, некоторые приложения, пользующиеся этими данными, не используют автоинкрементные айдишники, а используют выше обозначеный uuid V4. Засим, дабы не патчить эти приложения, вместо uuid V4 им можно подсунуть строковый уникальный идентификатор, о котором ниже:

Я хочу генерировать уникальные ключи вида (без квадратных скобок, они тут только для того, чтобы вам было понятно из чего состоит ключ):

[year][month][day][hour][min][sec][usec][usec][usec]

Где:

year – год, всегда 4 цифры

month – месяц в году, всегда 2 цифры

day – день, всегда 2 цифры

hour – текущий час, всегда 2 цифры

min – текущие минуты, всегда 2 цифры

sec – текущие секунды, всегда 2 цифры

usec – текущие микросекунды, всегда 6 цифр, три раза по 6

Теперь подробнее про микросекунды:

Тики процессора, в принципе, по частоте их следования, сопоставимы с его тактовой частотой и значениями микросекунд. Кроме того, процессор, как правило, выполняет несколько задач, циклически обходя каждую из них, и, возвращаясь к задаче генерации ключа, эта задача, трижды запрашивающая текущее значение микросекунд, будет получать немного отличающиеся значения (уже проверено). Ну а три раза подряд – это и есть защита от коллизий в пределах одной секунды, ещё и на разных инстансах.

Так вот вопрос:

Насколько по вашему подход, выбранный мной, будет надёжным? Конечно же, учитывая генерацию на разных инстансах.

★★★★★★★★★★

Ещё ты можешь каждому инстансу назначить свой уникальный номер и включить его в этот id.

Так же раз ты всё равно заменяешь системный генератор id патченным то что тебе мешает добавить к нему инкрементный счётчик который будет нумеровать id выданные на интервале в n наносекунд, при этом если счётчик наполняется то выдача id задерживается до следующего интервала.

torvn77    
★★
Android / Chrome
Ответ на: комментарий от torvn77

Ненене…

Я не заменяю «системный» генератор уидов. В этих «некоторых» приложениях он у каждого свой. Имелся в виду отдельный сервис, выдающий эти уиды, который и хотелось бы не вводить в зависимости.

Введение каждому инстансу своего префикса для ключа чревато ручным добавлением этих самых инстансов. Чего также хотелось бы избежать.

наносекунд

А где их, наносекунды, брать то? Не у всех машин такая точность. А в микросеки умеют все.

задерживается

Никаких задержек, плиз.

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

А в микросеки умеют все.

Это я писюк с fpga перепутал.

Никаких задержек, плиз.

А ты не делай больших периодов, скажем если у тебя период 50 микросекунд и на 40 микросекунде переполнился однобайтный счётчик то что, у тебя всё развалится от задержки в 10 микросекунд ожидания нового периода?

И ты точно уверен что за эти 50 микросекунд раздашь 255 штук id?

И даже если тебе не подходят эти значения, то что тебе меешает увеличить размер счётчика или уменьшить размер периода?

На худой конец можно сделать так, счётчик запоминает время и дальше выдаёт номера к запомненному времени пока не переполнится, а там запоминает новое время и так по кругу.

Ну может стоит поставить таймер инициализирующий этот счётчик раз за какой либо период, чтоб одна серия номеров слишком долго не тянулась.

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 2)

Android / Chrome
Ответ на: комментарий от torvn77

Как мне синхронизировать «запоминания» счётчиков разных инстансов?

Инстансы не мои и доступа туда я не имею, ну, кроме как «подсунуть вместо uuid своё строковое значение».

А база, да – моя.

deep-purple    
★★★★★★★★★★
Последнее исправление: deep-purple (всего исправлений: 2)

Linux / Firefox
Ответ на: комментарий от deep-purple

Думаю что самое надёжное вписывать id каждого инстанса, который каждому инстансу задавать в конфиге, всё равно ведь их у тебя много не будет.

На худой конец если инстансы в разных городах то используй в качестве id географические координаты города, дома или помещения в котором находится инстанс, яндекс или гуглокарты позволяют их определять с шагом около 10 метров.

Ну или сделай медленный сервис у которого инстанс по параметрам материнки, видеокарты, MAC и IP или подсетке, в общем по фингерпринту будет выдавать определённый постоянный id, мониторя факт работы этого инстанса посылая ему раз в секунду пакет и пока инстанс отвечает не отдавая этот ацди даже тем инстансам, кто может его получить.

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 2)

Android / Chrome
Ответ на: комментарий от torvn77

всё равно ведь их у тебя много не будет

Таки их много будет, иначе бы я и не заморачивался так. Срать своими uuid’ами они будут очень часто.

До фингерпринтов доступа нет. Есть только дрищщ от инстансов в виде их личных uuid’ов. Посылов к инстансу возможности нет – это они делают push, и никогда pull, и уж тем более с моей стороны никто не ожидает обращений, чтобы что-то там «синхронизировать». Я могу лишь ответить: «вот этот uuid – говно, держи правильный, там сам запомнишь».

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Код который на инстансе получает id не имеет доступа к /proc и /sys?

Да пусть даже так, тогда для вычисления фингерпринта можно сделать отдельный сервис который этот фингерпринт будет записывать в файл в /etc/fingerprint/fingerprint.txt

Да собственно тогда на этот вычислитель фингерпринта можно повесить и получение id с сервера и писать в файл сразу id.

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 1)

Android / Chrome
Ответ на: комментарий от torvn77

Код который на инстансе получает id не имеет доступа к /proc и /sys?

Ессна! Это обычная гуевая прилага с кучей проблем и зависимостей.

отдельный сервис

Чтобы эти инстансы не зависили от некоего единственного провайдера uuid’ов

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Тогда что тебе мешает использовать в качестве id географические координаты инстанса?

Ну понятно что их кто-то будет вписывать но положим расстряние между инстансами не менее чем 1 км, тогда даже не очень умному человеку будет сложно напутать.

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 2)

Android / Chrome
Ответ на: комментарий от torvn77

их кто-то будет вписывать

Таки их много будет, иначе бы я и не заморачивался так. Срать своими uuid’ами они будут очень часто

И легко и часто будут ситуации когда один старый скибнул, а совершенно новый прибыл. А старый ещё и вернуться когда-нибудь может – хоть через 5 минут, хоть через год.

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Может тогда лучше таки сделать сервис?

Ну или в качестве id инстанса использовать время/дату запуска инстанса в микросекундах, навряд ли они совпадут с такой точностью, чтобы были одинаковыми у двух инстансов сразу.

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 2)

Android / Chrome
Ответ на: комментарий от torvn77

Представь себе кучу гандозавров, положим, 40 тысяч, и каждый чего-то там синкует. У каждого из них свой генератор uuid, но эти uuid’ы, на стороне гандозавров на формат не проверяются, и могут быть заменены на мой личный уникалый uid того вида, как я описывал в стартпосте. Таким образом, я могу раздавать им глобально уникальные uid’ы, чтобы глобально же их различать у себя. Так, в итоге, сервис по выдаче uuid’ов и сервис по анализу их же, я хочу объединить в одном инстансе, к которому эти гандозавры и будут обращаться.

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Вообще я называл гондозавра инстансом, ну видимо не правильно понял что есть что.

Но по сути разве инстанс как ты его сейчас описал не будет единым провайдером id?

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 1)

Android / Chrome
Ответ на: комментарий от deep-purple

Я понимаю, ты щас скажешь, что, если ты можешь менять uuid’ы, то меняй именно uuid’ы, но, дело в том, что uuid’ы разных гандозавров могут быть одинаковы. Да, так и есть, да и хер с ними – это дело уникальности конкретного инстанса (гандозавра), но кроме uuid’а гандозавр присылает и путь до файла, к которому этот uuid и привязан, вот именно этот путь до файла, я считаю, должен быть уникален, не только для конкретного гандозавра, но и для всех остальных гандозавров, а также для АПИ с моей БД.

Суть проста: любой гандозавр должен сгенерировать максимально уникальный uid (или я его исправлю и отправлю гандозавру на апдейт). Конечно, я его проверю на уникальность, но коллизия должна быть исключением настолько редким, что песец.

deep-purple    
★★★★★★★★★★
Последнее исправление: deep-purple (всего исправлений: 1)

Linux / Firefox
Ответ на: комментарий от deep-purple

А инстанс это то, что это АПИ предоставляет?

И как я понимаю выполняется это всё, и гондозавры, и инстанс, паралельно (потоком или процессом не важно)на материнке с 4 ЦПУ по 32 ядра каждый?

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 2)

Android / Chrome
Ответ на: комментарий от deep-purple

А инстанс это то, что это АПИ предоставляет?

И как я понимаю выполняется это всё, и гондозавры, и инстансы, паралельно (потоком или процессом не важно)на нескольких компах с материнками с 4 ЦПУ по 32 ядра каждый?

torvn77    
★★
Последнее исправление: torvn77 (всего исправлений: 1)

Android / Chrome

Что, не теоретически, а практически, точно приведёт к коллизиям (генерации разными инстансами одинаковых значений).

Чего это?
Опасаться коллизий 128-битного UUID стоит, если у тебя элементов «хотя бы» порядка 2^64. У тебя что, правда столько?

Случай, когда ууиды генерируются одинаковыми ГПСЧ, которые инициализированы одним сидом, не рассматриваю, ибо тогда уже не просто «коллизии», а тупо одинаковые последовательности

TheAnonymous    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от TheAnonymous

если у тебя элементов «хотя бы» порядка 2^64

Сами элементы тут ни при чем, а вот инстансы могут херачить кто во что горазд:

https://stackoverflow.com/questions/6906916/collisions-when-generating-uuids-in-javascript

deep-purple    
★★★★★★★★★★
Linux / Firefox

UUID подразумевается глобально уникальным по умолчанию же. Коллизии могут теоритически возникнуть, если на разных инстансах генератор сидируют одним и тем же значением и генерация была в тот же момент времени. В этом плане таймстемп ещё менее надёжен, чем uuid, ибо неуникальность, clock drift и всё такое.

Если ты не доверяешь сторонним генераторам, то используй composite key на своей стороне (3rdparty uuid + client_id)

cocucka    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Там и причина указана - в реализации рандома в хромоногом js.
Если у тебя инстансы на js, можно использовать генератор, предназначенный для этой цели - crypto.randomUUID()

TheAnonymous    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от cocucka

В этом плане таймстемп ещё менее надёжен

Кстати, коли речь оказывается про js и браузеры, там вроде таймеры загрубили для защиты от всяких спектров-мельдониев, так что с уникальностью будет даже ещё хуже

TheAnonymous    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от cocucka

Вот бы не использовать айди клиента в ключе, ибо клиентов много и ручное их добавление – суть гемор.

таймстемп ещё менее надёжен

Я зацепился за микросеки, таймстамп там только ака неймспейс. Может этот самый ууид запользовать в конце вместо микросеков?

deep-purple    
★★★★★★★★★★
Последнее исправление: deep-purple (всего исправлений: 1)

Linux / Firefox
Ответ на: комментарий от TheAnonymous

Ща вообще с уникальностью проблемы. Только ленивый не деплоится в кубер, а там хз что творится вообще. Никто тебе не гарантирует, что твой контейнер не зашедулится на ту же ноду, что и другой такой же (не факт что даже твой ибо какой-нибудь GCP чёрный ящик с дыркой сбоку). Источники энтропии и системные часы будут одни и те же. Вот и гадай насколько уникальный твой уникальный идентификатор.

cocucka    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Я думаю тебе надо вернутся к твоему прежнему посту:

Я не заменяю «системный» генератор уидов. В этих «некоторых» приложениях он у каждого свой. Имелся в виду отдельный сервис, выдающий эти уиды, который и хотелось бы не вводить в зависимости.

Введение каждому инстансу своего префикса для ключа чревато ручным добавлением этих самых инстансов. Чего также хотелось бы избежать.

И так, если тебе надо чтобы инстансы имели общую характеристику, например уникальность для всего облака создаваемого инстансом id то должно быть что-то, что эти инстансы объединит, будь то сервис или созданный в ручную id инстанса.

Для тебя отмечу то, что как я понимаю тебе не нужно строгое соответствие между инстансами и их id, тебе достаточно чтобы в каждый момент времени каждый id инстанса использовался не более чем одним инстансом.

Отсюда простой рецепт: для каждого хоста являющимся сервером облака инстансов ты создаёшь на этом хосте директорию в которую складываешь пустые файлы с именами в виде предварительно сненерированных для этого хоста id инстансов и далее конкретный инстанс берёт себе из неё случайный свободный id инстанса и создаёт для него lock файл показывая что этот id инстанса занят.

torvn77    
★★
Android / Chrome
Ответ на: комментарий от deep-purple

Не, я б на твоём месте даже и не пытался на время завязываться. Это только у нормальных людей оно всё время вперед течёт, а у программистов бывает и наооборот.

cocucka    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от cocucka

Даже если будет у каждого свой, то авторизация никак не связана с данными в базе. Проблема в том, что все эти клиенты используют данные из одной базы, но ууиды для этих данных у этих клиентов у каждого свои. Отсюда возникают коллизии и на стороне базы и на стороне клиентов, т.к. каждый клиент мерджит данные, отправляет свои новые в базу и получает чужие (других клиентов) из базы. Клиенту можно скормить в ответе (в другом пересылаемом в обе стороны поле) ключи, уникальные для всей базы, а соответственно, уникальные и для всех клиентов. Клиент может сопоставить свой, коллизный к внешним, но уникальный у него, ууид и этот ключ для какой-то записи. Пусть ебется со своими ууидами сам. Дабы обойти коллизии с ууидами, я хочу вообще не цепляться за ууиды клиентов и вообще не хранить их в базе, вместо этого хранить свои уникальные.

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от cocucka

Потому и спрашиваю, насколько уникальными будут ключи, генерящиеся зависимо от времени добавления записи не важно каким клиентом?

Ты говоришь, что получится херня. Я согласен. Какой тогда формат ключа не даст коллизий для одной записи между всеми клиентами? Ключ клиента? Больше никак? Тогда придется дергать писателей клиентов, а это, не сказать, что просто и быстро – у них давно формат обмена данными устаканился. Хак с другим пересылаемым полем позволяет никого не дергать.

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Потому и спрашиваю, насколько уникальными будут ключи, генерящиеся зависимо от времени добавления записи не важно каким клиентом?

Если генерация зависит только от времени, то нужно для надёжности использовать hardware RTC, ну или хотя бы ядерные таймеры. Если ты будешь брать условное epoch time, то можно нарваться на коллизии при коррекции часов демоном ntp. И это всё должно быть на одном единственном хосте, на нескольких у тебя ещё больше сложностей будет. Плюс, если у тебя многопоточное приложение, то при одновременной обработке нескольких запросов так же может произойти коллизия, тогда надо к таймстампу дополнительно брать ещё один монотонный атомарный счётчик.

cocucka    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от deep-purple

Я, правда, до конца не понимаю механизм работы сервиса. Получается, что у тебя все клиенты могут добавлять записи в базу. При этом идентификаторы создаются ими же, а не тобой. И с этими айдишниками кто в лес, кто по дрова. Правильно?

Тогда надо генерить свой и возвращать клиенту в ответ, пусть они там сами ебутся с маппингом.

Если ты можешь заставить клиентов использовать твой айдишник, то генерь его сам тем же UUID генератором, только проинициализируй его правильно.

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

cocucka    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от cocucka

И с этими айдишниками кто в лес, кто по дрова. Правильно?

Именно так.

надо генерить свой и возвращать клиенту в ответ, пусть они там сами ебутся с маппингом

Они этого не умеют…

надо городить композитный ключ у себя, при этом нужно будет как-то уникально идентифицировать клиентов

Эх… Обрадовал ты меня!

deep-purple    
★★★★★★★★★★
Linux / Firefox
Ответ на: комментарий от TheAnonymous

Я не имею доступа аудита и модификации этих инстансов. Нормальный он там или не нормальный – это не решит проблему коллизий в агрегаторе данных на моей стороне. Да забейте уже, горожу ключи инстансов.

deep-purple    
★★★★★★★★★★
Android / Firefox