在传统的单体架构中，我们基本上只有一个库和一个业务表结构。一般每个业务表的ID从1开始递增，起始值设置为AUTO_INCREMENT=1。但是，在分布式服务架构模式下，子数据库和子表的设计使得多个数据库或表存储相同的业务数据。这种情况下会根据数据库的自增ID生成相同的ID，不能保证主键的唯一性。

如上图所示，如果第一个订单存储在DB1，那么订单ID为1，当新订单存储时，存储在DB2中的订单ID也为1。虽然我们系统的架构是分布式的，但是在用户层面应该是察觉不到的，重复顺序主键显然是不允许的。那么如何让主键对于分布式系统是唯一的呢？

Uuuid(通用唯一标识符)，通用唯一标识符的缩写。UUID由一组32位的十六进制数字组成，所以理论上uuid的总数是16 ^ 32=2 ^ 128，大约是3.4 x 10^38.也就是说，如果每纳秒产生1万亿个uuid，那么需要100亿年才能用完所有uuid。

生成的UUID由8-4-4-4-12格式的数据组成，包括32个字符和4个连字符'-'一般我们在使用的时候，连字符会从uuid.toString()中删除。replaceAll('-'' ')。

目前，UUID有五个版本，每个版本都有不同的算法和不同的应用范围。

UUID基于时间-版本1:这个一般是通过当前时间，随机数，和本地Mac地址计算出来的。可以通过org . Apache . logging . log4j . core . util包中的UuidUtil.getTimeBasedUuid()或者包中的其他工具使用。因为使用了MAC地址，可以保证唯一性，但同时也暴露了MAC地址，私密性不够好。UUID安全由DCE-版本2 DCE(分布式计算环境)安全UUID与UUID算法相同基于时间，但时间戳的前四位将改为POSIX的UID或GID。这个版本的UUID在实践中很少使用。基于名称的UUID(MD5)-基于名称的第3版UUID是通过计算名称和命名空间的MD5哈希值获得的。这个版本的UUID保证了同一名称空间中不同名称生成的uuid的唯一性；UUID在不同命名空间中的唯一性；在同一个命名空间中重复生成同名的UUID是一样的。随机UUID-版本4产生UUID根据随机数，或伪随机数。这个UUID的重复概率是可以计算的，但是重复的可能性微乎其微，所以这个版本也是一个经常使用的版本。这个版本在JDK使用。基于名称的UUID(SHA1)-第5版类似于基于名称的UUID算法，只是哈希值计算使用SHA1(安全哈希算法1)算法。Java中JDK生成的UUID是版本4中随机数生成的UUID，版本3中基于名字的UUID。如果你有兴趣，可以看看它的源代码。

public static void main(string[]args){//根据随机字节数组得到版本4的UUID。UUID uuid=uuid . random uuid()；system . out . println(uuid . tostring()。replaceAll('-'' ')；//根据指定的字节数组获取版本3的UUID(基于名称)。byte[] nbyte={10，20，30 }；UUID uuidFromBytes=uuid . namuuidfrombytes(nbyte)；system . out . println(uuidfrombytes . tostring()。replaceAll('-'' ')；}获得的UUID结果，

5 f 51 e 7 e 5 ca 453 bb faf 2c 1579 f 09 f 1d 7 f 49 b 84d 0 BBC 38 e9 a 493718013 baa CE6 UUID虽然生成简单，没有本地生成的网络消耗，但是使用起来也有一些缺点。

不易存储：UUID太长，16字节128位。通常表示为36长度的字符串，很多场景都不适用。信息不安全：基于MAC地址生成UUID的算法可能造成MAC地址泄露，暴露用户位置。Mysql索引的缺点：如果是数据库的主键，在InnoDB引擎下，UUID的无序可能会造成数据位置的频繁变化，严重影响性能。可以查阅MySQL索引原理B树的知识。数据库生成是否必须基于外部条件才能满足分布式唯一ID的需求？在我们的分布式数据库的基础上能得到我们需要的ID吗？

由于分布式数据库的初始自增量是相同的，所以会有冲突。然后，我们将分布式系统中数据库的同一业务表的自增量ID设计为不同的初始值，然后设置一个固定的步长，其值为子数据库或子表的个数。

以MySQL为例，给字段设置auto_increment_increment和auto_increment_offset，保证ID会自动增加。

Auto_increment_offset:表示自增长字段从该数字开始，取值范围为1.65535.Auto_increment_increment:表示自增字段每次的增量。其默认值为1，取值范围为1.65535.假设有三台机器，DB1订单表的初始ID值是1，DB2订单表的初始值是2，DB3订单表的初始值是3。它们的增量步长都是3，ID生成范围如下图所示：

这种方式的明显优点是依赖于数据库本身，不需要其他资源，ID号单调自增，可以实现一些对ID有特殊要求的服务。

但是缺点也很明显。一是严重依赖DB，DB异常时整个系统不可用。虽然配置主从复制可以尽可能提高可用性，但是在特殊情况下，数据一致性很难保证。主从切换不一致可能导致重复发号。还有ID编号性能的瓶颈，仅限于单个MySQL的读写性能。

利用redis实现Redis实现分布式唯一ID主要是通过提供INCR、INCRBY等自增原子命令。由于Redis本身的单线程特性，可以保证生成的ID唯一有序。

但是单机有一个性能瓶颈，无法满足高并发的业务需求，所以可以通过集群来实现。聚类会涉及到和数据库聚类一样的问题，所以也需要设置分段和步长。

为避免长期自增后数量过多，可结合当前时间戳使用。另外，为了保证业务的并发性和多线程，可以用Redisloa进行编码，保证安全性。

Redis实现分布式全球唯一ID，性能高，生成的数据有序，有利于业务排序。但也依赖于redis，需要系统引入Redis组件，增加了系统配置的复杂度。

当然现在Redis的使用已经很普遍了，所以如果其他业务都引入了Redis集群，我们可以考虑使用Redis进行资源利用。

算法-SnowflakeSnowflake，雪花算法是Twitter开源的分布式ID生成算法。它通过划分命名空间将64位的位分成多个部分，每个部分代表不同的含义。在Java中，64位整数是一种长整型，因此Java中雪花算法生成的ID存储为长整型。

第一位占用1bit，其值始终为0，可视为符号位未使用。第2位开头的41位是时间戳，41位可以代表2个41数，每个数代表毫秒，所以可用的雪花算法是时间岁是(1L41)/(1000L360024*365)=69岁时间。中间的10位可以表示机器的数量，即2 ^ 10=1024台机器，但一般情况下，我们不会部署这样的机器。如果我们对IDC(互联网数据中心)有需求，也可以把10位分成5位用于IDC，5位用于工作机。这个可以代表32个IDC，每个IDC可以有32台机器，具体划分可以根据自己的需求来定义。最后12位是自增序列，可以表示2 ^ 12=4096的个数。经过这种划分，相当于在一个数据中心的一台机器上，一毫秒内生成4096个有序且不重复的id。但是必须有不止一个IDC和机器，所以毫秒级生成的有序id数翻倍。

雪花的Twitter官方原版是用Scala写的。学过Scala语言的同学可以看看。下面是Java版本的编写方法。

包com . jajian . demo . distribute；

/**

*推特_雪花

*雪花片的结构如下(各部分用-)隔开：

* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

* 1位id，因为Java中基本类型long是带符号的，最高位是符号位，正数为0，负数为1，所以ID一般为正，最高位为0。

* 41位时间段(毫秒级)。注意，41位时间段不存储当前时间段，而是存储时间段的差(当前时间段

*获得的值)，这里是开头时间，一般是我们的id生成器使用的时间，是我们程序指定的(如下图程序IdWorker类的startTime属性所示)。41位时间件，可使用69年。全年t=(1l 41)/(1000 l * 60 * 60 * 24 * 365)=69。

* 10位数据机位，可部署在1024个节点，包括5位datacenterId和5位workerId。

* 12位序列，以毫秒为单位计数，12位计数序列号支持每个节点每毫秒生成4096个ID序列号(同机，同时间段)

*加起来刚好64位，属于长类型。

*雪花的好处是整体上按照时间排序，整个分布式系统不会出现ID冲突(以数据中心ID和机器ID区分)，效率高。经过测试，雪花每秒可以生成大约26万个id。

*/

公共类SnowflakeDistributeId {

//===========================字段===============================

/**

*开始时间时间 (2015-01-01)

*/

私终长twepoch=1420041600000L

/**

*机器id占用的位数

*/

private final long worker idbits=5L；

/**

*数据标识id占用的位数

*/

private final long datacenterIdBits=5L；

/**

*支持的最大机器id，结果是31(这种移位算法可以快速计算出几个二进制数所能代表的最大十进制数)

*/

private final long maxworkerid=-1l ^(-1l workeridbits)；

/**

*支持的最大数据id，结果是31

*/

private final long maxdatacenterid=-1l ^(-1l datacenteridbits)；

/**

id中序列的位数

*/

私有最终长序列=12L

/**

*机器ID向左移动12位。

*/

private final long workerid shift=sequence bits；

/**

*数据标识id向左移动17位(12 ^ 5)

*/

private final long data centerid shift=sequence bits worker idbits；

/**

*时间部分向左移动22位(5 5 12)

*/

private final long timestamp left shift=sequence bits worker idbits datacenterIdBits；

/**

*生成序列的掩码，这里是4095(0b 11111111111=0x fff=4095)

*/

私有最终长序列mask=-1l ^(-1l sequence bits)；

/**

*工作机ID(0~31)

*/

列兵长workerId

/**

*数据中心ID(0~31)

*/

private long datacenterId

/**

*毫秒内的序列(0~4095)

*/

私有长序列=0L

/**

*最后生成的ID时间

*/

private long last timestamp=-1L；

//===========================构造函数============================

/**

*构造函数

*

* @param workerId作业ID (0~31)

* @param datacenterId数据中心ID (0~31)

*/

public SnowflakeDistributeId(long workerId，long datacenterId) {

if(workerId maxWorkerId | | workerId 0){

抛出new IllegalArgumentException(string . format(' worker Id不能大于%d或小于0 'maxWorkerId))；

}

if(data centerid maxdata centerid | | data centerid 0){

抛出new IllegalArgumentException(string . format(' data center Id不能大于%d或小于0 'maxDatacenterId))；

}

this.workerId=workerId

this . data centerid=data centerid；

}

//===========================方法=============================

/**

*获取下一个ID(这个方法是线程安全的)

*

* @return SnowflakeId

*/

公共同步长nextId() {

长时间戳=time gen()；

//如果当前时间小于最后一个ID生成的时间戳记，则意味着系统时钟回滚时应该抛出异常。

if(时间戳lastTimestamp) {

抛出新的RuntimeException(

'时钟向后移动。拒绝为%d毫秒'生成id，last timestamp-timestamp))；

}

//如果是由同一个时间生成，则执行毫秒内的序列。

if (lastTimestamp==timestamp) {

sequence=(sequence 1)sequence mask；

//以毫秒为单位的序列溢出

if (sequence==0) {

//阻塞到下一毫秒，获取一个新的时间戳

timestamp=tilNextMillis(last timestamp)；

}

}

//时间标记更改，序列重置(毫秒)

否则{

sequence=0L

}

//最后生成的ID时间

lastTimestamp=时间戳；

//通过OR运算将移位和拼写在一起，形成一个64位ID

return((timestamp-twepoch)timestampLeftShift)//

|(数据中心Id数据中心IdShift) //

| (workerId workerIdShift) //

|序列；

}

/**

*阻塞直到下一个毫秒，直到获得一个新的时间戳

*

* @param lastTimestamp最后生成的ID时间

* @返回电流时间戳

*/

受保护的long tilNextMillis(long last timestamp){

长时间戳=time gen()；

while(timestamp=last timestamp){

timestamp=time gen()；

}

返回时间戳；

}

/**

*以毫秒为单位返回当前值时间

*

* @返回电流时间(毫秒)

*/

受保护的长时间生成(){

返回system . current time millis()；

}

}

测试代码如下

公共静态void main(String[] args) {

SnowflakeDistributeId id worker=new SnowflakeDistributeId(0，0)；

for(int I=0；i 1000i ) {

long id=id worker . nextid()；

//system . out . println(long . tobinary string(id))；

system . out . println(id)；

}

}

雪花算法提供了一个很好的设计思路。雪花算法生成的ID是趋势递增的，不依赖于数据库等第三方系统。它作为服务部署，具有更高的稳定性和非常高的ID生成性能。而且可以根据自己的业务特点分配比特，非常灵活。

然而，雪花算法严重依赖于机器时钟。如果机器上的时钟回拨，将导致重复号码或服务不可用。如果恰好在回滚之前生成了一些id，并且时间回滚，则生成的id可能会重复。对此没有官方的解决方案，只是简单的错误处理，在时间恢复之前会使时间的服务不可用。

许多其他类似雪花的算法也是基于这一思想设计的，然后加以改进以避免其缺陷。百度UIDGER中的雪花模式，以及后面介绍的美团分布式UidGenerator系统Leaf，都是在雪花的基础上进化而来的。

百度-UidGenerator百度的UidGenerator是百度开源唯一基于Java语言实现的ID生成器，在雪花算法的基础上做了一些改进。UidGenerator在应用项目中作为一个组件工作，支持自定义workerId数字和初始化策略，适用于docker等虚拟化环境中的自动重启和漂移等实例。

在实现方面，UidGenerator提供了两种生成唯一ID的方式，分别是DefaultUidGenerator和CacheUIGenerator。官方的建议是，如果有性能方面的考虑，就使用CacheUIGenerator。

UidGenerator仍然通过划分命名空间的方式将64位的位分成很多部分，但其默认的划分方式与雪花算法不同。默认按1-28-22-13的格式划分。根据您业务的情况和特点，您可以调整每个字段占用的位数。

第1位仍占1位，其值始终为0。第2位开头的28位是时间戳，28位可以代表2 ^ 28个数字。这里不再以毫秒为单位而是以秒为单位，每个数字都代表秒，所以可以用(1L28)/(360024365) 8.51年时间。中间的workId(数据中心工作机，可以用其他方式组成)由22位组成，可以表示2 ^ 22=4，194，304个workId。最后13位构成自增序列，可以表示2 ^ 13=8192的个数。WorkId(机器Id)最多可以支持420w左右的机器启动。内置是数据库在启动时分配的(表名为WORKER_NODE)，默认分配策略是用后即弃。稍后可以提供重用策略。

如果存在WORKER_NODE，则删除表；

创建表WORKER_NODE

（

ID BIGINT NOT NULL AUTO_INCREMENT注释'自动增量ID '

HOST_NAME VARCHAR(64) NOT NULL注释“主机名”，

PORT VARCHAR(64) NOT NULL注释“PORT”，

TYPE INT NOT NULL注释“节点类型：实际或容器”，

启动日期日期不为空注释'启动日期'

修改时间戳不为空注释'修改时间'

创建时间戳不为空注释'创建时间'

主键(ID)

)

COMMENT=' DB WorkerID Assigner for UID Generator 'ENGINE=INNODB

DefaultUidGenerator的实现

DefaultBuilder是正常的基础时间戳，机位和序列号的生成方法，和雪花算法很像，只对时钟回调抛出异常。只是有些区别，比如用秒代替毫秒，支持Docker等虚拟化环境。

受保护的同步long nextId(){ long current second=getCurrentSecond()；//时钟后移，拒绝生成uid if(current second last second){ long refused seconds=last second-current second；引发新的UidGenerateException('时钟向后移动。拒绝%d秒，拒绝秒)；} //在同一秒，增加sequence if(current second==last second){ sequence=(sequence 1)bits allocator . getmax sequence()；//超过max序列，我们等待下一秒生成uid if(sequence==0){ current second=get next second(last second)；} //在不同的秒，序列从零重新开始}否则{ sequence=0L} lastSecond=currentSecond//为UID分配位返回bits allocator . Allocate(currentSecond-epochSeconds，workerId，sequence)；}如果要用DefaultBuilder的实现，上面划分的占用位数可以用spring配置。

cachebuilder的实现

但是官方推荐的高性能生成CacheBuilder的方式是缓存RingBuffer生成的id。数组的每个元素都成为一个槽。默认情况下，RingBuffer容量是雪花算法中序列的最大值(2 ^ 13=8192)。可以通过boostPower配置进行扩展，读写吞吐量为提高 RingBuffer。

尾指针和光标指针用于读写环形数组上的槽：

尾指针表示生产者生产的最大序列号(这个序列号从0开始，继续增加)。Tail不能超过Cursor，也就是说，生成器不能覆盖未使用的插槽。当Tail追上curosr时，可以通过rejectedPutBufferHandler指定PutRejectPolicyCursor指针，以指示消费者消费的最小序列号(序列号序列与生产者序列相同)。游标不能超过Tail，即不能消耗非生产性槽。当光标追上tail时，可以通过rejectedTakeBufferHandler指定TakeRejectPolicyCachedBuilder使用双环形缓冲区，Uid-RingBuffer用于存储Uid，Flag-RingBuffer用于存储Uid状态(是否可以填充或消耗)。

因为数组元素是在内存中连续分配的，所以可以最大限度地利用CPU缓存来提高性能。同时会带来“伪共享”假共享的问题。因此，在尾部、光标指针和Flag-RingBuffer中采用了CacheLine补全。

环形缓冲区填充机会

初始化预填充的RingBuffer初始化时，整个RingBuffer都是预填充的。当填充即时Take消耗时，立即检查剩余的可用槽量(尾光标),如果它小于设置的阈值，则完成空闲槽。阈值可以通过paddingFactor进行配置，请参考快速入门中CacheBuilder的配置。周期通过调度线程来填充，空闲槽定期填充。可以通过scheduleInterval进行配置，以应用定时填充功能并指定Schedule时间间隔。美团LeafLeaf是美团基础R&D平台推出的分布式ID生成服务。它的名字取自德国哲学家、数学家莱布尼茨的名言：“世界上没有两片完全相同的树叶”。世界上不可能有两片完全相同的树叶。

Leaf还提供了两种ID生成方式，即叶段数据库方案和叶雪花方案。

叶段数据库方案

叶段数据库方案基于上述使用数据库的方案，具有以下变化：

在原方案中，每次获取ID都要对数据库进行一次读写，给数据库造成了很大的压力。相反，代理服务器用于一次获取一个段的值(步长决定大小)。用完后去数据库取一个新的号段，可以大大减轻数据库的压力。每个服务的不同发布需求通过biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后需要对数据库进行性能需求的扩展，不需要上述复杂的扩展操作，只需要对biz_tag数据库和表进行划分即可。数据库设计如下：

create ` leaf _ alloc `( ` biz _ tag ` varchar(128)not null default ' ' comment ' business key '` max _ id ` bigint(20)not null default ' 1 ' comment '目前已分配的最大ID '` step` int (11) not null comment '的初始步长，这也是动态调整的最小步长'` Description ` varchar(256)default null comment ' business key '` update _ time ` timestamp not null default current _ timestamp on update current _ timestamp原来每次得到ID都需要写数据库。现在你只需要把步长设置得足够大，比如1000。然后，只有在消耗完1000个数字后，才会再次读写数据库。数据库的读写频率由1次降为1次/步，大致结构如下图所示：

同时，为了解决TP999(满足999%网络请求所需的最低时间)数据波动较大的问题，当number Leaf-segment用完时，仍然会挂在更新数据库的I/O上，TP999数据会偶尔出现尖峰，所以提供了双缓冲优化。

简单来说，Leaf取号段的时间就是号段用完的时候，也就是说号段临界点的ID发出时间，这取决于下一次从DB时间中检索号段的时间，在此期间的传入请求也会因为没有检索到DB号段而被阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统影响不大。但是如果取DB时网络抖动，或者DB慢查询会导致整个系统反应慢时间。

为了使DB取号的过程畅通，DB取号时不需要阻塞请求线程，即当号段消耗到某一点时，下一个号段异步加载到内存中，不需要等到号段耗尽后再更新号段。这可以大大降低系统的TP999指数。具体实现如下图所示：

在双缓冲区方式中，叶子服务中有两个段缓冲区。当前号段已发行10%时，如果下一个号段没有更新，则启动另一个更新线程更新下一个号段。当前段全部发出后，如果下一段准备好了，就切换到下一段做当前段，然后发出，重复。

每个biz-tag都有消耗速度监控，通常建议在服务高峰期将段长设置为QPS的600倍(10分钟)，这样即使DB宕机，Leaf也可以继续发号10-20分钟而不受影响。每次有请求来的时候都会判断下一个网段的状态来更新这个网段，所以偶尔的网络抖动不会影响下一个网段的更新。这个方案还有一些问题。还是要看DB的稳定性，需要采用主从备份的方式提高 DB的可用性。此外，由叶段方案生成的id呈增加趋势，因此可以计算ID号。例如，在订单ID生成场景中，公司每天的订单数量可以通过减去订单ID号来粗略计算，这是不可容忍的。

树叶-雪花图

Leaf-snowflake方案完全沿用了雪花方案的bit设计，并为workerID的分配引入了Zookeeper的持久顺序节点的特性，自动为雪花节点配置wokerID。避免了业务规模较大时人工配置成本过高的问题。

叶子雪花按照以下步骤启动：

启动Leaf-snowflake服务，连接Zookeeper，检查自己是否在leaf_forever的父节点下注册过(是否有这个顺序的子节点)。如果您已经注册了直接检索您的worker ID(由ZK序列节点生成的int类型ID号)，请启动该服务。如果没有，在父节点下创建一个持久的顺序节点。成功创建后，检索序列号作为您的workerID号，并启动服务。为了减少对Zookeeper的依赖，在本地文件系统中缓存了一个workerID文件。ZooKeeper出现问题的时候，正好是机器出现问题需要重启的时候，可以保证服务正常启动。

上面已经解释过了，所有雪花类算法都存在时钟回调的问题。Leaf-snowflake通过检查自身系统时间与leaf_forever/${self}节点记录时间进行比较，然后启动闹铃，解决了时钟回调问题。

美团官方的建议是，由于对时钟的强依赖性，对时间的要求比较敏感。机器工作时，NTP同步也会造成二级回退。建议可以直接关闭NTP同步。要么在时钟回调时不提供服务直接返回ERROR_CODE，等待时钟追上来。或者做一层重试，然后上报报警系统，或者找到时钟回拨后自动移除自己的节点报警。

根据官方提供的关于性能的数据，目前Leaf的性能可以通过QPS在4C8G机器上测到接近5w/s，TP999 1ms。

上面的总结基本上列出了所有常用的分布式ID生成方法。其实粗略分类，可以分为两类：

一种是类DB，通过设置不同的起始值和步长实现趋势增量，需要考虑服务的容错性和可用性。

另一种是雪花型，将64位分成不同的段，每段代表不同的含义，基本是时间戳，机ID，序列号。这个方案就是考虑时钟回调，做一些缓冲设计提高性能。

而且通过将三者(时间戳、机ID、序列号)分成不同的位数，可以改变使用寿命和并发性。

比如对并发性要求不高，长期使用的应用，可以增加stamp位数时间，减少序列位数。例如，当配置为{'worker bits' 23，' time bits' 31，' seq bits' 9}时，可以支持28个节点以14400 UID/s的总并发速度连续运行。

对于节点重启频繁、长期使用的应用，可以增加工作机位数和时间 stamp位数，减少串行位数。例如，当它配置为{'worker bits' 27，' time bits' 30，' seq bits' 6}时，它可以支持37个节点连续运行，整体并发为2400 UID/s。

关注我：私信回复“555”获取Dubbo、Redis、Netty、zookeeper、Spring cloud、分布式、高并发等架构技术的往期Java高级架构资料、源代码、笔记、视频、往期架构视频。