分布式系統(tǒng)中畦攘，有一些需要使用全局唯一ID的場(chǎng)景霸妹，這種時(shí)候?yàn)榱朔乐笽D沖突可以使用36位的UUID，但是UUID有一些缺點(diǎn)知押，首先他相對(duì)比較長(zhǎng)叹螟，另外UUID一般是無序的。
有些時(shí)候我們希望能使用一種簡(jiǎn)單一些的ID台盯，并且希望ID能夠按照時(shí)間有序生成罢绽。而Twitter的SnowFlake算法解決了這種需求，并且該算法生成id的效率是極高的爷恳。
1. SnowFlake
SnowFlake算法產(chǎn)生的ID是一個(gè)64位的整型有缆，結(jié)構(gòu)如下（每一部分用“-”符號(hào)分隔）：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000
1位標(biāo)識(shí)部分，在java中由于long的最高位是符號(hào)位温亲，正數(shù)是0棚壁，負(fù)數(shù)是1，一般生成的ID為正數(shù)栈虚，所以為0袖外；
41位時(shí)間戳部分，這個(gè)是毫秒級(jí)的時(shí)間魂务，一般實(shí)現(xiàn)上不會(huì)存儲(chǔ)當(dāng)前的時(shí)間戳曼验，而是時(shí)間戳的差值（當(dāng)前時(shí)間-固定的開始時(shí)間），這樣可以使產(chǎn)生的ID從更小值開始粘姜；41位的時(shí)間戳可以使用69年鬓照，(1L << 41) / (1000L 60 60 24 365) = 69年；
10位節(jié)點(diǎn)部分孤紧，Twitter實(shí)現(xiàn)中使用前5位作為數(shù)據(jù)中心標(biāo)識(shí)豺裆，后5位作為機(jī)器標(biāo)識(shí)，可以部署1024個(gè)節(jié)點(diǎn)号显；
12位序列號(hào)部分臭猜，支持同一毫秒內(nèi)同一個(gè)節(jié)點(diǎn)可以生成4096個(gè)ID；
SnowFlake算法生成的ID大致上是按照時(shí)間遞增的押蚤，用在分布式系統(tǒng)中時(shí)蔑歌，需要注意數(shù)據(jù)中心標(biāo)識(shí)和機(jī)器標(biāo)識(shí)必須唯一，這樣就能保證每個(gè)節(jié)點(diǎn)生成的ID都是唯一的揽碘。
2. 算法實(shí)現(xiàn)
public class IdWorker {
// 時(shí)間起始標(biāo)記點(diǎn)次屠，作為基準(zhǔn)园匹，一般取系統(tǒng)的最近時(shí)間（一旦確定不能變動(dòng)）
private final static long twepoch = 1288834974657L;
// 機(jī)器標(biāo)識(shí)位數(shù)
private final static long workerIdBits = 5L;
// 數(shù)據(jù)中心標(biāo)識(shí)位數(shù)
private final static long datacenterIdBits = 5L;
// 機(jī)器ID最大值
private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 數(shù)據(jù)中心ID最大值
private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
// 毫秒內(nèi)自增位
private final static long sequenceBits = 12L;
// 機(jī)器ID偏左移12位
private final static long workerIdShift = sequenceBits;
// 數(shù)據(jù)中心ID左移17位
private final static long datacenterIdShift = sequenceBits + workerIdBits;
// 時(shí)間毫秒左移22位
private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
/* 上次生產(chǎn)id時(shí)間戳 */
private static long lastTimestamp = -1L;
// 0，并發(fā)控制
private long sequence = 0L;
private final long workerId;
// 數(shù)據(jù)標(biāo)識(shí)id部分
private final long datacenterId;
public IdWorker() {
this.datacenterId = getDatacenterId(maxDatacenterId);
this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
}
/**
* @param workerId 工作機(jī)器ID
* @param datacenterId 序列號(hào)
*/
public IdWorker(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;
}
/**
* 獲取下一個(gè)ID
*
* @return
*/
public synchronized String nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate uuid for %d milliseconds", lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
// 當(dāng)前毫秒內(nèi)帅矗，則+1
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
// 當(dāng)前毫秒內(nèi)計(jì)數(shù)滿了偎肃，則等待下一秒
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
// ID偏移組合生成最終的ID，并返回ID
long nextId = ((timestamp - twepoch) << timestampLeftShift)
| (datacenterId << datacenterIdShift)
| (workerId << workerIdShift) | sequence;
return String.valueOf(nextId);
}
private long tilNextMillis(final long lastTimestamp) {
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
/**
* <p>
* 獲取 maxWorkerId
* </p>
*/
protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
StringBuffer mpid = new StringBuffer();
mpid.append(datacenterId);
String name = ManagementFactory.getRuntimeMXBean().getName();
if (!name.isEmpty()) {
/*
* GET jvmPid
*/
mpid.append(name.split("@")[0]);
}
/*
* MAC + PID 的 hashcode 獲取16個(gè)低位
*/
return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}
/**
* <p>
* 數(shù)據(jù)標(biāo)識(shí)id部分
* </p>
*/
protected static long getDatacenterId(long maxDatacenterId) {
long id = 0L;
try {
InetAddress ip = InetAddress.getLocalHost();
NetworkInterface network = NetworkInterface.getByInetAddress(ip);
if (network == null) {
id = 1L;
} else {
byte[] mac = network.getHardwareAddress();
id = ((0x000000FF & (long) mac[mac.length - 1])
| (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
id = id % (maxDatacenterId + 1);
}
} catch (Exception e) {
System.out.println(" getDatacenterId: " + e.getMessage());
}
return id;
}
}
使用時(shí)浑此，只需要new IdWorker().next()即可累颂。
