Python 二进制 雪花算法

• Z时代
• 2024-01-10
• 分类：综合

1 雪花算法-Snowflake

1.1 雪花算法简介

Snowflake是Twitter提出来的一个算法，其目的是生成一个64bit的整数:

• 1bit:一般是符号位，不做处理

• 41bit:用来记录时间戳，这里可以记录69年，如果设置好起始时间比如今年是2018年，那么可以用到2089年，到时候怎么办？要是这个系统能用69年，我相信这个系统早都重构了好多次了。

• 10bit:10bit用来记录机器ID，总共可以记录1024台机器，一般用前5位代表数据中心，后面5位是某个数据中心的机器ID

• 12bit:循环位，用来对同一个毫秒之内产生不同的ID，12位可以最多记录4095个，也就是在同一个机器同一毫秒最多记录4095个，多余的需要进行等待下毫秒。

1.3 雪花算法特点

--- 优点：高性能、低延迟、按时间有序、生成效率极高
--- 缺点：要求机器时钟同步（到秒级即可）
--- 适用场景：分布式应用环境的数据主键

1.2 雪花算法实例

上面只是一个将64bit划分的标准，当然也不一定这么做，可以根据不同业务的具体场景来划分，比如下面给出一个业务场景：

1. 服务目前QPS10万，预计几年之内会发展到百万。
2. 当前机器三地部署，上海，北京，深圳都有。
3. 当前机器10台左右，预计未来会增加至百台。
   

   这个时候我们根据上面的场景可以再次合理的划分62bit,QPS几年之内会发展到百万，那么每毫秒就是千级的请求，目前10台机器那么每台机器承担百级的请求，为了保证扩展，后面的循环位可以限制到1024，也就是2^10，那么循环位10位就足够了。

机器三地部署我们可以用3bit总共8来表示机房位置，当前的机器10台，为了保证扩展到百台那么可以用7bit 128来表示，时间位依然是41bit,那么还剩下64-10-3-7-41-1 = 2bit,还剩下2bit可以用来进行扩展。

• 时钟回拨
  

  因为机器的原因会发生时间回拨，我们的雪花算法是强依赖我们的时间的，如果时间发生回拨，有可能会生成重复的ID，在我们上面的nextId中我们用当前时间和上一次的时间进行判断，如果当前时间小于上一次的时间那么肯定是发生了回拨，算法会直接抛出异常.

1.3 雪花算法实现代码

python"># Twitter's Snowflake algorithm implementation which is used to generate distributed IDs.
# https://github.com/twitter-archive/snowflake/blob/snowflake-2010/src/main/scala/com/twitter/service/snowflake/IdWorker.scala
import time
import logging
from .exceptions import InvalidSystemClock
# 64位ID的划分
WORKER_ID_BITS = 5 # 10bit-工作机器id
DATACENTER_ID_BITS = 5
SEQUENCE_BITS = 12 # 12bit-序列号
# 最大取值计算
# -1 ^ (-1 << 5)  ==> 得到5位都是1的二进制数
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)  # 2**5-1 0b11111
MAX_DATACENTER_ID = -1 ^ (-1 << DATACENTER_ID_BITS)
# 移位偏移计算
# 1bit符号位 + 41bit时间戳 + 5bit DATACENTER_ID + 5bit WOKER_ID + 12bit序列号
WOKER_ID_SHIFT = SEQUENCE_BITS # 12 即从后往前间隔12位
DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS # 12+5
TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS # 12+5+5
# 序号循环掩码
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):
        """
        生成整数时间戳
        time.time()单位秒，*1000后单位变毫秒
        :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 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(1, 2, 0)
    print(worker.get_id())

同文件夹下建立exceptions.py

class InvalidSystemClock(Exception):
    """
    时钟回拨异常
    """
    pass

配置文件中添加,对应的是机器ID和序列号

    # Snowflake ID Worker 参数
    DATACENTER_ID = 0
    WORKER_ID = 0
    SEQUENCE = 0

2 二进制、八进制、十六进制

2.1 各前缀

2.2 二进制

python负数的二进制表示

Python里的数是无所谓Overflow的，即没有位数限制，因此也就无所谓补码，因为补码都是相对于位数来说的，32位补码和16位补码，肯定是不一样的。

但是这样就导致了一个问题，就是无法直接得到32位二进制补码。

python实现补码

设计一个函数，使得可以同时对正数和负数使用得到正确的补码

• bin() 返回一个整数 int 或者长整数 long int 的二进制表示

>>>bin(-1)
'-0b1'
>>>bin(3)
'0b11'

二进制运算：异或

题：负数异或 -1 ^ -32

• 负数用补码表示原码，即补码就是负数在计算机中的二进制表示方法 = 符号位不变，其余取反再加1

• 正数的补码=原码

-1的补码=反码+1，反码的符号位不变
-1       = 1000 0001
-1的反码  = 1111 1110
-1的补码  = 1111 1111

-32的补码=反码+1，反码的符号位不变
-32      = 1010 0000
-32的反码 = 1101 1111
-32的补码 = 1110 0000

计算异或
1111 1111
1110 0000
结果为
0001 1111 = -1 ^ -32 --> 31

关于负数二进制的总结：

• 十进制变二进制：原码-->反码-->加一（补码）
• 二进制变十进制：减一-->反码-->原码

# 最大取值计算
# -1 ^ (-1 << 5)  ==> 得到5位都是1的二进制数
WORKER_ID_BITS = 5
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS)  # 2**5-1？ 0b11111

按位异或的常见用途

(1) 使某些特定的位翻转

例如对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算。

10100001^00000110 = 10100111

(2) 实现两个值的交换，而不必使用临时变量。

例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：

a = a^b； 　　//a=10100111
b = b^a； 　　//b=10100001
a = a^b； 　　//a=00000110

(3) 在汇编语言中经常用于将变量置零：

xor a，a

(4) 快速判断两个值是否相等

举例1: 判断两个整数a，b是否相等，则可通过下列语句实现：

return ((a ^ b) == 0)

按位与常见用法

(1)判断奇数偶数

4&1   # 0 是偶数 1是奇数

2.3 反码和补码

反码

• 正数的反码还是等于原码；负数的反码就是它的原码除符号位外，按位取反

补码

• 在补码表示中，用符号位表示数值的正负，形式与原码的表示相同，即0为正，1为负。但补码的符号可以看做是数值的一部分参加运算
• 由于补码表示中的符号位可以与数值位一起参加运算，并且可以将减法转换为加法进行运算，简化了运算过程，因此计算机中均采用补码进行加减运算

• 因为负数的反码加上这个负数的绝对值正好等于1111，在加1，就是10000，也就是四位二进数的模，而负数的补码是它的绝对值的同余数，可以通过模减去负数的绝对值得到它的补码，所以负数的补码就是它的反码+1。

以上是 Python 二进制 雪花算法 的全部内容， 来源链接： utcz.com/z/387769.html