技术标签: 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)
文章浏览阅读3.7w次,点赞171次,收藏430次。这篇博客介绍Java环境的配置,主要是安装JDK,以及path、JAVA_hOME、CLASSPAT的配置,还会介绍配置这些的原因。_windows java环境配置
文章浏览阅读2.3k次。本实验需要使用SEED互联网仿真器(已集成到docker配置文件)。启动docker容器,配置文件在/Labsetup/outputs/目录下。由于要配置很多docker容器,所以构建+启动过程会比较漫长。.随着docker启动,仿真器也随之运行,仿真器所用到的设备均为docker容器。..._bgp seed
文章浏览阅读2.1k次。 需求如下:该搜索框是对整个页面的input检索 ,但与弹出层中的input冲突 博主几经辗转 简单处理 解决问题,思路如下:排除掉特定class的input。代码如下:$('input:not(.pop)', this.footer()).on('keyup change', function () { if (that.search() !== th..._input排他选择器
文章浏览阅读5.6k次,点赞6次,收藏20次。看到别人有个1024的勋章,特意留了一篇在今年的10.24日,看看会不会获得。在日常开发中可能涉及接口之间的相互调用,虽然在现在微服务的理念推广下,很多公司都采用轻量级的JSON格式做为序列化的格式,但是不乏有些公司还是有一些XML格式的报文,最近就在对接某个合作方的时候遇到了XML报文。在JSON报文爽快的转换下很难试用一个一个的拿报文参数,还是希望能直接将报文转换成Bean。接下来就了解到..._jaxb 泛型
文章浏览阅读1.2k次。numpy的主要数据对象是多维数组,其中包含相同类型的元素,通常是数字类型,每个元素都有一个索引。使用numpy前通常要导入包。import numpy as np目录类型维度创建运算索引和切片类型numpy的数组被称为ndarray。numpy.array只处理一维数组,而ndarray对象才提供更多功能。a = np.array([[1, 2, 3], [4, 5, 6]])type(a) # <class 'numpy.ndarray'>dtype属性可以获得元素的数_ndarray的位置
文章浏览阅读1.6w次。还在苦于网上找到的一些指令已经不适用了吗?还在苦于有些地方的指令有误吗?还在苦于有些地方整理的指令不够全面吗?那么你来对地方了!小编为大家整理了《我的世界》原版游戏常用的指令,这些基本足以满足各位的基本需求了!大家来一起看看吧!注:表示的是必须输入的部分,[方括号]表示的是可选择性输入的部分基本命令列表命令描述/?/help的替代命令,提供命令使用帮助。/ban + 玩家名字将玩家加入封禁列表。/..._gamemode指令java
文章浏览阅读5.5k次。在AppStore中的应用越来越重视动画效果的使用,一个良好动画效果可以让两个状态之间平滑地过度,也可以利用动画吸引住用户的眼球_oc uiview animate 关键帧
文章浏览阅读8.7k次。代码错误的原因和调试方法_代码报错
文章浏览阅读5.2k次,点赞9次,收藏40次。---恢复内容开始---1.认识游戏 1.1什么是游戏 1.1.1游戏的定义 任何人类正常生理需求之外的活动均可称为游戏 1.1.2游戏的分类 RPG角色扮演游戏、ACT动作游戏、AVG冒险游戏、FPS第一人称视角射击游戏、TPS第三人称视角射击游戏、FTG格斗游戏、SPT体育游戏、RAC竞速游戏、RTS即时战略游戏、STG..._深度解析java游戏服务器开发
文章浏览阅读4k次。CSRF是什么我就不解释了,百度一搜全是,比波姐的片源还要多,千篇一律都他么是复制粘贴。那为什么这个令牌(token)操作可以防范CSRF呢?下面我就随便说说说错了大家不要介意。首先我们要知道令牌是存储在session里面的,这个很重要 php代码如下<?php namespace app\index\controller; //我直接允许跨域,因为伪装..._tp5 开启csrf令牌
文章浏览阅读1.7k次,点赞2次,收藏6次。市盈率PE市盈率 = 市值/净利润概念解析:买入一家公司,几年回本,年化收益率:净利润/市值(市盈率的倒数)举例:砖头10万买个砖头,每年拍人带来1万利润,需要10年回本市盈率:10/1 = 10年化收益率:1/10 = 10%市净率PB市净率 = 市值/净资产净资产 = 总资产 - 负债举例:张三便利店,净资产:120万市值:1..._净资产收益率和股息率
文章浏览阅读737次。教育部昨举行「102年国立馆所文创商品设计比赛」颁奖典礼,台北科技大学创新设计研究所硕士生谢镇宇,为TW艺术教育馆设计「墨器」杯垫,取「默契」谐音,用5片压克力板,展现水墨画层层渲染效果,增加立体视觉感受,并在杯架后方加入LED光源,获评审肯定夺特优奖和奖金10万元。台南应用科技大学商品设计系学生高郁翔,为国立自然科学博物馆设计「恐龙化石钉书机」,他认为小朋友把钉书机钉下去的那一刻,会觉得像暴龙準_杯垫文创设计说明