Python 二进制 雪花算法

python

1 雪花算法-Snowflake

1.1 雪花算法简介

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

000000000 00000000 00000000 00000000 00000000 000000000 0000000000 0000
1bit-不用41bit-时间戳10bit-工作机器id12bit-序列号

  • 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可以用来进行扩展。

1bit-符号位41bit-时间戳3bit-机房7bit-机器id10bit-循环位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 各前缀

进制基数(radix)前缀示例
二进制 binary0b 0B0b11 = 2+1=3
八进制 octal0o 0O 00o11 = 8+1=9
十进制 decimal无前缀11 = 11
十六进制 hex0x 0X0x11

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

回到顶部