您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

深度解密滴滴的高性能ID生成器(Tinyid)

时间:2020-09-09 11:07:41  来源:  作者:

1、引言

在中大型IM系统中,聊天消息的唯一ID生成策略是个很重要的技术点。不夸张的说,聊天消息ID贯穿了整个聊天生命周期的几乎每一个算法、逻辑和过程,ID生成策略的好坏有可能直接决定系统在某些技术点上的设计难易度。

有中小型IM场景下,消息ID可以简单处理,反正只要唯一就行,而中大型场景下,因为要考虑到分布式的性能、一致性等,所以要考虑的问题点又是另一回事。

总之就是,IM的消息ID生成这件事,可深可浅,看似简单但实际可探索的边界可以很大,这也是为什么即时通讯网为此专门整理了《IM消息ID技术专题》系列文章的原因。做技术所谓厚积薄发,了解的越多,你的技术可操作空间也就越大,希望随着这个系列文章的阅读,可以为你在ID生成这一块的技术选型带来更多有益的启发。

另外,因为即时通讯网主要关注的是即时通讯方面的系统开发,但并不意味着这个系统文章只适用于IM或消息推送等实时通信系统,它同样适用于其它需要唯一ID的应用中。

本文将要分享的是滴滴开源的分布式ID生成器Tinyid的技术原理、使用方法等等,希望能进一步为你打开这方面的技术视野。

学习交流:

- 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM》

- 开源IM框架源码:https://github.com/JackJiang2011/MobileIMSDK

(本文同步发布于:http://www.52im.net/thread-3129-1-1.html

2、专题目录

本文是“IM消息ID技术专题”系列文章的第6篇,专题总目录如下:

《IM消息ID技术专题(一):微信的海量IM聊天消息序列号生成实践(算法原理篇)》

《IM消息ID技术专题(二):微信的海量IM聊天消息序列号生成实践(容灾方案篇)》

《IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略》

《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法》

《IM消息ID技术专题(五):开源分布式ID生成器UidGenerator的技术实现》

《IM消息ID技术专题(六):深度解密滴滴的高性能ID生成器(Tinyid)》(* 本文)

3、什么是Tinyid?

Tinyid是滴滴用JAVA开发的一款分布式id生成系统,基于数据库号段算法实现。

Tinyid是在美团的ID生成算法Leaf的基础上扩展而来,支持数据库多主节点模式,它提供了REST API和Java客户端两种获取方式,相对来说使用更方便。不过,和美团的Leaf算法不同的是,Tinyid只支持号段一种模式(并不支持Snowflake模式)。(有关美团的Leaf算法,可以详读《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法》)

Tinyid目前在滴滴客服部门使用,且通过tinyid-client方式接入,每天生成的是亿级别的id。性能上,据称单实例能达到1千万QPS。

它的开源地址是:

主地址:https://github.com/didi/tinyid

备地址:https://github.com/52im/tinyid

PS:滴滴在Tinyid工程页面写了一句话,“tinyid,并不是滴滴官方产品,只是滴滴拥有的代码”,我语文不好,这句该怎么理解呢?

4、Tinyid的主要技术特性

主要特性总结一下就是:

1)全局唯一的long型ID:即id极限数量是2的64次方;

2)趋势递增的id:趋势递增的意思是,id是递增但不一定是连续的(这跟微信的ID生成策略类似);

3)提供 http 和 java-client 方式接入;

4)支持批量获取ID;

5)支持生成1,3,5,7,9…序列的ID;

6)支持多个db的配置。

适用的场景:只关心ID是数字,趋势递增的系统,可以容忍ID不连续,可以容忍ID的浪费。

不适用场景:像类似于订单ID的业务,因生成的ID大部分是连续的,容易被扫库、或者推算出订单量等信息。

另外:微信的聊天消息ID生成算法也是基于号段、趋势递增这种逻辑,如果有兴趣,可以详见:《IM消息ID技术专题(一):微信的海量IM聊天消息序列号生成实践(算法原理篇)》。

5、Tinyid的技术优势

性能方面:

1)http方式:访问性能取决于http server的能力,网络传输速度;

2)java-client方式:id为本地生成,号段长度(step)越长,qps越大,如果将号段设置足够大,则qps可达1000w+。

可用性方面:

1)当db不可用时,因为server有缓存,所以还可以使用一段时间;

2)如果配置了多个db,则只要有1个db存活,则服务可用;

3)使用tiny-client时,只要server有一台存活,则理论上server全挂,因为client有缓存,也可以继续使用一段时间。

6、Tinyid的技术原理详解

6.1 ID生成系统的技术要点

在简单系统中,我们常常使用db的id自增方式来标识和保存数据,随着系统的复杂,数据的增多,分库分表成为了常见的方案,db自增已无法满足要求。

这时候全局唯一的id生成系统就派上了用场,当然这只是id生成其中的一种应用场景。

那么,一个成熟的id生成系统应该具备哪些能力呢?

1)唯一性:无论怎样都不能重复,id全局唯一是最基本的要求;

2)高性能:基础服务尽可能耗时少,如果能够本地生成最好;

3)高可用:虽说很难实现100%的可用性,但是也要无限接近于100%的可用性;

4)易用性:能够拿来即用,接入方便,同时在系统设计和实现上要尽可能的简单。

6.2 Tinyid的实现原理

我们先来看一下最常见的id生成方式,db的auto_increment,相信大家都非常熟悉。

我也见过一些同学在实战中使用这种方案来获取一个id,这个方案的优点是简单,缺点是每次只能向db获取一个id,性能比较差,对db访问比较频繁,db的压力会比较大。

那么,是不是可以对这种方案优化一下呢?可否一次向db获取一批id呢?答案当然是可以的。

一批id,我们可以看成是一个id范围,例如(1000,2000],这个1000到2000也可以称为一个“号段”,我们一次向db申请一个号段,加载到内存中,然后采用自增的方式来生成id,这个号段用完后,再次向db申请一个新的号段,这样对db的压力就减轻了很多,同时内存中直接生成id,性能则提高了很多。

PS:简单解释一下什么是号段模式:

号段模式就是从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,业务服务将号段在本地生成1~1000的自增ID并加载到内存。

那么保存db号段的表该怎设计呢?我们继续往下看。

6.3 DB号段算法描述

深度解密滴滴的高性能ID生成器(Tinyid)

 

如上表,我们很容易想到的是db直接存储一个范围(start_id,end_id],当这批id使用完毕后,我们做一次update操作,update start_id=2000(end_id), end_id=3000(end_id+1000),update成功了,则说明获取到了下一个id范围。仔细想想,实际上start_id并没有起什么作用,新的号段总是(end_id,end_id+1000]。

所以这里我们更改一下,db设计应该是这样的:

深度解密滴滴的高性能ID生成器(Tinyid)

 

如上表所示:

1)我们增加了biz_type,这个代表业务类型,不同的业务的id隔离;

2)max_id则是上面的end_id了,代表当前最大的可用id;

3)step代表号段的长度,可以根据每个业务的qps来设置一个合理的长度;

4)version是一个乐观锁,每次更新都加上version,能够保证并发更新的正确性 。

那么我们可以通过如下几个步骤来获取一个可用的号段:

A、查询当前的max_id信息:select id, biz_type, max_id, step, version from tiny_id_info where biz_type='test';

B、计算新的max_id: new_max_id = max_id + step;

C、更新DB中的max_id:update tiny_id_info set max_id=#{new_max_id} , verison=version+1 where id=#{id} and max_id=#{max_id} and version=#{version};

D、如果更新成功,则可用号段获取成功,新的可用号段为(max_id, new_max_id];

E、如果更新失败,则号段可能被其他线程获取,回到步骤A,进行重试。

6.4 号段生成方案的简单架构

如上述内容,我们已经完成了号段生成逻辑。

那么我们的id生成服务架构可能是这样的:

深度解密滴滴的高性能ID生成器(Tinyid)

 

如上图,id生成系统向外提供http服务,请求经过我们的负载均衡router,到达其中一台tinyid-server,从事先加载好的号段中获取一个id。

如果号段还没有加载,或者已经用完,则向db再申请一个新的可用号段,多台server之间因为号段生成算法的原子性,而保证每台server上的可用号段不重,从而使id生成不重。

可以看到:

1)如果tinyid-server如果重启了,那么号段就作废了,会浪费一部分id;

2)同时id也不会连续;

3)每次请求可能会打到不同的机器上,id也不是单调递增的,而是趋势递增的(不过这对于大部分业务都是可接受的)。

6.5 简单架构的问题

到此一个简单的id生成系统就完成了,那么是否还存在问题呢?

回想一下我们最开始的id生成系统要求:高性能、高可用、简单易用。

在上面这套架构里,至少还存在以下问题:

1)当id用完时需要访问db加载新的号段,db更新也可能存在version冲突,此时id生成耗时明显增加;

2)db是一个单点,虽然db可以建设主从等高可用架构,但始终是一个单点;

3)使用http方式获取一个id,存在网络开销,性能和可用性都不太好。

6.6 优化办法及最终架构

1)双号段缓存:

对于号段用完需要访问db,我们很容易想到在号段用到一定程度的时候,就去异步加载下一个号段,保证内存中始终有可用号段,则可避免性能波动。

2)增加多db支持:

db只有一个master时,如果db不可用(down掉或者主从延迟比较大),则获取号段不可用。实际上我们可以支持多个db,比如2个db,A和B,我们获取号段可以随机从其中一台上获取。那么如果A,B都获取到了同一号段,我们怎么保证生成的id不重呢?tinyid是这么做的,让A只生成偶数id,B只生产奇数id,对应的db设计增加了两个字段,如下所示

深度解密滴滴的高性能ID生成器(Tinyid)

 

delta代表id每次的增量,remainder代表余数,例如可以将A,B都delta都设置2,remainder分别设置为0,1则,A的号段只生成偶数号段,B是奇数号段。通过delta和remainder两个字段我们可以根据使用方的需求灵活设计db个数,同时也可以为使用方提供只生产类似奇数的id序列。

3)增加tinyid-client:

使用http获取一个id,存在网络开销,是否可以本地生成id?

为此我们提供了tinyid-client,我们可以向tinyid-server发送请求来获取可用号段,之后在本地构建双号段、id生成,如此id生成则变成纯本地操作,性能大大提升,因为本地有双号段缓存,则可以容忍tinyid-server一段时间的down掉,可用性也有了比较大的提升。

4)tinyid最终架构:

最终我们的架构可能是这样的:

深度解密滴滴的高性能ID生成器(Tinyid)

 

下面是更具体的代码调用逻辑:

深度解密滴滴的高性能ID生成器(Tinyid)

 

如上图所示,下面是关于这个代码调用逻辑图的说明:

1)nextId和getNextSegmentId是tinyid-server对外提供的两个http接口;

2)nextId是获取下一个id,当调用nextId时,会传入bizType,每个bizType的id数据是隔离的,生成id会使用该bizType类型生成的IdGenerator;

3)getNextSegmentId是获取下一个可用号段,tinyid-client会通过此接口来获取可用号段;

4)IdGenerator是id生成的接口;

5)IdGeneratorFactory是生产具体IdGenerator的工厂,每个biz_type生成一个IdGenerator实例。通过工厂,我们可以随时在db中新增biz_type,而不用重启服务;

6)IdGeneratorFactory实际上有两个子类IdGeneratorFactoryServer和IdGeneratorFactoryClient,区别在于,getNextSegmentId的不同,一个是DbGet,一个是HttpGet;

7)CachedIdGenerator则是具体的id生成器对象,持有currentSegmentId和nextSegmentId对象,负责nextId的核心流程。nextId最终通过AtomicLong.andAndGet(delta)方法产生。

具体的代码实现,有兴趣可以直接阅读源码:

主地址:https://github.com/didi/tinyid

备地址:https://github.com/52im/tinyid

7、Tinyid的最佳实践

1)tinyid-server推荐部署到多个机房的多台机器:

多机房部署可用性更高,http方式访问需使用方考虑延迟问题。

2)推荐使用tinyid-client来获取id,好处如下:

a、id为本地生成(调用AtomicLong.addAndGet方法),性能大大增加;

b、client对server访问变的低频,减轻了server的压力;

c、因为低频,即便client使用方和server不在一个机房,也无须担心延迟;

d、即便所有server挂掉,因为client预加载了号段,依然可以继续使用一段时间

注:使用tinyid-client方式,如果client机器较多频繁重启,可能会浪费较多的id,这时可以考虑使用http方式。

3)推荐db配置两个或更多:

db配置多个时,只要有1个db存活,则服务可用 多db配置,如配置了两个db,则每次新增业务需在两个db中都写入相关数据。

8、Tinyid该怎么调用?

关于怎么调用。鉴于篇幅原因,就不再具体去写了,有兴趣的话,可以读一下这篇《Tinyid:滴滴开源千万级并发的分布式ID生成器》。

9、参考资料

[1] 面试总被问分布式ID怎么办? 滴滴(Tinyid)甩给他

[2] Tinyid:滴滴开源千万级并发的分布式ID生成器

[3] tinyid工程中文readme

[4] 滴滴开源的Tinyid如何每天生成亿级别的ID?



Tags:ID生成器   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
本文分享下Spring boot项目下使用JPA操作数据库时关于ID生成器的相关实现代码。在JPA中一个数据表必须要有主键,主键类型一般是推荐使用Long类型,那么在分布式微服务下需要保...【详细内容】
2021-08-17  Tags: ID生成器  点击:(293)  评论:(0)  加入收藏
1、引言在中大型IM系统中,聊天消息的唯一ID生成策略是个很重要的技术点。不夸张的说,聊天消息ID贯穿了整个聊天生命周期的几乎每一个算法、逻辑和过程,ID生成策略的好坏有可能...【详细内容】
2020-09-09  Tags: ID生成器  点击:(206)  评论:(0)  加入收藏
背景使用业务场景:1.利用数据库自增主键生成唯一ID,无法满足各个系统独自生成自增的唯一ID需求。在分布式系统,需要生成唯一ID的系统不止一个,这些ID的生成在各自业务内是独立的...【详细内容】
2020-08-21  Tags: ID生成器  点击:(112)  评论:(0)  加入收藏
在高并发或者分表分库情况下怎么保证数据id的幂等性呢?经常用到的解决方案有以下几种。微软公司通用唯一识别码(UUID)Twitter公司雪花算法(SnowFlake)基于数据库的id自增对id进行...【详细内容】
2019-12-23  Tags: ID生成器  点击:(67)  评论:(0)  加入收藏
▌简易百科推荐
摘 要 (OF作品展示)OF之前介绍了用python实现数据可视化、数据分析及一些小项目,但基本都是后端的知识。想要做一个好看的可视化大屏,我们还要学一些前端的知识(vue),网上有很多比...【详细内容】
2021-12-27  项目与数据管理    Tags:Vue   点击:(1)  评论:(0)  加入收藏
程序是如何被执行的  程序是如何被执行的?许多开发者可能也没法回答这个问题,大多数人更注重的是如何编写程序,却不会太注意编写好的程序是如何被运行,这并不是一个好...【详细内容】
2021-12-23  IT学习日记    Tags:程序   点击:(9)  评论:(0)  加入收藏
阅读收获✔️1. 了解单点登录实现原理✔️2. 掌握快速使用xxl-sso接入单点登录功能一、早期的多系统登录解决方案 单系统登录解决方案的核心是cookie,cookie携带会话id在浏览器...【详细内容】
2021-12-23  程序yuan    Tags:单点登录(   点击:(8)  评论:(0)  加入收藏
下载Eclipse RCP IDE如果你电脑上还没有安装Eclipse,那么请到这里下载对应版本的软件进行安装。具体的安装步骤就不在这赘述了。创建第一个标准Eclipse RCP应用(总共分为六步)1...【详细内容】
2021-12-22  阿福ChrisYuan    Tags:RCP应用   点击:(7)  评论:(0)  加入收藏
今天想简单聊一聊 Token 的 Value Capture,就是币的价值问题。首先说明啊,这个话题包含的内容非常之光,Token 的经济学设计也可以包含诸多问题,所以几乎不可能把这个问题说的清...【详细内容】
2021-12-21  唐少华TSH    Tags:Token   点击:(9)  评论:(0)  加入收藏
实现效果:假如有10条数据,分组展示,默认在当前页面展示4个,点击换一批,从第5个开始继续展示,到最后一组,再重新返回到第一组 data() { return { qList: [], //处理后...【详细内容】
2021-12-17  Mason程    Tags:VUE   点击:(14)  评论:(0)  加入收藏
什么是性能调优?(what) 为什么需要性能调优?(why) 什么时候需要性能调优?(when) 什么地方需要性能调优?(where) 什么时候来进行性能调优?(who) 怎么样进行性能调优?(How) 硬件配...【详细内容】
2021-12-16  软件测试小p    Tags:性能调优   点击:(19)  评论:(0)  加入收藏
Tasker 是一款适用于 Android 设备的高级自动化应用,它可以通过脚本让重复性的操作自动运行,提高效率。 不知道从哪里听说的抖音 app 会导致 OLED 屏幕烧屏。于是就现学现卖,自...【详细内容】
2021-12-15  ITBang    Tags:抖音防烧屏   点击:(23)  评论:(0)  加入收藏
11 月 23 日,Rust Moderation Team(审核团队)在 GitHub 上发布了辞职公告,即刻生效。根据公告,审核团队集体辞职是为了抗议 Rust 核心团队(Core team)在执行社区行为准则和标准上...【详细内容】
2021-12-15  InfoQ    Tags:Rust   点击:(24)  评论:(0)  加入收藏
一个项目的大部分API,测试用例在参数和参数值等信息会有很多相似的地方。我们可以复制API,复制用例来快速生成,然后做细微调整既可以满足我们的测试需求1.复制API:在菜单发布单...【详细内容】
2021-12-14  AutoMeter    Tags:AutoMeter   点击:(20)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条