Kolizje podczas generowania identyfikatorów UUID w JavaScript?

Dotyczy to tego pytania . Używam poniższego kodu z tej odpowiedzi do generowania UUID w 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);
});

Wydawało się, że to rozwiązanie działa dobrze, ale pojawiają się kolizje. Oto co mam:

• Aplikacja internetowa działająca w Google Chrome.
• 16 użytkowników.
• około 4000 UUID zostało wygenerowanych w ciągu ostatnich 2 miesięcy przez tych użytkowników.
• Mam około 20 kolizji - np. Nowy UUID wygenerowany dzisiaj był taki sam jak około 2 miesiące temu (inny użytkownik).

Co powoduje ten problem i jak mogę go uniknąć?

Domyślam się, że Math.random()z jakiegoś powodu twój system jest uszkodzony (jakkolwiek dziwnie to brzmi). To jest pierwszy raport, jaki widziałem, że ktoś ma kolizje.

node-uuidma wiązkę testową , której można użyć do przetestowania dystrybucji cyfr szesnastkowych w tym kodzie. Jeśli to wygląda w porządku, to nie jest Math.random(), więc spróbuj zastąpić implementację UUID, której używasz, do uuid()metody tamtej i sprawdź, czy nadal masz dobre wyniki.

[Aktualizacja: Właśnie zobaczyłem raport Veselina o błędzie Math.random()podczas uruchamiania. Ponieważ problem występuje tylko podczas uruchamiania, node-uuidtest raczej nie będzie przydatny. Bardziej szczegółowo skomentuję link devoluk.com.]

Rzeczywiście są kolizje, ale tylko w Google Chrome. Sprawdź moje doświadczenie na ten temat tutaj

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

(Link uszkodzony od 2019 r. Link do archiwum: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)

Wydaje się, że kolizje mają miejsce tylko podczas kilku pierwszych wywołań Math.random. Ponieważ jeśli po prostu uruchomisz powyższą metodę createGUID / testGUIDs (która oczywiście była pierwszą rzeczą, którą wypróbowałem), działa ona bez żadnych kolizji.

Aby wykonać pełny test, należy ponownie uruchomić Google Chrome, wygenerować 32 bajty, ponownie uruchomić Chrome, wygenerować, ponownie uruchomić, wygenerować ...

Aby inni ludzie mogli to wiedzieć - napotkałem zaskakująco dużą liczbę pozornych kolizji przy użyciu techniki generowania UUID wspomnianej tutaj. Te kolizje trwały nawet po przełączeniu się na seedrandom dla mojego generatora liczb losowych. To sprawiło, że wyrwałem sobie włosy, jak możesz sobie wyobrazić.

W końcu doszedłem do wniosku, że problem był (prawie?) Związany wyłącznie z robotami robotów indeksujących Google. Gdy tylko zacząłem ignorować żądania z „googlebotem” w polu klienta użytkownika, kolizje zniknęły. Zgaduję, że muszą buforować wyniki skryptów JS w jakiś półinteligentny sposób, w wyniku czego nie można liczyć na to, że ich przeglądarka internetowa będzie zachowywać się tak, jak robią to zwykłe przeglądarki.

Tylko do Twojej wiadomości.

Chciałem opublikować to jako komentarz do twojego pytania, ale najwyraźniej StackOverflow mi na to nie pozwala.

Właśnie przeprowadziłem podstawowy test 100 000 iteracji w Chrome przy użyciu opublikowanego przez Ciebie algorytmu UUID i nie wykryłem żadnych kolizji. Oto fragment kodu:

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

Czy na pewno nie dzieje się tu coś więcej?

Odpowiedź, która pierwotnie opublikowała to rozwiązanie UUID, została zaktualizowana 28 czerwca 2017 r .:

Dobry artykuł z programistów Chrome Omawiając stan jakości Math.random PRNG w Chrome, Firefoksie i Safari. tl; dr - od końca 2015 r. jest „całkiem niezła”, ale nie kryptograficzna. Aby rozwiązać ten problem, oto zaktualizowana wersja powyższego rozwiązania, która wykorzystuje ES6, cryptoAPI i trochę kreatora JS, za które nie mogę przypisać :

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

Odpowiedzi tutaj dotyczą „co powoduje problem?” (Problem z nasionami Chrome Math.random), ale nie „jak mogę tego uniknąć?”.

Jeśli nadal szukasz, jak uniknąć tego problemu, napisałem tę odpowiedź jakiś czas temu jako zmodyfikowaną wersję funkcji Broofa, aby obejść ten konkretny problem. Działa poprzez przesunięcie pierwszych 13 liczb szesnastkowych o część szesnastkową znacznika czasu, co oznacza, że ​​nawet jeśli Math.random znajduje się na tym samym ziarnie, nadal generuje inny identyfikator UUID, chyba że zostanie wygenerowany dokładnie w tej samej milisekundach.