针对高并发写，分布式ID是其业务基础，本文从一个面试题细细展开。

面试官：

1.对于Mysql的InnoDB引擎下，自增ID和UUID作为主键各自有什么优劣，对于一张表的主键你建议使用哪种ID？

2.除了UUID是否还了解其他类型的唯一ID？

对于这两个问题，我们需要深入了解的知识有两个：

1.mysql的innodb引擎的数据组织结构是什么样的

2.分布式ID都有几种各自的优劣是什么

还有这里要关注一点，为什么强调了InnoDB 引擎，还有什么引擎（MyISAM这个后续再说）？

Mysql-InnoDB 引擎

通常InnoDB为mysq的默认引擎，此引擎也是我们最熟识的B+树作为我们数据的基础组织结构，B+树作为一个“矮胖子”，通过4层高度就能组织千万数据，极大的减少了磁盘IO次数提升了数据访问效率，这也是它可以作为大多数公司数据持久化基石的原因。

（此图非原创-侵删）

对于此B+树结构，数据库的数据新增，顺序新增还是随机新增对于它的执行效率有很大影响，如果新增数据是随机的，那可能增加大量的IO，因为每次新增都可能页分裂与页合并，涉及数据挪移，而对于顺序新增，每次都会在页尾进行操作，这大大减小了磁盘IO，因此对于一个业务主键，它应该是单调递增的，这样可以大大提升数据插入效率。

自增ID和UUID作为主键对比

其实这个问题，面试官最主要就是要考察的UUID对于mysql 随机写入的影响，当然其他的了解越多越好。

特点对比	自增ID	UUID（v4）
实现方式	数据库支持	工具包支持
生成速率限制	取决于数据库的TPS，比较低	无上限
写入效率*	顺序写入，性能很高	随机写入导致数据写入性能急剧下降
查询效率	数字查询效率更高（数字比较）	36位字符（32+4个‘-’）比较效率稍低
存储空间	BigInt 8字节	Varchar(36) 1字节前缀+36字节=37字节
业务量推测	根据id相减可推测业务量	随机无法推测

其实可以看出，这两种方案都会存在一个致命性问题，自增id强依赖数据库且生成效率低，UUID对于写入效率又有很大问题。针对上面分析其实我们需要的分布式id 需要具有以下特性：全局唯一、单调递增、高效生成。很多大家熟悉的方案都是针对上面两种方案的优化产生，整理目前的解决方案如下：

分布式ID-Snowflake

先说说名字（个人猜测）之所以取雪花这个名字，是威尔逊·奥尔温·宾利（Wilson Bentley）他通过显微镜和显微摄影技术拍摄了5382张雪花照片，证实了雪花形态的独特性，因此产生观点“世界上没有两片完全相同的雪花”，美团的leaf名字异曲同工。

直接上图吧，原始snowflake 和mongo的objectId 原理相似。

而经典的雪花算法和类雪花算法，由于整体ID的组成使用了时间戳，所以都会存在一个重要的bug情况“时钟回拨”。

时钟回拨：是指一台机器的操作系统时钟，突然跳变到了一个比当前系统记录的时间更早的时刻。

一旦产生时钟回拨就可能产生致命的问题，分布式ID不能保证全局唯一，这样会对业务造成严重影响。

产生时钟回拨的原因：

NTP时间同步：一般毫秒级别回拨，当 NTP 客户端发现自己的本地时钟比时间服务器快时，为了逐步纠正这个误差，它可能会选择逐步减慢时钟（斯步进，slewing），但在某些配置或差异过大时，NTP 服务可能会认为时钟发生了严重故障，从而采取直接跳转（步进，stepping）的方式，将系统时间瞬间调回正确时间。硬件时钟（RTC）问题：回拨时间很严重，这个由CMOS电池供电（想不到吧），如果电池没电了会重置一个比较早的时间例如1970-01-01，如果这系统重启了，系统会先读取RTC时间，再NTP同步时间，在NTP同步之前时钟都是错误的。

虚拟化环境：挂起后恢复，需要同步宿主机时间。

人为误操作: 看修改情况了，谁脑子抽筋取修改系统时间或时区。

分布式ID-美团Leaf-Snowflake

美团leaf的雪花模式，针对于雪花算法做了两处优化：

1.workerId 不手动分配使用zookeeper（弱依赖）获取。

2.解决时钟回拨问题（所有以雪花模式生成分布式ID都会去解决时钟回拨）。

workerId 分配原理

对于workerId，当系统节点数过多的时候，很难手动维护，因此选择启动时通过zookeeper加载，在加载后会本地持久化一个workerId，当zooKeeper挂了了时则采用本地数据，提升SLA。

如何解决时钟回拨问题

1.启动时时间校准

如果启动时校验失败，则此机器启动失败，不接入发号集群。

（1）连接zookeeper

（2）判断是否节点已存在（Ip:port）本机时间>存在节点以前上报的时间

（3）存在则直接返回，不存在则新建

（4）获取leaf_temporary下所有其他机器ip：port

（5）RPC 请求所有其他机器的时间abs( 本机时间-sum(time)/nodeSize ) < 阈值，如果大于预置则直接失败

（6）成功后3s定时上报当前机器时间

2.发号过程等待或失败

做一层自旋等待重试，然后上报报警系统，自动摘除或者人工接收报警处理。

总结：美团leaf的雪花算法通过检测两个方面保证生成分布式ID单调递增，1.在启动时依赖zookeeper存储数据校验，失败则不允许加入集群，2.在每次发号时比较上次发号时间，小于5ms 则等待10ms再次校验，失败则报警或自动摘除。

分布式ID-百度uid-generator

百度主要实现了两种generator：

DefaultUidGenerator

雪花算法（以秒位单位）+时钟回拨报异常(没有自旋等待)

sign(1bit)
固定1bit符号标识，即生成的UID为正数。
delta seconds (28 bits)
当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年
worker id (22 bits)
机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。
sequence (13 bits)
每秒下的并发序列，13 bits可支持每秒8192个并发。

CachedUidGenerator

解决时钟回拨：

它不是每次实时获取当前时间而是只启动加载一次，之后通过原子自增实现；

那如果启动加载的时间有问题就是老时间呢，它通过每次重启的自增ID解决。

所以此方案通过自增的workerID +原子自增时间戳解决了时钟回拨问题。

数据填充时机：

通过异步预生成uid环，提升整体tps性能。

初始化预填充：RingBuffer初始化时，预先填充满整个RingBuffer。

即时填充：Take消费时，即时检查剩余可用slot量(tail - cursor)，如小于设定阈值，则补全空闲slots。阈值可通过paddingFactor来进行配置，请参考Quick Start中CachedUidGenerator配置。

周期填充：通过Schedule线程，定时补全空闲slots。可通过scheduleInterval配置，以应用定时填充功能，并指定Schedule时间间隔。

总结：百度CachedUidGenerator 通过于每次启动自增workerID和原子自增时间戳解决了时钟回拨问题；采用离线预生成的方案提升了整体生成的性能。

分布式ID-snowflake小结

主流的基于snowflake的从原理到实现与优化基本介绍完成，简单做下小结。

方案	依赖	峰值TPS	优化方案
原生snowflake	无	409.6w	无，存在时钟回拨问题
美团leaf-snowflake	zookeeper	409.6w	自动化workerID分配，自旋等待时钟，回拨则报错
百度uid-generator	mysql	600w+	自动化workerId分配，解决时钟回拨问题，缓存环提升了生成性能