Это относится к этому вопросу . Я использую приведенный ниже код из этого ответа для создания UUID в JavaScript:
'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
return v.toString(16);
});
Это решение работает нормально, но возникают коллизии. Вот что у меня есть:
- Веб-приложение, работающее в Google Chrome.
- 16 пользователей.
- около 4000 UUID были сгенерированы этими пользователями за последние 2 месяца.
- У меня было около 20 коллизий - например, новый UUID, сгенерированный сегодня, был таким же, как около 2 месяцев назад (другой пользователь).
Что вызывает эту проблему и как ее избежать?
(r&0x3|0x8)
часть / оценка?Ответы:
Я предполагаю, что
Math.random()
по какой-то причине ваша система сломалась (как бы странно это ни звучало). Это первый отчет о столкновениях, который я видел.node-uuid
имеет тестовую программу, которую вы можете использовать для проверки распределения шестнадцатеричных цифр в этом коде. Если все в порядке, значит, это неMath.random()
так, поэтому попробуйте заменить используемую вами реализацию UUID вuuid()
метод и посмотреть, получите ли вы по-прежнему хорошие результаты.[Обновление: только что видел отчет Веселина об ошибке
Math.random()
при запуске. Поскольку проблема только при запуске,node-uuid
тест вряд ли пригодится. Я прокомментирую более подробно ссылку на devoluk.com.]источник
Коллизии действительно есть, но только под Google Chrome. Ознакомьтесь с моим опытом по этой теме здесь
http://devoluk.com/google-chrome-math-random-issue.html
(Ссылка не работает с 2019 года. Ссылка на архив: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)
Похоже, что коллизии происходят только при первых вызовах Math.random. Потому что, если вы просто запустите описанный выше метод createGUID / testGUIDs (который, очевидно, был первым, что я попробовал), он просто работает без каких-либо столкновений.
Итак, чтобы провести полный тест, необходимо перезапустить Google Chrome, сгенерировать 32 байта, перезапустить Chrome, сгенерировать, перезапустить, сгенерировать ...
источник
Просто чтобы другие знали об этом - я столкнулся с удивительно большим количеством очевидных коллизий, используя упомянутую здесь технику генерации UUID. Эти столкновения продолжались даже после того, как я переключился на seedrandom для своего генератора случайных чисел. Это заставило меня вырвать себе волосы, как вы понимаете.
В конце концов я понял, что проблема была (почти?) Связана исключительно с роботами-роботами Google. Как только я стал игнорировать запросы с "googlebot" в поле user-agent, коллизии исчезли. Я предполагаю, что они должны кэшировать результаты JS-скриптов каким-то полуинтеллектуальным способом, в результате чего нельзя рассчитывать на то, что их браузеры-пауки будут вести себя так, как обычные браузеры.
Просто к вашему сведению.
источник
Я хотел опубликовать это как комментарий к вашему вопросу, но, видимо, StackOverflow мне не позволит.
Я только что провел рудиментарный тест из 100000 итераций в Chrome, используя опубликованный вами алгоритм UUID, и не получил никаких коллизий. Вот фрагмент кода:
var createGUID = function() { return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) { var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8); return v.toString(16); }); } var testGUIDs = function(upperlimit) { alert('Doing collision test on ' + upperlimit + ' GUID creations.'); var i=0, guids=[]; while (i++<upperlimit) { var guid=createGUID(); if (guids.indexOf(guid)!=-1) { alert('Collision with ' + guid + ' after ' + i + ' iterations'); } guids.push(guid); } alert(guids.length + ' iterations completed.'); } testGUIDs(100000);
Вы уверены, что здесь больше ничего не происходит?
источник
Ответ, который изначально опубликовал это решение UUID, был обновлен 28.06.2017:
function uuidv4() { return ([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[018]/g, c => (c ^ crypto.getRandomValues(new Uint8Array(1))[0] & 15 >> c / 4).toString(16) ) } console.log(uuidv4());
источник
Ответы здесь касаются того, "что вызывает проблему?" (Проблема с семенами Chrome Math.random), но не «как я могу этого избежать?».
Если вы все еще ищете, как избежать этой проблемы, я написал этот ответ некоторое время назад как модифицированный подход к функции Бруфа, чтобы обойти эту точную проблему. Он работает, смещая первые 13 шестнадцатеричных чисел шестнадцатеричной частью метки времени, что означает, что даже если Math.random находится на одном и том же семени, он все равно будет генерировать другой UUID, если он не сгенерирован точно в ту же миллисекунду.
источник