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

本文来自融云技术团队原创分享，原文发布于“融云全球互联网通信云”公众号，原题《如何实现分布式场景下唯一 ID 生成？》，即时通讯网收录时有部分改动。

1、引言

对于IM应用来说，消息ID（或称序列号）是个看似不起眼，但非常重要的东西之一。

消息ID的使用贯穿了IM技术逻辑的方方面面，比如：

• 1）聊天消息的顺序保证；
• 2）聊天消息QoS送达保证机制时的去重；
• 3）特定聊天消息的精确查找和匹配；
• 4）聊天消息的已读未读处理；
• 5）聊天消息的送达回执；
• 6）群聊消息的扩散读拉取标记；
• 7）... ...
  

但，IM系统高度个性化的特性（设计上没有统一的标准和思路），包括聊天消息ID的生成算法在内，每个产品都有自已的思路和考量。

常见的消息ID生成策略有：

• 1）UUID：这种方法简单直观，可以很好的保证唯一性，但对于技术洁癖的人来说ID长度会有点长，而且是无序的；
• 2）使用时间戳长整数：这个最偷懒，用在吞吐量不大的场景下，凑活也能用，但存在重复的风险，也无法保证分布式下的唯一性；
• 3）使用twitter开源的snowflake算法：在分布式高并发的情况下，这也是个不错的选择；
• 4）按用户使用独立的ID生成空间生成顺序的ID：比如微信的消息序列号生成策略就很不错。
  

从某种意义上来讲，消息ID生成策略的优劣决定了IM应用层某些功能实现的难易度，优良设计的消息ID结构会让IM产品的开发越做越顺，反之越做越别扭。

本文要分享的是融云即时通讯云产品中的聊天消息ID生成算法和策略，一个19字节的ID就能包含：时间戳、消息类型、会话ID、序列号，小ID、大用途，值得借鉴！

免责申明：本文来自融云官方技术团队的分享，仅用于技术交流学习和研究目的，请勿用于非法用途，文中如涉及商业秘密，请告之我处理！
特别说明：即时通讯网仅出于技术研究和学习目的来分享此文，并未收取任何好处，所以此文不是广告，我也不是托。如有不妥，请告之！

2、专题目录

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

• 《IM消息ID技术专题(一)：微信的海量IM聊天消息序列号生成实践（算法原理篇）》
• 《IM消息ID技术专题(二)：微信的海量IM聊天消息序列号生成实践（容灾方案篇）》
• 《IM消息ID技术专题(三)：解密融云IM产品的聊天消息ID生成策略》（* 本文）
• 《IM消息ID技术专题(四)：深度解密美团的分布式ID生成算法》
• 《IM消息ID技术专题(五)：开源分布式ID生成器UidGenerator的技术实现》
• 《IM消息ID技术专题(六)：深度解密滴滴的高性能ID生成器(Tinyid)》
  

3、技术背景

对于一套分布式部署的 IM 系统，要求每条消息的 ID 要保证在集群中全局唯一且按生成时间有序排列。如何快速高效的生成消息数据的唯一 ID ，是影响系统吞吐量的关键因素。

那么，融云是如何做到生成全局唯一消息 ID 的呢？

首先需要明确下 ID 生成的核心需求：

• 1）全局唯一；
• 2）有序。
  

4、设计思路

融云消息数据的唯一 ID 长度采用 80 Bit。

每 5 个 Bit ，进行一次 32 进制编码，转换为一个字符，字符取值范围是：数字 “2 ~ 9 ”和字母“A ~ B”。其中，已经去掉容易造成肉眼混淆的数字 0 和 1 （余下可用的数字就是8个了），及字母 O 和 I（余下可用的字母就是24个了），那么总可用字符就是32个（刚好可按32进制进行编码）。

这样，80 Bit 可以转换为 16 个字符，再加上 3 个分隔符（ - ），将 16 个字符分为 4 组，最终得到一个 19 字符的唯一 ID ，形如：“ BD8U-FCOJ-LDC5-L789 ”。 这样设计，即可以保证生成的 ID 是有序的，也能方便阅读。



如上图所示，80 Bit 被分为 4 段。

1）第一段 42 Bit：用于存放时间戳，最长可表示到 2109 年，足够开发者当前使用了。时间戳数据放在高位，可以保证生成的唯一 ID 是按时间有序的，这个是消息 ID 必须要满足的条件。

2）第二段 12 Bit：用于存放自旋转 ID 。我们知道，时间戳的精度是到毫秒的，对于一套亿级 IM 系统来说，同一毫秒内产生多条消息太正常不过了，这个自旋 ID 就是在给落到同一毫秒内的消息进行自增编号。12 Bit 则意味着，同一毫秒内，单台主机中最多可以标识 4096（ 2 的 12 次方）条消息。

3）第三段 4 Bit：用于标识会话类型。4 Bit ，最多可以标识 16 中会话，足够涵盖单聊、群聊、系统消息、聊天室、客服及公众号等常用会话类型。

4）第四段 22 Bit：会话 ID 。如群聊中的群 ID ，聊天室中的聊天室 ID 等。与第三段会话类型组合在一起，可以唯一标识一个会话。其他的一些 ID 生成算法，会预留两段，分别用来标识数据中心编号和主机编号（如 SnowFlake 算法），我们并没有这样做，而是将这两段用来标识会话。这样，ID 生成可以直接融入到业务服务中，且不必关心服务所在的主机，做到无状态扩缩容。

5、代码实现

消息 ID 共占 80 Bit ，计算时我们分为两部分，高 64 Bit （记为 highBits）和低 16 Bit （记为 lowBits）。

具体的代码实现过程，大致如下。

1）获取当前系统的时间戳，并赋值给消息 ID 的高 64 Bit ：


2）获取一个自旋 ID ， highBits 左移 12 位，并将自旋 ID 拼接到低 12 位中：


其中，自旋 ID 是一个从 0 到 4095 范围内，顺序递增的数，生成规则如下：


3）上步的 highBits 左移 4 位，将会话类型拼接到低 4 位：


4）取会话 ID 哈希值的低 22 位，记为 sessionIdInt：


5）highBits 左移 6 位，并将 sessionIdInt 的高 6 位拼接到 highBits 的低 6 位中：


6）取会话 ID 的低 16 位作为 lowBits：


7）highBits 与 lowBits 拼接得到 80 Bit 的消息 ID，对其进行 32 进制编码，即可得到唯一消息 ID：

编码规则：从左至右，每 5 个 Bit 转换为一个整数，以这个整数作为下标，即可在下表中找到对应的字符。

6、实际应用

PS：如果感觉上面两节介绍的算法思路和代码实现有点抽象，可以直接去看融云的IM产品中的实际消息ID生成情况。

比如，从融云的Demo产品中取出的同一个用户相近时间内的3条单聊消息ID样本：

BD8U-DG1U-5UI5-L789
BD8U-DU6D-2205-L789
BD8U-FCOJ-LDC5-L789

比如，可以直接登陆融云的Web产品 http://web.sealtalk.im，在浏览器端研究学习它的消息ID生成情况：


特别说明：即时通讯网仅仅出于技术研究和学习目的来分享此文，并没有收到融云的任何好处，所以此文不是广告，我也不是托。如有不妥，请告之！

7、注意事项

融云所使用的这种 ID 生成的方式，需要注意：

• 1）注意保证自旋 ID 的生成是线程安全的；
• 2）避免在并发情况下，生成出同样的 ID ；
• 3）此 ID 生成算法，强烈依赖系统时间，如果系统时间被改小，理论上也可能造成 ID 生成重复。
  

附录1：融云分享的其它文章

• 《融云技术分享：融云安卓端IM产品的网络链路保活技术实践》
• 《IM消息ID技术专题(三)：解密融云IM产品的聊天消息ID生成策略》
• 《融云技术分享：基于WebRTC的实时音视频首帧显示时间优化实践》（* 本文）
• 《即时通讯云融云CTO的创业经验分享：技术创业，你真的准备好了？》
• 《IM开发干货分享：浅谈IM系统中离线消息、历史消息的最佳实践》
  

附录2：更多IM开发热门技术文章

《新手入门一篇就够：从零开发移动端IM》
《移动端IM开发者必读(一)：通俗易懂，理解移动网络的“弱”和“慢”》
《移动端IM开发者必读(二)：史上最全移动弱网络优化方法总结》
《从客户端的角度来谈谈移动端IM的消息可靠性和送达机制》
《现代移动端网络短连接的优化手段总结：请求速度、弱网适应、安全保障》
《腾讯技术分享：社交网络图片的带宽压缩技术演进之路》
《小白必读：闲话HTTP短连接中的Session和Token》
《IM开发基础知识补课：正确理解前置HTTP SSO单点登陆接口的原理》
《移动端IM中大规模群消息的推送如何保证效率、实时性？》
《移动端IM开发需要面对的技术问题》
《开发IM是自己设计协议用字节流好还是字符流好？》
《请问有人知道语音留言聊天的主流实现方式吗？》
《IM消息送达保证机制实现(一)：保证在线实时消息的可靠投递》
《IM消息送达保证机制实现(二)：保证离线消息的可靠投递》
《如何保证IM实时消息的“时序性”与“一致性”？》
《一个低成本确保IM消息时序的方法探讨》
《IM单聊和群聊中的在线状态同步应该用“推”还是“拉”？》
《IM群聊消息如此复杂，如何保证不丢不重？》
《谈谈移动端 IM 开发中登录请求的优化》
《移动端IM登录时拉取数据如何作到省流量？》
《浅谈移动端IM的多点登陆和消息漫游原理》
《完全自已开发的IM该如何设计“失败重试”机制？》
《通俗易懂：基于集群的移动端IM接入层负载均衡方案分享》
《微信对网络影响的技术试验及分析（论文全文）》
《即时通讯系统的原理、技术和应用（技术论文）》
《开源IM工程“蘑菇街TeamTalk”的现状：一场有始无终的开源秀》
《腾讯原创分享(一)：如何大幅提升移动网络下手机QQ的图片传输速度和成功率》
《如约而至：微信自用的移动端IM网络层跨平台组件库Mars已正式开源》
《基于社交网络的Yelp是如何实现海量用户图片的无损压缩的？》
《腾讯技术分享：腾讯是如何大幅降低带宽和网络流量的(图片压缩篇)》
《腾讯技术分享：腾讯是如何大幅降低带宽和网络流量的(音视频技术篇)》
《字符编码那点事：快速理解ASCII、Unicode、GBK和UTF-8》
《全面掌握移动端主流图片格式的特点、性能、调优等》
《子弹短信光鲜的背后：网易云信首席架构师分享亿级IM平台的技术实践》
《IM开发基础知识补课(五)：通俗易懂，正确理解并用好MQ消息队列》
《微信技术分享：微信的海量IM聊天消息序列号生成实践（算法原理篇）》
《自已开发IM有那么难吗？手把手教你自撸一个Andriod版简易IM (有源码)》
《融云技术分享：解密融云IM产品的聊天消息ID生成策略》
>> 更多同类文章 ……

融云的这个id看起来很不错，很有技巧，拿到id的地方，就能知道时间戳、消息类型这些，很赞，有空来研究一下。

我有一个不明白的地方，就是会话id如果hash
冲突了，那不就表明不能通过会话类型和会话id唯一确定了啊

引用：高双文 发表于 2019-11-19 10:44
我有一个不明白的地方，就是会话id如果hash
冲突了，那不就表明不能通过会话类型和会话id唯一确定了啊

会话id不需要hash啊，会话id（比如群id号）可以用唯一主键的方式生成，没有什么问题

消息 id 客户端来生成可以吗?

引用：王卿 发表于 2020-01-18 18:22
设计很精巧，但有个疑问：集群环境下，假设同一会话的两个不同成员登录在不同主机，两人恰好同时发消息，此 ...

你说的理论上确实存在这种可能性，但现实来说几率小到可以忽略，当然程序员都是这种思维。
不过，记住做im不是做支付这类金融系统，数据可以允许万有一失（腾讯就是一直用这个原则设计qq的），聊天消息相当于自然语言，是有上下文关系的，系统做为容错机制扔掉一条冲突的消息，完全可以理解，也不会出现什么大不了的事。

引用：JackJiang 发表于 2020-01-18 20:25
你说的理论上确实存在这种可能性，但现实来说几率小到可以忽略，当然程序员都是这种思维。
不过，记住做 ...

请问集群环境下，服务器时钟不一致，会不会导致时间戳不一样造成消息乱序？

引用：461611894 发表于 2021-04-15 12:46
请问集群环境下，服务器时钟不一致，会不会导致时间戳不一样造成消息乱序？

是的，所以不能全依赖服务器时间来排序

楼主好，请问下，消息ID一般服务端有用作消息顺序性排序，如果是字符串，应该比较不了大小把

引用：逍遥小子 发表于 2021-07-07 18:09
楼主好，请问下，消息ID一般服务端有用作消息顺序性排序，如果是字符串，应该比较不了大小把

id用数字只能说比较大小更直接，字符串还不是一样可以有顺序，只是不直观而已，就看你要怎么用了

引用：JackJiang 发表于 2021-07-07 18:34
id用数字只能说比较大小更直接，字符串还不是一样可以有顺序，只是不直观而已，就看你要怎么用了

好的谢谢楼主

左右移的时候丢弃的数据，反解析时岂不是可能无法得到正确的值？

有个疑惑，ID生成是在哪里生成，是客户端每次要发送消息前，请求这个ID生成的服务嘛，然后把生成的ID加到消息中发给服务器

想问一下，使用这个算法生成的id，是不是就不需要另外弄一个id生成服务了?

引用：林北lpepsi 发表于 2021-09-11 23:32
有个疑惑，ID生成是在哪里生成，是客户端每次要发送消息前，请求这个ID生成的服务嘛，然后把生成的ID加到消 ...

有专门的ID发号器服务

集群模式如何确保ID不重复, 因为ID没有work_id 信息

这相当于是全局递增的是吧，不能做到会话级别递增吧

引用：HK意境 发表于 2023-02-10 21:18
这相当于是全局递增的是吧，不能做到会话级别递增吧

融云的是全局唯一