为什么要在生成的ID后附加分片ID?

6
我正在阅读这篇文章:https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c。在最后一节“解决方案”中,他们基于数据库的自增特征 + 纪元毫秒数 + 分片 ID 来生成全局唯一 ID。
那么为什么需要追加分片 ID 呢?
具体来说,它说:
接下来,我们使用特定数据片的分片 ID 来划分。假设我们按用户 ID 进行分片,并且有 2000 个逻辑分片;如果我们的用户 ID 是 31341,则分片 ID 为 31341 % 2000 -> 1341。我们用这个值填充接下来的 13 位。
这不太合理:如果您已经对用户 ID 模运算了分片数量(31341%2000),那么这意味着 1)您已经有了用户 ID!2)您已经通过模函数知道了它所属的分片!
我在这里误解了什么吗?
2个回答

9
也许我能更好地向您解释一下,不仅因为用户ID不适合。
他们在使用Twitter Snowflake ID。这个ID被设计成在多个服务器、多个数据中心中并行生成唯一的ID。例如,在完全相同的时间内,两个“项目”在两个“位置”需要一个保证独特的ID,任何时间间隔少于一毫秒的东西,甚至可能在同一纳秒内... 这个唯一的ID需要快速产生,高效,以逻辑方式构建,可以有效地解析,可以容纳在64位内,并且生成它的方法需要能够处理许多人的生命周期内产生的大量ID。这意味着他们不能进行数据库查找以获得一个尚未被占用的唯一ID,不能在生成后验证所生成的ID是否唯一,也不能使用可能会偶尔生成重复ID的现有方法,例如UUID。所以他们想出了一种方法...
他们设置了一个自定义共同纪元,例如今天作为长整数的基点。因此,他们有一个42位长的整数,从0+从该时间纪元开始计时。
然后,如果单个进程在同一毫秒内必须生成2个或更多的ID,则还添加了一个序列作为12位长整数。现在他们已经使用了42+12=54位,并且当您考虑到多个进程在多台机器上运行时(通常每个数据中心仅提供一台机器来提供ID,但可能有更多,并且通常只有一个工作程序/进程每个机器)您意识到需要更多的内容。
因此,他们还必须编码数据中心ID和“工作”(进程)ID。这将涵盖多个具有每个数据中心中多个工作程序的数据中心。这两个ID都是5位长整数。所有这些整数都是无符号的,因此这些5位整数可以增加到31,其中包括0。因此,32个数据中心,每个数据中心最多有32个工作程序... 因此,现在我们有42+12+5+5=64位,最多有32x32=1024个工作程序分布式生成这些ID。
所以... 随着寿命高达139年能够适应42位上限... 10位节点ID(或数据中心+工作程序ID)... 12位序列(每毫秒每个工作程序可生成4096个ID)... 您会得出一个最多保证唯一的64位ID系统/公式,它在这139年里的规模扩展得非常好,不以任何方式依赖数据库,但可以有效地产生和存储在数据库中。
因此,这个ID系统的计算为42+12+10,您可以按您喜欢的方式划分这些10位,而不会超出在任何地方存储64位无符号长整数。非常灵活,功能强大。

这叫做雪花ID,是Twitter提出的。这10位可以被称为分片ID、节点ID或数据中心ID和工作ID的组合,具体取决于您的需求。但是,通过将该分片/节点ID与多个进程相关联而非用户,并且能够在多个“事物”之间使用该ID,您就不必担心很多问题,并且可以跨越充满多种事物的多个数据库。

唯一需要注意的是,该分片/节点ID只能容纳1024个不同的值,而没有用户ID或任何可用的唯一ID会从0到1023进行自我分配。

因此,您可以看到,这10位必须是静态、可分配和易于解析的东西。

以下是一个简单的Python函数,可生成雪花ID:

def genSnowflakeId(worker_id, data_center_id, ids_generated):
    "Returns a snowflake ID - This function will generate a unique ID that fits in a 64 bit unsigned number that scales for multiple workers running in mutiple datacenters. You must manage a timestamp and sequence sanity with ids_generated (i.e. increment if time apart < 1 millisecond or always increment and roll over to 0 if > 4095). Ultimately this will allow you to efficiently generate unique IDs across multiple locations for 139 years that fits in a bigint(20) database field and can be parsed for the created timestamp, worker ID, and datacenter ID. See https://github.com/twitter-archive/snowflake/tree/snowflake-2010"

    import sys
    import time

    # Mon Jul  8 05:07:56 EDT 2019
    twepoch = 1562576876131L

    sequence = 0L
    worker_id_bits = 5L
    data_center_id_bits = 5L
    sequence_bits = 12L
    timestamp_bits = 42L
    #total bits 64

    max_worker_id = -1L ^ (-1L << worker_id_bits)
    max_data_center_id = -1L ^ (-1L << data_center_id_bits)
    max_ids_generated = -1L ^ (-1L << sequence_bits)

    worker_id_shift = sequence_bits
    data_center_id_shift = sequence_bits + worker_id_bits
    timestamp_left_shift = sequence_bits + worker_id_bits + data_center_id_bits
    sequence_mask = -1L ^ (-1L << sequence_bits)


    # Sanity checks for input
    if worker_id > max_worker_id or worker_id < 0:
        raise ValueError("worker_id", "worker id can't be greater than %i or less than 0" % max_worker_id)
    if data_center_id > max_data_center_id or data_center_id < 0:
        raise ValueError("data_center_id", "data center id can't be greater than %i or less than 0" % max_data_center_id)
    if ids_generated > max_ids_generated or ids_generated < 0:
        raise ValueError("ids_generated", "ids generated can't be greater than %i or less than 0" % max_ids_generated)

    timestamp = long(int(time.time() * 1000))

    new_id = ((timestamp - twepoch) << timestamp_left_shift) | (data_center_id << data_center_id_shift) | (worker_id << worker_id_shift) | sequence

    return new_id

希望这个答案能够满足你的需求 :)

0
他们需要一个长度为64位的图像ID。
其中41位用于自纪元以来的毫秒数,13位用于分片ID,10位用于自增值。
他们选择使用分片ID而不是用户ID,仅仅是因为只有分片ID适合13位,而用户ID将需要更多的位数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接