在互联网业务中，存在各种形式的唯一ID。比如支付系统中会有支付ID、退款ID等；视频网站会有每个视频的唯一ID；办公软件中会有用户ID、组织ID等等。这就意味着我们需要一种生成唯一ID的算法，而且现在的部署大多是分布式的，所以算法也要支持在不同的服务器之间也会生成唯一的ID。下面我们就介绍几种生成分布式唯一ID的算法。

MySQL自增ID

使用数据库的ID自增策略，MySQL的auto_increment。主要思路是为每个Server中的数据库设置不同的起始值和不同的步长（auto-increment-increment表示每一台数据库的起始id值，auto-increment-offset表示每一台数据库每一次的增加数字，即步长），生成不充分的ID的策略保证高可用。如果我们有3台数据库，设置值可以如下所示：

Server1：
auto-increment-increment = 1
auto-increment-offset = 3
 
Server2：
auto-increment-increment = 2
auto-increment-offset = 3
 
Server2：
auto-increment-increment = 3
auto-increment-offset = 3

如果是多个节点的话，假设为N：

MySQL分布式ID.png

但是呢，数据库自增ID并不是太适合作为分布式唯一ID。原因主要有两方面：

系统水平拓展比较困难。想象一下，如果我们现在部署了3个数据库。它们的起始ID分别是1，2，3，步长都是3。如果这三个数据库分别生成了3个ID，那就是1、2、3、4、5、6、7、8、9。如果我们需要扩容一个数据库，那它的起始ID和步长应该是多少呢？至少不能是4，3。因为如果这样生成的ID为4、7就已经是重复的了。这还是在数据库很少的情况下，如果我们上线了更多台数据库简直就是噩梦。

数据库压力会很大，每次获取ID都得读写一次数据库，非常影响性能，不符合分布式低延迟低和高QPS的要求(在高并发下，如果都去数据库里面获取id，那是非常影响性能的)。

Redis分布式ID

我们可以将这个分布式ID分为3部分：毫秒级时间、Redis集群节点、每个节点在每一毫秒自增序列值。

我们以生成64位节点值举例，因为ID为整数的时候第一位必须是0，所以最大值就是63位。
Redis分布式ID.png
然后我们将这63位进行分割，分出来41位作为毫秒，12位作为Redis节点的数量，剩余10位作为Redis节点在每一还毫秒的自增序列值。

41位的2进制转换为10进制的毫秒是2199023255551，再把这些毫秒转换为时间就是2039-09-07（需要注意的是开始时间是从1970-1-1开始计算的），可以用大约20年。
12位作为Redis节点，2进制转换为10进制是4095，也就是说最多支持4095个节点。
10位的自增序列值转换为10进制是1023，也就是说每个Redis节点每一毫秒值可以生成1023个节点值。

与MySQL相比，Redis集群可以说是解决了数据库集群创建分布式ID的性能问题，但是Redis集群系统水平扩展还是比较困难。毕竟节点的数量可能会超过我们预设的长度。

UUID

UUID 是通用唯一识别码（Universally Unique Identifier）的缩写。算法的核心思想是结合机器的网卡、当地时间、一个随记数来生成UUID。

优点是本地生成、效率高、无需考虑网络延迟。
缺点是没有递增趋势性、存储冗余、不易维护。

在Go语言中，有实现UUID的包，生成也很简单。

package main

import (
    "fmt"
    "github.com/satori/go.uuid"
)

func main() {
    u1 := uuid.NewV4()
    fmt.Printf("UUIDv4: %s\n", u1)
}

// 输出示例 UUIDv4: 43e480d2-db9b-4305-bdb6-4e6adbdbfe41

snowflake

snowflake雪花算法是Twitter的采用的一种生成分布式自增id的策略，是比较适合生产分布式ID的。

这个分布式ID我们分成3部分组成：时间戳，工作机器ID和序列号。

实际上我们发现刚才已经在Redis生成分布式ID上实现了类似的思路。其实对于中小型公司来说，可能并不需要这么长的位数，下列代码是雪花算法的19位简化版：

var (
    machineID     int64 // 机器 id 占10位, 十进制范围是 [ 0, 1023 ]
    sn            int64 // 序列号占 12 位,十进制范围是 [ 0, 4095 ]
    lastTimeStamp int64 // 上次的时间戳(毫秒级), 1秒=1000毫秒, 1毫秒=1000微秒,1微秒=1000纳秒
)

func init() {
    lastTimeStamp = time.Now().UnixNano() / 1000000
}

// SetMachineID 把机器 id 左移 12 位,让出 12 位空间给序列号使用
func SetMachineID(mid int64) {
    machineID = mid << 12
}

// GetSnowflakeID 生成全局唯一ID
func GetSnowflakeID() int64 {
    curTimeStamp := time.Now().UnixNano() / 1000000

    // 同一毫秒
    if curTimeStamp == lastTimeStamp {
        sn++
        // 序列号占 12 位,十进制范围是 [ 0, 4095 ]
        if sn > 4095 {
            time.Sleep(time.Millisecond)
            curTimeStamp = time.Now().UnixNano() / 1000000
            lastTimeStamp = curTimeStamp
            sn = 0
        }

        // 取 64 位的二进制数 0000000000 0000000000 0000000000 0001111111111 1111111111 1111111111  1 ( 这里共 41 个 1 )和时间戳进行并操作
        // 并结果( 右数 )第 42 位必然是 0,  低 41 位也就是时间戳的低 41 位
        rightBinValue := curTimeStamp & 0x1FFFFFFFFFF
        // 机器 id 占用10位空间,序列号占用12位空间,所以左移 22 位; 经过上面的并操作,左移后的第 1 位,必然是 0
        rightBinValue <<= 22
        id := rightBinValue | machineID | sn
        return id
    }

    if curTimeStamp > lastTimeStamp {
        sn = 0
        lastTimeStamp = curTimeStamp
        // 取 64 位的二进制数 0000000000 0000000000 0000000000 0001111111111 1111111111 1111111111  1 ( 这里共 41 个 1 )和时间戳进行并操作
        // 并结果( 右数 )第 42 位必然是 0,  低 41 位也就是时间戳的低 41 位
        rightBinValue := curTimeStamp & 0x1FFFFFFFFFF
        // 机器 id 占用10位空间,序列号占用12位空间,所以左移 22 位; 经过上面的并操作,左移后的第 1 位,必然是 0
        rightBinValue <<= 22
        id := rightBinValue | machineID | sn
        return id
    }

    if curTimeStamp < lastTimeStamp {
        return 0
    }

    return 0
}

over.