snowflake
<h1>snowflake</h1>
<p>SnowFlake算法是Twitter设计的一个可以在分布式系统中生成唯一的ID的算法，它可以满足Twitter每秒上万条消息ID分配的请求，这些消息ID是唯一的且有大致的递增顺序。</p>
<h2>snowflake算法原理</h2>
<p>SnowFlake算法产生的ID是一个64位的整型，结构如下（每一部分用“-”符号分隔）：
<img src="https://s2.ax1x.com/2019/12/17/QombYn.png" alt="snowflake算法" /></p>
<p>snowflake算法生成的id是一个64位的long型数字。</p>
<ul>
<li>1位标识部分</li>
</ul>
<p>在java中由于long的最高位是符号位，正数是0，负数是1，一般生成的ID为正数，所以为0；</p>
<ul>
<li>41位时间戳部分</li>
</ul>
<p>这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间-固定的开始时间），这样可以使产生的ID从更小值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L <em> 60 </em> 60 <em> 24 </em> 365) = 69年；</p>
<ul>
<li>10位节点部分</li>
</ul>
<p>Twitter实现中使用前5位作为数据中心标识，后5位作为机器标识，可以部署1024个节点，在Spring Cloud中可以为每一个实例生成唯一的机器识别码，这样就能保证每个实例中生成的id都不一样。</p>
<ul>
<li>12位序列号部分</li>
</ul>
<p>支持同一毫秒内同一个节点可以生成4096（2的12次方）个ID，这个同样可以扩展，但其实每毫秒生成4096个id已经能满足大部分场景了。</p>
<pre><code class="language-java">/**
* 基于Twitter的Snowflake算法实现分布式高效有序ID生产黑科技(sequence)
*
* SnowFlake的结构如下(每部分用-分开):
*
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
*
* 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
*
* 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)，
* 这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
*
* 10位的数据机器位，可以部署在1024个节点，包括5位dataCenterId和5位workerId
*
* 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号
*
* 加起来刚好64位，为一个Long型。
* SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
*
* @author 龙景强
* @date 2019/10/21
*/
public class Sequence {
/** 起始时间截 2019-10-21 16:42:13 */
private final long twepoch = 1571647333419L;
/** 机器标识id所占的位数 */
private final long workerIdBits = 5L;
/** 数据标识id所占的位数 */
private final long dataCenterIdBits = 5L;
/** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 支持的最大数据标识id，结果是31 */
private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
/** 毫秒内序列在id中占的位数 */
private final long sequenceBits = 12L;
/** 机器ID向左移12位 */
private final long workerIdShift = sequenceBits;
/** 数据标识id向左移17位(12+5) */
private final long dataCenterIdShift = sequenceBits + workerIdBits;
/** 时间截向左移22位(5+5+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
/** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** 工作机器ID(0~31) */
private long workerId;
/** 数据中心ID(0~31) */
private long dataCenterId;
/** 毫秒内序列(0~4095) */
private long sequence = 0L;
/** 上次生成ID的时间截 */
private long lastTimestamp = -1L;
/**
* @param workerId 工作ID (0~31)
* @param dataCenterId 数据中心ID (0~31)
*/
public Sequence(long workerId, long dataCenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("dataCenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerId;
this.dataCenterId = dataCenterId;
}
private Sequence() {
long workerID = ManageProperties.getInstance().getWorkerID();
long dataCenterId = ManageProperties.getInstance().getDataCenterID();
if (workerID > maxWorkerId || workerID < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("dataCenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
this.workerId = workerID;
this.dataCenterId = dataCenterId;
}
private static class SequenceHolder {
static Sequence sequence = new Sequence();
}
public static Sequence getInstance() {
return SequenceHolder.sequence;
}
/**
* 获得下一个ID (该方法是线程安全的)
*
* @return
*/
public synchronized long nextId() {
long timestamp = timeGen();
// 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过,这个时候应当抛出异常
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
wait(offset << 1);
timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
}
} catch (Exception e) {
throw new RuntimeException(e);
}
} else {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
}
}
// 如果是同一时间生成的，则进行毫秒内序列
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
// 毫秒内序列溢出
if (sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {// 时间戳改变，毫秒内序列重置
sequence = 0L;
}
// 上次生成ID的时间截
lastTimestamp = timestamp;
// 移位并通过或运算拼到一起组成64位的ID
return ((timestamp - twepoch) << timestampLeftShift)
| (dataCenterId << dataCenterIdShift)
| (workerId << workerIdShift)
| sequence;
}
/**
* 阻塞到下一个毫秒，直到获得新的时间戳
*
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒为单位的当前时间
*
* @return 当前时间(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
}
</code></pre>