现在我们的应用几乎都是分布式系统，在每个应用中都有许多需要保证唯一的业务ID，这时，分布式系统该如何保证生成的业务ID唯一，是一个重要的技术点。希望能通过今天的文章，和大家一起透彻的理解主流的分布式ID生成算法。

1. 分布式系统中ID生成的重复问题

在如下所示的三台机器的集群中，如果三台机器同时向DB中写入ID，如果我们需要保证ID唯一，那么该怎么做？

一种方法是依靠DB自身主键ID自增的特性保证ID不重复，但是很多时候，我们的业务ID与数据库的主键ID并不相同，这时就行不通了。

那么，有没有可能在执行insert操作之前，我们能够在业务应用上预生成一个全局唯一的ID，之后再将ID连带其他数据一起插入DB呢？这就是我们今天要说的分布式ID生成算法了。

2. 依靠中间件管理ID

2.1. 依靠DB或者Redis

之前我们提到了，DB的主键是可以保证自增唯一的，Redis中也有类似的incr操作。我们可以依赖这些中间件生成唯一ID，需要时从DB或者Redis中取数。

这类方案的短板也是非常明显的，首先，需要引入一个中间件来专门做唯一ID的维护，其次，连续的业务ID很容易被反推或者进行撞库，另外，每次申请ID都要读写DB或者Redis，会有额外的性能开销。

2.2. 依靠DB批量下发ID

我们可以通过预分配的方式把每次请求都需要的取数操作合并成一次。我们可以在在DB中维护一个sequence表，用于专门维护已经下发的ID：

列名	说明	类型
appkey	应用标识	varchar
max_index	最大ID数	bigint
assigned_index	已分配的ID数	bigint

每次应用启动或者已经拉取的ID用完时，从sequence中拉取一定数量的ID，拉取时依靠数据库的锁维护幂等，存储在内存中，需要分配时直接从本地内存中拿取，只需要保证本地取数操作上锁，就能保证拿到的ID全局唯一了。

这类方案很好的弥补了2.1中额外性能开销的问题，但是业务ID连续的情况依旧存在。另外，应用运行中若发生重启，会重新申请一段新的ID段，会产生ID“空洞”。

3. UUID

UUID（Universally Unique Identifier）在各种计算机系统中被广泛使用，包括分布式系统、数据库和网络协议等方面。它最初由OSF（Open Software Foundation）和DCS（Digital Equipment Corporation）开发，并成为了ISO标准以及其他标准的一部分。UUID在全球范围内具有唯一性，因此能在大多数情况下确保唯一性标识。

UUID是一种用来唯一标识信息的标准化方法。UUID通常由32个十六进制数字组成，以连字符分隔成5段，形如8-4-4-4-12的格式。它的长度为128位，可以保证在全球范围内的唯一性。

UUID的生成算法主要分为五种类型：

1. 时间戳和节点标识：基于时间和节点标识生成UUID，保证每个节点的唯一性。
2. 使用称为名字空间的概念根据一个命名空间和一个名字的MD5哈希值产生UUID。
3. 使用称为随机或熵空间的概念来生成UUID。
4. 基于真实的网卡MAC地址，但发现在实际情况中多数UUID生成算法并不使用MAC地址。
5. 基于DCE安全的算法，在分布式环境中能保证唯一性。

不管是哪种算法，我们都能发现，UUID的生成是本地化的，完全不需要依赖外部中间件，这也是其优势所在。不过UUID相对比较长（128位），数据量很大时会占用不小的存储空间。

4. 雪花算法

SnowFlake是Twitter最早提出的一种全局ID生成算法，可以产生一个Time-Based的全局ID， 由于生成简单、ID趋势递增，业界采用的比较广泛。

雪花算法生成的ID是64位的整数，其中包括41位的时间戳，10位的机器ID，以及12位的序列号。具体的组成结构如下：

1. 符号位：固定为0，表示正数。
2. 时间戳：占据了41位，表示从一个固定的开始时间点开始的毫秒数，这样可以保证在41位内可以使用69年，时间戳的精度是毫秒级。
3. 机器ID：占据了10位，表示数据中心和机器的唯一标识ID。
4. 序列号：占据了12位，表示同一个毫秒内生成的ID序列号，可以在同一个毫秒内生成4096个不同的ID。

雪花算法能在本地化生成，算法简单，效率高，并且生成的ID比UUID短一倍，但是其有两个问题：

1. 41位时间戳只能支撑69年，时间再长就不够用了（虽然能活69年的业务也不多）。
2. 机器ID如何保证唯一？

第一个问题业界有人提出了改良版的雪花算法（时间戳的位数提高），这个处理起来也很简单，唯一的问题就是会导致雪花算法生成的ID变长了。

这里我们来说一下可以保证机器ID唯一的方式：

• 【本地版】使用HostName、HostIp、MacAddress来组成，不用依赖外部分配。

• • 本地版的好处是架构简单，但是有些集群机器可能使用同样的虚拟ID，这个时候计算出的机器ID就可能一样的，如果说使用一定唯一的MacAddress，我们就需要确保我们使用的将MacAddress映射到1024的本地映射算法不会将不同的MacAddress映射到同一位上，这个显然也很难，因此，本地版的机器ID生成算法在很高QPS的情况下，并且机器数量很多时，是有重复的可能的。

• 【中心化】利用zookeepker维护每个应用实例的workID。

• • 中心化的方案引入了zookeepker管理workID，是能保证workID的全局唯一的（美团的方案就是这样），但是zookeepker的引入也会导致复杂度的上升。

5. 后记

本文介绍了几种常见的分布式ID算法，其实每种算法都是有优有劣的，并没有说哪种方法一定是最好的。