Java實現數值型ID生成器
基于推ter ID 生成策略
-
每秒能生成幾十萬條 ID
ID 生成要以一種非協作的（uncoordinated）的方式進行，例如不能利用一個全局的原子變量。
-
ID 大致有序，就是說生成時間相近的兩個ID，它們的值也應當相近
按 ID 排序后滿足 k-sorted 條件。如果序列 A 要滿足 k-sorted，當且僅當對于任意的 p, q，如果 1 <= p <= q - k (1 <= p <= q <= n)，則有 A[p] <= A[q]。換句話說，如果元素 p 排在 q 前面，且相差至少 k 個位置，那么 p 必然小于或等于 q。如果ID序列滿足這個條件，要獲取第 r 條ID之后的記錄，只要從第 r - k 條開始查找即可。
-
解決方案
推ter 解決這兩個問題的方案非常簡單高效：每一個 ID 都是 64 位數字，由時間戳、節點號和序列編號組成。其中序列編號是每個節點本地生成的序號，而節點號則由 ZooKeeper 維護。
-
實現代碼
/**
- @author zhujuan
- From: https://github.com/推ter/snowflake
- An object that generates IDs.
- This is broken into a separate class in case
- we ever want to support multiple worker threads
per process
*/
public class IdWorker {
protected static final Logger LOG = LoggerFactory.getLogger(IdWorker.class);
private long workerId;
private long datacenterId;
private long sequence = 0L;
private long workerIdBits = 5L;
private long datacenterIdBits = 5L;
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
private long sequenceBits = 12L;
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask = -1L ^ (-1L << sequenceBits);
private long lastTimestamp = -1L;
public IdWorker(long workerId, long datacenterId) {
// sanity check for workerId
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;
LOG.info(String.format("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId));
}
public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
LOG.error(String.format("clock is moving backwards. Rejecting requests until %d.", 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;
}
lastTimestamp = timestamp;
return (timestamp << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
}
}</code></pre>
基于Instagram 的ID生成策略
-
生成的ID可以按時間排序
與推ter需求大致相同
-
ID最好是64bit的
為了索引更小且方便存儲在像Redis這樣的系統中
-
按照某種用戶標識進行邏輯分片
-
解決方案
-
41bits 存儲毫秒格式的時間
-
10bits 表示邏輯分片ID
原方案是13bits（最多8192個邏輯分片）,這里為了與基于推ter的策略保持大致一致，改成了10bits
-
12bits 存儲自增序列值
原方案是10bits（最多1024個序列）,這里為了與基于推ter的策略保持大致一致，改成了12bits(最多4096個序列)
-
代碼實現
/**
- @author Mr_Shang
@version 1.0
/
public class InstaIdGenerator {
protected static final Logger LOG = LoggerFactory.getLogger(IdWorker.class);
/**
- 時間戳的位數，實際占41位，最高位保持為0，保證long值為正數
*/
private int timestampBitCount = 42;
/**
- 邏輯分片位數
*/
private int regionBitCount = 10;
/**
- 邏輯分片的最大數量
*/
private int regionModelVal = 1 << regionBitCount;
/**
- 序列位數
*/
private int sequenceBitCount = 12;
/**
- 總的位數
*/
private int totalBitCount = timestampBitCount + regionBitCount + sequenceBitCount;
/**
- 當前序列值
*/
private long sequence = 0;
/**
- 最后一次請求時間戳
*/
private long lastTimestamp = -1L;
/**
- 序列的位板
*/
private long sequenceMask = -1L ^ (-1L << sequenceBitCount);
/**
- 最后一次請求用戶標識
*/
private long lastTag=1L;
public InstaIdGenerator() {
}
public InstaIdGenerator(long seq) {
if (seq < 0) {
seq = 0;
}
this.sequence = seq;
}
public synchronized long nextId(long tag) {
long timestamp = timeGen();
if(tag<0){
tag=-tag;
}
if (timestamp < lastTimestamp) {
LOG.error(String.format("clock is moving backwards. Rejecting requests until %d.", 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;
}
if(tag==lastTag){
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
}
lastTag=tag;
lastTimestamp = timestamp;
return (timestamp << (totalBitCount - timestampBitCount))
| ((tag % regionModelVal) << (totalBitCount - timestampBitCount - regionBitCount)) | sequence;
}
}</code></pre>
參考內容
來自：http://www.jianshu.com/p/d76e86fdf045