一、snowflake算法

snowflake算法生成ID是一个64bit大小的整数，它的二进制结构如下图：

2.1、算法数据结构解释

1bit 二进制中最高位为1表示负数，但是我们最终生成的ID一般都是整数，所以这个最高位固定为0。
41bit 2(41次方)用于记录时间戳（毫秒）
- 41bit可以表示2(41次方)个数字
- 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是0到2(41次方)-1，减1是因为可表示的数值范围从0开始计算.
- 即41bit可以表示2(41次方)个毫秒值转换为年为2(41次方)/ (1000 60 60 24 365) ≈ 69年
10bit 用于记录机器ID
- 用于部署2(10次方)= 1024个节点，包含5bit个datacenterId 和 5bit个workerId
- 5bit可以表示的最大正整数为2(5次方)-1=31 即可以用0、1、2、3….31，这32个数字来表示不同的datacenterId 和 workerId
12bit 序列号用于记录相同毫秒内产生的不同ID
- 12bit可以表示的最大正整数为2(12次方)= 4096，可以用0、1、2、3…4095这4096个数字来表示同一机器同一时间戳（毫秒）内产生的4096个ID序号
  
  2.2、算法优缺点
  优点：
毫秒数在高位，自增序列在低位，整个ID 都是趋势递增的，整个分布式系统内不会产生重复ID，由于5bit 的 datacenterId 和5bit 的workerId来区分
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也是非常高的。可以根据自身业务特性分配 bit 位，非常灵活
高QPS，理论snowflake方案的QPS为409.6w/s，计算算法规则 = 1000 ≈ 409.6w

缺点：

强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态

2.3、算法思考

2.3.1、snowflake为啥用64位,是否可以扩容?

snowflake是否可以改变其QPS?

可以这么干的，百度的uid-generator就是这么干的，[后面在具体分析其实现原理](https://www.yuque.com/docs/share/fb19a718-7058-4a0d-91f0-a167dfb1bcfb?# 《3、uid-generator设计分析》).  [百度uid-generator github](https://github.com/baidu/uid-generator)

snowflake是否可以扩展位长度?

算法角度上，snowflake是可以扩展位长度，这样可以获取更大的key不重复使用年限及QPS，但是snowflake生成的是数字，在java中最大的数字就是long，故不能扩容. 有人肯定想mysql主键设置为String突破Long长度限制,这种设计虽然突破了限制.但是会导致mysql索引问题,可能导致B树重新平衡、大字段做主键会浪费MySQl宝贵的内存资源.

二、snowflake源码

下面代码是介绍snowflake如何实现的，其未处理应用关闭后时间戳重新复位问题，不可在生产环境中使用. 目前已知基于snowflake框架是美团的Leaf. ```plsql package com.yst.tms.order.center.util;

import java.net.Inet4Address; import java.net.UnknownHostException; import java.util.HashSet; import java.util.Random; import java.util.Set;

class SnowflakeUtils {

/** 时间部分所占长度 */
private static final int TIME_LEN = 41;
/** 数据中心id所占长度 */
private static final int DATA_LEN = 5;
/** 机器id所占长度 */
private static final int WORK_LEN = 5;
/** 毫秒内序列所占长度 */
private static final int SEQ_LEN = 12;
/** 定义起始时间 2015-01-01 00:00:00 */
private static final long START_TIME = 1420041600000L;
/** 上次生成ID的时间截 */
private static long LAST_TIME_STAMP = -1L;
/** 时间部分向左移动的位数 22 */
private static final int TIME_LEFT_BIT = 64 - 1 - TIME_LEN;
/** 自动获取数据中心id（可以手动定义 0-31之间的数） */
private static final long DATA_ID = getDataId();
/** 自动机器id（可以手动定义 0-31之间的数） */
private static final long WORK_ID = getWorkId();
/** 数据中心id最大值 31 */
private static final int DATA_MAX_NUM = ~(-1 << DATA_LEN);
/** 机器id最大值 31 */
private static final int WORK_MAX_NUM = ~(-1 << WORK_LEN);
/** 随机获取数据中心id的参数 32 */
private static final int DATA_RANDOM = DATA_MAX_NUM + 1;
/** 随机获取机器id的参数 32 */
private static final int WORK_RANDOM = WORK_MAX_NUM + 1;
/** 数据中心id左移位数 17 */
private static final int DATA_LEFT_BIT = TIME_LEFT_BIT - DATA_LEN;
/** 机器id左移位数 12 */
private static final int WORK_LEFT_BIT = DATA_LEFT_BIT - WORK_LEN;
/** 上一次的毫秒内序列值 */
private static long LAST_SEQ = 0L;
/** 毫秒内序列的最大值 4095 */
private static final long SEQ_MAX_NUM = ~(-1 << SEQ_LEN);
public synchronized static long genId(){
    long now = System.currentTimeMillis();
    //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
    if (now < LAST_TIME_STAMP) {
        throw new RuntimeException(String.format("系统时间错误！ %d 毫秒内拒绝生成雪花ID！", START_TIME - now));
    }
    //防止在同一时间,序列生成id,目的防止id重复
    if (now == LAST_TIME_STAMP) {
        LAST_SEQ = (LAST_SEQ + 1) & SEQ_MAX_NUM;
        //?这段代码什么目的?谁知道留言!
        if (LAST_SEQ == 0){
            now = nextMillis(LAST_TIME_STAMP);
        }
    } else {
        LAST_SEQ = 0;
    }
    //上次生成ID的时间截
    LAST_TIME_STAMP = now;
   /*
    * 1、(now - START_TIME)这步很重要,如果不做这步会从1970-01-01 08:00:00开始计时,预计2042年结束计时,减去START_TIME,可以从START_TIME时间点计时,让snowflake寿命更长!!!
    * 2、TIME_LEFT_BIT为啥是22? SnowFlake算法是计算用69年,这个时间戳移位22不超过long.max,故最大只能用22,防止越界.
    *    “1970-01-01 08:00:00的时间戳是0,加上69年后,时间戳是2177452800000,在移位22,就到long.max边界了”
    * 3、(DATA_ID << DATA_LEFT_BIT) ,用途是按照数据中心求或,目的让数据key按照数据中心规则分布
    * 4、(WORK_ID << WORK_LEFT_BIT),用途是按照部署机器id求或,目的让数据key在按照集群规则分布
    * 5、LAST_SEQ, 用途是按照随机数求或,目的让可以最后按照最后的key规则生成
    */
    return ((now - START_TIME) << TIME_LEFT_BIT) | (DATA_ID << DATA_LEFT_BIT) | (WORK_ID << WORK_LEFT_BIT) | LAST_SEQ;
}
/**
 * 获取下一不同毫秒的时间戳，不能与最后的时间戳一样
 */
public static long nextMillis(long lastMillis) {
    long now = System.currentTimeMillis();
    while (now <= lastMillis) {
        now = System.currentTimeMillis();
    }
    return now;
}
/**
 * 获取字符串s的字节数组，然后将数组的元素相加，对（max+1）取余
 */
private static int getHostId(String s, int max){
    byte[] bytes = s.getBytes();
    int sums = 0;
    for(int b : bytes){
        sums += b;
    }
    return sums % (max+1);
}
/**
 * 根据 host address 取余，发生异常就获取 0到31之间的随机数
 */
public static int getWorkId(){
    try {
        return getHostId(Inet4Address.getLocalHost().getHostAddress(), WORK_MAX_NUM);
    } catch (UnknownHostException e) {
        return new Random().nextInt(WORK_RANDOM);
    }
}
/**
 * 根据 host name 取余，发生异常就获取 0到31之间的随机数
 */
public static int getDataId() {
    try {
        return getHostId(Inet4Address.getLocalHost().getHostName(), DATA_MAX_NUM);
    } catch (UnknownHostException e) {
        return new Random().nextInt(DATA_RANDOM);
    }
}
public static void main(String[] args) {
    Set ids = new HashSet();
    long start = System.currentTimeMillis();
    for (int i = 0; i < 3000000; i++) {
        ids.add(genId());
    }
    long end = System.currentTimeMillis();
    System.out.println("共生成id[" + ids.size() + "]个，花费时间[" + (end - start) + "]毫秒");
}

} ```

分布式ID

2、snowflake雪花算法分析

一、snowflake算法

2.1、算法数据结构解释

2.2、算法优缺点

2.3、算法思考

2.3.1、snowflake为啥用64位,是否可以扩容?

二、snowflake源码