Generator ID Snowflake - Buat ID Terdistribusi Unik

Apa Itu Generator ID Snowflake?

Generator ID Snowflake membuat angka unik 64-bit dari stempel waktu, pengenal mesin, dan nomor urutan. Twitter membuat format ini pada 2010 untuk memberikan pengenal kepada setiap tweet yang dapat dihasilkan oleh banyak server secara bersamaan, tanpa perlu saling bertanya, "apakah angka ini sudah digunakan?" Alat ini membuat satu ID Snowflake dari nilai yang dimasukkan dan menunjukkan bagaimana nilai-nilai tersebut mengisi 64 bit.

Cara Kerja Generator ID Snowflake Ini

Generator ini menerima empat masukan:

• Stempel waktu: stempel waktu Unix dalam milidetik. Biarkan kosong untuk menggunakan waktu saat ini.
• ID mesin: bilangan bulat dari 0 hingga 31 (5 bit). Ini adalah "ID worker" asli Twitter.
• ID pusat data: bilangan bulat dari 0 hingga 31 (5 bit).
• Nomor urutan: bilangan bulat dari 0 hingga 4095 (12 bit), yang digunakan untuk membedakan ID yang dibuat pada milidetik yang sama.

Alat ini menggabungkan keempat nilai menjadi satu ID 64-bit. Kemudian, hasilnya ditampilkan sebagai biner, yang dibagi menjadi segmen stempel waktu, pusat data, mesin, dan urutan.

Stempel waktu diukur dari titik awal tetap yang disebut epoch Twitter: 4 November 2010, 1:42:54,657 UTC, atau 1.288.834.974.657 milidetik setelah epoch Unix. Generator ini tidak memungkinkan titik awal tersebut berubah. Setiap ID yang dihasilkannya diukur dari satu tanggal tetap itu.

Struktur ID Snowflake

ID Snowflake adalah bilangan bulat 64-bit yang dibagi menjadi empat bagian, dibaca dari bit paling signifikan ke bawah:

Bit awal selalu 0, sehingga ID Snowflake selalu merupakan angka positif. Stempel waktu 41-bit dan kolom urutan 12-bit adalah dua bagian yang membuat ID Snowflake berguna untuk pengurutan: ID yang dibuat belakangan memiliki segmen stempel waktu yang lebih besar, sehingga ditempatkan setelah ID yang dibuat lebih awal.

Rumus ID Snowflake

Generator ini membuat ID dengan rumus berikut:

$d = t - 1288834974657$

$I = (d << 22) \mathbin{|} (c << 17) \mathbin{|} (m << 12) \mathbin{|} s$

dengan d sebagai delta, t sebagai stempel waktu yang dimasukkan dalam milidetik, I sebagai ID akhir, c sebagai ID pusat data, m sebagai ID mesin, dan s sebagai nomor urutan.

<< adalah pergeseran bit ke kiri. Menggeser angka ke kiri sebanyak 22 bit sama dengan mengalikannya dengan 2²², atau 4.194.304. Besarnya pergeseran (22, 17, 12) berasal langsung dari lebar kolom: kolom urutan lebarnya 12 bit, sehingga ID mesin berada 12 bit di atasnya; kolom mesin lebarnya 5 bit, sehingga ID pusat data berada 17 bit di atasnya (12 + 5); dan seterusnya.

Cara Menghitung ID Snowflake: Contoh Terperinci

Misalkan seseorang memasukkan:

• Stempel waktu: 1.288.834.975.657 (tepat 1.000 md setelah epoch Twitter)
• ID pusat data: 1
• ID mesin: 1
• Nomor urutan: 0

Langkah 1 — Cari delta. Kurangkan epoch dari stempel waktu: 1.288.834.975.657 − 1.288.834.974.657 = 1.000.

Langkah 2 — Geser setiap kolom ke posisinya.

• Stempel waktu: 1.000 << 22 = 4.194.304.000
• ID pusat data: 1 << 17 = 131.072
• ID mesin: 1 << 12 = 4.096
• Urutan: 0

Langkah 3 — Gabungkan dengan OR bitwise. Karena tidak ada kolom yang digeser saling bertumpang tindih, penjumlahannya menghasilkan nilai yang sama seperti operasi OR:

4.194.304.000 + 131.072 + 4.096 + 0 = 4.194.439.168

Itulah ID Snowflake untuk masukan ini. Tampilan hasil alat ini membagi kembali string biner 64-bit yang sama menjadi blok stempel waktu 41-bit, blok pusat data 5-bit, blok mesin 5-bit, dan blok urutan 12-bit, sehingga struktur angkanya tetap terlihat.

Di Mana ID Snowflake Digunakan

Twitter membuat format ini untuk memberikan ID unik yang kurang lebih berurutan berdasarkan waktu kepada tweet di ribuan mesin basis data, tanpa penghitung pusat yang harus diperiksa oleh setiap server. Discord dan Instagram kemudian mengadopsi desain ID 64-bit serupa untuk pesan dan kiriman. Gagasan yang sama digunakan dalam sharding basis data, ID pesanan untuk sistem perdagangan elektronik, dan log peristiwa dalam aplikasi terdistribusi. Format ini cocok untuk situasi ketika banyak mesin memberikan ID secara independen, tetapi ID tersebut tetap perlu diurutkan kurang lebih berdasarkan waktu.

Keterbatasan ID Snowflake

Generator Snowflake untuk produksi biasanya memiliki jam internal yang terus berjalan: generator tersebut meningkatkan nomor urutan untuk setiap ID yang dibuat pada milidetik yang sama dan menunggu milidetik berikutnya setelah urutan mencapai 4.095. Alat ini tidak menyimpan keadaan di antara perhitungan. Alat ini membuat satu ID dari nilai apa pun yang dimasukkan, sehingga berguna untuk mempelajari format, tetapi berbeda dari layanan produksi yang berjalan langsung.

Desain ini memiliki batas tetap, apa pun layanan yang menerapkannya:

• Epoch tetap: generator ini hanya menerima stempel waktu pada atau setelah 4 November 2010 (epoch Twitter). Tanggal yang lebih awal tidak dapat dikodekan.
• Batas atas stempel waktu: kolom stempel waktu 41-bit habis sekitar Juli 2080. Setelah itu, delta dari epoch tidak lagi muat dalam 41 bit.
• Batas urutan: hanya 4.096 ID berbeda (0–4095) yang dapat diterbitkan oleh satu mesin pada milidetik yang sama sebelum nilainya berulang.
• Ruang mesin: dengan masing-masing 5 bit untuk ID mesin dan ID pusat data, suatu penerapan memiliki 1.024 identitas mesin yang berbeda (32 × 32) untuk dibagikan tanpa benturan.
• Pengurutan lokal, bukan global: ID hanya terurut dengan benar satu sama lain jika berasal dari mesin yang jamnya tersinkronisasi. Perbedaan waktu antarjam mesin dapat mengacaukan pengurutan waktu yang ketat.

Sejarah ID Snowflake

Twitter mengumumkan format ID Snowflake pada 2010 sebagai pengganti ID basis data yang bertambah otomatis secara sederhana, yang tidak dapat diskalakan di banyak server basis data independen. Namanya berasal dari gagasan bahwa, seperti kepingan salju sungguhan, tidak ada dua ID yang dihasilkan yang sama. Desain ini kemudian dijadikan sumber terbuka dan disalin, dengan modifikasi, oleh platform besar lain yang membutuhkan hal yang sama: ID unik yang dapat diurutkan dan dihasilkan oleh banyak mesin secara bersamaan.

Pertanyaan yang sering diajukan

Apa itu ID Snowflake? ID Snowflake adalah angka 64-bit yang terdiri atas stempel waktu, pengenal mesin, dan nomor urutan, yang dirancang agar banyak mesin dapat menghasilkan ID unik tanpa berkoordinasi satu sama lain.

Apa rumus ID Snowflake? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, dengan epoch sebagai tanggal awal tetap dan << sebagai pergeseran bit ke kiri.

Dapatkah epoch diubah dalam generator ini? Tidak. Alat ini selalu mengukur stempel waktu dari epoch Twitter yang tetap, 4 November 2010. Tidak ada kolom untuk menetapkan tanggal awal yang berbeda.

Apakah alat ini mendekode ID Snowflake yang sudah ada? Tidak. Alat ini hanya membuat ID baru dari stempel waktu, ID mesin, ID pusat data, dan nomor urutan yang dimasukkan, lalu menampilkan rincian bit ID baru tersebut.

Berapa banyak ID Snowflake yang dapat dihasilkan satu mesin per milidetik? Hingga 4.096, karena kolom urutan lebarnya 12 bit (nilai 0 hingga 4.095).

Sampai tahun berapa generator ini dapat menghasilkan stempel waktu yang valid? Hingga sekitar Juli 2080. Kolom stempel waktu 41-bit dapat menampung paling banyak sekitar 69,7 tahun yang diukur dari epoch tetap 2010, setelah itu nilainya meluap dari kolom.

Referensi

1. "Announcing Snowflake." Blog Teknik Twitter, 2010.
2. "Snowflake ID." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID