Whiz Tools

Generator ID-a pahuljice

Generator ID-a pahuljice

Optional: Unix timestamp in milliseconds (defaults to current time)

Generator ID-a Snježne pahulje

Uvod

ID snježne pahulje je jedinstveni identifikator korišten u distribuiranim sustavima, prvotno razvijen od strane Twittera. Ovaj alat omogućuje generiranje i analizu ID-a snježne pahulje, koji su 64-bitni cjelobrojni identifikatori sastavljeni od vremenskog oznake, ID-a stroja i broja sekvence.

Kako ID-ovi snježne pahulje rade

ID-ovi snježne pahulje su 64-bitni cjelobrojni identifikatori strukturirani na sljedeći način:

  • 41 bit: Vremenska oznaka (milisekunde od prilagođene epohe)
  • 10 bitova: ID stroja (5 bitova za ID podatkovnog centra, 5 bitova za ID radnika)
  • 12 bitova: Broj sekvence

Ova struktura omogućuje generiranje otprilike 4,096 jedinstvenih ID-a po milisekundi po stroju.

Korištenje generatora ID-a snježne pahulje

  1. (Opcionalno) Postavite prilagođenu epohu (zadano je Twitterova epoha: 2010-11-04T01:42:54.657Z)
  2. Unesite ID stroja (0-31) i ID podatkovnog centra (0-31)
  3. Kliknite "Generiraj" za stvaranje novog ID-a snježne pahulje
  4. Generirani ID i njegovi sastavni dijelovi bit će prikazani

Za analizu postojećeg ID-a snježne pahulje, unesite ga u polje "Analiziraj ID" i kliknite "Analiziraj".

Formula

ID snježne pahulje se konstruira pomoću bitovnih operacija:

ID = (vremenska oznaka << 22) | (ID_podatkovnog_centra << 17) | (ID_radnika << 12) | sekvenca

Gdje:

  • vremenska oznaka je broj milisekundi od epohe
  • ID_podatkovnog_centra je 5-bitni cijeli broj (0-31)
  • ID_radnika je 5-bitni cijeli broj (0-31)
  • sekvenca je 12-bitni cijeli broj (0-4095)

Izračun

Generator ID-a snježne pahulje provodi sljedeće korake:

  1. Dobijte trenutnu vremensku oznaku u milisekundama
  2. Osigurajte da je vremenska oznaka veća od posljednje korištene vremenske oznake (radi jedinstvenosti)
  3. Ako je vremenska oznaka ista kao posljednja, povećajte broj sekvence
  4. Ako broj sekvence pređe granicu (dođe do 4096), pričekajte sljedeću milisekundu
  5. Kombinirajte komponente pomoću bitovnih operacija kako biste stvorili konačni ID

Upotrebe

ID-ovi snježne pahulje su posebno korisni u:

  1. Distribuiranim sustavima: Generiranje jedinstvenih ID-a na više strojeva bez koordinacije
  2. Velikim podacima: Kreiranje sortabilnih ID-a za velike skupove podataka
  3. Mikrouslugama: Osiguranje jedinstvenih identifikatora među različitim uslugama
  4. Podatkovnom dijeljenju: Korištenje vremenske oznake ili ID-a stroja za učinkovito dijeljenje

Alternativa

Iako su ID-ovi snježne pahulje moćni, drugi sustavi generiranja ID-a uključuju:

  1. UUID (Univerzalni jedinstveni identifikator): Koristan kada je potrebna distribuirana generacija bez sortabilnosti
  2. Auto-incrementing ID-evi u bazi podataka: Jednostavni, ali ograničeni na jedinstvene instance baze podataka
  3. ULID (Univerzalni jedinstveni leksikografski sortirani identifikator): Sličan snježnoj pahulji, ali s drugačijom strukturom

Rubne situacije i ograničenja

  1. Sinkronizacija sata: ID-ovi snježne pahulje oslanjaju se na sustavno vrijeme. Ako se sat pomakne unatrag zbog NTP prilagodbi ili promjena ljetnog vremena, može doći do problema s generacijom ID-a.

  2. Problem godine 2038: 41-bitna vremenska oznaka će preplaviti 2079. (pretpostavljajući Twitterovu epohu). Sustavi koji koriste ID-ove snježne pahulje trebali bi planirati za ovu eventualnost.

  3. Sudari ID-a stroja: U velikim distribuiranim sustavima, osiguranje jedinstvenih ID-a stroja može biti izazovno i može zahtijevati dodatnu koordinaciju.

  4. Prelijevanje sekvence: U izuzetno visokim scenarijima, moguće je iscrpiti 4096 sekvenci po milisekundi, što može uzrokovati kašnjenja.

  5. Ne-monotonija između strojeva: Iako su ID-ovi monotonno rastući na jednom stroju, možda neće biti strogo monotonni među više strojeva.

Povijest

ID-ovi snježne pahulje uvedeni su od strane Twittera 2010. godine kako bi se zadovoljila potreba za distribuiranim, vremenski sortabilnim jedinstvenim identifikatorima. Od tada su ih usvojile i prilagodile mnoge druge tvrtke i projekti.

Primjeri

Evo implementacija generatora ID-a snježne pahulje u raznim jezicima:

class SnowflakeGenerator {
  constructor(epoch = 1288834974657, datacenterIdBits = 5, workerIdBits = 5, sequenceBits = 12) {
    this.epoch = BigInt(epoch);
    this.datacenterIdBits = datacenterIdBits;
    this.workerIdBits = workerIdBits;
    this.sequenceBits = sequenceBits;
    this.maxDatacenterId = -1n ^ (-1n << BigInt(datacenterIdBits));
    this.maxWorkerId = -1n ^ (-1n << BigInt(workerIdBits));
    this.sequenceMask = -1n ^ (-1n << BigInt(sequenceBits));
    this.workerIdShift = BigInt(sequenceBits);
    this.datacenterIdShift = BigInt(sequenceBits + workerIdBits);
    this.timestampLeftShift = BigInt(sequenceBits + workerIdBits + datacenterIdBits);
    this.sequence = 0n;
    this.lastTimestamp = -1n;
  }

  nextId(datacenterId, workerId) {
    let timestamp = this.currentTimestamp();

    if (timestamp < this.lastTimestamp) {
      throw new Error('Sat se pomaknuo unatrag. Odbijam generirati id');
    }

    if (timestamp === this.lastTimestamp) {
      this.sequence = (this.sequence + 1n) & this.sequenceMask;
      if (this.sequence === 0n) {
        timestamp = this.tilNextMillis(this.lastTimestamp);
      }
    } else {
      this.sequence = 0n;
    }

    this.lastTimestamp = timestamp;

    return ((timestamp - this.epoch) << this.timestampLeftShift) |
           (BigInt(datacenterId) << this.datacenterIdShift) |
           (BigInt(workerId) << this.workerIdShift) |
           this.sequence;
  }

  tilNextMillis(lastTimestamp) {
    let timestamp = this.currentTimestamp();
    while (timestamp <= lastTimestamp) {
      timestamp = this.currentTimestamp();
    }
    return timestamp;
  }

  currentTimestamp() {
    return BigInt(Date.now());
  }
}

// Upotreba
const generator = new SnowflakeGenerator();
const id = generator.nextId(1, 1);
console.log(`Generirani ID snježne pahulje: ${id}`);
import time
import threading

class SnowflakeGenerator:
    def __init__(self, datacenter_id, worker_id, sequence=0):
        self.datacenter_id = datacenter_id
        self.worker_id = worker_id
        self.sequence = sequence

        self.last_timestamp = -1
        self.epoch = 1288834974657

        self.datacenter_id_bits = 5
        self.worker_id_bits = 5
        self.sequence_bits = 12

        self.max_datacenter_id = -1 ^ (-1 << self.datacenter_id_bits)
        self.max_worker_id = -1 ^ (-1 << self.worker_id_bits)

        self.worker_id_shift = self.sequence_bits
        self.datacenter_id_shift = self.sequence_bits + self.worker_id_bits
        self.timestamp_left_shift = self.sequence_bits + self.worker_id_bits + self.datacenter_id_bits
        self.sequence_mask = -1 ^ (-1 << self.sequence_bits)

        self._lock = threading.Lock()

    def _til_next_millis(self, last_timestamp):
        timestamp = self._get_timestamp()
        while timestamp <= last_timestamp:
            timestamp = self._get_timestamp()
        return timestamp

    def _get_timestamp(self):
        return int(time.time() * 1000)

    def next_id(self):
        with self._lock:
            timestamp = self._get_timestamp()

            if timestamp < self.last_timestamp:
                raise ValueError("Sat se pomaknuo unatrag. Odbijam generirati id")

            if timestamp == self.last_timestamp:
                self.sequence = (self.sequence + 1) & self.sequence_mask
                if self.sequence == 0:
                    timestamp = self._til_next_millis(self.last_timestamp)
            else:
                self.sequence = 0

            self.last_timestamp = timestamp

            return ((timestamp - self.epoch) << self.timestamp_left_shift) | \
                   (self.datacenter_id << self.datacenter_id_shift) | \
                   (self.worker_id << self.worker_id_shift) | \
                   self.sequence

## Upotreba
generator = SnowflakeGenerator(datacenter_id=1, worker_id=1)
snowflake_id = generator.next_id()
print(f"Generirani ID snježne pahulje: {snowflake_id}")
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class SnowflakeGenerator {
    private final long epoch;
    private final long datacenterIdBits;
    private final long workerIdBits;
    private final long sequenceBits;
    private final long maxDatacenterId;
    private final long maxWorkerId;
    private final long workerIdShift;
    private final long datacenterIdShift;
    private final long timestampLeftShift;
    private final long sequenceMask;

    private long datacenterId;
    private long workerId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    private final Lock lock = new ReentrantLock();

    public SnowflakeGenerator(long datacenterId, long workerId) {
        this.epoch = 1288834974657L;
        this.datacenterIdBits = 5L;
        this.workerIdBits = 5L;
        this.sequenceBits = 12L;

        this.maxDatacenterId = ~(-1L << datacenterIdBits);
        this.maxWorkerId = ~(-1L << workerIdBits);

        this.workerIdShift = sequenceBits;
        this.datacenterIdShift = sequenceBits + workerIdBits;
        this.timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
        this.sequenceMask = ~(-1L << sequenceBits);

        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than maxDatacenterId or less than 0");
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("workerId can't be greater than maxWorkerId or less than 0");
        }
        this.datacenterId = datacenterId;
        this.workerId = workerId;
    }

    public long nextId() {
        lock.lock();
        try {
            long timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                throw new RuntimeException("Sat se pomaknuo unatrag. Odbijam generirati id");
            }

            if (lastTimestamp == timestamp) {
                sequence = (sequence + 1) & sequenceMask;
                if (sequence == 0) {
                    timestamp = tilNextMillis(lastTimestamp);
                }
            } else {
                sequence = 0L;
            }

            lastTimestamp = timestamp;

            return ((timestamp - epoch) << timestampLeftShift) |
                   (datacenterId << datacenterIdShift) |
                   (workerId << workerIdShift) |
                   sequence;
        } finally {
            lock.unlock();
        }
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowflakeGenerator generator = new SnowflakeGenerator(1, 1);
        long id = generator.nextId();
        System.out.println("Generirani ID snježne pahulje: " + id);
    }
}
require 'time'

class SnowflakeGenerator
  def initialize(datacenter_id, worker_id, sequence = 0)
    @datacenter_id = datacenter_id
    @worker_id = worker_id
    @sequence = sequence
    @last_timestamp = -1
    @epoch = 1288834974657

    @datacenter_id_bits = 5
    @worker_id_bits = 5
    @sequence_bits = 12

    @max_datacenter_id = -1 ^ (-1 << @datacenter_id_bits)
    @max_worker_id = -1 ^ (-1 << @worker_id_bits)

    @worker_id_shift = @sequence_bits
    @datacenter_id_shift = @sequence_bits + @worker_id_bits
    @timestamp_left_shift = @sequence_bits + @worker_id_bits + @datacenter_id_bits
    @sequence_mask = -1 ^ (-1 << @sequence_bits)
  end

  def next_id
    timestamp = (Time.now.to_f * 1000).to_i

    raise 'Sat se pomaknuo unatrag' if timestamp < @last_timestamp

    if timestamp == @last_timestamp
      @sequence = (@sequence + 1) & @sequence_mask
      timestamp = til_next_millis(@last_timestamp) if @sequence == 0
    else
      @sequence = 0
    end

    @last_timestamp = timestamp

    ((timestamp - @epoch) << @timestamp_left_shift) |
      (@datacenter_id << @datacenter_id_shift) |
      (@worker_id << @worker_id_shift) |
      @sequence
  end

  private

  def til_next_millis(last_timestamp)
    timestamp = (Time.now.to_f * 1000).to_i
    timestamp = (Time.now.to_f * 1000).to_i while timestamp <= last_timestamp
    timestamp
  end
end

## Upotreba
generator = SnowflakeGenerator.new(1, 1)
snowflake_id = generator.next_id
puts "Generirani ID snježne pahulje: #{snowflake_id}"
<?php

class SnowflakeGenerator {
    private $epoch;
    private $datacenterIdBits;
    private $workerIdBits;
    private $sequenceBits;
    private $maxDatacenterId;
    private $maxWorkerId;
    private $workerIdShift;
    private $datacenterIdShift;
    private $timestampLeftShift;
    private $sequenceMask;

    private $datacenterId;
    private $workerId;
    private $sequence = 0;
    private $lastTimestamp = -1;

    public function __construct($datacenterId, $workerId) {
        $this->epoch = 1288834974657;
        $this->datacenterIdBits = 5;
        $this->workerIdBits = 5;
        $this->sequenceBits = 12;

        $this->maxDatacenterId = -1 ^ (-1 << $this->datacenterIdBits);
        $this->maxWorkerId = -1 ^ (-1 << $this->workerIdBits);

        $this->workerIdShift = $this->sequenceBits;
        $this->datacenterIdShift = $this->sequenceBits + $this->workerIdBits;
        $this->timestampLeftShift = $this->sequenceBits + $this->workerIdBits + $this->datacenterIdBits;
        $this->sequenceMask = -1 ^ (-1 << $this->sequenceBits);

        if ($datacenterId > $this->maxDatacenterId || $datacenterId < 0) {
            throw new Exception("datacenterId can't be greater than maxDatacenterId or less than 0");
        }
        if ($workerId > $this->maxWorkerId || $workerId < 0) {
            throw new Exception("workerId can't be greater than maxWorkerId or less than 0");
        }
        $this->datacenterId = $datacenterId;
        $this->workerId = $workerId;
    }

    public function nextId() {
        $timestamp = $this->timeGen();

        if ($timestamp < $this->lastTimestamp) {
            throw new Exception("Sat se pomaknuo unatrag. Odbijam generirati id");
        }

        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;

        return (($timestamp - $this->epoch) << $this->timestampLeftShift) |
               ($this->datacenterId << $this->datacenterIdShift) |
               ($this->workerId << $this->workerIdShift) |
               $this->sequence;
    }

    private function tilNextMillis($lastTimestamp) {
        $timestamp = $this->timeGen();
        while ($timestamp <= $lastTimestamp) {
            $timestamp = $this->timeGen();
        }
        return $timestamp;
    }

    private function timeGen() {
        return floor(microtime(true) * 1000);
    }
}

// Upotreba
$generator = new SnowflakeGenerator(1, 1);
$id = $generator->nextId();
echo "Generirani ID snježne pahulje: " . $id . "\n";
using System;
using System.Threading;

public class SnowflakeGenerator
{
    private readonly long _epoch;
    private readonly int _datacenterIdBits;
    private readonly int _workerIdBits;
    private readonly int _sequenceBits;
    private readonly long _maxDatacenterId;
    private readonly long _maxWorkerId;
    private readonly int _workerIdShift;
    private readonly int _datacenterIdShift;
    private readonly int _timestampLeftShift;
    private readonly long _sequenceMask;

    private readonly long _datacenterId;
    private readonly long _workerId;
    private long _sequence = 0L;
    private long _lastTimestamp = -1L;

    private readonly object _lock = new object();

    public SnowflakeGenerator(long datacenterId, long workerId)
    {
        _epoch = 1288834974657L;
        _datacenterIdBits = 5;
        _workerIdBits = 5;
        _sequenceBits = 12;

        _maxDatacenterId = -1L ^ (-1L << _datacenterIdBits);
        _maxWorkerId = -1L ^ (-1L << _workerIdBits);

        _workerIdShift = _sequenceBits;
        _datacenterIdShift = _sequenceBits + _workerIdBits;
        _timestampLeftShift = _sequenceBits + _workerIdBits + _datacenterIdBits;
        _sequenceMask = -1L ^ (-1L << _sequenceBits);

        if (datacenterId > _maxDatacenterId || datacenterId < 0)
        {
            throw new ArgumentException($"datacenterId can't be greater than {_maxDatacenterId} or less than 0");
        }
        if (workerId > _maxWorkerId || workerId < 0)
        {
            throw new ArgumentException($"workerId can't be greater than {_maxWorkerId} or less than 0");
        }
        _datacenterId = datacenterId;
        _workerId = workerId;
    }

    public long NextId()
    {
        lock (_lock)
        {
            var timestamp = TimeGen();

            if (timestamp < _lastTimestamp)
            {
                throw new Exception("Sat se pomaknuo unatrag. Odbijam generirati id");
            }

            if (_lastTimestamp == timestamp)
            {
                _sequence = (_sequence + 1) & _sequenceMask;
                if (_sequence == 0)
                {
                    timestamp = TilNextMillis(_lastTimestamp);
                }
            }
            else
            {
                _sequence = 0L;
            }

            _lastTimestamp = timestamp;

            return ((timestamp - _epoch) << _timestampLeftShift) |
                   (_datacenterId << _datacenterIdShift) |
                   (_workerId << _workerIdShift) |
                   _sequence;
        }
    }

    private long TilNextMillis(long lastTimestamp)
    {
        var timestamp = TimeGen();
        while (timestamp <= lastTimestamp)
        {
            timestamp = TimeGen();
        }
        return timestamp;
    }

    private long TimeGen()
    {
        return DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
    }
}

// Upotreba
class Program
{
    static void Main(string[] args)
    {
        var generator = new SnowflakeGenerator(1, 1);
        var id = generator.NextId();
        Console.WriteLine($"Generirani ID snježne pahulje: {id}");
    }
}
package main

import (
	"fmt"
	"sync"
	"time"
)

type SnowflakeGenerator struct {
	epoch             int64
	datacenterIdBits  uint
	workerIdBits      uint
	sequenceBits      uint
	maxDatacenterId   int64
	maxWorkerId       int64
	workerIdShift     uint
	datacenterIdShift uint
	timestampLeftShift uint
	sequenceMask      int64

	datacenterId int64
	workerId     int64
	sequence     int64
	lastTimestamp int64

	lock sync.Mutex
}

func NewSnowflakeGenerator(datacenterId, workerId int64) (*SnowflakeGenerator, error) {
	g := &SnowflakeGenerator{
		epoch:             1288834974657,
		datacenterIdBits:  5,
		workerIdBits:      5,
		sequenceBits:      12,
		lastTimestamp:     -1,
	}

	g.maxDatacenterId = -1 ^ (-1 << g.datacenterIdBits)
	g.maxWorkerId = -1 ^ (-1 << g.workerIdBits)

	g.workerIdShift = g.sequenceBits
	g.datacenterIdShift = g.sequenceBits + g.workerIdBits
	g.timestampLeftShift = g.sequenceBits + g.workerIdBits + g.datacenterIdBits
	g.sequenceMask = -1 ^ (-1 << g.sequenceBits)

	if datacenterId > g.maxDatacenterId || datacenterId < 0 {
		return nil, fmt.Errorf("datacenterId can't be greater than %d or less than 0", g.maxDatacenterId)
	}
	if workerId > g.maxWorkerId || workerId < 0 {
		return nil, fmt.Errorf("workerId can't be greater than %d or less than 0", g.maxWorkerId)
	}
	g.datacenterId = datacenterId
	g.workerId = workerId

	return g, nil
}

func (g *SnowflakeGenerator) NextId() (int64, error) {
	g.lock.Lock()
	defer g.lock.Unlock()

	timestamp := g.timeGen()

	if timestamp < g.lastTimestamp {
		return 0, fmt.Errorf("sat se pomaknuo unatrag, odbijam generirati id")
	}

	if g.lastTimestamp == timestamp {
		g.sequence = (g.sequence + 1) & g.sequenceMask
		if g.sequence == 0 {
			timestamp = g.tilNextMillis(g.lastTimestamp)
		}
	} else {
		g.sequence = 0
	}

	g.lastTimestamp = timestamp

	return ((timestamp - g.epoch) << g.timestampLeftShift) |
		(g.datacenterId << g.datacenterIdShift) |
		(g.workerId << g.workerIdShift) |
		g.sequence, nil
}

func (g *SnowflakeGenerator) tilNextMillis(lastTimestamp int64) int64 {
	timestamp := g.timeGen()
	for timestamp <= lastTimestamp {
		timestamp = g.timeGen()
	}
	return timestamp
}

func (g *SnowflakeGenerator) timeGen() int64 {
	return time.Now().UnixNano() / int64(time.Millisecond)
}

func main() {
	generator, err := NewSnowflakeGenerator(1, 1)
	if err != nil {
		fmt.Printf("Greška pri stvaranju generatora: %v\n", err)
		return
	}

	id, err := generator.NextId()
	if err != nil {
		fmt.Printf("Greška pri generiranju ID-a: %v\n", err)
		return
	}

	fmt.Printf("Generirani ID snježne pahulje: %d\n", id)
}

Dijagram

Evo vizualne reprezentacije strukture ID-a snježne pahulje:

Vremenska oznaka (41 bita) ID stroja (10 bita) Sekvenca (12 bita)

Struktura ID-a snježne pahulje (64 bita)

Reference

  1. "Objava snježne pahulje." Twitter Engineering Blog, https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake
  2. "ID snježne pahulje." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID
  3. "Distribuirana generacija ID-a u mikrouslugama." Medium, https://medium.com/swlh/distributed-id-generation-in-microservices-b6ce9a8dd93f
Povratne informacije