GoSuda

隆重推出 Randflake ID：一种分布式、统一、不可预测、独一无二的随机 ID 生成器。

By Lemon Mint
views ...

设想这样一种情况：我们需要生成唯一的 64 位随机数，且外部方无法预测下一个或上一个数字。

在这种情况下，我们可以生成一个 8 字节的随机值，检查其是否已存在于数据库中，如果唯一则将其存储。

然而，此方法存在若干缺点。我们必须将生成的每个数字存储在数据库中以确保唯一性。至少一次往返数据库的需求会产生延迟问题，尤其是在可扩展性至关重要的分布式环境中。

为解决这些问题，我们引入了 Randflake ID：一种分布式、均匀、不可预测、唯一的随机 ID 生成器。

Randflake ID 如何运作？

Randflake ID 的灵感来源于 Snowflake ID，这是 X（前身为 Twitter）开发的广泛使用的 k 排序 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 伪代码提供了一个简化的实现：

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunday, October 27, 2024 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bits for timestamp (lifetime of 34 years)
10RANDFLAKE_NODE_BITS = 17  # 17 bits for node id (max 131072 nodes)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bits for sequence (max 131072 sequences)
12
13# Derived constants
14RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
15RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
16RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
17
18class Randflake:
19    def __init__(self, node_id: int, secret: bytes):
20        self.node_id = int(node_id)
21        self.sequence = int(0)
22        self.rollover = int(time.time())
23        self.sbox = Sparx64(secret)
24
25    def _new_raw(self) -> int:
26        while True:
27            now = int(time.time())
28
29            self.sequence += 1
30            sequence = self.sequence
31
32            if sequence > RANDFLAKE_MAX_SEQUENCE:
33                if now > self.rollover:
34                    self.sequence = 0
35                    self.rollover = now
36                    sequence = 0
37                else:
38                    continue
39
40            timestamp = now - RANDFLAKE_EPOCH_OFFSET
41            return (timestamp << 34) | (self.node_id << 17) | sequence
42
43    def generate(self) -> int:
44        id_raw = self._new_raw()
45        src = struct.pack("<q", id_raw)
46        dst = bytearray(8)
47        self.sbox.encrypt(dst, src)
48        return struct.unpack("<q", dst)[0]

Randflake 的生产级实现，包含节点 ID 租约机制，可在 GitHub 上获取。

其他考量

在本节中，我们将讨论实现 Randflake ID 的其他一些考量。

节点 ID 协调

我们建议采用基于租约的节点 ID 协调机制。

在此方法中，中央协调服务为每个生成器分配一个唯一的节点 ID。

在租约期内，此节点 ID 不会重新分配，以确保唯一性，从而减少与协调服务频繁通信的需要。

持有租约的生成器，如果满足续约条件，可以向协调服务请求租约续约。

续约条件是指必须满足的一组标准，以便租约得以续约，例如生成器仍然处于活动状态并需要该节点 ID。

租约持有者是节点 ID 范围的当前持有者。

如果租约在其有效时间内，则被认为是活动的且未过期。

通过这种方式，我们可以将往返次数减少到每个租约续约期一次，从而最大限度地减少延迟并提高分布式系统的效率。

针对时钟故障的缓解措施

租约服务在分配租约时必须检查时间戳一致性。分配的租约开始时间必须大于或等于上次租约开始时间。

如果当前时间戳小于租约开始时间或大于租约结束时间，生成器应拒绝请求。

当时间回溯时，此程序对于保护生成 ID 的唯一性至关重要。例如，如果时钟回溯，则可以分配一个新租约，其开始时间早于先前分配的租约，这可能导致生成重复 ID。通过拒绝时间戳在现有租约期内的请求，我们可以防止这种情况并保持 ID 的唯一性。

ID 分布的均匀性

ID 分布直方图

根据上述直方图，我们可以看到生成的 Randflake ID 的分布非常均匀。这表明 ID 分布可以直接用作分片键。

结论

在本文中，我们介绍了 Randflake，一种结合了 Snowflake 和 Sparx64 优势的新型 ID 生成算法。

我们希望本文能让您全面了解 Randflake 及其实现。

您可以在 GitHub 上找到 Randflake 的完整源代码。

如果您有任何问题或建议，请随时联系我们。我们也在寻找贡献者，以帮助改进 Randflake 并在其他编程语言中实现它。

我们计划发布一个用于 Randflake 和 Snowflake 的生产级协调服务，该服务将在 GitHub 上开源。敬请关注更新！