--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: Pembangkitan ID Unik 64-Bit Terdistribusi dengan Block Cipher Sparx64' description: Generator ID unik 64-bit terdistribusi yang menggabungkan timestamp 30-bit, ID node 17-bit, penghitung lokal 17-bit, dan block cipher Sparx64 ARX untuk menghasilkan ID yang tidak dapat ditebak. language: id date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Pertimbangkan suatu situasi di mana kita perlu menghasilkan angka acak 64-bit yang unik, dan pihak eksternal tidak boleh dapat memprediksi angka berikutnya maupun sebelumnya. Di sini, kita dapat menghasilkan nilai acak 8-byte, memeriksa apakah nilai tersebut sudah ada di dalam basis data, lalu menyimpannya jika bersifat unik. Namun, metode ini memiliki beberapa kelemahan. Kita harus menyimpan setiap angka yang dihasilkan di dalam basis data untuk memastikan keunikannya. Kebutuhan akan setidaknya satu kali perjalanan bolak-balik ke basis data menimbulkan masalah latensi, terutama dalam lingkungan terdistribusi di mana skalabilitas sangat penting. Untuk mengatasi masalah-masalah ini, kami memperkenalkan Randflake ID: sebuah generator ID acak yang terdistribusi, seragam, tidak dapat diprediksi, dan unik. ## Bagaimana Randflake ID Bekerja? Randflake ID terinspirasi oleh Snowflake ID, mekanisme pembangkitan id yang terurut-k (k-sorted) dan banyak digunakan, yang dikembangkan oleh X (sebelumnya twitter). Snowflake ID menggunakan stempel waktu saat ini, ID node, dan penghitung lokal untuk menghasilkan sebuah pengenal. Kami memperluas pendekatan ini lebih jauh untuk pembangkitan ID acak yang unik dan menambahkan elemen kunci rahasia yang baru. Gagasan utamanya adalah menambahkan lapisan block cipher pada generator ID unik yang sudah ada untuk mencapai ketidakmungkinan memprediksi hubungan antarangka. Block cipher merupakan fungsi kriptografi mendasar yang mengubah blok plaintext berpanjang tetap menjadi blok ciphertext dengan panjang yang sama. Transformasi ini diatur oleh sebuah kunci kriptografi. Karakteristik yang membedakan block cipher adalah sifat dapat dibalikkannya: fungsi tersebut harus bersifat satu-ke-satu (bijektif), yang memastikan bahwa setiap masukan unik berkorespondensi dengan keluaran unik, dan sebaliknya. Sifat ini sangat penting untuk dekripsi, yang memungkinkan plaintext asli dipulihkan dari ciphertext ketika kunci yang benar diterapkan. Dengan menggunakan block cipher sebagai fungsi satu-ke-satu, kita dapat menjamin bahwa setiap masukan unik menghasilkan keluaran unik yang sesuai dalam rentang yang telah ditentukan. ## Struktur dan Pertimbangan Desain Berdasarkan konsep-konsep fundamental ini, mari kita telaah bagaimana Randflake ID mengimplementasikan gagasan-gagasan tersebut dalam praktik. Struktur Randflake ID mencakup stempel waktu unix 30-bit dengan presisi detik, pengenal node 17-bit, penghitung lokal 17-bit, dan block cipher 64-bit yang didasarkan pada algoritma sparx64. Berikut beberapa keputusan desain: - Beberapa instans VM di Google Cloud Platform dapat menyinkronkan jam hingga presisi 0,2 ms, tetapi tingkat akurasi tersebut tidak tersedia di internet publik atau penyedia cloud lainnya. - Kami memilih presisi detik karena kami hanya dapat menyinkronkan jam antarnode secara efektif dalam resolusi beberapa milidetik. - Pengenal node 17-bit memungkinkan 131072 generator individual pada saat yang sama, yang dapat ditetapkan secara per-proses, per-core, atau per-thread. - Dalam sistem dengan throughput tinggi, penghitung lokal 17-bit mungkin tidak mencukupi. Untuk menyesuaikan throughput, kita dapat menetapkan beberapa generator, masing-masing dengan ID node yang berbeda, untuk bekerja dalam satu proses atau thread. - Kami mengadopsi sparx64 sebagai block cipher 64-bit, sebuah block cipher ringan modern berbasis ARX. - Randflake ID menawarkan keterlacakan internal, yang hanya mengungkapkan ID node asal dan stempel waktunya kepada pihak yang memiliki kunci rahasia. - Throughput maksimum teoretis adalah 17.179.869.184 ID/detik, yang memadai untuk sebagian besar aplikasi berskala global. ## Pseudokode Pembangkitan Randflake ID Untuk lebih lanjut mengilustrasikan proses pembangkitan Randflake ID, pseudokode Python berikut memberikan implementasi yang disederhanakan: ```python import time import struct from .sparx64 import Sparx64 # Konstanta RANDFLAKE_EPOCH_OFFSET = 1730000000 # Minggu, 27 Oktober 2024 pukul 03:33:20 UTC # Alokasi bit RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bit untuk stempel waktu (masa pakai 34 tahun) RANDFLAKE_NODE_BITS = 17 # 17 bit untuk id node (maksimum 131072 node) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bit untuk sekuens (maksimum 131072 sekuens) # Konstanta turunan RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1 RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1 RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1 class Randflake: def __init__(self, node_id: int, secret: bytes): self.node_id = int(node_id) self.sequence = int(0) self.rollover = int(time.time()) self.sbox = Sparx64(secret) def _new_raw(self) -> int: while True: now = int(time.time()) self.sequence += 1 sequence = self.sequence if sequence > RANDFLAKE_MAX_SEQUENCE: if now > self.rollover: self.sequence = 0 self.rollover = now sequence = 0 else: continue timestamp = now - RANDFLAKE_EPOCH_OFFSET return (timestamp << 34) | (self.node_id << 17) | sequence def generate(self) -> int: id_raw = self._new_raw() src = struct.pack("