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分别表示如下图所示：

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;

import org.apache.commons.lang.StringUtils;

import java.math.BigInteger;

/**
 * 通过 snowFlake 雪花算法生成唯一且在时间段内趋势递增的
 * 分布式ID
 *
 * @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 {
    /**
     * 起始的时间戳
     * 从 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)
     */
    public SnowFlakeIDUtil(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;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public 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();
    }

    /**
     * 获得订单ID生成时的时间戳
     * @param id
     * @return
     */
    public static long getIDTimestamp(long id){
        String str = Long.toUnsignedString(id,2);
        Long length = str.length()- SEQUENCE_BIT - MACHINE_BIT - DATACENTER_BIT;
        return Long.valueOf(str.substring(0, length.intValue()),2) + START_STMP;
    }

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

        String str = Long.toUnsignedString(id,2);
        Long start = SEQUENCE_BIT + MACHINE_BIT;
        Long end = SEQUENCE_BIT + MACHINE_BIT + DATACENTER_BIT;

        str = StringUtils.reverse(str).substring(start.intValue(),end.intValue());

        return Long.valueOf(StringUtils.reverse(str),2);
    }
   /**
     * 获得机器ID
     * @param id
     * @return
     */
    public static long getMachineId(long id){
        String str = Long.toUnsignedString(id,2);
        Long start = SEQUENCE_BIT ;
        Long end = SEQUENCE_BIT + MACHINE_BIT;

        str = StringUtils.reverse(str).substring(start.intValue(),end.intValue());

        return Long.valueOf(StringUtils.reverse(str),2);
    }
    /**
     * 生成一个 ID
     * datacenterId 从0开始
     * machineId 从0开始
     */
    public static long getNextId(){
        SnowFlakeIDUtil snowFlakeIDUtil = new SnowFlakeIDUtil(0,0);
        return snowFlakeIDUtil.nextId();
    }

    public static void main(String[] args){
        long id = getNextId();
        System.out.println(id);
        System.out.println("DatacenterId= "+getDatacenterId(id));
        System.out.println("MachineId= "+getMachineId(id));
    }
}

最后更新于 2019-01-16 14:56:43 并被添加「snowflake」标签，已有 2 位童鞋阅读过。