--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: Randflake ID：基于 Sparx64 分组密码的分布式 64 位唯一 ID 生成 description: 基于分布式的64位唯一ID生成器,结合30位时间戳、17位节点ID、17位本地计数器,以及用于生成不可猜测ID的Sparx64 ARX分组密码。 language: zh date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- 考虑这样一种情形：我们需要生成唯一的64位随机数，并且外部各方不应能够预测下一个或上一个数字。 在此，我们可以生成一个8字节的随机值，检查其是否已存在于数据库中，若唯一则将其存储。 然而，这种方法存在若干缺点。我们必须将生成的每个数字存储在数据库中以确保唯一性。至少一次数据库往返的要求会造成延迟问题，尤其是在可扩展性至关重要的分布式环境中。 为了解决这些问题，我们推出了Randflake ID：一种分布式、均匀、不可预测、唯一的随机ID生成器。 ## Randflake ID如何工作？ Randflake ID受到Snowflake ID的启发，后者是X（原Twitter）开发的、被广泛使用的k-sorted ID生成机制。 Snowflake ID使用当前时间戳、节点ID和本地计数器来生成标识符。 我们进一步扩展了这一方法，用于随机唯一ID的生成，并新增了一个密钥元素。 关键思想是在现有的唯一ID生成器之上添加一个分组密码层，从而实现对数字之间关系的不可预测性。 分组密码是一种基本的密码学函数，它将固定长度的明文分组转换为相同长度的密文分组。这种变换由密码密钥控制。分组密码的显著特征在于其可逆性：它必须是一一映射（双射）函数，确保每个唯一输入对应一个唯一输出，反之亦然。这一性质对于解密至关重要，在应用正确密钥时，可以从密文中恢复原始明文。 通过将分组密码作为一一映射函数使用，我们可以保证每个唯一输入在限定范围内都会产生一个对应的唯一输出。 ## 结构与设计考量 基于这些基本概念，让我们考察Randflake ID如何在实践中实现这些思想。 Randflake ID的结构包括一个精确到秒的30位Unix时间戳、一个17位节点标识符、一个17位本地计数器，以及一个基于sparx64算法的64位分组密码。 以下是一些设计决策： - Google Cloud Platform中的某些VM实例可以将时钟同步到0.2毫秒的精度，但这种精度在公共互联网或其他云服务提供商处并不可用。 - 我们选择秒级精度，因为我们只能在几毫秒的分辨率内有效地在节点之间同步时钟。 - 17位节点标识符允许同一时刻存在131072个独立生成器，可以按进程、按核心或按线程的方式进行分配。 - 在高吞吐量系统中，17位本地计数器可能不足。为了匹配吞吐量，我们可以分配多个生成器，每个生成器具有不同的节点ID，使其在同一进程或线程中工作。 - 我们采用sparx64作为64位分组密码，这是一种现代的轻量级ARX型分组密码。 - Randflake ID提供内部可追溯性，只有拥有密钥的人才能揭示其来源节点ID和时间戳。 - 理论最大吞吐量为17,179,869,184 ID/秒，这对于大多数全球规模的应用已经足够。 ## Randflake ID生成的伪代码 为了进一步说明Randflake ID的生成过程，以下Python伪代码提供了一个简化的实现： ```python import time import struct from .sparx64 import Sparx64 # 常量 RANDFLAKE_EPOCH_OFFSET = 1730000000 # 2024年10月27日星期日 UTC时间 3:33:20 AM # 位分配 RANDFLAKE_TIMESTAMP_BITS = 30 # 时间戳占30位（寿命为34年） RANDFLAKE_NODE_BITS = 17 # 节点ID占17位（最多131072个节点） RANDFLAKE_SEQUENCE_BITS = 17 # 序列号占17位（最多131072个序列） # 派生常量 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("