如何在Python中生成按时间顺序排列的uid？

Question

这可能吗？我听说Cassandra有类似的东西：https : //datastax.github.io/python-driver/api/cassandra/util.html

我一直在使用与ISO timestamp串联uuid4，但最终太大（58个字符），可能会导致过大杀伤力。

在我的上下文中，保持序列号不起作用（DynamoDB NoSQL）

值得一提的是，对于我的应用程序而言，批量创建/相同秒创建的项目是否随机排列uid都没有关系，只要不折叠即可。

我对最大长度没有具体限制，理想情况下，我希望看到不同长度的碰撞机会不同，但是它必须小于58（我的原始尝试）

与DynamoDB（NoSQL数据库）一起用作排序键

Answer 1

为什么uuid.uuid1不是顺序的

uuid.uuid1(node=None, clock_seq=None) 有效地：

• 60位时间戳（代表之后的100 ns间隔1582-10-15 00:00:00）
• 14位的“时钟序列”
• 48位的“节点信息”（从网卡的mac地址，主机名或RNG生成）。

如果不提供任何参数，则将调用System函数生成uuid。在这种情况下：

• 目前尚不清楚“时钟序列”是顺序的还是随机的。
• 尚不清楚在多个过程中使用它是否安全（可以clock_seq在不同的过程中重复吗？）。在Python 3.7中，此信息现在可用。

如果提供clock_seq或node，则“使用纯python实现”。在这种情况下，即使具有“固定值” clock_seq：

• 对于当前进程中的所有调用，即使在线程执行中，时间戳部分也保证是顺序的。
• clock_seq部分是随机生成的。但是，这并不是至关重要的，因为时间戳是连续且唯一的。
• 对于多个进程而言，这是不安全的（如果在“相同的100 ns时间间隔”内调用uuid1，使用相同的进程调用的进程clock_seq, node可能会返回冲突的值）

重用的解决方案 uuid.uuid1

很容易看出，您可以uuid1通过提供clock_seq或node参数（使用python实现）来进行顺序设置。

import time

from uuid import uuid1, getnode

_my_clock_seq = getrandbits(14)
_my_node = getnode()


def sequential_uuid(node=None):
    return uuid1(node=node, clock_seq=_my_clock_seq)
    # .hex attribute of this value is 32-characters long string


def alt_sequential_uuid(clock_seq=None):
    return uuid1(node=_my_node, clock_seq=clock_seq)


if __name__ == '__main__':
    from itertools import count
    old_n = uuid1()  # "Native"
    old_s = sequential_uuid()  # Sequential

    native_conflict_index = None

    t_0 = time.time()

    for x in count():
        new_n = uuid1()
        new_s = sequential_uuid()

        if old_n > new_n and not native_conflict_index:
            native_conflict_index = x

        if old_s >= new_s:
            print("OOops: non-sequential results for `sequential_uuid()`")
            break

        if (x >= 10*0x3fff and time.time() - t_0 > 30) or (native_conflict_index and x > 2*native_conflict_index):
            print('No issues for `sequential_uuid()`')
            break

        old_n = new_n
        old_s = new_s

    print(f'Conflicts for `uuid.uuid1()`: {bool(native_conflict_index)}')

多个流程问题

但是，如果您正在同一台计算机上运行一些并行进程，则：

• nodeuuid.get_node()所有进程的默认值都相同；
• clock_seq 在某些过程中具有相同可能性的可能性很小（机会为1/16384）

这可能会导致冲突！uuid.uuid1除非可以从Python3.7 访问SafeUUID，否则在同一台计算机上并行使用进程时，通常 要注意这一点。

如果您确保还node为运行此代码的每个并行进程将其设置为唯一值，则不会发生冲突。

即使您使用SafeUUID并将其设置为unique node，但如果它们是在不同进程中生成的，也可以具有非顺序（但唯一）的id。

如果可以接受一些与锁相关的开销，则可以将其存储clock_seq在某些外部原子存储中（例如，存储在“锁定”文件中），并在每次调用时对其进行递增：这样一来node，所有并行进程的值都相同，并且将使id -s顺序。对于所有并行流程都是使用multiprocessing以下命令创建的子流程的情况，clock_seq可以使用来“共享”multiprocessing.Value

因此，您始终必须记住：

• 如果您在同一台计算机上运行多个进程，则必须：

  • 确保的唯一性node。此解决方案的问题：您不能确定在相同的100 ns间隔内生成来自不同进程的顺序ID。但这是在进程启动时执行一次的非常“轻便”的操作，可以通过以下方式实现：通过向默认节点“添加”某些东西，例如int(time.time()*1e9) - 0x118494406d1cc000，或通过从计算机级原子数据库添加一些计数器来实现。

  • 确保“ 一台机器上的所有进程”的“机器级原子clock_seq”相同node。这样，您将有一些“锁定”开销clock_seq，但是即使在相同的100 ns间隔内在不同进程中生成id-s，也保证它们是顺序的（除非您从同一进程中的多个线程调用uuid）。

• 对于不同机器上的进程：

  • 您必须使用一些“全局柜台服务”；

  • 否则不可能在相同的100 ns间隔内在不同计算机上生成顺序ID。

减少ID的大小

生成UUID的一般方法非常简单，因此很容易从头开始实现类似的事情，例如，使用更少的位node_info：

import time
from random import getrandbits

_my_clock_seq = getrandbits(14)
_last_timestamp_part = 0
_used_clock_seq = 0


timestamp_multiplier = 1e7  # I'd recommend to use this value

# Next values are enough up to year 2116:
if timestamp_multiplier == 1e9:
    time_bits = 62  # Up to year 2116, also reduces chances for non-sequential id-s generated in different processes
elif timestamp_multiplier == 1e8:
    time_bits = 60  # up to year 2335
elif timestamp_multiplier == 1e7:
    time_bits = 56  # Up to year 2198.
else:
    raise ValueError('Please calculate and set time_bits')

time_mask = 2**time_bits - 1

seq_bits = 16
seq_mask = 2**seq_bits - 1

node_bits = 12
node_mask = 2**node_bits - 1

max_hex_len = len(hex(2**(node_bits+seq_bits+time_bits) - 1)) - 2  # 21

_default_node_number = getrandbits(node_bits)  # or `uuid.getnode() & node_mask`


def sequential_uuid(node_number=None):
    """Return 21-characters long hex string that is sequential and unique for each call in current process.

    Results from different processes may "overlap" but are guaranteed to
    be unique if `node_number` is different in each process.

    """
    global _my_clock_seq
    global _last_timestamp_part
    global _used_clock_seq
    if node_number is None:
        node_number = _default_node_number
    if not 0 <= node_number <= node_mask:
        raise ValueError("Node number out of range")

    timestamp_part = int(time.time() * timestamp_multiplier) & time_mask
    _my_clock_seq = (_my_clock_seq + 1) & seq_mask

    if _last_timestamp_part >= timestamp_part:
        timestamp_part = _last_timestamp_part
        if _used_clock_seq == _my_clock_seq:
            timestamp_part = (timestamp_part + 1) & time_mask
    else:
        _used_clock_seq = _my_clock_seq

    _last_timestamp_part = timestamp_part

    return hex(
        (timestamp_part << (node_bits+seq_bits))
        |
        (_my_clock_seq << (node_bits))
        |
        node_number
    )[2:]

笔记：

• 也许最好只在数据库中存储整数值（而不是十六进制字符串）
• 如果将其存储为文本/字符，则最好将整数转换为base64字符串，而不是将其转换为十六进制字符串。这样它将更短（21个字符的十六进制字符串？16个字符的b64编码字符串）：

from base64 import b64encode

total_bits = time_bits+seq_bits+node_bits
total_bytes = total_bits // 8 + 1 * bool(total_bits % 8)

def int_to_b64(int_value):
    return b64encode(int_value.to_bytes(total_bytes, 'big'))

碰撞机会

• 单一过程：不可能发生碰撞
• 手动设置唯一性 clock_seq 或node在每个过程中具有唯一性的多个过程：不可能发生冲突

• 随机设置的多个进程node（48位，“固定”时间）：

  • 有可能node在多个过程中发生冲突：

    • 在10000中的2个过程中：〜0.000018％
    • 在100000中的2个过程中：0.0018％

  • 在2个进程中每秒有一次ID与“碰撞”冲突的机会node：

    • 对于100 ns的“时间戳”间隔（默认为uuid.uuid1，在我的代码中为timestamp_multiplier == 1e7）：与3.72e-19 * avg_call_frequency²

    • 对于10 ns的“时间戳”间隔（timestamp_multiplier == 1e8）：与3.72e-21 * avg_call_frequency²