Apakah aman untuk mengasumsikan GUID akan selalu unik?

123

Saya tahu ada kemungkinan satu menit dari bentrokan tetapi jika saya menghasilkan kumpulan 1000 GUID (misalnya), apakah aman untuk mengasumsikan semuanya unik untuk menyimpan pengujian masing-masing?

Pertanyaan bonus

Cara optimal untuk menguji GUID untuk keunikan? Filter Bloom mungkin?

math unique guid probability collision Tom Savage
sumber
2
kemungkinan duplikat Apakah GUID unik 100% setiap saat?
ChrisF
29
Tidak, jika kita semua terus menekan tombol muat ulang di situs ini: wasteaguid.info
mipadi
12
Saya menyalahkan semua bug saya pada tabrakan GUID. Ini harus terjadi suatu saat kan?
Michael
8
Kemungkinan besar hiu dengan warna bermotif kotak-kotak yang indah akan jatuh dari langit dan menghancurkan komputer Anda hingga berkeping-keping, jadi saya akan menyampaikan bahwa mengambil tindakan pencegahan terhadap hal itu adalah alokasi sumber daya yang lebih tepat sebagai bagian dari pengurangan risiko Anda secara keseluruhan. rencana.
David Gladfelter
4
@mipadi: tautan bagus! Saya hanya bisa membayangkan beberapa pengembang di suatu tempat merengek "Guuuuys! Berhenti menyia-nyiakan GUID! Aku butuh itu!"
FrustratedWithFormsDesigner

Jawaban:

360

Ya kamu bisa. Karena GUID memiliki panjang 128 bit, memang ada kemungkinan kecil terjadinya bentrokan — tetapi kata "menit" tidak cukup kuat. Ada begitu banyak GUID sehingga jika Anda menghasilkan beberapa triliun di antaranya secara acak, Anda masih lebih mungkin terkena meteorit daripada hanya mengalami satu tabrakan (dari Wikipedia ). Dan jika Anda tidak membuatnya secara acak, tetapi misalnya menggunakan algoritma alamat-MAC-dan-cap waktu, maka mereka juga akan menjadi unik, karena alamat MAC unik di antara komputer dan stempel waktu unik di komputer Anda. komputer.

Sunting 1: Untuk menjawab pertanyaan bonus Anda, cara optimal untuk menguji sekumpulan GUID untuk keunikannya adalah dengan menganggap bahwa semuanya unik. Mengapa? Karena, dengan jumlah GUID yang Anda hasilkan, kemungkinan tabrakan GUID lebih kecil daripada kemungkinan sinar kosmik membalik sedikit di memori komputer Anda dan mengacaukan jawaban yang diberikan oleh algoritme "akurat" yang Anda pedulikan. untuk berlari. (Lihat jawaban StackOverflow ini untuk matematika.)

Ada banyak sekali GUID di luar sana. Mengutip Hitchhiker's Guide to the Galaxy dari Douglas Adams :

"Luar angkasa," katanya, "itu besar. Benar-benar besar. Anda tidak akan percaya betapa besarnya sangat luar biasa besarnya. Maksud saya, Anda mungkin berpikir itu masih jauh dari jalan menuju ahli kimia, tapi itu hanya kacang ke luar angkasa , dengarkan… "

Dan karena ada sekitar 7 × 10 22 bintang di alam semesta , dan sedikit di bawah 2 128 GUID, maka ada sekitar 4,86 ​​× 10 15 —hampir lima kuadriliun —GUID untuk setiap bintang. Jika setiap bintang memiliki dunia dengan populasi yang berkembang pesat seperti kita, maka di sekitar setiap bintang, setiap manusia atau alien yang pernah hidup berhak atas lebih dari empat puluh lima ribu GUID. Untuk setiap orang dalam sejarah di setiap bintang di alam semesta. Ruang GUID berada pada tingkat yang sama dengan ukuran seluruh alam semesta. Anda tidak perlu khawatir.

( Edit 2: Berkaca pada ini: wow Aku tidak menyadari. Diriku sendiri apa yang dimaksud Ruang GUID ini incomprehensibly besar aku semacam kagum itu...)

Antal Spector-Zabusky
sumber
1
Juga, WolframAlpha melaporkan bahwa, untuk setiap sel di setiap orang yang pernah hidup, ada 36 triliun UUID. Anda memiliki tentang 10^14sel dalam tubuh Anda, dan 106,5 miliar orang pernah hidup. Atau, 2.385 * 10^23UUID untuk setiap sen utang publik AS.
baru123456
5
Meskipun jumlahnya masih tinggi, kemungkinan tabrakan GUID lebih dari 50% pada 2 ^ 64 GUID.
NullUserException
1
Pada 2 ^ 64 GUID, ini akan mengurangi angka menjadi kurang dari satu (0,00026) per bintang di alam semesta dan 2 * 10 ^ (- 15) untuk setiap manusia atau alien yang pernah hidup. Ini masih memungkinkan lebih dari 170 juta GUID untuk setiap manusia yang pernah hidup, jadi saya pikir kita masih baik-baik saja.
NullUserException
12
Perlu dicatat bahwa tabrakan GUID juga hanya menjadi masalah jika berada di ruang bisnis yang sama. GUID yang saya gunakan untuk mengidentifikasi komponen dalam perangkat lunak bisa sama dengan GUID yang Anda gunakan dalam baris database di aplikasi Anda sendiri tanpa menyebabkan masalah
James Thorpe
1
Fakta bahwa ada 2 ^ 128 GUIDS tidaklah relevan, dan Anda tidak "masih baik" pada kemungkinan tabrakan 50%, Anda bahkan tidak pandai dalam 0,0000001%
BlackTigerX
40

Jawaban singkatnya: untuk tujuan praktis, ya.

Namun, Anda harus mempertimbangkan paradoks ulang tahun!

Saya telah menghitung beberapa probabilitas tabrakan yang representatif. Dengan UUID 122-bit seperti yang ditentukan dalam artikel Wikipedia , kemungkinan tabrakan adalah 1/2 jika Anda menghasilkan setidaknya2.71492e18 UUID. Dengan 10 ^ 19 UUID, probabilitasnya adalah 0,999918. Dengan 10 ^ 17 UUIDs, 0,000939953.

Beberapa angka untuk perbandingan dapat ditemukan di Wikipedia. Jadi, Anda dapat dengan aman menetapkan UUID untuk setiap manusia yang pernah hidup, setiap galaksi di alam semesta yang dapat diamati, setiap ikan di lautan, dan setiap individu semut di Bumi. Namun , tabrakan hampir pasti jika Anda menghasilkan UUID untuk setiap transistor yang diproduksi manusia dalam satu tahun, setiap serangga di Bumi, setiap butir pasir di Bumi, setiap bintang di alam semesta yang dapat diamati, atau apa pun yang lebih besar.

Jika Anda menghasilkan 1 miliar UUID per detik, itu akan memakan waktu sekitar 36 tahun untuk mendapatkan probabilitas tabrakan sebesar 10%.

Akhirnya, mungkin akan ada tabrakan di antara perangkat UUID yang dihasilkan selama sejarah manusia. Namun, kemungkinan bahwa UUID yang bertabrakan akan digunakan untuk tujuan yang sama semakin kecil, jadi tidak ada masalah dalam praktiknya.

Siput mekanis
sumber
13
Ini adalah bagaimana alam semesta berakhir ... Beberapa programmer hanya menganggap GUID mereka akan selalu unik untuk mega Death Star mereka ...
pkr298
Karena UUID didasarkan pada data non-acak, 36 tahun - Anda hanya perlu mengkhawatirkan setiap milidetik satu per satu.
mjaggard
UUID @mjaggard didasarkan pada data acak. Jenis modern apa pun.
Trejkaz
8

Analisis kemungkinan tabrakan tersedia di Wikipedia: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Seperti yang disebutkan di tautan, ini akan dipengaruhi oleh properti generator bilangan acak.

Ada juga kemungkinan bug dalam kode generator GUID; sementara kemungkinannya rendah, mereka mungkin lebih tinggi dari kemungkinan tabrakan berdasarkan matematika.

Filter Bloom mungkin cocok; itu dapat dengan cepat memberi tahu Anda jika GUID itu unik, tetapi ada kemungkinan indikasi benturan yang salah. Metode alternatif jika Anda menguji kelompok pada satu waktu adalah dengan mengurutkan kelompok dan membandingkan setiap elemen yang berurutan.

Mark Ransom
sumber
5

Secara umum, ya aman untuk diasumsikan.

Jika generator GUID Anda benar-benar acak, kemungkinan bentrokan dalam 1000 GUID sangatlah kecil.

Tentu saja, itu mengasumsikan generator GUID yang baik. Jadi pertanyaannya sebenarnya tentang seberapa besar Anda mempercayai alat yang Anda gunakan untuk menghasilkan GUID dan apakah alat tersebut memiliki pengujiannya sendiri?

Haacked
sumber
0

Meskipun tabrakan mungkin terjadi, sangat kecil kemungkinannya. (Matematika di sini .) Aman untuk mengasumsikan bahwa mereka sebenarnya berbeda.

VeeArr
sumber