Dapat diterima untuk bergantung pada int acak yang unik?

Saya telah mengimplementasikan protokol jaringan, dan saya membutuhkan paket untuk memiliki pengidentifikasi unik. Sejauh ini, saya baru saja menghasilkan bilangan bulat 32-bit acak, dan dengan asumsi bahwa secara astronomis tidak mungkin akan ada tabrakan selama umur suatu program / koneksi. Apakah ini secara umum dianggap sebagai praktik yang dapat diterima dalam kode produksi, atau haruskah seseorang membuat sistem yang lebih kompleks untuk mencegah tabrakan?

Waspadai paradoks ulang tahun .

Misalkan Anda menghasilkan urutan nilai acak (seragam, independen) dari satu set ukuran N (N = 2 ^ 32 dalam kasus Anda).

Kemudian, aturan praktis untuk paradoks ulang tahun menyatakan bahwa setelah Anda menghasilkan nilai-nilai sqrt (N), setidaknya ada kemungkinan 50% bahwa tabrakan telah terjadi, yaitu, bahwa setidaknya ada dua nilai identik di urutan yang dihasilkan.

Untuk N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Jadi setelah Anda menghasilkan sekitar 65k pengidentifikasi, kemungkinan besar keduanya bertabrakan daripada tidak! Jika Anda menghasilkan pengidentifikasi per detik, ini akan terjadi dalam waktu kurang dari sehari; Tak perlu dikatakan, banyak protokol jaringan beroperasi jauh lebih cepat dari itu.

Secara luas dianggap dapat diterima untuk mengandalkan angka acak yang unik jika angka-angka itu memiliki bit yang cukup. Ada protokol kriptografi di mana pengulangan nomor acak akan merusak seluruh keamanan. Dan selama tidak ada kerentanan serius dalam generator angka acak yang digunakan, itu tidak menjadi masalah.

Salah satu algoritma untuk menghasilkan UUID akan secara efektif menghasilkan ID yang terdiri dari 122 bit acak dan menganggapnya unik. Dan dua dari algoritma lainnya bergantung pada nilai hash yang terpotong menjadi 122 bit yang unik, yang memiliki risiko tabrakan yang kira-kira sama.

Jadi ada standar yang mengandalkan 122 bit yang cukup untuk membuat ID acak unik, tetapi 32 bit jelas tidak cukup. Dengan ID 32 bit, hanya dibutuhkan sekitar 2¹⁶ ID sebelum risiko tabrakan mencapai 50% karena dengan 2¹⁶ ID akan ada hampir 2 ³¹ pasangan yang masing-masing bisa berupa tabrakan.

Bahkan 122 bit kurang dari yang saya sarankan dalam desain baru. Jika mengikuti beberapa standardisasi penting bagi Anda, maka gunakan UUID. Kalau tidak gunakan sesuatu yang lebih besar dari 122 bit.

Fungsi hash SHA1 dengan output 160 bit tidak lagi dianggap aman yang sebagian karena 160 bit tidak cukup untuk menjamin keunikan output. Fungsi hash modern memiliki output dari 224 hingga 512 bit. ID yang dihasilkan secara acak harus bertujuan untuk ukuran yang sama untuk memastikan keunikan dengan margin keamanan yang baik.

Saya akan menyebut praktik buruk ini. Angka acak menghasilkan tidak membuat angka unik, mereka hanya membuat angka acak. Distribusi acak kemungkinan akan menyertakan beberapa duplikat. Anda dapat membuat keadaan ini tidak mungkin diterima dengan menambahkan elemen waktu. Jika Anda mendapatkan waktu saat ini dari jam sistem dalam milidetik. Sesuatu seperti ini:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Akan jauh. Jelas untuk benar-benar menjamin keunikan yang Anda butuhkan untuk menggunakan UUID / GUID. Tetapi mereka bisa mahal untuk menghasilkan, di atas kemungkinan cukup, karena satu-satunya kemungkinan tumpang tindih, adalah jika menghasilkan acak memiliki duplikat dalam milidetik yang sama.

Itu tergantung pada probabilitas kegagalan dan konsekuensi dari kegagalan.

Saya ingat perdebatan antara orang-orang perangkat lunak dan perangkat keras di mana orang-orang perangkat keras menganggap bahwa algoritma dengan probabilitas kecil hasil yang salah (sekitar 1 kegagalan dalam 100 tahun) dapat diterima, dan orang-orang perangkat lunak berpikir ini adalah kutukan. Ternyata orang-orang perangkat keras secara rutin menghitung tingkat kegagalan yang diharapkan, dan sangat terbiasa dengan gagasan bahwa semuanya akan memberikan jawaban yang salah sesekali, misalnya karena gangguan yang disebabkan oleh sinar kosmik; mereka merasa aneh bahwa orang-orang perangkat lunak mengharapkan keandalan 100%.

Tentu, Anda memiliki probabilitas yang sangat rendah dari dua bilangan bulat 32-bit acak yang berurutan tetapi itu tidak sepenuhnya mustahil. Keputusan teknik yang tepat didasarkan pada apa konsekuensi dari tabrakan, perkiraan volume angka yang Anda hasilkan, masa hidup yang memerlukan keunikan & apa yang terjadi jika pengguna jahat mulai berusaha menyebabkan tabrakan.

Dapat diterima untuk berasumsi bahwa angka acak akan unik tetapi Anda harus berhati-hati.

Dengan asumsi nomor acak Anda didistribusikan secara merata, kemungkinan tabrakan kira-kira (n ² /2) / k di mana n adalah jumlah angka acak Anda menghasilkan dan k adalah jumlah kemungkinan nilai-nilai "acak" nomor dapat mengambil.

Anda tidak menaruh angka pada kemungkinan astronomis jadi mari kita anggap sebagai 1 dalam 2 ³⁰ (kira-kira dalam satu miliar). Lebih jauh lagi katakanlah Anda menghasilkan 2 ³⁰ paket (jika setiap paket mewakili sekitar satu kilobyte data maka ini berarti sekitar satu terabyte dari total data, besar tetapi tidak terbayangkan). Kami menemukan kami membutuhkan nomor acak dengan setidaknya 2 ⁸⁹ nilai yang mungkin.

Pertama, angka acak Anda harus cukup besar. Angka acak 32 bit dapat memiliki paling banyak 2 ³² nilai yang mungkin. Untuk server yang sibuk yang tidak cukup tinggi.

Kedua generator nomor acak Anda harus memiliki keadaan internal yang cukup besar. Jika pembangkit angka acak Anda hanya memiliki keadaan internal 32-bit maka tidak peduli seberapa besar nilai yang Anda hasilkan dari itu, Anda masih akan mendapatkan paling banyak 2 ³² nilai yang mungkin.

Ketiga jika Anda membutuhkan nomor acak untuk menjadi unik di seluruh koneksi daripada hanya dalam koneksi, generator nomor acak Anda perlu diunggulkan dengan baik. Ini benar terutama jika program Anda sering dinyalakan ulang.

Secara umum generator nomor acak "reguler" dalam bahasa pemrograman tidak cocok untuk penggunaan tersebut. Generator angka acak yang disediakan oleh perpustakaan kriptografi umumnya.

dibangun ke dalam beberapa jawaban di atas adalah asumsi bahwa generator angka acak memang 'datar' - bahwa probabilitas setiap dua angka menjadi nomor berikutnya yang dihasilkan adalah sama.

Itu mungkin tidak benar untuk kebanyakan generator angka acak. Sebagian besar yang menggunakan polinomial orde tinggi berulang kali diterapkan pada biji.

Yang mengatakan, ada banyak sistem di luar sana yang bergantung pada skema ini, biasanya dengan UUID. Sebagai contoh, setiap objek dan aset dalam Second Life memiliki UUID 128 bit, dihasilkan secara acak, dan mereka jarang bertabrakan.

Banyak orang telah memberikan jawaban berkualitas tinggi, tetapi saya ingin menambahkan beberapa poin minor: pertama, poin @nomadictype tentang paradoks ulang tahun sangat baik .

Poin lain: keacakan tidak sesederhana untuk menghasilkan dan mendefinisikan sebagaimana orang mungkin menganggap. (Sebenarnya, sebenarnya ada tes statistik untuk keacakan tersedia).

Dengan mengatakan itu, penting untuk menyadari Kejatuhan Gambler , yang merupakan kekeliruan statistik di mana orang menganggap bahwa peristiwa independen entah bagaimana saling mempengaruhi. Peristiwa acak umumnya secara statistik independen satu sama lain - yaitu jika Anda secara acak menghasilkan "10", itu tidak mengubah probabilitas Anda di masa depan untuk menghasilkan lebih banyak "10". (Mungkin seseorang bisa membuat pengecualian untuk aturan itu, tapi saya berharap itu akan menjadi kasus untuk hampir semua generator bilangan acak).

Jadi jawaban saya adalah jika Anda dapat berasumsi bahwa urutan bilangan acak yang cukup lama adalah unik, mereka tidak akan benar-benar bilangan acak karena itu akan menjadi pola statistik yang jelas. Juga, itu akan menyiratkan bahwa setiap angka baru bukan peristiwa independen karena jika Anda menghasilkan, misalnya, angka 10 yang berarti bahwa probabilitas menghasilkan angka 10 di masa mendatang adalah 0% (tidak mungkin terjadi), ditambah itu berarti Anda akan meningkatkan peluang mendapatkan angka selain 10 (yaitu semakin banyak angka yang Anda hasilkan, semakin tinggi probabilitas masing-masing angka yang tersisa menjadi).

Satu hal lagi yang perlu dipertimbangkan: peluang memenangkan Powerball dari memainkan satu pertandingan adalah, seperti yang saya pahami, sekitar 1 banding 175 juta. Namun, peluang seseorang untuk menang jauh lebih tinggi dari itu. Anda lebih tertarik pada peluang seseorang "menang" (yaitu Menjadi duplikat) daripada dalam peluang nomor tertentu "menang" / menjadi duplikat.

Tidak masalah berapa banyak bit yang Anda gunakan - Anda TIDAK BISA menjamin bahwa dua angka "acak" akan berbeda. Sebagai gantinya, saya sarankan Anda menggunakan sesuatu seperti alamat IP atau alamat jaringan lain dari komputer dan nomor urut, lebih disukai nomor urut BES HONKIN - 128 bit (jelas tanpa tanda) terdengar seperti awal yang baik, tetapi 256 akan lebih baik.

Tidak, tentu saja tidak. Kecuali jika Anda menggunakan sampel tanpa penggantian, ada kemungkinan - betapapun kecil - duplikasi.