题记

当我们需要生成不重复的ID，通常有以下几种做法：

UUID（通用唯一标识符）：使用算法生成的通用唯一标识符，可以保证在同一台机器上生成的ID不会重复，也可以在多台机器之间生成全局唯一ID。
雪花算法（Snowflake）：Twitter开发的一种生成不重复ID的算法，可以在分布式系统中生成不重复的ID。使用时间戳、数据中心ID和工作节点ID等信息进行位运算和组合生成ID。
数据库自增列：对于单机或者主从架构的系统，可以使用数据库的自增列功能来生成不重复的ID。每次插入一条新记录时，自增列的值就会加1，生成一个新的ID。

本文将重点讲述雪花算法。

1.数据库自增序列

在关系型数据库中，每个表需要有一个主键来唯一标识每条记录，在插入新记录时需要为其分配一个唯一的标识值。

数据库自增列的优点包括：

保证唯一性：自增列可以保证主键的唯一性，避免了数据冲突和错误。
简单易用：系统会自动为新记录分配下一个可用的值，无需手动指定。
性能好：数据库自增列使用内部计数器实现，比其他生成ID的方法效率更高，且不容易出错。
支持事务：自增列操作通常是原子性的，支持事务回滚，避免了数据不一致的问题。

数据库自增列的缺点包括：

不适用于分布式系统：在分布式系统中，多个节点之间无法共享自增列的值，可能会导致ID冲突。
不能重复利用已删除的ID：如果删除了某个记录，对应的ID仍然会被保留，不能再次分配给新记录使用，可能会浪费一些ID值。
限制较多：某些数据库的自增列还存在一些限制，例如不能使用负数、不能跨越INT或BIGINT等类型的边界等。

需要根据具体的场景和需求选择适合的ID生成方法。对于单机或主从架构的系统，数据库自增列是一种简单、高效、可靠的生成ID的方法。但在分布式系统中，需要使用其他方法来保证ID的唯一性并避免冲突。

2.UUID

UUID（通用唯一标识符）是一种生成不重复ID的方法，它的背景是在分布式系统中需要生成全局唯一的ID。

UUID的优点包括：

唯一性：UUID可以保证在同一台机器上生成的ID不会重复，也可以在多台机器之间生成全局唯一ID。
无序性：UUID是随机生成的，没有顺序或者规律可言，可以有效提高数据安全性和防止伪造。
可扩展性：UUID的长度为128位，可以通过不同的算法和版本来扩展其功能和应用。
独立于数据库：UUID生成独立于数据库，不需要额外的查询操作，减轻了数据库的负担。

UUID的缺点主要有两个：

长度较长：UUID的长度为128位，存储空间相对于其他ID生成方法较大，可能会占用更多的存储空间。
不易读懂：由于UUID是随机生成的，没有规律可言，不如自增列等ID生成方法直观易读。

总的来说，UUID适合在分布式系统中生成全局唯一的ID，可以避免ID冲突问题，但需要注意存储空间和可读性方面的影响。

3.雪花算法

雪花算法（Snowflake）是Twitter开发的一种生成不重复ID的算法，背景是在分布式系统中需要生成全局唯一的ID。

在分布式系统中，使用自增列作为主键可能会存在多个节点之间冲突的问题，而UUID虽然可以保证全局唯一性，但其长度较长、无序性和不易读懂等特点也带来了一些不方便的问题。因此，Twitter开发了雪花算法来解决这些问题。

结构

雪花算法（Snowflake）生成ID的结构组成如下：

第一个部分是符号位，占用1个bit，始终为0。
第二个部分是时间戳，占用41个bit，精确到毫秒级别。可以支持约69年的时间范围。
第三个部分是数据中心ID，占用5个bit，可以支持32个不同的数据中心。
第四个部分是工作节点ID，占用5个bit，可以支持32个不同的工作节点。
第五个部分是序列号，占用12个bit，可以支持同一毫秒内生成4096个不同的ID。

在雪花算法中，时间戳、数据中心ID和工作节点ID等信息通过位运算进行组合，生成全局唯一的ID。其中，时间戳部分采用了41个bit来表示，可以支持约69年的时间范围，而序列号部分则采用了12个bit来表示，可以支持同一毫秒内生成4096个不同的ID，从而保证了其唯一性。

优缺点

雪花算法的优点包括：

唯一性：雪花算法可以保证全局唯一性，避免了冲突问题。
有序性：雪花算法生成的ID具有趋势递增的特点，有利于提高数据库的性能和查询效率。
简单易用：雪花算法的实现比较简单，只需要基于时间戳和数据中心ID以及工作节点ID等信息进行位运算和组合即可。
可定制性：雪花算法支持根据业务需求调整位数分配和ID版本等参数，具有较强的定制性和扩展性。

雪花算法的缺点包括：

依赖于时钟回拨：雪花算法使用时间戳作为其中一部分，如果系统时间发生了回拨，可能会导致生成的ID不唯一或者无序。
限制较多：雪花算法需要为每个节点分配一个唯一的数据中心ID和工作节点ID，这些ID的分配需要进行规划和管理，避免出现重复或者误用情况。

总体来说，雪花算法是一种适用于分布式系统中的高效、简单、可扩展的生成全局唯一ID的方法。

在Go中的应用

type Snowflake struct {
    mutex       sync.Mutex // 互斥锁，保证并发安全
    lastTime    int64      // 上一次生成ID的时间戳
    datacenterId int64     // 数据中心ID
    workerId    int64      // 工作节点ID
    sequence    int64      // 序列号
}

const (
    datacenterBits = 5   // 数据中心ID所占位数
    workerBits     = 5   // 工作节点ID所占位数
    sequenceBits   = 12  // 序列号所占位数
    maxDatacenterId = -1 ^ (-1 << datacenterBits) // 最大数据中心ID，这里假设最多支持32个数据中心
    maxWorkerId    = -1 ^ (-1 << workerBits)     // 最大工作节点ID，这里假设每个数据中心最多支持32个工作节点
    maxSequence    = -1 ^ (-1 << sequenceBits)   // 最大序列号，这里假设同一毫秒内最多生成4096个ID
    timeShift      = datacenterBits + workerBits + sequenceBits // 时间戳左移位数
    datacenterShift = workerBits + sequenceBits                // 数据中心ID左移位数
    workerShift    = sequenceBits                            // 工作节点ID左移位数
)

func NewSnowflake(datacenterId, workerId int64) (*Snowflake, error) {
    if datacenterId < 0 || datacenterId > maxDatacenterId {
        return nil, fmt.Errorf("datacenter ID must be between 0 and %d", maxDatacenterId)
    }
    if workerId < 0 || workerId > maxWorkerId {
        return nil, fmt.Errorf("worker ID must be between 0 and %d", maxWorkerId)
    }
    return &Snowflake{
        lastTime:    -1,
        datacenterId: datacenterId,
        workerId:    workerId,
        sequence:    0,
    }, nil
}

func (sf *Snowflake) NextId() (int64, error) {
    sf.mutex.Lock()
    defer sf.mutex.Unlock()

    now := time.Now().UnixNano() / 1000000 // 转换为毫秒级时间戳
    if now == sf.lastTime {
        sf.sequence = (sf.sequence + 1) & maxSequence
        if sf.sequence == 0 {
            now = sf.getNextMillis(now)
        }
    } else {
        sf.sequence = 0
    }

    if now < sf.lastTime {
        return 0, fmt.Errorf("clock moved backwards")
    }

    sf.lastTime = now

    id := (now << timeShift) | (sf.datacenterId << datacenterShift) | (sf.workerId << workerShift) | sf.sequence
    return id, nil
}

func (sf *Snowflake) getNextMillis(last int64) int64 {
    timestamp := time.Now().UnixNano() / 1000000
    for timestamp <= last {
        timestamp = time.Now().UnixNano() / 1000000
    }
    return timestamp
}

雪花算法生成 ID 重复问题

假设：

一个订单微服务，通过雪花算法生成 ID，共部署三个节点，标识位一致。此时有 200 并发，均匀散布三个节点，三个节点同一毫秒同一序列号下生成 ID，那么就会产生重复 ID。

解决：

增加并发控制：通过对Snowflake结构体中的mutex字段进行加锁，可以保证在同一时间只有一个goroutine可以调用NextId函数，从而避免了多个节点同时生成相同的ID的情况。但是这样会降低性能，并且不适合高并发场景。
增加随机数：可以将序列号部分替换为一个随机数，这样即使在同一毫秒内也很难生成相同的ID。但是这种方法会降低ID的有序性，可能会对某些应用造成影响。
采用更高精度的时间戳：可以采用更高精度的时间戳来代替毫秒级别的时间戳，在同一毫秒内生成更多的ID，从而减少重复的概率。例如使用纳秒级别的时间戳，或者通过NTP协议同步时钟。
增加节点标识位的区分：可以增加节点标识位的区分，即让不同的节点具有不同的标识位，这样即使在同一毫秒内也可以生成不同的ID。但是需要注意的是，标识位的数量是有限制的，需要根据实际情况进行调整。
增加重试机制：如果出现了生成重复ID的情况，可以增加重试机制，在下一毫秒再次尝试生成新的ID。但是这会降低系统性能，并且如果重试次数过多可能会对应用造成影响。

第四种方式是增加节点标识位的区分。在雪花算法中，数据中心ID和工作节点ID一般都是固定不变的，如果多个节点共享相同的数据中心ID和工作节点ID，那么可能会出现同一毫秒内序列号相同的情况，进而导致生成重复的ID。为了避免这个问题，我们可以通过增加节点标识位的区分来让不同的节点具有不同的标识位。例如，可以将数据中心ID和工作节点ID合并成一个节点标识位，然后根据节点标识位的不同来区分不同的节点。假设我们有3个节点，它们的节点标识位分别为0、1和2。此时，即使在同一毫秒内序列号相同，由于节点标识位不同，生成的ID也会不同，从而避免了重复ID的问题。具体实现时，我们可以将节点标识位放到高位，例如占用5个bit，那么就可以支持32个节点。然后，根据节点标识位、时间戳和序列号进行位运算，生成全局唯一的ID。这样，即使在同一毫秒内生成相同的序列号，由于不同的节点标识位，也能够生成不同的ID。需要注意的是，增加节点标识位区分的方法需要在节点之间进行规划和管理，以确保每个节点的标识位不同。如果节点的数量超过了标识位所能表示的最大值，那么就需要扩展节点标识位的位数。

雪花算法流程

获取当前时间，转换为毫秒级的时间戳。
检查当前时间戳是否小于上一次生成ID的时间戳，如果是，则表示系统时钟回拨，需要等待时钟追上上一次生成ID的时间戳。
如果当前时间戳等于上一次生成ID的时间戳，则需要通过递增序列号的方式生成唯一ID。递增序列号的初始值为0，最大值为4095。如果序列号超过最大值，需要等待下一毫秒再生成ID。
如果当前时间戳大于上一次生成ID的时间戳，则将序列号重置为0，并更新上一次生成ID的时间戳为当前时间戳。
将当前时间戳左移22位，工作机器ID左移12位，序列号左移0位，然后进行按位或运算，将它们合并成一个64位的唯一ID。
返回生成的唯一ID作为结果。

Olivia的小跟班

雪花算法

题记

1.数据库自增序列

2.UUID

3.雪花算法

结构

优缺点

在Go中的应用

雪花算法生成 ID 重复问题