分布式系统中全局唯一ID生成的必要性及业务系统对ID号的要求详解
背景
在复杂的分布式系统里，通常需要对数量众多的数据和消息进行独特的标识。像在美团点评的金融产品系统、支付产品系统、餐饮产品系统、酒店产品系统以及猫眼电影产品系统中，数据在不断地增长，当对数据进行分库分表处理之后，就需要有一个独一无二的 ID 来标识一条数据或者一条消息，而数据库的自增 ID 明显无法满足这种需求；更为特别的是，订单、骑手、优惠券等也都需要有唯一的 ID 来作为标识。此时非常有必要有一个能够生成全局唯一 ID 的系统。概括而言，业务系统对 ID 号有哪些要求呢？
全局具有唯一性，不能出现重复的 ID 号，因为它是唯一标识，所以这是最基本的要求。在趋势方面是递增的，在 MySQL InnoDB 引擎中使用的是聚集索引，多数 RDBMS 是用 B-tree 的数据结构来存储索引数据的，在主键的选择上我们应尽量使用有序的主键以保证写入性能。单调递增：要确保下一个 ID 必定大于上一个 ID，像事务版本号、IM 增量消息以及排序等这类特殊需求就是如此。信息安全方面：倘若 ID 是连续的，那么恶意用户进行扒取工作就会变得极为容易，只需按照顺序下载指定的 URL 就行；要是 ID 为订单号的话，那就更加危险了，竞争对手能够直接知晓我们一天的订单量。因此，在某些应用场景中，就需要 ID 没有规则、不规则。
上述 123 分别对应着三类不同的场景，3 的需求与 4 的需求是互斥的，不能够用同一个方案来满足。
同时，除了对 ID 号码本身有要求之外，业务对 ID 号生成系统的可用性要求也极高。试想一下，如果 ID 生成系统出现瘫痪情况，那么整个美团点评的支付、优惠券发券以及骑手派单等关键动作都将无法执行，这必然会带来一场灾难。
由此总结下一个ID生成系统应该做到如下几点：
平均延迟需尽可能低，TP999 延迟也需尽可能低；要达到可用性 5 个 9 的标准；要有高 QPS；下面介绍常见的 UUID 方法。
UUID 的标准型式包含 32 个 16 进制数字，被连字号分成五段，形式是 8 - 4 - 4 - 4 - 12 共 36 个字符，例如：550e8400 - e29b - 41d4 - a716 - 446655440000。到目前为止，业界生成 UUID 一共有 5 种方式，详情可查看 IETF 发布的 UUID 规范 A Universally Unique IDentifier (UUID) URN Namespace。
优点：
缺点：
对于 MySQL 索引而言存在不利之处：若将其作为数据库主键，在 InnoDB 引擎的环境下，UUID 所具有的无序性有可能导致数据位置频繁地发生变动，进而对性能产生极为严重的影响。
类snowflake方案
这种方案大致而言是一种通过划分命名空间（其中 UUID 也包含在内，因其较为常见，所以单独进行分析）来生成 ID 的算法。此方案将 64 - bit 划分成多个区段，分别用于标识机器、时间等。例如，在 snowflake 中，64 - bit 分别按照如下方式表示（图片来自网络）：
41 位的时间能够表示“世界上没有两片相同的树叶”。
综合对上述几种方案进行对比，每种方案都无法完全契合我们的要求。因此，Leaf 针对上述的第二种方案和第三种方案分别进行了相应的优化，从而实现了 Leaf-segment 方案和 Leaf-snowflake 方案。
Leaf-segment数据库方案
第一种 Leaf-segment 方案，在数据库使用方面做了如下改变：原方案每次获取 ID 都需读写一次数据库，这导致数据库压力较大。现改为利用 proxy server 进行批量获取，每次获取一个 segment（由 step 决定大小）的号段值。使用完毕后再去数据库获取新的号段，这样能大大减轻数据库的压力。各个业务的发号需求各不相同，用 biz_tag 字段来进行区分。每个 biz-tag 的 ID 获取是相互隔离的，彼此之间不会产生影响。倘若之后有性能方面的需求，需要对数据库进行扩容，那么不需要进行上述那种复杂的扩容操作，只需对 biz_tag 进行分库分表就可以了。
数据库表设计如下：
请提供需要改写的句子呀，你没有给出具体的内容呢。
该表格包含“Field”“Type”“Null”“Key”“Default”“Extra”这些字段。“Field”用于表示字段名称；“Type”用于表示字段类型；“Null”用于表示该字段是否可以为空；“Key”用于表示该字段是否为关键字；“Default”用于表示该字段的默认值；“Extra”用于表示该字段的其他信息。
+-------------+--------------+------+-----+-------------------+-----------------------------+
biz_tag 是 varchar(128)类型的，它不允许为空（NO），是主键（PRI），没有其他具体的说明内容，也没有其他相关的信息。
max_id 是一个 bigint(20) 类型的字段，它的属性为 NO，没有其他特殊设置，其值为 1 ，没有其他相关内容。
这一行数据中，“step”这一列的数据类型是 int(11)，“NO”列的值为 NO，其他列没有数据，为空值 NULL 。
desc 是 varchar(256)类型，它是 YES 的，其他为空，值为 NULL ，没有其他特殊情况。
update_time 对应的时间戳为 timestamp ，NO 为特定标识，当前时间为 CURRENT_TIMESTAMP ，在更新时也为 CURRENT_TIMESTAMP 。
+-------------+--------------+------+-----+-------------------+-----------------------------+
biz_tag 用于区分业务，max_id 指该 biz_tag 目前所被分配的 ID 号段的最大值，step 表示每次分配的号段长度。原先获取 ID 每次都需写数据库，现在只需将 step 设置得足够大，例如 1000。仅当 1000 个号被消耗完后，才会重新读写一次数据库。读写数据库的频率由 1 降低到了 1/step，其大致架构呈现如下情况：
test_tag 在第一台 Leaf 机器上的号段是 1 到 1000 。当此号段用完后，会加载另一个长度为 step = 1000 的号段。假设另外两台号段未更新，那么此时第一台机器新加载的号段应为 3001 到 4000 。数据库对应的 biz_tag 这条数据的 max_id 会被更新，从 3000 更新为 4000，更新号段的 SQL 语句如下：
Begin
将表中的 max_id 更新为 max_id 加上 step，条件是 biz_tag 等于 xxx
从表中选择标签、最大 ID 和步骤，条件是业务标签等于 xxx 。
Commit
这种模式有以下优缺点：
优点：
缺点：
双buffer优化
对于第二个缺点，Leaf-segment 进行了一些优化。具体而言：
Leaf 取号段的时机是在号段被消耗完的时候。这意味着号段临界点的 ID 下发时间取决于下一次从 DB 取回号段的时间。在这期间，进来的请求会因为 DB 号段没有取回来而导致线程阻塞。如果网络和 DB 的性能稳定，这种情况对系统的影响不大。然而，假如在取 DB 时网络出现抖动，或者 DB 发生慢查询，就会致使整个系统的响应时间变慢。
为此，我们希望 DB 取号段的过程是无阻塞的，在取号段时不会阻塞请求线程。也就是说，当号段消费到某个点时，能异步地将下一个号段加载到内存中，而不是要等到号段用尽才去更新号段。这样做能够在很大程度上降低系统的 TP999 指标。详细实现如下图所示：
Leaf 服务内部有两个号段缓存区 segment，采用双 buffer 的方式。当当前号段已下发 10%时，如果下一个号段未更新，就另启一个更新线程去更新下一个号段。在当前号段全部下发完后，如果下个号段准备好了，就切换到下个号段作为当前 segment 接着下发，如此循环往复。
Leaf高可用容灾
对于第三点“DB 可用性”的问题，我们当下采取一主两从的举措。并且进行了分机房的部署。Master 与 Slave 之间是以半同步的方式来同步数据的，此方式在[5]中有提及。同时，我们运用公司的 Atlas 数据库中间件，该中间件已开源且改名为 DBProxy，以此来进行主从切换的操作。这种方案在某些情况下会退化为异步模式，在非常极端的情况下甚至会导致数据不一致，不过出现的概率极小。倘若你的系统需保证 100%的数据强一致，便可选择采用“类 Paxos 算法”实现的强一致 MySQL 方案，像 MySQL 5.7 前段时间刚正式发布的 MySQL Group Replication 就可以。但是运维成本和精力都会相应的增加，根据实际情况选型即可。
Leaf 服务进行了 IDC 部署，其内部的服务化框架是“MTthrift RPC”。在进行服务调用时，依据负载均衡算法，会优先调用同一机房的 Leaf 服务。只有在该 IDC 内的 Leaf 服务不可用的情况下，才会选择其他机房的 Leaf 服务。服务治理平台 OCTO 提供了对服务的多种保护措施，包括过载保护、一键截流以及动态流量分配等。
Leaf-snowflake方案
Leaf-segment 方案能够生成趋势递增的 ID，并且 ID 号是可以计算的。然而，它不适用于订单 ID 生成场景。例如，竞对在两天中午 12 点分别下单，通过订单 ID 号相减就可以大致计算出公司一天的订单量，这种情况是不能被接受的。面对这个问题，我们提供了 Leaf-snowflake 方案。
Leaf-snowflake 方案依照 snowflake 方案的 bit 位设计，是以“1+41+10+12”的方式来组装 ID 号。在 workerID 的分配方面，倘若服务集群的数量比较少，是完全能够进行手动配置的。而 Leaf 服务的规模较大时，通过手动配置的成本会非常高。所以利用 Zookeeper 持久顺序节点的特性来自动为 snowflake 节点配置 workerID。Leaf-snowflake 的启动按照以下几个步骤进行：
启动 Leaf-snowflake 服务，接着连接 Zookeeper。然后在 leaf_forever 父节点下，检查自身是否已经注册过，也就是查看是否存在该顺序子节点。倘若已经注册过，就直接取回自己的 workerID（zk 顺序节点生成的 int 类型 ID 号），随后启动服务。如果未曾注册过，就在那个父节点的下方构建一个持久顺序节点。构建完成并取得成功后，获取该顺序号，并将其当作自身的 workerID 号。接着启动服务。
弱依赖ZooKeeper
每次会去 ZK 拿数据，同时也会在本机文件系统上缓存一个 workerID 文件。当 ZooKeeper 出现问题，并且机器恰好出现问题需要重启时，能够保证服务可以正常启动。通过这样的方式做到了对三方组件的弱依赖，在一定程度上提高了 SLA。
解决时钟问题
这种方案依赖时间。如果机器的时钟发生回拨，就有可能生成重复的 ID 号。所以需要解决时钟回退的问题。
查看上图中的整个启动流程图，在服务启动的时候，第一步要检查自身是否已经写过 ZooKeeper leaf_forever 节点。
若曾写过，就将自身系统时间与 leaf_forever/${self}节点的记录时间进行比较。如果自身系统时间小于 leaf_forever/${self}时间，那么就认为机器时间出现了大步长回拨。在此情况下，服务启动会失败并且会发出报警。若未曾写过，那就证明是新的服务节点。直接创建持久节点 leaf_forever/${self}，并将自身系统时间写入其中。接着，综合对比其余 Leaf 节点的系统时间，以判断自身系统时间是否准确。具体做法为：获取 leaf_temporary 下的所有临时节点（即所有运行中的 Leaf-snowflake 节点）的服务 IP：Port，然后通过 RPC 请求获取所有节点的系统时间，再计算 sum(time)/nodeSize。如果系统时间减去总和（时间）除以节点大小的绝对值< 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点leaf_temporary/${self} 维持租约。否则认为本机系统时间发生大步长偏移，启动失败并报警。每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}。
因为对时钟有很强的依赖性，对时间要求较为敏感，机器工作时 NTP 同步会导致秒级别的回退，所以建议直接关闭 NTP 同步。要么在时钟回拨时不提供服务直接返回 ERROR_CODE，等时钟追上就行。或者设置一层重试，接着上报报警系统。更或者是在发现时钟回拨后自动摘除自身节点并报警，具体如下：
//发生了回拨，此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
//时间偏差大小小于5ms，则等待两倍时间
wait(offset << 1);//wait
timestamp = timeGen();
if (timestamp < lastTimestamp) {
//还是小于，抛异常并上报
throwClockBackwardsEx(timestamp);
}
} catch (InterruptedException e) {
throw e;
}
} else {
//throw
throwClockBackwardsEx(timestamp);
}
}
//分配ID
从上线情况来看，2017 年闰秒出现时，部分机器曾出现回拨情况。由于 Leaf-snowflake 的策略予以保证，所以成功避免了对业务造成的影响。
Leaf现状
Leaf 在美团点评公司内部为众多业务线提供服务，这些业务线涵盖金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等。目前，Leaf 在 4C8G 的机器上进行压测，其性能 QPS 能达到近 5 万/s，TP999 为 1ms，已经能够满足大部分业务的需求。每天的调用量达到亿数量级，它是公司内部的公共基础技术设施。必须确保能提供高 SLA 和高性能的服务。目前我们仅仅达到了及格线，还有许多提升的空间。
作者简介
照东是美团点评基础架构团队的成员，他主要参与了美团大型分布式链路跟踪系统 Mtrace 以及美团点评分布式 ID 生成系统 Leaf 的开发工作。他之前曾在阿里巴巴就职，于 2016 年 7 月加入美团。
招聘：若你对在大规模分布式环境下的服务治理以及分布式会话链追踪等系统怀有兴趣，我们诚挚地欢迎你投递简历至 zhangjinlu#meituan.com。
参考资料为施瓦茨所著的《高性能 MySQL》，该书由电子工业出版社出版，出版年份为 2010 年，其内容在 162 至 171 页。维基百科提到了 UUID 和 snowflake。MySQL 有集群索引和二级索引。还有半同步复制（Semisynchronous Replication）。
phper