Java 开发

分布式主键调研

言七墨 · 11月30日 · 2019年 · · 240次已读

背景

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

正文

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

1、中心化生成算法

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

SEQUENCE区间方案

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

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

各数据库按特定步长自增

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

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

基于redis的方案

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

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

2、去中心化生成算法

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

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字节
timemachinepid自增
  • 优势:全局唯一
  • 劣势:非数字类型,24个字符,按照目前Mysql最常用的编码Utf-8,每一个字符对应的索引成本是3字节,也就是一个ObjectId需要72个字节的索引存储成本,是最大数字类型(8字节)的9倍的存储成本

snowflake算法

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

6362-2221-1211-0
1位:241位:支持69.7年10位:支持1023台机器12位:支持1毫秒产生4095个自增序列id

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

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

百度(uid-generator)

github地址:uid-generator

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

uid-generator中的workId是由uid-generator自动生成的,并且考虑到了应用部署在docker上的情况,在uid-generator中用户可以自己去定义workId的生成策略,默认提供的策略是:应用启动时由数据库分配。说的简单一点就是:应用在启动时会往数据库表(uid-generator需要新增一个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 的接口, 存在网络延迟。

美团(Leaf)

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无规则、不规则。
0 条回应