一、什么情况下需要全局唯一ID
在一个由多个服务器组成的业务系统中，有很多对象都需要一个ID来标识该对象，以示区分。这个ID应该是系统(全局)范围内唯一的，这种ID就是全局唯一ID(GUID，Globally Unique Identifier)。比如：购物商城中的用户ID和订单ID就应该是全局唯一ID。
二、生成全局唯一ID要求
既然要使用全局唯一ID，那么就需要先生成全局唯一ID。生成时主要考虑以下面几点：
全系统范围内唯一。显而易见，全局唯一ID肯定应该是全系统唯一不重复的。ID易于存储和比较。全局唯一ID的占用空间应该尽量的小且便于比较。比如：类型为64位整形(int64)的全局唯一ID就明显比类型为字符串(string)的全局唯一ID更易于存储和比较，使用起来也更好用。生成结果是有序递增(递减)的。一般会将生成后的全局唯一ID作为数据库的主键来存储该对象的信息。有序的主键在插入数据库时性能一般会更好。生成结果不可预测。生成的结果应当是不能预测的。如果能够预测出下一个生成结果，基本上就能猜测出所有的生成结果，比如在一个订单系统中，就能获取到所有的订单信息，这在安全性上是难以接受的。生成快速且稳定。在一个系统中，很有可能需要频繁的生成全局唯一ID，一旦生成的速度过慢甚至生成时卡顿，将导致整个系统的卡顿或者崩溃。所以，全局唯一ID的生成应当是快速且稳定的。
三、目前成熟的生成方法
1. 数据库自增ID
很多数据库提供生成自增ID的功能，如MySQL提供了变量auto_increment_offset来设置自增的初始值，变量auto_increment_increment设置每次自增的步长。借助数据库提供的这个功能，我们就能简单的实现生成全局唯一ID的功能了。
这种方式的优点很明显，那就是简单。不需要开发一个单独的系统，也不需要专人去维护。
但是缺点也是很明显的：
生成性能不够好。每次生成全局唯一ID都需要通过网络访问数据库一次，生成时间可能达到几十上百毫秒。而且在数据库内部生成自增ID时，常常还会加锁，多个地方同时生成全局唯一ID时，还需要竞争抢锁。并发性能也就不好。稳定性不够好。使用数据库来生成全局唯一ID方法的特点就是所有需要生成全局唯一ID的业务都需要连接相同的数据库，压力集中于一点。一旦数据库崩溃，将不能生成全局唯一ID，这会严重影响使用全局唯一ID的业务系统。即使数据库采用了主从结构，也难以保证在主从数据库切换时，生成的全局唯一ID不重复。生成结果可以预测。一旦确定了自增初始值和自增步长后，基本上不会再动态修改这两个值，那么根据这两个值生成出来的ID也就是可预测的了。
虽然使用数据库来生成全局唯一ID有上面的种种缺点，但是可以通过一些方法来改善这些问题：
A. Flickr的分布式唯一主键生成算法
针对使用数据库生成全局唯一ID性能不好的问题，Flickr提供了这样的解决方案：
部署多台数据库，每台数据库设置不同的自增初始值，相同的自增步长值。同时自增步长值必须大于等于数据库的数量。这样就能保证每台数据都能生成
全局唯一ID，且所有生成的全局唯一ID都不重复。
举例，比如部署了两台数据库，其自增初始值，自增步长值及结果分别如下：
| 数据库 | 自增初始值 | 自增步长值 | 生成结果 |
|---|---|---|---|
| 数据库A | 0 | 2 | 0,2,4,6,8… |
| 数据库B | 1 | 2 | 1,3,5,7,9… |
实际使用此方案时生成的全局唯一ID可能不是上面这种连续的结果，MySQL的下个自增ID的实际计算公式是INT(current_value / increment) x increment + offset，具体的可以参考MySql Master-Master Replication Causing Missing AutoIncrement Values。
Flickr分布式唯一主键生成算法的核心思想是：
分散单点数据库的压力到了多点数据库，从而在提升了生成的性能和稳定性。
但是这种方法中有一个很大的弊端，那就是因为要提前的确定自增的步长，所以扩展性很差。
B. 美团的Leaf-segment算法
同样是针对使用数据库生成全局唯一ID性能不好的问题，美团提供的解决方案是：
不同的业务使用不同的自增ID。同一个业务一次获取多个
全局唯一ID，缓存起来慢慢使用。同时在要用完时前就再次异步获取新的全局唯一ID缓存起来备用，就能为业务提供持续不断的全局唯一ID生成功能。
举例，系统中有用户和订单都需要使用全局唯一ID来标识。那么数据库中就分别为用户和订单使用不同的自增ID。每次获取10000个全局唯一ID。并规定当前消耗10%的全局唯一ID就马上异步的获取下一批并将结果缓存起来备用。
| 自增ID | 自增初始值 | 自增步长值 | 生成结果 |
|---|---|---|---|
| 用户 | 0 | 10000 | 0,10000,20000… |
| 订单 | 0 | 10000 | 0,10000,20000… |
美团Leaf-segment算法的核心思想是：批量获取和提前缓存。
- 批量获取的同时，也减少请求数据库的次数，也就降低了数据库的压力。
- 而提前缓存则是保证了即使在网络波动时和业务高峰时都能够持续不阻塞的生成
全局唯一ID。
2. UUID算法
UUID的全称是Universally Unique Identifier，中文名为通用唯一识别码。
UUID包含32个16进制的数字，大小是16字节128为，一般以连字号分为五段，形式为8-4-4-4-12的36个字符，比如：12fae663-e3dd-4b9e-b1a9-b7e598d2f853。具体的细节可以参考UUID的IETF标准A Universally Unique IDentifier (UUID) URN Namespace。
UUID生成的算法主要有5种，都不需要联网，本地即可生成。所以，使用UUID算法生成全局唯一ID的优点是很明显的，那就是：高性能且难于预测结果。但是缺点也很明显：
UUID不易存储和使用。目前的主流编程语言和数据库，最大支持64位的整数。128位的UUID难以原生的以整数方式存储和使用。UUID不是有序递增(递减)的。UUID算法生成出来的ID一般不是有序的，这对将UUID作为主键存入数据库的使用方式来说并不友好。
基于上面的缺点，UUID很少作为全局唯一ID来使用。
3. 字节(位)分段算法
这种算法的思想其实来自Twitter的雪花算法，其他的同类算法都是在此基础上的一些变种。算法核心是：
将组成
全局唯一ID的多个字节看做一个整体，并其划分成不同的段，分别控制不同段的值。
该算法具有与UUID算法相同的好处，那就是都不需要联网，本地即可生成。除此之外，还支持多个服务器同时生成，且生成的结果总体的保持递增或递减。在控制字节大小的情况下，也能较好的存储和比较。
A. Twitter的雪花算法
该算法生成的全局唯一ID的大小为64字节，能够使用64位整型来存储。其格式为：
+------------------------------------------------------------------------------------+
| UNUSED(1BIT) | TIMESTAMP(41BIT) | MACHINE-ID(10BIT) | SERIAL-NO(12BIT) |
+------------------------------------------------------------------------------------+其中：
1位不用。最高位不用，固定为0。因为二进制中最高位为1的表示是负数，而我们一般整数来表示ID，不希望有负数的ID，所以不用。41位的时间戳。用41位的空间来表示单位为毫秒的时间戳，大约可以表示(1L << 41) /（1000 * 60 * 60 * 24 * 365）= 69年的时间。10位的机器位。用来区分不同服务器生成出来的ID。10位空间最多可以表示(1L << 10) = 1024台服务器。12位的序列化。用12位空间来存储在同一毫秒内，同一台服务器生成出来的ID数量。最多可以存储(1L << 12) = 4096个。
使用Twitter的雪花算法只有一个明显的缺点，就是：
算法高度依赖时间戳，如果各个生成ID的服务器时间不同步，将会导致生成出来的ID是乱序或者重复的。
B. 百度的UidGenerator算法
百度UidGenerator算法与Twitter雪花算法的主要区别在于调整了各个分段的大小，改变了各个分度的意义，本质没变。
+-------------------------------------------------------------------------------------+
| UNUSED(1BIT) | DELTA SECONDS(28BIT) | WORKER-NODE-ID(22BIT) | SERIAL-NO(13BIT) |
+-------------------------------------------------------------------------------------+1位不用。最高位依旧不用，固定为0。28位的时间差。表示当前时间相对与”2016-05-20”的差值，单位为秒。最多可支持约8.7年。22位的机器位。表示机器ID。每次机器重启后都废弃重新从数据库申请，最多可支持约420w次机器启动。13位的序列化。每秒下的并发序列，可支持每秒8192个并发。
C. 美团的Leaf-snowflake算法
美团Leaf-snowflake算法沿用了Twitter雪花算法各个字段的意义，但是扩展了算法的使用方式，提高了算法的易用性和在时钟乱序时的容错性。
提升算法的易用性
在生成全局唯一ID的服务器集群中加入了Zookeeper。每次服务器启动时都去ZooKeeper读取(不存在时则注册)自己的用于生成全局唯一ID时的服务器ID值。因为服务器ID一般不会变，所以可以将这个值缓存起来，即使以后遇到连接ZooKeeper时，也能正常的启动服务器，并提供生成ID的服务。
提升时钟乱序时的容错性
服务器会在启动时判断时钟发生是否发生了回拨，具体细节如下：
- 如果服务器启动时，Zookeeper无此服务器的时间记录，那么就判断当前服务器的时间和其他的运行Leaf-snowflake算法服务器的时间的平均值(通过RPC获取)之间的差值，如果差值大于某个阈值，认为本机系统时间发生大步长偏移，启动失败并报警。
- 如果服务器启动时，Zookeeper已经有此服务器的时间记录，且当前服务器的时间小于记录的时间，那么就认为服务器时间发生了大步长回拨，服务启动失败并报警。
- 服务器正常启动后，定时(如每隔3秒)的向Zookeeper记录本服务器当前时间。
