zip安装包增量方案
音视频房间的架构设计思考
HashMap实现原理
摘要
HashMap是我们日常比较常用的数据结构,put(key, value),可以通过key来查找对象,JDK 1.8 中引入红黑树来优化查询效率,接下来就底层算法实现和原理做出一个详细的分析
HashMap 基本组成元素
如下图:
其基本组成部分是由一个2的n次幂长度的容量数组,最基本组成单元是Node节点,节点之间可以组成链式结构。如果节点数量大于8,会将其转成红黑树。
(1) HashMap put(key, value) 处理步骤
1. 需要找到key的hashcode所对应的数组下标位置
2. 如果数组中存在Node节点,key相同值覆盖,不同则追加链式链起来
3. 如果链中的Node节点大于8 转为红黑树
步骤就是上面三步,我们先围绕如何找到哈希桶数组下标位置,并且使用了哪些手段。
寻找key的hashcode对应哈希桶数组的index
- 记住重点,HashMap中数组的长度总是2的n次幂
- Java中32位字节
- 确定哈希桶数组索引位置
先看一段源码:
1 | static final int hash(Object key) { |
解释下:
hash(Object key)中是取得key对象的hashcode,
优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:
(h = k.hashCode()) ^ (h >>> 16)
右移16位,自己的高半区和低半区异或,就是为了混合原始哈希码的高位和低位,以此来加大低位随机性。
,主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。
- 得到hashcode值,换算成2进制
- 将值右移16位,就成了高16位与低16位进行异或运算
- 得到异或后的hashcode
这样获取的hashcode的随机性更强,也就是说产生hash碰撞的几率更低。
获取哈希桶数组的index
计算机中下面2个是等价的
1 | a%(2^n) 等价于 a&(2^n-1) |
举个例子:
n = 4;
a = 23;
23 % 16 = 7 (模运算)
我们转换成 & 运算,先转换成二进制
23 -> 16 + 4 + 2 + 1 -> 10111
2^n-1 = 16-1 = 15. -> 8 + 4 + 2 + 1 -> 01111
进行 & 运算
1 | 10111 |
经过以上步骤,我们就能给从一个key的hashcode值,通过(h = key.hashCode()) ^ (h >>> 16) & (length-1)
计算key对应哈希桶数组的index。
HashMap是利用了数组的取值的时间复杂度为O(1),然后通过算法,利用hashcode来找到对应的index,最好的算法是key均匀的分布在数组桶上。最差的算法是所有的key都分布在一个index里面。
Java 1.8 中的HashMap resize
使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。
扩展成一倍后,我们的高位增加了1个bit,新的key的hashcode计算后对应的index就发生新的变化:
因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:
所以在Java 1.8中HashMap的效率更高,省去了重新计算的时间
HashMap的线程不安全
2022上半年
焦虑、动荡
人生不知不觉的步入31岁,从一个懵懂的少年,已经成为人们口中的中年大叔。
2022年一切变化真的来得太快 毕业季
寒冬
真真实实的发生在自己身处的行业,面对身边的小伙伴都在讨论,不敢消费,越来越卷,似乎一切都是那么的梦幻。然而又是那么的真实。
步入腾讯
有幸通过自己的努力,拿到进入 阿里巴巴、腾讯互联网大厂的门票,也证明自己的努力是有回报的。
来自农村出身的自己,成了身边人羡慕的对象。期间自己吃过多少苦,熬了多少夜,面多过多少压力只有自己心里知道。
面对寒冬
在这个充满竞争、压力的社会,提升自己的硬实力,在哪都是硬道理。努力做一个靠谱
、有始有终
、谦虚
的人。 保持内心的阳光,因为
一颗阴暗的心永远托不起一张灿烂的脸
- 靠谱
- 我认为这个词是对人崇高的评价,只有让自己成为靠谱的人,才能够获取更多的机会
- 有始有终
- 做事要有始有终,自己要完成闭环
- 谦虚
- 接受变化,多听取别人的发言,大家站在不同的角度思考,立场都是不一样的,只有了解多方的信息,我们才能做出相对靠谱的决定
保持学习心态
人啊,长大了都是孤独的。接受自己的平庸,多读书,和伟人对话,这个时代差异真的是认知的差异。只有自己的认知到达了该有的境界,才能将你推向更高的水平
坚持写写博客吧
当过完一年回过头来,或许除了挣得一些金钱外,留给自己的回忆真的不多,尤其是当自己孤独无助,独自一个人面对的事情
Cronet请求流程,以及优雅的注入httpDNS
【音视频开发】视频数据格式、Dash协议的了解
I帧和IDR帧
DR(Instantaneous Decoding Refresh)–即时解码刷新。
I帧与IDR帧的相同点在于:
- I和IDR帧都是使用帧内预测的
- 都是同一个东西而已,在编码和解码中为了方便,要首个I帧和其他I帧区别开,所以才把第一个首个I帧叫IDR,这样就方便控制编码和解码流程
I帧与IDR帧的不同点在于:
- IDR帧的作用是立刻刷新,使错误不致传播,从IDR帧开始,重新算一个新的序列开始编码。而I帧不具有随机访问的能力,这个功能是由IDR承担
- IDR会导致DPB(DecodedPictureBuffer 参考帧列表——这是关键所在)清空,而I不会
- IDR图像一定是I图像,但I图像不一定是IDR图像
- 一个序列中可以有很多的I图像,I图像之后的图像可以引用I图像之间的图像做运动参考;对于IDR帧来说,在IDR帧之后的所有帧都不能引用任何IDR帧之前的帧的内容,与此相反,对于普通的I-帧来说,位于其之后的B-和P-帧可以引用位于普通I-帧之前的I-帧
- 从随机存取的视频流中,播放器永远可以从一个IDR帧播放,因为在它之后没有任何帧引用之前的帧。但是,不能在一个没有IDR帧的视频中从任意点开始播放,因为后面的帧总是会引用前面的帧
MP4 格式
FMP4格式
在Fragmented MP4文件中都有三个非常关键的 boxes:moov
、moof
和mdat
。
- moov(movie metadata box)
和普通MP4文件的‘moov’一样,包含了file-level的metadata信息,用来描述file。 mdat
(media data box)
和普通MP4文件的mdat
一样,用于存放媒体数据,不同的是普通MP4文件只有一个mdat
box,而Fragmented MP4文件中,每个fragment都会有一个mdat
类型的box。moof
(movie fragment box)
该类型的box存放的是fragment-level的metadata信息,用于描述所在的fragment。该类型的box在普通的MP4文件中是不存在的,而在Fragmented MP4文件中,每个fragment都会有一个moof
类型的box。
一个moof
和一个mdat
组成Fragmented MP4文件的一个fragment,这个fragment包含一个video track或audio track,并且包含足够的metadata以保证这部分数据可以单独解码。Fragment的结构如下所示。
Dash描述文件
MPD
媒体文件的描述文件(manifest),作用类似HLS的m3u8文件。MPD文件以XML格式组织Representation
对应一个可选择的输出(alternative)。如,480p video,720p video, 44100采样 audio,22050采样audio,都使用Representation描述。Segment(分片)
每个Representation会划分为多个Segment。Segment分为4类,其中,最重要的是:Initialization Segment(每个Representation都包含1个Init Seg),Media Segment(每个Representation的媒体内容包含若干Media Seg)
格式之间的关系
Dash中的数据对应的就是 FMP4 的不同数据块,FMP4每个数据块都能够单独的进行解码
Dash FMP4 与 HLS TS
服务器的cache效率会降低
实际的streaming应用场景中,往往需要cdn的支持,经常会被client请求的媒体分片就会存在距离client最近的edge server上。对于fmp4 streaming的情况,因为需要的文件更少,cache命中率也就更高。
举个例子:可能某一个audio track会和其他各种video track组合,那么就可以将这个audio track放在edge server上,而不用每次都跟origin server去请求。
相对地,在streaming TS流时,因为每一个音视频组合的都需要以复用文件的形式存储,组合数又非常多,相当于分母大了,edge server就会有很大的几率没有缓存需要的组合而要去向orgin server请求。
媒体文件存储成本和媒资管理成本增加
假设server端将video track编码为三个质量级别V1, V2, V3,audio track也被编码为三个质量级别A1, A2, A3,那么如果利用fmp4格式的特性,我们只需要存储这6份媒体文件,player在播放时再自主组合不同质量级别的音视频track即可。
而对于TS,则不得不提前将3x3=9种不同的音视频复用情况对应的媒体文件都存储到server端,平白无故多出三份文件的存储成本。实际中,因为要考虑到大屏端、小屏端、移动端、桌面端、不同语言、不同字幕等各种情况,使用TS而造成的冗余成本将更加可观。同时,存储文件的增加也意味着媒资管理成本的增加。这也是包括Netflix在内的一些公司选择使用fmp4做streaming格式的原因。
manifest文件更加复杂
fmp4格式的特性可以确保每一个单独的媒体分片都是可解密可解码的(当然player需要先从moov box中读到它们的编解码等信息),这意味着server端甚至根本不需要真的存储一大堆分片,player可以直接利用byte range request技术从一个大文件中准确地读出一个分片对应的media data,这也使得对应manifest(mpd)文件可以更加简洁。针对不同语言的音频,都只需要存一个大文件就够了。
相对地,在streaming TS流时,不得不在manifest(m3u8)文件中把成百上千个ts分片文件全都老老实实地记录下来。
无缝码流切换
无缝码流切换实现的关键在于
当第一个码流播放结束时,也就是发生切换的时间,第二个码流一定要以关键帧开始播放。在streaming TS流时,因为不能保证每一个TS chunk一定以关键帧开始,做码流切换时就意味着要同时download两个码流的相应分片,同时解析两个码流,然后找到关键帧对应的位置,才能切换。同时下载、解析两个码流的媒体内容对网络带宽以及设备性能都形成了挑战。而且有意思的是,如果当前网络环境不佳,player想要切换到低码率码流,结果还要在本来就不好的网络环境下同时进行两个码流的下载,可谓是雪上加霜。
而在fmp4中,除了保证各个分片一定以IDR帧开始外,还能保证不同码流的分片之间在时间线上是对齐的。而且streaming fmp4流时因为不要求音视频复用存储,也就意味着视频和音频的同步点可以不一样,视频可以全都以GOP边界作为同步点,音频可以都以sync frame作为同步点,这都使得无缝码流切换更简单。
- 平滑切换就是一定要切换的时候是以关键帧开始
Dash的大致流程
C++ Dash 移植的方案
- ffmpeg dash实现(C语言),一般都会基于ffmpeg的底层数据结构来完成dash的实现
- libdash (C++ 语言)库的时间相对比较老
多网络库组件化sdk
背景
个人一直在从事某国际娱乐App的网络优化事项,最初的网络接口的形态相对比较涣散,为了能够更高效、稳定的进行网络优化,我们提出将App的网络进行组件化。经过进一步的讨论,我们提出了以下3个方面:
- 保持业务上层的使用不变,避免大面积的业务逻辑变动,从而给业务同学带来额外的使用成本
- 组件化抹平多网络库的上层稳定Api,提供稳定、可扩展的上层Api
- 在组件化中提供网络优化能力下沉,将网络优化能力在网络组件中进行
优化前后的网络形态对比
没有优化时的网络形态
- 基本上都是直接去实现对应模块的网络数据
- 通用一些的就是使用已经封装好的utils来支撑
- 各个模块非常的零散,这给优化也带来的挑战
优化后的大概层次结构
- 上层使用统一的Api
- 网络组件中支持众多的扩展,更好的支撑来业务的可变性
- 网络组件中抹平了不同网络库之间的差异,提供了口径统一的监控体系
- 组件化网络中提供了Gson、Json、PB、文件下载(支持续传)、重试、网络库、域名的调度能力,能够进一步的提高容错能力
目前状态
目前网络组件已经非常稳定,支撑了目前短链的所有请求。将使用和优化进行分离,业务同学不需要关系当前情况,而只需要简单的了解Api的使用,提高的业务开发对网络的复杂度。
组件化网络库的架构设计
我们先看看网络请求的流程结构图:
- 网络请求流程大体分为以上的流程,该流程不涉及具体的网络库中的处理细节,这里注重的是网络组件化的处理(面向业务)
大致架构的结构图
- 网络组件化主要是面向业务,提供可扩展的业务能力,同时能够在组件化内完成网络优化细节
OkHttp Sockettimeout 问题和优化方案
背景
OkHttp 在某些场景下,会出现SocketTimeout,然后一段时间内会有大量的超时情况(如果没有设置连接池,5min内(默认设置)),在网络统计的数据中,top的错误统计就是SocketTimeout。
这些问题的原因还需要从h2协议和连接池以及OkHttp的实现说起
OkHttp h2
OkHttp 实现h2的协议
- 连接复用
- 同一个连接允许多个stream
如下图:
- h2是建立在tcp上层的,上层的多路stream,tcp拥有的特性,h2协议照样存在(比如对头阻塞等)
- h2多个stream是在同一个连接,如果一个连接的请求数据出现丢包,那边该连接上的所以请求都会进行等待
如果该条连接上出现超时,换句话说,就是这个连接连接不上Server,但是网络库并不知道,还是将相同的host的请求添加到该连接,那么势必会造成后续加入的请求都是不可用的。
OkHttp ConnectionPool
连接池
- 全局一个核心数为0,最大线程数量无限大的线程池
- 缓存连接
- 判断当前连接是否可用
- 清理连接
获取连接
1 |
|
通过get这个方法,我们可以知道
- 通过遍历connections,获取RealConnection
- 然后通过RealConnection的isEligible方法判断当前的这个连接是否符合要求的,如果符合条件则返回这个连接,否则返回一个null的值
我们在看看isEligible(RealConnection.java)具体是做了哪些工作:
1 |
|
优先判断了以下的条件:
- 对于h2协议的连接 allocationLimit 是Integer.MAX_VALUE,所以h2协议的请求allocations.size() >= allocationLimit 一般情况下是false, noNewStreams时设置该Connection是否能够加入新的请求流,如果设置为true,那边该连接设置为不可用,在后续的连接清理时会被清理掉
- 判断当前的Connection的Address是否和参数中的Address是一直的值
1 |
|
- 判断当前Connection的host是否是同一个,如果是,结合1、2的条件判断,则这个连接就是复用的Connection
后续的条件就不详细分析了,可以自己详细看。
从连接池中获取一个可以复用的连接逻辑并不复杂,但是有几点需要注意,allocationLimit、noNewStreams这两个变量,控制着连接的可用性。
接下来,我们看下如何使用连接池的连接获取的方法,上层对这个连接做了哪些处理。
StreamAllocation 使用连接的逻辑
顾名思义StreamAllocation是叫做流分配。
- 创建一个流
- 将流分配到一个Connection上
我们关注点放在如何获取一个Connection上,先看下核心的代码逻辑:
1 | public HttpCodec newStream( |
newStream的方法中调用findHealthyConnection查找一个健康可用的连接。findHealthyConnection通过findConnection来获取了一个候选的 candidate 的RealConnection,然后对这个RealConnection进行可用性检查。
- candidate的successCount为0,这个是一个新创建的连接,这跳过检查
- 如果不是新创建的连接,会进行健康检查candidate.isHealthy(doExtensiveHealthChecks),如果返回false,则调用noNewStreams()将RealConnection的noNewStreams设置为true
我们重点关注下isHealthy这个方法的判断逻辑,如下:
1 |
|
外部传的参数是true,那么就会做一个连接的全面检查。
- 保存原来的读取超时时间,设置读超时为1ms,判断stream是否exhausted
在此处,如果出现SocketTimeoutException,OkHttp则认为该连接是可用的,然而我们线上出现了大量的SocketTimeout的情况,而且在本地的测试环境中也能够遇到经常性的超时,所以我们对这块进行了改造。 - 通过AB实验,我们能够看到优化后的实验方案数据要好很多
如何解决连接不可用
在网络监听处,产生SocketTimeout时,设置Connection的noNewStreams为true,如果更极致的话,就是反射调用ConnectionPool中 去除掉Connection