码农戏码

新生代农民工的自我修养

0%

单一职责原则 SRP,single responsibility principle

SRP是所有原则中最简单的之一,也是最难正确运用的之一,也是我们日常中最常用的一个

不管是编码,重构,甚至当下流行的微服务中

在很多团队的规范中,都会听到一条编码规范:一个方法不要超过x行代码

作为一群自命不凡的程序员,为什么在规范中却有如此一条格调不对称规范

主要问题就在于思维对SRP的缺失


微服务这个术语的一个问题是会将你的关注点错误地聚集在“微”上。它暗示服务应该非常小。很多团队在实施时,也是往小了去考虑,偏移了核心目标

微服务的目标是将精心设计的服务定义为能够由小团队开发的服务,并且交付时间最短,与其它团队协作最小。

理论上,团队可能只负责单一服务,因此服务绝对不是微小的

单一

从个人理解可以分为狭义与广义

狭义:

狭义只是从面向底层实现细节的设计原则

一个类而言,应该仅有一个引起它变化的原因

在日常中,在编写方法或者重构方法,也是以这个为原则,即确保一个函数只完成一个功能。

在将大方法重构成小方法时经常会用到这个原则

广义:

相对狭义,适用的范围相对大些,不再是一个类,一个方法,亦或是一个原因

任何一个软件模块都应该只对某一类行为者负责

“软件模块”不再只是一个类,可以是一组紧密相关的函数和数据结构,甚至一个独立应用服务

职责

什么是职责?如果一个类承担多于一个职责,那么引起它变化的原因就会有多个

在SRP中,职责定义为“变化的原因”,如果你能够想到多于一个的动机去改变一个类,那么这个类就具有多于一个的职责

因此对于职责的定义需要结合具体业务,有时从感性上理解一个类的多个方法应该拆分,但如果应用程序的变化方式总是导致这几个职责同时变化,那么就不需要分离

这是近期在公司做的一次分享,这几年的互联网开发,算比较幸运,团队一直践行完善这套规范,没有太多的阻碍,得益于公司整体氛围,以及团队对规范和写文档的不排斥,形成了良好的开发习惯

在这次分享后,发现好些大V也在谈规范,写文档,估计是前段时间阿里又发布了开发手册(华山版),借鉴于一下,对一些细节做些补充,整理出来

整体流程

这个流程整体分为三个大阶段:需求阶段,开发阶段,上线阶段

需求阶段

需求分析

这个阶段主要是产品主导,收集痛点,归集需求,制定目标,与架构师讨论架构方案,与安全评估业务安全性

这儿可根据需求大小,具体行事,比如有些需求涉及方比较多,可能需要多次分组开会,不管是可行性分析,还是讨论方案,不是一次就能完成的

需求评审

当产品已经确定好这些方面,开始输出PRD,与研发、测试一起评审需求

研发与测试需要理解需求,更要挑战需求;

挑战需求的目的不是砍需求,而是确认产品在需求分析阶段的工作完备程度,比如遗留数据处理,对当前系统的影响层面,是否与当前系统重复度过高,业务价值

只有经过充分讨论,才能理解需求,完善需求,防止后期需求返工,某个细节没有考虑,影响整体设计实现

这儿各个团队实践方式各不相同,比如有些是所有团队成员都要参与,而有些只有具体参与开发测试参与

个人推崇所有成员都参与,这样一是讨论可以更充分,二是信息共享,防止因某成员个人原因,推迟需求进度

需求排期

对需求大家都达成了共识,此时就需要产品去需求确定优先级,排期开发

确定开发周期,这儿也有很多具体做法,有些团队是TL根据需求难易程序,变动大小,结合具体开发人员直接给出时间;有些团队是具体开发自行评估时间

一般都是由开发人员自行评估,只要在合理范围内,都给予认同

当然在确定开发周期时,必须给出依据,依据来源于详细设计,对于详细设计文档具体形式后面再谈,至少开发人员知道需要增加多少接口,修改多少接口,大概逻辑;不然评估时长就是一个空谈,造成整个项目的失控

开发阶段

需求阶段,从产品需求分析到开发人员评估出开发周期就已经结束了;下一个阶段进入开发阶段

开发阶段的进度,可以说八成是依赖第一阶段的成果。编码速度,实现手段只要是正常业务需求,一般都不会拖延时长

第一阶段成果,对于开发人员来讲,就是详细设计文档,文档中有了相应流程图,伪代码,具体涉及接口也有了,此时就是一个代码翻译过程

此阶段测试,需要输出测试用例,进行冒烟,回归测试;

自动化脚本完善

上线阶段

测试完成之后,就准备上线了。

根据确定的上线日期,提前核对checklist

对一些需要提前的变更开始申请审批流程

配合监控系统,需要对一些业务监控项进行配置

产品开始对预发布环境进行验收,验收成功后;发布正式环境

上线收尾

收尾工作,这个阶段,还有大量工作需要去做

  1. 产品对需求进行总结,收集数据,分析效果,为下一期需求做准备
  2. 开发需要对代码进行整理,比如有些是为了灰度而生的无用代码可以删除

一个完整的需求开发流程到此结束,当然这只是理想状态,还有很多不可预测问题,当然你也会吐槽,这是典型的瀑布开发模型,在敏捷大行其道时,是不是太守旧,太迟钝,都2091年了,为什么还在玩这一套

理想是丰满的,现实是骨感的。好比敏捷开发的参与者是一群开发经验丰富和才华横溢的开发人员,而这样的团队有多少?强硬为了敏捷而敏捷会不会造成项目的不可控呢?

当然瀑布模型也有天生的缺点:每个阶段的严格性,缺乏灵活性,而现实需求却是经常变化的

所以单纯地选择哪个模型是不可取的,只能根据实际情况出发,为业务提供最大化服务


细则规范

很多人都在要规范,但好像从没思考过为什么需要规范?

《阿里巴巴java开发手册》:手册的愿景是码出高效,码出质量

现代软件架构的复杂性需要协同开发完成,如何高效地协同呢?无规矩不成方圆,无规范难以协同,比如,制订交通法规表面上是要限制行车权,实际上是保障公众的人身安全,试想如果没有限速,没有红绿灯,谁还敢上路行驶?对软件来说,适当的规范和标准绝不是消灭代码内容的创造性、优雅性,而是限制过度个性化,以一种普遍认可的统一方式一起做事,提升协作效率,降低沟通成本。 代码的字里行间流淌的是软件系统的血液,质量的提
升是尽可能少踩坑,杜绝踩重复的坑,切实提升系统稳定性,码出质量

从上段可以看出几个目的

  1. 高效协同,降低沟通成本;书同文,车同轨
  2. 码出质量,降低故障率;
  3. 工匠精神,追求卓越

评审会议

很多开发人员最怕开会,更要命的是很多会议是效率低下的。主要表现:

  • 在没有基本的认知共识就被拉去开会:这可能是主持者没有提前知会,同步资料;以及没有在线下达到一定共识就开会,结果会上各种讨论;也可能是参会人员本身也没有提前准备
  • 会后没有结论,或者结论不明确

所以在参与评审后,需要有一份输出,文档或者邮件,主要包括以下内容

  1. 评审日期与轮次
  2. 业务需求的目的及价值描述
  3. 参与人员及角色
  4. 评审附件(PRD或邮件)
  5. 评审结论
  6. 评审遗留问题及跟进人

需求PRD

开发人员,最烦就是口头需求,一句话需求,需要明文禁止

产品写PRD,其实是个基本职业素养,结果现在还要明文规定,也算是个悲哀。

为什么要出PRD,其实不是开发人员故意为难产品,而是让产品深刻理解需求,看这又是个怪事,产品还有不理解业务需求的,但就是常有产品自己都不理解业务,还一本正经给研发提开发需求。

写PRD的过程,就是梳理思考的过程,让需求更明确,流程更完整,细节更透彻,这样就不会出现提交给开发时,被开发一堆问题阻塞住。也可以防止在开发过程中,却发现整个业务没有形成闭环,造成返工,延时

那么开发如何拒绝口头需求,一句话需求呢?

有时产品比较强势,开发人员不好沟通,此时TL就应该对团队明确规定,禁止产品此类行为,也要禁止开发接受此类需求,不能为了一时快,而整个工期慢

在接受到此类需求时,也需要一定的沟通技巧:

  1. 多问几个为什么:这比如你这个需求背后的目的和价值是什么?做了之后有什么预期的收益,为什么这么做就可以达到这个收益,你可以不直接问业务方,但是你也需要问自己,业务方的这个目标和做这个需求的路径是否可以匹配得上,如果实现路径存在逻辑漏洞或者不是最佳的则这个需求也就没有做的必要性

  2. 给出替代方案:经过上面的步骤,其实你会发现你已经过滤了一批无效的一句话需求,而有些需求可能是有一定的存在价值,但是可能业务方提到的点并不是有效的方案或者说成本太大的方案,这时你就需要思考替代方案,尽量通过现有方案或者小成本的方式来满足业务方,间接的达到“拒绝”的效果

  3. 不能直接说不,但可以有条件的说是:当你确定这个需求是ok的,但你确实暂时抽不出时间来搞定这个事情的时候,这时关键在于我们不能直接拒绝业务方,长此以往会影响到后续的合作关系,这种情况你可以说,这个需求我接受,但是我可能需要较长一些的缓冲时间或者砍一些需求(部分满足),又或者必须要按时上的话,不能保证项目的上线后的效果、质量等,让业务方来做部分的取舍

详细设计文档

首先禁止没有文档,直接修改代码;这跟需求PRD类似,强迫开发人员思考需求,完善需求,胸中有丘壑,下笔自有神;不能在编码过程,边写边思考,不仅慢,还会漏洞百出

其实让团队写文档,也是个难事,推动很难,尤其管理者没有引起重视,就更难。这是个怪事,不喜欢写文档,却喜欢被返工,在开发过程因需求逻辑不完备而加班赶点,从上到下默认了这种怪事的正常化

为什么要写设计文档?

  • 对自己,让自己在动手写代码之前,帮助自己想得更清楚;
  • 对项目,保证信息的一致性,保证项目的可控性,减少项目风险;
  • 对团队,确保知识的沉淀与传承;

项目涉及多少个子系统,每个子系统涉及多少个模块,模块间的依赖关系如何,彼此要提供多少个接口,每个接口的参数如何,接口实现过程中上下游交互如何,核心逻辑用什么技术方案实现…

难道相关技术人都一清二楚么?很多自信的技术大神,“以为”懂了,但却讲不明白,其实就是不懂。很多“讲得明白”,却“写不清楚”,其实就是没懂透。把一个项目,一个技术问题,按照逻辑,用文字来一遍,才表示真正的想清楚了

这也是现在流行的,一解释都懂,一问都不知,一讨论就吵架


不再写过多为什么要写文档了,一个习惯的改变不可能一下子就改变,这需要一个过程,也需要自我大胆尝试

这儿给出一些实践,详细设计文档写些什么

其实一份详细设计文档,整体分为两个部分:功能需求与非功能需求

1、需求信息

这儿包括需求背景,业务价值,预计上线时间,架构设计wiki,产品及开发负责人,涉及到的服务,上下游服务

2、系统流程图

阐述整体设计思路,涉及算法时,还需要详细算法思路

包含上下游系统交互和数据流向,建议viso或者astash图,要保存原图文件以防后期维护修改

当然最好还要把设计思路背景说明一下,有多种方案时也罗列一下,因为系统现有状况,进度安排,历史数据等等原因,而选择了当前方案,这样自我分析完整,也免将来别人接手时可以追溯

3、接口列表

这儿列出所有涉及到的接口列表

标明新增加或者修改,以及接口详细入参,返回值

一般会有api doc,或者类似swagger工具,接口变化时,也可以相应变化;如果没有,那只能在文档中详细输出

4、定时任务

有些任务不需要,有些任务可能有很多,需要指出任务功能,频率

5、存储变更

比如缓存,数据结构,过期时间,预计数据增长

DB表设计,表修改,索引信息,数据增长量;有新的业务场景,一定要请DBA帮忙评估索引或者其他信息

6、配置组件

配置:比如配置中心,增加修改配置项,常为了灰度增加一些开关之类

组件:第三方依赖jar,不管是公司自研,还是外部开源;关注新特性给系统带来的变化;这个对开发工作量很小,只需要修改版本号,但测试可能需要一些回归量,尤其常出现的包冲突,造成日志不能正常输出

7、非功能需求

接口在日常和大促时的调用量评估,是否有降级方案,灰度方案,能不能重试,需不需要压测,这些都是围绕服务治理做预案

这其实是个很大的模块,很多已经深入骨髓,变成常态,比如灰度,现在都是7*24小时在线服务的,前后版本的兼容必须考虑到

总结

当然这些并不是必须的,可以根据实际情况变通,有增有减;当然你也可能从不写文档,很多人喜欢看源码,而不看文档;其实这有些本末倒置,源码只是告诉你了how,而文档才解释了what,why

架构师是很多码农的追求,架构师如何设计系统,如何让开发人员去实施呢?当然是文档,总不能直接给代码吧

监控之前只总结了一篇《微服务-监控》,比较宏观。其中很多细节没有过深关注到,主要还是没有实践过,更没有去深度思考,所以很多有意思的技术点都错过了,比如traceid的生成,传递

大牛圈总的大作《微服务系统架构之分布式traceId追踪参考实现》已经给出解决方案,但还是再主动总结一下

意义

为什么需要traceid,为了查看完整的调用链,一旦调用过程中出现问题,可以第一时间定位到问题现场

整个调用链是一棵树形结构,traceid的传递涉及到主干与支干,进程内与进程外

生成

原则是唯一不重复,比如现成的UUID

但UUID一是丑、无意义,二是string;

从字面意义以及未来落盘都不能说是最佳方案,比如想让traceid包含信息更丰富一些,能一眼看出此traceid是主干还是分支

此traceid有没有最终落盘(这儿涉及到落盘抽样率,每天服务处理海量请求,总不能每个traceid都落盘)

Random

这儿引申到如何更好地获取一个随机数又是一个课题,另开篇吧

传递

《熔断机制》中提过,服务调用是一个1->N扇出,调用链展现出对应的树形结构,但调用嵌套都不会深,一般两层就差不多了

  • traceId1
    • traceId1.1
      • traceId1.1.1
    • traceId2.1
    • traceId3.1

进程外

服务之间的传递

serverA –> serverB – serverC

这儿在设计传输协议时,在协议头里面带上traceid

进程内

主干

这种场景ThreadLocal是最佳手法

支干

比如serviceA – > remote.serviceB

trace是个树形结构,可以将remote.serviceB的traceId.parentId = serviceA.traceId

异步子任务

子线程可以通过InheritableThreadLocal传递traceid

顺带一下,InheritableThreadLocal的详细实现,先可补习一下ThreadLocal《解析ThreadLocal》

在创建Thread时,会从父线程的inheritableThreadLocals复制到子线程中去,这样在子线程中就能拿到在父线程中的赋值

1
2
3
4
5
6
7
8
9
/* ThreadLocal values pertaining to this thread. This map is maintained
* by the ThreadLocal class. */
ThreadLocal.ThreadLocalMap threadLocals = null;

/*
* InheritableThreadLocal values pertaining to this thread. This map is
* maintained by the InheritableThreadLocal class.
*/
ThreadLocal.ThreadLocalMap inheritableThreadLocals = null;
1
2
3
if (parent.inheritableThreadLocals != null)
this.inheritableThreadLocals =
ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);

线程池

如果没有线程池,以上就算是解决所有问题了,可实现毕竟是实现

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
/**
* 子线程从父线程中取值
* @throws InterruptedException
*/
private static void testThreadpool() throws InterruptedException {
ExecutorService executorService = Executors.newFixedThreadPool(1);
final ThreadLocal<String> threadLocal = threadLocal();//new InheritableThreadLocal<>()
threadLocal.set("parent");
for(int i=0;i<1;i++) {
Runnable runnable = new Runnable() {
@Override
public void run() {
System.out.println(Thread.currentThread().getName() +" get parent value:" + threadLocal.get());
threadLocal.set("sun");
System.out.println(Thread.currentThread().getId() + "==" + threadLocal.get());
}
};
executorService.execute(runnable);
Thread.sleep(100);
executorService.execute(runnable);
Thread.sleep(100);
System.out.println("main:" + threadLocal.get());
}
executorService.shutdown();
}

为了好重现问题,线程池大小为1,但会连续跑两次任务

1
2
3
4
5
pool-1-thread-1 get parent value:parent
11==sun
pool-1-thread-1 get parent value:sun
11==sun
main:parent

在第二次取父线程值时,却是第一次任务线程中的赋值,在线程池中子线程不能正常获取父线程值

线程池中,线程会复用,线程中的inheritableThreadLocals没有被清空

解决方法一是:池中线程数大于任务线程,让线程没有重用机会

1
ExecutorService executor = Executors.newFixedThreadPool(>=[任务线程数])

但在多线程应用中,明显不能解决问题,任务数肯定远远超过线程数

解决方法二是:自定义实现在使用完线程主动清空inheritableThreadLocals

阿里开源transmittable-thread-local就实现这样的功能

整体思路也是从主线程复制,使用,再清理

TtlRunnable 构造方法中,调用了 TransmittableThreadLocal.Transmitter.capture() 获取当前线程中所有的上下文,并储存在 AtomicReference 中

当线程执行时,调用 TtlRunnable run 方法,TtlRunnable 会从 AtomicReference 中获取出调用线程中所有的上下文,并把上下文给 TransmittableThreadLocal.Transmitter.replay 方法把上下文复制到当前线程。并把上下文备份

当线程执行完,调用 TransmittableThreadLocal.Transmitter.restore 并把备份的上下文传入,恢复备份的上下文,把后面新增的上下文删除,并重新把上下文复制到当前线程

transmittable-thread-local代码不多,但有很多亮点,可以自行膜拜

在此场景,transmittable-thread-local还是太重了,其实可以简单借鉴一下transmittable-thread-local的思路,自定义Runnable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TransRunnable(Runnable runnable){
this.runnable = runnable;
//在创建时,获取父traceId
this.parentId = TranceContext.getParentTrace();
}
@Override
public void run() {
//
String old = TranceContext.getParentTrace();
//设置父traceid
TranceContext.setParentTrace(parentId);
runnable.run();
//还原
TranceContext.setParentTrace(old);
}

在创建子线程时,把父traceId带进去,就能在子线程业务方法中拿到父traceId,这样整个调用链也不会断

schedule

traceid生成,有主动请求时,会生成,但如果是个系统的定时任务呢?

  1. 让taskService调用一下入口,类似模拟用户行为
  2. 主动生成一个parent traceId

总结

到此,对于traceid的知识结构丰满了很多

想写个一份百万QPS系统的JVM参数,感觉太标题党了,虽然这的确是,但还是朴实点;

JVM参数调优是性能重器,安全第一,不可乱用,更不能因为网上推荐文章(此篇)而随便用

之前关于JVM的几篇文章《是否需要主动GC》《JIT优化》《GC及JVM参数》

这些都涉及到JVM参数,然道理懂不少,还是配置不好参数;调优的确是个费劲的事。这儿直接给一份参数,可以直接拿来主义,当然也有些参数需要配合硬件及应用环境,斟酌使用,一切以实战为准

其实有很多现成的,如elasticsearchcassandraVIP

jvm参数总体分两种:标准参数(以-开始)与非标准参数;

非标准参数又分了两种:不太标准(以-X开始)与特别不标准(以-XX开始)

参数列表就标准到非标准一一进行说明

标准参数

顾名思义,标准参数中包括功能和输出的参数都是很稳定的,很可能在将来的JVM版本中不会改变。你可以用java命令(或者是用 java -help)检索出所有标准参数

-server

这个参数涉及分层编译策略,简单讲,就是把更多的代码更早地编译成本地代码

-D

应用附加配置参数,通过System.getProperty读取

-Djava.security.egd=file:/dev/./urandom

-Djava.net.preferIPv4Stack=true

-Djava.awt.headless=true

-Dspring.profiles.active=dev

非标准参数

非标准化的参数在将来的版本中可能会改变

在实际情况中X参数和XX参数并没有什么不同。X参数的功能是十分稳定的,然而很多XX参数仍在实验当中(主要是JVM的开发者用于debugging和调优JVM自身的实现)

X参数

-Xms2048m

-Xmx2048m

-Xmn2048m

-Xss512K

这几个老面孔,设置堆大小

Xms和Xmx设置一样,可以减轻伸缩堆大小带来的压力;Xmn新年代大小

Xss规定了每个线程堆栈的大小。一般情况下256K是足够了; 如果线程数较多,函数的递归较少,线程栈内存可以调小节约内存,默认1M

-Xloggc

-Xloggc:/dev/shm/gc.log

有人担心写GC日志会影响性能,但测试下来实在没什么影响,GC问题是Java里最常见的问题,没日志怎么行。

后来又发现如果遇上高IO的情况,GC时操作系统正在flush pageCache 到磁盘,也可能导致GC log文件被锁住,从而让GC结束不了。所以把它指向了/dev/shm 这种内存中文件系统,避免这种停顿,详见Eliminating Large JVM GC Pauses Caused by Background IO Traffic


XX参数

XX参数 虽然是最不稳定参数,但使用的最多,好神奇,很多特殊的性能调优都需要用到

  • 对于布尔类型的参数,我们有”+”或”-“,然后才设置JVM选项的实际名称。例如,-XX:+用于激活选项,而-XX:-用于注销选项
  • 对于需要非布尔值的参数,如string或者integer,我们先写参数的名称,后面加上”=”,最后赋值。例如, -XX:=给赋值

在使用此类参数时,可以使用两个命令先确认一下JVM默认值,防止JVM变动,最好还是明确设置

1
2
-XX:+PrintFlagsInitial表示打印出所有XX选项的默认值
-XX:+PrintFlagsFinal表示打印出XX选项在运行程序时生效的值

这些参数从功能大体分类一下

  1. 空间大小,类似-X参数,但这些空间各个JVM可能不同实现,如PermSize
  2. 监控类,帮助确定问题Trouble shooting Options
  3. 优化类,调优性能
  4. GC策略类

内存类

-XX:PermSize=512m -XX:MaxPermSize=512m

1
2
Java HotSpot(TM) 64-Bit Server VM warning: ignoring option PermSize=200m; support was removed in 8.0
Java HotSpot(TM) 64-Bit Server VM warning: ignoring option MaxPermSize=256m; support was removed in 8.0

在JDK8之后,永久代向元空间的转换,配置项变成了

-XX:MetaspaceSize=200m -XX:MaxMetaspaceSize=256m

为什么需要这样转换?

1、字符串存在永久代中,容易出现性能问题和内存溢出。
2、类及方法的信息等比较难确定其大小,因此对于永久代的大小指定比较困难,太小容易出现永久代溢出,太大则容易导致老年代溢出。
3、永久代会为 GC 带来不必要的复杂度,并且回收效率偏低。
4、Oracle 可能会将HotSpot 与 JRockit 合二为一。

-XX:MaxDirectMemorySize=2048m

堆外内存的最大值,默认为Heap区总内存减去一个Survivor区的大小;像使用netty之类框架,用得多些。

在DirectByteBuffer中,首先向Bits类申请额度,Bits类有一个全局的 totalCapacity变量,记录着全部DirectByteBuffer的总大小,每次申请,都先看看是否超限 – 堆外内存的限额默认与堆内内存(由-XMX 设定)相仿,可用 -XX:MaxDirectMemorySize 重新设定。

如果已经超限,会主动执行Sytem.gc(),期待能主动回收一点堆外内存。然后休眠一百毫秒,看看totalCapacity降下来没有,如果内存还是不足,就抛出大家最头痛的OOM异常;详细可见《堆外内存》

-XX:ReservedCodeCacheSize=240M

JIT编译后二进制代码的存放区,满了之后就不再编译,对性能影响很大。JDK7默认不开多层编译48M,开了96M,而JDK8默认开多层编译240M。可以在JMX里看看CodeCache的大小,JDK7下的48M一般够了,也可以把它设大点,反正内存多

-XX:NewRatio=1

这个参数,与-Xmn or (-XX:NewSize and -XX:MaxNewSize) or -XX:NewRatio并列,都是设置年轻代大小。默认值为2, 也就是新生代占堆大小的1/3, 个人喜欢把对半分, 增大新生代的大小,能减少GC的频率(但也会加大每次GC的停顿时间),主要是看老生代里没多少长期对象的话,占2/3太多了。可以用-Xmn 直接赋值(等于-XX:NewSize and -XX:MaxNewSize同值的缩写),或把NewRatio设为1来对半分(但如果想设置新生代比老生代大就只能用-Xmn)

参数中带Ratio的还有一个-XX:SurvivorRatio,从字面意思看好像是新年代占比、survivor占比。其实是反的

-XX:NewRatio=4表示年老代与年轻代的比值为4:1

-XX:SurvivorRatio=8表示Eden区与Survivor区的大小比值是8:1:1, 因为Survivor区有两个

监控类

-XX:+PrintCommandLineFlags

让JVM打印出那些已经被用户或者JVM设置过的详细的XX参数的名称和值,还会打印出以及因为这些参数隐式影响的参数

打印出来,需要核实线上运行状态时,有据可查

-XX:-OmitStackTraceInFastThrow

有时查线上问题时,看到有异常信息,但只有

1
2
3
4
5
...
java.lang.NullPointerException
java.lang.NullPointerException
java.lang.NullPointerException
...

具体的异常栈没了,有时异常监控不位,人工发现这些异常时,却看不出哪里的问题,很是恼火

JVM对一些特定的异常类型做了Fast Throw优化,如果检测到在代码里某个位置连续多次抛出同一类型异常的话,C2会决定用Fast Throw方式来抛出异常,而异常Trace即详细的异常栈信息会被清空。这种异常抛出速度非常快,因为不需要在堆里分配内存,也不需要构造完整的异常栈信息

特定异常:

1
2
3
4
5
NullPointerException
ArithmeticException
ArrayIndexOutOfBoundsException
ArrayStoreException
ClassCastException

-XX:+PrintGCCause

打印产生GC的原因,比如AllocationFailure什么的,在JDK8已默认打开,JDK7要显式打开一下

-XX:+PrintGCApplicationStoppedTime

这是个非常非常重要的参数,但它的名字没起好,其实除了打印清晰的完整的GC停顿时间外,还可以打印其他的JVM停顿时间,比如取消偏向锁,class 被agent redefine,code deoptimization等等,有助于发现一些原来没想到的问题

1
2018-10-18T03:27:39.204+0800: 33729.026: Total time for which application threads were stopped: 0.0059280 seconds, Stopping threads took: 0.0001000 seconds

-XX:+PrintGCDateStamps

输出GC的时间戳(以日期的形式,如 2013-05-04T21:53:59.234+0800)

用PrintGCDateStamps而不是PrintGCTimeStamps,打印可读的日期而不是时间戳

-XX:+PrintGCDetails

输出GC的详细日志

-XX:ErrorFile

-XX:ErrorFile=${MYLOGDIR}/jvmerr_%p.log

JVM crash时,hotspot 会生成一个error文件,提供JVM状态信息的细节。如前所述,将其输出到固定目录,避免到时会到处找这文件。文件名中的%p会被自动替换为应用的PID

-XX:+HeapDumpOnOutOfMemoryError

两个配合使用 -XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=${LOGDIR}/

在Out Of Memory,JVM快死掉的时候,输出Heap Dump到指定文件。不然开发很多时候还真不知道怎么重现错误。

路径只指向目录,JVM会保持文件名的唯一性,叫java_pid${pid}.hprof。因为如果指向文件,而文件已存在,反而不能写入。

但在容器环境下,输出4G的HeapDump,在普通硬盘上会造成20秒以上的硬盘IO跑满,也是个十足的恶邻,影响了同一宿主机上所有其他的容器


优化类

-XX:AutoBoxCacheMax

-XX:AutoBoxCacheMax=20000

这个参数的意义是缓存自动装箱最大值

设为20000后,我们应用的QPS有足足4%的影响

看代码

1
2
3
4
Integer i = 129;
Integer j = 129;

i == j //true or false ?

JDK默认只缓存 -128 ~ +127的Integer 和 Long,超出范围的数字就要即时构建新的Integer对象;

如果这儿配置了最大值20000,那就是[-128,20000]都不再创建新对象,但有点奇怪的时,你不能认为AutoBoxCacheMax的默认值是127

为什么配置值是20000呢,就得说到-XX:+AggressiveOpts参数,这是是一些还没默认打开的优化参数集合, -XX:AutoBoxCacheMax是其中的一项。但这个参数在关键系统里不建议打开

There’s a JVM option -XX:+AggressiveOpts that supposedly makes your JVM faster. Lots of people turn this on in Eclipse to try to make it faster. But it makes your JVM less correct. Today I found it to be the cause of a longstanding bug in dx.
http://code.google.com/p/android/issues/detail?id=5817

-XX:+AggressiveOpts was deprecated in JDK 11 and should be removed in JDK 12

1
2
3
4
5
-     bool AggressiveOpts                           := false           {product}
+ bool AggressiveOpts := true {product}

- intx AutoBoxCacheMax = 128 {C2 product}
+ intx AutoBoxCacheMax = 20000 {C2 product}

通过上面的打印设置配置值的参数,可以看出此项默认值是128,在打开AggressiveOpts参数时,是20000

-XX:-UseCounterDecay

禁止JIT调用计数器衰减。默认情况下,每次GC时会对调用计数器进行砍半的操作,导致有些方法一直温热,
永远都达不到触发C2编译的1万次(server默认值)的阀值,详细可参考《JIT优化》

-XX:-UseBiasedLocking

JDK1.6开始默认打开的偏向锁,会尝试把锁赋给第一个访问它的线程,取消同步块上的synchronized原语

如果始终只有一条线程在访问它,就成功略过同步操作以获得性能提升

为什么会有偏向锁出现?因为经验表明,其实大部分情况下,都会是同一个线程进入同一块同步代码块

但线上应用基本都是使用多线程,一旦出现锁竞争,就会锁膨胀,GC日志中有不少RevokeBiasd的纪录,像GC一样Stop The World的干活,虽然只是很短的停顿,但对于多线程并发的应用,取消掉它反而有性能的提升

-XX:+PerfDisableSharedMem

JVM经常会默默的在/tmp/hperf目录写上一点statistics数据,如果刚好遇到PageCache刷盘,把文件阻塞了,就不能结束这个Stop the World的安全点

禁止JVM写statistics数据的代价,是jps和jstat用不了;详细可看jstat的具体实现

-XX:MaxTenuringThreshold=4

这是改动效果最明显的一个参数了。对象在Survivor区最多熬过多少次Young GC后晋升到年老代,JDK8里默认是15

Young GC是最大的应用停顿来源,而新生代里GC后存活对象的多少又直接影响停顿的时间,所以如果清楚Young GC的执行频率和应用里大部分临时对象的最长生命周期,可以把它设的更短一点,让其实不是临时对象的新生代对象赶紧晋升到年老代,别呆着。

用-XX:+PrintTenuringDistribution观察下,如果后面几代的大小总是差不多,证明过了某个年龄后的对象总能晋升到老生代,就可以把晋升阈值设小,比如JMeter里2就足够了

-XX:+UnlockDiagnosticVMOptions -XX: ParGCCardsPerStrideChunk=1024

Linkined的黑科技, 上一个版本的文章不建议打开,后来发现有些场景的确能减少YGC时间,详见《难道这些 Java 大牛说的都是真的?》,简单说就是影响YGC时扫描老生代的时间,默认值256太小了,但32K也未必对,需要自己试验

-XX:+ExplicitGCInvokesConcurrent

full gc时,使用CMS算法,不是全程停顿,必选

-XX:+AlwaysPreTouch

启动时访问并置零内存页面;启动时就把参数里说好了的内存全部舔一遍,可能令得启动时慢上一点,但后面访问时会更流畅,比如页面会连续分配,比如不会在晋升新生代到老生代时才去访问页面使得GC停顿时间加长。ElasticSearch和Cassandra都打开了它


GC策略

配置-server时默认使用ParallelScavenge系的GC,是个吞吐量优先的收集器

虽然现在有了G1 GC,甚至JDK11后的ZGC,但在大型互联网项目上估计CMS还是主流

CMS三个基本配置

-XX:+UseConcMarkSweepGC -XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSInitiatingOccupancyOnly

因为我们的监控系统会通过JMX监控内存达到90%的状况(留点处理的时间),所以设置让它75%就开始跑了,早点开始也能避免Full GC等意外情况(概念重申,这种主动的CMS GC,和JVM的老生代、永久代、堆外内存完全不能分配内存了而强制Full GC是不同的概念)。为了让这个设置生效,还要设置-XX:+UseCMSInitiatingOccupancyOnly,否则75只被用来做开始的参考值,后面还是JVM自己算

-XX:+ParallelRefProcEnabled -XX:+CMSParallelInitialMarkEnabled

并行的处理Reference对象,如WeakReference,默认为false,除非在GC log里出现Reference处理时间较长的日志,否则效果不会很明显,但我们总是要JVM尽量的并行,所以设了也就设了。同理还有-XX:+CMSParallelInitialMarkEnabled,JDK8已默认开启,但小版本比较低的JDK7甚至不支持

建议参数

-XX:ParallelGCThreads=? -XX:ConcGCThreads=?

-XX:ParallelGCThreads=n GC在并行处理阶段多少个线程,默认值和平台有关。(译者注:和程序一起跑的时候,使用多少个线程)

-XX:ConcGCThreads=n 并发收集的时候使用多少个线程,默认值和平台有关。(译者注:stop-the-world的时候,并发处理的时候使用多少个线程)

ParallelGCThreads=Processor < 8 ? 8 : 8 +( Processor - 8 ) ( 5/8 );

ConcGCThreads = (ParallelGCThreads + 3)/4

24个处理器,小于8个处理器时ParallelGCThreads按处理器数量,大于时按上述公式YGC线程数=18, CMS GC线程数=5。

CMS GC线程数的公式太怪,也有人提议简单改为YGC线程数的1/2。

一些不在乎停顿时间的后台辅助程序,比如日志收集的logstash,建议把它减少到2,避免在GC时突然占用太多CPU核,影响主应用。

而另一些并不独占服务器的应用,比如旁边跑着一堆sidecar的,也建议减少YGC线程数。

一个真实的案例,24核的服务器,默认18条YGC线程,但因为旁边有个繁忙的Service Mesh Proxy在跑着,这18条线程并不能100%的抢到CPU,出现了不合理的慢GC。把线程数降低到12条之后,YGC反而快了很多。 所以那些贪心的把YGC线程数=CPU 核数的,通常弄巧成拙。

不要-XX:+DisableExplicitGC

像R大说的,System GC是保护机制(如堆外内存满时清理它的堆内引用对象),禁了system.gc() 未必是好事,只要没用什么特别烂的类库,真有人调了总有调的原因,所以不应该加这个烂大街的参数。

Reference

关键业务系统的JVM参数推荐

JVM源码分析之Jstat工具原理完全解读

《难道这些 Java 大牛说的都是真的?》

SecureRandom的江湖偏方与真实效果

zk相关文章已经有了三篇
《zookeeper-paxos》
《zookeeper知识结构》
《zookeeper知识结构2-zab协议》

但都没有到具体到应用,此篇弥补一下

talk is cheap,show me the code

client

如何使用zk

除了zk提供原生客户端,还有能过编程方式

zkcli

zkcli原生操作指令比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
zkcli    连接默认zookeeper服务器

zkcli -server ip:port 连接指定的zookeeper服务器

create -s -e path data [acl] 创建节点,-s表示顺序,-e表示临时,默认是持久节点,acl缺省表示不做任何权限限制

ls path [watch] 显示path下的节点,不递归显示,watch注册监听,命令行可忽视

ls2 path 显示当前节点下的节点和当前节点的属性信息

get path [watch] 获取path的属性信息和数据内容

set path data [version] 更新path的数据内容,version是做类似cas的功能的对应dataversion,命令行可忽略

delete path [version] 删除节点,不能递归删除,只能删除叶子节点

setacl path acl 设置节点acl,例子(scheme:id:password=:perm)-(digest:example:sha-1(base64(pwd))=:cdrwa) create delete read write admin

getacl path 获取path节点的acl

stat path 查看path的属性信息

quit 退出zkcli

ZkClient VS Curator

这两个常用的开源组件

相对zkclient,Curator已经成为Apache的顶级项目,不仅解决了非常底层的细节开发工作,包括连接重连、反复注册Watcher和NodeExistsException异常等,还提供了Zookeeper各种应用场景(Recipe,如共享锁服务、Master选举机制和分布式计算器等)的抽象封装

所以推荐使用curator

应用

主要介绍两种常见情景,一是分布式锁,二是master选举

分布式锁

为什么zk能实现分布式锁?

像redis原理是通过全局key是否存,而zk则是通过其特定的数据结构来实现:利用节点名称的唯一性

ZooKeeper抽象出来的节点结构是一个和unix文件系统类似的小型的树状的目录结构。ZooKeeper机制规定:同一个目录下只能有一个唯一的文件名。例如:我们在Zookeeper目录/jjk目录下创建,两个客户端创建一个名为Lock节点,只有一个能够成功

思路一:持久节点

利用名称唯一性,加锁操作时,只需要所有客户端一起创建/lock节点,只有一个创建成功,成功者获得锁。解锁时,只需删除/lock节点,其余客户端再次进入竞争创建节点,直到所有客户端都获得锁

代码片段

尝试加锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 尝试加锁,直接创建节点,如果节点创建失败,说明加锁失败
* @param lockName
* @return
*/
public boolean tryLock(String lockName) {
try {
//创建节点
String path = cf.create().creatingParentsIfNeeded().withMode(CreateMode.PERSISTENT).forPath(getLockPath(lockName), lockName.getBytes());
logger.info(Thread.currentThread().getName()+ "try lock success ,path:"+path+" tid:"+Thread.currentThread().getName());
return true;
}catch (KeeperException.NodeExistsException e) {
logger.info("try lock fail,"+" tid:"+Thread.currentThread().getName());
}catch (Exception ex) {
ex.printStackTrace();
}
return false;
}

尝试加锁失败后,阻塞等待

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
/**
* 尝试加锁失败后,阻塞等待
* @param lockName
* @throws Exception
*/
public void waitForLock(String lockName) throws Exception {
//监听子节点
PathChildrenCache pathChildrenCache = new PathChildrenCache(cf, LOCK_PATH, false);
pathChildrenCache.start(PathChildrenCache.StartMode.BUILD_INITIAL_CACHE);
pathChildrenCache.getListenable().addListener(new PathChildrenCacheListener() {
@Override
public void childEvent(CuratorFramework client, PathChildrenCacheEvent event) throws Exception {
switch (event.getType()) {
case CHILD_REMOVED:
logger.info("path:" + event.getData().getPath() + " has removed,start to lock:{}",Thread.currentThread().getName());
countDownLatch.countDown();
break;
default:
//logger.info(" has changeed,{},start to lock:{}",event.getType(),Thread.currentThread().getName());
break;
}
}
});
boolean hasLock = false;
while(!hasLock) {
Stat stat = cf.checkExists().forPath(getLockPath(lockName));
//节点存在,此处与unlock非原子操作,如果在checkExists返回true时刻,成功unlock,那此端无限等待
if (stat == null) {
logger.info("waitForLock not exists:{}", Thread.currentThread().getName());
hasLock = tryLock(lockName);

if(hasLock) {
logger.info("waitForLock get lock :{}", Thread.currentThread().getName());
break;
}
} else {
logger.info("waitForLock exists:{}", Thread.currentThread().getName());
countDownLatch.await();
}
}
}

解锁

1
2
3
4
5
6
public boolean unlock(String lockName) throws Exception {
logger.info("start unlock:" + lockName + " tid:" + Thread.currentThread().getName());
cf.delete().forPath(getLockPath(lockName));
logger.info("end unlock:" + lockName + " tid:" + Thread.currentThread().getName());
return true;
}

这个方案比较简单,但会出现两个问题:

  1. “惊群效应”,所有客户端都是监听这个节点变化,当一端释放锁时,别的端都会抢占
  2. 如果加锁成功的client突然崩溃,那么锁无法正常释放,全局进入死锁状态

思路二:临时有序节点

为了应对上面的问题,可以使用临时有序节点:EPHEMERAL_SEQUENTIAL,之前的篇章中说明了临时节点特点,在client与zk断开连接时,临时节点会自动删除

加锁算法:

  1. 客户端调用create()方法创建名为“/lock”的节点,需要注意的是,这里节点的创建类型需要设置为EPHEMERAL_SEQUENTIAL
  2. 客户端调用getChildren(“lock”)方法来获取所有已经创建的子节点,同时在这个节点上注册上子节点变更通知的Watcher
  3. 客户端获取到所有子节点path之后,如果发现自己在步骤1中创建的节点是所有节点中序号最小的,那么就认为这个客户端获得了锁
  4. 如果在步骤3中发现自己并非是所有子节点中最小的,说明自己还没有获取到锁,就开始等待,直到下次子节点变更通知的时候,再进行子节点的获取,判断是否获取锁

解锁算法:

  • 删除自己创建的那个子节点

代码片段

尝试加锁失败后,阻塞等待

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
public void waitForLock(String lockName) throws Exception {
logger.info("waitForLock {}:{}",beforeNode, Thread.currentThread().getName());
boolean hasLock = false;
while(!hasLock) {
//是不是最小节点
boolean isMin = isMinNode();
if (isMin) {//是 则成功获取锁
logger.info("waitForLock getLock:{}", Thread.currentThread().getName());
break;
} else {
try {
cf.getData().usingWatcher(new Watcher() {
@Override
public void process(WatchedEvent event) {
switch (event.getType()) {
case NodeDeleted:
logger.info("path:" + event.getPath() + " has removed,before:{},start to lock:{}", beforeNode, Thread.currentThread().getName());
countDownLatch.countDown();
break;
}
}
}).forPath(beforeNode);
logger.info("waitForLock waiting:{}", Thread.currentThread().getName());
countDownLatch.await();
logger.info("开始抢占:{},{}", Thread.currentThread().getName(), currentNode);
}catch (KeeperException.NoNodeException e){
logger.info("waitForLock has delete:{},{}",beforeNode, Thread.currentThread().getName());
}
}
}
}

这个方案解决了思路一中的问题

  1. 只监听当前节点的上一个节点,这样就解决了“惊群”现象
  2. 临时节点,当连接断开后,就会自动删除,不会出现过期时间问题

完美了吗?

再回看《剖析分布式锁》。zk实现方式完美了吗?

显然示例中没有达到好锁的标准,更完善的实现可以看看curator中的InterProcessLock

单机

此锁高可用了吗?对比一下Redis,哪种方案更完美?

客户端1发生GC停顿的时候,zookeeper检测不到心跳,也是有可能出现多个客户端同时操作共享资源的情形

redis的最新set指令,zk的临时节点两个性质都是一样的,解决了因过期时间问题引起的死锁

有了“续命丸”方案,在单机情况下,redis更完美些,至少不会出现zk临时节点因session超时提前删除问题

集群

在集群下呢? 线上环境,为了高可用不大会使用单点

如redis的cluster,哨兵模式;但由于Redis的主从复制(replication)是异步的,这可能会出现在数据同步过程中,master宕机,slave来不及同步数据就被选为master,从而数据丢失

  1. 客户端1从Master获取了锁
  2. Master宕机了,存储锁的key还没有来得及同步到Slave上
  3. Slave升级为Master
  4. 客户端2从新的Master获取到了对应同一个资源的锁

RedLock算法

为了应对这个情形, redis的作者antirez提出了RedLock算法,步骤如下(该流程出自官方文档),假设我们有N个master节点(官方文档里将N设置成5,其实大等于3就行)

  1. 获取当前时间(单位是毫秒)
  2. 轮流用相同的key和随机值在N个节点上请求锁,在这一步里,客户端在每个master上请求锁时,会有一个和总的锁释放时间相比小的多的超时时间。比如如果锁自动释放时间是10秒钟,那每个节点锁请求的超时时间可能是5-50毫秒的范围,这个可以防止一个客户端在某个宕掉的master节点上阻塞过长时间,如果一个master节点不可用了,我们应该尽快尝试下一个master节点
  3. 客户端计算第二步中获取锁所花的时间,只有当客户端在大多数master节点上成功获取了锁(在这里是3个),而且总共消耗的时间不超过锁释放时间,这个锁就认为是获取成功了
  4. 如果锁获取成功了,那现在锁自动释放时间就是最初的锁释放时间减去之前获取锁所消耗的时间
  5. 如果锁获取失败了,不管是因为获取成功的锁不超过一半(N/2+1)还是因为总消耗时间超过了锁释放时间,客户端都会到每个master节点上释放锁,即便是那些他认为没有获取成功的锁

缺陷

比如一下场景,两个客户端client 1和client 2,5个redis节点nodes (A, B, C, D and E)。

  1. client 1从A、B、C成功获取锁,从D、E获取锁网络超时
  2. 节点C的时钟不准确(如时钟跳跃),导致锁快速超时(算法第4点)
  3. client 2从C、D、E成功获取锁,从A、B获取锁网络超时
  4. 这样client 1和client 2都获得了锁

对于步骤2,还有一种情况,比如节点C崩溃重启了,但客户端1在C上加的锁没有持久化下来,丢失了;节点C重启后,client2从C、D、E成功获取锁

对于这两种情况,redis作者antirez给出了两种人为补偿措施

  • 一时钟问题,不允许人员修改时间
  • 二节点重启,提出延迟重启的概念,即一个节点崩溃后,先不立即重启它,而是等待一段时间再重启,等待的时间大于锁的有效时间。采用这种方式,这个节点在重启前所参与的锁都会过期,它在重启后就不会对现有的锁造成影响

Redlock的问题,最关键的一点在于Redlock需要客户端去保证写入的一致性,后端5个节点完全独立,所有的客户端都得操作这5个节点。如果5个节点有一个leader,客户端只要从leader获取锁,其他节点能同步leader的数据,这样,分区、超时、冲突等问题都不会存在。所以为了保证分布式锁的正确性,我觉得使用强一致性的分布式协调服务能更好的解决问题

而强一致问题,zk可以完成,zk是个CP系统,zk内部机制就保证了各数据的一致性

分布式锁

到此,对分布式锁的实现可以总结一下

zookeeper可靠性比redis强太多,只是效率低了点,如果并发量不是特别大,追求可靠性,首选zookeeper

为了效率,则首选redis实现

总结

除了分布式锁,还有一个常用场景:master选举。在curator中也有相应封装:LeaderSelector;具体实现可以自行阅读源码

参考资料

基于zookeeper的分布式锁

《Is Redlock safe?》

《How to do distributed locking》

curator使用说明

分布式锁实现抉择

聊一聊分布式锁的设计

一本正经的胡说八道

对错自在你心,可能就是个饭后闲扯

所得

以前同事问,什么时候跳槽?或者什么时候会出去看看机会呢?我都会回答做到有所得的时候。有所得,当然不是说拷贝公司几份源码,那可是公司资产,不可误入歧途。但知识是自己的,成长是自己的

一直也是这么践行的,从出校门不懂的书生到能把书本知识灵活运用到一线工作,从毫无经验到开发工业级产品,从职场小白到带队主导开发流程,虽然经历的大多数公司已经倒闭了,但自己是实实在在的成长了。

是的,是所有得再考虑外面机会的,小池塘不能满足成长时,就要去大池塘

前些天跟老同事见面聊游戏开发周期,我问现在立项时还是提议半年开发一款产品吗?同事呵呵两声回答,半年开发一款早就得卷地铺走人了,现在两周就得上线。着实吓了我一跳,原来他们现在是主攻小游戏,依赖完备的微信生态,快速产品,快速变现

去年同事项目出了个爆款,公司整年有近3亿纯利,开发自然奖金不菲,当然也没有想像中那么多

我思考他们的开发模式,直接模仿国外游戏,改头换皮,再稍加修改,上线。大多数产品肯定是上得快,死得也快。如此环境,对技术人员的成长有多少帮助

绝大多数收益进入老板口袋,开发人员一直重复再重复,甚至有些游戏只是改了个名字,最后他们能得到什么?

此类游戏业务简单,公司组织也扁平,尤其服务端,平台提供了各种服务,小游戏前端已经在喊着要干掉服务端的口号,不 管哪个开发岗位,在几年后,当面对新机会时,怎么阐述自己的价值,是抄得更快速?还是因为运气,出了多少爆款?

由他而又思考到自己所谓的大公司,有人评价阿里工程师,说普遍被中间件惯坏了

不是背后说人坏话,只是一种现象,可能是大公司人的普遍问题
,进阿里是大多数技术人的梦想,包括我,但估计此生无缘,能力实在达不到阿里要求

面试造火箭,入职拧螺丝;公司越成熟,基础建设就越完备、基建设施模块化程度越高,工具体验做得越好,平台做得越完善,那么对上层做业务来讲,底层细节也就屏蔽越多

对业务来说本身是件好事,但对业务开发技术人员呢?有些领域技术变化很快,两三年可能迭代了好几轮,在深度、广度上有了质的飞跃,而你该怎么办,削足适履追求新技术吗?

回顾自己技术实力时,脱离了这些基础设施,还有多少生产力?尤其微服务会打散各个业务线,可能一条完整的业务链路都理不清

此时,还能有所得吗?得多少?褪去头顶公司光环,酒桌上的牛还能吹多大?

所思

有人说技术人就像丢在大海里的漂流瓶,努力漂泊,孤傲不羁,却怎么也不能融入大海,装不满自己空空如也的肚腩,因为他们不知道身体倾斜一点,才是最佳姿势,才有最快的装水速度

也许真是远离技术看技术,才有更大的格局

从事游戏开发很多年,一直觉得自己对游戏开发还是有见解的,但好像只是开发阶段的把握,而不是游戏本身的整体把握。

早些年总是抱怨,为什么我们技术这么好,为什么游戏总是死呢?其实考虑面太窄,没想过运营,商务,维护,推广等等事项,手上有把锤子,到处只看到钉子了

对于游戏类型,也很局限,最近看到一个外行人总结游戏类型,特别的汗颜

依据不同的投入类型,我们可以把游戏分成三大类:

1)反应。这类游戏,需要实时观察周围环境,并快速作出操作和应对。最典型的就是各种射击、动作、即时战略类游戏。

2)策略。这类游戏,需要综合考虑各种可能性,对未来作出规划,并安排好下一步行动。典型如各种策略模拟游戏。

3)沉浸。这类游戏,需要代入角色,理解和接受其世界观,阅读、记忆大量剧情,探索故事线。典型就是各种角色扮演游戏。

游戏的玩法可以千奇百怪,类型可以随意组合,但好的游戏,对玩家的要求,基本都不出这三类

这些只是单机玩法,大型网络游戏,还涉及到群体心理等等

在游戏行业打拼多年,尽然没有一个外行总结到位,抽象高度太低太低

技术里的世界不小,但技术外的世界更大

是该放下手中的技术,抬头看看外面的世界

功夫在诗外,也许再回头看技术时,别有一番天

当然千万别一时亢奋放弃技术,远离技术是在追求技术无法再提升格局的时候,跳出来,回头看

是从简入繁完成后,由繁化简的过程中的技法;无法打开一把锁时,不能只盯着锁看,因为钥匙可能在远离锁的地方

那么如何远离技术呢?远离程度呢?也许多读书是个切入口,《关于读书》这篇文章也许对你有所帮助,如果能找到牛人指点更好。

通过《zookeeper知识结构1》了解了zookeeper是什么?为什么使用zookeeper? 以及zookeeper内部数据结构,选举机制

zab定义

ZAB全称ZooKeeper Atomic Broadcast protocol

ZooKeeper原子广播协议,实现了主备模式下的系统架构,保持集群中各个副本之间的数据同步(数据最新,一致性)


原子广播

在具体深入zab之前,先搞明白原子广播

原子性好理解,不管是事务的ACID,还是多线程中,都有这个概念;广播也好理解,像系统中常引入消息队列进行消息广播

但两者合在一起,有点犯晕了,广播怎么需要原子性?哪部分操作不可分割呢?

所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的,也就是说,要么整个集群所有机器都成功应用了某一个事务, 要么就都没应用.

按照上面的解释,原子性体现在所有机器事务一致性,要么都接受广播,要么都不接受;为了更深入理解,从头开始深入一下这个机制的大致流程

在分布式中,这个机制有很多具体实现,比如2PC,3PC,paxos等等

副本

在这个机制介绍前,需要先介绍下分布式中的副本(Replication)

副本简直是处理故障恢复的的万能钥匙

数据副本的收益:

  1. 提升系统可用性,需要挂更多的节点才会导致数据丢失
  2. 提升系统性能,多个副本可以同时处理或者交给更快的机器处理

分布式系统采用副本可以获得可扩展性,高性能,可用性,容错性

  1. 害怕数据不可用,采用副本吧,多副本能确保数据由于故障丢失的概率大大降低;
  2. 计算太慢,采用副本吧,将计算散布到多台机器上;
  3. I/O太慢,采用副本吧,将数据cache到local机器上,可以极大的提升吞吐

正常多副本,可以从任何副本请求数据

数据同步

为了多个副本上的数据同步,一般会加一个dispatche,client请求到dispatche上,dispatche会对请求进行排序,并按同样的顺序分发到各个副本,保持各副本数据一致

此时,dispatche成了系统中的单点,不具备高可用,所以会部署多个dispatch

每个dispatche相互通信,并且每个dispatche都可以分发到各个副本;此时就会出现上图中的并发更新一致性问题,类似于《深入浅出事务》中的第二类更新丢失

在并发操作时,应用本身对于数据的先后都是可以接受的,但在各个副本中的数据必须保持一致,也就是下图中的结果都是可以的

也就是讲,各个dispatche得以相同的顺序进行更新副本

顺序同步

解决并发更新不一致问题,思路就是对请求操作进行排序,按顺序执行

数据更新的过程如下:

  1. 客户发送操作请求到任意一个节点的分发器上
  2. 分发器接收到请求后,将请求广播到其他节点上的分发器,并且这些分发器之间会对所有的并发请求进行排序。最终每个节点的分发器上都会有一份完全一样的请求列表。这个功能通常称作原子广播(Atomic Broadcast) 或者 全局排序广播(Total Order Broadcast)
  3. 分发器将列表中的操作请求按照顺序送给本节点的数据副本

在这个模型中,原子广播的逻辑和业务逻辑是分开的。这么做的好处是非常明显的,业务逻辑的实现不再受分布式需求的限制,原子广播的逻辑则不需要考虑业务逻辑的具体需求。独立的原子广播的逻辑可以被重用到很多的分布式的应用上

原型

根据上面的推导,得出一个最简单的原型

dispatche增加一个队列,也可以把它设计成日志文件(顺序追加的文件)或者管道等等,当有请求时,会按顺序存储到队列,但这个队列中的每个位置只能存储一次数据,存储后不能进行更改

请求操作

  1. 收到客户端的数据存储请求后,选择一个存储位置。发送数据储存指令给其他的分发器,同时将数据存储到自己的存储队列中
  2. 当收到其他分发器发送的存储指令后,将数据存储到自己的存储队列。如果该位置已经存储了数据,则返回失败
  • 数据存储指令的内容:[存储位置,数据]
  • 存储位置的选择:选择最小的空存储位

并发更新

当两个client分别发到不同到dispatche上请求,两个dispatche相互同步时,出现了不一致,违背了各个队列的每个位置只能存储一次元素,不能更改的原则

对于并发问题,首先想到就是加锁,对于分布式系统怎么加锁呢?

2PC提供了好的思路

借鉴一下2pc,加锁过程如下:

第一步:加锁

  1. 接受到请求,选择本地队列位置,并加锁
  2. 发送加锁指令到别的dispatche2,dipatche2进行相同位置加锁,并回返lock ack
  • 加锁指令:[位置]

第二步:更新

  1. 收到所有dispatche都返回lock ack
  2. 数据写入队列位置上,并发送存储指令给所有disptache
  3. dispatche收到存储指令,把数据写入队列相应位置

死锁

并发考虑的两个问题:安全性与活跃性

dispatche1与dispatche2分别接收到请求,在第一步加锁时,先给自己队列加锁,再发送加锁指令给其它dispatche

此时,就出现死锁:如dispathe1对自身队列位置1加锁,再发送指令给disptache2的队列位置1加锁,但disptache2的队列位置1被自己锁住了,反之disptache1队列位置1也一样,此时双方进入死锁,永远阻塞

优先级锁

有一种策略,就是给锁增加一个优化级

  • 每个锁请求都有一个优先级,优先级高的锁请求可以撤销优先级低的锁。
  • 如果一个存储指令的锁被撤销了,就不能被执行

如图所示,两个dispatche分别接收到请求,p1 p2是各自锁的优先级,p1高于p2

  1. dispatch1接收请求后,自己队列加锁;收到dispatch2的加锁请求,但p2优先级低于p1,所以被阻塞
  2. dispatche2自身加锁后,收到dispatche1的加锁请求,由于p1高于p2,dispatche2撤销p2操作,p1成功加锁
  3. dispatche1成功在所有dispatche上加锁

优先级:

  1. 有先后次序,优先级不能相等
  2. 不可重复

比如以dispatche的id作为优先级值,dispatcheId是不同的,也能区分优先级,但这样会出现不平衡,以id大的优先级高,那永远id为大的优先获取锁,加锁成功处理请求

为了更好的均衡各个客户的请求处理,可以采用下面的优先级定义:[数值,dispatcheID]

数值可以由各个dispatche指定,比如所有disptache都原子累加,这样可以保证每个dispathe的均衡,当数值相等时,再比较dispatcheId

节点故障

故障可能发生在每个阶段,一是加锁阶段,二是数据更新阶段;再细节大概有三种情况:

  1. 加锁成功,但没有写入数据
  2. 部分节点写入了数据
  3. 故障dispatche已经写入数据,但没有同步到别的dispatche

加锁成功,没有写入数据

这个很好解决,通过优先级锁,另的节点发起一个更高优先级操作就可以覆盖先前的记录

部分节点写入数据

解决这个问题,需要加强一下更新操作,之前的更新操作,发送存储指令给各个节点,就结束了

现在不单单发送指令,还需要再广播

也就是节点接受到存储指令,如果节点已经有数据写入,则与数据一起返回;这样当所有节点返回加锁成功后,检查是否有数据返回,如果有数据返回,则将数据放入存储指令,发送给所有节点

没有同步别的dispatche

需要增加一个“预存储队列”,预写入机制

当dispatche1发生故障时,其它的dispatche的预存储队列中已经存入了数据。其它节点接管dispatche1时,会先重发预存储队列中的数据到所有dispatche

预写入过程可以保证:如果数据被写入了任意的存储队列,那么所有节点的预存储队列都有这个数据

多数派

上面的广播机制中,加锁以及预写入都需要所有节点返回成功。如果任意一个节点有故障都会失败。在复杂网络环境下,整个系统很脆弱,不能高可用

因此可以改进为半数以上节点成功回复就可以

大多数派机制下,会带来一些更复杂的中间状态,整个过程:

  1. 发送加锁指令
  2. 收到加锁指令后,检查指定存储位置是否已经加锁,如没有,则返回加锁成功;如被加锁,则比较锁优先级,如果优先级更高,就撤销原有锁,重新加锁返回成功;如果已经预写入数据,则将数据一并返回
  3. 当超过半数节点返回加锁成功后,检查是否有数据返回。如果有数据返回,则将优先级最高的数据存入预存储指令。如果没有数据返回,则将自己的数据写入预存储指令。发送预存储指令给所有dispatche,并写入自己的预存储队列
  4. 收到预存储指令,将数据写入预存储队列。如果预存储锁被撤销,则返回失败
  5. 当超过半数返回预存储成功,刚发送存储指令给所有dispatche,并写入自己的存储队列
  6. 当收到存储队列,将数据写入自己存储队列中

ZAB详细

有了上面的原型,理解其它的具体协议就会轻松很多,在具体实现时,都会看到原型中的概念

ZAB协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复原子广播 协议

ZAB协议定义了选举(election)、发现(discovery)、同步(sync)、广播(Broadcast)四个阶段

原型抽象

根据上面的原型,结合zk的源码,梳理一下源码中对应原型的抽象

投票对象

这个对象对应着原型中的存储指令,优先级加锁指令

1
2
3
4
5
6
7
public Vote(long id, long zxid) {
this.id = id;
this.zxid = zxid;
this.electionEpoch = -1;
this.peerEpoch = -1;
this.state = ServerState.LOOKING;
}

id:被推举的Leader的SID

zxid:被推举的Leader事务ID

为了保证事务的顺序一致性,zookeeper 采用了递增的事 务 id 号(zxid)来标识事务。

所有的提议(proposal)都在被提出的时候加上了 zxid。

实现中 zxid 是一个 64 位的数字

它高32 位是 epoch(ZAB 协议通过 epoch 编号来区分 Leader 周期变化的策略)用来标识 leader关系是否改变,每次一个 leader 被选出来,它都会有一个新的epoch=(原来的 epoch+1),标识当前属于那个 leader 的统治时期。

低 32 位用于递增计数

可以想象为中国古代的年号,例如万历十五年,万历是epoch,十五年是id

electionEpoch:逻辑时钟,用来判断多个投票是否在同一轮选举周期中,该值在服务端是一个自增序列,每次进入新一轮的投票后,都会对该值进行加1操作

peerEpoch:被推举的Leader的epoch

electionEpoch和peerEpoch的区别在于,electionEpoch记录的选举的轮次,而peerEpoch则指的是当前leader的任期

state:当前服务器的状态

FastLeaderElection

zk默认的选举算法,为什么需要选举可以参照《zookeeper知识结构1》

术语

  • 外部投票:特指其他服务器发来的投票。
  • 内部投票:服务器自身当前的投票。
  • 选举轮次:Zookeeper服务器Leader选举的轮次,即logicalclock
  • PK:对内部投票和外部投票进行对比来确定是否需要变更内部投票

electionEpoch和logicalclock的区别在于,electionEpoch指的是发出server的logicalclock,而logicalclock则指的是当前Server所处的选举的轮次

队列

  • sendqueue:选票发送队列,用于保存待发送的选票。
  • recvqueue:选票接收队列,用于保存接收到的外部投票。
  • WorkerReceiver:选票接收器。其会不断地从QuorumCnxManager中获取其他服务器发来的选举消息,并将其转换成一个选票,然后保存到recvqueue中,在选票接收过程中,如果发现该外部选票的选举轮次小于当前服务器的,那么忽略该外部投票,同时立即发送自己的内部投票。
  • WorkerSender:选票发送器,不断地从sendqueue中获取待发送的选票,并将其传递到底层QuorumCnxManager中

QuorumCnxManager

ClientCnxn是ZooKeeper客户端中用于处理网络I/O的一个管理器

在Leader选举的过程中也有类似的角色,那就是QuorumCnxManager——每台服务器启动的时候都会启动一个QuorumCnxManager,负责各台服务器之间的底层Leader选举过程中的网络通信

QuorumCnxManager这个类内部维护了一系列的队列,用于保存接收到的、待发送的消息,以及消息的发送器。

除接收队列以外,这里提到的所有队列都有一个共同点——按SID分组形成队列集合,我们以发送队列为例来说明这个分组的概念。

假设集群中除自身外还有4台机器,那么当前服务器就会为这4台服务器分别创建一个发送队列,互不干扰。

  • queueSendMap:消息发送队列,用于保存那些待发送的消息。queueSendMap是一个Map,按照SID进行分组,分别为集群中的每台机器分配了一个单独队列,从而保证各台机器之间的消息发送互不影响。
  • senderWorkerMap:发送器集合。每个SendWorker消息发送器,都对应一台远程ZooKeeper服务器,负责消息的发送。同样,在sendWorkerMap中,也按照SID进行了分组。
  • lastMessageSent:最近发送过的消息。在这个集合中,为每个SID保留最近发送过的一个消息

在SendWorker的具体实现中,有一个细节需要我们注意一下:一旦ZooKeeper发现针对当前远程服务器的消息发送队列为空,那么这个时候就需要从lastMessageSent中取出一个最近发送过的消息来进行再次发送。这个细节的处理主要为了解决这样一类分布式问题:接收方在消息接收前,或者是在接收到消息后服务器挂掉了,导致消息尚未被正确处理。那么如此重复发送是否会导致其他问题呢?当然,这里可以放心的一点是,ZooKeeper能够保证接收方在处理消息的时候,会对重复消息进行正确的处理

lastMessageSent接近原型中的预存储队列

选票过程

  • 1.自增选举轮次。Zookeeper规定所有有效的投票都必须在同一轮次中,在开始新一轮投票时,会首先对logicalclock进行自增操作。
  • 2.初始化选票。在开始进行新一轮投票之前,每个服务器都会初始化自身的选票,并且在初始化阶段,每台服务器都会将自己推举为Leader
  • 3.发送初始化选票。完成选票的初始化后,服务器就会发起第一次投票。Zookeeper会将刚刚初始化好的选票放入sendqueue中,由发送器WorkerSender负责发送出去。
  • 4.接收外部投票。每台服务器会不断地从recvqueue队列中获取外部选票。如果服务器发现无法获取到任何外部投票,那么就会立即确认自己是否和集群中其他服务器保持着有效的连接,如果没有连接,则马上建立连接,如果已经建立了连接,则再次发送自己当前的内部投票
  • 5.判断选举轮次。在发送完初始化选票之后,接着开始处理外部投票。在处理外部投票时,会根据选举轮次来进行不同的处理。
    • 5.1.外部投票的选举轮次大于内部投票。若服务器自身的选举轮次落后于该外部投票对应服务器的选举轮次,那么就会立即更新自己的选举轮次(logicalclock),并且清空所有已经收到的投票,然后使用初始化的投票来进行PK以确定是否变更内部投票。最终再将内部投票发送出去。
    • 5.2.外部投票的选举轮次小于内部投票。若服务器接收的外选票的选举轮次落后于自身的选举轮次,那么Zookeeper就会直接忽略该外部投票,不做任何处理,并返回步骤4。
    • 5.3.外部投票的选举轮次等于内部投票。此时可以开始进行选票PK
  • 6.选票PK。在进行选票PK时,符合任意一个条件就需要变更投票
    • 6.1.若外部投票中推举的Leader服务器的选举轮次大于内部投票,那么需要变更投票。
    • 6.2.若选举轮次一致,那么就对比两者的ZXID,若外部投票的ZXID大,那么需要变更投票。
    • 6.3.若两者的ZXID一致,那么就对比两者的SID,若外部投票的SID大,那么就需要变更投票。
  • 7.变更投票。经过PK后,若确定了外部投票优于内部投票,那么就变更投票,即使用外部投票的选票信息来覆盖内部投票,变更完成后,再次将这个变更后的内部投票发送出去。
  • 8.选票归档。无论是否变更了投票,都会将刚刚收到的那份外部投票放入选票集合recvset中进行归档。recvset用于记录当前服务器在本轮次的Leader选举中收到的所有外部投票(按照服务队的SID区别,如{(1, vote1), (2, vote2)…})。
  • 9.统计投票。完成选票归档后,就可以开始统计投票,统计投票是为了统计集群中是否已经有过半的服务器认可了当前的内部投票,如果确定已经有过半服务器认可了该投票,则终止投票。否则返回步骤4
  • 10.更新服务器状态。若已经确定可以终止投票,那么就开始更新服务器状态,服务器首选判断当前被过半服务器认可的投票所对应的Leader服务器是否是自己,若是自己,则将自己的服务器状态更新为LEADING,若不是,则根据具体情况来确定自己是FOLLOWING或是OBSERVING。

以上10个步骤就是FastLeaderElection的核心,其中步骤4-9会经过几轮循环,直到有Leader选举产生。

总结

通过对原子广播原型的理解,更容易理解zab,对于paxos也一样

当然zab还有很多的细节,还能再深入,挖出很多知识点。但只看理论终归有些空洞,下一篇实践一下,详述zk版本分布式锁

参考资料

Leader选举

分布式系统

由浅入深理解Paxos协议

之前写过关于zookeeper的一篇文章《zookeeper-paxos》,paxos太难理解了,当时理解了,但现在又忘记了,机械学习果然是不行的

虽然曾经有一篇文章讲阿里不使用zk做服务发现,但大多数公司的分布式架构中基本都能看到zk的身影,而且他躲在里面,你可能看不到他,感受不到他的存在

对于架构体系中的这样一位选手,了解,学习,研究是相当有必要的

ZK是什么

ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是Google的Chubby 一个开源的实现

ZooKeeper 是集群的管理者,监视着集群中各节点的状态,根据节点提交的反馈进行下 一步合理的操作。最终,将简单易用的接口和功能稳定,性能高效的系统提供给用户

zooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services

这大概描述了Zookeeper的作用,配置管理,名字服务,提供分布式同步以及集群管理

为什么需要ZK

知道了zk的定义,其实跟不知道差不多,还是要追根溯源,看看zk今世因缘,存在的意义

zk的历史很多地方都有介绍,这儿就不赘述了

相对历史,更想知道为什么需要zk?

以前经历的系统,都是使用redis做为服务中心了,不管使用single redis,还是redis cluster,能胜任架构需求,全局命名服务、订阅发布监听服务列表、分布式锁足矣

一度怀疑zk的价值,也阻碍了进一步学习的热情,但存在即合理

设计 ZooKeeper 的目的是为了减轻分布式应用程序所承担的协调任务

还是从ZK的定义追溯它的作用

配置管理

在我们的应用中除了代码外,还有一些就是各种配置。比如数据库连接等

一般我们都是使用配置文件的方式,在代码中引入这些配置文件。但是当我们只有一种配置,只有一台服务器,并且不经常修改的时候,使用配置文件是一个很好的做法,但是如果我们配置非常多,有很多服务器都需要这个配置,而且还可能是动态的话使用配置文件就不是个好主意了。

这个时候往往需要寻找一种集中管理配置的方法,我们在这个集中的地方修改了配置,所有对这个配置感兴趣的都可以获得变更。比如我们可以把配置放在数据库里,然后所有需要配置的服务都去这个数据库读取配置

但是,因为很多服务的正常运行都非常依赖这个配置,所以需要这个集中提供配置服务的服务具备很高的可靠性。

一般我们可以用一个集群来提供这个配置服务,但是用集群提升可靠性,那如何保证配置在集群中的一致性呢? 这个时候就需要使用一种实现了一致性协议的服务了。Zookeeper就是这种服务,它使用Zab这种一致性协议来提供一致性

名字服务

比如为了通过网络访问一个系统,我们得知道对方的IP地址,但是IP地址对人非常不友好,这个时候我们就需要使用域名来访问。

但是计算机是不能是别域名的。

怎么办呢?

如果我们每台机器里都备有一份域名到IP地址的映射,这个倒是能解决一部分问题,但是如果域名对应的IP发生变化了又该怎么办呢?于是我们有了DNS这个东西。

我们只需要访问一个大家熟知的(known)的点,它就会告诉你这个域名对应的IP是什么。

在我们的应用中也会存在很多这类问题,特别是在我们的服务特别多的时候,如果我们在本地保存服务的地址的时候将非常不方便,但是如果我们只需要访问一个大家都熟知的访问点,这里提供统一的入口,那么维护起来将方便得多了

分布式锁

比如在一个分布式环境中,为了提高可靠性,我们的集群的每台服务器上都部署着同样的服务

但是,一件事情如果集群中的每个服务器都进行的话,那相互之间就要协调,编程起来将非常复杂。而如果我们只让一个服务进行操作,那又存在单点。通常还有一种做法就是使用分布式锁,在某个时刻只让一个服务去干活,当这台服务出问题的时候锁释放,立即fail over到另外的服务

这在很多分布式系统中都是这么做,这种设计有一个更好听的名字叫Leader Election(leader选举)。比如HBase的Master就是采用这种机制。但要注意的是分布式锁跟同一个进程的锁还是有区别的,所以使用的时候要比同一个进程里的锁更谨慎的使用

这儿其实说了两个作用

  1. 传统意义的锁,如《剖析分布式锁》,保护对共享资料操作
  2. master选举,像JOB,为了高可用,会有多台服务器部署同一套JOB程序,但在运行时,只有一台服务器真正执行业务,此时,需要选择一台服务器,如果这台机器挂了,别的机器需要顶替上来

集群管理

在分布式的集群中,经常会由于各种原因,比如硬件故障,软件故障,网络问题,有些节点会进进出出。有新的节点加入进来,也有老的节点退出集群。这个时候,集群中其他机器需要感知到这种变化,然后根据这种变化做出对应的决策

比如我们是一个分布式存储系统,有一个中央控制节点负责存储的分配,当有新的存储进来的时候我们要根据现在集群目前的状态来分配存储节点

这个时候我们就需要动态感知到集群目前的状态,这也就是注册中心

CAP

分布式系统在设计时,都会考虑一下CAP,在现有理论下,CAP是不能同时满足的,所以需要根据业务场景选择合适的设计要求

CAP定义在《zookeeper-paxos》中有详细说明

ZooKeeper是个CP(一致性+分区容错性)的,即任何时刻对ZooKeeper的访问请求能得到一致的数据结果,同时系统对网络分割具备容错性;但是它不能保证每次服务请求的可用性。也就是在极端环境下,ZooKeeper可能会丢弃一些请求,消费者程序需要重新请求才能获得结果。

ZooKeeper是分布式协调服务,它的职责是保证数据在其管辖下的所有服务之间保持同步、一致;所以就不难理解为什么ZooKeeper被设计成CP而不是AP特性的了

而且, 作为ZooKeeper的核心实现算法Zab,就是解决了分布式系统下数据如何在多个服务之间保持同步问题的

特点

  • 顺序一致性:从同一客户端发起的事务请求,最终将会严格地按照顺序被应用到 ZooKeeper 中去。
  • 原子性:所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的,也就是说,要么整个集群中所有的机器都成功应用了某一个事务,要么都没有应用。
  • 单一系统映像:无论客户端连到哪一个 ZooKeeper 服务器上,其看到的服务端数据模型都是一致的。
  • 可靠性:一旦一次更改请求被应用,更改的结果就会被持久化,直到被下一次更改覆盖。

znode

在谈到分布式的时候,我们通常说的“节点”是指组成集群的每一台机器
然而,在 ZooKeeper 中,“节点”分为两类:

  1. 第一类同样是指构成集群的机器,我们称之为机器节点。
  2. 第二类则是指数据模型中的数据单元,我们称之为数据节点一ZNode

与Linux文件系统不同的是,Linux文件系统有目录和文件的区别,而Zookeeper的数据节点称为ZNode,ZNode是Zookeeper中数据的最小单元,每个ZNode都可以保存数据,同时还可以挂载子节点,因此构成了一个层次化的命名空间,称为树

  • 每一个znode默认能够存储1MB的数据(对于记录状态性质的数据来说,够了)

  • 可以使用zkCli命令,登录到zookeeper上,并通过ls、create、delete、sync等命令操作这些znode节点

znode除了名称、数据以外,还有一套属性:zxid

ZooKeeper状态的每一次改变, 都对应着一个递增的Transaction id, 该id称为zxid. 由于zxid的递增性质, 如果zxid1小于zxid2, 那么zxid1肯定先于zxid2发生

创建任意节点, 或者更新任意节点的数据, 或者删除任意节点, 都会导致Zookeeper状态发生改变, 从而导致zxid的值增加

此外,znode还有操作权限。如果我们把以上几类属性细化,又可以得到以下属性的细节:

  • czxid:创建节点的事务的zxid
  • mzxid:对znode最近修改的zxid
  • ctime:以距离时间原点(epoch)的毫秒数表示的znode创建时间
  • mtime:以距离时间原点(epoch)的毫秒数表示的znode最近修改时间
  • version:znode数据的修改次数
  • cversion:znode子节点修改次数
  • aversion:znode的ACL修改次数
  • ephemeralOwner:如果znode是临时节点,则指示节点所有者的会话ID;如果不是临时节点,则为零。
  • dataLength:znode数据长度。
  • numChildren:znode子节点个数。

znode是由客户端创建的,它和创建它的客户端的内在联系,决定了它的存在性:

  1. PERSISTENT-持久化节点:创建这个节点的客户端在与zookeeper服务的连接断开后,这个节点也不会被删除(除非您使用API强制删除)。
  2. PERSISTENT_SEQUENTIAL-持久化顺序编号节点:当客户端请求创建这个节点A后,zookeeper会根据parent-znode的zxid状态,为这个A节点编写一个全目录唯一的编号(这个编号只会一直增长)。当客户端与zookeeper服务的连接断开后,这个节点也不会被删除。
  3. EPHEMERAL-临时目录节点:创建这个节点的客户端在与zookeeper服务的连接断开后,这个节点(还有涉及到的子节点)就会被删除。
  4. EPHEMERAL_SEQUENTIAL-临时顺序编号目录节点:当客户端请求创建这个节点A后,zookeeper会根据parent-znode的zxid状态,为这个A节点编写一个全目录唯一的编号(这个编号只会一直增长)。当创建这个节点的客户端与zookeeper服务的连接断开后,这个节点被删除。

另外,无论是EPHEMERAL还是EPHEMERAL_SEQUENTIAL节点类型,在zookeeper的client异常终止后,节点也会被删除。

服务的四种状态

服务器具有四种状态,分别是LOOKING,FOLLOWING,LEADING,OBSERVING

  • LOOKING
    寻找leader状态
    当前服务器处于该状态时,它会认为当前集群中没有leader,因此需要进入leader选举状态
  • FOLLOWING
    跟随者状态
    表示当前服务器的角色是Follower角色
  • LEADING
    领导者状态
    表示当前服务器是Leader
  • OBSERVING
    观察者状态
    表示当前服务器角色是Observer


角色

最典型集群模式:Master/Slave 模式(主备模式)

在这种模式中,通常 Master 服务器作为主服务器提供写服务,其他的 Slave 服务器从服务器通过异步复制的方式获取 Master 服务器最新的数据提供读服务

zookeeper都是集群形式部署的,而zk服务又分为不同角色来执行不同的任务,ZooKeeper中没有选择传统的 Master/Slave 概念

而是引入了Leader、Follower 和 Observer 三种角色

在区分zk服务器角色之前,需要解释几个概念:

  • 事务请求
    在zk中,那些会改变服务器状态的请求称为事务请求(创建节点、更新数据、删除节点、创建会话等等)
  • 非事务请求
    从zk读取数据但是不对状态进行任何修改的请求称为非事务请求

领导者Leader

  1. 事务请求的唯一调度和处理者,保证集群事务处理的顺序性;
  2. 集群内部各服务器的调度者
  3. 只有一个

跟随者(Follower)

  1. 处理客户端非事务请求,转发事务请求给Leader服务器
  2. 参与事务请求Proposal的投票
  3. 参与Leader选举的投票

观察者(Observer):

  1. Follower 和 Observer 唯一的区别在于 Observer 机器不参与 Leader 的选举过程
  2. 也不参与写操作的“过半写成功”策略,因此 Observer
  3. 机器可以在不影响写性能的情况下提升集群的读性能

数据流

  1. 在Client向Follwer发出一个写的请求
  2. Follwer把请求发送给Leader
  3. Leader接收到以后开始发起投票并通知Follwer进行投票
  4. Follwer把投票结果发送给Leader
  5. Leader将结果汇总后如果需要写入,则开始写入同时把写入操作通知给Leader,然后commit;
  6. Follwer把请求结果返回给Client

leader选举

选举(election)是分布式系统实践中常见的问题,通过打破节点间的对等关系,选得的leader(或叫master、coordinator)有助于实现事务原子性、提升决议效率

为什么需要选举

集群本身有很多种类,如tomcat集群,集群里面每一台机器是对等的,所以其自身不存在leader之说

另外一类,如fastDfs,其依赖于独特的HASH算法,建立文件名和路径之间的映射关系,写操作都是通过namenode分发到各台datanode之上,算法保证了文件名的独一无二,也不存在leader的说法

还有memcache集群,集群里面的机器之间彼此无心跳,通过一致性hash尽可能将key值的存储分散化,降低单一memcahe服务器down机的影响。

还有一类是主从复制,主节点负责写,从节点负责读,提高读的性能。从节点定期通过心跳与主节点沟通,一旦主节点挂掉了,从节点马上接手主节点的任务

对于分布式应用,难以避免出现网络的抖动。比如,
主节点暂时失去响应,如瞬时负载过高,网络拥塞或者其他原因导致主节点暂时失去响应,超过响应超时时间,这个时候从节点启动,承担起leader的职责,但是原先的主节点又恢复了服务。这个时候,如果没有选举机制(不能仅仅自己宣告自己是leader,还要广而告之,让其他服务器或者客户端知道自己是leader),有可能会存在两个leader节点,导致集群发生混乱

上图示例一下此类场景

主节点出现问题,那就是单点故障

单点故障

传统方式是采用一个备用节点,这个备用节点定期给当前主节点发送ping包,主节点收到ping包以后向备用节点发送回复Ack,当备用节点收到回复的时候就会认为当前主节点还活着,让他继续提供服务

当主节点挂了,这时候备用节点收不到回复了,然后他就认为主节点挂了接替他成为主节点如下图

但是这种方式就是有一个隐患,就是网络问题,来看一网络问题会造成什么后果,如下图

也就是说我们的主节点的并没有挂,只是在回复的时候网络发生故障,这样我们的备用节点同样收不到回复,就会认为主节点挂了,然后备用节点将他的Master实例启动起来,

这样我们的分布式系统当中就有了两个主节点也就是—双Master

出现Master以后我们的从节点就会将它所做的事一部分汇报给了主节点,一部分汇报给了从节点,这样服务就全乱了

选举

场景

在哪些场景下需要进行leader选举

  1. 服务器初始化启动
  2. 服务器运行期间无法和Leader保持连接

初始化时

若进行Leader选举,则至少需要两台机器,这里选取3台机器组成的服务器集群为例。在集群初始化阶段,当有一台服务器Server1启动时,其单独无法进行和完成Leader选举,当第二台服务器Server2启动时,此时两台机器可以相互通信,每台机器都试图找到Leader,于是进入Leader选举过程。选举过程如下

  • 1.每个Server发出一个投票。由于是初始情况,Server1和Server2都会将自己作为Leader服务器来进行投票,每次投票会包含所推举的服务器的myid和ZXID,使用(myid, ZXID)来表示,此时Server1的投票为(1, 0),Server2的投票为(2, 0),然后各自将这个投票发给集群中其他机器。
  • 2.接受来自各个服务器的投票。集群的每个服务器收到投票后,首先判断该投票的有效性,如检查是否是本轮投票、是否来自LOOKING状态的服务器
  • 3.处理投票。针对每一个投票,服务器都需要将别人的投票和自己的投票进行PK,PK规则如下
    • 3.1.优先检查ZXID。ZXID比较大的服务器优先作为Leader
    • 3.2.如果ZXID相同,那么就比较myid。myid较大的服务器作为Leader服务器

对于Server1而言,它的投票是(1, 0),接收Server2的投票为(2, 0),首先会比较两者的ZXID,均为0,再比较myid,此时Server2的myid最大,于是更新自己的投票为(2, 0),然后重新投票,对于Server2而言,其无须更新自己的投票,只是再次向集群中所有机器发出上一次投票信息即可。

  • 4.统计投票。每次投票后,服务器都会统计投票信息,判断是否已经有过半机器接受到相同的投票信息,对于Server1、Server2而言,都统计出集群中已经有两台机器接受了(2, 0)的投票信息,此时便认为已经选出了Leader。
  • 5.改变服务器状态。一旦确定了Leader,每个服务器就会更新自己的状态,如果是Follower,那么就变更为FOLLOWING,如果是Leader,就变更为LEADING。

Leader挂掉

在Zookeeper运行期间,Leader与非Leader服务器各司其职,即便当有非Leader服务器宕机或新加入,此时也不会影响Leader,但是一旦Leader服务器挂了,那么整个集群将暂停对外服务,进入新一轮Leader选举,其过程和启动时期的Leader选举过程基本一致。假设正在运行的有Server1、Server2、Server3三台服务器,当前Leader是Server2,若某一时刻Leader挂了,此时便开始Leader选举。选举过程如下

  • 1.变更状态。Leader挂后,余下的非Observer服务器都会讲自己的服务器状态变更为LOOKING,然后开始进入Leader选举过程
  • 2.每个Server会发出一个投票。在运行期间,每个服务器上的ZXID可能不同,此时假定Server1的ZXID为123,Server3的ZXID为122;在第一轮投票中,Server1和Server3都会投自己,产生投票(1, 123),(3, 122),然后各自将投票发送给集群中所有机器。
  • 3.接收来自各个服务器的投票。与启动时过程相同。
  • 4.处理投票。与启动时过程相同,此时,Server1将会成为Leader。
  • 5.统计投票。与启动时过程相同。
  • 6.改变服务器的状态。与启动时过程相同

过程

理想状态

  1. 在第一轮中,按照“我最牛逼,我怕谁”的原则,每个节点都推荐它自己为集群的leader节点
  2. 按照我们假设的理想条件,节点S1首先收到了S2发送来的推荐者“2”,节点S1发现“2”要比它之前推荐的“1”(也就是它自己)牛。根据谁牛推荐谁的原则,“S1”清空自己的票箱,重新选举“2”(注意,此时“S1”的新票箱中已经有两票选举“2”了,一票是它自己,另外一票是”S2”,并且所有节点都是Looking状态)
  3. 同样的事情发生在“S2”身上:”S2”收到了”S3”发过来的推荐信息,发现“3”这个被推举者比之前自己推举的“2”要牛,于是也清空自己的票箱,发起一轮新的投票,此时“S2”选举“3”。依次类推”S3”、”S4”
  4. 这里要注意S5这个节点,在第一轮接受到了来源于“S1”——“S4”的推举者(一定注意,每一次接受信息,都会广播一次“我坚持推举的人”),发现“还是推荐的5最牛”,于是“我继续推举S5吧”
  5. 以上这个过程在整个理想的网络环境上一直持续。到了第四轮,“S1”收到了“S2”发送来的推举者“5”,发现“5”要比当前“S1”推荐的“4”要牛。所以“S1”清空了自己的票箱,重新推举“5”(发送给其他所有节点)
  6. 关键的第五轮来了,我们再重复一下,经过之前的选举,现在“S2”——“S5”都已经推举“5”为Leader了,而且都处于第四轮。这时他们收到了”S1”发来的新的“第五轮”投票,于是都和之前一样,做相同的一件事:清空自己的票箱,重新向其他所有节点广播自己的第五轮投票“5”
  7. 于是,节点X,收到了大于N / 2 +1的选举“5”的投票,且都是第五轮投票。这样每个节点就都知道了自己的角色。,选举结束。所有将成为Follower状态的节点,向将要成为Leader的节点发起最后一次“工作是否正常”的询问。得到肯定的ack后,整个集群的工作状态就确认了

非理想状态

过程中出现了宕机、网络延迟、网络物理层断开等情况

在第三轮的选举过程后,“S1”,“S2”两个节点就断开了,他们的投票信息根本没有发送出去

  • “S3”收到了“S4”,“S5”发来的投票信息,这时“S3”的票箱处于第3轮,并且发现了占大多数的投票结果:大家选举“S5”为Leader节点
  • 同样的事情也发生在“S4”身上。这样“S3”,“S4”两个节点率先知道了投票结果,在最后一次询问Leader节点是否能正常工作,并得到了肯定的ACK之后,“S3”,“S4”两个节点变成了Follower状态
  • 之后,无论“S3”,“S4”两个节点收到了任何节点的投票信息,都直接向源节点反馈投票结果,不会再进行投票了。
  • 在投票完成后,“S1”,“S2”重新连入后,虽然他们发起了投票,但是不会再收到投票反馈了。直接根据“S3”或者“S4”发来的结果状态,变成Follower状态

总结

此篇zookeeper的基础内容基本都包含了

了解这些基本已经入门

下一篇学习其中最核心的zab协议,理解原子性广播概念,以及zab的实现过程

参考资料

面试问题,请说明zookeeper的选举机制

zookeeper选举机制

Zookeeper的Leader选举

再起航系列,一枚互联网菜鸟的成长历程

春风三月,却是很多职场人的混沌时节

总结性文章,让人难以落笔。可能观察生活、体察自己不够细心;也许是成长缓慢,后知后觉;更可能本身就是平庸,普通人平平淡淡,没有什么轰烈可期的事情。但不管多难,终需落笔,无论什么原因,总得回顾总结

来到互联网行业已经两年,在这个时间节点,可能再次处于混沌

在第一年里,从好奇,新鲜,无知,疑惑 到 熟悉,充足;再到第二年,可能就是重复,机械,麻木,厌烦了。

在刚换行时,一切都是新鲜,好奇的。经过一年时间的积累,对业务已经熟悉,能够应对各种业务需求,并能很好地实践业务场景中的技术栈,自己的能力圈在扩大,给人一种很充实的感觉

慢慢地,从刚开始还能对技术栈的细节,深度保持一颗期待之心,陷入了各种业务需求中,毕竟是要解决问题体现价值的,不能仅仅学习新鲜事物,这也是前辈们常讲的不要抱着进大公司学习技术的心态,热爱学习的人在哪儿都能学习,并且学好

你也是这么被洗脑的,因此你熟悉了各种业务场景,处理各样的业务咨询以及各环境的故障,帮上下游解决问题,开始重复生活,机械操作,厌烦了,总会厌烦,也有能力厌烦,毕竟你支撑了团队,混熟了业务线上的同事,老油条诞生了,大公司的螺丝钉也铸成了

这些感受都是来自外界的刺激,似乎是常理的周期反应,此时需要一丝保持平静,进步的心,都会向外寻找答案,寻求机会。一切都得向外扩张

但不管如何向外,都会落空,不踏实,终需回归自我,向内而问。不忘初心,方得始终

从工作之初,有一种思想一直占据内心,那就是跟随团队,公司成长,是最夯实,也是最快的成长试。奈何,在实现中,几任老东家都走向了末路,而我也付之东流。尤其这次,完全换了行业,一切从零开始,命也,运也?

以前厌倦了项目总是失败,总是从头开始,总想着能有一个成功的项目,不停地迭代,走向完美。这一次终于满足了,就一个项目不停地迭代,让你迭代个够。每一次迭代,历史包袱特别大,想想都替命运着急,过去走在创新的路上,嫌弃没有积累,现在迭代,又抱怨历史包袱了,人真难伺候

混沌期总是迷茫,没有方向。牛人总有规划,人生规划。普通人总是在寻找方向,选择方向,而又没有方向

在《再起航三转行互联网》中,提到程序员分为两类:技术型和产品型

技术型,一直在路上,只要没有脱离技术型公司,这永远在路上,技术人不可能,也不能丢弃技术。不管老酒装新瓶,还是新酒装老瓶,都是保持与技术的距离。但也得认清自己,不可能做到技术大牛,技术领跑者。智商,经历沉淀都已经让我无法走上这条路

产品型,但你能跨越三十五岁魔咒吗?体力,精力方面是得向年轻人低头的。

那前途在何方?哪片土地是你希望的田野?

管理领导?但现在不在其位置,考虑学习太多理论,都是形而上学。终归要落实到形而下学上

路在何方呢?

何时拨开云雾,走出混沌!

可能需要未来的你给出答案


现在可以没有答案,甚至说未来也没有答案,但行动不能停止,思考更不能停止

从第二年的开始,已经开始关注速度《再起航二成长速度》,第一年得以业务为核心,了解熟悉业务,把手头工作处理好。第二年就得把在第一年关注好奇的技术进行深入研究了,所以开始以组件为单位,一个一个了解学习,以微服务为基架,深入每一个环节

是的,来大公司不是学习的,老板聘用你,不是让你来学习的,但自己得知道,学习一刻都不能停,到大公司,的确不是学习的,在哪儿都能学习,主要是有一个场景,一个能更加深入层次学习的场景,好比之前的《剖析分布式锁》,在一般公司错误的写法,准确的说,不严谨的实现也能胜任,但更大业务量时,能不能胜任,需要思考,更多的时候,需要一个场景告诉你,你当下的完美,可能是个大大的残次品

现在不管是外部大环境,还是公司内部小环境,都不理想,尤其公司现在的体量,是不需要我的陪伴成长的,所以前方还有别的路,创业别想,成熟条件完全没有,那只能去一家与自己相匹配的公司,一起成长

公司不能大,也不能小。中型有成长的公司,核心业务部门,深入业务;或者基础架构,让面试造火箭,名副其实


可能现在格局太小,总是以技术为一切;此篇只是总结当前的一种状态,不抱怨,不迷信,何时开悟走出混沌,尽人事,知天命,一切随缘

从第一篇《算法概要》开始,到此篇已经经历了将近四个月时间,常见的基础排序已经温习完成

内外排序

内部排序:待排序记录存放在计算机随机存储器中(说简单点,就是内存)进行的排序过程

外部排序:待排序记录的数量很大,以致于内存不能一次容纳全部记录,所以在排序过程中需要对外存进行访问的排序过程

衡量效率

内部排序:比较次数,也就是时间复杂度

外部排序:IO次数,也就是读写外存的次数

IO对排序的影响可以阅读《深入浅出索引》体会

算法

排序导图

详细介绍

算法渣-排序-冒泡

冒泡排序,应该是很多人会且只会的算法;两两比较交换

为了减小比较与交换的次数,通过双向比较(鸡尾酒排序)、设定是否交换位实现

算法渣-排序-快速排序

快速排序,相对冒泡又改进了,都是交换,但引入了分治思想


算法渣-排序-插入

插入排序,像打牌时,整理牌一样,通过比较、移动来达到排序

算法渣-排序-希尔

希尔,相对插入做了改进,不是一步一步的移动,而是大步大步的移动


算法渣-排序-选择

选择,类似插入的反向操作;插入排序是边读边排,每当读入一个新的数时,目前的数组一定是排好序的。而选择排序不同,它必须是读完所有的数据之后才能开始排序的

算法渣-排序-堆排序

堆排序,借助堆数据结构,构造堆结构,选取堆顶元素,不再需要遍历所有元素选择


算法渣-排序-归并排序

归并排序,也是分治思想,但与快速有些区别;归并排序是由下向上的,先处理子数组然后再合并。而快速排序正好相反,它的过程是由上向下的,先分出两个子区间,再对子区间进行排序


算法渣-排序-基数排序

算法渣-排序-桶排序

算法渣-排序-计数排序

线性排序算法,非基于比较的排序算法,性能很高,但都有限制才能达到线性排序的效果

场景

对于排序算法选择,不能单从时间复杂上看,简单算法都是O(n^2),就不考虑,只选择改进算法

插入排序 vs 快速排序 vs 归并排序

由下图可以看出,在输入规模小于100时,插入排序要好于归并和快速排序。在输入规模小于200时,插入排序优于归并排序。规模在30以下时,插入排序效率要比快速排序高50%以上,规模在50以下时,插入排序比归并排序效率高90%以上

改进算法

在数据量大时,使用改进算法

  1. 就时间性能而言, 希尔排序、快速排序、树形选择排序、堆排序和归并排序都是较为先进的排序方法。耗时远小于O(N^2)级别的算法。
  2. 先进算法之中,快排的效率是最高的。 但其缺点十分明显:在待排序列基本有序的情况下,会蜕化成起泡排序,时间复杂度接近 O(N^2)。
  3. 希尔排序的性能让人有点意外,这种增量插入排序的高效性完全说明了:在基本有序序列中,直接插入排序绝对能达到令人吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案,要知道增量的选取直接影响排序的效率。
  4. 归并排序的效率非常不错,在数据规模较大的情况下,它比希尔排序和堆排序都要好。
  5. 堆排序在数据规模较小的情况下还是表现不错的,但是随着规模的增大,时间代价也开始和上面两种排序拉开的距离。

总结

总的来说,并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。下面有一些指导性的意见:

  1. 数据规模很小,而且待排序列基本有序的情况下,选择直接插入排序绝对是上策。不要小看它O(N^2)级别
  2. 数据规模不是很大,完全可以使用内存空间。而且待排序列杂乱无序(越乱越开心),快排永远是不错的选择,当然付出log(N)的额外空间是值得的。
  3. 海量级别的数据,必须按块存放在外存(磁盘)中。此时的归并排序是一个比较优秀的算法

试题

【京东】假设你只有100Mb的内存,需要对1Gb的数据进行排序,最合适的算法是( )

A. 归并排序  B. 插入排序  C. 快速排序  D. 冒泡排序

根据题目,我们可以知道,我们现有的内存限制使得我们无法把数据一次性加载到内存中,所以我们只能先加载一部分数据,对其排序后存入磁盘中。然后再加载一些数据,把它们“合并”到已排序的数据集中去,重复这个过程直到排序完成,显然最能胜任这个工作的是归并排序。

【2016阿里巴巴校招笔试题】现有1GB数据进行排序,计算资源只有1GB内存可用,下列排序方法中最可能出现性能问题的是( )

A. 堆排序  B. 插入排序  C. 归并排序  D. 快速排序  E. 选择排序  F. 冒泡排序

根据题目的描述,我们能够很明确的知道这道题考察我们的是原地排序的概念,这里我们只需要选择非原地排序的占用额外空间最大的算法,显然答案是”C. 归并排序”。

【2015阿里巴巴研发工程师笔试题】个数约为50K的数列需要进行从小到大排序,数列特征是基本逆序(多数数字从大大小,个别乱序),以下哪种排序算法在事先不了解数列特征的情况下性能最优

A. 冒泡排序  B. 改进冒泡排序  C. 选择排序  D. 快速排序  E. 堆排序  F.插入排序

根据题目中的描述,首先我们可以排除A、B、C,因为它们的时间复杂度都是O(n^2)。接下来我们看下D选项,我们前面提到过,快速排序在最坏情况下的时间复杂度会退化至O(n^2),F选项的插入排序在逆序数很大时性能也很差(O(n^2))。而堆排序在最坏情况下的复杂度也为O(logn),所以这里我们应该选择堆排序

参考资料

基于比较的内部排序总结

常见比较排序算法的耗时测试