对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次幂),那么生成器会等待到下个毫秒继续生成。
![](http://upload-images.jianshu.io/upload_images/9919411-5d8d8b0aeff37834.png?imageMogr2/auto-orient/strip|imageView2/2/w/1200/format/webp)
实现
基础算法
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
。
![](http://upload-images.jianshu.io/upload_images/9919411-c3538eeebfa6dcc7.png?imageMogr2/auto-orient/strip|imageView2/2/w/478/format/webp)
如果发生了时钟回拨,那么当前的时间戳小于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
作者:土豆肉丝盖浇饭
链接:https://www.jianshu.com/p/71872358104a
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 标签:workerid,雪花,workId,主键,那些,毫秒,算法,id From: https://www.cnblogs.com/shoshana-kong/p/17319209.html