python UUID与雪花ID

在分布式架构中经常需要要使用到唯一的ID值，该ID值的生成一般会要求：全局唯一性、递增性、高可用性、高性能性。这时候常见的方法有使用UUID和雪花算法实现ID两种机制。UUID这个比较好理解，在linux下/etc/fstab中我们经常就会用uuid=xxx代表某个分区。而雪花算法SnowFlake是Twitter公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的ID。这里分别用python来实现上如何实现生成这种某一值。

一、python下生成uuid 

python下直接有个uuid模块，只需提供了以下几种常见的uuid生成方法，可以根据实际需要选择任一种：

>>> import uuid
# make a UUID based on the host ID and current time
>>> uuid.uuid1()    # doctest: +SKIP
UUID('a8098c1a-f86e-11da-bd1a-00112444be1e')
# make a UUID using an MD5 hash of a namespace UUID and a name
>>> uuid.uuid3(uuid.NAMESPACE_DNS, 'python.org')
UUID('6fa459ea-ee8a-3ca4-894e-db77e160355e')
# make a random UUID
>>> uuid.uuid4()    # doctest: +SKIP
UUID('16fd2706-8baf-433b-82eb-8c7fada847da')
# make a UUID using a SHA-1 hash of a namespace UUID and a name
>>> uuid.uuid5(uuid.NAMESPACE_DNS, 'python.org')
UUID('886313e1-3b8a-5372-9b90-0c9aee199e5d')

二、python雪花id生成

雪花id的生成原理如下：

组成部分（64bit） 

1.第一位 占用1bit，其值始终是0，没有实际作用。 

2.时间戳 占用41bit，精确到毫秒，总共可以容纳约69年的时间。 

3.工作机器id 占用10bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID，做多可以容纳1024个节点。 4.序列号 占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生4096个ID。 

SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢：： 同一毫秒的ID数量 = 1024 X 4096 = 4194304

代码如下：

# coding: utf-8
import time
class InvalidSystemClock(Exception):
    """
    时钟回拨异常
    """
    pass
# 64位ID的划分
WORKER_ID_BITS = 5
DATACENTER_ID_BITS = 5
SEQUENCE_BITS = 12
# 最大取值计算
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)  # 2**5-1 0b11111
MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS)
# 移位偏移计算
WOKER_ID_SHIFT = SEQUENCE_BITS
DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS
# 序号循环掩码
SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)
# 开始时间截 (2015-01-01)
TWEPOCH = 1420041600000
class IdWorker(object):
    """
    用于生成IDs
    """
    def __init__(self, datacenter_id, worker_id, sequence=0):
        """
        初始化
        :param datacenter_id: 数据中心（机器区域）ID
        :param worker_id: 机器ID
        :param sequence: 起始序号
        """
        # sanity check
        if worker_id > MAX_WORKER_ID or worker_id < 0:
            raise ValueError('worker_id值越界')
        if datacenter_id > MAX_DATACENTER_ID or datacenter_id < 0:
            raise ValueError('datacenter_id值越界')
        self.worker_id = worker_id
        self.datacenter_id = datacenter_id
        self.sequence = sequence
        self.last_timestamp = -1  # 上次计算的时间戳
    def _gen_timestamp(self):
        """
        生成整数时间戳
        :return:int timestamp
        """
        return int(time.time() * 1000)
    def get_id(self):
        """
        获取新ID
        :return:
        """
        timestamp = self._gen_timestamp()
        # 时钟回拨
        if timestamp < self.last_timestamp:
            raise InvalidSystemClock
        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & SEQUENCE_MASK
            if self.sequence == 0:
                timestamp = self._til_next_millis(self.last_timestamp)
        else:
            self.sequence = 0
        self.last_timestamp = timestamp
        new_id = ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | (self.datacenter_id << DATACENTER_ID_SHIFT) | \
                 (self.worker_id << WOKER_ID_SHIFT) | self.sequence
        return new_id
    def _til_next_millis(self, last_timestamp):
        """
        等到下一毫秒
        """
        timestamp = self._gen_timestamp()
        while timestamp <= last_timestamp:
            timestamp = self._gen_timestamp()
        return timestamp
if __name__ == '__main__':
    worker = IdWorker(0, 0)
    print(worker.get_id())

三、uuid和雪花算法的比较

相比常见的64位数字字母随机数的UUID，使用雪花算法（snowflake）生成雪花数的方法更好，具体比较结果如下：

	UUID	雪花数
全局唯一	支持	支持
有序，可以支持排序、比较	无序	支持，大致有序，按时间排序
节约存储空间	64位数字字母随机组合的字符串	19位正整数，更节约存储空间
根据UID查询速度快，且稳定	数据库根据索引查询速度不稳定	数据库根据索引查询速度快且稳定
防止被恶意推测	支持	支持
带有业务属性	无	无
限制条件	全局唯一性依赖于生成随机数的种子和随机数的长度	需要单独部署雪花数生成器；依赖于生成器的时间戳。