Коллизии при генерации UUID в JavaScript?

Question

Это относится к этому вопросу . Я использую этот ответ для генерации 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 пользователей.
• за последние 2 месяца сгенерировано около 4000 UUID.
• Я получил около 20 столкновений - например, новый UUID, созданный сегодня, был таким же, как около 2 месяцев назад (другой пользователь).

Итак, вопросов :

1. Что является причиной проблемы?
2. Как мне этого избежать?

Answer 1

Действительно, есть коллизии, но только под Google Chrome. Проверьте мой опыт по теме здесь

http://devoluk.com/google-chrome-math-random-issue.html

Кажется, что столкновения случаются только при первых нескольких вызовах Math.random. Причина, если вы просто запустите метод createGUID / testGUIDs выше (который, очевидно, был первым, что я попробовал), он просто работает без каких-либо коллизий.

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

Answer 2

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

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

Answer 3

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

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

Просто к вашему сведению.

Answer 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);

Вы уверены, что здесь больше ничего не происходит?

Answer 5

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

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

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());