SnowFlake方案 (美团的leaf和百度的UidGenerator都使用这种算法,leaf也支持数据库)

算法简介

SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图:

  • 1位,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0
  • 41位,用来记录时间戳(毫秒)。
    • 41位可以表示241−1241−1个数字,
    • 如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至 241−1241−1,减1是因为可表示的数值范围是从0开始算的,而不是1。
    • 也就是说41位可以表示241−1241−1个毫秒的值,转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69(241−1)/(1000∗60∗60∗24∗365)=69年
  • 10位,用来记录工作机器id。
    • 可以部署在210=1024210=1024个节点,包括5位datacenterId和5位workerId
    • 5位(bit)可以表示的最大正整数是25−1=3125−1=31,即可以用0、1、2、3、….31这32个数字,来表示不同的datecenterId或workerId
  • 12位,序列号,用来记录同毫秒内产生的不同id。
    • 12位(bit)可以表示的最大正整数是212−1=4095212−1=4095,即可以用0、1、2、3、….4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号
      由于在Java中64bit的整数是long类型,所以在Java中SnowFlake算法生成的id就是long来存储的。
      SnowFlake可以保证:
  • 所有生成的id按时间趋势递增
  • 整个分布式系统内不会产生重复id(因为有datacenterId和workerId来做区分)

优缺点分析

优点:快(哈哈,天下武功唯快不破)。没有啥依赖,实现也特别简单。知道原理之后可以根据实际情况调整各各位段,方便灵活。
缺点:只能趋势递增。(有些也不叫缺点,网上有些如果绝对递增,竞争对手中午下单,第二天在下单即可大概判断该公司的订单量,危险!!!)依赖机器时间,如果发生回拨会导致可能生成id重复。
下面重点讨论时间回拨问题。snowflake算法时间回拨问题思考由于存在时间回拨问题,但是他又是那么快和简单,我们思考下是否可以解决呢?
在网上找了一圈没有发现具体的解决方案,但是找到了一篇美团不错的文章:Leaf——美团点评分布式ID生成系统(https://tech.meituan.com/MT_Leaf.html)文章很不错,可惜并没有提到时间回拨如何具体解决。下面看看零度的一些思考:分析时间回拨产生原因
第一:人物操作,在真实环境一般不会有那个傻逼干这种事情,所以基本可以排除。
第二:由于有些业务等需要,机器需要同步时间服务器(在这个过程中可能会存在时间回拨,查了下我们服务器一般在10ms以内(2小时同步一次))。解决方法由于是分布在各各机器自己上面,如果要几台集中的机器(并且不做时间同步),那么就基本上就不存在回拨可能性了(曲线救国也是救国,哈哈),但是也的确带来了新问题,各各结点需要访问集中机器,要保证性能,百度的uid-generator产生就是基于这种情况做的(每次取一批回来,很好的思想,性能也非常不错)https://github.com/baidu/uid-generator。
如果到这里你采纳了,基本就没有啥问题了,你就不需要看了,如果你还想看看零度自己的思考可以继续往下看看(部分问题,但是引入了一些其他问题和依赖。是零度的思考,期待更多的大佬给点建议。时间问题回拨的解决方法:当回拨时间小于15ms,就等时间追上来之后继续生成。当时间大于15ms时间我们通过更换workid来产生之前都没有产生过的来解决回拨问题。首先把workid的位数进行了调整(15位可以达到3万多了,一般够用了)

Snowflake算法稍微调整下位段:sign(1bit)
固定1bit符号标识,即生成的畅途分布式唯一id为正数。delta seconds (38 bits)
当前时间,相对于时间基点”2017-12-21″的增量值,单位:毫秒,最多可支持约8.716年worker id (15 bits)
机器id,最多可支持约3.28万个节点。sequence (10 bits)
每秒下的并发序列,10 bits,这个算法单机每秒内理论上最多可以生成1000*(2^10),也就是100W的ID,完全能满足业务的需求。由于服务无状态化关系,所以一般workid也并不配置在具体配置文件里面,看看我这篇的思考,为什么需要无状态化。高可用的一些思考和理解,这里我们选择redis来进行中央存储(zk、db)都是一样的,只要是集中式的就可以。下面到了关键了:
现在我把3万多个workid放到一个队列中(基于redis),由于需要一个集中的地方来管理workId,每当节点启动时候,(先在本地某个地方看看是否有 借鉴弱依赖zk 本地先保存),如果有那么值就作为workid,如果不存在,就在队列中取一个当workid来使用(队列取走了就没了 ),当发现时间回拨太多的时候,我们就再去队列取一个来当新的workid使用,把刚刚那个使用回拨的情况的workid存到队列里面(队列我们每次都是从头取,从尾部进行插入,这样避免刚刚a机器使用又被b机器获取的可能性)。有几个问题值得思考:如果引入了redis为啥不用redis下发id?(查看分布式系统唯一ID生成方案汇总会获得答案,我们这里仅仅是用来一致性队列的,能做一致性队列的基本都可以)。引入redis就意味着引入其他第三方的架构,做基础框架最好是不要引用(越简单越好,目前还在学习提高)。redis一致性怎么保证?(redis挂了怎么办,怎么同步,的确值得商榷。可能会引入会引入很多新的小问题)

其他的坑

  • 如果请求发号器的QPS不高,比如发号器没毫秒只发一个ID,可能会造成ID的末位永远是1,分库分表使用ID作为分区键会造成分库分表的不均匀。解决方法是:
    1. 时间戳不记录毫秒而是记录到秒,在一个时间区间里多发几个号。
    2. 生成序列号的起始号可以做一下随机,这一秒是21,下一秒是30,尽量平衡。

java实现的代码参考如下:


/**
 * snowflake的java版本
 *https://segmentfault.com/a/1190000011282426
 * https://www.cnblogs.com/relucent/p/4955340.html
 *
 * 1位,不用。二进制中最高位为1的都是负数,但是我们生成的id一般都使用整数,所以这个最高位固定是0
 * 41位,用来记录时间戳(毫秒)。

 * 41位可以表示$2^{41}-1$个数字,
 * 如果只用来表示正整数(计算机中正数包含0),可以表示的数值范围是:0 至 $2^{41}-1$,减1是因为可表示的数值范围是从0开始算的,而不是1。
 * 也就是说41位可以表示$2^{41}-1$个毫秒的值,转化成单位年则是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
 * 10位,用来记录工作机器id。

 * 可以部署在$2^{10} = 1024$个节点,包括5位datacenterId和5位workerId
 * 5位(bit)可以表示的最大正整数是$2^{5}-1 = 31$,即可以用0、1、2、3、....31这32个数字,来表示不同的datecenterId或workerId
 * 12位,序列号,用来记录同毫秒内产生的不同id。

 * 12位(bit)可以表示的最大正整数是$2^{12}-1 = 4095$,即可以用0、1、2、3、....4094这4095个数字,来表示同一机器同一时间截(毫秒)内产生的4095个ID序号
 */
public class IdWorker {
    private long workerId;
    private long datacenterId;
    private long sequence;

    public IdWorker(long workerId, long datacenterId, long sequence){
        // sanity check for workerId
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
        }
        System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }
    //起始时间戳,用于用当前时间戳减去这个时间戳,算出偏移量
    private long twepoch = 1288834974657L;
    //workerId占用的位数:5
    private long workerIdBits = 5L;
    //datacenterId占用的位数:5
    private long datacenterIdBits = 5L;
    //位运算得出workIdBits位的最大整数 这里结果是31
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    //位运算得出datacenterits位的最大整数,这里结果是31
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    //序列在id中占的位数
    private long sequenceBits = 12L;
    //机器ID向左移12位
    private long workerIdShift = sequenceBits;
    //数据标识id向左移17位(12+5)
    private long datacenterIdShift = sequenceBits + workerIdBits;
    //时间截向左移22位(5+5+12)
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    //生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    public long getWorkerId(){
        return workerId;
    }

    public long getDatacenterId(){
        return datacenterId;
    }

    public long getTimestamp(){
        return System.currentTimeMillis();
    }

    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    lastTimestamp - timestamp));
        }
        //如果是同一时间生成的,则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            //用mask防止溢出,保证序列号是0-4095
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
            //时间戳改变,毫秒内序列重置
        } else {
            sequence = 0;
        }
        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }
    /**
     * 阻塞到下一个毫秒,直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

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

    //---------------测试---------------
    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1,1,1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }
}

百度 uid-generator

https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。

在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。

依赖版本:Java8及以上版本, MySQL(内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖)
定义不同的snowflake的位数


Snowflake算法描述:指定机器 & 同一时刻 & 某一并发序列,是唯一的。据此可生成一个64 bits的唯一ID(long)。默认采用上图字节分配方式:

sign(1bit)
固定1bit符号标识,即生成的UID为正数。

delta seconds (28 bits)
当前时间,相对于时间基点”2016-05-20″的增量值,单位:秒,最多可支持约8.7年

worker id (22 bits)
机器id,最多可支持约420w次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。

sequence (13 bits)
每秒下的并发序列,13 bits可支持每秒8192个并发。

数据库产生算法

美团的leaf方案
Leaf特性Leaf在设计之初就秉承着几点要求:全局唯一,绝对不会出现重复的ID,且ID整体趋势递增。高可用,服务完全基于分布式架构,即使MySQL宕机,也能容忍一段时间的数据库不可用。高并发低延时,在CentOS 4C8G的虚拟机上,远程调用QPS可达5W+,TP99在1ms内。接入简单,直接通过公司RPC服务或者HTTP调用即可接入。Leaf诞生Leaf第一个版本采用了预分发的方式生成ID,即可以在DB之上挂N个Server,每个Server启动时,都会去DB拿固定长度的ID List。这样就做到了完全基于分布式的架构,同时因为ID是由内存分发,所以也可以做到很高效。接下来是数据持久化问题,Leaf每次去DB拿固定长度的ID List,然后把最大的ID持久化下来,也就是并非每个ID都做持久化,仅仅持久化一批ID中最大的那一个。这个方式有点像游戏里的定期存档功能,只不过存档的是未来某个时间下发给用户的ID,这样极大地减轻了DB持久化的压力。整个服务的具体处理过程如下:
Leaf Server 1:从DB加载号段[1,1000]。Leaf Server 2:从DB加载号段[1001,2000]。Leaf Server 3:从DB加载号段[2001,3000]。用户通过Round-robin的方式调用Leaf Server的各个服务,所以某一个Client获取到的ID序列可能是:1,1001,2001,2,1002,2002……也可能是:1,2,1001,2001,2002,2003,3,4……当某个Leaf Server号段用完之后,下一次请求就会从DB中加载新的号段,这样保证了每次加载的号段是递增的。Leaf数据库中的号段表格式如下:
Leaf数据库中的号段表格式如下:
+————-+————–+——+—–+——————-+—————————–+
| Field | Type | Null | Key | Default | Extra |
+————-+————–+——+—–+——————-+—————————–+
| biz_tag | varchar(128) | NO | PRI | | |
| max_id | bigint(20) | NO | | 1 | |
| step | int(11) | NO | | NULL | |
| desc | varchar(256) | YES | | NULL | |
| update_time | timestamp | NO | | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+————-+————–+——+—–+——————-+—————————–+
Leaf Server加载号段的SQL语句如下:
Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

整体上,V1版本实现比较简单,主要是为了尽快解决业务层DB压力的问题,而快速迭代出的一个版本。因而在生产环境中,也发现了些问题。比如:在更新DB的时候会出现耗时尖刺,系统最大耗时取决于更新DB号段的时间。当更新DB号段的时候,如果DB宕机或者发生主从切换,会导致一段时间的服务不可用。Leaf双Buffer优化为了解决这两个问题,Leaf采用了异步更新的策略,同时通过双Buffer的方式,保证无论何时DB出现问题,都能有一个Buffer的号段可以正常对外提供服务,只要DB在一个Buffer的下发的周期内恢复,就不会影响整个Leaf的可用性。


这个版本代码在线上稳定运行了半年左右,Leaf又遇到了新的问题:号段长度始终是固定的,假如Leaf本来能在DB不可用的情况下,维持10分钟正常工作,那么如果流量增加10倍就只能维持1分钟正常工作了。号段长度设置的过长,导致缓存中的号段迟迟消耗不完,进而导致更新DB的新号段与前一次下发的号段ID跨度过大。Leaf动态调整Step假设服务QPS为Q,号段长度为L,号段更新周期为T,那么Q * T = L。最开始L长度是固定的,导致随着Q的增长,T会越来越小。但是Leaf本质的需求是希望T是固定的。那么如果L可以和Q正相关的话,T就可以趋近一个定值了。所以Leaf每次更新号段的时候,根据上一次更新号段的周期T和号段长度step,来决定下一次的号段长度nextStep

  • T < 15min,nextStep = step * 2
  • 15min < T < 30min,nextStep = step
  • T > 30min,nextStep = step / 2

至此,满足了号段消耗稳定趋于某个时间区间的需求。当然,面对瞬时流量几十、几百倍的暴增,该种方案仍不能满足可以容忍数据库在一段时间不可用、系统仍能稳定运行的需求。因为本质上来讲,Leaf虽然在DB层做了些容错方案,但是号段方式的ID下发,最终还是需要强依赖DB。MySQL高可用在MySQL这一层,Leaf目前采取了半同步的方式同步数据,通过公司DB中间件Zebra加MHA做的主从切换。未来追求完全的强一致,会考虑切换到MySQL Group Replication。现阶段由于公司数据库强一致的特性还在演进中,Leaf采用了一个临时方案来保证机房断网场景下的数据一致性:多机房部署数据库,每个机房一个实例,保证都是跨机房同步数据。半同步超时时间设置到无限大,防止半同步方式退化为异步复制。Leaf监控针对服务自身的监控,Leaf提供了Web层的内存数据映射界面,可以实时看到所有号段的下发状态。比如每个号段双buffer的使用情况,当前ID下发到了哪个位置等信息都可以在Web界面上查看。

微信序列号生成器

文档地址:https://www.infoq.cn/article/wechat-serial-number-generator-architecture
思想和数据库方案有点类似,都是为每个客户(数据库是每个需要id的应用)分配一个单独的数据,开始递增。采用一定的步长进行递增,对当前允许的最大值进行持久化。

  1. 内存中储存最近一个分配出去的 sequence:cur_seq,以及分配上限:max_seq
  2. 分配 sequence 时,将 cur_seq++,同时与分配上限 max_seq 比较:如果 cur_seq > max_seq,将分配上限提升一个步长 max_seq += step,并持久化 max_seq
  3. 重启时,读出持久化的 max_seq,赋值给 cur_seq