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