Snaigės ID generatorius: kurkite ir analizuokite ID

1## Snoflako ID generatorius
2
3### Įvadas
4
5Snoflako ID yra unikalus identifikatorius, naudojamas paskirstytose sistemose, pirmą kartą sukurtas „Twitter“. Šis įrankis leidžia generuoti ir analizuoti snoflako ID, kurie yra 64 bitų sveikieji skaičiai, sudaryti iš laiko žymės, mašinos ID ir sekos numerio.
6
7### Kaip veikia snoflako ID
8
9Snoflako ID yra 64 bitų sveikieji skaičiai, struktūrizuoti taip:
10
11- 41 bitas: Laiko žymė (milisekundės nuo pasirinkto epochos)
12- 10 bitų: Mašinos ID (5 bitai duomenų centro ID, 5 bitai darbuotojo ID)
13- 12 bitų: Sekos numeris
14
15Ši struktūra leidžia generuoti maždaug 4,096 unikalių ID per milisekundę kiekvienai mašinai.
16
17### Naudojant snoflako ID generatorių
18
191. (Pasirinktinai) Nustatykite pasirinktinę epochą (numatytoji yra „Twitter“ epocha: 2010-11-04T01:42:54.657Z)
202. Įveskite mašinos ID (0-31) ir duomenų centro ID (0-31)
213. Paspauskite „Generuoti“, kad sukurtumėte naują snoflako ID
224. Sugeneruotas ID ir jo komponentai bus rodomi
23
24Norėdami išanalizuoti esamą snoflako ID, įveskite jį į „Išanalizuoti ID“ lauką ir paspauskite „Išanalizuoti“.
25
26### Formulė
27
28Snoflako ID yra sudaromas naudojant bitų operacijas:
29
30

plaintext ID = (laikoŽymė << 22) | (duomenųCentroId << 17) | (darbuotojoId << 12) | seka

1
2Kur:
3- `laikoŽymė` yra milisekundžių skaičius nuo epochos
4- `duomenųCentroId` yra 5 bitų sveikasis skaičius (0-31)
5- `darbuotojoId` yra 5 bitų sveikasis skaičius (0-31)
6- `seka` yra 12 bitų sveikasis skaičius (0-4095)
7
8### Apskaičiavimas
9
10Snoflako ID generatorius atlieka šiuos veiksmus:
11
121. Gauti dabartinę laiko žymę milisekundėmis
132. Užtikrinti, kad laiko žymė būtų didesnė už paskutinę naudotą laiko žymę (unikalumui)
143. Jei laiko žymė yra tokia pati kaip paskutinė, padidinti sekos numerį
154. Jei sekos numeris perpildomas (pasiekia 4096), palaukti kitos milisekundės
165. Sujungti komponentus naudojant bitų operacijas, kad sukurtumėte galutinį ID
17
18### Naudojimo atvejai
19
20Snoflako ID ypač naudingi:
21
221. Paskirstytose sistemose: Generuoti unikalius ID keliose mašinose be koordinavimo
232. Didelio tūrio duomenyse: Kurti rūšiuojamus ID dideliems duomenų rinkiniams
243. Mikroservisuose: Užtikrinti unikalius identifikatorius skirtingose paslaugose
254. Duomenų bazės dalijime: Naudoti laiko žymės arba mašinos ID komponentą efektyviam dalijimui
26
27#### Alternatyvos
28
29Nors snoflako ID yra galingi, kitos ID generavimo sistemos apima:
30
311. UUID (Universaliai unikalus identifikatorius): Naudingas, kai reikia paskirstyto generavimo be rūšiavimo
322. Automatiškai didėjantys duomenų bazės ID: Paprasta, bet ribota iki vienos duomenų bazės instancijos
333. ULID (Universaliai unikalus lexikografiškai rūšiuojamas identifikatorius): Panašus į snoflaką, bet su kita struktūra
34
35### Kraštutiniai atvejai ir apribojimai
36
371. Laiko sinchronizacija: Snoflako ID priklauso nuo sistemos laiko. Jei laikrodis juda atgal dėl NTP koregavimų ar vasaros laiko pokyčių, tai gali sukelti problemų su ID generavimu.
38
392. 2038 metų problema: 41 bitų laiko žymė perpildys 2079 m. (atsižvelgiant į „Twitter“ epochą). Sistemos, naudojančios snoflako ID, turėtų planuoti šį įvykį.
40
413. Mašinos ID kolizijos: Didelėse paskirstytose sistemose užtikrinti unikalius mašinos ID gali būti sudėtinga ir gali prireikti papildomos koordinacijos.
42
434. Sekos perpildymas: Ekstremaliai didelio našumo scenarijuose gali būti įmanoma išnaudoti 4096 sekas per milisekundę, potencialiai sukeliant vėlavimus.
44
455. Ne monotoniškumas tarp mašinų: Nors ID yra monotoniškai didėjantys vienoje mašinoje, jie gali nebūti griežtai monotoniški tarp kelių mašinų.
46
47### Istorija
48
49Snoflako ID buvo pristatyti „Twitter“ 2010 m. siekiant patenkinti poreikį turėti paskirstytus, laiko rūšiuojamus unikalius identifikatorius. Jie nuo to laiko buvo priimti ir pritaikyti daugelio kitų įmonių ir projektų.
50
51### Pavyzdžiai
52
53Štai snoflako ID generatorių įgyvendinimai įvairiose kalbose:
54
55

javascript 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('Laikrodis juda atgal. Atsisakoma generuoti 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()); } }

// Naudojimas const generator = new SnowflakeGenerator(); const id = generator.nextId(1, 1); console.log(Sugeneruotas snoflako ID: ${id});

1
2

python 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("Laikrodis juda atgal. Atsisakoma generuoti 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

Naudojimas

generator = SnowflakeGenerator(datacenter_id=1, worker_id=1) snowflake_id = generator.next_id() print(f"Sugeneruotas snoflako ID: {snowflake_id}")

1
2

java 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("duomenų centro ID negali būti didesnis už maksimalią duomenų centro ID arba mažesnis už 0");
    }
    if (workerId > maxWorkerId || workerId < 0) {
        throw new IllegalArgumentException("darbuotojo ID negali būti didesnis už maksimalią darbuotojo ID arba mažesnis už 0");
    }
    this.datacenterId = datacenterId;
    this.workerId = workerId;
}

public long nextId() {
    lock.lock();
    try {
        long timestamp = timeGen();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Laikrodis juda atgal. Atsisakoma generuoti 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("Sugeneruotas snoflako ID: " + id);
}

}

1
2

ruby 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 'Laikrodis juda atgal' 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

Naudojimas

generator = SnowflakeGenerator.new(1, 1) snowflake_id = generator.next_id puts "Sugeneruotas snoflako ID: #{snowflake_id}"

1
2

php

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("duomenų centro ID negali būti didesnis už maksimalią duomenų centro ID arba mažesnis už 0"); } if ($workerId > $this->maxWorkerId || $workerId < 0) { throw new Exception("darbuotojo ID negali būti didesnis už maksimalią darbuotojo ID arba mažesnis už 0"); } $this->datacenterId = $datacenterId; $this->workerId = $workerId; } public function nextId() { $timestamp = $this->timeGen(); if ($timestamp < $this->lastTimestamp) { throw new Exception("Laikrodis juda atgal. Atsisakoma generuoti 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); } } // Naudojimas $generator = new SnowflakeGenerator(1, 1); $id = $generator->nextId(); echo "Sugeneruotas snoflako ID: " . $id . "\n";

1
2

csharp 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($"duomenų centro ID negali būti didesnis už {_maxDatacenterId} arba mažesnis už 0");
    }
    if (workerId > _maxWorkerId || workerId < 0)
    {
        throw new ArgumentException($"darbuotojo ID negali būti didesnis už {_maxWorkerId} arba mažesnis už 0");
    }
    _datacenterId = datacenterId;
    _workerId = workerId;
}

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

        if (timestamp < _lastTimestamp)
        {
            throw new Exception("Laikrodis juda atgal. Atsisakoma generuoti 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();
}

}

// Naudojimas class Program { static void Main(string[] args) { var generator = new SnowflakeGenerator(1, 1); var id = generator.NextId(); Console.WriteLine($"Sugeneruotas snoflako ID: {id}"); } }

1
2

go 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("duomenų centro ID negali būti didesnis už %d arba mažesnis už 0", g.maxDatacenterId)
}
if workerId > g.maxWorkerId || workerId < 0 {
	return nil, fmt.Errorf("darbuotojo ID negali būti didesnis už %d arba mažesnis už 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("laikrodis juda atgal, atsisakoma generuoti 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("Klaida kuriant generatorių: %v\n", err) return }

id, err := generator.NextId()
if err != nil {
	fmt.Printf("Klaida generuojant ID: %v\n", err)
	return
}

fmt.Printf("Sugeneruotas snoflako ID: %d\n", id)

}

1
2### Diagrama
3
4Štai vizualinė snoflako ID struktūros atvaizdavimo schema:
5
6<svg width="600" height="100" xmlns="http://www.w3.org/2000/svg">
7  <rect x="0" y="0" width="380" height="50" fill="#4299e1"/>
8  <text x="190" y="30" font-family="Arial" fontSize="14" fill="white" textAnchor="middle">Laiko žymė (41 bitas)</text>
9  
10  <rect x="380" y="0" width="90" height="50" fill="#48bb78"/>
11  <text x="425" y="30" font-family="Arial" fontSize="14" fill="white" textAnchor="middle">Mašinos ID (10 bitų)</text>
12  
13  <rect x="470" y="0" width="130" height="50" fill="#ed8936"/>
14  <text x="535" y="30" font-family="Arial" fontSize="14" fill="white" textAnchor="middle">Sekos numeris (12 bitų)</text>
15  
16  <text x="300" y="80" font-family="Arial" fontSize="16" fill="black" textAnchor="middle">64 bitų snoflako ID struktūra</text>
17</svg>
18
19### Nuorodos
20
211. "Pristatome snoflaką." „Twitter“ inžinerijos tinklaraštis, https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake
222. "Snoflako ID." Vikipedija, https://en.wikipedia.org/wiki/Snowflake_ID
233. "Paskirstytas ID generavimas mikroservisuose." Medium, https://medium.com/swlh/distributed-id-generation-in-microservices-b6ce9a8dd93f
24

Whiz Tools

Snaigės ID generatorius: kurkite ir analizuokite ID

Snaigės ID generatorius