本文来自融云技术团队原创分享，原文发布于“融云全球互联网通信云”公众号，原题《如何实现分布式场景下唯一 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、大用途，值得借鉴！
免责申明：本文来自融云官方技术团队的分享，仅用于技术交流学习和研究目的，请勿用于非法用途，文中如涉及商业秘密，请告之我处理！
特别说明：仅出于技术研究和学习目的来分享此文，并未收取任何好处，所以此文不是广告，我也不是托。如有不妥，请告之！
学习交流：
- 即时通讯/推送技术开发交流5群：215477170[推荐]
- 移动端IM开发入门文章：《新手入门一篇就够：从零开发移动端IM》
（本文同步发布于：http://www.52im.net/thread-2747-1-1.html）
2、相关文章
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 生成重复。
附录：更多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生成策略》
>> 更多同类文章 ……
（本文同步发布于：http://www.52im.net/thread-2747-1-1.html）