分布式主键ID生成方式-snowflake雪花算法

这里写自定义目录标题

一、业务场景
二、技术选型
- 1、UUID方案
- 2、Leaf方案-美团（基于数据库自增id）
- 3、Snowflake雪花算法方案
总结

一、业务场景

大量的业务数据需要保存到数据库中，原来的单库单表的方式扛不住大数据量、高并发，需要分库分表；这样原来的数据库自增id作为主键就不能满足业务需求，需要有一个在分库分表中的唯一标识id作为主键，这个id需要有如下要求：

全局唯一性
趋势递增：在MySQL的InnoDB中使用的是聚焦索引，用的是B-tree的数据结构来存储索引数据，所以要尽量选用有序的主键来保证写入性能
信息安全：不能通过主键看出业务信息

二、技术选型

1、UUID方案

uuid是32位数的16进制数字所构成，以连字号分为五段，总共有 36个字符（即三十二个英数字母和四个连字号），550e8400-e29b-41d4-a716-446655440000，所以理论上uuid的总数有16^32，基本用不完。
优点： 性能非常强，本地内存生成。
缺点： 36个字符串存储，太长了，而且生成的id是无序的，MySQL要求主键越短越好，同时要有序，保证索引的写入性能。

2、Leaf方案-美团（基于数据库自增id）

在数据库中设计一张表用于生成自增id
| biz_tag | maxId | step
| user_tab | 2000 | 1000
| home_tab | 3000 | 2000
biz_tag是业务表名用来区分业务，maxId是目前所被分配的id号段的最大值，step是每次分配的长度。
Leaf微服务从数据库中一次取step个号码端，比如step为1000，则每次取1000个到Leaf服务内存中，用于应用层调用接口获取主键id，每调一次加一，内存中的1000个用完后，Leaf再去数据库取一次号码段（取的时候maxId也会相应更新）。
这样Leaf服务和数据库交互频率就大大减少，性能瓶颈就不在数据库，而在于Leaf微服务，而Leaf服务是无状态的，因此可以根据实际需求横向扩展，可以部署多个Leaf微服务用于获取主键id

优点：

扩展性好，可以随着业务的发展线性扩展多个Leaf服务
生成的主键id是趋势递增的8byte的64位数，符合数据库存储的主键id要求
容灾性好，即使DB宕机一会，Leaf服务内存中缓存的号码段可以支撑一段时间等待DB恢复
maxId可以自定义大小，方便其他业务ID迁移到Leaf服务。
缺点：
ID不够随机，安全性不够
TP999性能波动大，当某一时刻，多个Leaf服务的号码段都使用到999最后一个时，同时调用数据库获取号码端，会造成偶尔的突刺，导致获取主键ID延迟。
DB数据库长时间宕机会导致整个服务不可用。
优化：
争对TP999，可以采用提前获取号码段（双buffer）的方式，当Leaf内存中还剩下指定的号码时（eg：800），就提前获取下1000个号码段放到内存中，即Leaf服务内部有两个号段缓存区segment，这样当数据库调用延迟，需要等待时，Leaf服务还有号码段可以对外提供服务。
DB数据库可以采用一主两从的方式，或者用多机房，提高容灾性。

3、Snowflake雪花算法方案

Snowflake算法可以生成64位的ID，刚好可以用Long型存储，并且生成的ID有大致的顺序；它以划分命名空间的方式，讲64-bit位划分为4个部分：
0 - 41位时间戳 - 10位机器id - 12位序列号
示意图

第一位是符号位，不用。
第二部分是41位的时间戳，可以表示2^41个数，每个数代表毫秒（ms）。
第三部分是10位的机器id，即2^10=1024台机器，实际中用不到这么多机器，可以进一步细分，加上机房信息，或者业务信息。
第四部分是12位的自增序列，2^12=4096个数，即理论上1ms内一台机器支持4096个请求。

Java实现：

/**
 * twitter的snowflake算法 -- java实现
 * 
 */
public class SnowFlake {

    /**
     * 每一部分占用的位数
     */
    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;//上一次时间戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            // 时钟回拨问题怎么处理？
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

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

        lastStmp = currStmp;

        return (currStmp << TIMESTMP_LEFT) //时间戳部分
                | (datacenterId << DATACENTER_LEFT)       //数据中心部分
                | (machineId << MACHINE_LEFT)             //机器标识部分
                | sequence;                             //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(1, 1);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}