技术标签: java
很多人一想到IM应用开发,第一印象就是“长连接”、“socket”、“保活”、“协议”这些关键词,没错,这些确实是IM开发中肯定会涉及的技术范畴。
但,当你真正开始编写第一行代码时,最现实的问题实际上是“聊天消息ID该怎么生成?”这个看似微不足道的小事情。说它看似微不足道,是因为在IM里它太平常了,处处可见它的身影。不过,虽然看似微不足道,但实际却很重要,因为它的生成算法和生成策略的优劣在某种意义上来说,决定了你的IM应用层某些功能实现的难易度。
有签于此,即时通讯网专门整理了“IM消息ID技术专题”系列文章,希望能带给你对这个看似微小但却很重要的技术点有更深刻的理解和最佳实践思路。
本文是专题系列文章的第5篇,专门介绍百度开源的分布式消息ID生成器UidGenerator的算法逻辑、实现思路、重点源码解读等,或许能带给你更多的启发。
学习交流:
- 即时通讯/推送技术开发交流5群:215477170 [推荐]
- 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM》
(本文同步发布于:http://www.52im.net/thread-2953-1-1.html)
本文是“IM消息ID技术专题”系列文章的第5篇,专题总目录如下:
《IM消息ID技术专题(一):微信的海量IM聊天消息序列号生成实践(算法原理篇)》
《IM消息ID技术专题(二):微信的海量IM聊天消息序列号生成实践(容灾方案篇)》
《IM消息ID技术专题(三):解密融云IM产品的聊天消息ID生成策略》
全局ID(常见的比如:IM聊天系统中的消息ID、电商系统中的订单号、外卖应用中的订单号等)服务是分布式服务中的基础服务,需要保持全局唯一、高效、高可靠性。有些时候还可能要求保持单调,但也并非一定要严格递增或者递减。
全局ID也可以通过数据库的自增主键来获取,但是如果要求QPS很高显然是不现实的。
UidGenerator(备用地址)工程是百度开源的基于Snowflake算法的唯一ID生成器(百度对Snowflake算法进行了改进),引入了高性能队列高性能队列disruptor中RingBuffer思想,进一步提升了效率。
UidGenerator是Java语言实现的,它以组件形式工作在应用项目中,支持自定义workerId位数和初始化策略,,从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。
在技术实现上,UidGenerator有以下关键特性:
1)UidGenerator通过借用未来时间来解决sequence天然存在的并发限制;
2)采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费;
3)同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题。
基于以上技术特性,UidGenerator的单机压力测试数据显示,其QPS可高达600万。
依赖的环境:
1)Java8及以上版本(代码中使用了函数式编程语句等新特性,请见:uid-generator源码在线版);
2)MySQL(内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖)。
以下是UidGenerator工程的相关资源:
1)完整源码地址:https://github.com/baidu/uid-generator
2)备用源码地址:https://github.com/52im/uid-generator
3)源码在线阅读:http://docs.52im.net/extend/docs/src/uid-generator/(推荐)
友情提示:本节文字内容摘选自《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法》一文,如果您想了解美团对于SnowFlake算法的理解和应用情况,可详细阅读之。
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。
这 64 个 bit 中,其中 1 个 bit 是不用的,然后用其中的 41 bit 作为毫秒数,用 10 bit 作为工作机器 ID,12 bit 作为序列号。
SnowFlake的ID构成:
(本图引用自《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法》)
SnowFlake的ID样本:
(本图引用自《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法》)
给大家举个例子吧,如上图所示,比如下面那个 64 bit 的 long 型数字:
1)第一个部分,是 1 个 bit:0,这个是无意义的;
2)第二个部分,是 41 个 bit:表示的是时间戳;
3)第三个部分,是 5 个 bit:表示的是机房 ID,10001;
4)第四个部分,是 5 个 bit:表示的是机器 ID,1 1001;
5)第五个部分,是 12 个 bit:表示的序号,就是某个机房某台机器上这一毫秒内同时生成的 ID 的序号,0000 00000000。
① 1 bit:是不用的,为啥呢?
因为二进制里第一个 bit 为如果是 1,那么都是负数,但是我们生成的 ID 都是正数,所以第一个 bit 统一都是 0。
② 41 bit:表示的是时间戳,单位是毫秒。
41 bit 可以表示的数字多达 2^41 - 1,也就是可以标识 2 ^ 41 - 1 个毫秒值,换算成年就是表示 69 年的时间。
③ 10 bit:记录工作机器 ID,代表的是这个服务最多可以部署在 2^10 台机器上,也就是 1024 台机器。
但是 10 bit 里 5 个 bit 代表机房 id,5 个 bit 代表机器 ID。意思就是最多代表 2 ^ 5 个机房(32 个机房),每个机房里可以代表 2 ^ 5 个机器(32 台机器)。
④12 bit:这个是用来记录同一个毫秒内产生的不同 ID。
12 bit 可以代表的最大正整数是 2 ^ 12 - 1 = 4096,也就是说可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 ID。理论上snowflake方案的QPS约为409.6w/s,这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。
简单来说,你的某个服务假设要生成一个全局唯一 ID,那么就可以发送一个请求给部署了 SnowFlake 算法的系统,由这个 SnowFlake 算法系统来生成唯一 ID。
最终一个 64 个 bit 的 ID 就出来了,类似于:
(本图引用自《IM消息ID技术专题(四):深度解密美团的分布式ID生成算法》)
这个算法可以保证说,一个机房的一台机器上,在同一毫秒内,生成了一个唯一的 ID。可能一个毫秒内会生成多个 ID,但是有最后 12 个 bit 的序号来区分开来。
下面我们简单看看这个 SnowFlake 算法的一个代码实现,这就是个示例,大家如果理解了这个意思之后,以后可以自己尝试改造这个算法。
总之就是用一个 64 bit 的数字中各个 bit 位来设置不同的标志位,区分每一个 ID。
SnowFlake 算法的一个典型Java实现代码,可以参见文章中的第“6.5 方案四:SnowFlake 算法的思想分析”节:《通俗易懂:如何设计能支撑百万并发的数据库架构?》,是Jack Jiang曾在某项目中实际使用过的代码。
对于份布式的业务系统来说,SnowFlake算法的优缺点如下。
► 优点:
1)毫秒数在高位,自增序列在低位,整个ID都是趋势递增的;
2)不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的;
3)可以根据自身业务特性分配bit位,非常灵活。
► 缺点:
强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。
通过上节,我们知道了原版SnowFlake算法的基本构成。
具体是,原版SnowFlake算法核心组成:
原版SnowFlake算法各字段的具体意义是:
1)1位sign标识位;
2)41位时间戳;
3)10位workId(即5位数据中心id+5位工作机器id);
4)12位自增序列。
而UidGenerator改进后的SnowFlake算法核心组成如下图:
简单来说,UidGenerator能保证“指定机器 & 同一时刻 & 某一并发序列”,是唯一,并据此生成一个64 bits的唯一ID(long),且默认采用上图字节分配方式。
与原版的snowflake算法不同,UidGenerator还支持自定义时间戳、工作机器id和序列号等各部分的位数,以应用于不同场景(详见源码实现)。
如上图所示,UidGenerator默认ID中各数据位的含义如下:
通过阅读UidGenerator的源码可知,UidGenerator的具体实现有两种选择,即 DefaultUidGenerator 和 CachedUidGenerator。我们分别来看看这两个具体代码实现的精妙之处。
DefaultUidGenerator 的源码很清楚的说明了几个生成ID的关键位的实现逻辑。
1)delta seconds(28 bits):
这个值是指当前时间与epoch时间的时间差,且单位为秒。epoch时间就是指集成DefaultUidGenerator生成分布式ID服务第一次上线的时间,可配置,也一定要根据你的上线时间进行配置,因为默认的epoch时间可是2016-09-20,不配置的话,会浪费好几年的可用时间。
2)worker id(22bits):
接下来说一下DefaultUidGenerator是如何给worker id赋值的,搭建DefaultUidGenerator的话,需要创建一个表:
DROP DATABASE IF EXISTS `xxxx`;
CREATE DATABASE `xxxx` ;
use `xxxx`;
DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE
(
ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',
HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
PORT VARCHAR(64) NOT NULL COMMENT 'port',
TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
MODIFIED TIMESTAMP NOT NULL COMMENT 'modified time',
CREATED TIMESTAMP NOT NULL COMMENT 'created time',
PRIMARY KEY(ID)
)
COMMENT='DB WorkerID Assigner for UID Generator', ENGINE = INNODB;
DefaultUidGenerator会在集成用它生成分布式ID的实例启动的时候,往这个表中插入一行数据,得到的id值就是准备赋给workerId的值。由于workerId默认22位,那么,集成DefaultUidGenerator生成分布式ID的所有实例重启次数是不允许超过4194303次(即2^22-1),否则会抛出异常。
3)sequence(13bits):
核心代码如下,几个实现的关键点:
a. synchronized保证线程安全;
b. 如果时间有任何的回拨,那么直接抛出异常;
c. 如果当前时间和上一次是同一秒时间,那么sequence自增。如果同一秒内自增值超过2^13-1,那么就会自旋等待下一秒(getNextSecond);
d. 如果是新的一秒,那么sequence重新从0开始。
(上述源码节选自:DefaultUidGenerator 类中的 nextId() 方法)
4)小结:
通过DefaultUidGenerator的实现可知,它对时钟回拨的处理比较简单粗暴。另外如果使用UidGenerator的DefaultUidGenerator方式生成分布式ID,一定要根据你的业务的情况和特点,调整各个字段占用的位数:
<!-- Specified bits & epoch as your demand. No specified the default value will be used -->
<property name="timeBits" value="29"/>
<property name="workerBits" value="21"/>
<property name="seqBits" value="13"/>
<property name="epochStr" value="2016-09-20"/>
CachedUidGenerator是DefaultUidGenerator的重要改进实现。它的核心利用了RingBuffer,它本质上是一个数组,数组中每个项被称为slot。CachedUidGenerator设计了两个RingBuffer,一个保存唯一ID,一个保存flag。RingBuffer的尺寸是2^n,n必须是正整数。
以下是CachedUidGenerator中的RingBuffer原理示意图:
扩展知识:什么是RingBuffer?
Ring Buffer的概念,其实来自于Linux内核(Maybe),是为解决某些特殊情况下的竞争问题提供了一种免锁的方法。这种特殊的情况就是当生产者和消费者都只有一个,而在其它情况下使用它也是必须要加锁的。
环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据,写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下,环形缓冲区的读用户仅仅会影响读指针,而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户,那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区,那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。
更多具体的 CachedUidGenerator 的代码实现,有兴趣可以仔细读一读,也可以前往百度uid-generator工程的说明页看看具体的算法原理,这里就不再赘述。
简要的小结一下,CachedUidGenerator方式主要通过采取如下一些措施和方案规避了时钟回拨问题和增强唯一性:
CachedUidGenerator通过缓存的方式预先生成一批唯一ID列表,可以解决唯一ID获取时候的耗时。但这种方式也有不好点,一方面需要耗费内存来缓存这部分数据,另外如果访问量不大的情况下,提前生成的UID中的时间戳可能是很早之前的。而对于大部分的场景来说,DefaultUidGenerator 就可以满足相关的需求了,没必要来凑CachedUidGenerator这个热闹。
另外,关于UidGenerator比特位分配的建议:
对于并发数要求不高、期望长期使用的应用, 可增加timeBits位数, 减少seqBits位数. 例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为12次/天, 那么配置成{"workerBits":23,"timeBits":31,"seqBits":9}时, 可支持28个节点以整体并发量14400 UID/s的速度持续运行68年.
对于节点重启频率频繁、期望长期使用的应用, 可增加workerBits和timeBits位数, 减少seqBits位数. 例如节点采取用完即弃的WorkerIdAssigner策略, 重启频率为24*12次/天, 那么配置成{"workerBits":27,"timeBits":30,"seqBits":6}时, 可支持37个节点以整体并发量2400 UID/s的速度持续运行34年.
UidGenerator的测试数据显示,在MacBook Pro(2.7GHz Intel Core i5, 8G DDR3)上进行的CachedUidGenerator(单实例)的UID吞吐量测试情况如下。
首先:固定住workerBits为任选一个值(如20), 分别统计timeBits变化时(如从25至32, 总时长分别对应1年和136年)的吞吐量, 测试结果如下图所示:
再固定住timeBits为任选一个值(如31), 分别统计workerBits变化时(如从20至29, 总重启次数分别对应1百万和500百万)的吞吐量, 测试结果如下图所示:
由此可见:不管如何配置, CachedUidGenerator总能提供600万/s的稳定吞吐量,只是使用年限会有所减少,这真的是太棒了!
最后:固定住workerBits和timeBits位数(如23和31), 分别统计不同数目(如1至8,本机CPU核数为4)的UID使用者情况下的吞吐量,测试结果如下图所示:
[1] 改进版Snowflake全局ID生成器-uid-generator
[2] UidGenerator
[3] 百度开源分布式id生成器uid-generator源码剖析
《移动端IM开发者必读(一):通俗易懂,理解移动网络的“弱”和“慢”》
《移动端IM开发者必读(二):史上最全移动弱网络优化方法总结》
《现代移动端网络短连接的优化手段总结:请求速度、弱网适应、安全保障》
《小白必读:闲话HTTP短连接中的Session和Token》
《IM开发基础知识补课:正确理解前置HTTP SSO单点登录接口的原理》
《IM消息送达保证机制实现(一):保证在线实时消息的可靠投递》
《开源IM工程“蘑菇街TeamTalk”的现状:一场有始无终的开源秀》
《QQ音乐团队分享:Android中的图片压缩技术详解(上篇)》
《QQ音乐团队分享:Android中的图片压缩技术详解(下篇)》
《腾讯原创分享(一):如何大幅提升移动网络下手机QQ的图片传输速度和成功率》
《腾讯原创分享(二):如何大幅压缩移动网络下APP的流量消耗(上篇)》
《腾讯原创分享(三):如何大幅压缩移动网络下APP的流量消耗(下篇)》
《如约而至:微信自用的移动端IM网络层跨平台组件库Mars已正式开源》
《基于社交网络的Yelp是如何实现海量用户图片的无损压缩的?》
《腾讯技术分享:腾讯是如何大幅降低带宽和网络流量的(图片压缩篇)》
《腾讯技术分享:腾讯是如何大幅降低带宽和网络流量的(音视频技术篇)》
《字符编码那点事:快速理解ASCII、Unicode、GBK和UTF-8》
《子弹短信光鲜的背后:网易云信首席架构师分享亿级IM平台的技术实践》
《IM开发基础知识补课(五):通俗易懂,正确理解并用好MQ消息队列》
《微信技术分享:微信的海量IM聊天消息序列号生成实践(算法原理篇)》
《自已开发IM有那么难吗?手把手教你自撸一个Andriod版简易IM (有源码)》
《IM开发基础知识补课(六):数据库用NoSQL还是SQL?读这篇就够了!》
《适合新手:从零开发一个IM服务端(基于Netty,有完整源码)》
《IM里“附近的人”功能实现原理是什么?如何高效率地实现它?》
《IM开发基础知识补课(七):主流移动端账号登录方式的原理及设计思路》
《IM开发基础知识补课(八):史上最通俗,彻底搞懂字符乱码问题的本质》
《IM“扫一扫”功能很好做?看看微信“扫一扫识物”的完整技术实现》
《IM的扫码登录功能如何实现?一文搞懂主流应用的扫码登录技术原理》
>> 更多同类文章 ……
(本文同步发布于:http://www.52im.net/thread-2953-1-1.html)
文章浏览阅读2.5w次,点赞6次,收藏50次。官方解释是,docker 容器是机器上的沙盒进程,它与主机上的所有其他进程隔离。所以容器只是操作系统中被隔离开来的一个进程,所谓的容器化,其实也只是对操作系统进行欺骗的一种语法糖。_docker菜鸟教程
文章浏览阅读5.7k次,点赞3次,收藏14次。该如何避免的,今天小编给大家推荐两个下载Windows系统官方软件的资源网站,可以杜绝软件捆绑等行为。该站提供了丰富的Windows官方技术资源,比较重要的有MSDN技术资源文档库、官方工具和资源、应用程序、开发人员工具(Visual Studio 、SQLServer等等)、系统镜像、设计人员工具等。总的来说,这两个都是非常优秀的Windows系统镜像资源站,提供了丰富的Windows系统镜像资源,并且保证了资源的纯净和安全性,有需要的朋友可以去了解一下。这个非常实用的资源网站的创建者是国内的一个网友。_msdn我告诉你
文章浏览阅读1.2k次。vue2封装对话框el-dialog组件_
文章浏览阅读4.7k次,点赞5次,收藏6次。MFC 文本框换行 标签: it mfc 文本框1.将Multiline属性设置为True2.换行是使用"\r\n" (宽字符串为L"\r\n")3.如果需要编辑并且按Enter键换行,还要将 Want Return 设置为 True4.如果需要垂直滚动条的话将Vertical Scroll属性设置为True,需要水平滚动条的话将Horizontal Scroll属性设_c++ mfc同一框内输入二行怎么换行
文章浏览阅读832次。检查Linux是否是否开启所需端口,默认为6379,若未打开,将其开启:以root用户执行iptables -I INPUT -p tcp --dport 6379 -j ACCEPT如果还是未能解决,修改redis.conf,修改主机地址:bind 192.168.85.**;然后使用该配置文件,重新启动Redis服务./redis-server redis.conf..._redis-server doesn't support auth command or ismisconfigured. try
文章浏览阅读4.9k次。济大数电实验报告_数据选择器及其应用
文章浏览阅读236次。1研究内容消费在生产中占据十分重要的地位,是生产的最终目的和动力,是保持省内经济稳定快速发展的核心要素。预测河南省社会消费品零售总额,是进行宏观经济调控和消费体制改变创新的基础,是河南省内人民对美好的全面和谐社会的追求的要求,保持河南省经济稳定和可持续发展具有重要意义。本文建立灰色预测模型,利用MATLAB软件,预测出2019年~2023年河南省社会消费品零售总额预测值分别为21881...._灰色预测模型用什么软件
文章浏览阅读1.2k次。12.4-在Qt中使用Log4Qt输出Log文件,看这一篇就足够了一、为啥要使用第三方Log库,而不用平台自带的Log库二、Log4j系列库的功能介绍与基本概念三、Log4Qt库的基本介绍四、将Log4qt组装成为一个单独模块五、使用配置文件的方式配置Log4Qt六、使用代码的方式配置Log4Qt七、在Qt工程中引入Log4Qt库模块的方法八、获取示例中的源代码一、为啥要使用第三方Log库,而不用平台自带的Log库首先要说明的是,在平时开发和调试中开发平台自带的“打印输出”已经足够了。但_log4qt
文章浏览阅读786次。全局观思维模型,一个教我们由点到线,由线到面,再由面到体,不断的放大格局去思考问题的思维模型。_计算机中对于全局观的
文章浏览阅读330次。一、CountDownLatch介绍CountDownLatch采用减法计算;是一个同步辅助工具类和CyclicBarrier类功能类似,允许一个或多个线程等待,直到在其他线程中执行的一组操作完成。二、CountDownLatch俩种应用场景: 场景一:所有线程在等待开始信号(startSignal.await()),主流程发出开始信号通知,既执行startSignal.countDown()方法后;所有线程才开始执行;每个线程执行完发出做完信号,既执行do..._countdownluach于cyclicbarrier的用法
文章浏览阅读508次。Prometheus 算是一个全能型选手,原生支持容器监控,当然监控传统应用也不是吃干饭的,所以就是容器和非容器他都支持,所有的监控系统都具备这个流程,_-自动化监控系统prometheus&grafana实战
文章浏览阅读4.7k次。输入关键字,可以通过键盘的搜索按钮完成搜索功能。_react search