雪花演算法及微服務集群唯一ID解決方案
- 2022 年 6 月 22 日
- 筆記
- mybatis/plus, MySQL, springboot
雪花演算法（SnowFlake）
簡介
現在的服務基本是分散式、微服務形式的，而且大數據量也導致分庫分表的產生，對於水平分表就需要保證表中 id 的全局唯一性。
對於 MySQL 而言，一個表中的主鍵 id 一般使用自增的方式，但是如果進行水平分表之後，多個表中會生成重複的 id 值。那麼如何保證水平分表後的多張表中的 id 是全局唯一性的呢？
如果還是藉助資料庫主鍵自增的形式，那麼可以讓不同表初始化一個不同的初始值，然後按指定的步長進行自增。例如有3張拆分表，初始主鍵值為1，2，3，自增步長為3。
當然也有人使用 UUID 來作為主鍵，但是 UUID 生成的是一個無序的字元串，對於 MySQL 推薦使用增長的數值類型值作為主鍵來說不適合。
也可以使用 Redis 的自增原子性來生成唯一 id，但是這種方式業內比較少用。
當然還有其他解決方案，不同互聯網公司也有自己內部的實現方案。雪花演算法是其中一個用於解決分散式 id 的高效方案，也是許多互聯網公司在推薦使用的。
SnowFlake 雪花演算法
SnowFlake 中文意思為雪花，故稱為雪花演算法。最早是 Twitter 公司在其內部用於分散式環境下生成唯一 ID。在2014年開源 scala 語言版本。
雪花演算法的原理就是生成一個的 64 位比特位的 long 類型的唯一 id。
最高 1 位固定值 0，因為生成的 id 是正整數，如果是 1 就是負數了。
接下來 41 位存儲毫秒級時間戳，2^41/(1000606024365)=69，大概可以使用 69 年。
再接下 10 位存儲機器碼，包括 5 位 datacenterId 和 5 位 workerId。最多可以部署 2^10=1024 台機器。
最後 12 位存儲序列號。同一毫秒時間戳時，通過這個遞增的序列號來區分。即對於同一台機器而言，同一毫秒時間戳下，可以生成 2^12=4096 個不重複 id。
可以將雪花演算法作為一個單獨的服務進行部署，然後需要全局唯一 id 的系統，請求雪花演算法服務獲取 id 即可。
對於每一個雪花演算法服務，需要先指定 10 位的機器碼，這個根據自身業務進行設定即可。例如機房號+機器號，機器號+服務號，或者是其他可區別標識的 10 位比特位的整數值都行。
實際應用
MybatisPlus實現
依賴：
<dependency>
<groupId>com.baomidou</groupId>
<artifactId>mybatis-plus-boot-starter</artifactId>
<version>3.3.1</version>
</dependency>
yml配置：
mybatis-plus:
configuration:
log-impl: org.apache.ibatis.logging.stdout.StdOutImpl
global-config:
worker-id: ${random.int(1,31)}
datacenter-id: ${random.int(1,31)}
測試實體：
@Data
@TableName("test_content")
public class TestContent {
/**
* ID
*/
@TableId(type = IdType.ASSIGN_ID)
private Long id;
/**
* 數據內容
*/
private String content;
/**
* 部門id
*/
private Integer deptId;
}
測試控制層：
@GetMapping("/test2")
public String add() {
TestContent testContent = new TestContent();
testContent.setContent(new Random().nextInt() + "自定義添加內容");
testContent.setDeptId(1);
int insert = testContentService.getBaseMapper().insert(testContent);
log.info("插入成功:{}", testContent.getId());
return "插入成功";
}
插入測試：
非ID欄位需要id時可使用Idwork
testContent.setId(IdWorker.getId());
源碼解析：
IdWorker提供獲取id的基本方法，底層通過DefaultIdentifierGenerator生成序列Sequence類用於生成雪花id
public class IdWorker {
private static IdentifierGenerator IDENTIFIER_GENERATOR = new DefaultIdentifierGenerator();
public static final DateTimeFormatter MILLISECOND = DateTimeFormatter.ofPattern("yyyyMMddHHmmssSSS");
public IdWorker() {
}
public static long getId() {
return getId(new Object());
}
public static long getId(Object entity) {
return IDENTIFIER_GENERATOR.nextId(entity).longValue();
}
public static String getIdStr() {
return getIdStr(new Object());
}
public static String getIdStr(Object entity) {
return IDENTIFIER_GENERATOR.nextId(entity).toString();
}
public static String getMillisecond() {
return LocalDateTime.now().format(MILLISECOND);
}
public static String getTimeId() {
return getMillisecond() + getIdStr();
}
public static void initSequence(long workerId, long dataCenterId) {
IDENTIFIER_GENERATOR = new DefaultIdentifierGenerator(workerId, dataCenterId);
}
public static void setIdentifierGenerator(IdentifierGenerator identifierGenerator) {
IDENTIFIER_GENERATOR = identifierGenerator;
}
public static String get32UUID() {
ThreadLocalRandom random = ThreadLocalRandom.current();
return (new UUID(random.nextLong(), random.nextLong())).toString().replace("-", "");
}
}
Sequence類：主要構造方法包含兩個參數 類比雪花演算法的機器ID和服務ID，集群模式下最好不要重複，否則可能會造成生成的Id重複,兩個參數可在YML文件中配置
public class Sequence {
private static final Log logger = LogFactory.getLog(Sequence.class);
private final long twepoch = 1288834974657L;
private final long workerIdBits = 5L;
private final long datacenterIdBits = 5L;
private final long maxWorkerId = 31L;
private final long maxDatacenterId = 31L;
private final long sequenceBits = 12L;
private final long workerIdShift = 12L;
private final long datacenterIdShift = 17L;
private final long timestampLeftShift = 22L;
private final long sequenceMask = 4095L;
private final long workerId;
private final long datacenterId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public Sequence() {
this.datacenterId = getDatacenterId(31L);
this.workerId = getMaxWorkerId(this.datacenterId, 31L);
}
public Sequence(long workerId, long datacenterId) {
Assert.isFalse(workerId > 31L || workerId < 0L, String.format("worker Id can't be greater than %d or less than 0", 31L), new Object[0]);
Assert.isFalse(datacenterId > 31L || datacenterId < 0L, String.format("datacenter Id can't be greater than %d or less than 0", 31L), new Object[0]);
this.workerId = workerId;
this.datacenterId = datacenterId;
}
protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
StringBuilder mpid = new StringBuilder();
mpid.append(datacenterId);
String name = ManagementFactory.getRuntimeMXBean().getName();
if (StringUtils.isNotBlank(name)) {
mpid.append(name.split("@")[0]);
}
return (long)(mpid.toString().hashCode() & '\uffff') % (maxWorkerId + 1L);
}
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();
if (null != mac) {
id = (255L & (long)mac[mac.length - 1] | 65280L & (long)mac[mac.length - 2] << 8) >> 6;
id %= maxDatacenterId + 1L;
}
}
} catch (Exception var7) {
logger.warn(" getDatacenterId: " + var7.getMessage());
}
return id;
}
public synchronized long nextId() {
long timestamp = this.timeGen();
if (timestamp < this.lastTimestamp) {
long offset = this.lastTimestamp - timestamp;
if (offset > 5L) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
}
try {
this.wait(offset << 1);
timestamp = this.timeGen();
if (timestamp < this.lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", offset));
}
} catch (Exception var6) {
throw new RuntimeException(var6);
}
}
if (this.lastTimestamp == timestamp) {
this.sequence = this.sequence + 1L & 4095L;
if (this.sequence == 0L) {
timestamp = this.tilNextMillis(this.lastTimestamp);
}
} else {
this.sequence = ThreadLocalRandom.current().nextLong(1L, 3L);
}
this.lastTimestamp = timestamp;
return timestamp - 1288834974657L << 22 | this.datacenterId << 17 | this.workerId << 12 | this.sequence;
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp;
for(timestamp = this.timeGen(); timestamp <= lastTimestamp; timestamp = this.timeGen()) {
}
return timestamp;
}
protected long timeGen() {
return SystemClock.now();
}
}
