Twitter的分布式自增ID算法Snowflake

标签: twitter 分布 id | 发表时间:2015-05-09 11:52 | 作者:yuanhsh
出处:http://www.iteye.com

Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。

Snowflake算法核心

时间戳工作机器id序列号组合在一起。

 

snowflake-64bit

 

除了最高位bit标记为不可用以外,其余三组bit占位均可浮动,看具体的业务需求而定。 默认情况下41bit的时间戳可以支持该算法使用到2082年,10bit的工作机器id可以支持1023台机器,序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

 

Snowflake – 时间戳

这里时间戳的细度是毫秒级,具体代码如下,建议使用64位linux系统机器,因为有 vdso,gettimeofday()在用户态就可以完成操作,减少了进入内核态的损耗。

1
2
3
4
5
6
uint64_t generateStamp()
{
     timeval tv;
     gettimeofday(&tv, 0);
     return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;
}

默认情况下有41个bit可以供使用,那么一共有T(1llu << 41)毫秒供你使用分配,年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用,那么根据同样的算法最后年份 = 17.4年。

Snowflake – 工作机器id

严格意义上来说这个bit段的使用可以是进程级, 机器级的话你可以使用MAC地址来唯一标示工作机器工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少,可以使用配置文件来设置这个id是一个不错的选择,如果机器过多配置文件的维护是一个灾难性的事情。

这里的解决方案是需要一个工作id分配的进程,可以使用自己编写一个简单进程来记录分配id,或者利用Mysql auto_increment机制也可以达到效果。

snowflake - 工作id

 

工作进程与工作id分配器只是在工作进程启动的时候交互一次,然后工作进程可以自行将分配的id数据落文件,下一次启动直接读取文件里的id使用。

PS:这个工作机器id的bit段也可以进一步拆分,比如用前5个bit标记进程id,后5个bit标记线程id之类:D

Snowflake – 序列号

序列号就是一系列的自增id(多线程建议使用atomic),为了处理在同一毫秒内需要给多条消息分配id,若同一毫秒把序列号用完了,则“等待至下一毫秒”。

1
2
3
4
5
6
7
8
uint64_t waitNextMs(uint64_t lastStamp)
{
     uint64_t cur = 0;
     do {
         cur = generateStamp();
     } while (cur <= lastStamp);
     return cur;
}

 

总体来说,是一个很高效很方便的GUID产生算法,一个int64_t字段就可以胜任,不像现在主流128bit的GUID算法,即使无法保证严格的id序列性,但是对于特定的业务,比如用做游戏服务器端的GUID产生会很方便。另外,在多线程的环境下,序列号使用atomic可以在代码实现上有效减少锁的密度。

 

结构为:

   0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---0000000000 00

在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。

这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。

 

public class IdWorker {
    private final long        workerId;
    private final static long twepoch            = 1361753741828L;
    private long              sequence           = 0L;
    private final static long workerIdBits       = 4L;
    private final static long maxWorkerId        = -1L ^ -1L << workerIdBits;
    private final static long sequenceBits       = 10L;

    private final static long workerIdShift      = sequenceBits;
    private final static long timestampLeftShift = sequenceBits + workerIdBits;
    private final static long sequenceMask       = -1L ^ -1L << sequenceBits;

    private long              lastTimestamp      = -1L;

    public IdWorker(final long workerId) {
        super();
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format(
                "worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = this.timeGen();
        if (this.lastTimestamp == timestamp) {
            this.sequence = (this.sequence + 1) & sequenceMask;
            if (this.sequence == 0) {
                System.out.println("###########" + sequenceMask);
                timestamp = this.tilNextMillis(this.lastTimestamp);
            }
        } else {
            this.sequence = 0;
        }
        if (timestamp < this.lastTimestamp) {
            try {
                throw new Exception(String.format(
                    "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    this.lastTimestamp - timestamp));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        this.lastTimestamp = timestamp;
        long nextId = ((timestamp - twepoch << timestampLeftShift))
                      | (this.workerId << workerIdShift) | (this.sequence);
        //  System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"
        //       + timestampLeftShift + ",nextId:" + nextId + ",workerId:"
        //       + workerId + ",sequence:" + sequence);
        return nextId;
    }

    private long tilNextMillis(final long lastTimestamp) {
        long timestamp = this.timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) throws InterruptedException {
        IdWorker worker2 = new IdWorker(2);
        System.out.println(worker2.nextId());
        Thread.sleep(1000L);
        System.out.println(worker2.nextId());
    }
}

 

 

Reference:

http://www.lanindex.com/twitter-snowflake/



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [twitter 分布 id] 推荐:

Twitter的分布式自增ID算法Snowflake

- - 企业架构 - ITeye博客
Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同. Snowflake算法核心. 把 时间戳, 工作机器id, 序列号组合在一起.

分布式高可用id服务器设计实现

- - C++博客-首页原创精华区
服务端/后台开发中如何生成id是每个开发者都会遇到的问题,在电商、游戏领域尤其突出. 如何保证生成id的唯一性、可靠性、高可用性,如何组织id的格式,在不同的应用场景和限制下实现方式也不尽相同. 我们的应用场景类似电商,在一个订单的生命周期内,有多个逻辑需要生成各自的id,还要考虑到可读性和灵活性,我们决定实现一个独立的id服务.

Leaf——美团点评分布式ID生成系统

- - 美团点评技术团队
在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识. 如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一个唯一ID来标识一条数据或消息,数据库的自增ID显然不能满足需求;特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识. 此时一个能够生成全局唯一ID的系统是非常必要的.

SnowFlake 分布式ID生成算法Java实现

- - ITeye博客
SnowFlake 分布式ID生成Java实现. SnowFlake不依赖第三方介质,不像基于ZK,Redis等,每次用完一个区间还得通过网络去获取下一个区间,效率较低,基于SnowFlake的分布式ID生成是目前我见过的最快的. SnowFlake生成的是一个64位的数字,其中42位时间戳,接下来10位是自定义的数,其作用就是区分集群中的所有机器,最后12位是毫秒内序列,集群内每个机器能够在1毫秒内生成2^12 - 1个ID.

分布式系统中唯一 ID 的生成方法

- - 文章 – 伯乐在线
本文主要介绍在一个分布式系统中, 怎么样生成全局唯一的 ID. 在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现..

分布式系统中, 怎么样生成全局唯一的 ID

- - zzm
在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.. 但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:.

产生Id

- - 研发管理 - ITeye博客
// worker编号最大值,决定支持的部署节点数量. // 毫秒内自增位数,每毫秒最大序号支持65535. // worker编号偏移量. // 毫秒基线:2015-01-01 00:00:00. * 从环境变量中获取worker编号,每个部署环境编号不能重复. * 每个部署环境编号不能重复. * @param workerId Worker编号.

id Software发布《狂怒(Rage)》

- ArmadilloCommander - Solidot
id Software发布了容量为21GB的第一人称射击游戏《狂怒(Rage)》. 游戏基于id Tech 5引擎,背景是世界末日后的未来. 目前对它的评价好坏参半,媒体综合评分80左右,玩家评分相似或更低. 在游戏中,玩家将扮演一位小行星Apophis撞击地球后的幸存者. 在灾难发生前,全世界展开合作将包括科学家在内的精英冰冻在地下,以在灾难后重建地球.

小米手机ID简介

- miyizs - Billwang 工业设计
      小米手机是小米公司(全称北京小米科技有限责任公司)专为发烧友级手机控打造的 一款高品质智能手机. 下面我们将对其做一个简单的介绍.       小米手机的外观设计走的是简约内敛路线,直板加圆润的边角让其显得简单清爽. 小米手机配置了,1.5GHz双核处理器、1G RAM、4英寸夏普屏、800万像素摄像头以及大容量电池.