分布式唯一Id：snowflake雪花算法

亦凉 2023-02-13 11:21 98阅读 0赞

### snowflake ###

是Twitter开源的分布式ID生成算法，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0

### 为什么使用snowflake？ ###

其实呢如果只是想保证分布式id的唯一性，那么使用**UUID**是完全可以没问题的，**UUID**的方式能生成一串唯一随机32位长度数据，它是无序的一串数据，它是由以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字组成的，所以保证了分布式不同机器上的id唯一性，但是UUID作为分布式唯一ID有一些缺点  
1，首先分布式id一般都会作为主键，但是安装mysql官方推荐主键要尽量越短越好，UUID每一个都很长，所以不是很推荐  
2，既然分布式id是主键，然后主键是包含索引的，然后mysql的索引是通过b+树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的b+树进行修改，因为UUID数据是无序的，所以每一次UUID数据的插入都会对主键地城的b+树进行很大的修改，这一点很不好  
3，信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。  
**我们针对第2点说一下：**  
这里涉及到b+树索引分裂：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]  
众所周知，关系型数据库的索引大都是B+树的结构，拿ID字段来举例，索引树的每一个节点都存储着若干个ID。  
如果我们的ID按递增的顺序来插入，比如陆续插入8，9，10，新的ID都只会插入到最后一个节点当中。当最后一个节点满了，会裂变出新的节点。这样的插入是性能比较高的插入，因为这样节点的分裂次数最少，而且充分利用了每一个节点的空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]  
但是，如果我们的插入完全无序，不但会导致一些中间节点产生分裂，也会白白创造出很多不饱和的节点，这样大大降低了数据库插入的性能。

所以我们可以使用snowflake雪花算法，简单介绍一下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 2]  
SnowFlake所生成的ID一共分成四部分：

1.第一位

占用1bit，其值始终是0，没有实际作用。

2.时间戳

占用41bit，精确到毫秒，总共可以容纳约140年的时间。

3.工作机器id

占用10bit，其中高位5bit是数据中心ID（datacenterId），低位5bit是工作节点ID（workerId），做多可以容纳1024个节点。

4.序列号

占用12bit，这个值在同一毫秒同一节点上从0开始不断累加，最多可以累加到4095。

SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢？只需要做一个简单的乘法：

同一毫秒的ID数量 = 1024 X 4096 = 4194304  
这个数字在绝大多数并发场景下都是够用的。

### 代码实现： ###

public class SnowflakeIdWorker {
        
    
        // ==============================Fields===========================================
        /** 开始时间截 (2015-01-01) */
        private final long twepoch = 1420041600000L;
    
        /** 机器id所占的位数 */
        private final long workerIdBits = 5L;
    
        /** 数据标识id所占的位数 */
        private final long datacenterIdBits = 5L;
    
        /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
        private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    
        /** 支持的最大数据标识id，结果是31 */
        private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    
        /** 序列在id中占的位数 */
        private final long sequenceBits = 12L;
    
        /** 机器ID向左移12位 */
        private final long workerIdShift = sequenceBits;
    
        /** 数据标识id向左移17位(12+5) */
        private final long datacenterIdShift = sequenceBits + workerIdBits;
    
        /** 时间截向左移22位(5+5+12) */
        private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    
        /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
        private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    
        /** 工作机器ID(0~31) */
        private long workerId;
    
        /** 数据中心ID(0~31) */
        private long datacenterId;
    
        /** 毫秒内序列(0~4095) */
        private long sequence = 0L;
    
        /** 上次生成ID的时间截 */
        private long lastTimestamp = -1L;
    
        //==============================Constructors=====================================
        /**
         * 构造函数
         * @param workerId 工作ID (0~31)
         * @param datacenterId 数据中心ID (0~31)
         */
        public SnowflakeIdWorker(long workerId, long datacenterId) {
        
            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));
            }
            this.workerId = workerId;
            this.datacenterId = datacenterId;
        }
    
        // ==============================Methods==========================================
        /**
         * 获得下一个ID (该方法是线程安全的)
         * @return SnowflakeId
         */
        public synchronized long nextId() {
        
            long timestamp = timeGen();
    
            //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
            if (timestamp < lastTimestamp) {
        
                throw new RuntimeException(
                        String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
            }
    
            //如果是同一时间生成的，则进行毫秒内序列
            if (lastTimestamp == timestamp) {
        
                sequence = (sequence + 1) & sequenceMask;
                //毫秒内序列溢出
                if (sequence == 0) {
        
                    //阻塞到下一个毫秒,获得新的时间戳
                    timestamp = tilNextMillis(lastTimestamp);
                }
            }
            //时间戳改变，毫秒内序列重置
            else {
        
                sequence = 0L;
            }
    
            //上次生成ID的时间截
            lastTimestamp = timestamp;
    
            //移位并通过或运算拼到一起组成64位的ID
            return ((timestamp - twepoch) << timestampLeftShift) //
                    | (datacenterId << datacenterIdShift) //
                    | (workerId << workerIdShift) //
                    | sequence;
        }
    
        /**
         * 阻塞到下一个毫秒，直到获得新的时间戳
         * @param lastTimestamp 上次生成ID的时间截
         * @return 当前时间戳
         */
        protected long tilNextMillis(long lastTimestamp) {
        
            long timestamp = timeGen();
            while (timestamp <= lastTimestamp) {
        
                timestamp = timeGen();
            }
            return timestamp;
        }
    
        /**
         * 返回以毫秒为单位的当前时间
         * @return 当前时间(毫秒)
         */
        protected long timeGen() {
        
            return System.currentTimeMillis();
        }
    
        //==============================Test=============================================
        /** 测试 */
        public static void main(String[] args) {
        
            SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
            for (int i = 0; i < 1000; i++) {
        
                long id = idWorker.nextId();
                System.out.println(Long.toBinaryString(id));
                System.out.println(id);
            }
        }
    }

### 时间回拨问题 ###

###### 分析时间回拨产生原因 ######

第一：人物操作，在真实环境一般不会有那个傻逼干这种事情，所以基本可以排除。  
第二：由于有些业务等需要，机器需要同步时间服务器（在这个过程中可能会存在时间回拨，查了下我们服务器一般在10ms以内（2小时同步一次））。

###### 时间问题回拨的解决方法： ######

当回拨时间小于15ms，就等时间追上来之后继续生成。  
当时间大于15ms时间我们通过更换workid来产生之前都没有产生过的来解决回拨问题。  
首先把workid的位数进行了调整（15位可以达到3万多了，一般够用了）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 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机器获取的可能性）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200528180346112.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200528180524290.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200528180808642.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200528181356599.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70