概述

雪花算法是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 = 4095个id，当毫秒内生成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)，输出如下：

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

return newId.toString();

以字符串形式返回，运行测试用例，单进程生成一百万id约500ms左右，

与uuid效率相当。toString()可占用近1/3的性能消耗。