Leaf原理分析

本文主要是介绍Leaf原理分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、Snowflake生成ID的模式

snowflake算法对于ID的位数是上图这样分配的：

1位的符号位+41位时间戳+10位workID+12位序列号

加起来一共是64个二进制位，正好与Java中的long类型的位数一样。

美团的Leaf框架对于snowflake算法进行了一些位数调整，位数分配是这样：

最大41位时间差+10位的workID+12位序列化

虽然看美团对Leaf的介绍文章里面说：

Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号。

其实看代码里面是没有专门设置符号位的，如果timestamp过大，导致时间差占用42个二进制位，时间差的第一位为1时，可能生成的id转换为十进制后会是负数：

//timestampLeftShift是22，workerIdShift是12
long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;

时间差是什么？

因为时间戳是以1970年01月01日00时00分00秒作为起始点，其实我们一般取的时间戳其实是起始点到现在的时间差，如果我们能确定我们取的时间都是某个时间点以后的时间，那么可以将时间戳的起始点改成这个时间点，Leaf项目中，如果不设置起始时间，默认是2010年11月4日09:42:54，这样可以使得支持的最大时间增长，Leaf框架的支持最大时间是起始点之后的69年。

 

workID怎么分配？

Leaf使用Zookeeper作为注册中心，每次机器启动时去Zookeeper特定路径/forever/下读取子节点列表，每个子节点存储了IP:Port及对应的workId，遍历子节点列表，如果存在当前IP:Port对应的workId，就使用节点信息中存储的workId，不存在就创建一个永久有序节点，将序号作为workId，并且将workId信息写入本地缓存文件workerID.properties，供启动时连接Zookeeper失败，读取使用。因为workId只分配了10个二进制位，所以取值范围是0-1023。

 

序列号怎么生成？

序列号是12个二进制位，取值范围是0到4095，主要保证同一个leaf服务在同一毫秒内，生成的ID的唯一性。
序列号是生成流程如下：
        1.当前时间戳与上一个ID的时间戳在同一毫秒内，那么对sequence+1，如果sequence+1超过了4095，那么进行等待，等到下一毫秒到了之后再生成ID。
        2.当前时间戳与上一个ID的时间戳不在同一毫秒内，取一个100以内的随机数作为序列号。

if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;if (sequence == 0) {//seq 为0的时候表示是下一毫秒时间开始对seq做随机sequence = RANDOM.nextInt(100);timestamp = tilNextMillis(lastTimestamp);}
} else {//如果是新的ms开始sequence = RANDOM.nextInt(100);
}
lastTimestamp = timestamp;

二、segment生成ID的模式

这种模式需要依赖MySQL，表字段biz_tag代表业务名，max_id代表该业务目前已分配的最大ID值，step代表每次Leaf往数据库请求时，一次性分配的ID数量。

大致流程就是每个Leaf服务在内存中有两个Segment实例，每个Segement保存一个分段的ID：

• 一个Segment是当前用于分配ID，有一个value属性保存这个分段已分配的最大ID，以及一个max属性这个分段最大的ID。
• 另外一个Segement是备用的，当一个Segement用完时，会进行切换，使用另一个Segement进行使用。
• 当一个Segement的分段ID使用率达到10%时，就会触发另一个Segement去DB获取分段ID，初始化好分段ID供之后使用。

Segment {private AtomicLong value = new AtomicLong(0);private volatile long max;private volatile int step;
}
SegmentBuffer {private String key;private Segment[] segments; //双bufferprivate volatile int currentPos; //当前的使用的segment的indexprivate volatile boolean nextReady; //下一个segment是否处于可切换状态private volatile boolean initOk; //是否初始化完成private final AtomicBoolean threadRunning; //线程是否在运行中private final ReadWriteLock lock;private volatile int step;private volatile int minStep;private volatile long updateTimestamp;
}

这篇关于Leaf原理分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---