当前位置：首页 > article >正文

Snowflake算法js(实现)

article 2024/10/20 1:20:34

Snowflake算法是一种分布式环境下的唯一ID生成算法，最初由Twitter开发并在其内部使用。该算法旨在生成全局唯一、递增的64位整数ID，同时具备高性能的特点。以下是Snowflake算法的一些关键特点及其工作原理：

特点

全局唯一性：生成的ID在分布式环境中几乎可以保证全局唯一。
时间有序：生成的ID随着生成时间递增，方便排序。
无须依赖外部系统：不需要依赖数据库或其他中心化的服务来生成ID，降低了系统的耦合度。
高吞吐量：即使在高并发情况下也能保持高性能。

工作原理

Snowflake生成的ID是一个64位的整数，分为以下几个部分：

时间戳部分（41位）：表示生成ID的时间戳（毫秒级），占41位，最高位是符号位（始终为0，表示正数），剩余40位用来表示时间戳。
机器标识部分（10位）：标识生成ID的工作机器，可以区分不同的服务器。
序列号部分（12位）：表示同一毫秒内生成的不同ID，可以区分同一台机器在同一毫秒内生成的多个ID。

ID格式

一个典型的Snowflake ID结构如下所示：

0 - 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
------------------- --------------- --------------- ---------------
        sign bit          timestamp            workerId              sequence

实现步骤

初始化时间戳基准：选择一个固定的时间点作为基准时间，比如某个项目的启动时间。所有生成的ID的时间戳部分都是相对于这个基准时间的偏移量。
分配机器标识：每台服务器在启动时需要分配一个唯一的机器标识（workerId），通常可以通过配置文件或环境变量设置。
生成ID：当需要生成新的ID时，算法会根据当前的时间戳、机器标识和序列号来组合成一个64位的整数。

示例代码

以下是一个简单的JavaScript实现示例：

class Snowflake {
  constructor(workerId, epoch = 1514764800000 /* 2018-01-01 */) {
    this.workerId = workerId;
    this.epoch = epoch;
    this.sequence = 0;
    this.lastTimestamp = -1;
  }

  nextId() {
    const timestamp = Date.now();

    if (timestamp < this.lastTimestamp) {
      throw new Error(`Clock moved backwards. Refusing to generate id for ${this.lastTimestamp - timestamp} milliseconds`);
    }

    if (timestamp === this.lastTimestamp) {
      this.sequence = (this.sequence + 1) & 0xFFF; // 12 bits
      if (this.sequence === 0) {
        timestamp = this.waitNextMillis(this.lastTimestamp);
      }
    } else {
      this.sequence = 0;
    }

    this.lastTimestamp = timestamp;

    return ((timestamp - this.epoch) << 22) |
           (this.workerId << 12) |
           this.sequence;
  }

  waitNextMillis(lastTimestamp) {
    let timestamp = Date.now();
    while (timestamp <= lastTimestamp) {
      timestamp = Date.now();
    }
    return timestamp;
  }
}

// 使用示例
const snowflake = new Snowflake(1); // 假设这是机器标识
console.log(snowflake.nextId());