《亿级流量Java高并发与网络编程实战》

2.5 分布式lD生成器

本章的最后，再详细介绍一个分布式系统必然要面对的技术—分布式ID生成器，作为本书实战性案例的开端。

在分布式系统中，如何在各个不同的服务器上产生ID值？例如，有一个订单系统被部署在了A、B两个节点上（即两台计算机上），那么如何在这两个节点上各自生成订单ID，并且保证ID值不会冲突？

通常有以下3种解决方案。

① 使用数据库的自增特性（或Oracle中的序列），不同节点直接使用相同数据库的自增ID值。

② 使用UUID算法产生ID值。

③ 使用SnowFlake算法产生ID值。

由于Java提供了对UUID的支持，可以直接通过UUID.randomUUID()获取到UUID值。因此本节主要介绍SnowFlake算法。

SnowFlake算法被称为雪花算法，是由Twitter提出的一种生成ID的算法，该算法会生成一个64bit的整数，但实际只使用63bit，共可以表示263个ID值。如果用十进制表示，就是9223372036854775808个ID值。

SnowFlake的组成结构如图2—16所示。

图2—16 SnowFlake的ID结构

SnowFlake算法生成的ID是64位的，而Java中long类型也是64位的，因此可以用long来存储ID值。

41位时间戳：表示某一时刻的时间戳（时间戳：假设设置的起始时间是2018-01-01T00：00：00.000，那么该起始时间到某一时刻所经过的毫秒数，就称为“某一时刻的时间戳”）。41位时间戳可以表示2 ⁴¹ 个数字，如果用每一个数字表示1ms的时间，那么41位的时间戳可以表示69年的时间[2 ⁴¹ /(1000*60*60*24*365)=69]。因此，如果以2018-01-01T00：00：00.000作为起始时间，41位随机数可以表示2018—2087这69年间的任一时刻（精确到ms）。

10位机器码：可以将机器的MAC地址或IP地址等唯一标识符转换成的10位二进制数字，也可以将10位机器码拆分成“5位地理位置+5位机器编号”的形式。总之，就是想通过10位与节点有关的物理信息（或各种标识信息），对不同节点生成不同ID值。

12位序列号：0、1、2、3…12位递增数字的二进制表示形式。

SnowFlake算法采用“41位时间戳+10位机器码+12位序列号”的大致思想是，当多个节点需要生成多个ID值时，先判断这些节点是否是在同一时刻（精确到ms）生成的ID。如果不是，可以直接根据41位时间戳区分出ID值；如果是在同一时刻生成的，就再根据“10位机器码和12位序列号”区分ID值。

Twitter在GitHub上给出了SnowFlake算法的Scala源码，以下是翻译过来的Java版代码（本算法中，将10位机器码看作“5位datacenterId + 5位workerId”）。

【 源码： demo/ch02/SnowFlake.java】

Twitter在GitHub上给出了SnowFlake算法的Scala源码，笔者也将其翻译成了对应的Java版源码，读者可以在本书赠送的配套资源中查看。