分布式主键调研文档

Posted on Edited on In

背景

在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。随着数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求，此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？

  1. 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
  2. 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
  3. 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
  4. 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

上述123对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。

常见方法

分布式主键的生成方式分为中心化和去中心化两大类。

  • 中心化方法包括SEQUENCE区间方案、基于redis的方案、基于zookeeper顺序节点；
  • 非中心化方案包括UUID、mongodb的ObjectId、snowflake方案、基于Ignite的分布式ID生成器；

SEQUENCE区间方案

所有应用服务器去同一个库获取可使用的sequence（乐观锁保证一致性），得到（sequence，sequence+步长]个可被这个数据源使用的id，当应用服务器插入“步长”个数据后，再次去争取新的sequence区间。

以MySQL举例，利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增，每次业务使用下列SQL读写MySQL得到ID号。

begin;
REPLACE INTO Tickets64 (stub) VALUES (‘a’);
SELECT LAST_INSERT_ID();
commit;

优点：

  • 非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护。
  • ID号单调自增，可以实现一些对ID有特殊要求的业务。

缺点：

  • 强依赖DB，当DB异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
  • ID发号性能瓶颈限制在单台MySQL的读写性能。

基于redis的方案

另一种中心化生成分布式主键的方式是采用Redis在内存中生成自增序列，通过redis的原子自增操作(incr接口)生成一个自增的序列。

优点：

  • 生成一个 全局连续递增 的数字类型主键。

缺点：

  • 强依赖Redis，一旦Redis不可用导致系统不可用，属于致命问题，另外Redis的单点问题也需要解决，部署复杂度较高。

UUID方案

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倍的存储成本。

mongodb的ObjectId

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

4字节 3字节 2字节 3字节
time machine pid 增量

优点：

  • 全局唯一 。

缺点：

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

IgniteAtomicSequence方案

Ignite是apache开源的框架，IgniteAtomicSequence接口提供了分布式的原子性序列，类似于分布式原子性的Long类型，但是他的值只能增长，他特有的功能是支持预留一定范围的序列值，来避免每次序列获取下一个值时都需要的昂贵的网络消耗和缓存更新，也就是，当在一个原子性序列上执行了incrementAndGet()（或者任何其他的原子性操作），数据结构会往前预留一定范围的序列值，他会保证对于这个序列实例来说跨集群的唯一性。 这个类型的使用是非常简单的，相关代码如下：

1
2
3
4
5
6
7
8
9
10
Ignite ignite = Ignition.start();
IgniteAtomicSequence seq = ignite.atomicSequence("seqName",//序列名
 0, //初始值
true//如果序列不存在则创建
);
for (int i = 0; i < 20; i++) {
  long currentValue = seq.get();//获取当前值
  long newValue = seq.incrementAndGet();//先加1再取值
  ...
}

按照前述，直接按照初始值0创建IgniteAtomicSequence，是有很大风险的，无法在生产环境下使用，而且存在长度不固定问题，所以还需要进一步想办法，研究的重点在于解决初始值的问题。 因为IgniteAtomicSequence的值为long型，而在Java中long类型的最大值是9223372036854775807，这个数值长度为19位，对于实际应用来说，是一个很大的值，但是对于常见的没有环境依赖的ID生成器来说，还是比较短的。因此我们打算在这方面做文章。 因为系统重置的一个重要指标就是时间，那么我们以时间作为参照，然后加上一个扩展，可能是一个比较理想的选择，我们以如下的规则作为初始值： 时间的yyyyMMddHHmmss+00000 这个长度正好是19位，然后每次加1，因为现在是2018年，这个规则在常规应用场景中，是不会超过long类型的最大值的。 但是，这个规则存在一个风险，就是假设不考虑实际应用和实际性能，如果增加操作业务量特别大，会使这个序列值快速进位，如果某个时间节点宕机后瞬间重启，是有可能存在重启后的初始值小于原来的最大值的，这时就无法保证唯一性了。

优点：

  • 简单，初始值从0开始递增
  • 带时间值，方便阅读

缺点：

  • 强依赖服务器时间，时钟回拨问题

snowflake方案

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

63 62-22 21-12 11-0
1位：2 41位：支持69.7年（单位ms） 10位：1024 12位：4096

默认情况下41bit的时间戳可以支持该算法使用到2018+69年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。

优点：

  • 在服务器规模不是很大（不超过1024条件） 全局唯一 ，单机递增 ，是数字类型，存储索引成本低。

缺点：

  • 机器规模大于1024无法支持，需要运维配合解决单机部署多个同服务进程问题。

mysql-left-segment数据库方案

基于第一种SEQUENCE区间方案，做了如下改变：

  • 原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。
  • 各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。
  • 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。为此，我们设置了一个消费进度阈值，用于当号段消费到某个点时就异步的把下一个号段加载到内存中。

test_tag在第一台Leaf机器上是11000的号段，当这个号段用完时，会去加载另一个长度为step=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是30014000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000

采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。

  • 每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
  • 每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

数据库表设计如下：

left_segment: 号段存储表
Field | Type | Null | Default | Extra | Desc |
—|—|—|—|—|—|
id | bigint(20) | NO | | | 主键id |
biz_tag | varchar(128) | NO | | 唯一索引 | 业务标识 |
max_id | bigint(20) | NO | 1 | | 该业务所被分配的ID号段的最大值 |
step | int(22) | NO | | 1000 | 表示每次分配的号段长度 |
desc | varchar(256) | YES | Null | | 备注信息 |
create_time | timestamp | NO | CURRENT_TIMESTAMP | | 创建时间 |
update_time | timestamp | NO | Null | on update CURRENT_TIMESTAMP | 更新时间 |

left_segment_log: 号段更新日志表
Field | Type | Null | Default | Extra | Desc |
—|—|—|—|—|—|
id | bigint(20) | NO | | 主键id | |
min_id | bigint(20) | NO | 1 | | 初始号段 |
max_id | bigint(20) | NO | 1 | | 更新后号段 |
ip | varchar(20) | YES | Null | | 更新应用ip |
create_time | timestamp | NO | CURRENT_TIMESTAMP | | 创建时间 |

优点：

  • Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
  • ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。
  • 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
  • 可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点：

  • ID号码不够随机，能够泄露发号数量的信息，不太安全。
  • DB宕机会造成整个系统不可用。

总结

由于公司业务复杂度，最终选择去中心化的雪花算法分布式主键和中心化的mysql-left-segment数据库方案。