首页 > 编程语言 > 详细

从主键id生成方案到雪花算法的python详解

时间:2021-03-06 12:59:05      阅读:35      评论:0      收藏:0      [点我收藏+]

我们在分布式环境下为什么用雪花算法去生成主键id, 为什么单机情况下推荐mysql自增id而不推荐使用uuid,雪花算法的具体实现是怎么样的?接下来详细讲述一下。

1、概述

分布式id方案那么多种,我们该以什么样的角度去思考并选择,下面我给出我的出发点。

  • 1.1、常用的索引方案

    • mysql自增id: 这是mysql官方推荐的方案(适合单机版)
    • uuid:数据量小的时候可以使用(不推荐)
    • redis自增id:分布式id的一种方案
    • 雪花算法:分布式id的解决方案(推荐)
  • 1.2、什么样的方案适合做索引

    • 唯一:生成出来的序列必须是唯一的
    • 趋势递增:生成出来的序列可以不是连续递增,但必须是趋势递增的
    • 占用字段小:索引占用的空间尽量小
    • 分布式:分布式环境下生成的id要唯一
    • 高并发:能满足高并发环境生成id的要求
    • 高可用:要高可用,尽量不依赖外界

综上所述,如果我们要选择一个分布式id生成方案雪花算法是最好的选择,其中mysql自增id在分库分表时的id不是唯一(pass),uuid方案它生成的id不是递增的在索引查找时效率慢,reids自增id方案,因为redis的计算层面是单线程的所以可以生成唯一且递增的id又符合分布式要求,目前有一些公司有在使用这种方案,但是这种方案我们必须依赖redis增加我们的不可控的因素,所以不是很推荐。

2、雪花算法的实现

雪花算法是Twitter提出来的算法,看完真的很精妙,它最终会生成一个64bit的整数,最终存到数据库就只占用8字节。

2.0 组成

技术分享图片

  • 1bit: 一般是符号位,代表正负数的所以这一位不做处理
  • 41bit:这个部分用来记录时间戳,如果从1970-01-01 00:00:00来计算开始时间的话,它可以记录到2039年,足够我们用了,并且后续我们可以设置起始时间,这样就不用担心不够的问题, 这一个部分是保证我们生辰的id趋势递增的关键。
  • 10bit:这是用来记录机器id的, 默认情况下这10bit会分成两部分前5bit代表数据中心,后5bit代表某个数据中心的机器id,默认情况下计算大概可以支持32*32 - 1= 1023台机器。
  • 12bit:循环位,来对应1毫秒内产生的不同的id, 大概可以满足1毫秒并发生成2^12-1=4095次id的要求。

2.1 实现代码

import time
import logging



# 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)

# Twitter元年时间戳
TWEPOCH = 1288834974657


logger = logging.getLogger(‘flask.app‘)


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:
            logging.error(‘clock is moving backwards. Rejecting requests until{}‘.format(self.last_timestamp))
            raise Exception

        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


def test():
    for i in range(10):
        id = worker.get_id()
        print(id)


if __name__ == ‘__main__‘:
    from threading import Thread
    worker = IdWorker(1, 1, 0)
    l = list()
    for i in range(2):
        t = Thread(target=test)
        t.start()
        l.append(t)
    for t in l:
        t.join()

2.2 位运算简示

# 经过计算各个部分可以得出(以下全部为二进制)

# 1、时间戳部分,

time = b‘10101010101010101010101010101010101010101000000000000000000000‘

# 2、机器id部分,假设是1机器中心的1机器生成id

dev = b‘000000000000000000000000000000000000000000000100001000000000000‘

# 3、在本毫秒生成的第一个id为

seq = b‘000000000000000000000000000000000000000000000000000000000000001‘

# 从上我们得出每个部分二进制的值,那我们进行或位运算,两个位同为0时才为0,只要有1则为1

id = time | dev | seq

# 经过上面计算可以得出
id = b‘10101010101010101010101010101010101010101000010000100000000001‘

# 然后二进制id转成整形以后就变成一下

id = 1368043503778664451

# 这样就得到了我们的id

3、缺点及方案

看完上述方案,可能察觉到雪花算法方案非常依赖机器上的时间戳,你想如果机器上的时钟发生回拨的话,极有可能生成重复的id。

为解决以上问题各大厂都有对应的开源方案,可以自己进行查找。

从主键id生成方案到雪花算法的python详解

原文:https://www.cnblogs.com/lifei01/p/14490119.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!