Clever Geek Handbook

Bagaimana UUID dibuat



Anda mungkin sudah menggunakan UUID dalam proyek Anda dan menganggapnya unik. Mari kita lihat aspek-aspek utama implementasi dan lihat mengapa UUID secara praktis unik, karena ada kemungkinan kecil dari nilai yang sama terjadi.



Implementasi modern UUID dapat ditelusuri kembali ke RFC 4122, yang menjelaskan lima pendekatan berbeda untuk menghasilkan pengenal ini. Kami akan membahas masing-masing dan menjalankan penerapan versi 1 dan versi 4.



Teori



UUID (pengenal unik universal) adalah nomor 128-bit yang digunakan dalam pengembangan perangkat lunak sebagai pengenal unik untuk elemen. Representasi tekstual klasiknya adalah rangkaian 32 karakter heksadesimal, dipisahkan oleh tanda hubung menjadi lima kelompok dalam pola 8-4-4-4-12.



Misalnya: 



3422b448-2460-4fd2-9183-8000de6f8343


Informasi implementasi UUID disematkan dalam urutan karakter yang tampaknya acak ini: 



xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx


Nilai di posisi M dan N masing-masing menentukan versi dan varian UUID.



Versi: kapan



Nomor versi diidentifikasi oleh empat bit paling signifikan di posisi M. Saat ini ada versi berikut:





Pilihan



Bidang ini mendefinisikan templat informasi yang disematkan dalam UUID. Interpretasi dari semua bit lain dalam UUID bergantung pada nilai varian.



Kami menentukannya dengan 1-3 bit paling signifikan pertama di posisi N.





Saat ini, opsi 1 paling sering digunakan, di mana MSB0sama dengan 1dan MSB1sama 0. Ini berarti bahwa diberikan wildcard - bit yang dipilih - hanya nilai yang mungkin adalah 8, 9, Aatau B.



Memo:



1 0 0 0 = 8

1 0 0 1 = 9

1 0 1 0 = A

1 0 1 1 = B


Jadi jika Anda melihat UUID dengan nilai seperti itu di posisi N, maka ini adalah pengenal di opsi 1.



Versi 1 (waktu + id host unik atau acak)



Dalam hal ini, UUID dibuat seperti ini: beberapa properti pengenal perangkat yang menghasilkan UUID ditambahkan ke waktu saat ini, paling sering adalah alamat MAC (juga dikenal sebagai ID node).



Pengenal diperoleh dengan menggabungkan alamat MAC 48-bit, stempel waktu 60-bit, urutan jam "unik" 14-bit, dan 6 bit yang dicadangkan untuk UUID versi dan varian.



Urutan jam hanyalah nilai yang bertambah setiap kali jam diubah.


Stempel waktu yang digunakan dalam versi ini adalah jumlah interval 100 nanodetik sejak 15 Oktober 1582, tanggal asal kalender Gregorian.



Anda mungkin sudah familiar dengan sistem waktu Unix sejak permulaan zaman. Ini hanya jenis Day Zero yang berbeda. Ada layanan di web yang dapat membantu Anda mengubah satu representasi temporal menjadi representasi lain, jadi jangan memikirkannya.


Meskipun implementasi ini terlihat cukup sederhana dan dapat diandalkan, penggunaan alamat MAC dari mesin tempat pengenal dibuat tidak memungkinkan metode ini dianggap universal. Apalagi jika keamanan menjadi kriteria utama. Oleh karena itu, dalam beberapa implementasi, alih-alih pengenal node, digunakan 6 byte acak yang diambil dari generator nomor acak yang dilindungi secara kriptografis.



Membangun UUID versi 1 berjalan seperti ini:



  1. 32 bit paling signifikan dari stempel waktu UTC saat ini diambil. Ini akan menjadi 4 byte pertama (8 karakter hex) dari UUID [ TimeLow].
  2. 16 bit tengah dari stempel waktu UTC saat ini diambil. Ini akan menjadi 2 byte berikutnya (4 karakter hex) [ TimeMid].
  3. 2 byte berikutnya (4 karakter hex) menggabungkan 4 bit versi UUID dengan 12 MSB tersisa dari stempel waktu UTC saat ini (yang memiliki total 60 bit) [ TimeHighAndVersion].
  4. 1-3 bit berikutnya menentukan varian versi UUID. Bit yang tersisa berisi urutan jam yang menambahkan sedikit keacakan untuk implementasi ini. Hal ini untuk menghindari tabrakan ketika beberapa generator UUID berjalan pada sistem yang sama: baik jam sistem disetel kembali untuk generator, atau perubahan waktu diperlambat [ ClockSequenceHiAndRes && ClockSequenceLow].
  5. 6 byte terakhir (12 karakter heksadesimal, 48 bit) adalah "ID node", yang biasanya merupakan alamat MAC generator [ NodeID].


UUID versi 1 dibuat menggunakan penggabungan: 



TimeLow + TimeMid + TimeHighAndVersion + (ClockSequenceHiAndRes && ClockSequenceLow) + NodeID


Karena implementasi ini bergantung pada clock, kita perlu menangani situasi edge. Pertama, untuk meminimalkan korelasi antar sistem, secara default urutan jam diambil sebagai nomor acak - ini dilakukan hanya sekali dalam seluruh siklus hidup sistem. Ini memberi kita manfaat tambahan dari mendukung ID node yang dapat dibawa lintas sistem, karena urutan jam awal sepenuhnya tidak bergantung pada ID node.



Ingatlah bahwa tujuan utama penggunaan urutan jam adalah untuk menambahkan keacakan pada persamaan kita. Bit urutan jam membantu memperpanjang cap waktu dan mengakomodasi situasi di mana beberapa UUID dibuat bahkan sebelum jam prosesor berubah. Dengan cara ini kami menghindari membuat pengenal yang sama ketika jam disetel kembali (perangkat mati) atau pengenal node berubah. Jika jam disetel mundur, atau bisa saja disetel kembali (misalnya, saat sistem dimatikan), dan generator UUID tidak dapat memverifikasi bahwa pengenal dibuat dengan stempel waktu lebih lama dari nilai jam yang ditentukan, maka urutan jam harus diubah. Jika kita mengetahui nilai sebelumnya, kita cukup meningkatkannya;jika tidak, itu harus diatur secara acak atau dengan PRNG berkualitas tinggi.



Versi 2 (Keamanan Lingkungan Komputasi Terdistribusi)



Perbedaan utama dari versi ini dari versi sebelumnya adalah bahwa alih-alih "keacakan" dalam bentuk bit paling signifikan dari urutan jam, karakteristik pengenal sistem digunakan di sini. Seringkali ini hanya ID pengguna saat ini. Versi 2 lebih jarang digunakan, ini sangat sedikit berbeda dari versi 1, jadi mari kita lanjutkan.



Versi 3 (nama + hash MD5)



Jika pengenal unik diperlukan untuk penamaan atau informasi penamaan, biasanya UUID versi 3 atau versi 5 digunakan.



Mereka menyandikan entitas "bernama" (situs, DNS, teks biasa, dll.) Ke dalam nilai UUID. Yang terpenting, UUID yang sama akan dibuat untuk namespace atau teks yang sama.



Perhatikan bahwa namespace itu sendiri adalah UUID. 



let namespace = “digitalbunker.dev”
let namespaceUUID = UUID3(.DNS, namespace)

// Ex: 
UUID3(namespaceUUID, “/category/things-you-should-know-1/”) 
4896c91b-9e61-3129-87b6-8aa299028058

UUID3(namespaceUUID, “/category/things-you-should-know-2/”) 
29be0ee3-fe77-331e-a1bf-9494ec18c0ba

UUID3(namespaceUUID, “/category/things-you-should-know-3/”) 
33b06619-1ee7-3db5-827d-0dc85df1f759


Dalam implementasi ini, namespace UUID diubah menjadi string byte yang digabungkan dengan nama input, kemudian di-hash dengan MD5, menghasilkan 128 bit untuk UUID. Kami kemudian menulis ulang beberapa bit untuk mereproduksi versi dan informasi versi secara akurat, dan membiarkan sisanya tidak tersentuh.



Penting untuk dipahami bahwa baik namespace maupun nama input tidak dapat dihitung berdasarkan UUID. Ini adalah operasi yang tidak dapat diubah. Satu-satunya pengecualian adalah brute force ketika salah satu nilai (namespace atau teks) sudah diketahui penyerang.



Dengan input yang sama, UUID versi 3 dan 5 yang dihasilkan akan bersifat deterministik.



Versi 4 (PRNG)



Implementasi paling sederhana.



6 bit dicadangkan untuk versi dan varian, masih tersisa 122 bit. Versi ini hanya menghasilkan 128 bit acak dan kemudian menggantikan 6 bit tersebut dengan data versi dan versi.



UUID semacam itu sepenuhnya bergantung pada kualitas PRNG (pembuat nomor acak-semu). Jika algoritmanya terlalu sederhana, atau tidak memiliki nilai awal, kemungkinan pengulangan pengenal akan meningkat.



Dalam bahasa modern, UUID versi 4 paling sering digunakan.



Implementasinya cukup sederhana:



  1. Kami menghasilkan 128 bit acak.
  2. Tulis ulang beberapa bit dengan versi yang benar dan informasi versi:



    1. Ambil bit ketujuh dan 0x0FAND untuk menghapus gigitan tinggi. Dan kemudian 0x40ATAU digunakan untuk menetapkan versi 4.
    2. Kemudian kita mengambil byte kesembilan, melakukan 0x3Foperasi AND pada c dan 0x80operasi OR padanya.
  3. Ubah 128 bit menjadi hex dan masukkan tanda hubung.


Versi 5 (nama + SHA-1-hash)



Satu-satunya perbedaan dari versi 3 adalah kami menggunakan algoritme hashing SHA-1, bukan MD5. Versi ini lebih disukai daripada yang ketiga (SHA-1> MD5).



Praktek



Salah satu keuntungan penting dari UUID adalah bahwa keunikannya tidak bergantung pada otoritas otorisasi pusat atau pada koordinasi antara sistem yang berbeda. Siapa pun dapat membuat UUID dengan kepastian bahwa tidak ada orang lain yang akan menghasilkan nilai ini di masa mendatang.



Ini memungkinkan untuk menggabungkan pengidentifikasi yang dibuat oleh peserta berbeda dalam satu database, atau memindahkan pengidentifikasi antar database dengan probabilitas tabrakan yang dapat diabaikan.



UUID dapat digunakan sebagai kunci utama dalam database, sebagai nama unik untuk file yang diunggah, sebagai nama unik untuk sumber web apa pun. Anda tidak memerlukan otoritas otorisasi pusat untuk membuatnya. Tapi ini adalah solusi bermata dua. Karena kurangnya pengontrol, tidak mungkin melacak UUID yang dihasilkan.



Ada beberapa kekurangan lagi yang perlu diatasi. Keacakan yang melekat meningkatkan keamanan, tetapi ini membuat proses debug menjadi lebih sulit. Selain itu, UUID mungkin berlebihan dalam beberapa situasi. Katakanlah tidak masuk akal menggunakan 128 bit untuk mengidentifikasi data secara unik yang ukuran totalnya kurang dari 128 bit.



Keunikan



Tampaknya jika Anda memiliki cukup waktu, Anda dapat mengulangi sebuah nilai. Terutama dalam kasus versi 4. Namun kenyataannya tidak demikian. Jika Anda menghasilkan satu miliar UUID per detik selama 100 tahun, peluang salah satu nilai terulang adalah sekitar 50%. Ini mengingat fakta bahwa PRNG memberikan jumlah entropi yang cukup (keacakan benar), jika tidak, kemungkinan ganda akan lebih tinggi. Contoh yang lebih ilustratif: jika Anda membuat 10 triliun UUID, kemungkinan munculnya dua nilai identik adalah 0,00000006%.



Dan dalam kasus versi 1, jam akan disetel ulang ke nol hanya di 3603. Jadi, jika Anda tidak berencana untuk terus menjalankan layanan hingga tahun 1583, Anda aman.



Namun, kemungkinan munculnya double tetap, dan dalam beberapa sistem mereka mencoba memperhitungkannya. Namun dalam sebagian besar kasus, UUID dapat dianggap sangat unik. Jika Anda membutuhkan lebih banyak bukti, berikut adalah visualisasi sederhana dari kemungkinan tabrakan dalam praktiknya.


More articles:


All Articles