分布式主键调研

近期要对一个亿级别的表分库分表，一个很重要的环节就是要选定一个分布式主键的生成方式，本文主要总结下对分布式主键调研的结果。

分布式主键生成方式主要分为两大类：中心化、去中心化。

中心化生成算法经典的方案主要有：基于SEQUENCE区间方案、各数据库按特定步长自增和基于redis生成自增序列三种。

淘宝分布式数据层TDDL就是采用SEQUENCE方案实现了分库分表、Master/Salve、动态数据源配置等功能。大致原理是：所有应用服务器去同一个库获取可使用的sequence（乐观锁保证一致性），得到（sequence，sequence+步长]个可被这个数据源使用的id，当应用服务器插入“步长”个数据后，再次去争取新的sequence区间。

• 优势：生成一个全局唯一的连续数字类型主键，延用单库单表时的主键id
• 劣势：无法保证全局递增，需要开发各种数据库类型id生成器，扩容历史数据不好迁移。数据在插入前，无法获得ID，数据在插入后，获取的ID虽然是唯一的，但一定要等到事务提交后，ID才算是有效的。有些双向引用的数据，不得不插入后再做一次更新，比较麻烦

可以继续采用数据库生成自增主键的方式，为每个不同的分库设置不同的初始值，并按步长设置为分片的个数即可，这种方式对分片个数有依赖，一旦再次水平扩展，原有的分布式主键不易迁移。为了预防后续库表扩容，这边可以采用提前约定最大支持的库表数量，后续扩容为2的指数倍扩容。
比如：我们规定最大支持1024张分表，数据库增长的步长为1024（即使现在的表数量只有64）。

• 优势：生成一个全局唯一的数字类型主键，延用单库单表时的主键id。当分表数没有达到约定的1024张分表，全局不连续
• 劣势：无法保证全局递增，也不保证单机连续。需要开发各种数据库类型id生成器。需要依赖一个中心库表sequence

通过redis的原子自增操作(incr接口)生成一个自增的序列。

• 优势：生成一个全局连续递增的数字类型主键
• 劣势：此言七墨种方式新增加了一个外部组件的依赖，一旦Redis不可用，则整个数据库将无法在插入，可用性会大大下降，另外Redis的单点问题也需要解决，部署复杂度较高

去中心化方式无需额外部署，以jar包方式被加载，可扩展性也很好，因此更推荐使用。目前主流的去中心化生成算法有：UUID、Mongo的ObjectId、snowflake算法及其言七墨变种…

UUID是通用唯一识别码（Universally Unique Identifier）的缩写，是一种软件建构的标准，亦为开放软件基金会组织在分布式计算环境领域的一部分。其目的，是让分布式系统中的所有元素，都能有唯一的辨识信息，而不需要通过中央控制端来做辨识信息的指定。UUID有很多变种实现，目前最广泛应用的UUID，是微软公司的全局唯一标识符（GUID）。
UUID是一个由4个连字号(-)将32个字节长的字符串分隔后生成的字符串，总共36个字节长。算法的核心思想是结合机器的网卡、当地时间、一个随机数来生成GUID。从理论上讲，如果一台机器每秒产生10000000个GUID，则可以保证（概率意义上）3240年不重复。

• 优七墨博客势：全局唯一，各种语言都有UUID现成实现，Mysql也有UUID实现
• 劣势：36个字符组成，按照目前Mysql最常用的编码Utf-8，每一个字符对应的索引成本是3字节，也就是一个UUID需要108个字节的索引存储成本，是最大数字类型（8字节）的13.5倍的存储成本

objectid有12个字节，包含时间信息（4字节、秒为单位）、机器标识（3字节）、进程id（2字节）、计数器（3字节，初始值随机）。其中，时间位精度（秒或者毫秒）与序列位数，二者决定了单位时间内，对于同一个进程最多可产生多少唯一的ObjectId，在MongoDB中，那每秒就是2^24（16777216）。但是机器标识与进程id一定要保证是不重复的，否则极大概率上会产生重复的ObjectId。由于ObjectId生成12个字节的16进制表示，无法用现有基础类型存储，只能转化为字符串存储，对应24个字符。objectid的组成结构如下：

• 优势：全局唯一
• 劣势：非数字类型，24个字符，按照目前Mysql最常用的编码Utf-8，每一个字符对应的索引成本是3字节，也就是一个ObjectId需要72个字节的索引存储成本，是最大数字类型（8字节）的9倍的存储成本

Snowflake算法产生是为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。Snowflake算法把时间戳，工作机器id，序列号组合在一起。生成Id的结构如下：

工作机器id可以使用IP+Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件的维护是一个灾难性的事情。

• 优势：在服务器规模不是很大（不超过1024条件）全局唯一 ，单机递增 ，是数字类型，存储索引成本低，ID生成算法完全是一个无状态机，无网络调用，高效可靠
• 劣势：机器规模大于1024无法支持，需要运维配合解决单机部https://qimok.cn署多个同服务进程问题，在大厂里，其实并没有直接使用snowflake，而是进行了改造，因为snowflake算法中最难实践的就是工作机器id，原始的snowflake算法需要人工去为每台机器去指定一个机器id，并配置在某个地方从而让snowflake从此处获取机器id，但是在大厂里，机器是很多的，人力成本太大且容易出错，所以大厂对snowflake进行了改造。

github地址：uid-generator

uid-generator使用的就是snowflake，只是在生产机器id，也叫做workId时有所不同。

uid-generator中的workId是由uid-generator自动生成的，并且考虑到了应用部署在docker上的情况，在uid-generator中用户可以自己去定义workId的生成策略，默认提供的策略是：应用启动时由数据库分配。说的简单一点就是：应用在启动时会往数据库表(uid-genhttps://qimok.cnerator需要新增一个WORKER_NODE表)中去插入一条数据，数据插入成功后返回的该数据对应的自增唯一id就是该机器的workId，而数据由host，port组成。

对于uid-generator中的workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和原始的snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，同一个应用每重启一次就会消费一个workId。

具体可参考https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

• 优势：允许用户覆盖workId位和初始化策略，适合于虚拟化环境，例如docker。通过消耗将来的时间克服了Snowflake算法的并发限制，通过使用RingBuffer缓存UID来并行化UID产生和使用，通过填充消除了来自RingBuffer的CacheLine伪共享，每个实例可以提供超过600万个QPS
• 劣势：需要建 DB 表, 需要有专门的服务来提供获取 id 的接口, 存在网络延迟。

github地址：Leaf

美团的Leaf也是一个分布式ID生成框架。它非常全面，即支持号段模式，也支持snowflake模式。

号段模式：

采用了分发的方式生成ID，即可以在DB之上挂N个Server，每个Server启动时，都会去DB拿固定长度的ID List。这样就做到了完全基于分布式的架构，同时因为ID是由内存分发，所以也可以做到很高效。接下来是数据持久化问题，Leaf每次去DB拿固定长度的ID List，然后把最大的ID持久化下来，也就是并非每个ID都做持久化，仅仅持久化一批ID中最大的那一个。这个方式有点像游戏里的定期存档功能，只不过存档的是未来某个时间下发给用户的ID，这样极大地减轻了DB持久化的压力。

• 优势：ID号码是趋势递增的8byte的64位数字。容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。 可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。
• 劣势：ID号码不够随机，能够泄露发号数量的信息，不太安全。TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。DB宕机会造成整个系统不可用

snowflake模式：

Leaf中的snowflake模式和原始snowflake算法的不同点，也主要在workId的生成，Leaf中workId是基于ZooKeeper的顺序Id来生成的，每个应用在使用Leaf-snowflake时，在启动时都会都在Zookeeper中生成一个顺序Id，相当于一台机器对应一个顺序节点，也就是一个workId。

• 优势：ID号码随机。解决雪花算法的时钟回拨问题。弱依赖ZooKeeper，除了每次会去ZK拿数据以外，也会在本机文件系统上缓存一个workerID文件。当ZooKeeper出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。这样做到了对三方组件的弱依赖。一定程度上提高了SLA
• 劣势：搭建稍复杂

• 总体优势： Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景，为了追求更高的性能，需要通过 RPC Server 来部署 Leaf 服务，那仅需要引入 leaf-core 的包，把生成 ID 的 API 封装到指定的 RPC 框架中即可
• 总体劣势：相对于其他方式而言比较复杂

分布式唯一ID需要满足以下条件：

• 高可用性：不能有单点故障。
• 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
• 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
• 时间有序：以时间为序，或者ID里包含时间。这样一是可以少一个索引，二是冷热数据容易分离。
• 分片支持：可以控制ShardingId。比如某一个用户的文章要放在同一个分片内，这样查询效率高，修改也容易。
• 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
• 长度适中：不要太长，最好64bit。使用long比较好操作，如果是96bit，那就要各种移位相当的不方便，还有可能有些组件不能支持这么大的ID。
• 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。