基于Twitter ID 生成策略
- 每秒能生成幾十萬條 ID
ID 生成要以一種非協(xié)作的（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 條開始查找即可。
解決方案
Twitter 解決這兩個問題的方案非常簡單高效：每一個 ID 都是 64 位數字，由時間戳、節(jié)點號和序列編號組成。其中序列編號是每個節(jié)點本地生成的序號，而節(jié)點號則由 ZooKeeper 維護。實現(xiàn)代碼
/**
* @author zhujuan
* From: https://github.com/twitter/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;
}
}
基于Instagram 的ID生成策略
生成的ID可以按時間排序
與Twitter需求大致相同ID最好是64bit的
為了索引更小且方便存儲在像Redis這樣的系統(tǒng)中按照某種用戶標識進行邏輯分片
解決方案
- 41bits 存儲毫秒格式的時間
- 10bits 表示邏輯分片ID
原方案是13bits（最多8192個邏輯分片）,這里為了與基于Twitter的策略保持大致一致，改成了10bits - 12bits 存儲自增序列值
原方案是10bits（最多1024個序列）,這里為了與基于Twitter的策略保持大致一致，改成了12bits(最多4096個序列)
- 代碼實現(xiàn)
/**
*
* @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;
}
}
完整源碼地址
項目已經托管到github,飛機在這里? 數值型id生成器
