概述

雪花算法是Twitter使用并开源的分布式唯一ID生成算法,其核心思想是通过对一个64位数字(Long)进行分段划分,通过时间戳保证有序递增,在Node中,由于Node本身单进程特性,其计算过程肯定是线程安全的,但多进程条件下无法保证唯一性,因此,可以通过划分一段数据位用于进程编码,进程编码在进程启动时通过环境变量传入,来保证进程安全。

区段划分

各区段划分如下:

0  0000000000000000000000000000000000000000  000  00000  00  000000000000
_  ________________________________________  ___  _____  __  ____________
A                     B                       C     D     E       F
  • A,1位,最高位不用,因id需时钟为正数,因而始终为0
  • B,41位,为id生成时间与基准时间的毫秒数差值,某一基准时间下可保证(2 ** 41 - 1) / (1000 * 3600 ** 24 * 365) ≈ 67年不重复
  • C,3位,机器码标志,不同机器依次递增,最多可分布式部署(2 ** 3 - 1) = 7台机器
  • D,5位,进程标志,不同进程按启动次序依次递增,同一机器最多可启动(2 ** 5 - 1) = 31个进程,配合机器码标志位,可最多启动31 * 7 = 217个实例,绝大多场景下完全够用。
  • E,2位,时钟回拨标志。时钟回拨指程序运行期间服务器时钟由于人为或其它原因造成回退,因算法是根据与基准时间差保证递增的,因此若时钟发生回退,可能造成id重复,当本次id生成时的时钟小于上次id生成时的时钟时,说明时钟发生回退,这时将时钟回退标志加1,可防止id重复,但此方式也仅在程序运行期间有效,若时钟发生了回退但程序重启,则时钟回退标志归0,或时钟回退次数超过允许最大值,依然可能造成重复,这也是雪花算法的一个弊端。2位时钟回拨位数最多可容忍2 ** 2 - 1 = 3次时钟回拨。
  • F,12位,毫秒内序列号,时间戳是毫秒单位的,当多个id在同一毫秒内生成时,依次递增序列号,一毫秒内最多可生成2 ^ 12 - 1 = 4095id,当毫秒内生成id数量超过4095时,等待下一毫秒。

代码实现

代码实现如下:

// SnowFlake.js
const logger = console.log;
module.exports = class SnowFlake {

    // 开始基准时间戳 2020-01-01 00:00:00.000
    static initiallyTs = 1580486400000;

    // 机器标志位数
    static datacenterIdBits = 3;
    // 机器标志
    static datacenterId = parseInt(process.env.workerId, 10);;

    // 进程标识位数
    static workerIdBits = 5;
    // 进程标志
    static workerId = parseInt(process.env.workerId, 10);;

    // 时钟回退标识位数
    static tsBackBits = 2;
    // 时钟回退标志
    static tsBack = 0;

    // 序列号位数
    static sequenceBits = 12;
    // 序列号
    static sequence = 0;

    // 各标志左移位数
    static tsBackShitf = SnowFlake.sequenceBits  // 12
    static workIdShift = SnowFlake.tsBackShitf + SnowFlake.tsBackBits; // 14
    static datacenterIdShift = SnowFlake.workIdShift + SnowFlake.workerIdBits; // 18
    static tsShift = SnowFlake.datacenterIdShift + SnowFlake.datacenterIdBits; // 22

    
    // 最大允许时钟回退次数
    static maxTsBack = -1 ^ (-1 << SnowFlake.tsBackBits);
    // 毫秒最大允许序列号
    static maxSequence = -1 ^ (-1 << SnowFlake.sequenceBits)
    // 上次生成id的时间
    static lastGenTs = new Date().getTime();

    /**
     * node本身即为单线程,因而此处一定是线程安全的
     */
    static nextId() {
        let ts = SnowFlake.getTimestap();
        if (ts < SnowFlake.lastGenTs) {
            // 小于上次id生成时间,发生时钟回退
            SnowFlake.tsBack = (SnowFlake.tsBack + 1) & SnowFlake.maxTsBack;
            logger.warn(`clock is moving backwards, server time = ${ts}, last time = ${SnowFlake.lastGenTs}, tsBack = ${SnowFlake.tsBack}`);
            if (SnowFlake.tsBack === 0) {
                // 时钟回退发生超过了最大次数,抛出异常
                throw new ForbiddenException(`clock moves backwards too many times ....`);
            }
        }
        if (ts === SnowFlake.lastGenTs) {
            // 时间戳重复,即同一毫秒内生成,增加序列号
            SnowFlake.sequence = (SnowFlake.sequence + 1) & SnowFlake.maxSequence;
            if (SnowFlake.sequence === 0) {
                // 序列号达到上限,等待下一毫秒
                ts = SnowFlake.waitNextMillis(SnowFlake.lastGenTs);
            }
        } else {
            // 新一毫秒,序列号从0开始累计
            SnowFlake.sequence = 0;
        }
        SnowFlake.lastGenTs = ts; // 更新上次id生成时间
        // 各标志位进行位移,组成最终id
        const newId = (BigInt(ts - SnowFlake.initiallyTs) << BigInt(SnowFlake.tsShift)) | BigInt((SnowFlake.datacenterId << SnowFlake.datacenterIdShift)
                    | SnowFlake.workerId << SnowFlake.workIdShift | SnowFlake.tsBack << SnowFlake.tsBackShitf | SnowFlake.sequence);
        return newId;
    }

    static getTimestap() {
        return new Date().getTime();
    };

    static waitNextMillis(lastTs) {
        let tempTs = SnowFlake.getTimestap();
        while(tempTs <= lastTs) {
            tempTs = SnowFlake.getTimestap();
        }
        return tempTs;
    }
}

效率

生成一百万个id,如下:

const cluster = require('cluster');
const SnowFlake = require('./SnowFlake');

if (cluster.isMaster) {
    const datacenterId = 1; // 机器编码
    for (let i = 0; i < 3; i ++) {
        // 3个进程
        cluster.fork({
            datacenterId,
            workerId: i
        });
    }
} else {

    const max = 1000000;
    
    const startDate = new Date();
    for (let i  = 0; i < max; i ++) {
        const _ = SnowFlake.nextId();
    }
    const endDate = new Date();
    console.log(`process id = ${process.pid}, time = ${endDate.getTime() - startDate.getTime()}ms`);
}

在我的电脑上(i5-8250u@1.6GHz),输出如下:

snowflake_out2.png

一秒钟粗略计算可生成三百万id左右。用uuid v1做同样测试(uuid库),生成一百万id大约600ms左右,可见,比起uuid,此场景实现下雪花算法效率还是有优势的。但由于node中一些模块是将长整型作为字符串处理的(毕竟BigInt是从node10才开始支持的,node中无法自然的表示大数),如typeorm等,因此id可能需要通过字符串返回,如下:

return newId.toString();

以字符串形式返回,运行测试用例,单进程生成一百万id600ms左右,与uuid效率相当。toString()可占用约1/3的性能消耗。