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

Это относится к этому вопросу. Я использую этот ответ для генерации 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. Как я могу избежать этого?
Источник

5 ответов

Решение

Я думаю, что 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

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

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

Источник

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

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

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

Источник

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

Хорошая статья от разработчиков Chrome, в которой обсуждается состояние качества MNT.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());

Источник

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

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

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

Источник

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

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

Источник
Другие вопросы по тегам