背景

最近項(xiàng)目上遇到一個(gè)改造主鍵生成策略的問題：需要將原Redis自增id改造成雪花算法。

一個(gè)好消息是項(xiàng)目用的ORM框架(Mybatis-Plus)自帶雪花算法生成策略，只需在id字段上加上特定的注解。

而問題在于該策略生成id為19位數(shù), 如：1582631966690799617，這樣的id返給前端存在精度丟失問題。

當(dāng)然，一個(gè)簡(jiǎn)單的辦法就是將id轉(zhuǎn)化為string類型，但是該業(yè)務(wù)流程長(zhǎng)，涉及范圍廣，改動(dòng)地方太多。

所以為了解決這樣的問題，我起了改造雪花算法生成策略的心思，也將這次改造過程中的收獲分享出來。

在此之前我先給大家介紹一下什么是雪花算法及原理

雪花算法

起源

雪花算法(snowflake)最早是twitter內(nèi)部使用的分布式下唯一id生成算法

https://github.com/twitter-archive/snowflake

該算法具有以下特性

• 唯一性：高并發(fā)分布式系統(tǒng)中生成id唯一
• 高性能：每秒可生成百萬個(gè)id
• 有序性：生成的id是有序遞增的

原理

雪花算法生成的id由64個(gè)bit組成，其中41bit填充時(shí)間戳，10bit填充工作機(jī)器id，12bit作為自增序列號(hào)。

image-20221019162610173.png

假設(shè)時(shí)間戳：1666168108422(ms), 轉(zhuǎn)為二進(jìn)制：11000001111101111010110111011010110000110

工作機(jī)器id: 1, 轉(zhuǎn)為二進(jìn)制：0000000001

序列號(hào)：1，轉(zhuǎn)為二進(jìn)制：000000000001

以上組成二進(jìn)制為：11000001111101111010110111011010110000110-0000000001-000000000001

轉(zhuǎn)為十進(jìn)制：6988415561826833844，一個(gè)id號(hào)就這樣生成了。

接下來分別介紹每部分的內(nèi)容。

時(shí)間戳

時(shí)間戳一般通過當(dāng)前時(shí)間-基準(zhǔn)時(shí)間計(jì)算得出。

基準(zhǔn)時(shí)間一般取最近時(shí)間（系統(tǒng)上線時(shí)間）。

因?yàn)楫?dāng)前時(shí)間是以1970年為基準(zhǔn)時(shí)間算起的，而我們只需要從系統(tǒng)上線時(shí)算起就可以了。

為什么要這樣做呢？我們可以來算一下該算法可以支持系統(tǒng)運(yùn)行到多少年。

首先算出41bit的最大數(shù)值：11111111111111111111111111111111111111111(二進(jìn)制) -> 2199023255551(十進(jìn)制)

假設(shè)我們以1970年作為基準(zhǔn)時(shí)間，那么當(dāng)時(shí)間達(dá)到2199023255551時(shí)，時(shí)間戳部分就超出41bit了。

將2199023255551進(jìn)行時(shí)間戳轉(zhuǎn)換：2039-09-07 23:47:35

以1970年作為基準(zhǔn)時(shí)間，該算法可運(yùn)行至2039-09-07 23:47:35

假設(shè)我們以最近時(shí)間2022-10-19 00:00:00作為基準(zhǔn)時(shí)間。

將2022-10-19 00:00:00轉(zhuǎn)為時(shí)間戳：1666108800000

那么系統(tǒng)可達(dá)到的最大時(shí)間為：1666108800000 + 2199023255551 = 3865132055551

3865132055551進(jìn)行時(shí)間戳轉(zhuǎn)換：2092-06-24 15:47:35

以2022年10月19日作為基準(zhǔn)時(shí)間，該算法可運(yùn)行至2092-06-24 15:47:35

工作機(jī)器id

工作機(jī)器id部分可以用來保證生成id的唯一性：分布式系統(tǒng)中，每個(gè)節(jié)點(diǎn)的工作機(jī)器id不同，那么生成的id也一定不同。

該部分占用10bit, 意味著可以部署1024個(gè)節(jié)點(diǎn)。

工作機(jī)器id的設(shè)置可以由開發(fā)者手動(dòng)設(shè)置，比如設(shè)置在JVM啟動(dòng)參數(shù)中，或者配置文件里，以保證工作機(jī)器id在每個(gè)節(jié)點(diǎn)的唯一性。

當(dāng)然，如果節(jié)點(diǎn)太多對(duì)于配置來說也是災(zāi)難性的，此時(shí)可以考慮使用機(jī)器的mac地址或者ip做hash運(yùn)算，以此作為工作機(jī)器id，但這就可能造成hash碰撞導(dǎo)致工作機(jī)器id重復(fù)(碰撞概率取決于hash算法)，從而會(huì)有極小的概率生成id重復(fù)。

有時(shí)我們沒有那么多的節(jié)點(diǎn)需要部署，那么就可以縮減該部分的bit位，用于增加時(shí)間戳部分bit位延長(zhǎng)算法的使用時(shí)間，或者增加序列號(hào)部分增加每毫秒可生成的id樹。

有時(shí)我們一個(gè)節(jié)點(diǎn)可能會(huì)部署多個(gè)實(shí)例，那么可以將10bit拆分，取5bit作為機(jī)器id，5bit作為進(jìn)程id。

當(dāng)然，你也可以取其中幾個(gè)bit做業(yè)務(wù)標(biāo)識(shí)。

由此可見，工作機(jī)器id部分是最容易自定義的部分

序列號(hào)

序列號(hào)部分用于在同一毫秒同一機(jī)器上生成不同的id號(hào)。

該部分占12bit，意味著同一毫秒同一機(jī)器上可生成4096個(gè)序列號(hào)，1秒即為4096000個(gè)(4百萬)

和另外兩個(gè)部分一樣，該部分同樣可以調(diào)整，如果單個(gè)實(shí)例的并發(fā)量確認(rèn)達(dá)不到這么高，那么同樣可以縮減該部分，將bit位讓予其他部分使用。

實(shí)現(xiàn)

知道原理之后，接下來分析一下代碼應(yīng)當(dāng)如何實(shí)現(xiàn)。

時(shí)間戳

時(shí)間戳部分有41bit, 值為當(dāng)前時(shí)間戳 - 基準(zhǔn)時(shí)間，轉(zhuǎn)化為JAVA代碼即為

long twepoch = 1666108800000L;

long time = System.currentTimeMillis() - twepoch;

這里在高并發(fā)多線程的場(chǎng)景下有個(gè)小小的優(yōu)化點(diǎn)，可以使用定時(shí)任務(wù)線程池將System.currentTimeMillis()緩存起來，其他線程從緩存中獲取。

public class SystemClock {

    private final long period;
    private final AtomicLong now;

    private SystemClock(long period) {
        this.period = period;
        this.now = new AtomicLong(System.currentTimeMillis());
        scheduleClockUpdating();
    }
    private void scheduleClockUpdating() {
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {
            Thread thread = new Thread(runnable, "System Clock");
            thread.setDaemon(true);
            return thread;
        });
        scheduler.scheduleAtFixedRate(() -> now.set(System.currentTimeMillis()), period, period, TimeUnit.MILLISECONDS);
    }

    private long currentTimeMillis() {
        return now.get();
    }
}

摘自：https://gitee.com/yu120/sequence

這里直接給出原因：

• 單線程情況下，直接調(diào)用System.currentTimeMillis()更快
• 高并發(fā)多線程情況下，使用緩存獲取時(shí)間戳更快

具體測(cè)試過程見文末參考

工作機(jī)器id

工作機(jī)器id可以在構(gòu)造方法中傳入，也可以取mac地址hash，方法如下

long id = 0L;
try {
  NetworkInterface network = NetworkInterface.getByInetAddress(getLocalAddress());
  if (null == network) {
    id = 1L;
  } else {
    byte[] mac = network.getHardwareAddress();
    if (null != mac) {
      id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
      id = id & 1023;
    }
  }
} catch (Exception e) {
  log.warn(" getWorkId: " + e.getMessage());
}

return id;

序列號(hào)

序列號(hào)可以直接從0開始自增。這里有兩個(gè)要注意的點(diǎn)：

1、當(dāng)序列號(hào)達(dá)到最大值時(shí)的問題

比如序列號(hào)占12bit位，最大值為4095，當(dāng)序列號(hào)在同一毫秒自增到4095時(shí)，再加1則會(huì)超出bit位，此時(shí)需要將序列號(hào)重置為0,但是重置為0就會(huì)出現(xiàn)同一毫秒有兩個(gè)序列號(hào)為0的id，所以重置為0的同時(shí)還需要等待至下一毫秒。

2、數(shù)據(jù)傾斜問題

如果序列號(hào)從0自增，那么對(duì)于大部分同一毫秒內(nèi)只會(huì)有一個(gè)請(qǐng)求的系統(tǒng)，生成的id號(hào)序列號(hào)大部分為0(偶數(shù))，此時(shí)如果以id進(jìn)行分表，就會(huì)造成數(shù)據(jù)的嚴(yán)重傾斜。該問題可以用過序列號(hào)從(0,1)隨機(jī)開始自增。

3、時(shí)間回?fù)軉栴}

時(shí)間回?fù)軙r(shí)可通過等待，或者使用過去時(shí)間生成id解決。

private long getSequence(){
  long timestamp = timeGen();
  // 閏秒
  if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
      try {
        // 休眠雙倍差值后重新獲取，再次校驗(yàn)
        wait(offset << 1);
        timestamp = timeGen();
        if (timestamp < lastTimestamp) {
          throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
        }
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    } else {
      throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
    }
  }

  if (lastTimestamp == timestamp) {
    // 相同毫秒內(nèi)，序列號(hào)自增
    sequence = (sequence + 1) & sequenceMask;
    if (sequence == 0) {
      // 同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
      timestamp = tilNextMillis(lastTimestamp);
    }
  } else {
    // 不同毫秒內(nèi)，序列號(hào)置為 0|1 隨機(jī)數(shù)
    sequence = ThreadLocalRandom.current().nextLong(0, 2);
  }
  return sequence;
}

protected long tilNextMillis(long lastTimestamp) {
  long timestamp = timeGen();
  while (timestamp <= lastTimestamp) {
    timestamp = timeGen();
  }

  return timestamp;
}

protected long timeGen() {
  return System.currentTimeMillis();
}

整體代碼

public class MySequence {

    private static final Logger log = LoggerFactory.getLogger(MySequence.class);

    /**
     * 時(shí)間起始標(biāo)記點(diǎn)，作為基準(zhǔn)，一般取系統(tǒng)的最近時(shí)間（一旦確定不能變動(dòng)）
     */
    private final long twepoch = 1666108800000L;

    /**
     * 10位的機(jī)器id
     */
    private final long workerIdBits = 10L;
    /**
     * 12位的序列號(hào) 每毫秒內(nèi)產(chǎn)生的id數(shù): 2的12次方個(gè)
     */
    private final long sequenceBits = 12L;
    /**
     * 1023
     */
    protected final long maxWorkerId = ~(-1L << workerIdBits);
    /**
     * 機(jī)器id左移動(dòng)位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 時(shí)間戳左移動(dòng)位
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits;
    /**
     * 4095
     */
    private final long sequenceMask = ~(-1L << sequenceBits);

    /**
     * 所屬機(jī)器id
     */
    private final long workerId;
    /**
     * 并發(fā)控制序列
     */
    private long sequence = 0L;

    /**
     * 上次生產(chǎn) ID 時(shí)間戳
     */
    private long lastTimestamp = -1L;

    public MySequence() {
        this.workerId = getWorkerId();
    }

    /**
     * 有參構(gòu)造器
     *
     * @param workerId     工作機(jī)器 ID
     */
    public MySequence(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("Worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }

    /**
     * 基于網(wǎng)卡MAC地址計(jì)算余數(shù)作為機(jī)器id
     */
    protected long getWorkerId() {
        long id = 0L;
        try {
            NetworkInterface network = NetworkInterface.getByInetAddress(InetAddress.getLocalHost());
            if (null == network) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                if (null != mac) {
                    id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
                    id = id % (maxWorkerId + 1);
                }
            }
        } catch (Exception e) {
            log.warn("getWorkerId: " + e.getMessage());
        }

        return id;
    }

    /**
     * 獲取下一個(gè) ID
     *
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        // 閏秒
        if (timestamp < lastTimestamp) {
            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try {
                    // 休眠雙倍差值后重新獲取，再次校驗(yàn)
                    wait(offset << 1);
                    timestamp = timeGen();
                    if (timestamp < lastTimestamp) {
                        throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
                    }
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            } else {
                throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
            }
        }

        if (lastTimestamp == timestamp) {
            // 相同毫秒內(nèi)，序列號(hào)自增
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                // 同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 不同毫秒內(nèi)，序列號(hào)置為 1 - 3 隨機(jī)數(shù)
            sequence = ThreadLocalRandom.current().nextLong(1, 3);
        }

        lastTimestamp = timestamp;

        // 時(shí)間戳部分 | 機(jī)器標(biāo)識(shí)部分 | 序列號(hào)部分
        return ((timestamp - twepoch) << timestampLeftShift)
                | (workerId << workerIdShift)
                | sequence;
    }

    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }

        return timestamp;
    }

    protected long timeGen() {
        return System.currentTimeMillis();
    }

}

改造

要解決JS精度丟失的問題，就要清楚原因是什么。

這是因?yàn)镴S的number類型最大精度為2^53，即9007199254740992

轉(zhuǎn)為二進(jìn)制：100000000000000000000000000000000000000000000000000000 (54位)

那么我們只要讓生成的id不超過9007199254740991即可

轉(zhuǎn)為二進(jìn)制：11111111111111111111111111111111111111111111111111111（53位）

可對(duì)此53位做以下分配

（1）時(shí)間戳(41位)-工作機(jī)器id(6位)-序列號(hào)(6位)：最大支持64個(gè)workerId, 每毫秒生成64個(gè)序列號(hào)

（2）時(shí)間戳(39位)-工作機(jī)器id(4位)-序列號(hào)(10位)：最大支持16個(gè)workerId, 每毫秒生成1024個(gè)序列號(hào)

此兩種情況分別為兩個(gè)極端，下面分別計(jì)算此兩種情況的使用時(shí)長(zhǎng)

第一種

41位時(shí)間戳的最大值為：2199023255551

取當(dāng)前時(shí)間戳：1666108800000

計(jì)算：1666108800000 + 2199023255551 = 3865132055551（2092-06-24 15:47:35）

系統(tǒng)運(yùn)行至2092年達(dá)到最大值

第二種

39位時(shí)間戳的最大值為：549755813887

取當(dāng)前時(shí)間戳：1666108800000

計(jì)算：1666108800000 + 549755813887 = 2215864613887（2040-03-20 21:56:53）

系統(tǒng)運(yùn)行至2040年達(dá)到最大值

使用

于是結(jié)合雪花算法原理，我對(duì)需要改造的項(xiàng)目從并發(fā)量(序列號(hào))和實(shí)例數(shù)(工作機(jī)器id)方面做了調(diào)研。

從調(diào)研結(jié)果進(jìn)行了bit位分配。

并且基于現(xiàn)有的id最大值，計(jì)算了基準(zhǔn)數(shù)，讓修改后的id生成策略必然大于以前的id。

最后該策略已上線運(yùn)行，達(dá)到了預(yù)期結(jié)果。

小結(jié)

雪花算法的特點(diǎn)：唯一性，高性能，有序性。

雪花算法的三個(gè)部分：時(shí)間戳、工作機(jī)器id、序列號(hào)。

JS最大精度為2^53, 生成的id不超過該數(shù)即可。

使用時(shí)可根據(jù)實(shí)際業(yè)務(wù)情況對(duì)三個(gè)部分的bit位進(jìn)行調(diào)整。

參考：

分布式高效ID生產(chǎn)黑科技: https://gitee.com/yu120/sequence

System.currentTimeMillis的性能真有如此不堪嗎？: https://juejin.cn/post/6887743425437925383