如何为分布式游戏服务器中的实体创建全局唯一数字id

游戏中需要使用唯一ID的场景

游戏场景唯一id
场景中的实体的唯一id(NPC、Monster、Building、Resource...)
业务系统中的唯一实体的id

唯一ID的实现方式

字符串唯一ID
数字唯一ID

如何设计一个全局唯一的数字id

使用数字做全局唯一id面临的问题

最大使用uint64位整数做唯一id
如何是分布式系统中各个服务(程序)创建全局唯一id
如何尽可能的使唯一id生成器使用足够长的时间

uint64位整数如何做到全局唯一？

要想在分布式系统做做到唯一id，那么意味着这个唯一id中已经包含/表达了足够区分各个系统(服务)的信息，那么如何在一个只有64bits的数字中包含这些信息呢？

第一步考虑就是需要在id中包含一个机器码(服务的唯一id)以此来区分不同的服务实例.
如何保证高并发环境下各个服务实例同时创建的id的唯一性.
如何保证同一个实例高并发环境下唯一id的生成.

基于Sonyflake改造后的idgenerator

想要了解如何使用一个数字去做到全局唯一首先需要了解一些雪花算法Snowflake，这是Twitter公司提出来的算法。因为Snowflake的灵活性和缺点，比如索尼的Sonyflake等等。我们这里也是基于这个算法进行改造。
我们先看下原生的Snowflake算法，原生Snowflake算法使用一个64 bit的整型数据，根据当前的时间来生成ID。原生Snowflake结构如下：

因为最高位是标识位，为1表示为负数，所以最高位不使用。
41bit 保存时间戳，精确到毫秒。也就是说最大可使用的年限是69年。
10bit 的机器位，能部属在1024台机器节点来生成ID。
12bit 的序列号，一毫秒最大生成唯一ID的数量为4096个。

Sonyflake是基于上面的snowflake改造的，变更了时间、机器码、序列号的位数，snoyflake的结构图如下:

下面来看看我们基于Sonyflake改造后设计实现的idgenerator的基本结构说明:

36bit 保存以10ms为时间单位的时间戳，最大可使用的年限是21年。
13bit 的机器位，能部属8192个节点来生成ID。
14bit 的序列号，10毫秒最大生成唯一ID的数量为16384个。

根据上面的结构我们可以看出来我们调整了时间、机器码、序列号的位数,下面我们来分析一下这么调整的原因。

时间位36bit 首先我们看下36bit能够表达的数最大值是1 << 36 (68719476736) 然后我们根据10ms时间单位来计算一下可以使用的天数. 1day = 24 60 60 100 10ms = 8640000 * 10ms 然后我们来计算68719476736 / 8640000 = 7953 day ≈ 21年.
13bit 的机器位 13bit表达机器码最多能支持8192个节点,一般游戏服务器架构节点很难突破这个节点数量.
14bit 序列号，这个是一个累增的序列表达每10ms内能够产生的唯一id数量. 10ms内允许产生16384个已经足够了.

我们改造后的idgenerator基本能够满足游戏服务器内产生的实体id的唯一性需求了，如果后续考虑其他方面的扩展性可以考虑根据实际应用场景调整时间、机器码、序列码的位数进行灵活控制.

核心实现代码如下:

// NextID generates a next unique ID.
func (sf *Idgenerator) NextID() (uint64, error) {
    const maskSequence = uint32(1<<BitLenSequence - 1)

    sf.mutex.Lock()
    defer sf.mutex.Unlock()

    current := currentElapsedTime(sf.startTime)
    if sf.elapsedTime < current {
        sf.elapsedTime = current
        sf.sequence = 0
    } else { // sf.elapsedTime >= current
        sf.sequence = (sf.sequence + 1) & maskSequence
        if sf.sequence == 0 {
            // 理论上不可能到这里,正常情况10ms不可能需要超过1<<20个id
            sf.elapsedTime++
            overtime := sf.elapsedTime - current
            time.Sleep(sleepTime((overtime)))
        }
    }

    return sf.toID()
}

func (sf *Idgenerator) toID() (uint64, error) {
    if sf.elapsedTime >= 1<<BitLenTime {
        return 0, errors.New("over the time limit")
    }

    return uint64(sf.elapsedTime)<<(BitLenSequence+BitLenMachineID) |
        uint64(sf.sequence)<<BitLenMachineID |
        uint64(sf.machineID), nil
}

// NextID generates a next unique ID.

func (sf *Idgenerator) NextID() (uint64, error) {

const maskSequence = uint32(1<<BitLenSequence - 1)

sf.mutex.Lock()

defer sf.mutex.Unlock()

current := currentElapsedTime(sf.startTime)

if sf.elapsedTime < current {

sf.elapsedTime = current

sf.sequence = 0

} else { // sf.elapsedTime >= current

sf.sequence = (sf.sequence + 1) & maskSequence

if sf.sequence == 0 {

// 理论上不可能到这里,正常情况10ms不可能需要超过1<<20个id

sf.elapsedTime++

overtime := sf.elapsedTime - current

time.Sleep(sleepTime((overtime)))

}

return sf.toID()

}

func (sf *Idgenerator) toID() (uint64, error) {

if sf.elapsedTime >= 1<<BitLenTime {

return 0, errors.New("over the time limit")

}

return uint64(sf.elapsedTime)<<(BitLenSequence+BitLenMachineID) |

uint64(sf.sequence)<<BitLenMachineID |

uint64(sf.machineID), nil

}