Jack Jiang

我的最新工程MobileIMSDK:http://git.oschina.net/jackjiang/MobileIMSDK
posts - 493, comments - 13, trackbacks - 0, articles - 1

     摘要: 本文原题“WebSocket:5分钟从入门到精通”,作者“程序猿小卡_casper”,原文链接见文末参考资料部分。本次收录时有改动。1、引言自从HTML5里的WebSocket出现后,彻底改变了以往Web端即时通讯技术的基础通道这个“痛点”(在此之前,开发者们不得不弄出了诸如:短轮询、长轮询、Comet、SSE等技术,可谓苦之...  阅读全文

posted @ 2020-10-14 14:40 Jack Jiang 阅读(384) | 评论 (0)编辑 收藏

     摘要: 本文由融云技术团队原创投稿,作者是融云WebRTC高级工程师苏道,转载请注明出处。1、引言在一个典型的IM应用里,使用实时音视频聊天功能时,视频首帧的显示,是一项很重要的用户体验指标。本文主要通过对WebRTC接收端的音视频处理过程分析,来了解和优化视频首帧的显示时间,并进行了总结和分享。(本文同步发布于:http://www.52im.net/thread-3169-1-1.html)2、什么是...  阅读全文

posted @ 2020-09-28 22:17 Jack Jiang 阅读(263) | 评论 (0)编辑 收藏

本文引用自“蚂蚁金服科技”公众号,原文由支付宝技术团队原创分享。 本次收录时有改动。

1、引言

最早接触2维码扫码功能,是在2011年,那会移动互联网正是起步阶段,大家都感觉智能手机可以更强大,但到底要做些什么功能,都是在探索和创新。2维码扫描功能就是这些创新功能之一。

当然,2维码扫描说到底还是图像识别,这种技术不是一般的公司能搞定的,所以大家用的最多的2维码扫描库就是ZXing。这个库,很多人应该非常熟悉,用过这个库的人,基本都记住了下面这个图片(ZXing的logo)。

▲ ZXing工程的logo

这个库的使用前题就是需要手机摄像头有自动对焦功能,那会手机成本还没现在这么低,所以自动对焦功能不是所有手机都具备,也就限制了2维码扫码功能在一些较低端的手机上的使用,同时也制约了扫码功能的普及。

后来的事情大家都知道了,微信这种社交IM越来越受欢迎,微信里可以用来扫码加好友的“扫一扫”功能,让2维码扫描功能几乎变成了IM软件的标配。

 

▲ 早期微信里的“扫一扫”功能

现在的微信,不仅可以扫2维友加好友,还可以扫码支付以及各种图像识别方面的功能,越做越丰富。2维码扫码功能从一个单一的图像识别技术,逐渐演变成了移动线联网的入口功能。

从去年开始,微信对2维码扫描功能进行了升级,不仅可以在UI上让用户知道被扫描2维码的中心点,还能同时识别最多3个2维码,相当强大。

 

▲ 现在的微信可以同时识别最多3个2维码(注意绿点)

如上图所示,原本大家都习以为常的2维码扫描功能,原来还可以做的这么友好。

正好看到支付宝分享的这篇2维码扫描优化文章,市面上真正分享这方面的技术的文章几乎没有,而2维码扫码加友作为IM中最常见的功能之一,对于即时通讯网的开发者来说,虽然不需要自已从底层开发,但了解这方面的知识,还是很有必要的。

本文要分享的是支付宝针对2维码扫描功能,在2维码残缺、变形、变色等等恶劣条件下,是如何提升扫码识别率、识别速度的技术实践总结。希望能带给你启发。

学习交流:

- 即时通讯/推送技术开发交流5群:215477170[推荐]

- 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM

- 开源IM框架源码:https://github.com/JackJiang2011/MobileIMSDK

(本文同步发布于:http://www.52im.net/thread-3150-1-1.html

2、技术背景

随着支付宝的线下场景不断扩大,收钱码、口碑、共享单车、充电宝、停车缴费等产品让我们的生活越来越便利。

二维码因为成本低、兼容性好成为了线上线上最主要的连接工具,也因此面临更多新的挑战。

因为二维码是一种点阵式信息编码方式,任何视觉上的缺损、弯曲以及光线作用都会极大的影响识别成功率,如果识别困难也就意味着用户可能选择放弃,影响支付体验也影响用户心智。

用户扫码体验的最关键的主要有以下几个因素:

  • 1)识别率:这是扫码服务的基础指标,识别率能直接体现识别能力,识别率如果无法提高意味着大量的用户将无法使用更便捷的服务;
  • 2)识别耗时:包括 app 启动耗时以及图像识别耗时,这是衡量一个用户从点击 app 到正确识别到内容耗时,每增加 1s,将有相当大量的用户放弃等待并离开;
  • 3)精准反馈:识别结果不仅需要及时反馈给用户,还需要非常精准,特别是在目前线下有多个二维码的场景下,需要避免用户二次操作。

本文将从以上三个方面,分享支付宝扫码技术团队是如何为用户打造一个又准又快又稳的极致扫码体验。

我们对用户反馈进行了大量统计分析,发现绝大部分识别失败都是因为二维码并不标准,并且很遗憾的是在使用我们早期的扫码版本进行识别率测试时发现识别率只有 60%。下面的文字,将首先从提高识别率的方向着手。

3、提高识别率策略1:优化桩点查找算法长宽比耐受

以往的扫码算法,检查长宽比例时允许差异 40%,但是由于使用前向误差,判断结果跟长宽的先后顺序相关,这会导致有些长宽比失调的码,横着扫不出来,但是旋转 90 度竖着却能扫出来了(^OMG^)。

优化策略总结:

  • 1)通过修改长宽比的判定规则,长宽比将不再受先后顺序影响;
  • 2)对于已知长度,修改规则将可接受的宽度范围扩大,增强长宽比的耐受。

在我们对比测试集中,识别率提高了 1% 左右。

4、提高识别率策略2:新增1:5:1桩点识别模式模式

在一张图片中,要找到二维码,关键在找二维码特征定位点: 

三个角的回字型图案,这就是二维码特征定位点。

中间区域的黑白色块比例是1:1:3:1:1:

以往的扫码算法,桩点识别是通过状态机 查找11311模式后 取中间位置确定x位置(此时扫描线在第一行11311比例处)在x位置纵向搜索11311模式, 确定y位置再以 (x,y) 位置横向搜索11311比例,修正x位置。

这种模式在桩点污损的情况下,识别能力较差只要在任何一次11311模式搜索中遇到干扰点,哪怕是一个像素的椒盐噪声也能使桩点查找失败。(支付宝蓝的桩点,会在蓝色区域产生大量噪点,导致识别率低下)

为此,我们新增了一种桩点识别方式。在状态机达到151模式的时候,开始尝试确认桩点。(此时扫描线在第一行151比例处)。

优化效果:

  • 1)新的查找方法将不再受桩点中心或边缘部分被污损的影响,支付宝蓝色桩点码识别率明显提升;
  • 2)修改后识别率整体提升了接近 1%,但识别失败的耗时有所提升。

5、提高识别率策略3:添加一种对角线过滤规则

在枚举所有可能桩点组合 O(N^3) 之前,对所有可疑桩点进行一次对角线检查过滤。由于桩点对角线也应该满足 11311模式 ,用这个规则做一次过滤可疑有效减少运算量,也就有效降低了识别成功和失败的耗时。

6、提高识别率策略4:基于 Logistic Regression 的二维码分类器

在以往的扫码算法中在拿到三个桩点后,基于夹角,长度偏差,单位长度查三个数值,用简单公式计算得到阈值,判断是否为可能的二维码,误判概率较大。

为此,我们引入机器学习中的逻辑回归算法模型。

基于支付宝丰富的二维码数据集,训练出逻辑回归模型,作为二维码分类器,明显降低了误判概率,也将明显降低无二维码时识别失败的耗时。

7、提高识别率策略5:修改跳行扫描的间隔数

由于输入的相机帧分辨率高,像素点多,运算量大,以往的扫码算法在水平跟垂直方向跳行采样进行计算。但在实际运算中,由于跳过了太多列,错过了11311模式中某些1位置的点,导致桩点查找失败。

我们通过将跳行计算行数修改为可配置项,通过线上 AB 灰度测试得到最合适的跳行策略,整体配置此跳行策略后,识别率得到明显提升。

上述优化在测试集的表现: 

综上优化:扫码核心识别能力,在7744张图片测试集上提高了6.95个百分点。

8、特殊策略优化

除此上述通用扫码优化之外,我们还对特殊场景扫码能力进行提高。

8.1 畸变?不怕不怕!

线下场景复杂多变。饮料瓶身上变形的二维码、超市小票卷起边角弯曲的二维码、路边小贩凹凸不平甚至折叠的二维码......这些畸变的二维码容易增加识别难度,甚至导致识别失败。

以往的扫码算法抗畸变策略中,先用透视变换关系建立映射关系。

优点是:适应性好,满足大多数应用场景。

不足也明显:对 Version 1 的码,因为映射关系退化为仿射变换,效果较差,手机必须和码平面平行才能方便识别。当物料表面不是平面的时候,效果较差。

优化策略:

  • 1)假设采样坐标系到二维码坐标系遵守一个更复杂的映射关系,并且假设物料表面的卷曲较小,通过使用二次函数可以较好的拟合这个映射关系;
  • 2)实际发票上的二维码版本普遍大于等于 7,高版本二维码具有多个辅助定位点,更利于构造二次映射表;
  • 3)基于以上推论,使用新的映射代替旧的透视变换,进行更精准的采样。

用新的策略,发票码这个场景的二维码识别能力提升明显。

▲注意:由于采用了增强算法,请对准二维码稍作等待

样本测试结果:

8.2 容错识别能力提升

商户或者供应商生成二维码后,通常会在二维码的中间部分贴上 Logo,这部分有可能会使二维码 Decode 时出错。

优化策略:

对于采样后拿到的 BitMatrix,对于中间部分一块矩形区域内的点,采用某些策略来改变中间点的值,使它能够通过容错边界的检查。目前采用两种策略,第一种是反转,第二种是每一个点随机取值。目前所取的矩形区域是长、宽的四分之一。

通过此项优化后,扫码的容错能力也得到明显提升。

9、更小的识别耗时

针对识别效率,我们使用了GPU计算二值化,降低识别单帧耗时。

所谓图像二值化就是将图像上的像素点的灰度值设置为 0 或 255,也就是将整个图像呈现出明显的只有黑和白的视觉效果。下图左边为原图,右边是二值化处理过的图。

在扫码算法解码前,有二值化计算,图像的二值化计算能使图像中数据量大为减少,并弱化图像模糊、颜色对比度不强、光线过强/太弱、图像污损等情况下其他信息的干扰,更利于检测识别。

传统算法是在 CPU 上进行二值化运算,非常消耗 CPU 资源,但其实 GPU 更擅长大规模并行计算,所以我们选择使用 GPU 来做二值化计算。在安卓平台上使用 RenderScript,iOS 平台上使用 Metal,都是很底层的框架。

1)iOS优化结果:统一电池、角度、光线等环境变量, 在iPhone6上测试扫码核心5种摄像头二值化算法。

表现如下: 

 

可以看出,在图像二值化方面 Metal 有相当高的优势,相比原来的单纯 CPU 处理快了接近 150%, 同时降低了近50个百分点的CPU资源。

2)Andriod优化结果:由于Android机型众多,我们抽取了线上数据,可以看到GPU 在二值化处理中显著降低了单帧耗时30%以上。 

10、算法分级、场景分类、科学调度

线下物料千奇百怪,扫码算法为了解决一些不理想的场景,如二维码有遮挡、污损、模糊或角度很不好的特殊情况,需要使用一些比较耗时但比较强大的算法,但普通情况不需要这些算法。

所以,我们对识码算法定了优先级,通过时间推移、跳帧触发等方式调度。

优先级:

  • 1)高优先级:每帧执行;
  • 2)中优先级:降帧率执行;
  • 3)低优先级:低帧率执行。

不同优先级的功能执行时机可配置。不同功能属于哪个优先级可配置

特殊场景算法能力:

  • 1)反色码识别能力;
  • 2)容错边界码识别能力;
  • 3)污损桩点识别能力等;
  • 4)条码识别能力。

附录:更多阿里团队分享的文章

社交软件红包技术解密(七):支付宝红包的海量高并发技术实践

阿里钉钉技术分享:企业级IM王者——钉钉在后端架构上的过人之处

来自阿里OpenIM:打造安全可靠即时通讯服务的技术实践分享

淘宝技术分享:手淘亿级移动端接入层网关的技术演进之路

阿里技术分享:深度揭秘阿里数据库技术方案的10年变迁史

阿里技术分享:阿里自研金融级数据库OceanBase的艰辛成长之路

作者谈《阿里巴巴Java开发手册(规约)》背后的故事

淘宝技术分享:手淘亿级移动端接入层网关的技术演进之路

《阿里巴巴Android开发手册(规约)》背后的故事

手机淘宝消息推送系统的架构与实践(音频+PPT) [附件下载]

重磅发布:《阿里巴巴Android开发手册(规约)》[附件下载]

阿里技术结晶:《阿里巴巴Java开发手册-v1.6.0-泰山版》[附件下载]

(本文同步发布于:http://www.52im.net/thread-3150-1-1.html

posted @ 2020-09-25 14:29 Jack Jiang 阅读(295) | 评论 (0)编辑 收藏

本文在编写时参考了博客作者“鹿呦呦”和在线课程“即时消息技术剖析与实战”的相关资料,一并表示感谢。

1、引言

随着移动互联网络的发展,IM技术的应用已经不仅限于聊天应用本身,它早已融入各种应用形态中,比如:直播中的主播互动、联网游戏中的玩家互动、外卖/打车应用中的实时位置共享、在线教育应用中的互动白板等。

在这些风格迥异的应用场景下,IM技术所呈现出来的功能形态虽有不同,但“实时性”这个技术特征并无区别。

那么,对于技术门外汉来说,到底什么是IM的“实时性”?该如何理解它?这就是本文想要讨论的主题。

区别于强大的原生应用,Web端的IM系统,在很长一段时间内想实现真正的“实时性”,是非常困难的,因为无法直接使用UDP、TCP通信协议,在HTML5中的WebSocket出现之前,Web端几乎没有真正意义上的“双向实时通信”这种技术存在。

正因为如此,理解Web端即时通信技术的演进,也就自然而然能循序渐进地体会到IM系统中的“实时性”了。所以本文将围绕Web端即时通讯技术,为你展开IM“实时性”这个话题。

友情提示:本系列文章侧重于理论概念的讲述,篇幅有限,点到即止,如需系统、深入、具体地学习IM技术的方方面面,请从此文入手:《新手入门一篇就够:从零开发移动端IM》(史诗级文章,适合从入门到放弃)。

学习交流:

- 即时通讯/推送技术开发交流5群:215477170 [推荐]

- 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM

- 开源IM框架源码:https://github.com/JackJiang2011/MobileIMSDK

(本文同步发布于:http://www.52im.net/thread-3143-1-1.html

2、系列文章目录

IM开发快速入门(一):什么是IM系统?

IM开发快速入门(二):什么是IM系统的实时性?》(* 本文

《IM开发快速入门(三):什么是IM系统的可靠性? (稍后发布)》

《IM开发快速入门(四):什么是IM系统的一致性? (稍后发布)》

《IM开发快速入门(五):什么是IM系统的安全性? (稍后发布)》

《IM开发快速入门(六):什么是IM系统的的心跳机制? (稍后发布)》

《IM开发快速入门(七):如何理解并实现IM系统消息未读数? (稍后发布)》

《IM开发快速入门(八):如何理解并实现IM系统的多端消息漫游? (稍后发布)》

3、短轮询技术

在早期的Web时代,技术的创造者们无法预见如今各种选进的技术应用形式,他们认为数据只是用来“看”的,也数据的获取基本就是“请求 -> 响应”这种一问一答形式。包括我们平时浏览的各种门户网站都是采用的“请求响应”模式。

这种依赖于用户“主动”请求的数据获取模式,如果想实现IM系统,是无法即时获得最新的聊天消息的,因为用户并不知道新消息什么时候到来,而服务端也没有办法主动通知用户。

在这个时期,虽然技术和思路都受当时技术水平的限制,但IM总不能不做吧。

于是,一种被称为“短轮询”的数据获取模式出现了。在“短轮询”模式下,IM客户端定时轮询服务端,以便让用户知道是否有新的聊天消息存在。

这种模式下,服务端收到请求后,即刻查询是否存在新消息,有就返回给客户端,没有则返回空并立即关闭连接。

相较于前面用户需要“手动”去刷新页面的方式,这种模式只是将用户的“手动”变为“自动”而已,技术本质并没有发生任何实质性改变。

短轮询这种模式,就好比旧时代一个等待重要邮件的人,他需要每天自已跑到邮局,主动去问是否有自己的信件,有就拿回家,如果没有,则第二天继续去问。一来一去,非常低效。

技术原理总结如下图所示:

短轮询这种模式有好处,也有坏处。

好处是:

  • 1)技术简单,容易实现;
  • 2)可维护性强,因为它没什么复杂的。

坏处是:

  • 1)因为无法预知数据是否存在,所以多数请求是无用的,浪费计算资源;
  • 2)为了提升实时性,高频率的请求会加大服务端的性能负载。

总结一下就是,短轮询这种模式对于IM技术大拿来说,显的非常low,因为技术实现实在是简单粗暴。

4、长轮询技术

正如你所见,用短轮询技术来保证IM的实时性,确实难说优雅。不过,这难不倒无所不能的程序员,一种被称为“长轮询”的数据获取模式出现了。

从技术上来说,长轮询实现的IM相较于短轮询最大的改进在于:短轮询情况下,服务端不管有没有新消息,请求结束就会立即断开连接。而长轮询时,如果本次请求没有新消息发生,糨不会马上断开连接并返回,而是会将本次连接“挂起”一段时间,如果在这段“挂起”时间内有新的聊天消息出现,就能马上读取并立即返回给客户端,接着结束本次连接。一段时间后又会再次发起请求,如此周而复始。

长轮询这种模式,拿上节等待邮件的这个例子来说,就好比收信的人每天到邮局去问是否有信件,如果没有,他不马上回家,而是在邮局待上一段时间,如果这段时间过去了,还是没有,就先回家,接着第二天再来。

技术原理总结如下图所示: 

长轮询的优点是:

  • 1)相较于短连询,一定程度降低了服务端请求负载;
  • 2)相较于短连询,实时性有提升,因为它是主动“等”消息。

长轮询的缺点是:

  • 1)长论询模式下,连接“挂起”的这段时间内,服务端需要配合开启单独的消息查询线程,仍然存在无用功;
  • 2)相较于短连询模式,在一次长轮询结束、下次轮询发起前的窗口期内,仍然存在“实时性”盲区。

实际上,在Web端即时通讯技术里,长轮询有个专业的术语叫“Comet”,有兴趣可以详细学习《Comet技术详解:基于HTTP长连接的Web端实时通信技术》。

5、轮询无法实现真正的“实时性”

对于Web端即时通讯技术来说,上面提到的无论是短轮询,还是长轮询,它们都存在“实时性”盲区。

我们回到上两节介绍的短轮询和长轮询技术原理图。

先看看短轮询这张图:

很明显,短轮询在每次轮询结束和下次轮询开始的间隔期内,是无法感知到新消息的,这也便形成了“实时性盲区”。换句话说,短轮询技术在“实时性盲区”内,无法做到“实时”。

再来看看长轮询:

跟短轮询道理一样,长轮询在每次轮询结束和下次轮询开始的间隔期,依然会形成“实时性盲区”。

要理解纠结轮询技术的实时性缺陷,就得了解它们背后的技术——HTTP协议了。

HTTP协议设计的目的,就是为了实现“请求--响应”这种模式的数据交互,也就是众所周之的“短连接”设计。而无论是短轮询还是长轮询,都跳不出HTTP的先天技术逻辑(请求--响应--断开)。

所以,归根到底,想要基于HTTP协议来实现IM,要达到真正的“实时性”,是相当勉强的。因为HTTP设计的目的,就是用“短连接”来简化传统TCP长连接通信带来的复杂性,而IM的实时性恰好要用到的又是TCP的长连接特性,所以这就是个悖论。

要真正实现Web端的IM“实时性”,肯定不能强行HTTP上做文章了,我们需要新的技术。

6、WebSocket让Web端IM真正的“实时性”变成可能

好消息是,HTML5中带来了WebSocket技术。WebSocket是真正的全双式双向通信技术(详见:《WebSocket从入门到精通,半小时就够!》)。

下图上旧式轮询技术跟WebSocket的对比图:

从上图可以看出:

  • 1)轮询技术一问一答,在下一个请求发起之前,存在“实时性”盲区;
  • 2)WebSocket一旦建立连接后,数据可以随时双向通信(即客户端可以随时向服务端发消息,服务端也可以随时通知客户端有新消息)。

举个例子就是:轮询技术相当于传统的邮件传递方法(你得自已去邮局问有没有新邮件),而WebSocket相当于现代的电话系统,只要你拨通后,随时可以实时收听到对方的声音,对方也能随时收听到你的声音。完美!

总结一下WebSocket 的优点是:

  • 1)真正的实时性:支持客户端与服务端真正的双向实时通信;
  • 2)大幅降低负载:少了轮询技术中高频率无用的请求,可大大降低服务端QPS压力;
  • 3)网络开销降低:一次连接,随时使用,再也不用轮询技术中每次发起HTTP请求(随之而来的是每次HTTP的大量冗余协议头信息等)。

7、本文小结

本文以Web端即时通讯技术的演进为例,从短轮询到长轮询,再到WebSocket,理论联系实际地讲解了Web端IM“实时性”的技术变迁,从而帮助读者理解IM中“实时性”这个最为关键的技术特征。

附录:更多Web端即时通讯资料

新手入门贴:史上最全Web端即时通讯技术原理详解

Web端即时通讯技术盘点:短轮询、Comet、Websocket、SSE

SSE技术详解:一种全新的HTML5服务器推送事件技术

Comet技术详解:基于HTTP长连接的Web端实时通信技术

新手快速入门:WebSocket简明教程

WebSocket详解(一):初步认识WebSocket技术

WebSocket详解(二):技术原理、代码演示和应用案例

WebSocket详解(三):深入WebSocket通信协议细节

WebSocket详解(四):刨根问底HTTP与WebSocket的关系(上篇)

WebSocket详解(五):刨根问底HTTP与WebSocket的关系(下篇)

WebSocket详解(六):刨根问底WebSocket与Socket的关系

socket.io实现消息推送的一点实践及思路

LinkedIn的Web端即时通讯实践:实现单机几十万条长连接

Web端即时通讯技术的发展与WebSocket、Socket.io的技术实践

Web端即时通讯安全:跨站点WebSocket劫持漏洞详解(含示例代码)

开源框架Pomelo实践:搭建Web端高性能分布式IM聊天服务器

使用WebSocket和SSE技术实现Web端消息推送

详解Web端通信方式的演进:从Ajax、JSONP 到 SSE、Websocket

MobileIMSDK-Web的网络层框架为何使用的是Socket.io而不是Netty?

理论联系实际:从零理解WebSocket的通信原理、协议格式、安全性

微信小程序中如何使用WebSocket实现长连接(含完整源码)

八问WebSocket协议:为你快速解答WebSocket热门疑问

快速了解Electron:新一代基于Web的跨平台桌面技术

一文读懂前端技术演进:盘点Web前端20年的技术变迁史

Web端即时通讯基础知识补课:一文搞懂跨域的所有问题!

Web端即时通讯实践干货:如何让你的WebSocket断网重连更快速?

WebSocket从入门到精通,半小时就够!

>> 更多同类文章 ……

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

▲ 本文在公众号上的链接是:点此进入,原文链接是:http://www.52im.net/thread-3143-1-1.html

posted @ 2020-09-18 13:56 Jack Jiang 阅读(205) | 评论 (0)编辑 收藏

1、引言

在中大型IM系统中,聊天消息的唯一ID生成策略是个很重要的技术点。不夸张的说,聊天消息ID贯穿了整个聊天生命周期的几乎每一个算法、逻辑和过程,ID生成策略的好坏有可能直接决定系统在某些技术点上的设计难易度。

有中小型IM场景下,消息ID可以简单处理,反正只要唯一就行,而中大型场景下,因为要考虑到分布式的性能、一致性等,所以要考虑的问题点又是另一回事。

总之就是,IM的消息ID生成这件事,可深可浅,看似简单但实际可探索的边界可以很大,这也是为什么即时通讯网为此专门整理了《IM消息ID技术专题》系列文章的原因。做技术所谓厚积薄发,了解的越多,你的技术可操作空间也就越大,希望随着这个系列文章的阅读,可以为你在ID生成这一块的技术选型带来更多有益的启发。

另外,因为即时通讯网主要关注的是即时通讯方面的系统开发,但并不意味着这个系统文章只适用于IM或消息推送等实时通信系统,它同样适用于其它需要唯一ID的应用中。

本文将要分享的是滴滴开源的分布式ID生成器Tinyid的技术原理、使用方法等等,希望能进一步为你打开这方面的技术视野。

学习交流:

- 即时通讯/推送技术开发交流5群:215477170[推荐]

- 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM

- 开源IM框架源码:https://github.com/JackJiang2011/MobileIMSDK

(本文同步发布于:http://www.52im.net/thread-3129-1-1.html

2、专题目录

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

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

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

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

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

IM消息ID技术专题(五):开源分布式ID生成器UidGenerator的技术实现

IM消息ID技术专题(六):深度解密滴滴的高性能ID生成器(Tinyid)》(* 本文

3、什么是Tinyid?

Tinyid是滴滴用Java开发的一款分布式id生成系统,基于数据库号段算法实现。

Tinyid是在美团的ID生成算法Leaf的基础上扩展而来,支持数据库多主节点模式,它提供了REST API和Java客户端两种获取方式,相对来说使用更方便。不过,和美团的Leaf算法不同的是,Tinyid只支持号段一种模式(并不支持Snowflake模式)。(有关美团的Leaf算法,可以详读《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法

Tinyid目前在滴滴客服部门使用,且通过tinyid-client方式接入,每天生成的是亿级别的id。性能上,据称单实例能达到1千万QPS。

它的开源地址是:

PS:滴滴在Tinyid工程页面写了一句话,“tinyid,并不是滴滴官方产品,只是滴滴拥有的代码”,我语文不好,这句该怎么理解呢?

4、Tinyid的主要技术特性

主要特性总结一下就是:

  • 1)全局唯一的long型ID:即id极限数量是2的64次方;
  • 2)趋势递增的id:趋势递增的意思是,id是递增但不一定是连续的(这跟微信的ID生成策略类似);
  • 3)提供 http 和 java-client 方式接入;
  • 4)支持批量获取ID;
  • 5)支持生成1,3,5,7,9…序列的ID;
  • 6)支持多个db的配置。

适用的场景:只关心ID是数字,趋势递增的系统,可以容忍ID不连续,可以容忍ID的浪费。

不适用场景:像类似于订单ID的业务,因生成的ID大部分是连续的,容易被扫库、或者推算出订单量等信息。

另外:微信的聊天消息ID生成算法也是基于号段、趋势递增这种逻辑,如果有兴趣,可以详见:《IM消息ID技术专题(一):微信的海量IM聊天消息序列号生成实践(算法原理篇)》。

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)方法产生。

具体的代码实现,有兴趣可以直接阅读源码:

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该怎么调用?

关于怎么调用。鉴于篇幅原因,就不再具体去写了,有兴趣的话,可以读一下这篇《Tinyid:滴滴开源千万级并发的分布式ID生成器》。

9、参考资料

[1] 面试总被问分布式ID怎么办? 滴滴(Tinyid)甩给他

[2] Tinyid:滴滴开源千万级并发的分布式ID生成器

[3] tinyid工程中文readme

[4] 滴滴开源的Tinyid如何每天生成亿级别的ID?

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

新手入门一篇就够:从零开发移动端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开发干货分享:如何优雅的实现大量离线消息的可靠投递

IM开发干货分享:有赞移动端IM的组件化SDK架构设计实践

>> 更多同类文章 ……

本文已同步发布于“即时通讯技术圈”公众号,欢迎关注:

▲ 本文在公众号上的链接是:点此进入,原文链接是:http://www.52im.net/thread-3129-1-1.html

posted @ 2020-09-08 22:31 Jack Jiang 阅读(357) | 评论 (0)编辑 收藏

     摘要: 本文由小米信息技术团队研发工程师陈刚原创,原题“当我们在谈论高并发的时候究竟在谈什么?”,为了更好的内容呈现,即时通讯网收录时有修订和改动。1、引言在即时通讯网社区里,多是做IM、消息推送、客服系统、音视频聊天这类实时通信方面的开发者,在涉及到即时通讯技术时聊的最多的话题就是高并发、高吞吐、海量用户。代码还没开始写,就考虑万一哪天这IM用户量破百万、千万该怎么办的问题,是多...  阅读全文

posted @ 2020-09-03 23:08 Jack Jiang 阅读(295) | 评论 (0)编辑 收藏

本文内容编写时,参考了网上的资料,详见“参考资料”部分,感谢分享者。

1、引言

这个系列文章已经整理了10篇,但都没有涉及到具体的红包算法实现,主要有以下两方面原因。

一方面是各社交/IM产品中的红包功能同质化严重,红包算法的“可玩性”便是“核心竞争力所在”,这是同质化功能的差异化竞争思路,不会随便公开。

另一方面,市场上还存在各种抢红包插件这类灰产存在,一旦公开这些算法,很可能又被这帮插件开发者们搞出什么幺蛾子。

所以,这样的情况下,如果要做社交/IM产品中的红包功能,红包随便算法该怎么实现,基本上只能自已琢磨,很难找到大厂算法直接套用。

本着即时通讯网一贯的im知识传播精神,我收集整理并参考了大量的网上资料,综合了比较靠谱的信息来源,便有了本文。本文根据有限的资料,分享了微信红包随机算法实现中的一些技术要点,并整理了两种比较靠谱的红包算法实现思路(含可运行的实现代码),希望能给你的红包算法开发带来启发。

申明:本文资料整理自网络,仅供学习研究之用,如有不妥,请通知作者。

学习交流:

- 即时通讯开发交流5群:215477170 [推荐]

- 移动端IM开发入门文章:新手入门一篇就够:从零开发移动端IM

- 开源IM框架源码:https://github.com/JackJiang2011/MobileIMSDK  [推荐]

本文已同步发布于“即时通讯技术圈”公众号,欢迎关注:

▲ 本文在公众号上的链接是:点此进入,原文链接是:http://www.52im.net/thread-3125-1-1.html

2、系列文章

3、微信红包算法要点汇总

这是目前能找到的仅有的一份,有微信团队人员参与的微信红包算法技术要点的讨论资料。分享于2015年,差不多是微信红包刚火没多久,大概是微信技术团队的人当时没有现在这些技术之外的顾虑,所以作了有限的分享,资料难得,本次重新整理了一下,可以作为参考资料使用。以下是资料正文。

资料来源:来自InfoQ的某架构群的技术讨论,由朱玉华整理(个人博客是:zhuyuhua.com(目前已无法访问))。

资料背景:起因是有朋友在朋友圈咨询微信红包的架构,于是在微信团队成员参与讨论的情况下,我(指“朱玉华”)整理了这次讨论的技术要点,也就是下面的内容(内容为问答形式)。

3.1、算法实现的技术要点

问:微信的金额什么时候算?

答:微信金额是拆的时候实时算出来,不是预先分配的,采用的是纯内存计算,不需要预算空间存储。

为什么采取实时计算金额?原因是:实时效率更高,预算才效率低下。预算还要占额外存储。因为红包只占一条记录而且有效期就几天,所以不需要多大空间。就算压力大时,水平扩展机器是。

问:关于实时实时性,为什么明明抢到红包,点开后发现没有?

答:2014年的红包一点开就知道金额,分两次操作,先抢到金额,然后再转账。

2015年的红包的拆和抢是分离的,需要点两次,因此会出现抢到红包了,但点开后告知红包已经被领完的状况。进入到第一个页面不代表抢到,只表示当时红包还有。

问:关于分配算法,红包里的金额怎么算?为什么出现各个红包金额相差很大?

答:随机,额度在 0.01 和剩余平均值 2 之间。 例如:发 100 块钱,总共 10 个红包,那么平均值是 10 块钱一个,那么发出来的红包的额度在 0.01元~20元之间波动。

当前面 3 个红包总共被领了 40 块钱时,剩下 60 块钱,总共 7 个红包,那么这 7 个红包的额度在:0.01~(60/7 * 2)=17.14之间。

注意:这里的算法是每被抢一个后,剩下的会再次执行上面的这样的算法(Tim老师也觉得上述算法太复杂,不知基于什么样的考虑)。

这样算下去,会超过最开始的全部金额,因此到了最后面如果不够这么算,那么会采取如下算法:保证剩余用户能拿到最低1分钱即可。

如果前面的人手气不好,那么后面的余额越多,红包额度也就越多,因此实际概率一样的。

问:红包的设计

答:微信从财付通拉取金额数据过来,生成个数/红包类型/金额放到redis集群里,app端将红包ID的请求放入请求队列中,如果发现超过红包的个数,直接返回。根据红包的逻辑处理成功得到令牌请求,则由财付通进行一致性调用,通过像比特币一样,两边保存交易记录,交易后交给第三方服务审计,如果交易过程中出现不一致就强制回归。

问:并发性处理:红包如何计算被抢完?

答:cache会抵抗无效请求,将无效的请求过滤掉,实际进入到后台的量不大。cache记录红包个数,原子操作进行个数递减,到 0 表示被抢光。财付通按照 20万笔每秒入账准备,但实际还不到 8万每秒

问:通如何保持8w每秒的写入?

答:多主sharding,水平扩展机器。

问:数据容量多少?

答:一个红包只占一条记录,有效期只有几天,因此不需要太多空间。

问:查询红包分配,压力大不?

答:抢到红包的人数和红包都在一条cache记录上,没有太大的查询压力。

问:一个红包一个队列?

答:没有队列,一个红包一条数据,数据上有一个计数器字段。

问:有没有从数据上证明每个红包的概率是不是均等?

答:不是绝对均等,就是一个简单的拍脑袋算法。

问:拍脑袋算法,会不会出现两个最佳?

答:会出现金额一样的,但是手气最佳只有一个,先抢到的那个最佳。

问:每领一个红包就更新数据么?

答:每抢到一个红包,就cas更新剩余金额和红包个数。

问:红包如何入库入账?

答:数据库会累加已经领取的个数与金额,插入一条领取记录。入账则是后台异步操作。

问:入帐出错怎么办?比如红包个数没了,但余额还有?

答:最后会有一个take all操作。另外还有一个对账来保障。

问:既然在抢的时候有原子减了就不应该出现抢到了拆开没有的情况?

答:这里的原子减并不是真正意义上的原子操作,是Cache层提供的CAS,通过比较版本号不断尝试。

问:cache和db挂了怎么办?

答:主备 +对账。

问:为什么要分离抢和拆?

答:总思路是设置多层过滤网,层层筛选,层层减少流量和压力。

这个设计最初是因为抢操作是业务层,拆是入账操作,一个操作太重了,而且中断率高。 从接口层面看,第一个接口纯缓存操作,搞压能力强,一个简单查询Cache挡住了绝大部分用户,做了第一道筛选,所以大部分人会看到已经抢完了的提示。

问:抢到红包后再发红包或者提现,这里有什么策略吗?

答:大额优先入账策略。

针对上面的技术要点,有人还画了张原理图(这是网上能找到的相对清晰的版本): 

3.2、微信抢红包的过程模拟

针对上节中整理的资料,当有人在微信群里发了一个 N 人的红包、总金额 M 元,后台大概的技术逻辑如下。

3.2.1)发红包后台操作:

  • 1)在数据库中增加一条红包记录,存储到CKV,设置过期时间;
  • 2)在Cache(可能是腾讯内部kv数据库,基于内存,有落地,有内核态网络处理模块,以内核模块形式提供服务))中增加一条记录,存储抢红包的人数N。

3.2.2)抢红包后台操作:

  • 1)抢红包分为抢和拆:抢操作在Cache层完成,通过原子减操作进行红包数递减,到0就说明抢光了,最终实际进入后台拆操作的量不大,通过操作的分离将无效请求直接挡在Cache层外面。
  • 这里的原子减操作并不是真正意义上的原子减操作,是其Cache层提供的CAS,通过比较版本号不断尝试,存在一定程度上的冲突,冲突的用户会放行,让其进入下一步拆的操作,这也解释了为啥有用户抢到了拆开发现领完了的情况。
  • 2)拆红包在数据库完成:通过数据库的事务操作累加已经领取的个数和金额,插入一条领取流水,入账为异步操作,这也解释了为啥在春节期间红包领取后在余额中看不到。
  • 拆的时候会实时计算金额,其金额为1分到剩余平均值2倍之间随机数,一个总金额为M元的红包,最大的红包为 M * 2 /N(且不会超过M),当拆了红包后会更新剩余金额和个数。财付通按20万笔每秒入账准备,实际只到8万每秒。

4、微信红包算法模拟实现1(含代码)

根据上一节的微信红包随机算法技术要点资料,实现了一个算法,以下供参考。(注:本节内容引用自《微信红包随机算法初探》一文)

4.1、算法约定

算法很简单,跟微信的算法一样,不是提前算好,而是抢红包时计算。

即:金额随机,额度在0.01和剩余平均值*2之间。(参见上一节的 “关于分配算法,红包里的金额怎么算?为什么出现各个红包金额相差很大?” 内容)

4.2、代码实现

算法的逻辑主要是:

public static double getRandomMoney(RedPackage _redPackage) {

    // remainSize 剩余的红包数量

    // remainMoney 剩余的钱

    if(_redPackage.remainSize == 1) {

        _redPackage.remainSize--;

        return (double) Math.round(_redPackage.remainMoney * 100) / 100;

    }

    Random r     = newRandom();

    double min   = 0.01; //

    double max   = _redPackage.remainMoney / _redPackage.remainSize * 2;

    double money = r.nextDouble() * max;

    money = money <= min ? 0.01: money;

    money = Math.floor(money * 100) / 100;

    _redPackage.remainSize--;

    _redPackage.remainMoney -= money;

    return money;

}

LeftMoneyPackage数据结构如下:

class RedPackage {

    int remainSize;

    double remainMoney;

}

测试时初始化相关数据是:

static void init() {

    redPackage.remainSize  = 30;

    redPackage.remainMoney = 500;

}

附件是可以运行的完整Java代码文件:

(无法上传附件,如有需要请从此链接处下载:http://www.52im.net/thread-3125-1-1.html

4.3、测试结果

4.3.1 单次测试

按上述代码中的初始化数据(30人抢500块),执行了两次,结果如下:

//第一次

15.69   21.18   24.11   30.85   0.74    20.85   2.96    13.43   11.12   24.87   1.86    19.62   5.97    29.33   3.05    26.94   18.69   34.47   9.4 29.83   5.17    24.67   17.09   29.96   6.77    5.79    0.34    23.89   40.44   0.92

//第二次

10.44   18.01   17.01   21.07   11.87   4.78    30.14   32.05   16.68   20.34   12.94   27.98   9.31    17.97   12.93   28.75   12.1    12.77   7.54    10.87   4.16    25.36   26.89   5.73    11.59   23.91   17.77   15.85   23.42   9.77

第一次随机红包数据图表如下: 

▲ x轴为抢的顺序,y轴为抢到的金额

第二次随机红包数据图表如下:

▲ x轴为抢的顺序,y轴为抢到的金额

4.3.2 多次均值

重复执行200次的均值:

▲ x轴为抢的顺序,y轴为该次抢到金额的概率均值

重复执行2000次的均值: 

▲ x轴为抢的顺序,y轴为该次抢到金额的概率均值

从以上两张图的均值结果可以看出,这个算法中每一次能抢到的金额几率几乎是均等的,从随机性来说比较合理。

5、微信红包算法模拟实现2(含代码)

我对随机算法很感兴趣,正巧最近研究的方向有点偏随机数这块,所以也自己实现了一下微信的红包分发算法(算法要点参考的是本文第三节内容)。(注:本节内容引用自《微信红包算法的分析》一文)

5.1、代码实现

从第三节中可以了解到,微信并不是一开始就预分配所有的红包金额,而是在拆时进行计算的。这样做的好处是效率高,实时性。本次的代码中,红包具体是怎么计算的呢?请参见第4节中的“关于分配算法,红包里的金额怎么算?为什么出现各个红包金额相差很大?”。

那基于这个思想,可以写出一个红包分配算法:

/**

 * 并不完美的红包算法

 */

public static double rand(double money, int people, List<Double> l) {

    if(people == 1) {

        double red = Math.round(money * 100) / 100.0;

        l.add(red);

        return0;

    }

    Random random = newRandom();

    double min = 0.01;

    double max = money / people * 2.0;

    double red = random.nextDouble() * max;

    red = red <= min ? min : red;

    red = Math.floor(red * 100) / 100.0;

    l.add(red);

    double remain = Math.round((money - red) * 100) / 100.0;

    return remain;

}

算法整体思路很简单,就在在最后一个人的时候要注意,此时不进行随机数计算,而是直接将剩余金额作为红包。

5.2、第一次分析

采用上述算法,可以对用户的抢红包行为做分析。这里的模仿行为是:30 元的红包,10 人抢。操作 100 次。

可以得出如下结果: 

▲ x轴为抢的顺序,y轴为该次抢到金额

从上图中可以很轻易的看出来,越后抢的人,风险越大,同时收益也越大,有较大几率获得“手气最佳”。

那红包面值的分布性如何呢?

▲ x轴为抢的顺序,y轴为该次抢到金额重复 100 次后的平均值

从上图可以看出,都是比较接近平均值(3 元)的。

那重复 1000 次呢?

▲ x轴为抢的顺序,y轴为该次抢到金额重复 1000 次后的平均值

更接近了。。。

可以看出,这个算法可以让大家抢到红包面额在概率上是大致均等的。

5.3、不足之处

有人提出了这个问题: 

他接下来放了好几张他试验的截图。我这里取了一张,如果有兴趣,可以去知乎的问题里查看更多图片。

而此时,我哥们在和我的在讨论中,也告诉我,确实存在某个规律,可能让最后一个抢的人占有某些微小的优势,比如,多 0.01 的之类。

例如发 6 个,总额 0.09 的包,最后一个抢的有极大概率是 0.03。

然而我之前的代码却没办法体现出这一点。

比如 10 人拆 0.11 元的包,我的结果是:

可见以上代码还存在不足之处。

于是我就有一个猜测:

微信可能不是对全金额进行随机的,可能在派发红包之前,已经对金额做了处理,比如,事先减去(红包个数*0.01),之后在每个红包的随机值基础上加 0.01,以此来保证每个红包最小值都是 0.01。

这个猜测或许可以解开那位知友和我哥们这边的疑惑。

5.4、完善算法

在原先的基础上对代码进行简单的修正:

public static double rand(double money, int people, List<Double> l) {

    if(people == 1) {

        double red = Math.round(money * 100) / 100.0;

        l.add(red+0.01);

        return 0;

    }

    Random random = newRandom();

    double min = 0;

    double max = money / people * 2.0;

    double red = random.nextDouble() * max;

    red = red <= min ? min : red;

    red = Math.floor(red * 100) / 100.0;

    l.add(red+0.01);

    double remain = Math.round((money - red) * 100) / 100.0;

    return remain;

}

这个算法,在第一次调用时传入 money 的值是总金额减去红包数*0.01,大概像这样:

_money = _money - people * 0.01;

5.5、第二次分析

5.5.1 验证上次的不足之处

1)10 人抢 0.11 元的包:

2)2 人抢 0.03 元的包: 

3)6 人抢 0.09 的包:

5.5.2 修改后的代码会不会对已知结论造成影响?

30 元的红包,10 人抢,操作 100 次。

▲ x轴为抢的顺序,y轴为该次抢到金额 

▲ x轴为抢的顺序,y轴为该次抢到金额重复 100 次后的平均值

由上面两图可见,结论基本上没有改变。

5.6、结论

经过上述代码实践可知:

1)先抢后抢,金额期望都是相同的;

2)微信的红包算法很可能是预先分配给每人 0.01 的“底额”;

3)后抢者风险高,收益大。

5.7、补充

上几张后面测试的图,补充一下之前的观点,发 n 个红包,总金额是(n+1)*0.01,最后一个领的一定是手气最佳。

 

大家也可以试试。

以上,大概可以证明,微信红包是在分配前先给每个人 0.01 的最低金额的!

6、参考资料

[1] 微信红包随机算法初探

[2] 微信红包算法的分析

[3] 微信红包的架构设计简介

[4] 微信红包的随机算法是怎样实现的?

另外,知乎上对于微信红包算法的讨论问题很多人参与,有兴趣可以上去看看,或许会有更多启发:《微信红包的随机算法是怎样实现的?》。

附录:更多微信相关资源

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

微信本地数据库破解版(含iOS、Android),仅供学习研究 [附件下载]

(本文同步发布于:http://www.52im.net/thread-3125-1-1.html

posted @ 2020-08-26 14:32 Jack Jiang 阅读(290) | 评论 (0)编辑 收藏

本文由手机淘宝技术团队原创分享,吴志华(天施)、洪海(孤星)、陈虓将(仲升)等专家参与了本文创作,首次发表于公众号“淘系技术”,收录整理时有修订和改动。

1、引言

移动端网络的优化是超级APP们永恒的话题,而对于无线电商来说这更为重要,因为网络请求体验跟用户的购买行为息息相关。

手机淘宝从过去的HTTP API网关,到后来扛住双十一战场主要流量的自研高性能、全双工、安全的ACCS(阿里云通道服务),无论是基础架构的演进、网络调优、协议的优化、异地多活、网络调度上,都有不少宝贵的经验与大家分享,本文借此机会总结了整个技术演进过程。

* 阅读对象:本文属于移动端网络优化的深水区总结性文章,适合有一定移动端网络应用经验的开发者阅读(尤其对移动弱网有一定了解的),初学者如果没有相关知识积累的话,可以简单了解无需深入。如果你对移动弱网很有兴趣,可以进一步阅读本文末尾“附录”部分的推荐文章。

本文已同步发布于“即时通讯技术圈”公众号,欢迎关注:

▲ 本文在公众号上的链接是:点此进入,原文链接是:http://www.52im.net/thread-3110-1-1.html

2、相关文章

Netty干货分享:京东京麦的生产级TCP网关技术实践总结

知乎技术分享:知乎千万级并发的高性能长连接网关技术实践

手机淘宝消息推送系统的架构与实践(音频+PPT) [附件下载]

3、技术背景

回想移动电商在双十一业务开始兴起的时候,当时双十一当天移动成交243亿占整体571亿的42.6%。

业务高速发展希望更多主动推送去触达用户,一些新的玩法和互动形式,需要连接买家与买家、买家与卖家、买家与达人,因为没有有效的通道能力,业务采取的是不停去轮询服务器,一来对服务器造成不必要的压力,二来对于用户手机的电量流量也是极大的浪费,关键在双十五这种大促的情况下,不必要的请求过大甚至会导致后端集群限流,从而影响到用户体验。

信息传播形态的变化的背后是移动化带来新的技术特征导致的结果。移动电商领域,手机淘宝一直是先行者。移动电商从最初的复制WEB的业务形态到移动特性不断涌现,更多的互动形式的出现,向社交化、娱乐化不断迈进的今天,一个单纯的商品的陈列架形式已经不能满足业务的需求。

业务上需要实时的触达用户,充分发挥移动的特性,将消费时间的碎片利用起来,事实也证明了用户的消费时间随着移动化的进程不断发生变化,逐步分布到全天的碎片时间中。同时货架形态也在向社区化、娱乐化的方向发展,这些都对网络层连接用户有了更高的要求。更多的媒体形态和展示方式,对网络层提出了更多元的要求。

大家可以关注到手机淘宝内的消息盒子这些产品都是业务求变的体现,业务的变化倒逼技术的前进。

4、移动网络环境的挑战性一直都存在

移动网络的速度随便3g、4g、5g的普及,速度有很大提升,但网络环境的多样性和差异性使移动网络的环境更加复杂,在过去双十一前还常遇到一些移动网络劫持的事情。网络劫持这块问题的排查效率很低,需要找到用户、复现现场,甚至找网工、运营商配合排查,一查就是几天过去。

同时在我们的舆情反馈上总是看到用户在说“某个页面加载中、页面打不开、请求很慢、打开某个功能很慢”,面对这些问题过去我们是没有太好的办法,只能猫抓耗子一桩桩去排雷很被动。很多网络的问题是偶现的,一旦错过现在就无从查起。

诸如此类的问题,背后的原因很多:

  • 1)运营商问题;
  • 2)机房部署原因;
  • 3)客户端SDK Bug;
  • 4)弱网和网络抖动;
  • 5)DNS劫持和数据篡改。

在PC时代,我们访问网站的接入条件是相对恒定的,所以在开发时很少考虑网络对用户体验的影响。但是移动APP则不然,尤其是在国内,基础的移动网络环境还不算太好,而且我们有很多用户的访问是发生在地铁、公交车这样的移动环境下,移动基站的频繁切换进一步增加了网络的不稳定。从手机淘宝的数据可以看出,我们每天活跃用户中有不少来自于弱网环境。如果端到云的连接不稳定、高延时,那么所有的用户体验都无从谈起。

基础网络的效率就像一辆列车,时延是火车的速度(启动时间),而带宽就像火车的车厢装载量,整个传输的物理链路就像火车的铁轨。目前现实条件下的移动网络条件非常复杂,我们的目标很简单,就是想让所有用户都能在手机淘宝获得流畅的体验。

下面这张图,能够让大家更加直观的了解国内的移动网络环境。描述了从用户到IDC的端到端的路由情况,不仅数据传输耗时长且丢包率高,同时安全性也是相当糟糕的,DNS劫持、内容劫持在中国就是家常便饭。

因此,我们在改善网络通道上有很多的事情可以去做,去探索突破运营商基础网络的限制,力争为用户创造极致的购物体验。

移动端的DNS问题相当普遍,可以详读以下专题文章:

全面了解移动端DNS域名劫持等杂症:原理、根源、HttpDNS解决方案等

美图App的移动端DNS优化实践:HTTPS请求耗时减小近半

百度APP移动端网络深度优化实践分享(一):DNS优化篇

移动端网络优化之HTTP请求的DNS优化

5、整体技术架构

为了满足移动电商业务高速发展的需求,我们决定打造一个世界级的网络接入服务,构建一个无线网络下”水、电、煤“ 一样的基础设施。

这样一个基础设施需要做到的四个目标:

  • 1)全双工;
  • 2)低延时;
  • 3)高安全;
  • 4)开放。

在这四个目标之上是围绕这个接入服务配套的运维体系,帮助最终用户取得良好的端上体验的同时,帮助开发者快速构建自己的业务。 

如上图所示,在整个接入服务上我们划分为两层:

  • 1)接入网关:负责连接的保持、消息的解析、消息的分发;
  • 2)应用网关:实现各种应用层协议:API、SYNC、RPC、PUSH等,在应用网关的背后是具体的业务系统。

同时我们建立了一个统一调度服务,而不是采用传统的DNS,调度服务是我们的控制中心,通过它我们可以强有力的指挥我们的客户端,并且不会受到DNS污染的影响。

与服务端的分层架构对应的是客户端的SDK,最底层的统一网络库SDK集中了我们对网络优化的策略,并向上为各个应用网关技术的SDK提供API。

基于上面的开放架构,业务方可以选择直接开放具体的后端服务对接不同的应用网关,不需要了解网络背后的细节,并通过应用网关如API网关提供的开发工具快速生成客户端代码。业务方也可以基于这个接入层设计自己的协议。

统一接入层集中管理了用户的设备、在线状态,并提供信息的双向传递能力。

如下图所示:

网关将致力于解决中间网络的通讯,为上层的服务提供高质量的双向通讯能力。

6、稳定性与容灾

稳定性与容灾是服务端中间件永恒的主题,统一接入层这样一个汇聚网关收益和风险是并存的,一旦这个入口故障了,波及的用户范围是不可想象的,如何做的更加稳定,是一个巨大的挑战。

6.1 网关架构的优化

对于一个统一网关来说,对接的业务网关的信息传递特点是不一样的,大部分的业务在全天都是比较平缓的,但是个别营销类业务会在短时间内发布海量的信息,这样的信息发布会抢占网关的大量资源,对于用户的正常访问会产生影响。

举个例子:push服务需要通过网关推送2亿条消息,而这些消息需要在短时间内全部推送完,而同时网关在为正常的用户的交互提供服务,海量信息的推送和正常的用户交互相互竞争资源,最终会造成正常用户的交互失败,对于业务来说,这是不可接受的。

基于上面的情况考虑,整个网关在布署上分为两个集群:

  • 1)一个集群处理常态的在线用户访问;
  • 2)一个集群处理海量信息的推送。

如下图所示,通过这样的方式,避免了业务形态不同,对统一网关的冲击,将不同的业务形态进行了隔离。

6.2 异地多活

在异地多活的整体方案中,统一网关承担了快速引导流量的职责,也是这一方案顺利实施的一个重要环节。

异地多活是一个多机房的整体方案,在多个地区同时存在对等的多个机房,以用户维度划分,多机房共同承担全量用户的流量;在单个机房发生故障时,故障机房的流量可以快速的被迁引到可用机房,减少故障的恢复时间。

6.2.1)无线接入层单元化的协商机制:

先看一下web端在这异地多活中的实现方式:

从上图可以看到,浏览器的业务器求会发给CDN,由CDN上保存的分发规则,向后续的单元机房分发。

无线端也这样做吗?

  • 1)客户端拥有强大的能力,可以做的更灵活;
  • 2)CDN的分发节点带来更多的机器成本;
  • 3)对于需要双工通讯能力的客户端,消息投递更为复杂。

这些是我们思考与WEB不同的地方,是不是能做些不一样的选择?

如上图所示, 我们借助了客户端的强大能力,利用协商的机制来完成用户的请求正确被分配到不同的单元。

含以下几点:

  • 1)客户端的请求始终带上当前用户归属单元的信息;
  • 2)当请求到达服务端时,服务端判断用户归属单元是否正确,不正确将用户重定向到正确的单元 ;
  • 3)当前请求由网关在服务端上通过跨单元调用保证业务的正确性;
  • 4)当客户端归属单元更新后,后续的请求都会发到正确的单元机房。

6.2.2)无线接入层单元化的旁路调度:

协商机制看起来很不错,这里一个重磅炸弹丢过来了,机房的入口网络断了!

如上图,外网不可用,协商的机会都没有故障单元的用户无法恢复,这时旁路的调度服务出场了。

如上图,我们设计的调度中心这时又承担了单元化的旁路调度职责,当app访问的单元无法访问的时候,app会访问不同单元的调度中心,询问用户的归属单元。通过这种方式取得可用的单元节点,将用户切到正确的单元。这个方案同样适用于单机房的接入层网关不可用的场景。

6.2.3)应用层网关不可用:

某个单元机房的应用层网关不可用,这时等待应用网关排查问题需要的时间比较久,为了达到最快的故障恢复,我们通过开关把修改接入层的转发规则,将流量切到可用的单元。

如下图所示: 

7、端到端网络优化

7.1 统一网络库

在做网络优化一开始,我们想做一个通用的网络库,这个网络库包含策略、httpDNS、SPDY协议等一切系统网络优化需要的方方面面。(如果你对httpDNS不甚了解,可以详读《全面了解移动端DNS域名劫持等杂症:原理、根源、HttpDNS解决方案等》)

上层api网关请求逻辑、推送逻辑、上传下载逻辑对于这样一个通用网络库来说都是业务。在分层上将通用网络库和上层应用逻辑分开、彻底解耦,对长期持续优化网络是很有必要。

如下图所示架构: 

这样架构上分离,可以让我们更专注更系统化去做无线网络优化。

统一网络库的几个重要特性:

  • 1)灵活控制客户端网络行为策略(建连、超时处理、请求协议、是否加密);
  • 2)包含HTTPDNS;
  • 3)支持异地多活;
  • 4)更细粒度控制和调度(域名级和域名下参数级)。

1、2、3、4均由网络调度中心的集群控制,我们希望这个可以做到与业务无关,去掉一些阿里的业务属性后,这个模块大家可以理解为HTTPDNS,可以理解我们在HTTPDNS之外做了大量网络优化的端到端的工作。

7.2 就近就快接入

基于网络库我们实现了一套智能学习的网络策略,智能学习客户端在不同网络环境下建连策略,用户重新回到这个网络环境会给出最优的策略进行快速连接,并定期去更新或淘汰本地cache的历史最优网络策略。

为了建立更加迅速在各自网络下穿透性更好,接入服务器支持了多种协议和端口,客户端建连时可以极速接入网络。

我们有一个重要指标是打开客户端30秒内网络请求成功率,就是关注连的快给用户体验带来的价值。

基于调度中心,我们搭建了一个智能大数据分析平台,将客户端在在网络请求过程中的数据如建连时间、首包收取时间、整包收取时间、ssl握手时间等重要指标收集上来 。根据这些指标分析出网络异常区域,调整我们的就近就快接入规则,甚至推动IDC建设和CDN的布点完善。

7.3 弱网优化和抗抖动

在弱网优化上我们尝试了QUIC协议,在网络延时较高、丢包严重情况下比TCP有更好表现。

线上手机淘宝灰度版本实测切换到QUIC后,平均RT收益有接近20%。考虑QUIC在移动网络可能存在穿透性问题,未来我们将采取SPDY为主,QUIC为辅助的模式来完善我们的网络链接策略。

现在QUIC协议在移动端应用的越来越广泛,有兴趣的话可详细以下文章:

网络编程懒人入门(十):一泡尿的时间,快速读懂QUIC协议

技术扫盲:新一代基于UDP的低延时网络传输层协议——QUIC详解

让互联网更快:新一代QUIC协议在腾讯的技术实践分享

七牛云技术分享:使用QUIC协议实现实时视频直播0卡顿!

同样在一些网络环境较差情况下,我们采取长短链接结合方式,在长链接遇到请求超时或穿透性较差情况,利用短链接HTTP短链接去请求数据(在移动网络环境下HTTP协议尤其HTTP1.0的穿透性是最好的),这样可以在一些极端情况下最大程度保证用户体验。

数据如下图:

网络切换和网络抖动情况下的技术优化也是一个很重要的方面,我们经常遇到移动设备网络切换和信号不稳定的情况,在这种情况我们怎么保证用户的体验?

针对这种情况我们的思路是有策略合理增加重试。我们对一个网络请求以是否发送到socket缓冲区作为分割,将网络请求生命周期划分为“请求开始到发送到 socket缓冲区”和“已经发送到socket缓冲区到请求结束”两个阶段。在阶段一内请求失败了,会根据业务需求帮助业务请求去做重试。阶段二请求失败只针对读操作提供重试能力。

设想一个场景:用户在进电梯发起一个刷新数据请求,进到电梯因为网络抖动的原因网络链接断了,这个时候我们能够合理策略去做重试,这样当用户离开电梯时很可能网络请求重试成功,帮助用户拉到了想要的数据,提升了用户体验和客户端的网络抗抖动能力。

7.4 加密传输1秒钟法则

众所周知的传统https的整个握手流程是非常重的,在网络质量不高的情况下,造成建连过慢,用户体验惨不能睹,甚至都无法完成安全握手。然而从安全的角度我们是需要一个安全的传输通道保护用户的隐私数据。

安全与网络这一对冲突放在我们的面前,需要在技术上有所突破,因此我们自建了一套slight-ssl的技术,参考了tls1.3的协议,通过合并请求,优化加密算法,运用session-ticket等策略,最终在安全和体验之间找到了一个平衡点,在基本不牺牲用户体验的基础上,达到了安全传输的目地, 同时还大幅度提升了服务端的性能。通过技术的创新,我们实现了无线网络加密传输下1秒钟法则。

关于TLS1.3在移动端的应用,也可以详读微信团队分享的这篇《微信新一代通信安全解决方案:基于TLS1.3的MMTLS详解》。

附录:有关移动端弱网方面的资料汇总

IM开发者的零基础通信技术入门(十一):为什么WiFi信号差?一文即懂!

IM开发者的零基础通信技术入门(十二):上网卡顿?网络掉线?一文即懂!

IM开发者的零基础通信技术入门(十三):为什么手机信号差?一文即懂!

IM开发者的零基础通信技术入门(十四):高铁上无线上网有多难?一文即懂!

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

聊聊iOS中网络编程长连接的那些事

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

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

全面了解移动端DNS域名劫持等杂症:原理、根源、HttpDNS解决方案等

美图App的移动端DNS优化实践:HTTPS请求耗时减小近半

百度APP移动端网络深度优化实践分享(一):DNS优化篇

百度APP移动端网络深度优化实践分享(二):网络连接优化篇

百度APP移动端网络深度优化实践分享(三):移动端弱网优化篇

爱奇艺移动端网络优化实践分享:网络请求成功率优化篇

美团点评的移动端网络优化实践:大幅提升连接成功率、速度等

5G时代已经到来,TCP/IP老矣,尚能饭否?

微信Mars:微信内部正在使用的网络层封装库,即将开源

如约而至:微信自用的移动端IM网络层跨平台组件库Mars已正式开源

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

腾讯原创分享(一):如何大幅提升移动网络下手机QQ的图片传输速度和成功率》 

腾讯原创分享(二):如何大幅压缩移动网络下APP的流量消耗(下篇)》 

腾讯原创分享(三):如何大幅压缩移动网络下APP的流量消耗(上篇)》 

IM开发者的零基础通信技术入门(十一):为什么WiFi信号差?一文即懂!

IM开发者的零基础通信技术入门(十二):上网卡顿?网络掉线?一文即懂!

IM开发者的零基础通信技术入门(十三):为什么手机信号差?一文即懂!

IM开发者的零基础通信技术入门(十四):高铁上无线上网有多难?一文即懂!

>> 更多同类文章 ……

(本文已同步发布于:http://www.52im.net/thread-3110-1-1.html

posted @ 2020-08-19 13:49 Jack Jiang 阅读(295) | 评论 (0)编辑 收藏

1、引言

最近在从头重写 MobileIMSDK 的TCP版,自已组织TCP数据帧时就遇到了字节序大小端问题。所以,借这个机会单独整理了这篇文章,希望能加深大家对字节序问题的理解,加强对IM这种基于网络通信的程序在数据传输这一层的知识掌控情况。

程序员在写应用层程序时,一般不需要考虑字节序问题,因为字节序跟操作系统和硬件环境有关,而我们编写的程序要么不需要跨平台(比如只运行在windows),要么需要跨平台时会由Java这种跨平台语言在虚拟机层屏蔽掉了。

但典型情况,当你编写网络通信程序,比如IM聊天应用时,就必须要考虑字节序问题,因为你的数据在这样的场景下要跨机器、跨网络通信,必须解决不同系统、不同平台的字节序问题。

* 阅读对象:本文属于计算机基础知识,特别适合从事网络编程方面工作(比如IM这类通信系统)的程序员阅读。面视时,面视官一般都会聊到这个知识点。

本文已同步发布于“即时通讯技术圈”公众号,欢迎关注:

▲ 本文在公众号上的链接是:点此进入 ,原文链接是:http://www.52im.net/thread-3101-1-1.html

2、什么是字节序?

字节序,是指数据在内存中的存放顺序,当字节数大于1时需要考虑(只有一个字节的情况下,比如char类型,也就不存在顺序问题啦)。

从下图中,可以直观的感受到什么是字节序问题: 

上图片改编自《C语言打印数据的二进制格式-原理解析与编程实现

3、字节序的分类

字节序常被分为两类:

  • 1)Big-Endian(大端字节序):高位字节排放在内存的低地址端,低位字节排放在内存的高地址端(这是人类读写数值的方法);
  • 2)Little-Endian(小端字节序):低位字节排放在内存的低地址端,高位字节排放在内存的高地址端。

举个具体的例子,0x1234567 的大端字节序和小端字节序写法如下:

如上图所示:大端小端字节序最小单位1字节,即8bit;大端字节序就是和我们平时写法的顺序一样,从低地址到高地址写入0x01234567;而小端字节序就是和我们平时的写法反过来,因为字节序最小单位为1字节,所以从低地址到高地址写入0x67452301。

4、为什么会存在大端、小端字节序问题?

4.1 比较合理的解释

一个比较合理的解释是说:计算机中电路优先处理低位字节,效率比较高,因为计算机都是从低位开始的,所以计算机内部处理都是小端字节序。

而人类人类读写数值的方法,习惯用大端字节序,所以除了计算机的内部处,其他的场理合都是大端字节序,比如:网络传输和文件储存时都是用的大端字节序(关于网络字节序,会在后面继续展开说明)。

大小端字节序问题,最有可能是跟技术算硬件或软件的创造者们,在技术创立之初的一些技术条件或个人习惯有关。

所以大小端问题,体现在实际的计算机工业应用来上,不同的操作系统和不同的芯片类型可能都会有不同。

4.2 常见的操作系统和芯片使用的字节序

具体来说:DEC和Intel的机器(X86平台)一般采用小端,IBM、Motorola(Power PC)、Sun的机器一般采用大端。

当然,这不代表所有情况。有的CPU即能工作于小端, 又能工作于大端,比如:Arm、Alpha、摩托罗拉的PowerPC。 

而且,具体这类CPU是大端还是小端,和具体设置也有关。如:Power PC支持小端字节序,但在默认配置时是大端字节序。

一般来说:大部分用户的操作系统(如:Windows、FreeBsd、Linux)是小端字节序。少部分,如:Mac OS 是大端字节序。

4.3 如何判断用的是什么字节序?

怎么判断我的计算机里使用的是大端还是小端字节序呢?

下面的这段代码可以用来判断计算机是大端的还是小端。判断的思路是:确定一个多字节的值(下面使用的是4字节的整数),将其写入内存(即赋值给一个变量),然后用指针取其首地址所对应的字节(即低地址的一个字节),判断该字节存放的是高位还是低位,高位说明是Big endian,低位说明是Little endian。

#include <stdio.h>

int main ()

{

  unsigned int x = 0x12345678;

  char*c = (char*)&x;

  if(*c == 0x78) {

    printf("Little endian");

  } else{

    printf("Big endian");

  }

  return 0;

}

5、“大端”、“小端”名字由来

根据网上的资料,据说名字的由来跟乔纳森·斯威夫特的著名讽刺小说《格列佛游记》有关。

书中的故事是这样的:一般来说,大家都认为吃鸡蛋前,原始的方法是打破鸡蛋较大的一端。可是当今皇帝的祖父小时候吃鸡蛋,一次按古法打鸡蛋时碰巧将一个手指弄破了,因此他的父亲,当时的皇帝,就下了一道敕令,命令全体臣民吃鸡蛋时打破鸡蛋较小的一端,违令者重罚。

小人国内部分裂成Big-endian和Little-endian两派,区别在于一派要求从鸡蛋的大头把鸡蛋打破,另一派要求从鸡蛋的小头把鸡蛋打破。

小人国国王改变了打开鸡蛋的方位与理由,并由此招致了修改法律、引发战争和宗教改革等一序列事件的发生。

《格列佛游记》中的这则故事,原本是借以讽刺英国的政党之争。而在计算机工业中,也借用了这个故事来代指大家在数据储存字节顺序中的分歧,并把“大端”(Big-endian)、“小端”(Little-endian)的名字,沿用到了计算机中。 

上图片改编自《“字节序”是个什么鬼?

或许,借用这个故事来命名大小端字节序问题,无非就是想告诉大家,所谓的“大端”、“小端”实际上可能无关计算机性能,更多的只是创造者们在创立计算机之初,代入了个人的一些约定俗成的习惯而已。

6、什么是网络字节序?

6.1 字节序问题给网络通信带来的困扰

对于搞网络通信应用(比如IM、消息推送、实时音视频)开发的程序员来说,自已写通信底层的话是一定会遇到大小端问题的,对于网络字节序这个知识点是一定要必知必会。(当然,你要是很没追求的认为,反正我公司就让租租第3方,能用就行,具体通底层怎么写我才不想掉头发去考虑那么多。。。。 那哥也救不了你。。

上面所说的大小端字节序都是在说计算机自己,也被称作主机字节序。同型号计算机上写的程序,在相同的系统上面运行总归是没有问题。

但计算机网络的出现让大小端问题变的复杂化了,因为每个计算机都有自己的主机字节序。不同计算机之间通过网络通信时:我“说”的你听不懂,你“说”我也听不懂,这可怎么办?

6.2 TCP/IP协议强行约定了字节序方案

好消息是,TCP/IP协议很好的解决了这个问题,TCP/IP协议规定使用“大端”字节序作为网络字节序。

这样,即使不使用大端的计算机也没有关系,因为发送数据的时候可以将自己的主机字节序转换为网络字节序(即“大端”字节序),对接收到的数据转换为自己的主机字节序。这样一来,也就达到了与CPU、操作系统无关,实现了网络通信的标准化。

具体的原理就是:

  • 1)TCP/IP协议会把接收到的第一个字节当作高位字节看待,这就要求发送端发送的第一个字节是高位字节;
  • 2)而在发送端发送数据时,发送的第一个字节是该数值在内存中的起始地址处对应的那个字节。

也就是说,该数值在内存中的起始地址处对应的那个字节就是要发送的第一个高位字节(即:高位字节存放在低地址处)。由此可见,多字节数值在发送之前,在内存中就是以大端法存放的。

所以说,网络字节序就是大端字节序。

6.3 主机字机序到网络字节序的转换

那么,为了程序的兼容,程序员们每次发送和接受数据都要进行转换,这样做的目的是保证代码在任何计算机上执行时都能达到预期的效果。

通信时的这种常用的操作,Socket API这一层,一般都提供了封装好的转换函数,方便程序员使用。比如从主机字节序到网络字节序的转换函数:htons、htonl(C语言中常用),从网络字节序到主机字节序的转换函数:ntohs、ntohl(C语言中常用)。当然,也可以编写自己的转换函数。

7、实践中的大小端字节序处理

在我编写MobileIMSDK的TCP版时(MobileIMSDK是我开源的IM通信层库),同样遇到了大小端字节序问题。

以MobileIMSDK的iOS端拼装网络数据收发的代码为例:

如上图代码所示,注意以下两个大小端转换函数的使用:

  • 1)第27行“CFSwapInt32HostToBig”函数:网络发出数据之前,先将主机字节序转为网络字节序(即大端字节序);
  • 2)第53行“CFSwapInt32BigToHost”函数:收到原始网络数据后,转为主机字节序后就可以在程序中正常使用了。

如果对网络大小端转换这方面的实践感兴趣,可以自已去下载MobileIMSDK源码试一试:https://github.com/JackJiang2011/MobileIMSDK

8、参考资料

[1] “字节序”是个什么鬼?

[2] 大小端及网络字节序

[3] C语言打印数据的二进制格式-原理解析与编程实现

附录:系列文章

本文是系列文章中的第9篇,本系列大纲如下:

脑残式网络编程入门(一):跟着动画来学TCP三次握手和四次挥手

脑残式网络编程入门(二):我们在读写Socket时,究竟在读写什么?

脑残式网络编程入门(三):HTTP协议必知必会的一些知识

脑残式网络编程入门(四):快速理解HTTP/2的服务器推送(Server Push)

脑残式网络编程入门(五):每天都在用的Ping命令,它到底是什么?

脑残式网络编程入门(六):什么是公网IP和内网IP?NAT转换又是什么鬼?

脑残式网络编程入门(七):面视必备,史上最通俗计算机网络分层详解

脑残式网络编程入门(八):你真的了解127.0.0.1和0.0.0.0的区别?

脑残式网络编程入门(九):面试必考,史上最通俗大小端字节序详解》(本文)

(本文同步发布于:http://www.52im.net/thread-3101-1-1.html

posted @ 2020-08-13 14:58 Jack Jiang 阅读(289) | 评论 (0)编辑 收藏

本文作者网易智慧企业web前端开发工程师马莹莹。为了提升内容质量,收录时有修订和改动。

1、引言

在一个完善的即时通讯IM应用中,WebSocket是极其关键的一环,它为基于Web的即时通讯应用提供了一种全双工的通信机制。但为了提升IM等实际应用场景下的消息即时性和可靠性,我们需要克服WebSocket及其底层依赖的TCP连接对于复杂网络情况下的不稳定性,即时通讯的开发者们通常都需要为其设计一套完整的连接保活、验活以及断片网重连方案。

就断网重连而言,其重连响应速度将严重影响了上层应用的“即时性”和用户体验。试想打开网络一分钟后,微信的网络不能即时感知到socket连接的恢复,无法即时收发聊天消息的话,是不是很崩溃?

因此,如何在复杂网络场景下,更即时快速地感知网络变动,并快速恢复WebSocket的可用性,就变得尤为重要。本文将基于笔者的开发实践,分享WebSocket在不同状态下、不同的网络状态下,应该如何实现快速断网重连。

* 阅读对象:本文适合有过IM底层网络实际开发经验,或者对底层网络实现有较深了解的开发者阅读。如果对底层网络了解甚少,建议跳过本文,直接阅读网络本文末尾附录部分的基础后再回头来看。

* 内容点评:本文内容没有高大上,但比较干货,实用性较高,内容也很通俗,建议可详细阅读。文中虽讲的是WebSocket,但思想可以延伸应用到基于TCP协议的同类技术中。

本文已同步发布于“即时通讯技术圈”公众号,欢迎关注:

▲ 本文在公众号上的链接是:点此进入原文链接是:http://www.52im.net/thread-3098-1-1.html

2、预备知识

本文中将要分享的内容是基于实践总结,如果你对Web端的即时通讯知识还一头雾水,务必先读:《新手入门贴:史上最全Web端即时通讯技术原理详解》、《Web端即时通讯技术盘点:短轮询、Comet、Websocket、SSE》。

限于篇幅,本文不会深究WebSocket技术细节,如有兴趣请系统学习:

3、快速了解WebSocket

Websocket诞生于2008年,在2011年成为国际标准,现在所有的浏览器都已支持(详见《新手快速入门:WebSocket简明教程》)。它是一种全新的应用层协议,是专门为web客户端和服务端设计的真正的全双工通信协议,可以类比HTTP协议来了解websocket协议。

图片引用自《WebSocket详解(四):刨根问底HTTP与WebSocket的关系(上篇)

它们的不同点:

  • 1)HTTP的协议标识符是http,WebSocket的是ws;
  • 2)HTTP请求只能由客户端发起,服务器无法主动向客户端推送消息,而WebSocket可以;
  • 3)HTTP请求有同源限制,不同源之间通信需要跨域,而WebSocket没有同源限制。

它们的相同点:

  • 1)都是应用层的通信协议;
  • 2)默认端口一样,都是80或443;
  • 3)都可以用于浏览器和服务器间的通信;
  • 4)都基于TCP协议。

两者和TCP的关系图:

图片引用自《新手快速入门:WebSocket简明教程

有关Http和WebSocket的关系,可以详读:

有关WebSocket和Socket的关系,可以详读:《WebSocket详解(六):刨根问底WebSocket与Socket的关系》.

4、WebSocket重连过程拆解

首先考虑一个问题,何时需要重连?

最容易想到的是WebSocket连接断了,为了接下来能收发消息,我们需要再发起一次连接。

但在很多场景下,即便WebSocket连接没有断开,实际上也不可用了。

比如以下场景:

  • 1)设备切换网络;
  • 2)链路中间路由崩溃(常识是一条socket连接对应的网络通路上,会存在很多路由设备);
  • 3)链路的前端出口不可用(比如家庭WiFi中,网络连接正常,但实际运营商的宽带已经欠费被停机);
  • 4)服务器负载持续过高无法响应等。

这些场景下的WebSocket都没有断开,但对上层来说,都没办法正常的收发数据了。

因此在重连前,我们需要一种机制来感知连接是否可用、服务是否可用,而且要能快速感知,以便能够快速从不可用状态中恢复。

一旦感知到了连接不可用,那便可以弃旧图新了,弃用并断开旧连接,然后发起一次新连接。这两个步骤看似简单,但若想达到快,且不是那么容易的。

首先:是断开旧连接,对客户端来说,如何快速断开?协议规定客户端必须要和服务器协商后才能断开WebSocket连接,但是当客户端已经联系不上服务器、无法协商时,如何断开并快速恢复?

其次:是快速发起新连接。此快非彼快,这里的快并非是立即发起连接,立即发起连接会对服务器带来不可预估的影响。重连时通常会采用一些退避算法,延迟一段时间后再发起重连。但如何在重连间隔和性能消耗间做出权衡?如何在“恰当的时间点”快速发起连接?

带着这些疑问,我们来细看下这三个过程:

5、快速重连关键1:快速感知何时需要重连

5.1 场景

需要重连的场景可以细分为三种:

  • 1)连接明确断开了;
  • 2)连接没断但是不可用了;
  • 3)连接对端的服务不可用了。

对于第一种场景:这很简单,连接直接断开了,肯定需要重连了。

对于后两者:无论是连接不可用,还是服务不可用,对上层应用的影响都是不能再收发即时消息了。

5.2 心跳包主动探测网络可用性

所以从上面这个角度出发,感知何时需要重连的一种简单粗暴的方法就是通过心跳包超时:发送一个心跳包,如果超过特定的时间后还没有收到服务器回包,则认为服务不可用,如下图中左侧的方案(这种方法最直接)。

那如果想要快速感知呢,就只能多发心跳包,加快心跳频率。但是心跳太快对移动端流量、电量的消耗又会太多,所以使用这种方法没办法做到快速感知,可以作为检测连接和服务可用的兜底机制。

5.3 被动监听网络状态改变

如果要检测连接不可用,除了用心跳检测,还可以通过判断网络状态来实现,因为断网、切换wifi、切换网络是导致连接不可用的最直接原因,所以在网络状态由offline变为online时,大多数情况下需要重连下,但也不一定,因为webscoket底层是基于TCP的,TCP连接不能敏锐的感知到应用层的网络变化,所以有时候即便网络断开了一小会,对WebSocket连接是不会有影响的,网络恢复后,仍然能够正常地进行通信。

因此在网络由断开到连接上时,立即判断下连接是否可用,可以通过发一个心跳包判断,如果能够正常收到服务器的心跳回包,则说明连接仍是可用的,如果等待超时后仍没有收到心跳回包,则需要重连,如上图中的右侧。这种方法的优点是速度快,在网络恢复后能够第一时间感知连接是否可用,不可用的话可以快速执行恢复,但它只能覆盖应用层网络变化导致WebSocket不可用的情况。

5.4 小结

综上所述:

  • 1)定时发送心跳包检测的方案贵在稳定,能够覆盖所有场景,但速度不即时(心跳间隔是固定的);
  • 2)判断网络状态的方案速度快,无需等待心跳间隔,较为灵敏,但覆盖场景较为局限。

因此,我们可以结合两种方案:

  • 1)定时以不太快的频率发送心跳包,比如40s/次、60s/次等,具体可以根据应用场景来定;
  • 2)然后在网络状态由offline变为online时立即发送一次心跳,检测当前连接是否可用,不可用的话立即进行恢复处理。

这样在大多数情况下,上层的应用通信都能较快从不可用状态中恢复,对于少部分场景,有定时心跳作为兜底,在一个心跳周期内也能够恢复。

6、快速重连关键2:快速断开旧连接

通常情况下,在发起下一次连接前,如果旧连接还存在的话,应该先把旧连接断开。

这样做的目的:

  • 1)一来可以释放客户端和服务器的资源;
  • 2)二来可以避免之后误从旧连接收发数据。

我们知道WebSocket底层是基于TCP协议传输数据的,连接两端分别是服务器和客户端,而TCP的TIME_WAIT状态是由服务器端维持的,因此在大多数正常情况下,应该由服务器发起断开底层TCP连接,而不是客户端。

也就是说:

  • 1)要断开WebSocket连接时,如果是服务器收到指示要断开WebSocket,那它应该立即发起断开TCP连接;
  • 2)如果是客户端收到指示要断开WebSocket,那它应该发信号给服务器,然后等待底层TCP连接被服务器断开或直至超时。

那如果客户端想要断开旧的WebSocket,可以分为WebSocket连接可用和不可用两种情况来讨论。

具体如下:

  • 1)当旧连接可用时,客户端可以直接给服务器发送断开信号,然后服务器发起断开连接即可;
  • 2)当旧连接不可用时,比如客户端切换了wifi,客户端发送了断开信号,但是服务器收不到,客户端只能迟迟等待,直至超时才能被允许断开。

超时断开的过程相对来说是比较久的,那有没有办法可以快点断开?

上层应用无法改变只能由服务器发起断开连接这种协议层面的规则,所以只能从应用逻辑入手,比如在上层通过业务逻辑保证旧连接完全失效,模拟连接断开,然后在发起新连接,恢复通讯。

这种方法相当于尝试断开旧连接不行时,直接弃之,然后就能快速进入下一流程,所以在使用时一定要确保在业务逻辑上旧连接已完全失效。

比如:

  • 1)保证丢掉从旧连接收到所有数据;
  • 2)旧连接不能阻碍新连接的建立
  • 3)旧连接超时断开后不能影响新连接和上层业务逻辑等等。

7、快速重连关键3:快速发起新连接

有IM开发经验的同学应该有所了解,遇到因网络原因导致的重连时,是万万不能立即发起一次新连接的,否则当出现网络抖动时,所有的设备都会立即同时向服务器发起连接,这无异于黑客通过发起大量请求消耗网络带宽引起的拒绝服务攻击,这对服务器来说简直是灾难(即:服务端雪崩效应)。

所以在重连时通常采用一些退避算法,延迟一段时间再发起重连,如下图中左侧的流程。

如果要快速连上呢?最直接的做法就是缩短重试间隔,重试间隔越短,在网络恢复后就能越快的恢复通讯。但是太频繁的重试对性能、带宽、电量的消耗就比较严重。

如何在这之间做一个较好的权衡呢?

  • 1)一种比较合理的方式是随着重试次数增多,逐渐增大重试间隔;
  • 2)另一方面监听网络变化,在网络状态由offline变为online这种比较可能重连上的时刻,适当地减小重连间隔。

上述第2)种方案,如上图中的右侧所示,随重试次数的增多,重连间隔也会变大。这两种方式配合使用,更为合理。

除此之外,还可以结合业务逻辑,根据成功重连上的可能性适当的调整间隔,如网络未连接时或应用在后台时重连间隔可以调大一些,网络正常的状态下可以适当调小一些等等,加快重连上的速度。

8、本文小结

最后总结一下。

本文将WebSocket断网重连逻辑细分为三个步骤:

  • 1)确定何时需要重连;
  • 2)断开旧连接;
  • 3)发起新连接。

然后分别分析了在WebSocket的不同状态下、不同的网络状态下,如何快速完成这个三个步骤。

过程具体总结就是:

  • 1)首先:通过定时发送心跳包的方式检测当前连接是否可用,同时监测网络恢复事件,在恢复后立即发送一次心跳,快速感知当前状态,判断是否需要重连;
  • 2)其次:正常情况下由服务器断开旧连接,与服务器失去联系时直接弃用旧连接,上层模拟断开,来实现快速断开;
  • 3)最后:发起新连接时使用退避算法延迟一段时间再发起连接,同时考虑到资源浪费和重连速度,可以在网络离线时调大重连间隔,在网络正常或网络由offline变为online时缩小重连间隔,使之尽可能快地重连上。

以上就是我关于如何实现WebSocket快速重连的技术分享,欢迎留言与我探讨。

9、参考资料

[1] RFC 6455 文档

[2] 新手快速入门:WebSocket简明教程

[3] WebSocket详解(四):刨根问底HTTP与WebSocket的关系(上篇)

[4] WebSocket详解(五):刨根问底HTTP与WebSocket的关系(下篇)

[5] WebSocket详解(六):刨根问底WebSocket与Socket的关系

附录:更多Web端即时通讯资料

新手入门贴:史上最全Web端即时通讯技术原理详解

Web端即时通讯技术盘点:短轮询、Comet、Websocket、SSE

SSE技术详解:一种全新的HTML5服务器推送事件技术

Comet技术详解:基于HTTP长连接的Web端实时通信技术

socket.io实现消息推送的一点实践及思路

LinkedIn的Web端即时通讯实践:实现单机几十万条长连接

Web端即时通讯技术的发展与WebSocket、Socket.io的技术实践

Web端即时通讯安全:跨站点WebSocket劫持漏洞详解(含示例代码)

开源框架Pomelo实践:搭建Web端高性能分布式IM聊天服务器

使用WebSocket和SSE技术实现Web端消息推送

详解Web端通信方式的演进:从Ajax、JSONP 到 SSE、Websocket

MobileIMSDK-Web的网络层框架为何使用的是Socket.io而不是Netty?

理论联系实际:从零理解WebSocket的通信原理、协议格式、安全性

微信小程序中如何使用WebSocket实现长连接(含完整源码)

八问WebSocket协议:为你快速解答WebSocket热门疑问

快速了解Electron:新一代基于Web的跨平台桌面技术

一文读懂前端技术演进:盘点Web前端20年的技术变迁史

Web端即时通讯基础知识补课:一文搞懂跨域的所有问题!

Web端即时通讯实践干货:如何让你的WebSocket断网重连更快速?

>> 更多同类文章 ……

(本文同步发布于:http://www.52im.net/thread-3098-1-1.html

posted @ 2020-08-05 15:36 Jack Jiang 阅读(369) | 评论 (0)编辑 收藏

仅列出标题
共50页: First 上一页 26 27 28 29 30 31 32 33 34 下一页 Last 
Jack Jiang的 Mail: jb2011@163.com, 联系QQ: 413980957, 微信: hellojackjiang