Apakah tabrakan GUID mungkin?

128

Saya sedang mengerjakan basis data di SQL Server 2000 yang menggunakan GUID untuk setiap pengguna yang menggunakan aplikasi yang terkait dengannya. Entah bagaimana, dua pengguna berakhir dengan GUID yang sama. Saya tahu bahwa microsoft menggunakan algoritme untuk menghasilkan GUID acak yang memiliki peluang sangat rendah untuk menyebabkan kolusi, tetapi apakah tabrakan masih dimungkinkan?

Jason Baker
sumber
11
Semua orang mengatakan tidak adalah salah. Saya telah bertabrakan 1 UniqueIdentifier dengan set data kurang dari setengah juta catatan, MSSQL 2008 R2
Behrooz
2
@Behrooz Yikes. Bukan tidak mungkin berkat paradoks ulang tahun teman kita, tetapi masih sangat sial dengan GUID v4 yang sepenuhnya acak. Mungkin Anda menggunakan strategi pembuatan GUID yang lebih lemah?
Craig Ringer
6
@Behrooz Wow. Itu keberuntungan yang mengejutkan.
Craig Ringer
6
@ Behrooz ini mungkin nomor acak palsu yang rusak yang digunakan dalam MSSQL (saya tidak akan terkejut jika mereka memiliki seed 32-bit di generator mereka atau sejenisnya yang diberikan kualitas perangkat lunak mereka). Matematika tidak berbohong. Kemungkinan ini sangat kecil sehingga Anda bisa menjadi 99,999999999999 (dan banyak dari 9 setelah)% sehingga generator panduan MSSQL rusak (atau mungkin generator acak palsu yang digunakan untuk menghasilkan GUID) atau Anda membuat kesalahan.
Alex
2
Senang bagaimana pada saat yang tepat ini, baik pertanyaan dan jawaban yang dipilih memiliki skor 128. Kebetulan? 🤔
Caio Cunha

Jawaban:

127

Pada dasarnya tidak. Saya pikir seseorang pergi mucking dengan database Anda. Bergantung pada GUID versi yang Anda gunakan nilainya unik (untuk hal-hal seperti GUID versi 1), atau unik dan tidak dapat diprediksi (untuk hal-hal seperti GUID versi 4). Implementasi SQL Server untuk fungsi NEWID () mereka tampaknya menggunakan nomor acak 128-bit, sehingga Anda tidak akan mendapatkan tabrakan.

Untuk kemungkinan tabrakan 1%, Anda harus menghasilkan sekitar 2.600.000.000.000.000.000.000 GUID.

Tom Ritter
sumber
3
Itulah yang saya pikirkan, tetapi saya hanya ingin memastikan saya tidak bisa mengesampingkan hal itu. Anda tidak pernah tahu jenis bug aneh apa yang mungkin muncul dalam perangkat lunak berusia 8 tahun. :)
Jason Baker
6
Sebenarnya itu tidak benar lagi. Memang benar untuk GUID v1, tetapi tidak untuk yang v4 saat ini. Lihat en.wikipedia.org/wiki/Globally_Unique_Identifier#Algorithm untuk info lebih lanjut.
Greg Beech
97
Tidak memilih karena, pada prinsipnya (dalam bentuk paling mentah), Anda salah mengatakan "tidak" pada pertanyaan "Apakah tabrakan GUID mungkin?". Itu sangat mungkin. Kemungkinannya kecil, tapi itu mungkin. Saya benci kedengarannya terlalu berlebihan - tetapi SO adalah tentang singkat dan akurat.
13
masukkan "selesaikan [1-exp [- (n ^ 2 / (2 * 2 ^ 128))]> 0,01, n]" ke wolfram alpha untuk mendapatkan hasil sebesar 1% ... Ketahuilah bahwa sementara jumlah ini tampaknya besar dalam konteks SATU aplikasi, tentu tidak besar untuk seluruh dunia. Jika setiap komputer di bumi akan menghasilkan GUID yang benar, mereka akan menyebabkan tabrakan dengan probabilitas 1% dalam waktu sekitar satu detik, dengan asumsi mereka dapat menghasilkan GUID setiap nanosecond (yang mungkin cukup realistis hari ini). Jadi, jika Anda menggunakan GUID untuk ID basis data Anda, maka mereka unik. GUID untuk setiap perhitungan yang dilakukan di bumi, akan berbenturan segera.
lukisan
11
Mengatakan 'Tidak' itu tidak mungkin, dan kemudian mengatakan bahwa ada peluang 1% untuk mendapatkan tabrakan ketika jumlah tertentu dihasilkan, adalah konflik langsung. Respons yang benar harus secara teoritis - ya, tabrakan dapat terjadi secara acak. Namun, kemungkinan tabrakan secara statistik lebih kecil dari asteroid yang menghantam Bumi, memantul dari Bumi dan memantul dari Bulan untuk menghantam Bumi untuk kedua kalinya, dalam satu jam berikutnya.
Baaleos
112

Pada dasarnya mereka tidak mungkin! , kemungkinannya sangat rendah .

Tapi ... Saya satu-satunya orang di dunia yang saya kenal, yang pernah mengalami tabrakan GUID (ya!).

Dan saya yakin akan hal itu, dan itu bukan kesalahan.

Bagaimana itu terjadi, dalam aplikasi kecil yang berjalan di Pocket PC, pada akhir operasi, perintah yang menghasilkan GUID harus dikeluarkan. Perintah setelah dieksekusi di server itu disimpan dalam tabel perintah di server bersama dengan tanggal eksekusi. Suatu hari ketika saya sedang debug saya mengeluarkan perintah modul (dengan GUID yang baru dibuat terpasang) dan tidak ada yang terjadi. Saya melakukannya lagi (dengan panduan yang sama, karena panduan hanya dihasilkan sekali di awal operasi), dan lagi, dan tidak ada, akhirnya mencoba mencari tahu mengapa perintah tidak dijalankan, saya memeriksa tabel perintah, dan GUID yang sama dengan yang sekarang dimasukkan 3 minggu yang lalu. Tidak percaya ini, saya mengembalikan database dari cadangan 2 minggu, dan panduan ada di sana. Memeriksa kode, panduan baru itu dibuat tanpa keraguan tentangnya.

Sunting: ada beberapa faktor yang bisa sangat meningkatkan peluang terjadinya hal ini, aplikasi sedang berjalan di emulator PocketPC, dan emulator memiliki fitur save state, yang berarti bahwa setiap kali keadaan dipulihkan, waktu setempat dipulihkan juga waktu setempat dan panduan didasarkan pada timer internal .... juga algoritma yang menghasilkan panduan untuk kerangka kerja kompak mungkin kurang lengkap daripada misalnya COM satu ...

Pop Catalin
sumber
38
Terpilih. Simpan status & ulangan benar-benar akan menghasilkan duplikat pedoman.
Joshua
35
Kemungkinan yang terjadi adalah ini adalah implementasi GUID yang "buruk". The teoritis peluang yang sangat rendah, namun pada Pocket PC ?? Siapa yang mengatakan bahwa mereka tidak mengambil jalan pintas yang menabrak peluang itu ke dalam kategori "tidak mungkin, tetapi mungkin".
Dave Dopson
9
Hanya karena sesuatu memiliki probabilitas yang sangat rendah untuk terjadi bukan berarti itu tidak akan terjadi.
Renan
3
Seperti yang saya katakan di atas kemungkinan yang semakin kecil sehingga aman untuk berasumsi bahwa Anda membuat kesalahan atau MSSQL menggunakan PRNG yang rusak ( en.wikipedia.org/wiki/Pseudorandom_number_generator ). Misalnya, kemungkinan PRNG ini diinisialisasi dengan benih berukuran kecil. PRNG yang rusak tidak jarang (lihat schneier.com/paper-prngs.html ) - misalnya satu cacat baru-baru ini ditemukan di Android SDK - android-developers.blogspot.com/2013/08/… + usenix.org/conference/woot14 / workshop-program / presentasi / ...
Alex
2
@Alex, kesalahannya adalah "Save State and Restore" dari Emulator, yang mengembalikan seluruh gambar emulator termasuk jam emulator. Jadi setelah ribuan operasi Pemulihan lebih dari satu tahun, satu tabrakan panduan dihasilkan. Anda benar ada kesalahan!
Pop Catalin
34

Secara teori mereka mungkin, tetapi dengan angka 3,4E38 kemungkinan, jika Anda membuat puluhan triliun GUID dalam setahun kemungkinan memiliki satu duplikat adalah 0,00000000006 ( Sumber ).

Jika dua pengguna berakhir dengan GUID yang sama, saya berani bertaruh bahwa ada bug dalam program yang menyebabkan data disalin atau dibagikan.

Ben Hoffstein
sumber
"tetapi dengan 3,4E38 kemungkinan angka" - no. Dua GUID yang dihasilkan hampir bersamaan pada mesin yang sama akan berakhir dengan GUID yang sangat mirip.
Kirk Strauser
4
Itu akan tergantung pada bagaimana GUID dihasilkan, dan beberapa implementasi berdasarkan waktu CPU atau milidetik akan (mudah-mudahan) menjelaskan perhitungan apa pun yang didasarkan pada sehingga dua GUID yang dihasilkan dari milidetik terpisah akan memiliki perbedaan besar.
Dalin Seivewright
4
Dengan lebih dari 1 prosesor pada mesin, jika panduan didasarkan pada waktu dan alamat mac maka masing-masing inti dapat mengeluarkan panduan yang sama pada saat yang bersamaan.
AndyM
12
Saya cukup yakin implementasi GUID yang baik tidak akan terjadi
Guillaume86
1
@ MatthewLock Paradoks ulang tahun tercakup dalam sumber. Periksa tautannya.
Zero3
21

Pertama mari kita lihat peluang tabrakan dua GUID. Bukan, seperti jawaban lain nyatakan, 1 dalam 2 ^ 128 (10 ^ 38) karena paradoks ulang tahun , yang berarti bahwa untuk peluang 50% dua GUID bertabrakan probabilitas sebenarnya 1 dalam 2 ^ 64 (10 ^ 19) yang jauh lebih kecil. Namun, ini masih merupakan angka yang sangat besar, dan karena itu kemungkinan tabrakan dengan asumsi Anda menggunakan jumlah GUID yang masuk akal adalah rendah.

Perhatikan juga bahwa GUID tidak mengandung stempel waktu atau alamat MAC seperti yang tampaknya dipercaya banyak orang. Ini berlaku untuk GUID v1 tetapi sekarang GUID v4 digunakan, yang hanya merupakan angka pseudo-acak yang berarti bahwa kemungkinan tabrakan bisa dibilang lebih tinggi karena mereka tidak lagi unik untuk waktu dan mesin.

Jadi intinya jawabannya adalah ya, tabrakan itu mungkin. Tetapi mereka sangat tidak mungkin.

Sunting: diperbaiki untuk mengatakan 2 ^ 64

Greg Beech
sumber
2
Sementara saya setuju dengan semua fakta Anda, berhati-hatilah dengan matematika Anda. Untuk mengatakan bahwa Anda memiliki peluang 1 dalam 10 ^ 19 dari dua GUID yang bertabrakan tergantung pada berapa banyak GUID yang ada di set. Untuk itu Anda perlu ~ 2 ^ 32 GUID, jadi di hampir semua skenario dunia nyata, peluangnya jauh lebih rendah.
DocMax
1
Anda memiliki kesalahan ketik 1 in 10^64 (10^19), yang saya pikir seharusnya 1 in 2^64 (10^19). Saya juga sangat bingung bagaimana Anda berpikir paradoks ulang tahun hanya berlaku untuk 2 angka. Saya berasumsi Anda telah melihat en.wikipedia.org/wiki/Birthday_paradox . Tabel menunjukkan berapa banyak panduan yang Anda butuhkan untuk probabilitas duplikat yang diberikan. Dari tabel itu, probabilitas 1 dalam 10 ^ 18 membutuhkan panduan 2.6 * 10 ^ 10, bukan sesuatu yang mendekati hanya dua GUID.
Tony Lee
Satu point - v1 guids masih digunakan secara luas, dan bergantung pada alamat MAC, khususnya dalam database karena mereka memiliki karakteristik yang diinginkan. Lihat UuidCreateSequential dan itu pembungkus SQL Server NewSequentialID ( msdn.microsoft.com/en-us/library/windows/desktop/… ).
EBarr
18

Kemungkinan dua GUID acak bertabrakan (~ 1 dalam 10 ^ 38) lebih rendah daripada kemungkinan tidak mendeteksi paket TCP / IP yang rusak (~ 1 dalam 10 ^ 10). http://wwwse.inf.tu-dresden.de/data/courses/SE1/SE1-2004-lec12.pdf , halaman 11. Ini juga berlaku untuk drive disk, drive cd, dll ...

GUID secara statistik unik dan data yang Anda baca dari db hanya benar secara statistik.

Tony Lee
sumber
Apakah Anda yakin saya tidak mungkin melengkapi jaringan saya sehingga kurang dari 1 dalam 10 ^ 28 paket rusak?
Joshua
13

Saya akan menganggap pisau cukur Occam sebagai panduan yang baik dalam kasus ini. Sangat tidak mungkin Anda memiliki tabrakan GUID. Kemungkinan besar Anda memiliki bug, atau seseorang mengacaukan data Anda.

Jason Jackson
sumber
1
Sebenarnya dalam situasi ini pisau cukur Occam sama sekali bukan panduan yang bagus! Razor Occam mengatakan bahwa kasus dengan asumsi paling tidak mungkin benar. Dalam situasi ini kasus tabrakan GUID sebenarnya jauh lebih sederhana, tetapi Occam's Razor tidak berlaku untuk situasi seperti ini di mana kita sudah tahu bahwa salah satu kasus sangat tidak mungkin.
lockstock
11

Lihat artikel Wikipedia Global Identifier . Ada beberapa cara untuk menghasilkan GUID. Rupanya cara lama (?) Menggunakan alamat Mac, cap waktu ke unit yang sangat pendek dan penghitung unik (untuk mengelola generasi cepat di komputer yang sama), sehingga membuat duplikat mereka hampir mustahil. Tetapi GUID ini dijatuhkan karena bisa digunakan untuk melacak pengguna ...

Saya tidak yakin dengan algoritma baru yang digunakan oleh Microsoft (artikel mengatakan urutan GUID dapat diprediksi, sepertinya mereka tidak lagi menggunakan cap waktu? Artikel Microsoft yang ditautkan di atas mengatakan sesuatu yang lain ...).

Sekarang, GUID dirancang dengan hati-hati, dengan nama, unik secara global, jadi saya akan mengambil risiko itu tidak mungkin, atau kemungkinan sangat sangat sangat rendah. Saya akan mencari di tempat lain.

PhiLho
sumber
9

Dua mesin Win95 yang memiliki kartu ethernet dengan alamat MAC duplikat akan mengeluarkan GUIDS duplikat dalam kondisi yang dikontrol dengan ketat, terutama jika, misalnya, listrik padam di gedung dan mereka berdua boot pada waktu yang sama persis.

Joshua
sumber
Apakah umum untuk dua mesin berbeda memiliki alamat MAC ethernet yang sama?
Dave Lucre
@DaveLucre: Tidak, tetapi insiden telah dicatat.
Joshua
Saya benar-benar ingin tahu bagaimana ini terjadi. Apakah lebih mungkin dengan VM yang secara acak menghasilkan MAC untuk setiap NIC? Saya belum pernah mendengar tentang NIC fisik yang diproduksi dengan duplikat MAC! Jenis melempar kunci pas besar dalam karya jika itu mungkin!
Dave Lucre
Wow! Terima kasih atas tautannya. Benar-benar kekacauan besar!
Dave Lucre
@ DaveLucre Saya telah menggunakan beberapa NIC USB yang sangat murah di mana SEMUA dari mereka diproduksi dengan MAC yang sama. Tapi tentu saja, itu tidak ada hubungannya dengan matematika dari keacakan, dan semuanya ada hubungannya dengan kemalasan pabrikan.
rudolfbyker
5

Saya akan mengawali ini dengan "Saya bukan orang yang berjejaring, jadi saya bisa membuat kalimat yang sama sekali tidak jelas berikut.".

Ketika saya bekerja di Illinois State University, kami memiliki dua desktop Dell, dipesan pada waktu yang berbeda. Kami menempatkan yang pertama di jaringan, tetapi ketika kami mencoba menempatkan yang kedua di jaringan kami mulai menerima kesalahan gila. Setelah banyak pemecahan masalah, ditentukan bahwa kedua mesin memproduksi GUID yang sama (saya tidak yakin untuk apa, tetapi itu membuat keduanya tidak dapat digunakan di jaringan). Dell benar-benar mengganti kedua mesin sebagai cacat.

John Kraft
sumber
3
Khususnya GUID. Itu ada hubungannya dengan GUID yang dihasilkan oleh mesin ketika mereka bergabung dengan jaringan. Butuh beberapa minggu bagi Dell untuk mengganti mesin karena mereka mengatakan tidak mungkin bagi GUID untuk menjadi sama. Kami dapat mereproduksi masalah, Dell mengambil kembali mesin, dan mampu menghasilkan hasil yang sama di jaringan mereka. Mereka akhirnya mengganti kedua mesin. Seperti yang saya katakan, saya bukan orang yang berjejaring, tapi saya secara khusus ingat itu adalah masalah dengan GUID.
John Kraft
5

Saya tahu orang-orang menyukai jawaban merasa-baik bahwa GUID ajaib dan dijamin unik, tetapi dalam kenyataannya, sebagian besar GUID hanya angka acak 121-bit (tujuh bit dihabiskan untuk memformat). Jika Anda tidak akan merasa nyaman menggunakan nomor acak besar, maka Anda seharusnya tidak merasa nyaman menggunakan GUID.

Rick Yorgason
sumber
11
Juga merekomendasikan Anda untuk tidak menggunakan jaringan. Atau komputer. Bit paritas hanya bisa melakukan banyak hal!
Rushyo
Kamu salah paham. Ada dua hal yang saya coba katakan dalam posting ini: 1) Jika Anda memerlukan nomor acak besar, gunakan nomor acak besar. Menggunakan GUID sebagai angka acak besar tidak perlu menyesatkan. (2)
Rick Yorgason
4
Yang saya sadari sepenuhnya. Anda menyatakan "jika Anda tidak akan merasa nyaman menggunakan nomor acak besar." tetapi GUID sangat unik sehingga Anda akan menemukan bahwa hampir semua hal lain di komputer lebih acak, bahkan operasi yang Anda anggap remeh. Ada lebih banyak kemungkinan kesalahan memori aneh akan memecah kolom identitas Anda daripada tabrakan GUID (benar) akan terjadi. Anda seharusnya tidak merasa 'tidak nyaman' tentang mereka. Jika mereka tidak ideal untuk skenario maka baik-baik saja - tetapi mereka tidak perlu perhatian khusus.
Rushyo
3
Saya kira ini tidak menuju ke mana-mana tetapi apa yang orang coba jelaskan kepada Anda adalah bahwa mekanisme pendeteksian kesalahan pada perangkat keras umum seperti kartu jaringan atau hard drive menggunakan algoritma yang memiliki peluang lebih besar untuk tidak mendeteksi kesalahan daripada Anda mendapatkan tabrakan GUID, jadi jika Anda mengandalkan ini, Anda juga bisa mengandalkan GUID
Guillaume86
1
@ Rick, tergantung seberapa besar nomor Anda. Jelas tidak dengan int 4 byte atau bigint 8 byte. GUID = 16 byte, jadi Anda akan membutuhkan implementasi 16 byte angka besar kustom untuk mencapai 2 ^ 128 kemungkinan kombinasi yang sama. Jadi secara umum, jika menggunakan 'normal' int atau nomor acak bigint, kesempatan tabrakan dengan GUID adalah rendah (meninggalkan keluar pertimbangan algo acak untuk masing-masing).
Wim Hollebrandse
3

Bisakah kode yang digunakan untuk menghasilkan GUID memiliki bug di dalamnya? Ya tentu saja bisa. Tetapi jawabannya sama dengan bug kompiler - kode Anda sendiri adalah urutan besarnya lebih cenderung menjadi buggy, jadi lihat dulu dulu.

Mark tebusan
sumber
2

Tentu saja mungkin .... Kemungkinan? Tidak mungkin, tetapi itu mungkin.

Ingat, mesin yang sama menghasilkan setiap GUID (server), jadi banyak "keacakan" yang didasarkan pada informasi spesifik mesin hilang.

FlySwat
sumber
1

Hanya untuk menyeringai, coba skrip berikut ... (berfungsi pada SQL 2005, tidak yakin tentang 2000)

declare @table table
(
    column1 uniqueidentifier default (newid()),
    column2 int,
    column3 datetime default (getdate())
)

declare @counter int

set @counter = 1

while @counter <= 10000
begin
    insert into @table (column2) values (@counter)
    set @counter = @counter + 1
end

select * from @table

select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2

Menjalankan ini berulang kali (membutuhkan waktu kurang dari satu detik) menghasilkan rentang yang cukup luas dari pemilihan pertama, bahkan dengan jeda waktu yang sangat pendek. Sejauh ini pemilihan kedua belum menghasilkan apa-apa.

GalacticCowboy
sumber
1
Anda memerlukan 15 angka nol lagi di akhir konter untuk memiliki peluang duplikat 50%. Tapi, demi Pete, jangan lakukan itu!
Jim Birchall
0

Tidak mungkin jika pengguna memiliki mesin yang berbeda dengan kartu jaringan, dan bahkan jika itu masih merupakan risiko yang hampir secara teoritis marjinal.

Secara pribadi saya akan mencari di tempat lain karena lebih mungkin bug daripada bentrokan GUID ...

Memberikan tentu saja Anda tidak memotong bit GUID untuk membuatnya lebih pendek.

Richard Harrison
sumber
GUID akan dibuat di Server, sehingga kartu jaringan pengguna tidak ikut bermain.
Tom Ritter
0

Tentu itu mungkin, dan bahkan mungkin. Ini tidak seperti setiap GUID berada di bagian acak dari ruang angka yang mungkin. Jika dua utas berusaha menghasilkan satu secara bersamaan, kecuali beberapa fungsi GUID terpusat dengan semafor di sekitarnya, mereka dapat berakhir dengan nilai yang sama.

Kirk Strauser
sumber
0

Sangat tidak mungkin bahwa Anda akan mengalami tabrakan GUID jika Anda menghasilkan mereka melalui sesuatu seperti NEWID()fungsi di SQL Server (meskipun tentu saja mungkin, karena jawaban lain telah menekankan). Satu hal yang belum mereka tunjukkan adalah kemungkinan besar Anda akan mengalami tabrakan jika Anda membuat GUID di JavaScript pada peramban di alam. Tidak hanya kadang-kadang ada masalah di RNG di browser yang berbeda, tetapi saya juga mengalami masalah di mana laba-laba Google tampaknya men-cache hasil fungsi seperti itu, dan akhirnya berulang kali meneruskan GUID yang sama ke sistem kami.

Lihat berbagai jawaban di sini untuk perincian lebih lanjut:

Tabrakan saat membuat UUID dalam JavaScript?

Ken Smith
sumber