Nodejs 实现雪花飘移算法

很久之前就了解过雪花算法，一直没在意。最近看到一个比较有趣的类雪花算法————雪花飘移算法，号称比传统的雪花算法还要好。

雪花算法

雪花算法是由 twitter 创建，传统的雪花算法里，第一段是 41bit 的时间戳，第二段是 10bit 的服务 id+机器 id，剩下 12bit 用来放计算机生成的序列号。这导致雪花算法得到的 id 数字长达 64 位之多。

这在 nodejs 的项目中是很痛苦的，因为 js 的 Number 最大值就只有9007199254740992，根本容不下这么长的数字 id，只能把 id 转为字符串。目前也有开源的模块支持生成雪花算法的 id，如 https://github.com/Welogix-Tech/node-snowflake。

还有没有更好的方法？

雪花飘移算法

这个算法和雪花算法的区别是，通过减少 Seq 位数来压缩长度，在缩减长度的同时，能保证生成速度不变。

下面的算法是从 go 版本 直接转义过来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

class Genid {
    /**
     *Creates an instance of Genid.
     * @author bubao
     * @date 2021-04-27
     * @param {{
     *     Method: 1, // 雪花计算方法，（1-漂移算法|2-传统算法），默认 1
     *     BaseTime: 1577836800000,  // 基础时间（ms 单位），不能超过当前系统时间
     *     WorkerId: Number, // 机器码，必须由外部设定，最大值 2^WorkerIdBitLength-1
     *     WorkerIdBitLength: 6,   // 机器码位长，默认值 6，取值范围 [1, 15](要求：序列数位长+机器码位长不超过 22)
     *     SeqBitLength: 6,   // 序列数位长，默认值 6，取值范围 [3, 21](要求：序列数位长+机器码位长不超过 22)
     *     MaxSeqNumber: 5, // 最大序列数（含），设置范围 [MinSeqNumber, 2^SeqBitLength-1]，默认值 0，表示最大序列数取最大值（2^SeqBitLength-1]）
     *     MinSeqNumber: 5, // 最小序列数（含），默认值 5，取值范围 [5, MaxSeqNumber]，每毫秒的前 5 个序列数对应编号 0-4 是保留位，其中 1-4 是时间回拨相应预留位，0 是手工新值预留位
     *     TopOverCostCount: 2000// 最大漂移次数（含），默认 2000，推荐范围 500-10000（与计算能力有关）
     * }} options
     * @memberof Genid
     */
    constructor(options) {
        if (options.WorkerId === undefined) {
            throw new Error("lost WorkerId");
        }
        // 1.BaseTime
        const BaseTime = 1577836800000;
        if (!options.BaseTime || options.BaseTime < 0) {
            options.BaseTime = BaseTime;
        }
        // 2.WorkerIdBitLength
        const WorkerIdBitLength = 6;
        if (!options.WorkerIdBitLength || options.WorkerIdBitLength < 0) {
            options.WorkerIdBitLength = WorkerIdBitLength;
        }

        // 4.SeqBitLength
        const SeqBitLength = 6;
        if (!options.SeqBitLength || options.SeqBitLength < 0) {
            options.SeqBitLength = SeqBitLength;
        }
        // 5.MaxSeqNumber
        const MaxSeqNumber = (1 << SeqBitLength) - 1;
        if (options.MaxSeqNumber <= 0 || options.MaxSeqNumber === undefined) {
            options.MaxSeqNumber = MaxSeqNumber;
        }
        // 6.MinSeqNumber
        const MinSeqNumber = 5;
        if (!options.MinSeqNumber || options.MinSeqNumber < 0) {
            options.MinSeqNumber = MinSeqNumber;
        }
        // 7.Others
        const topOverCostCount = 2000;
        if (!options.TopOverCostCount || options.TopOverCostCount < 0) {
            options.TopOverCostCount = topOverCostCount;
        }

        if (options.Method !== 2) {
            options.Method = 1;
        } else {
            options.Method = 2;
        }

        this.Method = BigInt(options.Method);
        this.BaseTime = BigInt(options.BaseTime);
        this.WorkerId = BigInt(options.WorkerId);
        this.WorkerIdBitLength = BigInt(options.WorkerIdBitLength);
        this.SeqBitLength = BigInt(options.SeqBitLength);
        this.MaxSeqNumber = BigInt(options.MaxSeqNumber);
        this.MinSeqNumber = BigInt(options.MinSeqNumber);
        this.TopOverCostCount = BigInt(options.TopOverCostCount);

        const timestampShift = this.WorkerIdBitLength + this.SeqBitLength;
        const currentSeqNumber = this.MinSeqNumber;

        this._TimestampShift = timestampShift;
        this._CurrentSeqNumber = currentSeqNumber;

        this._LastTimeTick = 0;
        this._TurnBackTimeTick = 0;
        this._TurnBackIndex = 0;
        this._IsOverCost = false;
        this._OverCostCountInOneTerm = 0;
    }

    // DoGenIDAction .
    DoGenIdAction(OverCostActionArg) { }

    BeginOverCostAction(useTimeTick) { }

    EndOverCostAction(useTimeTick) {
        // if m1._TermIndex > 10000 {
        //     m1._TermIndex = 0
        // }
    }

    BeginTurnBackAction(useTimeTick) { }

    EndTurnBackAction(useTimeTick) { }

    NextOverCostId() {
        const currentTimeTick = this.GetCurrentTimeTick();
        if (currentTimeTick > this._LastTimeTick) {
            // this.EndOverCostAction(currentTimeTick)
            this._LastTimeTick = currentTimeTick;
            this._CurrentSeqNumber = this.MinSeqNumber;
            this._IsOverCost = false;
            this._OverCostCountInOneTerm = 0;
            // this._GenCountInOneTerm = 0
            return this.CalcId(this._LastTimeTick);
        }
        if (this._OverCostCountInOneTerm >= this.TopOverCostCount) {
            // this.EndOverCostAction(currentTimeTick)
            this._LastTimeTick = this.GetNextTimeTick();
            this._CurrentSeqNumber = this.MinSeqNumber;
            this._IsOverCost = false;
            this._OverCostCountInOneTerm = 0;
            // this._GenCountInOneTerm = 0
            return this.CalcId(this._LastTimeTick);
        }
        if (this._CurrentSeqNumber > this.MaxSeqNumber) {
            this._LastTimeTick++;
            this._CurrentSeqNumber = this.MinSeqNumber;
            this._IsOverCost = true;
            this._OverCostCountInOneTerm++;
            // this._GenCountInOneTerm++

            return this.CalcId(this._LastTimeTick);
        }

        // this._GenCountInOneTerm++
        return this.CalcId(this._LastTimeTick);
    }

    NextNormalId() {
        const currentTimeTick = this.GetCurrentTimeTick();
        if (currentTimeTick < this._LastTimeTick) {
            if (this._TurnBackTimeTick < 1) {
                this._TurnBackTimeTick = this._LastTimeTick - 1;
                this._TurnBackIndex++;
                // 每毫秒序列数的前 5 位是预留位，0 用于手工新值，1-4 是时间回拨次序
                // 支持 4 次回拨次序（避免回拨重叠导致 ID 重复），可无限次回拨（次序循环使用）。
                if (this._TurnBackIndex > 4) {
                    this._TurnBackIndex = 1;
                }
                this.BeginTurnBackAction(this._TurnBackTimeTick);
            }
            return this.CalcTurnBackId(this._TurnBackTimeTick);
        }
        // 时间追平时，_TurnBackTimeTick 清零
        if (this._TurnBackTimeTick > 0) {
            this.EndTurnBackAction(this._TurnBackTimeTick);
            this._TurnBackTimeTick = 0;
        }

        if (currentTimeTick > this._LastTimeTick) {
            this._LastTimeTick = currentTimeTick;
            this._CurrentSeqNumber = this.MinSeqNumber;
            return this.CalcId(this._LastTimeTick);
        }

        if (this._CurrentSeqNumber > this.MaxSeqNumber) {
            this.BeginOverCostAction(currentTimeTick);
            // this._TermIndex++
            this._LastTimeTick++;
            this._CurrentSeqNumber = this.MinSeqNumber;
            this._IsOverCost = true;
            this._OverCostCountInOneTerm = 1;
            // this._GenCountInOneTerm = 1

            return this.CalcId(this._LastTimeTick);
        }

        return this.CalcId(this._LastTimeTick);
    }

    CalcId(useTimeTick) {
        const result = BigInt(useTimeTick << this._TimestampShift) + BigInt(this.WorkerId << this.SeqBitLength) + BigInt(this._CurrentSeqNumber);
        this._CurrentSeqNumber++;
        return result;
    }

    CalcTurnBackId(useTimeTick) {
        const result = BigInt(useTimeTick << this._TimestampShift) + BigInt(this.WorkerId << this.SeqBitLength) + BigInt(this._TurnBackIndex);
        this._TurnBackTimeTick--;
        return result;
    }

    GetCurrentTimeTick() {
        const millis = BigInt((new Date()).valueOf());
        return millis - this.BaseTime;
    }

    GetNextTimeTick() {
        let tempTimeTicker = this.GetCurrentTimeTick();
        console.log(tempTimeTicker);
        while (tempTimeTicker <= this._LastTimeTick) {
            tempTimeTicker = this.GetCurrentTimeTick();
        }
        return tempTimeTicker;
    }

    NextId() {
        if (this._IsOverCost) {
            return parseInt(this.NextOverCostId());
        } else {
            return parseInt(this.NextNormalId());
        }
    }
}

module.exports = Genid;

另外，也有人写过类似的算法，CSDN 博主「狼丶宇先生」的 nodejs 雪花算法生成 long 型主键 ID 默认 16 位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
/**
 * 雪花 ID 生成器
 * Date: 2020 年 9 月 25 日 14:20:21
 * Version: 1.0.0
 * A function for converting hex <-> dec w/o loss of precision.
 * By Dan Vanderkam http://www.danvk.org/hex2dec.html
 * @description js Number 最大长度不超过 17 位，否则会出现精度丢失的问题
 */
class SnowflakeID {
    constructor(options) {
        options = options || {};
        this.seq = 0;
        //机器 id 或任何随机数。如果您是在分布式系统中生成 id，强烈建议您提供一个适合不同机器的 mid。
        this.mid = (options.mid || 1) % 1023;
        //这是一个时间偏移量，它将从当前时间中减去以获得 id 的前 42 位。这将有助于生成更小的 id。
        this.offset = options.offset || (new Date().getFullYear() - 1970) * 31536000 * 1000;
        this.lastTime = 0;
    }

    generate() {
        const time = Date.now();
        const bTime = (time - this.offset).toString(2);
        // get the sequence number
        if (this.lastTime == time) {
            this.seq++;
            if (this.seq > 4095) {
                this.seq = 0;
                // make system wait till time is been shifted by one millisecond
                while (Date.now() <= time) {}
            }
        } else {
            this.seq = 0;
        }

        this.lastTime = time;

        let bSeq = this.seq.toString(2);
        let bMid = this.mid.toString(2);

        // create sequence binary bit
        while (bSeq.length < 12) bSeq = '0' + bSeq;

        while (bMid.length < 10) bMid = '0' + bMid;

        const bid = bTime + bMid + bSeq;
        let id = '';
        for (let i = bid.length; i > 0; i -= 4) {
            id = parseInt(bid.substring(i - 4, i), 2).toString(16) + id;
        }
        return this.hexToDec(id);
    }

    add(x, y, base) {
        let z = [];
        let n = Math.max(x.length, y.length);
        let carry = 0;
        let i = 0;
        while (i < n || carry) {
            let xi = i < x.length ? x[i] : 0;
            let yi = i < y.length ? y[i] : 0;
            let zi = carry + xi + yi;
            z.push(zi % base);
            carry = Math.floor(zi / base);
            i++;
        }
        return z;
    }

    /**
     * 乘以数字
     * @param {*} num
     * @param {*} x
     * @param {*} base
     */
    multiplyByNumber(num, x, base) {
        if (num < 0) return null;
        if (num == 0) return [];

        let result = [];
        let power = x;
        while (true) {
            if (num & 1) {
                result = this.add(result, power, base);
            }
            num = num >> 1;
            if (num === 0) break;
            power = this.add(power, power, base);
        }

        return result;
    }

    /**
     * 解析为数组
     * @param {*} str
     * @param {*} base
     */
    parseToDigitsArray(str, base) {
        let digits = str.split('');
        let ary = [];
        for (let i = digits.length - 1; i >= 0; i--) {
            let n = parseInt(digits[i], base);
            if (isNaN(n)) return null;
            ary.push(n);
        }
        return ary;
    }

    /**
     * 转换
     * @param {*} str
     * @param {*} fromBase
     * @param {*} toBase
     */
    convertBase(str, fromBase, toBase, legnth) {
        let digits = this.parseToDigitsArray(str, fromBase);
        if (digits === null) return null;
        let outArray = [];
        let power = [1];
        for (let i = 0; i < digits.length; i++) {
            // inletiant: at this point, fromBase^i = power
            if (digits[i]) {
                outArray = this.add(
                    outArray,
                    this.multiplyByNumber(digits[i], power, toBase),
                    toBase
                );
            }
            power = this.multiplyByNumber(fromBase, power, toBase);
        }
        let out = '';
        //设置了这里-3 会返回 16 位的字符，如果是设置为 outArray.length - 1 会返回 18 位的字符
        for (let i = outArray.length - 3; i >= 0; i--) {
            out += outArray[i].toString(toBase);
        }
        return out;
    }

    /**
     * 16 进制=> 10 进制
     * @param {*} hexStr
     */
    hexToDec(hexStr) {
        if (hexStr.substring(0, 2) === '0x') hexStr = hexStr.substring(2);
        hexStr = hexStr.toLowerCase();
        return this.convertBase(hexStr, 16, 10);
    }
}

//下面是测试代码部分，不需要的可以直接移除
const snid = new SnowflakeID({
    mid: +new Date()
});
let id = snid.generate();
console.log(id, id.length);
let arr = [];
for (let index = 0; index < 10000; index++) {
    id = snid.generate();
    console.log(id);
    arr.push(snid.generate(), +new Date());
}
//测试是否会有重复的 id, 目前的测试情况来看，不会有重复的
// console.log(arr, arr.length, Array.from(new Set(arr)).length);
module.exports = SnowflakeID;
// ————————————————
// 版权声明：本文为 CSDN 博主「狼丶宇先生」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
// 原文链接：https://blog.csdn.net/qq_33270001/article/details/108800547

类雪花算法的优缺点

雪花算法的出现，其实是为了解决数据库的主键使用非自增 id 的情况下，使用类似 guid 或者 uuid，在数据量大的情况下查询慢的情况。而雪花算法是工具时间戳生成的，序列号有一定的递增顺序，可用来排序。

但是依然还是存在一些缺点，根据时间戳生成的 id，有个致命的缺点就是时间回拨。一旦发生时间回拨，就会产生重复的 id，而雪花飘移算法通过配置参数在一定程度上可解决时间回拨的问题。

科普 > 系统设计
#mysql #node.js #算法 #go
Nodejs 实现雪花飘移算法
https://bubao.github.io/posts/50e649ca.html
作者
一念
发布于
2021年4月27日
许可协议