Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将 64-bit位分割成多个部分，每个部分代表不同的含义。
位运算异或( ^ ) ，左移( << ) ，与( & )，或( | )
ts
typescript
class SnowflakeIdGenerate {
private START_STMP = 0;
private SEQUENCE_BIT = 12;
private MACHINE_BIT = 5;
private DATACENTER_BIT = 5;
private MAX_DATACENTER_NUM = -1 ^ (-1 << this.DATACENTER_BIT);
private MAX_MACHINE_NUM = -1 ^ (-1 << this.MACHINE_BIT);
private MAX_SEQUENCE = -1 ^ (-1 << this.SEQUENCE_BIT);
private MACHINE_LEFT = this.SEQUENCE_BIT;
private DATACENTER_LEFT = this.SEQUENCE_BIT + this.MACHINE_BIT;
private TIMESTMP_LEFT = this.DATACENTER_LEFT + this.DATACENTER_BIT;
private datacenterId; //数据中心
private machineId; //机器标识
private sequence = 0; //序列号
private lastStmp = -1; //上一次时间戳
constructor(machineId = 1, datacenterId = 1) {
if (this.machineId > this.MAX_MACHINE_NUM || this.machineId < 0) {
throw new Error(
'config.worker_id must max than 0 and small than maxWrokerId-[' +
this.MAX_MACHINE_NUM +
']'
);
}
if (this.datacenterId > this.MAX_DATACENTER_NUM || this.datacenterId < 0) {
throw new Error(
'config.data_center_id must max than 0 and small than maxDataCenterId-[' +
this.MAX_DATACENTER_NUM +
']'
);
}
this.machineId = machineId;
this.datacenterId = datacenterId;
}
private getNewstmp = (): number => {
return Date.now();
};
private getNextMill = (): number => {
let timestamp = this.getNewstmp();
while (timestamp <= this.lastStmp) {
timestamp = this.getNewstmp();
}
return timestamp;
};
nextId = (): string => {
let timestamp: number = this.getNewstmp();
if (timestamp < this.lastStmp) {
throw new Error(
'Clock moved backwards. Refusing to generate id for ' +
(this.lastStmp - timestamp)
);
}
if (this.lastStmp === timestamp) {
this.sequence = (this.sequence + 1) & this.MAX_SEQUENCE;
if (this.sequence === 0) {
timestamp = this.getNextMill();
}
} else {
this.sequence = 0;
}
this.lastStmp = timestamp;
const timestampPos =
BigInt(timestamp - this.START_STMP) *
BigInt(2) ** BigInt(this.TIMESTMP_LEFT);
const dataCenterPos = BigInt(this.datacenterId << this.DATACENTER_LEFT);
const workerPos = BigInt(this.machineId << this.MACHINE_LEFT);
return (
timestampPos |
dataCenterPos |
workerPos |
BigInt(this.sequence)
).toString();
};
}
class Snowflake {
private readonly epoch: number = 1620950400000; // 开始时间戳，2021-05-14 00:00:00 UTC+8
private readonly workerIdBits: number = 5; // 机器 ID 所占的位数
private readonly datacenterIdBits: number = 5; // 数据中心 ID 所占的位数
private readonly maxWorkerId: number = ~(-1 << this.workerIdBits); // 最大机器 ID，2^5-1
private readonly maxDatacenterId: number = ~(-1 << this.datacenterIdBits); // 最大数据中心 ID，2^5-1
private readonly sequenceBits: number = 12; // 序列号所占的位数
private readonly workerIdShift: number = this.sequenceBits; // 机器 ID 左移位数，即序列号占用的位数
private readonly datacenterIdShift: number = this.sequenceBits + this.workerIdBits; // 数据中心 ID 左移位数
private readonly timestampLeftShift: number =
this.sequenceBits + this.workerIdBits + this.datacenterIdBits; // 时间戳左移位数
private sequenceMask: number = ~(-1 << this.sequenceBits); // 序列号的掩码，2^12-1
private sequence: number = 0; // 当前序列号
private lastTimestamp: number = -1; // 上次生成雪花 ID 的时间戳
private readonly workerId: number; // 当前机器 ID private readonly datacenterId: number; // 当前数据中心 ID
/** * 构造函数
* @param workerId 机器 ID
* @param datacenterId 数据中心 ID
*/ constructor(workerId: number, datacenterId: number) {
if (workerId > this.maxWorkerId || workerId < 0) {
throw new Error(`workerId must be between 0 and ${this.maxWorkerId}`);
}
if (datacenterId > this.maxDatacenterId || datacenterId < 0) {
throw new Error(`datacenterId must be between 0 and ${this.maxDatacenterId}`);
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
/**
* 生成下一个雪花 ID
* @returns 64 位的雪花 ID
*/ nextId(): string {
let timestamp = this.timeGen();
if (timestamp < this.lastTimestamp) {
throw new Error(
`Clock moved backwards. Refusing to generate id for ${
this.lastTimestamp - timestamp
} milliseconds`,
);
}
if (this.lastTimestamp === timestamp) {
this.sequence = (this.sequence + 1) & this.sequenceMask;
if (this.sequence === 0) {
timestamp = this.tilNextMillis(this.lastTimestamp);
}
} else {
this.sequence = 0;
}
this.lastTimestamp = timestamp;
const id =
((timestamp - this.epoch) << this.timestampLeftShift) |
(this.datacenterId << this.datacenterIdShift) |
(this.workerId << this.workerIdShift) |
this.sequence;
return id.toString();
}
/**
* 获取当前时间
*
*/
private timeGen(): number {
return Date.now();
}
/**
等待下一毫秒，直到返回新的时间戳
@param lastTimestamp 上次生成雪花 ID 的时间戳
@returns 新的时间戳
*/
private tilNextMillis(lastTimestamp: number): number {
let timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}
}