伍中联(Vanda)的博客

当一切理所当然就没有你什么事了 当你说:“这个好麻烦,那么不要犹豫,主动出击”

0%

背景

最近转到QQ社交线这边,来负责海外的项目,其中涉及到音视频模块,考虑到业务的快速发展和长期迭代,需要对当前的房间音视频进行架构设计,目的是能够高效、低耦合、稳定的进行业务开发,同时能够形成统一的开发思想

摘要


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. 确定哈希桶数组索引位置

先看一段源码:

1
2
3
4
5
6
7
8
9
10
11
static final int hash(Object key) {
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

static int indexFor(int h, int length) {
return h & (length-1); //第三步 取模运算
}

解释下:
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
2
3
4
5
10111
01111
-----
00111 -> 2^2 + 2^1 + 2^0 = 4 + 2 + 1 = 7

经过以上步骤,我们就能给从一个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的线程不安全

  

焦虑、动荡

人生不知不觉的步入31岁,从一个懵懂的少年,已经成为人们口中的中年大叔。

2022年一切变化真的来得太快 毕业季 寒冬 真真实实的发生在自己身处的行业,面对身边的小伙伴都在讨论,不敢消费,越来越卷,似乎一切都是那么的梦幻。然而又是那么的真实。

步入腾讯

有幸通过自己的努力,拿到进入 阿里巴巴腾讯互联网大厂的门票,也证明自己的努力是有回报的。
来自农村出身的自己,成了身边人羡慕的对象。期间自己吃过多少苦,熬了多少夜,面多过多少压力只有自己心里知道。

面对寒冬

在这个充满竞争、压力的社会,提升自己的硬实力,在哪都是硬道理。努力做一个靠谱有始有终谦虚的人。 保持内心的阳光,因为

一颗阴暗的心永远托不起一张灿烂的脸

  • 靠谱
    • 我认为这个词是对人崇高的评价,只有让自己成为靠谱的人,才能够获取更多的机会
  • 有始有终
    • 做事要有始有终,自己要完成闭环
  • 谦虚
    • 接受变化,多听取别人的发言,大家站在不同的角度思考,立场都是不一样的,只有了解多方的信息,我们才能做出相对靠谱的决定

保持学习心态

人啊,长大了都是孤独的。接受自己的平庸,多读书,和伟人对话,这个时代差异真的是认知的差异。只有自己的认知到达了该有的境界,才能将你推向更高的水平

坚持写写博客吧

当过完一年回过头来,或许除了挣得一些金钱外,留给自己的回忆真的不多,尤其是当自己孤独无助,独自一个人面对的事情

背景

之前基于73版本的chromium编译定制了net模块,实现了hostResolve,预建连接、metric的remoteIp指标纬度的统计,目前已经间隔了快3年的时间,这次也安排了升级cronet库,并且剥离net模块,实现Android、iOS的双端编译。
这里面主要是分析下Cronet的请求流程。

创建CronetEngine

使用Cronet之前需要创建一个engine,然后通过该engine来请求,一般来说一个App中只会存在一个engine,那我们先看看Java层的CronetEngine

1

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:moovmoofmdat

  1. moov(movie metadata box)
    和普通MP4文件的‘moov’一样,包含了file-level的metadata信息,用来描述file。
  2. mdat(media data box)
    和普通MP4文件的mdat一样,用于存放媒体数据,不同的是普通MP4文件只有一个mdat box,而Fragmented MP4文件中,每个fragment都会有一个mdat类型的box。
  3. 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++ 语言)库的时间相对比较老

背景

个人一直在从事某国际娱乐App的网络优化事项,最初的网络接口的形态相对比较涣散,为了能够更高效、稳定的进行网络优化,我们提出将App的网络进行组件化。经过进一步的讨论,我们提出了以下3个方面:

  • 保持业务上层的使用不变,避免大面积的业务逻辑变动,从而给业务同学带来额外的使用成本
  • 组件化抹平多网络库的上层稳定Api,提供稳定、可扩展的上层Api
  • 在组件化中提供网络优化能力下沉,将网络优化能力在网络组件中进行

优化前后的网络形态对比

没有优化时的网络形态

  • 基本上都是直接去实现对应模块的网络数据
  • 通用一些的就是使用已经封装好的utils来支撑
  • 各个模块非常的零散,这给优化也带来的挑战

优化后的大概层次结构

  • 上层使用统一的Api
  • 网络组件中支持众多的扩展,更好的支撑来业务的可变性
  • 网络组件中抹平了不同网络库之间的差异,提供了口径统一的监控体系
  • 组件化网络中提供了Gson、Json、PB、文件下载(支持续传)、重试、网络库、域名的调度能力,能够进一步的提高容错能力

目前状态

目前网络组件已经非常稳定,支撑了目前短链的所有请求。将使用和优化进行分离,业务同学不需要关系当前情况,而只需要简单的了解Api的使用,提高的业务开发对网络的复杂度。

组件化网络库的架构设计

我们先看看网络请求的流程结构图:

  • 网络请求流程大体分为以上的流程,该流程不涉及具体的网络库中的处理细节,这里注重的是网络组件化的处理(面向业务)

大致架构的结构图

  • 网络组件化主要是面向业务,提供可扩展的业务能力,同时能够在组件化内完成网络优化细节

背景

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

private final Deque<RealConnection> connections = new ArrayDeque<>();

/**
* Returns a recycled connection to {@code address}, or null if no such connection exists. The
* route is null if the address has not yet been routed.
*/
@Nullable RealConnection get(Address address, StreamAllocation streamAllocation, Route route) {
assert (Thread.holdsLock(this));
for (RealConnection connection : connections) {
if (connection.isEligible(address, route)) {
streamAllocation.acquire(connection, true);
return connection;
}
}
return null;
}

通过get这个方法,我们可以知道

  • 通过遍历connections,获取RealConnection
  • 然后通过RealConnection的isEligible方法判断当前的这个连接是否符合要求的,如果符合条件则返回这个连接,否则返回一个null的值

我们在看看isEligible(RealConnection.java)具体是做了哪些工作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/** Current streams carried by this connection. */
public final List<Reference<StreamAllocation>> allocations = new ArrayList<>();

/**
* Returns true if this connection can carry a stream allocation to {@code address}. If non-null
* {@code route} is the resolved route for a connection.
*/
public boolean isEligible(Address address, @Nullable Route route) {
// If this connection is not accepting new streams, we're done.
if (allocations.size() >= allocationLimit || noNewStreams) return false;

// If the non-host fields of the address don't overlap, we're done.
if (!Internal.instance.equalsNonHost(this.route.address(), address)) return false;

// If the host exactly matches, we're done: this connection can carry the address.
if (address.url().host().equals(this.route().address().url().host())) {
return true; // This connection is a perfect match.
}

// At this point we don't have a hostname match. But we still be able to carry the request if
// our connection coalescing requirements are met. See also:
// https://hpbn.co/optimizing-application-delivery/#eliminate-domain-sharding
// https://daniel.haxx.se/blog/2016/08/18/http2-connection-coalescing/

// 1. This connection must be HTTP/2.
if (http2Connection == null) return false;

// 2. The routes must share an IP address. This requires us to have a DNS address for both
// hosts, which only happens after route planning. We can't coalesce connections that use a
// proxy, since proxies don't tell us the origin server's IP address.
if (route == null) return false;
if (route.proxy().type() != Proxy.Type.DIRECT) return false;
if (this.route.proxy().type() != Proxy.Type.DIRECT) return false;
if (!this.route.socketAddress().equals(route.socketAddress())) return false;

// 3. This connection's server certificate's must cover the new host.
if (route.address().hostnameVerifier() != OkHostnameVerifier.INSTANCE) return false;
if (!supportsUrl(address.url())) return false;

// 4. Certificate pinning must match the host.
try {
address.certificatePinner().check(address.url().host(), handshake().peerCertificates());
} catch (SSLPeerUnverifiedException e) {
return false;
}

return true; // The caller's address can be carried by this connection.
}

优先判断了以下的条件:

  1. 对于h2协议的连接 allocationLimit 是Integer.MAX_VALUE,所以h2协议的请求allocations.size() >= allocationLimit 一般情况下是false, noNewStreams时设置该Connection是否能够加入新的请求流,如果设置为true,那边该连接设置为不可用,在后续的连接清理时会被清理掉
  2. 判断当前的Connection的Address是否和参数中的Address是一直的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/*Address.java*/

boolean equalsNonHost(Address that) {
return this.dns.equals(that.dns)
&& this.proxyAuthenticator.equals(that.proxyAuthenticator)
&& this.protocols.equals(that.protocols)
&& this.connectionSpecs.equals(that.connectionSpecs)
&& this.proxySelector.equals(that.proxySelector)
&& equal(this.proxy, that.proxy)
&& equal(this.sslSocketFactory, that.sslSocketFactory)
&& equal(this.hostnameVerifier, that.hostnameVerifier)
&& equal(this.certificatePinner, that.certificatePinner)
&& this.url().port() == that.url().port();
}

  1. 判断当前Connection的host是否是同一个,如果是,结合1、2的条件判断,则这个连接就是复用的Connection

后续的条件就不详细分析了,可以自己详细看。

从连接池中获取一个可以复用的连接逻辑并不复杂,但是有几点需要注意,allocationLimit、noNewStreams这两个变量,控制着连接的可用性。

接下来,我们看下如何使用连接池的连接获取的方法,上层对这个连接做了哪些处理。

StreamAllocation 使用连接的逻辑

顾名思义StreamAllocation是叫做流分配。

  1. 创建一个流
  2. 将流分配到一个Connection上

我们关注点放在如何获取一个Connection上,先看下核心的代码逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public HttpCodec newStream(
OkHttpClient client, Interceptor.Chain chain, boolean doExtensiveHealthChecks) {
int connectTimeout = chain.connectTimeoutMillis();
int readTimeout = chain.readTimeoutMillis();
int writeTimeout = chain.writeTimeoutMillis();
int pingIntervalMillis = client.pingIntervalMillis();
boolean connectionRetryEnabled = client.retryOnConnectionFailure();

try {
RealConnection resultConnection = findHealthyConnection(connectTimeout, readTimeout,
writeTimeout, pingIntervalMillis, connectionRetryEnabled, doExtensiveHealthChecks);
HttpCodec resultCodec = resultConnection.newCodec(client, chain, this);

synchronized (connectionPool) {
codec = resultCodec;
return resultCodec;
}
} catch (IOException e) {
throw new RouteException(e);
}
}


/**
* Finds a connection and returns it if it is healthy. If it is unhealthy the process is repeated
* until a healthy connection is found.
*/
private RealConnection findHealthyConnection(int connectTimeout, int readTimeout,
int writeTimeout, int pingIntervalMillis, boolean connectionRetryEnabled,
boolean doExtensiveHealthChecks) throws IOException {
while (true) {
RealConnection candidate = findConnection(connectTimeout, readTimeout, writeTimeout,
pingIntervalMillis, connectionRetryEnabled);

// If this is a brand new connection, we can skip the extensive health checks.
synchronized (connectionPool) {
if (candidate.successCount == 0) {
return candidate;
}
}

// Do a (potentially slow) check to confirm that the pooled connection is still good. If it
// isn't, take it out of the pool and start again.
if (!candidate.isHealthy(doExtensiveHealthChecks)) {
noNewStreams();
continue;
}

return candidate;
}
}

newStream的方法中调用findHealthyConnection查找一个健康可用的连接。findHealthyConnection通过findConnection来获取了一个候选的 candidate 的RealConnection,然后对这个RealConnection进行可用性检查。

  • candidate的successCount为0,这个是一个新创建的连接,这跳过检查
  • 如果不是新创建的连接,会进行健康检查candidate.isHealthy(doExtensiveHealthChecks),如果返回false,则调用noNewStreams()将RealConnection的noNewStreams设置为true

我们重点关注下isHealthy这个方法的判断逻辑,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/** Returns true if this connection is ready to host new streams. */
public boolean isHealthy(boolean doExtensiveChecks) {
if (socket.isClosed() || socket.isInputShutdown() || socket.isOutputShutdown()) {
return false;
}

if (http2Connection != null) {
return !http2Connection.isShutdown();
}

if (doExtensiveChecks) {
try {
int readTimeout = socket.getSoTimeout();
try {
socket.setSoTimeout(1);
if (source.exhausted()) {
return false; // Stream is exhausted; socket is closed.
}
return true;
} finally {
socket.setSoTimeout(readTimeout);
}
} catch (SocketTimeoutException ignored) {
// Read timed out; socket is good.
} catch (IOException e) {
return false; // Couldn't read; socket is closed.
}
}

return true;
}

外部传的参数是true,那么就会做一个连接的全面检查。

  • 保存原来的读取超时时间,设置读超时为1ms,判断stream是否exhausted
    在此处,如果出现SocketTimeoutException,OkHttp则认为该连接是可用的,然而我们线上出现了大量的SocketTimeout的情况,而且在本地的测试环境中也能够遇到经常性的超时,所以我们对这块进行了改造。
  • 通过AB实验,我们能够看到优化后的实验方案数据要好很多

如何解决连接不可用

在网络监听处,产生SocketTimeout时,设置Connection的noNewStreams为true,如果更极致的话,就是反射调用ConnectionPool中 去除掉Connection

LeakCanary流程分析

  • 在页面进行销毁时,调用watch方法,然后框架自动处理对象是否被回收
  • Activity、Fragment有生命周期回调,所以在destroy的时候进行watch
  • 这里面的核心操作是,用弱引用引用watch的对象,然后加入一个引用队列,当该引用队列poll对象不为null时,说明垃圾回收器认为该对象需要被回收