1.寫唯一ID生成器的原由
在閱讀工程源碼的時(shí)候脆荷，發(fā)現(xiàn)有一個(gè)工具職責(zé)生成一個(gè)消息ID，方便進(jìn)行全鏈路的查詢懊悯，實(shí)現(xiàn)方式特別簡(jiǎn)單蜓谋，核心源碼不過兩行，根據(jù)時(shí)間戳以及隨機(jī)數(shù)生成一個(gè)ID炭分，這種算法ID在分布式系統(tǒng)中重復(fù)的風(fēng)險(xiǎn)就很明顯了桃焕。本來以為只是日志打印功能，根據(jù)于此在不同系統(tǒng)調(diào)用間關(guān)聯(lián)業(yè)務(wù)日志而已捧毛，不過后來發(fā)現(xiàn)此ID需要入庫观堂，看到這里就覺得有些風(fēng)險(xiǎn)了，于是就想著怎么改造它呀忧。
String timeString = String.valueOf(System.currentTimeMillis());
return Long.parseLong(timeString.substring(timeString.length() - 8, timeString.length()))
* RandomUtils.nextInt(1, 9);
2. Twitter snowflake
既然是分布式唯一ID师痕，自然而然想到了Twitter的snowflake算法，在以前的做的部分業(yè)務(wù)中也用到過它來生成數(shù)據(jù)庫主鍵ID而账，不過當(dāng)時(shí)僅限于使用胰坟，以及將64 bit的long數(shù)字拆分成幾個(gè)部分，以保證唯一泞辐，對(duì)具體實(shí)現(xiàn)沒有深入研究笔横。正好借著機(jī)會(huì)深入下。
該ID生成方式铛碑，用41位時(shí)間戳保存當(dāng)前時(shí)間的毫秒數(shù)（69年后一個(gè)輪回）狠裹，十位機(jī)器碼虽界，最多可以供一項(xiàng)業(yè)務(wù)1024臺(tái)實(shí)例汽烦，每個(gè)毫秒數(shù)，12位序列自增莉御，每秒理論上單機(jī)環(huán)境可生產(chǎn)409.6萬個(gè)ID撇吞，分享一個(gè)官方github的scala實(shí)現(xiàn)，twitter-archive/snowflake礁叔。
3.關(guān)于snowflake的一些思考
1.監(jiān)視器鎖
此鎖的目的是為了保證在多線程的情況下牍颈，只有一個(gè)線程進(jìn)入方法體生成ID，保證并發(fā)情況下生成ID的唯一性琅关，如果在競(jìng)爭(zhēng)激烈情況下煮岁，自旋鎖+ CAS原子變量的方式或許是更為合理的選擇，可以達(dá)到優(yōu)化部分性能的目的。
2.時(shí)間回退問題
時(shí)間校準(zhǔn)画机，以及其他因素冶伞，可能導(dǎo)致服務(wù)器時(shí)間回退（時(shí)間向前快進(jìn)不會(huì)有問題），如果恰巧回退前生成過一些ID步氏，而時(shí)間回退后响禽，生成的ID就有可能重復(fù)。官方對(duì)于此并沒有給出解決方案荚醒，而是簡(jiǎn)單的拋錯(cuò)處理芋类，這樣會(huì)造成在時(shí)間被追回之前的這段時(shí)間服務(wù)不可用，顯然我無法接受這一點(diǎn)界阁。
而對(duì)于此的思考是侯繁，既然snowflake理論情況下單機(jī)可實(shí)現(xiàn)每秒409.6萬個(gè)ID的生成上限，實(shí)際上能想得到的業(yè)務(wù)都不太可能產(chǎn)生如此高的并發(fā)铺董，那么就會(huì)存在在過去的一段時(shí)間內(nèi)巫击，有大量的時(shí)間戳“被浪費(fèi)”，達(dá)不到該上限精续，可能在某一毫秒內(nèi)只生成幾個(gè)ID,如果發(fā)生了時(shí)間回退坝锰，這些“被浪費(fèi)”的資源是不是就能利用起來，而不是拋錯(cuò)重付。
如果在內(nèi)存中建立一個(gè)數(shù)組顷级，這個(gè)數(shù)組設(shè)定固定長(zhǎng)度，比如說200确垫，這些數(shù)組中存儲(chǔ)上一次該位置對(duì)應(yīng)的毫秒數(shù)的messageId弓颈，那么就能在時(shí)間回退到追回時(shí)間這段時(shí)間內(nèi)，再至多提供819200（(2^12) *200）個(gè)messageId删掀，如果發(fā)生時(shí)間回退翔冀，就只用在上一次messageId進(jìn)行+1操作，直到系統(tǒng)時(shí)間被追回（此段結(jié)合后續(xù)源碼進(jìn)行解釋）披泪。
4.改進(jìn)版的snowflake
1.機(jī)器碼生成器 MachineIdService設(shè)計(jì)及其實(shí)現(xiàn)：
public interface MachineIdService {
/**
* 生成MachineId的方法
*
* @return machineId 機(jī)器碼
* @throws MessageIdException 獲取機(jī)器碼可能因?yàn)橥獠恳蛩厥? */
Long getMachineId() throws MessageIdException;
}
實(shí)現(xiàn)該接口確保一個(gè)集群中纤子，每臺(tái)實(shí)例生成不同的machineID，并且MachineID 不能超過(2^10) 1023,具體實(shí)現(xiàn)方式款票，可使用MySQL數(shù)據(jù)庫控硼，文件描述映射，Redis自增等方式艾少，這里我使用了Redis自增的方式（所以在需要用到該ID生成器的地方需要依賴Redis）卡乾，具體實(shí)現(xiàn)方式如下：
public class RedisMachineIdServiceImpl implements MachineIdService {
private static final String MAX_ID = "MAX_ID";
private static final String IP_MACHINE_ID_MAPPING = "IP_MACHINE_ID_MAPPING";
private RedisTemplate<String, String> redisTemplate;
private String redisKeyPrefix;
//設(shè)置RedisTemplate實(shí)例
public void setRedisTemplate(RedisTemplate<String, String> redisTemplate) {
this.redisTemplate = redisTemplate;
}
// 設(shè)置redisKey前綴，如果多個(gè)業(yè)務(wù)使用同一個(gè)Redis集群缚够，使用不同的Redis前綴進(jìn)行區(qū)分
public void setRedisKeyPrefix(String redisKeyPrefix) {
this.redisKeyPrefix = redisKeyPrefix;
}
@Override
public Long getMachineId() throws MessageIdException {
String host;
try {
//獲取本機(jī)IP地址
host = InetAddress.getLocalHost().getHostAddress();
} catch (UnknownHostException e) {
throw new MessageIdException("Can not get the host!", e);
}
if (redisTemplate == null) {
throw new MessageIdException("Can not get the redisTemplate instance!");
}
if (redisKeyPrefix == null) {
throw new MessageIdException("The redis key prefix is null,please set redis key prefix first!");
}
HashOperations<String, String, Long> hashOperations = redisTemplate.opsForHash();
//通過IP地址在Redis中的映射幔妨，找到本機(jī)的MachineId
Long result = hashOperations.get(redisKeyPrefix + IP_MACHINE_ID_MAPPING, host);
if (result != null) {
return result;
}
//如果沒有找到鹦赎，說明需要對(duì)該實(shí)例進(jìn)行新增MachineId，使用Redis的自增函數(shù)误堡，生成一個(gè)新的MachineId
Long incrementResult = redisTemplate.opsForValue().increment(redisKeyPrefix + MAX_ID, 1L);
if (incrementResult == null) {
throw new MessageIdException("Get the machine id failed,please check the redis environment!");
}
//將生成的MachineId放入Redis中钙姊，方便下次查找映射
hashOperations.put(redisKeyPrefix + IP_MACHINE_ID_MAPPING, host, incrementResult);
return incrementResult;
}
}
2.MessageIdService設(shè)計(jì)以及實(shí)現(xiàn)
public interface MessageIdService {
/**
* 生成一個(gè)保證全局唯一的MessageId
*
* @return messageId
*/
long genMessageId();
/**
* 初始化方法
*
* @throws MessageIdException
*/
void init() throws MessageIdException;
}
public class MessageIdServiceImpl implements MessageIdService {
private static final Logger LOGGER = LoggerFactory.getLogger(MessageIdServiceImpl.class);
//最大的MachineId，1024個(gè)
private static final long MAX_MACHINE_ID = 1023L;
//AtomicLongArray 環(huán)的大小埂伦，可保存200毫秒內(nèi)煞额，每個(gè)毫秒數(shù)上一次的MessageId，時(shí)間回退的時(shí)候依賴與此
private static final int CAPACITY = 200;
// 時(shí)間戳在messageId中左移的位數(shù)
private static final int TIMESTAMP_SHIFT_COUNT = 22;
// 機(jī)器碼在messageId中左移的位數(shù)
private static final int MACHINE_ID_SHIFT_COUNT = 12;
// 序列號(hào)的掩碼 2^12 4096
private static final long SEQUENCE_MASK = 4095L;
//messageId 沾谜，開始的時(shí)間戳膊毁，start the world，世界初始之日
private static long START_THE_WORLD_MILLIS;
//機(jī)器碼變量
private long machineId;
// messageId環(huán)基跑，解決時(shí)間回退的關(guān)鍵婚温，亦可在多線程情況下減少毫秒數(shù)切換的競(jìng)爭(zhēng)
private AtomicLongArray messageIdCycle = new AtomicLongArray(CAPACITY);
//生成MachineIds的實(shí)例
private MachineIdService machineIdService;
static {
try {
//使用一個(gè)固定的時(shí)間作為start the world的初始值
START_THE_WORLD_MILLIS = SimpleDateFormat.getDateTimeInstance().parse("2018-09-13 00:00:00").getTime();
} catch (ParseException e) {
throw new RuntimeException("init start the world millis failed", e);
}
}
public void setMachineIdService(MachineIdService machineIdService) {
this.machineIdService = machineIdService;
}
/**
* init方法中通過machineIdService 獲取本機(jī)的machineId
* @throws MessageIdException
*/
@Override
public void init() throws MessageIdException {
if (machineId == 0L) {
machineId = machineIdService.getMachineId();
}
//獲取的machineId 不能超過最大值
if (machineId <= 0L || machineId > MAX_MACHINE_ID) {
throw new MessageIdException("the machine id is out of range,it must between 1 and 1023");
}
}
/**
* 核心實(shí)現(xiàn)的代碼
*/
@Override
public long genMessageId() {
do {
// 獲取當(dāng)前時(shí)間戳，此時(shí)間戳是當(dāng)前時(shí)間減去start the world的毫秒數(shù)
long timestamp = System.currentTimeMillis() - START_THE_WORLD_MILLIS;
// 獲取當(dāng)前時(shí)間在messageIdCycle 中的下標(biāo)媳否，用于獲取環(huán)中上一個(gè)MessageId
int index = (int)(timestamp % CAPACITY);
long messageIdInCycle = messageIdCycle.get(index);
//通過在messageIdCycle 獲取到的messageIdInCycle栅螟，計(jì)算上一個(gè)MessageId的時(shí)間戳
long timestampInCycle = messageIdInCycle >> TIMESTAMP_SHIFT_COUNT;
// 如果timestampInCycle 并沒有設(shè)置時(shí)間戳，或時(shí)間戳小于當(dāng)前時(shí)間篱竭，認(rèn)為需要設(shè)置新的時(shí)間戳
if (messageIdInCycle == 0 || timestampInCycle < timestamp) {
long messageId = timestamp << TIMESTAMP_SHIFT_COUNT | machineId << MACHINE_ID_SHIFT_COUNT;
// 使用CAS的方式保證在該條件下力图，messageId 不被重復(fù)
if (messageIdCycle.compareAndSet(index, messageIdInCycle, messageId)) {
return messageId;
}
LOGGER.debug("messageId cycle CAS1 failed");
}
// 如果當(dāng)前時(shí)間戳與messageIdCycle的時(shí)間戳相等，使用環(huán)中的序列號(hào)+1的方式掺逼，生成新的序列號(hào)
// 如果發(fā)生了時(shí)間回退的情況吃媒，（即timestampInCycle > timestamp的情況）那么不能也更新messageIdCycle 的時(shí)間戳，使用Cycle中MessageId+1
if (timestampInCycle >= timestamp) {
long sequence = messageIdInCycle & SEQUENCE_MASK;
if (sequence >= SEQUENCE_MASK) {
LOGGER.debug("over sequence mask :{}", sequence);
continue;
}
long messageId = messageIdInCycle + 1L;
// 使用CAS的方式保證在該條件下吕喘，messageId 不被重復(fù)
if (messageIdCycle.compareAndSet(index, messageIdInCycle, messageId)) {
return messageId;
}
LOGGER.debug("messageId cycle CAS2 failed");
}
// 整個(gè)生成過程中赘那，采用的spinLock
} while (true);
}
}
