滴滴com(滴滴出行生成器)

1.引言在大中型IM系统中，聊天消息的唯一ID生成策略是一个非常重要的技术点。毫不夸张地说，聊天消息ID几乎贯穿了整个聊天生命周期的每一个算法、逻辑和流程。

ID生成策略的好坏，在某些技术点上可能直接决定了系统的设计难度。在中小型IM场景中，消息ID可以简单处理，只要它是唯一的。在中大型场景下，出于分布式性能和一致性的考虑，

所以要考虑的问题是另一回事。总之，IM的消息ID的生成可深可浅，看似简单，但实际可以探索的边界可以非常大，这也是为什么即时通讯网特意整理了0755到79000的系列文章。

你对技术了解的越多，你的技术运作的空间就越大。希望随着这一系列文章的阅读，能给你在ID生成中的技术选择带来更多有益的启发。此外，由于即时通讯网主要专注于即时通讯的系统开发，

但并不意味着这篇系统文章只适用于IM或消息推送等实时通信系统，同样适用于其他需要唯一ID的应用。本文将分享滴滴开源的分布式id生成器Tinyid的技术原理、用法等。

希望能为你进一步打开这个技术视野。学习交流：

-移动IM开发入门文章：《IM消息ID技术专题》

-Open source instant messaging framework source code: https://github.com/jackjiang2011/mobileimsdk

(本文在http://www.52im.net/thread-3129-1-1.html同步发表)

2.主题目录本文是“IM消息ID技术主题”系列文章的第六篇。一般主题目录如下：

《新手入门一篇就够：从零开发移动端IM》

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

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

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

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

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

3.Tinyid是什么？Tinyid是Didi用Java开发的分布式id生成系统，基于数据库号段算法实现。Tinyid是美团的id生成算法Leaf的扩展，支持多主数据库模式。

它提供了REST API和Java客户端两种获取方式，使用起来相对更方便。但与美团的叶子算法不同，Tinyid只支持号段的一种模式(不是雪花模式)。

(美团的叶子算法请详细阅读《IM消息ID技术专题(六)：深度解密滴滴的高性能ID生成器(Tinyid)》。)滴滴客服部门目前使用的是Tiny id，通过tinyid-client访问，每天产生几十亿的id。在性能方面，

据说单个实例可以达到1000万QPS。它的开源地址是：

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

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

PS:滴滴在tinyid项目页面写了一句话“Tinyid不是滴滴的官方产品，而是滴滴拥有的代码”。我的中文不好。这句话怎么理解？

4.Tinyid的主要技术特征总结如下：

1)全局唯一长ID:即ID的极限个数为2的64次方；

2)递增趋势的id:递增趋势是指id在增加但不一定持续(这和微信的ID生成策略类似)；

3)提供http和java客户端访问；

4）支持批量获取ID；

5）支持生成1,3,5,7,9…序列的ID；

6）支持多个db的配置。

适用的场景：只关心ID是数字，趋势递增的系统，可以容忍ID不连续，可以容忍ID的浪费。不适用场景：像类似于订单ID的业务，因生成的ID大部分是连续的，容易被扫库、或者推算出订单量等信息。

另外：微信的聊天消息ID生成算法也是基于号段、趋势递增这种逻辑，如果有兴趣，可以详见： 《IM消息ID技术专题(四)：深度解密美团的分布式ID生成算法》 。

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号段算法描述如上表，我们很容易想到的是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设计应该是这样的：

如上表所示：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生成系统向外提供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设计增加了两个字段，

如下所示

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最终架构：最终我们的架构可能是这样的：

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

如上图所示，下面是关于这个代码调用逻辑图的说明：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该怎么调用？关于怎么调用。鉴于篇幅原因，就不再具体去写了，有兴趣的话，可以读一下这篇《IM消息ID技术专题(一)：微信的海量IM聊天消息序列号生成实践（算法原理篇）》 。

9、参考资料[1] 面试总被问分布式ID怎么办？ 滴滴（Tinyid）甩给他[2] Tinyid：滴滴开源千万级并发的分布式ID生成器[3] tinyid工程中文readme[4] 滴滴开源的Tinyid如何每天生成亿级别的ID？

附录：更多IM开发热门技术文章《Tinyid：滴滴开源千万级并发的分布式ID生成器》

《新手入门一篇就够：从零开发移动端IM》

《移动端IM开发者必读(一)：通俗易懂，理解移动网络的“弱”和“慢”》

《移动端IM开发者必读(二)：史上最全移动弱网络优化方法总结》

《从客户端的角度来谈谈移动端IM的消息可靠性和送达机制》

《现代移动端网络短连接的优化手段总结：请求速度、弱网适应、安全保障》

《移动端IM中大规模群消息的推送如何保证效率、实时性？》

《移动端IM开发需要面对的技术问题》

《开发IM是自己设计协议用字节流好还是字符流好？》

《请问有人知道语音留言聊天的主流实现方式吗？》

《IM消息送达保证机制实现(一)：保证在线实时消息的可靠投递》

《IM消息送达保证机制实现(二)：保证离线消息的可靠投递》

《如何保证IM实时消息的“时序性”与“一致性”？》

《一个低成本确保IM消息时序的方法探讨》

《IM单聊和群聊中的在线状态同步应该用“推”还是“拉”？》

《IM群聊消息如此复杂，如何保证不丢不重？》

《谈谈移动端 IM 开发中登录请求的优化》

《移动端IM登录时拉取数据如何作到省流量？》

《浅谈移动端IM的多点登录和消息漫游原理》

《完全自已开发的IM该如何设计“失败重试”机制？》

《自已开发IM有那么难吗？手把手教你自。一个Andriod版简易IM (有源码)》

《IM开发基础知识补课(六)：数据库用NoSQL还是SQL？读这篇就够了！》

《适合新手：从零开发一个IM服务端（基于Netty，有完整源码）》

《拿起键盘就是干：跟我一起徒手开发一套分布式IM系统》

《适合新手：手把手教你用Go快速搭建高性能、可扩展的IM系统(有源码)》

《IM里“附近的人”功能实现原理是什么？如何高效率地实现它？》

《IM开发基础知识补课(七)：主流移动端账号登录方式的原理及设计思路》

《IM要做手机扫码登录？先看看微信的扫码登录功能技术原理》

《IM开发宝典：史上最全，微信各种功能参数和逻辑规则资料汇总》

《IM开发干货分享：我是如何解决大量离线消息导致客户端卡顿的》

《IM开发干货分享：如何优雅的实现大量离线消息的可靠投递》

更多同类文章……

本文已同步发布于“即时通讯技术圈”公众号。