雪花算法那些事
对id的要求
业务
- 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
- 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。
- 可读性
技术
- 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
- 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
目前使用方式
uuid
满足全局唯一性，信息安全
可用于一些唯一性的标识，比如标识图片，但是不能用作数据库索引。
redis生成
满足全局唯一性，单调递增，可读性
通过 prefix + yyyyMMdd + sequence 这个格式生成id，其中sequence通过redis的incr命令生成。
public Long generate(String redisKeyPrefix, Integer sequenceLength){
String date = DATE_FORMATTER.format(LocalDateTime.now());
return Long.parseLong(date) * IntMath.pow(10,sequenceLength)+ stringIntegerRedisTemplate.opsForValue().increment(Joiner.on(":").join(Lists.newArrayList(redisKeyPrefix,date)),1);
}
可在内部项目使用，不能透出给外部第三方。
redis生成+hashIds
对内满足全局唯一性，单调递增，可读性
对外满足全局唯一性，信息安全
在之前方式的基础上，对外通过hashIds算法将id混淆，一种妥协的方式，混淆逻辑会增加工作量。
雪花算法
满足全局唯一性，趋势递增，可读性，信息安全
公司已有雪花服务，使用成本极低，完美解决方案。
雪花算法
雪花算法是由Twitter公布的分布式主键生成算法，它能够保证不同进程主键的不重复性，以及相同进程主键的有序性。
在同一个进程中，它首先是通过时间位保证不重复，如果时间相同则是通过序列位保证。 同时由于时间位是单调递增的，且各个服务器如果大体做了时间同步，那么生成的主键在分布式环境可以认为是总体有序的，这就保证了对索引字段的插入的高效性。例如MySQL的Innodb存储引擎的主键。
使用雪花算法生成的主键，二进制表示形式包含4部分，从高位到低位分表为：1bit符号位、41bit时间戳位、10bit工作进程位以及12bit序列号位。
- 符号位(1bit)
预留的符号位，恒为零。
- 时间戳位(41bit)
41位的时间戳可以容纳的毫秒数是2的41次幂，一年所使用的毫秒数是：365 * 24 * 60 * 60 * 1000。通过计算可知：
Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L);
结果约等于69.73年。ShardingSphere的雪花算法的时间纪元从2016年11月1日零点开始，可以使用到2086年，相信能满足绝大部分系统的要求。
- 工作进程位(10bit)
该标志在Java进程内是唯一的，如果是分布式应用部署应保证每个工作进程的id是不同的。该值默认为0，可通过属性设置。
- 序列号位(12bit)
该序列是用来在同一个毫秒内生成不同的ID。如果在这个毫秒内生成的数量超过4096(2的12次幂)，那么生成器会等待到下个毫秒继续生成。
实现
基础算法
public class SnowFlake {
/**
* 起始的时间戳
*/
private final static long START_STMP = 1480166465631L;
/**
* 每一部分占用的位数
*/
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 - START_STMP) << 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(2, 3);
for (int i = 0; i < (1 << 12); i++) {
System.out.println(snowFlake.nextId());
}
}
}
这端代码将workerid分为datacenterId和machineId，如果我们业务上不需要做区分的话，直接使用10位的workerid即可。
成熟实现
上面基础算法在项目中是不能直接使用的。我们需要在分布式环境下协调每一台机器的workerid的唯一性以及避免时钟回拨导致id重复。
美团的Leaf项目专门用于生成分布式全局id，其中snowflake模式就是对应雪花算法实现。
下面让我们来看下Leaf怎么解决这些问题
workerid生成
主要原理是通过zookeeper的有序节点保证id的全局唯一性，比如我通过以下命令创建一个永久有序节点
# 创建一个根节点
create /test ''
# 创建永久有序节点
create -s /test/ip-port- ''
# 返回 Created /test/ip-port-0000000000
ip-port对应当前leaf-server的ip和zookeeper的port
其中/test/ip-port-0000000000中的0000000000就是我们的workerid
并且该workerid会存储到本地文件，如果zookeeper挂了，直接从本地文件获取即可。
时钟回拨解决
snowflake算法很依赖时钟，一但出现时钟回拨，那就可能造成id重复。
Leaf中为了解决这个问题，会定时(3分钟)保存当前操作系统的时间戳到上节的/test/ip-port-0000000000
节点中，同时将该值保存到字段lastTimestamp。
image.png
如果发生了时钟回拨，那么当前的时间戳小于lastTimestamp了，那么会根据回拨时钟的大小做不同处理
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
wait(offset << 1);
timestamp = timeGen();
if (timestamp < lastTimestamp) {
return new Result(-1, Status.EXCEPTION);
}
} catch (InterruptedException e) {
LOGGER.error("wait interrupted");
return new Result(-2, Status.EXCEPTION);
}
} else {
return new Result(-3, Status.EXCEPTION);
}
}
如果小于等于5毫秒，那么进行等待，等待的时间为offset的2倍
如果大于5毫秒，返回异常
那么为什么要把时间戳保存到zk？
把时间戳保存到zk，是为了应对宕机重启，确保不发之前已经发过的号。
workerid回收
现在的应用很多都是容器化部署了，每次主机的ip都会发生变化，如果在容器化中使用zk来协调workerid(使用上一节的方式)，那么就会存在workerid很快用完的问题。
issue在这里
不过官方并不认为这是一个问题，如果仅仅因为workerid不够用的话，只要增加workerid位数就可以了。
不过也有个热心人提供了解决方案。
它提供配置使用RecyclableZookeeperHolder替代原来的zk实现SnowflakeZookeeperHolder
RecyclableZookeeperHolder的具体逻辑如下
- 首先会在未使用的workId池(zookeeper路径为/snowflake/leaf.name/recycle/notuse/)中生成所有workId。
- 然后每次服务器启动时都是去未使用的workId池取一个新的workId，然后放到正在使用的workId池(zookeeper路径为/snowflake/leaf.name/recycle/inuse/)下，将此workId用于Id生成，并且定时上报时间戳，更新zookeeper中的节点信息。
- 并且定时检测正在使用的workId池，发现某个workId超过最大时间没有更新时间戳的workId，会把它从正在使用的workId池移出，然后放到未使用的workId池中，以供workId循环使用。
- 并且正在使用这个很长时间没有更新时间戳的workId的服务器，在发现自己超过最大时间，还没有上报时间戳成功后，会停止id生成服务，以防workId被其他服务器循环使用，导致id重复。
参考
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://shardingsphere.apache.org/document/legacy/4.x/document/cn/features/sharding/other-features/key-generator/#snowflake
