一口气说出9种分布式ID生成方式，面试官有点懵 (3)

Java版本的Snowflake算法实现：

/** * Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数，然后转化为62进制变成一个短地址URL * * https://github.com/beyondfengyu/SnowFlake */ public class SnowFlakeShortUrl { /** * 起始的时间戳 */ private final static long START_TIMESTAMP = 1480166465631L; /** * 每一部分占用的位数 */ private final static long SEQUENCE_BIT = 12; //序列号占用的位数 private final static long MACHINE_BIT = 5; //机器标识占用的位数 private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数 /** * 每一部分的最大值 */ private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT); /** * 每一部分向左的位移 */ private final static long MACHINE_LEFT = SEQUENCE_BIT; private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; private long dataCenterId; //数据中心 private long machineId; //机器标识 private long sequence = 0L; //序列号 private long lastTimeStamp = -1L; //上一次时间戳 private long getNextMill() { long mill = getNewTimeStamp(); while (mill <= lastTimeStamp) { mill = getNewTimeStamp(); } return mill; } private long getNewTimeStamp() { return System.currentTimeMillis(); } /** * 根据指定的数据中心ID和机器标志ID生成指定的序列号 * * @param dataCenterId 数据中心ID * @param machineId 机器标志ID */ public SnowFlakeShortUrl(long dataCenterId, long machineId) { if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) { throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_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 currTimeStamp = getNewTimeStamp(); if (currTimeStamp < lastTimeStamp) { throw new RuntimeException("Clock moved backwards. Refusing to generate id"); } if (currTimeStamp == lastTimeStamp) { //相同毫秒内，序列号自增 sequence = (sequence + 1) & MAX_SEQUENCE; //同一毫秒的序列数已经达到最大 if (sequence == 0L) { currTimeStamp = getNextMill(); } } else { //不同毫秒内，序列号置为0 sequence = 0L; } lastTimeStamp = currTimeStamp; return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分 | dataCenterId << DATA_CENTER_LEFT //数据中心部分 | machineId << MACHINE_LEFT //机器标识部分 | sequence; //序列号部分 } public static void main(String[] args) { SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3); for (int i = 0; i < (1 << 4); i++) { //10进制 System.out.println(snowFlake.nextId()); } } }

2.7、百度（uid-generator）
uid-generator 是由百度技术部开发，GitHub地址：https://github.com/baidu/uid-generator

uid-generator是基于Snowflake算法实现的，与原始的snowflake算法不同在于，uid-generator支持自定义时间戳、工作机器ID和 序列号 等各部分的位数，而且uid-generator中采用用户自定义workId的生成策略。

uid-generator需要与数据库配合使用，需要新增一个WORKER_NODE表。当应用启动时会向数据库表中去插入一条数据，插入成功后返回的自增ID就是该机器的workId数据由host，port组成。

对于uid-generator ID组成结构：

workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和原始的snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，而且同一应用每次重启就会消费一个workId。

参考文献

https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

2.8、美团（Leaf）
Leaf由美团开发，GitHub地址：https://github.com/Meituan-Dianping/Leaf

Leaf同时支持号段模式和snowflake算法模式，可以切换使用。

2.8.1 号段模式

先导入源码 https://github.com/Meituan-Dianping/Leaf，再建一张表leaf_alloc

DROP TABLE IF EXISTS `leaf_alloc`; CREATE TABLE `leaf_alloc` ( `biz_tag` varchar(128) NOT NULL DEFAULT '' COMMENT '业务key', `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id', `step` int(11) NOT NULL COMMENT '初始步长，也是动态调整的最小步长', `description` varchar(256) DEFAULT NULL COMMENT '业务key的描述', `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '数据库维护的更新时间', PRIMARY KEY (`biz_tag`) ) ENGINE=InnoDB;