β

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

峰云就她了 505 阅读

这两天在看大规模分布式系统架构与设计实战,让我受益良多,尤其是从底层的架构上了解了分布式整体架构,及其各个功能组件是如何协调的。 书里面多次的提到了分布式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,然后暂时缓冲到自己队列里面,然后由另一个线程再刷数据入库。

作者:峰云就她了
专注于运维平台化、运维自动化、python运维
原文地址:使用python实现分布式自增id算法, 感谢原作者分享。