1. 需求分析
在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在电商、金融、支付等系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID不能满足需求，此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？
全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道系统一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。
上述123对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。
同时除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高，想象一下，如果ID生成系统瘫痪，整个业务系统都无法执行。
由此总结下一个ID生成系统应该做到如下几点：
平均延迟和TP999延迟都要尽可能低；
可用性5个9；
高QPS。
2. 为什么数据库自增ID无法满足需求
如果是数据库的自增ID的话，那么ID自增是在单库单表之中的，如果做了分库分表之后要使用全局的自增ID，就需要创建全局唯一的Sequence表(类似Hive MetaStore之中的sequence_table表)来表示全局自增的ID值。
性能问题
此时每个分数据库中需要插入数据，都得先竞争请求Sequence表来确定下一个自增ID，而且请求更新时一定是要加锁的
可靠性问题
全局的sequence table是单点的，存在单点可靠性问题。即使做了主从也是有百毫秒同步的时间延迟。同时切换也是需要时间的。
同时这个问题也是为什么Mongodb作为分布式数据库使用自增ID是不合适的原因，可以参考Mongodb自增ID不好
3. UUID
UUID的信息参考：UUID
简单的来讲就是UUID长度是128byte，也就是32个16进制数，至于切分通常形式为xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)。
优点
性能非常高：本地生成，没有网络消耗。
缺点
不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。
信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用：
MySQL官方有明确的建议主键要尽量越短越好，36个字符长度的UUID不符合要求。
对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，使用的是聚簇索引，UUID的无序性会引起数据位置频繁变动，严重影响性能。
4. 多台Mysql服务器
既然MySQL可以产生自增ID，那么用多台MySQL服务器，能否组成一个高性能的分布式发号器呢？
我们可以使用多台Mysql，利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增。同时使用Mysql的replace into特性。sql操作类似如下：
begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
commit;
假设在8台Mysql服务器下，第一台MySQL初始值是1，每次自增8，第二台MySQL初始值是2，每次自增8，依次类推。前面用一个 round-robin load balancer 挡着，每来一个请求，由 round-robin balancer 随机地将请求发给8台MySQL中的任意一个，然后返回一个ID。
这种方案的特点：
实现简单
系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是1,2,3,4,5(步长是1)，这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如14(假设在扩容时间之内第一台不可能发到14)，同时设置步长为2，那么这台机器下发的号码都是14以后的偶数。然后摘掉第一台，把ID值保留为奇数，比如7，然后修改第一台的步长为2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。所以系统水平扩展方案复杂难以实现。
ID没有了单调递增的特性，只能趋势递增，这个缺点对于一般业务需求不是很重要，可以容忍。
数据库压力还是很大，每次获取ID都得读写一次数据库，只能靠堆机器来提高性能。
5. Twitter Snowflake
Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序(方便客户端排序)，并且在分布式系统中不同机器产生的id必须不同。
Snowflake的原理和UUID，Mongodb ObjectId的原理类似都是以划分命名空间来生成ID的一种算法。
Snowflake把时间戳，工作机器id，序列号组合在一起。
41-bit的时间可以表示(1L<<41)/(1000L * 3600 * 24 * 365)=69年的时间，10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求，还可以将10-bit分5-bit给IDC，分5-bit给工作机器。这样就可以表示32个IDC，每个IDC下可以有32台机器，可以根据自身需求定义。12个自增序列号可以表示2^12个ID，理论上snowflake方案的QPS约为409.6w/s，这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。
这种方式的优缺点是：
优点：
毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
可以根据自身业务特性分配bit位，非常灵活。
缺点：
强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
6. 美团Leaf
参考文章：