Seberapa baik UUID.randomUUID Java?

311

Saya tahu bahwa UUID acak memiliki probabilitas yang sangat, sangat, sangat rendah untuk tabrakan secara teori, tetapi saya bertanya-tanya, dalam praktiknya, seberapa baik Java randomUUID()dalam hal tidak memiliki tabrakan? Adakah yang punya pengalaman untuk dibagikan?

java uuid Alvin
sumber
10
Dalam pengalaman saya, saya belum pernah melihat tabrakan ;-)
Thilo
4
Algoritma ditentukan dalam RFC1422: ietf.org/rfc/rfc4122.txt
skaffman
8
@skaffman: RFC mengatakan apa-apa tentang algoritma yang digunakan untuk menghasilkan angka acak.
Michael Borgwardt
4
Karena ini adalah pertanyaan yang lebih terbuka, saya kira saya tidak akan menandai jawaban apa pun sebagai jawaban yang benar; sebagai gantinya, saya akan memberikan satu suara untuk masing-masing jawaban yang menurut saya baik :)
Alvin
5
Dari wikipedia: ... Dengan kata lain, hanya setelah menghasilkan 1 miliar UUID setiap detik selama 100 tahun ke depan, kemungkinan membuat hanya satu duplikat adalah sekitar 50%.
MaVRoSCy

Jawaban:

168

Penggunaan UUID java.security.SecureRandom, yang seharusnya "kuat secara kriptografi". Sementara implementasi aktual tidak ditentukan dan dapat bervariasi di antara JVM (artinya setiap pernyataan konkret yang dibuat hanya valid untuk satu JVM tertentu), itu mengamanatkan bahwa output harus lulus uji generator angka acak statistik.

Selalu mungkin bagi suatu implementasi untuk mengandung bug halus yang merusak semua ini (lihat bug pembangkitan kunci OpenSSH) tapi saya tidak berpikir ada alasan konkret untuk khawatir tentang keacakan Java UUID.

Michael Borgwardt
sumber
34
"Selalu mungkin bagi implementasi untuk mengandung bug halus ..." - Atau (mengenakan topi timah) ... kekurangan yang disengaja disengaja. <:-)
Stephen C
25
Kekuatan kriptografi sama sekali tidak relevan untuk pertanyaan tabrakan.
Osa
14
@osa: Tidak menghasilkan tabrakan (lebih dari yang diharapkan dari keacakan sempurna) cukup banyak persyaratan kualitas terendah untuk RNG, sedangkan kekuatan kriptografi adalah yang tertinggi. Dengan kata lain, RNG yang kuat secara kriptografis pasti tidak akan menghasilkan lebih banyak tabrakan dari yang diperkirakan.
Michael Borgwardt
3
Mungkin berguna untuk dicatat, bahwa, jika Anda menjalankan JVM seperti mengeluarkan UUID di blogs.vmware.com/cto/… , Anda mungkin akan mendapatkan banyak, banyak tabrakan. Semua perangkat lunak RNG adalah PRNG, dan mereka pada akhirnya hanya sebagus sumber entropi mereka; dua PRNG yang mendapatkan seeded secara identik juga akan berperilaku identik, dan itu dapat terjadi secara mengejutkan sering dengan pengaturan server yang sama persis dan duplikat serta prosedur startup.
user508633
@ user508633: Saya benar-benar berharap untuk mendapatkan tingkat tabrakan 100% dalam kasus khusus itu, tetapi ini adalah kasus yang sangat spesifik yang jauh melampaui "pengaturan server yang konsisten, duplikat tepat dan prosedur memulai". Saya cukup yakin Anda tidak akan mendapatkan peningkatan tingkat tabrakan jika Anda hanya mengkloning VM dan menjalankannya secara normal. Penyemaian sendiri SecureRandom berusaha sangat keras untuk mendapatkan beberapa entropi nyata, hingga menghalangi eksekusi jika tidak dapat menemukan apa pun: seancassidy.me/wiggle-the-mouse-to-fix-the-test.html
Michael Borgwardt
114

Wikipedia memiliki jawaban yang sangat bagus http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

jumlah acak versi 4 UUID yang perlu dihasilkan untuk memiliki probabilitas 50% dari setidaknya satu tabrakan adalah 2,71 triliun, dihitung sebagai berikut:

...

Jumlah ini setara dengan menghasilkan 1 miliar UUID per detik selama sekitar 85 tahun, dan file yang mengandung banyak UUID ini, dengan 16 byte per UUID, akan menjadi sekitar 45 exabytes, beberapa kali lebih besar dari database terbesar saat ini yang ada, yang ada di urutan ratusan petabyte.

...

Dengan demikian, agar ada kemungkinan duplikasi satu per satu miliar, 103 triliun versi 4 UUID harus dihasilkan.

sheki
sumber
56
Saya juga mengutip dari halaman itu, "Probabilitas satu duplikat akan menjadi sekitar 50% jika setiap orang di bumi memiliki 600 juta UUID."
Jeff Axelrod
24
Ini hanya berlaku untuk keacakan yang sebenarnya, bukan untuk nomor pseudorandom seperti javas UUID.
Markus
9
@ Markus: sepenuhnya salah. Kemungkinan tabrakan untuk RNG acak pseudorandom yang baik, khususnya yang kuat secara kriptografis, tidak berbeda dengan keacakan "benar".
Michael Borgwardt
6
@ Eric - Saya pikir tanggung jawab ada pada Anda untuk mendukung pernyataan Anda. FWIW, satu-satunya skenario yang dapat saya pikirkan di mana UUID tipe 4 akan bertabrakan lebih sering yang menurut teori probabilitas adalah: 1) sumber angka crypto acak yang buruk, atau 2) perpustakaan UUID yang telah dikompromikan.
Stephen C
13
Ini tidak menjawab pertanyaan yang diajukan. Pertanyaannya adalah tentang kualitas keacakan di Jawa UUID.randomUUID(), bukan tentang peluang teoretis untuk generator angka acak sempurna yang diberikan.
kratenko
69

Adakah yang punya pengalaman untuk dibagikan?

Ada 2^122nilai yang mungkin untuk UUID tipe-4. (Spesifikasi mengatakan bahwa Anda kehilangan 2 bit untuk tipe, dan 4 bit lebih lanjut untuk nomor versi.)

Dengan asumsi bahwa Anda menghasilkan 1 juta UUID acak per detik, kemungkinan duplikat yang terjadi dalam hidup Anda akan semakin kecil. Dan untuk mendeteksi duplikat, Anda harus menyelesaikan masalah dengan membandingkan 1 juta UUID baru per detik dengan semua UUID yang sebelumnya Anda hasilkan 1 !

Peluang yang pernah dialami seseorang (yaitu benar-benar diperhatikan ) duplikat dalam kehidupan nyata bahkan lebih kecil daripada semakin kecil ... karena kesulitan praktis dalam mencari tabrakan.

Sekarang tentu saja, Anda biasanya akan menggunakan generator angka pseudo-acak, bukan sumber angka yang benar-benar acak. Tapi saya pikir kita bisa yakin bahwa jika Anda menggunakan penyedia yang dapat dikreditkan untuk angka acak kekuatan kriptografis Anda, maka itu akan menjadi kekuatan kriptografi, dan kemungkinan pengulangan akan sama seperti untuk generator nomor acak yang ideal (tidak bias). .

Namun, jika Anda menggunakan JVM dengan generator nomor crypto-random yang "rusak", semua taruhan dimatikan. (Dan itu mungkin termasuk beberapa solusi untuk masalah "kekurangan entropi" pada beberapa sistem. Atau kemungkinan bahwa seseorang telah bermain-main dengan JRE Anda, baik di sistem Anda atau di hulu.)

1 - Dengan asumsi bahwa Anda menggunakan "semacam binary btree" seperti yang diusulkan oleh komentator anonim, setiap UUID akan membutuhkan O(NlogN)bit memori RAM untuk mewakili NUUID yang berbeda dengan asumsi kepadatan rendah dan distribusi acak bit. Sekarang kalikan dengan 1.000.000 dan jumlah detik untuk menjalankan eksperimen. Saya tidak berpikir itu praktis untuk lamanya waktu yang dibutuhkan untuk menguji tabrakan RNG berkualitas tinggi. Bahkan dengan representasi pandai (hipotetis).

Stephen C
sumber
4
"(Dan untuk mendeteksi duplikatnya, Anda harus menyelesaikan masalah dengan membandingkan 1 juta UUID per detik dengan semua UUID yang telah Anda buat sebelumnya!)" - bagian itu relatif mudah dengan asumsi Anda telah menyimpan uuids di beberapa jenis struktur pohon biner, itu hanya akan menjadi satu keturunan pohon per uuid baru. Anda tidak perlu membandingkannya satu per satu dengan semua uuids yang dibuat sebelumnya.
user467257
20

Saya bukan ahli, tetapi saya berasumsi bahwa cukup banyak orang pintar melihat generator angka acak Jawa selama bertahun-tahun. Oleh karena itu, saya juga berasumsi bahwa UUID acak itu baik. Jadi Anda harus benar-benar memiliki probabilitas tumbukan teoritis (yaitu sekitar 1: 3 × 10 ^ 38 untuk semua UUID yang mungkin. Apakah ada yang tahu bagaimana perubahan ini hanya untuk UUID acak? Apakah ini 1/(16*4)di atas?)

Dari pengalaman praktis saya, saya belum pernah melihat tabrakan sejauh ini. Saya mungkin akan menumbuhkan janggut panjang yang mencengangkan pada hari saya mendapatkan yang pertama;)

sfussenegger
sumber
10
Dari wikipedia: ... Dengan kata lain, hanya setelah menghasilkan 1 miliar UUID setiap detik selama 100 tahun ke depan, kemungkinan membuat hanya satu duplikat adalah sekitar 50%.
MaVRoSCy
1
Sebenarnya wikipedia mengatakan ini untuk 85 tahun ke depan ... Saya katakan jangan mengandalkannya, seseorang di suatu tempat telah menghasilkan UUID yang sama seperti Anda
smac89
12

Di mantan majikan kami memiliki kolom unik yang berisi uuid acak. Kami mendapat tabrakan pada minggu pertama setelah dikerahkan. Tentu, peluangnya rendah tetapi tidak nol. Itu sebabnya Log4j 2 mengandung UuidUtil.getTimeBasedUuid. Ini akan menghasilkan UUID yang unik selama 8,925 tahun selama Anda tidak menghasilkan lebih dari 10.000 UUID / milidetik pada server tunggal.

rgoers
sumber
2
Iya. Tetapi pertanyaannya adalah tentang UUID acak (yaitu tipe-4).
Stephen C
1
Ia bertanya tentang kemungkinan tabrakan. Implikasinya adalah dia ingin memastikan untuk menghindari mereka.
rgoers
1
(Tabrakan kemungkinan besar disebabkan oleh sumber acak yang rusak untuk penyemaian PRNG. Pikir saya kira itu mungkin karena kebetulan murni.)
Stephen C
9

Skema generasi asli untuk UUID adalah untuk menyatukan versi UUID dengan alamat MAC komputer yang menghasilkan UUID, dan dengan jumlah interval 100 nanodetik sejak adopsi kalender Gregorian di Barat. Dengan mewakili satu titik dalam ruang (komputer) dan waktu (jumlah interval), peluang tabrakan nilai secara efektif adalah nihil.

Alex2Ustas
sumber
1
Penjelasan ini membuat saya optimis untuk tidak melihat tabrakan dalam praktek. Bisakah Anda menunjuk referensi apa pun untuk pernyataan ini (beberapa kode sumber akan lebih baik)?
Dragan Marjanović
Menemukan ini di specs ietf.org/rfc/rfc4122.txt . Namun demikian akan bagus untuk melihat implementasi.
Dragan Marjanović
1
Namun, skema itu bukan yang diterapkan Java. Java mengimplementasikan UUID tipe 4, yang merupakan acak murni dan tidak termasuk alamat MAC atau waktu. Kebetulan, karena sekarang ada banyak perangkat fisik dan virtual di mana Anda dapat memilih alamat MAC Anda, algoritma asli tidak menjamin keunikan.
Søren Boisen
8

Banyak jawaban membahas berapa banyak UUID yang harus dihasilkan untuk mencapai kemungkinan tabrakan 50%. Tapi kemungkinan tabrakan 50%, 25%, atau bahkan 1% tidak berguna untuk aplikasi di mana tabrakan harus (secara virtual) tidak mungkin.

Apakah pemrogram secara rutin menganggap sebagai "tidak mungkin" peristiwa lain yang dapat dan memang terjadi?

Ketika kita menulis data ke disk atau memori dan membacanya kembali, kita menerima begitu saja bahwa datanya benar. Kami mengandalkan koreksi kesalahan perangkat untuk mendeteksi adanya korupsi. Tetapi kemungkinan kesalahan yang tidak terdeteksi sebenarnya sekitar 2 -50 .

Tidakkah masuk akal untuk menerapkan standar yang serupa dengan UUID acak? Jika ya, Anda akan menemukan bahwa tabrakan "tidak mungkin" dimungkinkan dalam koleksi sekitar 100 miliar UUID acak (2 36,5 ).

Ini adalah angka astronomi, tetapi aplikasi seperti penagihan terperinci dalam sistem layanan kesehatan nasional, atau pencatatan data sensor frekuensi tinggi pada sejumlah besar perangkat pasti dapat mencapai batas ini. Jika Anda menulis Panduan Hitchhiker berikutnya untuk Galaxy, jangan mencoba untuk menetapkan UUID untuk setiap artikel!

erickson
sumber
Sebagai perbandingan, peluang memenangkan jackpot Powerball adalah 1 banding 300 juta, tetapi penjualan 10 hingga 20 juta tiket adalah tipikal. Intinya adalah bahwa banyak orang mendefinisikan "tidak mungkin" sebagai sesuatu yang kurang dari satu peluang dalam ratusan juta.
erickson
4

Karena sebagian besar jawaban berfokus pada teori, saya pikir saya dapat menambahkan sesuatu ke dalam diskusi dengan memberikan tes praktis yang saya lakukan. Dalam database saya, saya memiliki sekitar 4,5 juta UUID yang dihasilkan menggunakan Java 8 UUID.randomUUID (). Berikut ini adalah beberapa yang saya temukan:

c0f55f62 -b990-47bc-8caa-f42313669948

c0f55f62 -e81e-4253-8299-00b4322829d5

c0f55f62 -4979-4e87-8cd9-1c556894e2bb


b9ea2498-fb32-40ef-91ef-0ba 00060fe64

be87a209-2114-45b3-9d5a-86d 00060fe64


4a8a74a6-e972-4069-b480-b dea1177b21f

12fb4958-bee2-4c89-8cf8-e dea1177b21f

Jika itu benar-benar acak, kemungkinan memiliki UUID serupa semacam ini akan sangat rendah (lihat edit), karena kami hanya mempertimbangkan 4,5 juta entri. Jadi, meskipun fungsi ini baik, dalam hal tidak memiliki tabrakan, bagi saya itu tidak tampak bahwa baik karena akan dalam teori.

Edit :

Banyak orang tampaknya tidak memahami jawaban ini jadi saya akan menjelaskan maksud saya: Saya tahu bahwa kesamaannya "kecil" dan jauh dari tabrakan penuh. Namun, saya hanya ingin membandingkan UUID.randomUUID () Java dengan generator nomor acak yang sebenarnya, yang merupakan pertanyaan sebenarnya.

Dalam penghasil bilangan acak sejati, probabilitas kasus terakhir terjadi adalah sekitar = 0,007%. Karena itu, saya pikir kesimpulan saya benar.

Formula dijelaskan dalam artikel wiki ini en.wikipedia.org/wiki/Birthday_problem

André Pinheiro
sumber
6
Ini tidak benar. Kesamaan semacam ini akan muncul bahkan dengan generator nomor acak benar pada uuids 4,5M. Kesamaan antara UUID yang Anda berikan kecil dan jauh, oh begitu jauh dari tabrakan penuh.
user3711864
Saya sepenuhnya setuju dengan Anda bahwa kesamaan "kecil" dan jauh dari tabrakan penuh. Namun, saya hanya ingin membandingkan UUID.randomUUID () Java dengan generator nomor acak yang sebenarnya (ini adalah pertanyaannya). Dengan beberapa perhitungan kita dapat melihat bahwa, dalam generator angka acak yang benar, probabilitas kasus terakhir terjadi adalah sekitar 1-e ^ (- 4500000 ^ 2 / (2 * 36 ^ 11)) = 0,007% = 1 dalam 13rb Saya harus sangat beruntung :)
André Pinheiro
1
Dengan 4,5 juta item dan peluang 1 banding 13k, bukankah sebagian tabrakan seperti itu akan diperkirakan 346 kali?
Ben Lee
Tidak @BenLee, saya menghitung probabilitas peristiwa itu terjadi mengingat kami memiliki 4,5 juta item. Ini bukan peluang 1 dalam 13k yang terjadi untuk setiap item. Formula yang saya gunakan dapat ditemukan di artikel wiki ini en.wikipedia.org/wiki/Birthday_problem
André Pinheiro
2
Apa harapanmu? Serupa tidak sama, bukan?
Koray Tugay
3

Saya bermain lotere tahun lalu, dan saya tidak pernah menang .... tetapi tampaknya lotere memiliki pemenang ...

doc: http://tools.ietf.org/html/rfc4122

Tipe 1: tidak diterapkan. tabrakan dimungkinkan jika uuid dihasilkan pada saat yang sama. impl dapat disinkronkan secara artifisial untuk mem-bypass masalah ini.

Tipe 2: tidak pernah melihat implementasi.

Tipe 3: hash md5: kemungkinan tabrakan (128 bit-2 byte teknis)

Tipe 4: acak: kemungkinan tabrakan (seperti lotere). perhatikan bahwa jdk6 impl tidak menggunakan "benar" secure random karena algoritma PRNG tidak dipilih oleh pengembang dan Anda dapat memaksa sistem untuk menggunakan algo PRNG "buruk". Jadi UUID Anda bisa ditebak.

Tipe 5: sha1 hash: tidak diimplementasikan: kemungkinan collision (160 bit-2 byte teknis)

Giher
sumber
4
Kemungkinan memenangkan lotere mungkin satu dari 10 atau 100 juta (10 ^ 7 atau 10 ^ 8) atau sesuatu seperti itu. Probabilitas tabrakan dengan angka acak 128 bit adalah 3,4 * 10 ^ 28. Beri aku tiket lotere kapan saja!
Stephen C
0

Kami telah menggunakan UUID acak Java dalam aplikasi kami selama lebih dari satu tahun dan itu sangat luas. Tapi kami tidak pernah menemukan tabrakan.

Afsar
sumber