2019-01-06

Snowflake算法生成分布式系统唯一ID

在复杂的系统中唯一ID是我们在设计的时候常常会遇见的问题，生成ID的方法有很多，适应不同的场景、需求以及性能要求。所以有些比较复杂的系统会有多个ID生成的策略，下面就介绍一些常见的ID生成策略。

1. 数据库自增长序列或字段

最常见的方式。利用数据库，全数据库唯一。

优点：

简单，代码方便，性能可以接受。
数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点：

不同数据库语法和实现不同，数据库迁移的时候或多数据库版本支持的时候需要处理。
在单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成。有单点故障的风险。
在性能达不到要求的情况下，比较难于扩展。
如果遇见多个系统需要合并或者涉及到数据迁移会相当痛苦。

优化方案：

针对主库单点，如果有多个Master库，则每个Master库设置的起始数字不一样，步长一样，可以是Master的个数。比如：Master1 生成的是 1，4，7，10，Master2生成的是2,5,8,11 Master3生成的是 3,6,9,12。这样就可以有效生成集群中的唯一ID，也可以大大降低ID生成数据库操作的负载。

2. UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前为止业界一共有5种方式生成UUID。

优点：

简单，代码方便。
生成ID性能非常好，基本不会有性能问题，本地生成，没有网络消耗。
全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更等情况下，可以从容应对。

缺点：

不易于存储，UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。MySQL官方有明确的建议主键要尽量越短越好
信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
生成ID无序对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。

3. snowflake方案

大致来说是一种以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法，这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如下图所示：

1	0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

1bit 表示符号位，表示是正数还是负数，设为正数固定为0
41bit 的时间戳可以表示( 1L<<41 ) / ( 1000L * 3600 * 24 *365 )=69年的时间。
10bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10bit分5bit给IDC，分5bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。
12bit可以表示的最大正整数是2^12-1=4095，即可以用0、1、2、3、….4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号，这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

优点：

毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
可以根据自身业务特性分配bit位，非常灵活。

缺点：

强依赖机器时钟，在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，还有闰秒的存在，会导致重复或者服务会处于不可用状态。

附上相关的代码：

package com.dm.tool.util;

/**
 * 通过 snowFlake 雪花算法生成唯一且在时间段内趋势递增的
 * 分布式ID
 * @author Nick
 * @projectName dm-mt
 * @package com.dm.tool.util
 * @createDate 2019/01/17 09:17
 * @updateDate 2019/01/17 09:17
 */

public class SnowFlake{

    private static volatile SnowFlake instance ;
    /**
     * 起始的时间戳
     * 从 2019/01/01 00:00:00 开始
     */
    private final static long START_STMP = 1546272000000L;
    /**
     * 序列号占用的位数
     */
    private final static long SEQUENCE_BIT = 12;
    /**
     * 机器标识占用的位数
     */
    private final static long MACHINE_BIT = 5;
    /**
     * 数据中心占用的位数
     */
    private final static long DATACENTER_BIT = 5;

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    /**
     * 数据中心
     */
    private long datacenterId;
    /**
     * 机器标识
     */
    private long machineId;
    /**
     * 序列号
     */
    private long sequence = 0L;
    /**
     * 上一次时间戳
     */
    private long lastStmp = -1L;

    /**
     *
     * @param datacenterId 数据中心ID (0~31)
     * @param machineId  workerId 工作ID (0~31)
     */
    private SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenterId can't be greater than %d or less than 0",MAX_DATACENTER_NUM));
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException(String.format("machineId can't be greater than %d or less than 0",MAX_MACHINE_NUM));
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    public static SnowFlake getInstance(long datacenterId, long machineId){

        if (instance == null){
            synchronized (SnowFlake.class){
                if (instance == null){
                    instance = new SnowFlake(datacenterId,machineId);
                }
            }
        }
        return instance;
    }
    /**
     * 产生下一个ID
     *
     * @return
     */
    protected synchronized long nextId() {
        long currStmp = getNewTimestamp();
        if (currStmp < lastStmp) {
            String msg = String.format("Clock moved backwards. Refusing to generate id! currStmp=%d,lastStmp=%d",currStmp,lastStmp);
            throw new RuntimeException(msg);
        }

        if (currStmp == lastStmp) {
            // 相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            // 同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            // 不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStmp = currStmp;
        // 时间戳 41  数据中心 5 机器标识 5 序列号 12
        return (currStmp - START_STMP) << TIMESTMP_LEFT
                | datacenterId << DATACENTER_LEFT
                | machineId << MACHINE_LEFT
                | sequence;
    }

    private long getNextMill() {
        long mill = getNewTimestamp();
        while (mill <= lastStmp) {
            mill = getNewTimestamp();
        }
        return mill;
    }
    private long getNewTimestamp() {
        return System.currentTimeMillis();
    }

    public static long getSequenceBit() {
        return SEQUENCE_BIT;
    }

    public static long getMachineBit() {
        return MACHINE_BIT;
    }

    public static long getDatacenterBit() {
        return DATACENTER_BIT;
    }

    public static long getStartStmp() {
        return START_STMP;
    }
}

工具类如下：

package com.dm.tool.util;

import org.apache.commons.lang.StringUtils;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * snowFlake工具类
 *
 * @author Nick
 * @projectName dm-mt
 * @package com.dm.tool.util
 * @createDate 2019/01/16 09:30
 * @updateDate 2019/01/16 09:30
 */
public class SnowFlakeIDUtil {

    private static final int radix = 2;

    /**
     * 数据中心ID 0，机器ID 0
     * @param datacenterId
     * @param machineId
     * @return
     */
    public static long getNextId(long datacenterId, long machineId){
        return SnowFlake.getInstance(datacenterId,machineId).nextId();
    }
    /**
     * 获得订单ID生成时的时间戳
     * @param id
     * @return
     */
    public static long getIDTimestamp(long id){
        return (id >> SnowFlake.getTimestmpLeft() & ~(-1L << 41))+SnowFlake.getStartStmp();
    }

    /**
     * 获取数据中心 ID
     * @param id
     * @return
     */
    public static long getDatacenterId(long id){

        return id >> SnowFlake.getDatacenterLeft() & ~(-1L << SnowFlake.getDatacenterBit());
    }

    /**
     * 获得机器ID
     * @param id
     * @return
     */
    public static long getMachineId(long id){

        return id >> SnowFlake.getMachineLeft() & ~(-1L << SnowFlake.getMachineBit());
    }

    /**
     * 获取序列ID
     * @param id
     * @return
     */
    public static long getSequence(long id){
        return id & ~(-1L << SnowFlake.getSequenceBit());
    }
    public static void main(String[] args){

        MyThread thread1 = new MyThread();
        MyThread thread2 = new MyThread();
        MyThread thread3 = new MyThread();
        MyThread thread4 = new MyThread();

        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();
    }

    static class MyThread extends Thread{
        @Override
        public void run() {
            while (true){
                long id = SnowFlakeIDUtil.getNextId(0,0);
                System.out.println("ID="+id+"时间戳= "+getIDTimestamp(id)+" DatacenterId= "+getDatacenterId(id)+" MachineId="+getMachineId(id)+" Sequence="+getSequence(id));

            }
        }
    }
}

作者: Sam
发布时间: 2019-01-06 23:23:41
最后更新: 2019-12-09 23:03:26
文章链接: https://ydstudios.gitee.io/post/4f74853e.html
版权声明: 本网所有文章除特别声明外, 禁止未经授权转载，违者依法追究相关法律责任!

Sam的个人博客

一个程序员的成长记录

Snowflake算法生成分布式系统唯一ID

1. 数据库自增长序列或字段

2. UUID

3. snowflake方案