分布式唯一id生成
在实际应用中，对于分布式系统，我们希望能有一个ID生成器用来生成全局的、唯一的ID，比如用户id,订单号，支付单号等等。
目前，存在的主要有以下几种。
1、UUID
这个应该读很熟悉，通用唯一识别码，它是由32位的16进制数组成的。
类似：00112233-4455-6677-8899-aabbccddeeff。
其生成规则有很多的版本，有根据网卡或时间生成的，有随机生成的，有基于时间生成的等等。具体可见： UUID维基百科
但其并不适合做为我们实际系统中的ID生成器，因为其是随机的，无序的，在实际中我们系统它是有序的，此外无序的索引在Mysql中查询数据也是有性能的影响。此外，UUID标识位较多，较占空间。
2、数据库主键自增
使用Mysql的主键当作ID生成器，不同的系统可以统一通过DB代理访问数据库，并获取生成的主键ID。
这种方式是相对比较简单的一种做法，不需要额外做什么操作，只需要部署好DB。但其本身也存在缺点，因为该方式是强依赖DB的，假如DB挂了，那服务完全不可用。且ID生产性能受限于Mysql性能。此外，如果后续Mysql分库分表的话，很难保证ID不出现重复。
3、Redis,zk
其实说实话，基本没有用的，虽然两个都能实现。然而Redis非常可能导致数据丢失，从而出现重复。zk的话本身集群的性能一般。
4、SnowFlake算法
该算法是Twitter开源的一个算法，生成的ID是由63位数字组成的long型整数，41位的时间戳+5位的数据中心id+5位机器id+12位递增序列号。
第1位是符号位，0是正数，1是负数。
41位时间戳是毫秒时间戳，不过这个时间戳并不是绝对时间戳，而是一个差值，差值是当前时间戳减去起始时间戳，而起始时间戳的值取决于自己的选择。时间戳最多可以用69年。
中间的10位是机器ID，由5为数据中心ID和5为机器ID组成，也就是总共可部署1024个机器。
最后的12bit是循环位，用来同一毫秒内生成不同的id，12位最多可以生成4095个，因此同一毫秒内，允许生成4095个ID。
该算法最大的缺点就是性能超好，没有其他的依赖，全局唯一。如果部署1024个机器的话，理论上美妙可产生40多亿个id。
但该算法有一个众所周知的缺点就是时钟回拨的问题，即因为机器的原因，时钟回拨了，可能导致当前时间戳还要小于之前的时间戳，这样就出现ID重复。
针对这个问题，目前有很多的解决方案。
方案1：每台都维护一个上个时间戳 lastTimestamp，每次都会将当前时间戳和上一个时间戳进行比较。如果查值较小（有多小完全取决于实际业务需求，可以5ms，可以10ms)，可以等待，一直到时间超过lastTimestamp；如果差值较大，无法一直阻塞，可以直接抛出异常，然后将时钟回滚。或者增加在后面再增加扩展位（但我觉得这种方式不妥，因为扩展位的位数也是有限的，不是解决问题的优先方案）；
方案2：百度提了一个UIdGenerator，源码： UIDGenerator .
其基本思想是不采用SnowFlake算法中传统的取当前时间戳，而是通过AtomicLong类型，采用逐步+1的方式生成时间戳，这里只需要维护一个初始时间戳即可。这样不需要再依赖服务器的时间，不会出现回拨问题。
当然这样做的弊端就是，如果你希望通过序列号来获取时间的话，这样做是不可取的，因为通过这个方法获取的不一定就是那时实际的时间戳。
目前这个项目，最后一次维护还是3年前。
5、美团Leaf
其主要有两个方案：Leaf-segment方案和Leaf-snowflake方案。
Leaf-segment方案就是基于数据库自增ID来实现的，它在数据库的性能上的提升做了一定的改进，即它一利用代理去一次生成一段的ID(segment)，然后存储下来，等用完了再去请求数据库。这样做的一个明显有点就是没必要每次生成ID都需要请求一次数据库，减少IO,提升了性能。此外，在此基础上，美团又提出了buffer的优化，即当已获取的一段ID号用了一定数量后，且未完全耗尽时，会异步再去请求数据库并存储下来。这对客户端来讲时无感知的，因此性能又得到了极大的提升。
Leaf-snowflake方案是一种类似snowflake的一种实现方式。它主要是采用了ZK去管理配置机器节点。
但说实话，我不知道这个方案有什么实际的意义，我是觉得用了ZK反倒影响性能。
关于Leaf更详细的介绍可见： Leaf——美团点评分布式ID生成系统
下面是用JAVA实现的SnowFlake算法，改进之处就是对于时钟回拨的处理，参考了美团。
public class OrderIdGeneratorServiceImpl implements OrderIdGeneratorService {
private static final Logger logger = LoggerFactory.getLogger(OrderIdGeneratorServiceImpl.class);
/**
* work开始id
*/
public static final AtomicLong START_WORK_ID = new AtomicLong(0);
public static final Long START_TIMESTAMP = 1580580122000L;
/**
* ID 首位
*/
private static final Short ID_HEADER = 1;
private static final Long WorkIDBits = 8L;
private static final Long MAX_WORK_ID = ~(-1L << WorkIDBits); //最大的work id
private static final Long CycleIdBits = 12L;
private static final Long MAX_CYCLE_ID = ~(-1L << CycleIdBits);
private static final Long WorkIdShifts = CycleIdBits;
private static final Long TimeStampShifts = CycleIdBits + WorkIDBits;
private Long workerId;
private Long sequenceId = 0L;
private Long lastTimeStamp = -1L;
@Override
public synchronized Long getOrderId() throws OrderIdGenerationException {
Long timestamp = this.getCurTimeStamp();
if(timestamp < this.lastTimeStamp) {
Long delta = this.lastTimeStamp - timestamp;
Long MAX_DElTA = 5L;
if(delta <= MAX_DElTA){
try{
//设定一个休眠时间
wait(delta << 1);
timestamp = this.getCurTimeStamp();
if(timestamp < lastTimeStamp){
throw new OrderIdGenerationException("时钟已经回拨，请检查机器时钟");
}
}catch (Exception e){
throw new OrderIdGenerationException(e.getMessage());
}
}else {
throw new OrderIdGenerationException("时钟已经回拨，请检查机器时钟");
}
}
if(timestamp.equals(this.lastTimeStamp)){
sequenceId = (sequenceId + 1 ) & MAX_CYCLE_ID;
if(sequenceId == 0){
timestamp = tillNextMill(lastTimeStamp);
}
}else {
//如果不是在同一毫秒，直接返回0
sequenceId = 0L;
}
lastTimeStamp = timestamp;
workerId = this.getCurWorkId();
logger.info("time:{},work:{},sequence:{}",timestamp,workerId,sequenceId);
return (timestamp - START_TIMESTAMP) << TimeStampShifts |
workerId << WorkIdShifts |
sequenceId;
}
private Long getCurTimeStamp(){
return System.currentTimeMillis();
}
private Long tillNextMill(Long lastTimeStamp){
Long timestamp = this.getCurTimeStamp();
while(timestamp <= lastTimeStamp){
timestamp = this.getCurTimeStamp();
}
return timestamp;
}
/**
*
* 工作节点，要使用 ZK来管理,保证该机器异常时，要摘除这个id
* @return
*/
private Long getCurWorkId() throws OrderIdGenerationException {
//TODO 通过zookeeper获取workid,通过ZK感知其可用性,目前暂时使用原子变量替换，
this.workerId = START_WORK_ID.incrementAndGet() & MAX_WORK_ID;
logger.info("work id:{}",this.workerId);
if (this.workerId > MAX_WORK_ID){
throw new OrderIdGenerationException(String.format("work ID 超过最大值:%d",MAX_WORK_ID));
}
if (this.workerId < 0L ){
throw new OrderIdGenerationException("work ID 不可为负数");
}
//TODO 通过zookeeper获取workid
return this.workerId;
}
}上述的workId应该采用ZK管理比较合适，我上面就是随意瞎写的，不规范，因为workerid是和机器有关的，每台机器是一样的。
例子：
public class SnowFlake {
protected long workerId;
protected long datacenterId;
protected long sequence;
private static final long START_STMP = 1617206400000L;
private long workerIdBits = 8L;
private long datacenterIdBits = 2L;
protected long maxWorkerId;
protected long maxDatacenterId;
private long sequenceBits;
private long sequenceMask;
private long workerIdShift;
private long datacenterIdShift;
private long timestampLeftShift;
protected long lastTimestamp;
private final byte[] lock;
private static AtomicLong STORE_CNT = new AtomicLong();
public SnowFlake() {
this.maxWorkerId = ~(-1L << (int)this.workerIdBits);
this.maxDatacenterId = ~(-1L << (int)this.datacenterIdBits);
this.sequenceBits = 12L;
this.sequenceMask = ~(-1L << (int)this.sequenceBits);
this.workerIdShift = this.sequenceBits;
this.datacenterIdShift = this.sequenceBits + this.workerIdBits;
this.timestampLeftShift = this.sequenceBits + this.workerIdBits + this.datacenterIdBits;
this.lastTimestamp = -1L;
this.lock = new byte[0];
this.datacenterId = this.makeDatacenterId(this.maxDatacenterId);
this.workerId = this.makeWorkerId(this.datacenterId, this.maxWorkerId);
this.sequence = 0L;
}
public SnowFlake(long datacenterId, long workerId, long sequence) {
this.maxWorkerId = ~(-1L << (int)this.workerIdBits);
this.maxDatacenterId = ~(-1L << (int)this.datacenterIdBits);
this.sequenceBits = 12L;
this.sequenceMask = ~(-1L << (int)this.sequenceBits);
this.workerIdShift = this.sequenceBits;
this.datacenterIdShift = this.sequenceBits + this.workerIdBits;
this.timestampLeftShift = this.sequenceBits + this.workerIdBits + this.datacenterIdBits;
this.lastTimestamp = -1L;
this.lock = new byte[0];
if (workerId <= this.maxWorkerId && workerId >= 0L) {
if (datacenterId <= this.maxDatacenterId && datacenterId >= 0L) {
this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
} else {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0\r\n", this.maxDatacenterId));
}
} else {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0\r\n", this.maxWorkerId));
}
}
public long nextId() {
synchronized(this.lock) {
long timestamp = this.timeGen();
if (timestamp < this.lastTimestamp) {
System.err.printf("clock is moving backwards. Rejecting requests until %d.", this.lastTimestamp);
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", this.lastTimestamp - timestamp));
} else {
if (this.lastTimestamp == timestamp) {
this.sequence = this.sequence + 1L & this.sequenceMask;
if (this.sequence == 0L) {
timestamp = this.getNextMillis(this.lastTimestamp);
}
} else {
this.sequence = 0L;
}
this.updateLastTimestamp(timestamp);
return timestamp - 1617206400000L << (int)this.timestampLeftShift | this.datacenterId << (int)this.datacenterIdShift | this.workerId << (int)this.workerIdShift | this.sequence;
}
}
}
protected long makeWorkerId(long datacenterId, long maxWorkerId) {
long workId = this.randomLong(this.maxDatacenterId);
try {
StringBuffer sb = new StringBuffer();
sb.append(datacenterId);
String localIp = Utils.getIp();
sb.append(localIp);
String name = ManagementFactory.getRuntimeMXBean().getName();
if (null != name && !name.isEmpty()) {
sb.append(name.split("@")[0]);
}
sb.append(this.randomLong(this.maxDatacenterId));
workId = (long)(sb.toString().hashCode() & '\uffff') % (maxWorkerId + 1L);
} catch (Exception var10) {
System.out.println("makeWorkerId Exception:" + var10.getMessage());
}
return workId;
}
protected long recoverLastTimestamp() {
return -1L;
}
private void updateLastTimestamp(long newTime) {
this.lastTimestamp = newTime;
this.storeLastTimestamp(this.lastTimestamp);
}
protected void storeLastTimestamp(long lastTimestamp) {
STORE_CNT.addAndGet(1L);
}
private long randomLong(long maxId) {
return ThreadLocalRandom.current().nextLong(0L, maxId);
}
protected long makeDatacenterId(long maxDatacenterId) {
long datacenterId = 0L;
return datacenterId;
}
public long getWorkerId() {
return this.workerId;
}
public long getDatacenterId() {
return this.datacenterId;
}
private long getNextMillis(long lastTimestamp) {
long timestamp = this.timeGen();
do {
if (timestamp > lastTimestamp) {
return timestamp;
}
timestamp = this.timeGen();
} while(lastTimestamp - timestamp <= 3000L);
throw new RuntimeException(String.format("clock is moving backwards. Rejecting requests until %s.", lastTimestamp));
}
private long timeGen() {
return System.currentTimeMillis();
}
}
Over~
微信分享/微信扫码阅读
