Ini berkaitan dengan pertanyaan ini . Saya menggunakan kode di bawah ini dari jawaban ini untuk menghasilkan UUID dalam 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);
});
Solusi ini tampaknya berfungsi dengan baik, tetapi saya mengalami benturan. Inilah yang saya miliki:
- Aplikasi web yang berjalan di Google Chrome.
- 16 pengguna.
- sekitar 4000 UUID telah dibuat dalam 2 bulan terakhir oleh para pengguna ini.
- Saya mendapat sekitar 20 tabrakan - misalnya UUID baru yang dibuat hari ini sama dengan sekitar 2 bulan lalu (pengguna berbeda).
Apa yang menyebabkan masalah ini dan bagaimana cara menghindarinya?
javascript
random
uuid
collision
Muxa
sumber
sumber
(r&0x3|0x8)
porsi / evaluasi itu?Jawaban:
Tebakan terbaik saya adalah yang
Math.random()
rusak pada sistem Anda karena beberapa alasan (aneh kedengarannya). Ini adalah laporan pertama yang saya lihat dari seseorang yang mengalami tabrakan.node-uuid
memiliki test harness yang dapat Anda gunakan untuk menguji distribusi digit hex dalam kode itu. Jika itu terlihat oke maka tidakMath.random()
, jadi coba gantikan implementasi UUID yang Anda gunakan ke dalamuuid()
metode di sana dan lihat apakah Anda masih mendapatkan hasil yang baik.[Pembaruan: Baru saja melihat laporan Veselin tentang bug dengan
Math.random()
saat startup. Karena masalahnya hanya pada saat permulaan,node-uuid
pengujian tersebut tidak mungkin berguna. Saya akan berkomentar lebih detail di tautan devoluk.com.]sumber
Memang ada benturan tapi hanya di bawah Google Chrome. Lihat pengalaman saya tentang topik tersebut di sini
http://devoluk.com/google-chrome-math-random-issue.html
(Tautan rusak pada 2019. Tautan arsip: https://web.archive.org/web/20190121220947/http://devoluk.com/google-chrome-math-random-issue.html .)
Sepertinya tabrakan hanya terjadi pada beberapa panggilan pertama Math.random. Penyebab jika Anda hanya menjalankan metode createGUID / testGUIDs di atas (yang jelas merupakan hal pertama yang saya coba) itu hanya berfungsi tanpa benturan sama sekali.
Jadi untuk melakukan tes lengkap seseorang perlu memulai ulang Google Chrome, menghasilkan 32 byte, memulai ulang Chrome, menghasilkan, memulai ulang, menghasilkan ...
sumber
Hanya agar orang lain dapat mengetahui hal ini - saya mengalami banyak sekali tabrakan yang terlihat menggunakan teknik pembuatan UUID yang disebutkan di sini. Tabrakan ini berlanjut bahkan setelah saya beralih ke seedrandom untuk generator nomor acak saya. Itu membuat saya merobek rambut saya, seperti yang bisa Anda bayangkan.
Saya akhirnya menemukan bahwa masalahnya (hampir?) Secara eksklusif terkait dengan bot perayap web Google. Segera setelah saya mulai mengabaikan permintaan dengan "googlebot" di bidang agen pengguna, tabrakan tersebut menghilang. Saya menduga mereka harus menyimpan hasil skrip JS dalam beberapa cara semi-cerdas, dengan hasil akhir bahwa peramban spidering mereka tidak dapat diandalkan untuk berperilaku seperti yang dilakukan peramban normal.
Hanya FYI.
sumber
Saya ingin memposting ini sebagai komentar untuk pertanyaan Anda, tetapi tampaknya StackOverflow tidak mengizinkan saya.
Saya baru saja menjalankan pengujian dasar 100.000 iterasi di Chrome menggunakan algoritme UUID yang Anda posting dan tidak ada benturan. Berikut cuplikan kodenya:
Apakah Anda yakin tidak ada hal lain yang terjadi di sini?
sumber
Jawaban yang awalnya memposting solusi UUID ini diperbarui pada 2017-06-28:
sumber
Jawabannya di sini berhubungan dengan "apa yang menyebabkan masalah?" (Masalah benih Chrome Math.random) tetapi bukan "bagaimana saya bisa menghindarinya?".
Jika Anda masih mencari cara untuk menghindari masalah ini, saya menulis jawaban ini beberapa waktu lalu sebagai modifikasi dari fungsi Broofa untuk mengatasi masalah yang sebenarnya ini. Ini bekerja dengan mengimbangi 13 angka hex pertama dengan bagian hex dari timestamp, yang berarti bahwa meskipun Math.random berada di seed yang sama, itu masih akan menghasilkan UUID yang berbeda kecuali dibuat pada milidetik yang sama persis.
sumber