mmdjiji revised this gist . Go to revision
No changes
mmdjiji revised this gist . Go to revision
1 file changed, 160 insertions
Twitter_Snowflake.js(file created)
| @@ -0,0 +1,160 @@ | |||
| 1 | + | // import bigInt from 'big-integer'; | |
| 2 | + | // http://peterolson.github.io/BigInteger.js/ | |
| 3 | + | ||
| 4 | + | // https://blog.csdn.net/xiaopeng9275/article/details/72123709 | |
| 5 | + | // https://zhuanlan.zhihu.com/p/36330307 | |
| 6 | + | // https://segmentfault.com/a/1190000011282426 | |
| 7 | + | ||
| 8 | + | /** | |
| 9 | + | * Twitter_Snowflake | |
| 10 | + | * | |
| 11 | + | * SnowFlake的结构如下(共64bits，每部分用-分开): | |
| 12 | + | * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 | |
| 13 | + | * | ----------------------|---------------------- --|-- --|-- -----|------ | |
| 14 | + | * 1bit不用 41bit 时间戳 数据标识id 机器id 序列号id | |
| 15 | + | * | |
| 16 | + | * - 1位标识，二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0 | |
| 17 | + | * - 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69 | |
| 18 | + | * - 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId | |
| 19 | + | * - 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号 | |
| 20 | + | * - 加起来刚好64位，为一个Long型。 | |
| 21 | + | * SnowFlake的优点是 | |
| 22 | + | * - 整体上按照时间自增排序 | |
| 23 | + | * - 并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分) | |
| 24 | + | * - 并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。 | |
| 25 | + | */ | |
| 26 | + | class SnowFlake { | |
| 27 | + | /** | |
| 28 | + | * 构造函数 | |
| 29 | + | * 运行在内阁 | |
| 30 | + | * @param {bigint} workerId 工作ID (0~31) | |
| 31 | + | * @param {bigint} dataCenterId 数据中心ID (0~31) | |
| 32 | + | * @param {bigint} sequence 毫秒内序列 (0~4095) | |
| 33 | + | */ | |
| 34 | + | constructor(workerId, dataCenterId) { | |
| 35 | + | // 开始时间截 (2018-02-01)，这个可以设置开始使用该系统的时间，可往后使用69年 | |
| 36 | + | this.twepoch = 1548988646430n; | |
| 37 | + | ||
| 38 | + | // 位数划分 [数据标识id(5bit 31)、机器id(5bit 31)](合计共支持1024个节点)、序列id(12bit 4095) | |
| 39 | + | this.workerIdBits = 5n; | |
| 40 | + | this.dataCenterIdBits = 5n; | |
| 41 | + | this.sequenceBits = 12n; | |
| 42 | + | // this.timestampBits = 41n; | |
| 43 | + | ||
| 44 | + | // 支持的最大十进制id | |
| 45 | + | // 这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数 | |
| 46 | + | // -1 左移5位后与 -1 异或 | |
| 47 | + | this.maxWorkerId = -1n ^ (-1n << this.workerIdBits); | |
| 48 | + | this.maxDataCenterId = -1n ^ (-1n << this.dataCenterIdBits); | |
| 49 | + | // 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) | |
| 50 | + | this.sequenceMask = -1n ^ (-1n << this.sequenceBits); | |
| 51 | + | ||
| 52 | + | // 机器ID向左移12位 数据标识id向左移17位(12+5) 时间截向左移22位(5+5+12) | |
| 53 | + | this.workerIdShift = this.sequenceBits; | |
| 54 | + | this.dataCenterIdShift = this.sequenceBits + this.workerIdBits; | |
| 55 | + | this.timestampLeftShift = this.dataCenterIdShift + this.dataCenterIdBits; | |
| 56 | + | ||
| 57 | + | // 工作机器ID(0~31) 数据中心ID(0~31) 毫秒内序列(0~4095) | |
| 58 | + | // this.workerId; | |
| 59 | + | // this.dataCenterId; | |
| 60 | + | this.sequence = 0n; | |
| 61 | + | ||
| 62 | + | // 上次生成ID的时间截（这个是在内存中？系统时钟回退+重启后呢） | |
| 63 | + | this.lastTimestamp = -1n; | |
| 64 | + | ||
| 65 | + | const { maxWorkerId, maxDataCenterId } = this; | |
| 66 | + | if (workerId > maxWorkerId || workerId < 0n) { | |
| 67 | + | throw new Error( | |
| 68 | + | `workerId can't be greater than ${maxWorkerId} or less than 0` | |
| 69 | + | ); | |
| 70 | + | } | |
| 71 | + | if (dataCenterId > maxDataCenterId || dataCenterId < 0n) { | |
| 72 | + | throw new Error( | |
| 73 | + | `dataCenterId can't be greater than ${maxDataCenterId} or less than 0` | |
| 74 | + | ); | |
| 75 | + | } | |
| 76 | + | this.workerId = workerId; | |
| 77 | + | this.dataCenterId = dataCenterId; | |
| 78 | + | return this; | |
| 79 | + | } | |
| 80 | + | ||
| 81 | + | /** | |
| 82 | + | * 获得下一个ID (该方法是线程安全的) | |
| 83 | + | * | |
| 84 | + | * @returns {bigint} SnowflakeId 返回 id | |
| 85 | + | */ | |
| 86 | + | nextId() { | |
| 87 | + | let timestamp = this.timeGen(); | |
| 88 | + | // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常 | |
| 89 | + | const diff = timestamp - this.lastTimestamp; | |
| 90 | + | if (diff < 0n) { | |
| 91 | + | throw new Error( | |
| 92 | + | `Clock moved backwards. Refusing to generate id for ${-diff} milliseconds` | |
| 93 | + | ); | |
| 94 | + | } | |
| 95 | + | ||
| 96 | + | // 如果是同一时间生成的，则进行毫秒内序列 | |
| 97 | + | if (diff === 0n) { | |
| 98 | + | this.sequence = (this.sequence + 1n) & this.sequenceMask; | |
| 99 | + | // 毫秒内序列溢出 | |
| 100 | + | if (this.sequence === 0n) { | |
| 101 | + | // 阻塞到下一个毫秒，获得新的时间戳 | |
| 102 | + | timestamp = this.tilNextMillis(this.lastTimestamp); | |
| 103 | + | } | |
| 104 | + | } else { | |
| 105 | + | // 时间戳改变，毫秒内序列重置 | |
| 106 | + | this.sequence = 0n; | |
| 107 | + | } | |
| 108 | + | ||
| 109 | + | // 保存上次生成ID的时间截 | |
| 110 | + | this.lastTimestamp = timestamp; | |
| 111 | + | ||
| 112 | + | // 移位并通过或运算拼到一起组成64位的ID | |
| 113 | + | // 将各 bits 位数据移位后或运算合成一个大的64位二进制数据 | |
| 114 | + | return ( | |
| 115 | + | ((timestamp - this.twepoch) << this.timestampLeftShift) | // 时间数据左移22 | |
| 116 | + | (this.dataCenterId << this.dataCenterIdShift) | // 数据标识id左移 17 | |
| 117 | + | (this.workerId << this.workerIdShift) | // 机器id左移 12 | |
| 118 | + | this.sequence | |
| 119 | + | ); | |
| 120 | + | } | |
| 121 | + | /** | |
| 122 | + | * 阻塞到下一个毫秒，直到获得新的时间戳 | |
| 123 | + | * @param {bigint} lastTimestamp 上次生成ID的时间截 | |
| 124 | + | * @return {bigint} 当前时间戳 | |
| 125 | + | */ | |
| 126 | + | tilNextMillis(lastTimestamp) { | |
| 127 | + | let timestamp = this.timeGen(); | |
| 128 | + | while (timestamp <= lastTimestamp) { | |
| 129 | + | timestamp = this.timeGen(); | |
| 130 | + | } | |
| 131 | + | return timestamp; | |
| 132 | + | } | |
| 133 | + | ||
| 134 | + | /** | |
| 135 | + | * 返回以毫秒为单位的当前时间 | |
| 136 | + | * @return {bigint} 当前时间(毫秒) | |
| 137 | + | */ | |
| 138 | + | timeGen() { | |
| 139 | + | return BigInt(+new Date()); | |
| 140 | + | } | |
| 141 | + | } | |
| 142 | + | ||
| 143 | + | // ========== TEST ========== | |
| 144 | + | ||
| 145 | + | // 测试 | |
| 146 | + | function main() { | |
| 147 | + | console.time('id'); | |
| 148 | + | const idWorker = new SnowFlake(1n, 1n); | |
| 149 | + | ||
| 150 | + | const tempIds = []; | |
| 151 | + | for (let i = 0; i < 50000; i++) { | |
| 152 | + | const id = idWorker.nextId(); | |
| 153 | + | console.log(id); | |
| 154 | + | tempIds.push(id); | |
| 155 | + | } | |
| 156 | + | console.log(tempIds.length); | |
| 157 | + | // const end = +new Date(); | |
| 158 | + | console.timeEnd('id'); | |
| 159 | + | } | |
| 160 | + | main(); | |
Newer
Older