使用python实现分布式自增id算法

这两天在看大规模分布式系统架构与设计实战,让我受益良多,尤其是从底层的架构上了解了分布式整体架构,及其各个功能组件是如何协调的。 书里面多次的提到了分布式id,但是没有阐述是分布式自增id是怎么玩的… …   记得去年去百度面试也有问过分布式ID的事情,我当时也说过不不少的解决的方案…  至于结果,不知道了….
说起分布式自增id,那么我们就要说起,snowflake了。 Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序,我们可以通过一定的索引来range id,在分布式系统中不同机器产生的id必须不同。 

我自己觉得分布式自增ID,方案还是不少的。 最简单就是api接口模式,在server端进行有序计算id 。   来说下redis的方案,我们可以在每个分布式的节点上,或者是每个节点的每个进程都依靠redis来做自增的id。很简单的用redis incrby来自增,redis是个单线程的server,也能保持原子操作。  但是这的缺点很明显,每个节点每个进程都要和redis操作,这本身就花费些时间,每次都从redis获取数据。 

用过MongoDB的人都知道,他的_objectid的生成方式很好,专为分布式而设计的ID生成: 机器编号+进程PID+当前时间戳+自增,snowflake跟他很像,然后他的id也是可以sort的。  


扯了这么多的方法,再来说下Twitter的snowflake。  它是使用 time – 41 bits + configured machine id – 10 bits + sequence number – 12 bits的形式分配id,共63位,最高部分使用毫秒级的时间戳,保证了一定程度的有序性,机器标示使用10位,最多可容纳1024个分配器,最后的12位序列号可以支持在1ms内产生4096个不重复的id。从工程角度,这些都足够用了。但对系统时间的依赖性非常强,需要关闭ntp的时间同步功能,或者当检测到ntp时间调整后,拒绝分配id。

关于分布式自增id的文章,出处是 http://xiaorui.cc/?p=1783

个人认为snowflake的算法还是不错的,其实本身不复杂,复杂的是你客户端怎么用。 但是snowflake对于那种喜欢用sort id的人来说,有些弊端,需要数据库层面做索引,或者是hhbase的rowkey那样,可以使用前缀来回的扫描。 下面是python的实现方式,首先用melt返回snowflake几个值…… 

import time
from snowflake import *

snowflake_id = 345063379196600321
timestamp, data_center, worker, sequence = melt(snowflake_id)
print 'the tweet was created at %s' % local_datetime(timestamp)

print snowflake(time.time()*1000, 1, 0, 0)

具体的实现方法  , 源码 https://github.com/falcondai/python-snowflake/blob/master/snowflake.py

import datetime

# twitter's snowflake parameters
twepoch = 1288834974657L
datacenter_id_bits = 5L
worker_id_bits = 5L
sequence_id_bits = 12L
max_datacenter_id = 1 << datacenter_id_bits
max_worker_id = 1 << worker_id_bits
max_sequence_id = 1 << sequence_id_bits
max_timestamp = 1 << (64L - datacenter_id_bits - worker_id_bits - sequence_id_bits)

def make_snowflake(timestamp_ms, datacenter_id, worker_id, sequence_id, twepoch=twepoch):

    sid = ((int(timestamp_ms) - twepoch) % max_timestamp) << datacenter_id_bits << worker_id_bits << sequence_id_bits
    sid += (datacenter_id % max_datacenter_id) << worker_id_bits << sequence_id_bits
    sid += (worker_id % max_worker_id) << sequence_id_bits
    sid += sequence_id % max_sequence_id

    return sid

def melt(snowflake_id, twepoch=twepoch):
    """inversely transform a snowflake id back to its parts."""
    sequence_id = snowflake_id & (max_sequence_id - 1)
    worker_id = (snowflake_id >> sequence_id_bits) & (max_worker_id - 1)
    datacenter_id = (snowflake_id >> sequence_id_bits >> worker_id_bits) & (max_datacenter_id - 1)
    timestamp_ms = snowflake_id >> sequence_id_bits >> worker_id_bits >> datacenter_id_bits
    timestamp_ms += twepoch

    return (timestamp_ms, int(datacenter_id), int(worker_id), int(sequence_id))

def local_datetime(timestamp_ms):
    """convert millisecond timestamp to local datetime object."""
    return datetime.datetime.fromtimestamp(timestamp_ms / 1000.)

if __name__ == '__main__':
    import time
    t0 = int(time.time() * 1000)
    print local_datetime(t0)
    assert(melt(make_snowflake(t0, 0, 0, 0))[0] == t0)

其实我更推荐大家用Snowflake的方式,因为有不少的场景下是客户端来控制频次,比如攒了1000条数据再推送,那这时候客户端会把数据首先追加id,然后暂时缓冲到自己队列里面,然后由另一个线程再刷数据入库。   


大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码,感谢!
另外再次标注博客原地址  xiaorui.cc

4 Responses

  1. hugo 2018年2月10日 / 上午10:11

    经测试,你这样写法,一个while 1 生成30多个重复uuid

    • hugo 2018年2月10日 / 上午10:26

      local_datetime 这个def也没用到

      • rfyiamcool 2018年2月10日 / 下午6:28

        那是github上的一个例子…

    • rfyiamcool 2018年2月10日 / 下午6:31

      当初从github引入的一个方法,https://github.com/falcondai/python-snowflake

发表评论

邮箱地址不会被公开。 必填项已用*标注