1.评论
对于即时通讯系统来说，如何将即时通讯聊天信息离线拉取(差异拉取是为了节省流量)、多终端消息同步、消息顺序保证等是一个典型的即时通讯技术难点。
就像以下由即时通讯组织的即时消息开发干货系列一样:
即时消息传递保证机制的实现(一):保证在线实时消息的可靠传递
即时消息传递保证机制的实现(二):保证离线消息的可靠传递
如何确保即时消息的“时间”和“一致性”？》
我应该使用“推”还是“拉”来同步即时消息单聊和群聊的在线状态？》
即时消息群聊新闻如此复杂，如何确保它不丢失或沉重？》
浅谈移动即时通信的多点登录和消息漫游原理
即时消息群聊消息是一份拷贝(即扩散阅读)还是多份拷贝(即扩散写作)？》
上述文章中涉及的即时消息聊天消息的流量节省、可靠传递、离线拉取、定时、一致性、多终端同步等问题，实际上就是要解决一个问题:如何保证聊天消息的唯一性和顺序确定。
当即时通讯网络的许多组成员讨论这个问题时，一般认为使用整数自增序列号作为消息id(即MsgId):这不仅可以保证消息的唯一性，而且问题是在分布式的情况下很难保证消息Id的唯一性和顺序增量，并且很难保持id生成的一致性(网络延迟、调试错误等)。可能导致不同机器获得的消息标识之间的冲突)
即时消息标识技术主题(1):在微信上生成大量即时消息聊天消息序列号的实践(算法原理)_22.jpg
但是，通过本文微信团队共享的微信消息序列号生成的思想，实际上为了解决消息的唯一性和序列性问题，一个技术点可以分解为两个:每条消息的原始自增唯一消息标识被分解为两个关键属性——消息标识和消息序列号，也就是说， 只要消息标识是唯一的，不需要注意顺序(比如直接使用UUID)，消息序列号也不需要注意唯一性(就像本文中微信的想法)，这种技术分解就能很好地解决原始消息标识既要保证唯一性又要保证顺序的问题。
那么，我们如何优雅地解决“消息的序列号只需要保证序列，而不需要注意唯一性”的问题呢？这是本文要分享的内容，强烈建议您深入理解和阅读。
这篇文章因篇幅长而分为两部分。请点击阅读:
第一部分:“微信技术共享:微信的海量即时聊天信息序列号生成实践(算法原理)”(本文)
下一部分:“微信技术共享:微信海量即时聊天信息序列号生成实践(灾难恢复计划)”
推荐:融云团队分享的消息标识生成文章也值得一读“融云技术共享:解密融云即时通讯产品的聊天消息标识生成策略”，美团的这篇文章也不错“美团技术共享:深度解密美团分布式标识生成算法”。
本文是题为“即时消息识别技术专题”系列文章的第一篇。专题的一般内容如下:
“即时消息标识技术专题(一):微信海量即时消息聊天消息序列号生成实践(算法原理)”(*本文)
"即时消息标识技术专题(二):微信群发即时消息聊天消息序列号生成实践(灾难恢复方案)"
即时消息标识技术主题(3):在融云解密即时消息产品的聊天消息标识生成策略
即时消息标识技术专题(四):美团分布式标识生成算法的深度解密
即时消息标识技术主题(5):开源分布式标识生成器的技术实现
2.文本简介
项目开始时，微信利用数据版本号建立了终端与后台之间的数据增量同步机制(注:具体实现方式为本文共享的消息序列号)，确保消息在发送时能够可靠地传递到对方手机，避免了大量潜在的家庭纠纷。到目前为止，微信已经走过了第五个年头，这种同步机制在需要数据同步的地方仍然发挥着核心作用，如消息传递、好友圈通知、好友数据更新等。
在这种同步机制的背后，需要一个高度可用和可靠的消息序列号生成器来生成用于同步数据的版本号(注意:由于序列号的自然递增，它可以用作版本号，但不限于使用版本号)。这个消息序列号生成器在微信中被称为seqsvr，它已经发展成为一个每天有数万亿个呼叫的重量级系统，其中每个序列号应用程序通常需要1毫秒，99.9%的呼叫需要不到3毫秒，该服务部署在数百个4核中央处理器服务器上。
本文将重点介绍微信消息序列号生成器seqsvr的算法原理和架构核心思想，以及随着业务量的快速增长seqsvr的架构演进(下期《微信技术共享:微信群发即时聊天消息序列号生成实践(容灾方案)》将重点关注分布式容灾方案，敬请关注)。
即时消息标识技术主题(一):在微信上生成批量即时消息聊天消息序列号的实践(算法原理)_1370849023895.jpg
3.关于作者
曾秦颂:微信高级工程师，负责微信基础设施、微信翻译引擎、微信围棋凤凰网，致力于高可用性、高性能后台系统的设计研发。2011年毕业于西安电子科技大学，之前在腾讯搜搜从事搜索架构和分布式数据库工作。
4.技术理念
微信服务器将为每个需要与客户端同步的数据分配一个唯一且递增的序列号(以下简称为序列号)作为数据的版本号(这利用了递增序列号的特性)。当客户端和服务器同步时，客户端将带来同步数据的最大版本号，后台将根据客户端的最大版本号和服务器的最大版本号计算待同步的增量数据，并返回给客户端。这不仅确保了客户机和服务器之间数据同步的可靠性，而且还极大地减少了同步过程中的冗余数据(如本文中所讨论的:“如何确保即时消息的“定时”和“一致性”？).
没有乐观锁定机制来生成版本号，但是使用独立的seqsvr来处理序列号操作:
1)一方面，因为服务有大量的序列查询需求——查询已经分配的最后一个序列，并且基于seqsvr的查询操作可以非常轻量级，避免了存储层上的大量io查询操作；
2)另一方面，微信用户的不同类型数据存在于不同的键值系统中，使用统一的序列号有助于避免重复开发，业务逻辑可以轻松判断用户的各类数据是否更新。
从seqsvr应用并用作数据版本号的序列有两个基本属性:
1)增量64位整数变量；
2)每个用户都有自己的64位序列空间。
例如，小明的当前应用程序的顺序是100，所以他的下一个应用程序的顺序可能是101或110，这必须大于前一个应用程序的100。和小红，她的序列是独立的小明的序列。如果她现在申请的序列是50，无论小明申请了多少次，都不会影响她下一次申请的值(可能是51)。
在本文中，使用独立于每个用户的64位序列系统来代替全局64位(或更高阶)序列。最大的原因是全局唯一序列将有一个非常严重的申请互斥的问题，并不容易实现高性能和高可靠性的架构。对于微信服务，每个用户独立的64位序列空间已经满足了服务需求。
目前，序列不仅用于终端与后台之间的数据同步，还广泛用于微信后台逻辑层的基础数据一致性缓存，大大减少了逻辑层对存储层的访问。虽然一个用于终端-后台数据同步，另一个用于后台缓存一致性保证，但情况大不相同。
然而，经过仔细分析，我们会发现这两种情况都使用序列的可靠增量特性来确保数据的一致性，这要求我们的seqsvr确保分配的序列稳定增长。一旦有了退路，它将不可避免地导致各种数据混乱和消息消失；此外，这两个场景非常常见。当我们使用微信时，我们会无意识地对应这两个场景:小明给小红发信息，小红拉住小明，小明发一圈失恋的朋友。简单的分手可能适用于许多序列。
目前，微信拥有上亿活跃用户，并且一直有大量的序列应用，这也是对seqsvr设计的一大挑战。那么，如何设计seqsvr的体系结构呢？seq SVR需要可靠的序列增量，并且能够承受大规模的访问。让我们从seqsvr的架构原型开始。
5.特定技术架构的原型
不管seqsvr的具体架构如何，它应该是一个64位的大数组，每个微信用户在这个大数组中都有一个8字节的专有空间，用户分配的最后一个序列:cur _ seq被放在这个网格中。当每个用户申请序列时，他只需要将用户的cur_seq+=1保存回数组并返回给用户。
即时消息标识技术主题(1):在微信上生成大量即时消息聊天消息序列号的实践(算法原理)_a.jpg
▲图1:小明申请序列，返回101
5.1预分配中间层
在大规模的访问下，任何看似简单的事情都不会变得容易。如上所述，seqsvr需要确保分配的序列递增(数据是可靠的)，并且它还需要满足大量的访问(每天接近万亿次访问)。如果数据是可靠的，我们可以很容易地想到将数据保存到硬盘上，但是根据目前每秒钟数千万次的访问(大约10 7 QPS)，基本上没有硬盘系统可以支持它。
背景架构设计通常是一种权衡的哲学，考虑是否可以针对不同的场景降低某些需求，以换取其他的改进。在仔细考虑我们的需求之后，我们只要求增量，而不是连续的，也就是说，允许大的跳跃(例如，分配的序列:1，2，3，10，100，101)。
所以我们实施了一个简单而优雅的策略:
1)最新分配序列:cur _ seq，分配上限:max _ seq存储在存储器中；
2)分配序列时，将cur_seq++与max_seq进行比较:如果cur_seq > max_seq，则将分配上限提高一个步长max_seq += step，并保持max _ seq；
3)重新启动时，读取持久最大值并将其分配给当前值。
即时消息标识技术主题(1):在微信上生成大量即时消息聊天消息序列号的实践(算法原理)_b.jpg
▲图2:小明、小红和小白各申请一个序列，但只有小白的max_seq增加了100步
这样，通过增加一个预分配序列的中间层，在保证序列不后退的前提下，大大提高了分配序列的性能。在实际应用中，当每次升级的步长为10000时，永久硬盘IO的数量从约10 7 QPS减少到约10 3 QPS，在可接受的范围内。在正常操作中，分配的序列按顺序递增。只有在机器重新启动后，第一次分配的序列才会产生相对较大的跳转，跳转大小取决于步长。
5.2分号段共享存储
由请求引起的硬盘IO问题已经解决，可以支持服务的顺利运行，但是这个模型仍然存在一个问题:重启时需要读取大量的max_seq数据并加载到内存中。
我们可以简单地计算出，在当前uid(用户唯一id)上限为2 32，最大空间为8字节的情况下，总数据大小为32GB，从硬盘加载需要很长时间。另一方面，为了数据的可靠性，需要一个可靠的存储系统来存储max_seq数据，并且在重新启动时通过网络从可靠的存储系统加载数据。如果max_seq数据太大，重新启动时会花费大量时间进行数据传输，导致一段时间无法使用。
为了解决这个问题，我们引入了截面的概念。具有相邻用户标识的用户属于同一区段，并且同一区段中的用户共享一个最大值序列，这极大地减小了最大值序列数据的大小并减少了输入输出次数。
即时消息标识技术主题(1):在微信上生成大量即时消息聊天消息序列号的实践(算法原理)_c.jpg
▲图3:小明、小红和小白属于同一个区段，它们共有一个最大值序列。当每个人都申请一个序列时，只有小白打破了最大序列上限，需要更新最大序列并保持它
目前，一段seqsvr包含100，000个uid，最大序列数据只有300+KB，这为我们重新从可靠的存储系统中读取最大序列数据奠定了基础。
5.3项目实现
工程实施对上述两种策略进行了一些调整，主要是为了数据可靠性和灾难隔离:
1)将存储层和缓存中间层分为两个模块:StoreSvr和AllocSvr。StoreSvr是存储层，它使用多机NRW策略来确保数据在持久化后不会丢失；AllocSvr是缓存的中间层，部署在多台机器上。每个AllocSvr负责几个段的序列分配，并分发大量序列应用程序请求。
2)整个系统按照uid范围划分为若干个集合，每个集合都是一个完整独立的StoreSvr+AllocSvr子系统。子集合设计的目的是进行灾难隔离，一个集合的失败只会影响集合中的用户，而不会影响其他用户。
即时消息标识技术主题(1):在微信上生成大量即时消息聊天消息序列号的实践(算法原理)
▲图4:原型架构图
6.这个总结
seqsvr的基本原型已经完成，它是一个简单而优雅的模型，可靠而稳定地支持了微信在过去五年的快速发展。在过去的五年里，访问的次数一再增加，seqsvr本身也大大小小地进行了重建，但seqsvr的等级结构没有改变，在可预见的未来将保持不变。
生产环境的原型和版本之间有一定的差距，主要的差距在于容灾。微信等即时通讯应用对系统可用性非常敏感，seqsvr处于发送和接收信息、朋友圈和其他功能的关键路径上，这需要非常高的可用性。这是长时间停止服务时，在几分钟内编写故障报告的节奏。
----------------------------------------------------------------------------------
哇谷im_im即时通讯_私有云_公有云-哇谷云科技官网-JM沟通
IM下载体验 - 哇谷IM-企业云办公IM即时聊天社交系统-JM 沟通下载
IM功能与价格 - 哇谷IM-提供即时通讯IM开发-APP搭建私有化-公有云-私有化云-海外云搭建
新闻动态 - 哇谷IM-即时通讯热门动态博客聊天JM沟通APP
关于哇谷-哇谷IM-提供企业即时通讯IM开发-语音通话-APP搭建私有化-公有云-私有化云-海外云搭建
联系我们 - 哇谷IM-即时通讯IM私有化搭建提供接口与SDK及哇谷云服务
公有云和私有云之间有什么区别？类似融云、环信云、网易云、哇谷云？