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、注意事项


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

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




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 是有序的,也能方便阅读。

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

如上图所示,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 :
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_2.png 

2)获取一个自旋 ID , highBits 左移 12 位,并将自旋 ID 拼接到低 12 位中:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_3.png 

其中,自旋 ID 是一个从 0 到 4095 范围内,顺序递增的数,生成规则如下:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_4.png 

3)上步的 highBits 左移 4 位,将会话类型拼接到低 4 位:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_5.png 

4)取会话 ID 哈希值的低 22 位,记为 sessionIdInt:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_6.png 

5)highBits 左移 6 位,并将 sessionIdInt 的高 6 位拼接到 highBits 的低 6 位中:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_7.png 

6)取会话 ID 的低 16 位作为 lowBits:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_8.png 

7)highBits 与 lowBits 拼接得到 80 Bit 的消息 ID,对其进行 32 进制编码,即可得到唯一消息 ID:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_9.png 
编码规则:从左至右,每 5 个 Bit 转换为一个整数,以这个整数作为下标,即可在下表中找到对应的字符。

6、实际应用


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

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

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


比如,可以直接登陆融云的Web产品 http://web.sealtalk.im,在浏览器端研究学习它的消息ID生成情况:
IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略_WX20190919-120024@2x.png 

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


哇谷im_im即时通讯_私有云_公有云-哇谷云科技官网-JM沟通

IM下载体验 - 哇谷IM-企业云办公IM即时聊天社交系统-JM 沟通下载

IM功能与价格 - 哇谷IM-提供即时通讯IM开发-APP搭建私有化-公有云-私有化云-海外云搭建

新闻动态 - 哇谷IM-即时通讯热门动态博客聊天JM沟通APP

哇谷IM-JM沟通热门动态博客短视频娱乐生活

关于哇谷-哇谷IM-提供企业即时通讯IM开发-语音通话-APP搭建私有化-公有云-私有化云-海外云搭建

联系我们 - 哇谷IM-即时通讯IM私有化搭建提供接口与SDK及哇谷云服务

即时通讯开发涉及到的技术领域十分广泛,主要涉及以下几个领域:

即时通讯私有化部署是什么?

哇谷科技JM沟通即时通讯内核升级新版哇谷2.0即将上线

2.0哇谷即时通讯系统正式上线适合大型项目运营超稳定性

哇谷IM动态增加官网显示热门动态

JM沟通app即时通讯聊天系统功能介绍