分布式主键ID生成方式-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）

1. 在数据库中设计一张表用于生成自增id
   | biz_tag | maxId | step
   | user_tab | 2000 | 1000
   | home_tab | 3000 | 2000
   biz_tag是业务表名用来区分业务，maxId是目前所被分配的id号段的最大值，step是每次分配的长度。
2. Leaf微服务从数据库中一次取step个号码端，比如step为1000，则每次取1000个到Leaf服务内存中，用于应用层调用接口获取主键id，每调一次加一，内存中的1000个用完后，Leaf再去数据库取一次号码段（取的时候maxId也会相应更新）。
3. 这样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位序列号

1. 第一位是符号位，不用。
2. 第二部分是41位的时间戳，可以表示2^41个数，每个数代表毫秒（ms）。
3. 第三部分是10位的机器id，即2^10=1024台机器，实际中用不到这么多机器，可以进一步细分，加上机房信息，或者业务信息。
4. 第四部分是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 {//不同毫秒内，序列号置为0sequence = 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());}}
}

时钟回拨问题：
当某台机器的时间出现了问题，回到了前几秒，则调用该机器雪花算法时，会生成重复的id，因为前几秒是时间已经生成过id了。
根据实际的业务和机器的情况不同，有几种解决方案：

1. 当回拨的时间不长，比如不到100ms，小于接口调用超时时间，则可以用sleep方法等待时间正常。
2. 当回拨时间适中，比如100ms~1s内，等待的话会接口超时，这种情况，可以将前一秒的每个ms的最大序列号维护在缓存中，然后maxId+1。
3. 当回拨时间比较长，可以重试调用其他机器生成id，等过一段时间再调用该机器。或者直接把这个机器下线掉。

雪花算法生成架构：

部署多个服务，通过服务发现被应用服务调用，同时机器id可以动态通过zookeeper（可以生成自增序列）获取。

总结

分布式主键id的生成方式有很多种，最重要的是根据自己的实际业务情况来选择最合适自己的一种方式。