雪花算法这一在分布式架构中很常见的玩意，但一般也不需要怎么去深入了解，一方面一般个人项目用不到分布式之类的大型架构，另一方面，就算要用到，市面上很多 ID 生成器也帮我们完成了这项工作。
不能出现有重复的 ID 标识，这是基本要求。
确保生成 ID 对于用户或业务是递增的。
确保任何时候都能生成正确的 ID。
在高并发的环境下依然表现良好。
Java 自带的生成一串唯一随机 36 位字符串（32 个字符串 + 4 个“-”）的算法。它可以保证唯一性，且据说够用 N 亿年，但是其业务可读性差，无法有序递增。
今天的主角雪花算法，它是 Twitter 开源的由 64 位整数组成分布式 ID，性能较高，并且在单机上递增。具体参考：
UidGenerator 是百度开源的分布式 ID 生成器，其基于雪花算法实现。具体参考：
https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
Leaf 是美团开源的分布式 ID 生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper 等中间件。具体参考：
SnowFlake 是 Twitter 公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的ID。
1.第一位 占用 1bit，其值始终是 0，没有实际作用。
2.时间戳 占用 41bit，精确到毫秒，总共可以容纳约 69 年的时间。
3.工作机器id 占用 10bit，其中高位 5bit 是数据中心 ID，低位 5bit 是工作节点 ID，做多可以容纳 1024 个节点。
4.序列号 占用 12bit，每个节点每毫秒 0 开始不断累加，最多可以累加到 4095，一共可以产生 4096 个 ID。
SnowFlake 算法在同一毫秒内最多可以生成多少个全局唯一 ID 呢？
同一毫秒的ID数量 = 1024 X 4096 = 4194304
雪花算法的实现主要依赖于数据中心 ID 和数据节点 ID 这两个参数，具体实现如下：
Jeffrey的博客
public class SnowflakeIdWorker {
/**
* 开始时间截 (2015-01-01)
*/
private final long twepoch = 1420041600000L;
/**
* 机器 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 SnowflakeIdWorker(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;
}
/**
* 获得下一个 ID (该方法是线程安全的)
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
// 如果当前时间小于上一次 ID 生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// 如果是同一时间生成的，则进行毫秒内序列
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();
}
public static void main(String[] args) throws InterruptedException {
SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
for (int i = 0; i < 10; i++) {
long id = idWorker.nextId();
Thread.sleep(1);
System.out.println(id);
}
}
}
# -*- coding: utf-8 -*-
import time
class InvalidSystemClock(Exception):
"""
时钟回拨异常
"""
pass
# 64 位 ID 的划分
WORKER_ID_BITS = 5
DATA_CENTER_ID_BITS = 5
SEQUENCE_BITS = 12
# 最大取值计算
MAX_WORKER_ID = -1 ^ (-1 << WORKER_ID_BITS) # 2**5-1 0b11111
MAX_DATA_CENTER_ID = -1 ^ (-1 << DATA_CENTER_ID_BITS)
# 移位偏移计算
WORKER_ID_SHIFT = SEQUENCE_BITS
DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS
TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS
# 序号循环掩码
SEQUENCE_MASK = -1 ^ (-1 << SEQUENCE_BITS)
# 开始时间截 (2015-01-01)
TWEPOCH = 1420041600000
class IdWorker(object):
"""
用于生成IDs
"""
def __init__(self, data_center_id, worker_id, sequence=0):
"""
初始化
:param data_center_id: 数据中心（机器区域） ID
:param worker_id: 机器 ID
:param sequence: 起始序号
"""
# sanity check
if worker_id > MAX_WORKER_ID or worker_id < 0:
raise ValueError('worker_id不合法')
if data_center_id > MAX_DATA_CENTER_ID or data_center_id < 0:
raise ValueError('data_center_id不合法')
self.worker_id = worker_id
self.data_center_id = data_center_id
self.sequence = sequence
self.last_timestamp = -1 # 上次计算的时间戳
@staticmethod
def _gen_timestamp():
"""
生成整数时间戳
:return:int timestamp
"""
return int(time.time() * 1000)
def _til_next_millis(self, last_timestamp):
"""
等到下一毫秒
"""
timestamp = self._gen_timestamp()
while timestamp <= last_timestamp:
timestamp = self._gen_timestamp()
return timestamp
def get_id(self):
"""
获取新 ID
:return:
"""
timestamp = self._gen_timestamp()
# 时钟回拨
if timestamp < self.last_timestamp:
raise InvalidSystemClock
if timestamp == self.last_timestamp:
self.sequence = (self.sequence + 1) & SEQUENCE_MASK
if self.sequence == 0:
timestamp = self._til_next_millis(self.last_timestamp)
else:
self.sequence = 0
self.last_timestamp = timestamp
new_id = ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | (self.data_center_id << DATA_CENTER_ID_SHIFT) | \
(self.worker_id << WORKER_ID_SHIFT) | self.sequence
return new_id
if __name__ == '__main__':
idWorker = IdWorker(0, 0)
for i in range(10):
print(idWorker.get_id())