跳转至

雪花算法

雪花算法（Snow Flake）是一种生成全局唯一ID的算法，它可以生成64位的ID，其中5位是毫秒级时间戳，41位是自增序列号，10位是机器标识和计数器。

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TIMESTAMP_LEFT_SHIFT 5
#define TIMESTAMP_MASK 0x1F
#define MACHINE_ID_LEFT_SHIFT 41
#define MACHINE_ID_MASK 0x7FF
#define SEQUENCE_LEFT_SHIFT 12
#define SEQUENCE_MASK 0xFFF

unsigned long long snowflake_next_id()
{
    static unsigned long long last_timestamp = 0;
    static unsigned long long machine_id = 0;
    static unsigned long long sequence = 0;

    unsigned long long timestamp = time(NULL);
    if (timestamp < last_timestamp) {
        fprintf(stderr, "Clock moved backwards. Refusing to generate id.");
        exit(1);
    }

    if (timestamp == last_timestamp) {
        sequence = (sequence + 1) & SEQUENCE_MASK;
        if (sequence == 0) {
            timestamp = (timestamp + 1) & TIMESTAMP_MASK;
            if (timestamp == 0) {
                machine_id = (machine_id + 1) & MACHINE_ID_MASK;
                if (machine_id == 0) {
                    fprintf(stderr, "Failed to generate unique machine id.");
                    exit(1);
                }
            }
        }
    } else {
        sequence = 0;
    }

    last_timestamp = timestamp;

    return ((timestamp << TIMESTAMP_LEFT_SHIFT) |
            (machine_id << MACHINE_ID_LEFT_SHIFT) |
            (sequence << SEQUENCE_LEFT_SHIFT));
}

int main()
{
    unsigned long long id = snowflake_next_id();
    printf("Generated id: %llu\n", id);
    return 0;
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package main

import (
    "fmt"
    "time"
)

const (
    TIMESTAMP_LEFT_SHIFT = 5
    TIMESTAMP_MASK       = 0x1F
    MACHINE_ID_LEFT_SHIFT = 41
    MACHINE_ID_MASK       = 0x7FF
    SEQUENCE_LEFT_SHIFT  = 12
    SEQUENCE_MASK        = 0xFFF
)

var (
    lastTimestamp = uint64(0)
    machineId     = uint64(0)
    sequence      = uint64(0)
)

func snowflakeNextId() uint64 {
    timestamp := uint64(time.Now().UnixNano() / 1e6)
    if timestamp < lastTimestamp {
        fmt.Println("Clock moved backwards. Refusing to generate id.")
        return 0
    }

    if timestamp == lastTimestamp {
        sequence = (sequence + 1) & SEQUENCE_MASK
        if sequence == 0 {
            timestamp = (timestamp + 1) & TIMESTAMP_MASK
            if timestamp == 0 {
                machineId = (machineId + 1) & MACHINE_ID_MASK
                if machineId == 0 {
                    fmt.Println("Failed to generate unique machine id.")
                    return 0
                }
            }
        }
    } else {
        sequence = 0
    }

    lastTimestamp = timestamp

    return ((timestamp << TIMESTAMP_LEFT_SHIFT) |
            (machineId << MACHINE_ID_LEFT_SHIFT) |
            (sequence << SEQUENCE_LEFT_SHIFT))
}

func main() {
    id := snowflakeNextId()
    fmt.Printf("Generated id: %d\n", id)
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import time
import struct

class SnowFlake:
    def __init__(self):
        self.machine_id = 0
        self.sequence = 0
        self.last_timestamp = 0

    def get_next_id(self):
        timestamp = int(time.time() * 1000)
        if timestamp < self.last_timestamp:
            raise ValueError('Clock moved backwards.')
        if timestamp == self.last_timestamp:
            self.sequence = (self.sequence + 1) & 0xfff
        else:
            self.sequence = 0
        self.last_timestamp = timestamp
        machine_id = struct.pack('>H', self.machine_id)
        return struct.unpack('>Q', machine_id + struct.pack('>L', timestamp-self.last_timestamp) + struct.pack('>H', self.sequence))[0]

if __name__ == '__main__':
    snowflake = SnowFlake()
    for i in range(10):
        print(snowflake.get_next_id())