Столкновения при генерации UUID в JavaScript?

Ответ 1

Я думаю, что Math.random() по какой-то причине не работает в вашей системе (как это ни странно звучит). Это первое сообщение о столкновениях, которое я видел.

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

[Обновление: только что увидел Веселин отчет об ошибке с Math.random() при запуске. Поскольку проблема возникает только при запуске, тест node-uuid вряд ли будет полезен. Более подробно прокомментирую ссылку на devoluk.com.]

Ответ 2

Действительно, есть столкновения, но только под 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, сгенерировать, перезапустить, сгенерировать...

Ответ 3

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

В конце концов я понял, что проблема была (почти?) исключительно связана с бот-роботами Google. Как только я начал игнорировать запросы с "googlebot" в поле user-agent, столкновение исчезло. Я предполагаю, что они должны кэшировать результаты JS-скриптов каким-то полу-интеллектуальным способом, в результате чего их браузер spidering не может рассчитывать на то, как ведут себя обычные браузеры.

Просто FYI.

Ответ 4

Я хотел опубликовать это как комментарий к вашему вопросу, но, по-видимому, StackOverflow не позволяет мне.

Я только что провел рутинный тест 100 000 итераций в 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);

Вы уверены, что здесь что-то еще не происходит?

Ответ 5

Ответ, который первоначально опубликовал это решение UUID, был обновлен в 2017-06-28:

A хорошая статья от разработчиков Chrome обсуждение состояния Math.random PRNG в Chrome, Firefox и Safari. tl; dr - По состоянию на конец 2015 года это "неплохо", но не криптографическое. Чтобы решить эту проблему, приведена обновленная версия вышеупомянутого решения, которое использует ES6, API crypto и немного JS wizardy, я не могу взять кредит:

  function uuidv4() {
 return ([1e7] + - 1e3 + -4e3 + -8e3 + -1e11).replace(/[018]/g, c = >
   (c ^ crypto.getRandomValues ​​(новый Uint8Array (1)) [0] & c/4).toString(16)
 )
}

console.log(uuidv4());код>

Ответ 6

Ответы здесь имеют дело с "чем вызвана проблема?" (Chrome Math.random семян), но не "как я могу избежать этого?"

Если вы все еще ищете, как избежать этой проблемы, я написал этот ответ некоторое время назад в качестве модифицированного подхода к функции Broofa, чтобы обойти эту проблему. Он работает путем смещения первых 13 шестнадцатеричных чисел на шестнадцатеричную часть метки времени, что означает, что даже если Math.random находится в том же начальном числе, он все равно будет генерировать другой UUID, если он не будет сгенерирован в ту же миллисекунду.