mysql實作的雪花演算法

【相關學習推薦：mysql影片教學】

#一、為何要用雪花演算法

1、問題產生的背景

現在越來越多的公司都在用分散式、微服務，那麼對應的就會針對不同的服務進行資料庫拆分，然後當資料量上來的時候也會進行分錶，那麼隨之而來的就是分錶以後id的問題。

例如先前單體項目中一個表格中的資料主鍵id都是自增的，mysql是利用autoincrement來實現自增，而oracle是利用序列來實現的，但是當單表資料量上來以後就要進行水平分錶，阿里java開發建議是單表大於500w的時候就要分錶，但是具體還是得看業務，如果索引用的號的話，單表千萬的數據也是可以的。水平分錶就是將一張表的資料分成多張表，那麼問題就來瞭如果還是按照以前的自增來做主鍵id，那麼就會出現id重複，這個時候就得考慮用什麼方案來解決分佈式id的問題了。

2、解決方案

2.1、資料庫表

可以在某個庫中專門維護一張表，然後每次無論哪個表需要自增id的時候都去查這個表的記錄，然後用for update鎖表，然後取到的值加一，然後返回以後把再把值記錄到表中，但是這個方法適合併發量比較小的項目，因此每次都得鎖表。

2.2、redis

因為redis是單線程的，可以在redis中維護一個鍵值對，然後哪個表需要直接去redis中取值然後加一，但是這個跟上面同樣由於單線程都是對高並發的支援不高，只適合併發量小的項目。

2.3、uuid

可以使用uuid作為不重複主鍵id，但是uuid有個問題就是其是無序的字串，如果使用uuid當做主鍵，那麼主鍵索引就會失效。

2.4、雪花演算法

雪花演算法是解決分散式id的一個高效率的方案，大部分網路公司都在使用雪花演算法，當然還有公司自己實作其他的方案。

二、雪花演算法

1、原理

儲存id，最高位元一位儲存0或1,0代表整數，1代表負數，通常都是0，所以最高位元不變，41位元儲存毫秒時間戳，10位元儲存機器碼（包含5位元datacenterId和5位元workerId），12儲存序號。這樣最大2的10次方的機器，也就是1024台機器，最多每毫秒每台機器產生2的12次方也就是4096個id。 （下面有程式碼實作）

但是一般我們沒有那麼多台機器，所以我們也可以使用53位元來儲存id。為什麼要用53位？

因為我們幾乎都是跟web頁面打交道，就需要跟js打交道，js支援最大的整型範圍為53位，超過這個範圍就會失去精度，53之內可以直接由js讀取，超過53位元就需要轉換成字串才能確保js處理正確。 53儲存的話，32位元儲存秒級時間戳，5位元儲存機器碼，16位元儲存序列化，這樣每台機器每秒可以生產65536個不重複的id。

2、缺點

由於雪花演算法嚴重依賴時間，所以當發生伺服器時鐘回撥的問題是會導致可能產生重複的id。當然幾乎沒有公司會修改伺服器時間，修改以後會導致各種問題，公司寧願新加一台伺服器也不願意修改伺服器時間，但不排除特殊情況。

如何解決時鐘回撥的問題？序列化的初始值可以設定步長，每次觸發時脈回撥事件，則其初始步長就加1w，可以在下面程式碼的第85行來實現，將sequence的初始值設定為10000。

三、程式碼實作

64位元的程式碼實作：

package com.yl.common;
/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeIdWorker {

 // ==============================Fields===========================================
 /** 开始时间截 (2020-01-01) */
 private final long twepoch = 1577808000000L;

 /** 机器id所占的位数 */
 private final long workerIdBits = 5L;

 /** 数据标识id所占的位数 */
 private final long datacenterIdBits = 5L;

 /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
 private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

 /** 支持的最大数据标识id，结果是31 */
 private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

 /** 序列在id中占的位数 */
 private final long sequenceBits = 12L;

 /** 机器ID向左移12位 */
 private final long workerIdShift = sequenceBits;

 /** 数据标识id向左移17位(12+5) */
 private final long datacenterIdShift = sequenceBits + workerIdBits;

 /** 时间截向左移22位(5+5+12) */
 private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

 /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
 private final long sequenceMask = -1L ^ (-1L << sequenceBits);

 /** 工作机器ID(0~31) */
 private long workerId;

 /** 数据中心ID(0~31) */
 private long datacenterId;

 /** 毫秒内序列(0~4095) */
 private long sequence = 0L;

 /** 上次生成ID的时间截 */
 private long lastTimestamp = -1L;

 //==============================Constructors=====================================
 /**
 * 构造函数
 * @param workerId 工作ID (0~31)
 * @param datacenterId 数据中心ID (0~31)
 */
 public SnowflakeIdWorker(long workerId, long datacenterId) {
 if (workerId > maxWorkerId || workerId < 0) {
 throw new IllegalArgumentException(String.format("worker Id can&#39;t be greater than %d or less than 0", maxWorkerId));
 }
 if (datacenterId > maxDatacenterId || datacenterId < 0) {
 throw new IllegalArgumentException(String.format("datacenter Id can&#39;t be greater than %d or less than 0", maxDatacenterId));
 }
 this.workerId = workerId;
 this.datacenterId = datacenterId;
 }

 // ==============================Methods==========================================
 /**
 * 获得下一个ID (该方法是线程安全的)
 * @return SnowflakeId
 */
 public synchronized long nextId() {
 long timestamp = timeGen();

 //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
 if (timestamp < 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;
 }

 //上次生成ID的时间截
 lastTimestamp = timestamp;

 //移位并通过或运算拼到一起组成64位的ID
 return ((timestamp - twepoch) << timestampLeftShift) //
 | (datacenterId << datacenterIdShift) //
 | (workerId << workerIdShift) //
 | sequence;
 }

 /**
 * 阻塞到下一个毫秒，直到获得新的时间戳
 * @param lastTimestamp 上次生成ID的时间截
 * @return 当前时间戳
 */
 protected long tilNextMillis(long lastTimestamp) {
 long timestamp = timeGen();
 while (timestamp <= lastTimestamp) {
 timestamp = timeGen();
 }
 return timestamp;
 }

 /**
 * 返回以毫秒为单位的当前时间
 * @return 当前时间(毫秒)
 */
 protected long timeGen() {
 return System.currentTimeMillis();
 }

 //==============================Test=============================================
 /** 测试 */
 public static void main(String[] args) {
 SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
 
 for (int i = 0; i < 100; i++) {
 long id = idWorker.nextId();
 System.out.println(id);
 }
 }
}

補充知識： 雪花演算法實作分散式自成長ID

我就廢話不多說了，大家還是直接看程式碼吧~

/**
 * <p>名称：IdWorker.java</p>
 * <p>描述：分布式自增长ID</p>
 * <pre class="brush:php;toolbar:false">
 * Twitter的 Snowflake　JAVA实现方案
 * 

* 核心代码为其IdWorker这个类实现，其原理结构如下，我分别用一个0表示一位，用—分割开部分的作用： * 1||0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000 * 在上面的字符串中，第一位为未使用（实际上也可作为long的符号位），接下来的41位为毫秒级时间， * 然后5位datacenter标识位，5位机器ID（并不算标识符，实际是为线程标识）， * 然后12位该毫秒内的当前毫秒内的计数，加起来刚好64位，为一个Long型。 * 这样的好处是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和机器ID作区分）， * 并且效率较高，经测试，snowflake每秒能够产生26万ID左右，完全满足需要。 *

* 64位ID (42(毫秒)+5(机器ID)+5(业务编码)+12(重复累加)) * * @author Polim */ public class IdWorker { // 时间起始标记点，作为基准，一般取系统的最近时间（一旦确定不能变动） private final static long twepoch = 1288834974657L; // 机器标识位数 private final static long workerIdBits = 5L; // 数据中心标识位数 private final static long datacenterIdBits = 5L; // 机器ID最大值 private final static long maxWorkerId = -1L ^ (-1L << workerIdBits); // 数据中心ID最大值 private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 毫秒内自增位 private final static long sequenceBits = 12L; // 机器ID偏左移12位 private final static long workerIdShift = sequenceBits; // 数据中心ID左移17位 private final static long datacenterIdShift = sequenceBits + workerIdBits; // 时间毫秒左移22位 private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; private final static long sequenceMask = -1L ^ (-1L << sequenceBits); /* 上次生产id时间戳 */ private static long lastTimestamp = -1L; // 0，并发控制 private long sequence = 0L; private final long workerId; // 数据标识id部分 private final long datacenterId; public IdWorker(){ this.datacenterId = getDatacenterId(maxDatacenterId); this.workerId = getMaxWorkerId(datacenterId, maxWorkerId); } /** * @param workerId * 工作机器ID * @param datacenterId * 序列号 */ 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; } /** * 获取下一个ID * * @return */ public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } if (lastTimestamp == timestamp) { // 当前毫秒内，则+1 sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { // 当前毫秒内计数满了，则等待下一秒 timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0L; } lastTimestamp = timestamp; // ID偏移组合生成最终的ID，并返回ID long nextId = ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; return 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(); } /** *

* 获取 maxWorkerId *

*/ 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个低位 */ return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1); } /** *

* 数据标识id部分 *

*/ 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; } }

相關推薦：程式設計影片課程

以上是mysql實作的雪花演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！