🏠
📚
June 14, 2024

Generating unique ids using Twitter's Snowflake

Snowflake is an algorithm for generating unique ids in a distributed system. Its basically a 64-bit integer id.

Structure of a Snowflake ID

+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp |  10 Bit Node ID  |   12 Bit Sequence ID |
+--------------------------------------------------------------------------+
+--------------------------------------------------------------------------+
| 1 Bit Unused | 41 Bit Timestamp |  10 Bit Node ID  |   12 Bit Sequence ID |
+--------------------------------------------------------------------------+
  • Sign bit(1 bit) - always 0
  • Timestamp (41 bits) - milliseconds since a custom epoch. This epoch can be any time in past.
  • Worker ID (10 bits) - identifies the server/process generating the ID. Upto 1024 nodes/servers are supported.
  • Sequence Number (12 bits) - counter that resets every millisecond. This allows upto 4096 ids per node per millisecond

How snowflake works ?

Snowflake plays with 3 variables - timestamp, workerId and sequenceNumber

  1. Get the current timestamp in millisecons
  2. If the timestamp is same as previous timestamp, increment the sequenceNumber
  3. If the timestamp is different, reset the sequenceNumber to 0
  4. Combine all three variables to get the final id - (1) Shift timestamp left by (10+12) bits and (2) Shift node ID left by 12 bits or all components together

Why is Snowflake useful ?

  • There is no coordination required between the server nodes.
  • All ids are time sortable.
  • The ids are globally unique.
  • The ids are compact and smaller in size compared to UUIDs.
  • Supports high throughput. One server can generate upto 4096 ids per millisecond.

Mitigating clock synchronization issues in snowflake

  • Use redudant NTP servers to synchronize the clock
  • Monitor clock drifts
  • Disable ID generation for servers who clock moved back significantly

Implementation

Here's a quick javascript implementation of snowflake algorithm.

/**
 * JavaScript Implementation of Twitter's Snowflake ID Generator Algorithm
 * 
 * Structure of a Snowflake ID (64 bits total):
 * - Sign bit: 1 bit (always 0, reserved for future use)
 * - Timestamp: 41 bits (milliseconds since custom epoch)
 * - Worker ID: 10 bits (identifies the server/process)
 * - Sequence: 12 bits (counter that resets every millisecond)
 */
class Snowflake {
  constructor(options = {}) {
    // Custom epoch (January 1, 2020)
    this.epoch = options.epoch || 1577836800000;
    
    // Worker ID (0-1023)
    this.workerId = options.workerId || 1;
    if (this.workerId < 0 || this.workerId > 1023) {
      throw new Error('Worker ID must be between 0 and 1023');
    }
    
    // Sequence starts at 0
    this.sequence = 0;
    
    // Last timestamp we generated an ID for
    this.lastTimestamp = -1;
  }

  // Generate a unique Snowflake ID
  nextId() {
    let timestamp = this._currentTimestamp();
    
    // Clock moved backwards - handle error case
    if (timestamp < this.lastTimestamp) {
      throw new Error(`Clock moved backwards. Refusing to generate ID for ${this.lastTimestamp - timestamp} milliseconds`);
    }
    
    // Same millisecond as last time
    if (timestamp === this.lastTimestamp) {
      // Increment sequence
      this.sequence = (this.sequence + 1) & 4095; // 2^12 - 1 = 4095
      
      // Sequence overflow in the same millisecond
      if (this.sequence === 0) {
        // Wait for next millisecond
        timestamp = this._waitNextMillis(this.lastTimestamp);
      }
    } else {
      // Different millisecond, reset sequence
      this.sequence = 0;
    }
    
    this.lastTimestamp = timestamp;
    
    // Build ID using bitwise operations
    // Note: JavaScript bitwise operations work on 32 bits, so we need to use BigInt
    const id = BigInt(timestamp - this.epoch) << 22n |
               BigInt(this.workerId) << 12n |
               BigInt(this.sequence);
    
    return id.toString();
  }
  
  // Get current timestamp in milliseconds
  _currentTimestamp() {
    return Date.now();
  }
  
  // Wait until next millisecond
  _waitNextMillis(lastTimestamp) {
    let timestamp = this._currentTimestamp();
    while (timestamp <= lastTimestamp) {
      timestamp = this._currentTimestamp();
    }
    return timestamp;
  }
}

// Example usage
const snowflake = new Snowflake({
  epoch: 1577836800000, // Custom epoch (Jan 1, 2020)
  workerId: 1           // Worker ID
});

// Generate IDs
console.log("Generated Snowflake ID:", snowflake.nextId());
console.log("Generated Snowflake ID:", snowflake.nextId());
console.log("Generated Snowflake ID:", snowflake.nextId());

// Generate multiple IDs to demonstrate sequence numbers
const generateBatch = () => {
  console.log("\nGenerating batch of IDs in the same millisecond:");
  const ids = [];
  for (let i = 0; i < 5; i++) {
    ids.push(snowflake.nextId());
  }
  console.log(ids);
};

generateBatch();
/**
 * JavaScript Implementation of Twitter's Snowflake ID Generator Algorithm
 * 
 * Structure of a Snowflake ID (64 bits total):
 * - Sign bit: 1 bit (always 0, reserved for future use)
 * - Timestamp: 41 bits (milliseconds since custom epoch)
 * - Worker ID: 10 bits (identifies the server/process)
 * - Sequence: 12 bits (counter that resets every millisecond)
 */
class Snowflake {
  constructor(options = {}) {
    // Custom epoch (January 1, 2020)
    this.epoch = options.epoch || 1577836800000;
    
    // Worker ID (0-1023)
    this.workerId = options.workerId || 1;
    if (this.workerId < 0 || this.workerId > 1023) {
      throw new Error('Worker ID must be between 0 and 1023');
    }
    
    // Sequence starts at 0
    this.sequence = 0;
    
    // Last timestamp we generated an ID for
    this.lastTimestamp = -1;
  }

  // Generate a unique Snowflake ID
  nextId() {
    let timestamp = this._currentTimestamp();
    
    // Clock moved backwards - handle error case
    if (timestamp < this.lastTimestamp) {
      throw new Error(`Clock moved backwards. Refusing to generate ID for ${this.lastTimestamp - timestamp} milliseconds`);
    }
    
    // Same millisecond as last time
    if (timestamp === this.lastTimestamp) {
      // Increment sequence
      this.sequence = (this.sequence + 1) & 4095; // 2^12 - 1 = 4095
      
      // Sequence overflow in the same millisecond
      if (this.sequence === 0) {
        // Wait for next millisecond
        timestamp = this._waitNextMillis(this.lastTimestamp);
      }
    } else {
      // Different millisecond, reset sequence
      this.sequence = 0;
    }
    
    this.lastTimestamp = timestamp;
    
    // Build ID using bitwise operations
    // Note: JavaScript bitwise operations work on 32 bits, so we need to use BigInt
    const id = BigInt(timestamp - this.epoch) << 22n |
               BigInt(this.workerId) << 12n |
               BigInt(this.sequence);
    
    return id.toString();
  }
  
  // Get current timestamp in milliseconds
  _currentTimestamp() {
    return Date.now();
  }
  
  // Wait until next millisecond
  _waitNextMillis(lastTimestamp) {
    let timestamp = this._currentTimestamp();
    while (timestamp <= lastTimestamp) {
      timestamp = this._currentTimestamp();
    }
    return timestamp;
  }
}

// Example usage
const snowflake = new Snowflake({
  epoch: 1577836800000, // Custom epoch (Jan 1, 2020)
  workerId: 1           // Worker ID
});

// Generate IDs
console.log("Generated Snowflake ID:", snowflake.nextId());
console.log("Generated Snowflake ID:", snowflake.nextId());
console.log("Generated Snowflake ID:", snowflake.nextId());

// Generate multiple IDs to demonstrate sequence numbers
const generateBatch = () => {
  console.log("\nGenerating batch of IDs in the same millisecond:");
  const ids = [];
  for (let i = 0; i < 5; i++) {
    ids.push(snowflake.nextId());
  }
  console.log(ids);
};

generateBatch();