常用热点知识回顾

什么是堆?什么是栈?堆和栈的区别

程序加载进内存之后,操作系统会为进行分配一段固定大小的空间,这个空间由很多组成部分,堆和栈是其中的两个部分。
其中栈地址占用的空间比较小,一般是1M左右的连续空间,栈空间的数据是由系统自动分配的,按照后进先出的顺序进行压栈操作,一般存放的数据是程序执行过程中使用的局部变量,函数参数等。
而堆一般占用的空间比较大,根据程序需求来定。比如Java的JVM可以使用配置参数来决定堆的大小。堆中存放的数据是由程序主动申请和释放的,比如通过new操作创建的对象等。

JVM的线程栈申请的内存空间数据堆外内存,是向操作系统申请的,使用的是操作系统剩余的可用内存,同时也不属于JVM的直接内存。(可以通过配置-Xmx 10m,然后创建大量线程并阻塞来验证)。JVM能创建的线程数需要的内存,不是JVM运行内存,堆内存,直接内存,而是操作系统剩余的可用内存,这个也决定了能创建的线程数,如果内存不够用,创建线程的时候便会出现内存溢出的错误。

在操作系统的可用内存不足的情况下,想要创建更多的线程,可以考虑减少线程栈的空间大小(-Xss),但是不建议过小,栈尝试减小容易栈溢出错误。

extends 关键字和 interface关键字的作用?为什么要区分继承和接口?

java通过extends关键字定义类的继承关系,继承是为了得到父类所拥有的方法和属性,可以添加新的属性和方法,对原来的类的功能进行扩展,父类的方法也可以被重写,实现类的运行时多态。
继承可以实现代码的复用,实现统一的处理流程。在Java中,要实现多重继承可以通过多级继承的方式。

但是由于继承会破坏类的封装性,子类会继承一些自己用不到的方法和属性。

接口只定义行为,而不包含属性。接口是用来限定行为的,一般只用来定义抽象方法。
接口是一种特殊的抽象类,内部的所有方法都是抽象的,需要子类去实现。

继承更多地来让子类能够复用已存在的属性和方法,而接口则是用来限定子类实现某种行为。

机器的大小端编码

十六进制 0x12345678
网络字节一般使用大端编码方式:12 34 56 78
个人电脑一般使用小端保存: 78 56 34 12

Mysql框架体系

Mysql基本框架大致分为连接器,分析器,优化器,执行器几个部分。

行为树的节点有哪些:
选择节点:每次执行的时候任意选择一个节点执行,返回该节点的执行状态;
顺序节点:序列执行所有节点,任意节点返回失败则节点返回失败
循环节点:循环执行一定次数后返回成功
条件节点:返回条件的判断结果
动作节点:叶子节点

状态机:状态与状态之间约束性更强,状态变多之后,逻辑变得复杂难以控制。
行为树:逻辑更清晰,更容易控制。即使有很多种行为,也可以比较清晰地控制。

决策树,行为树和状态机有什么区别?

决策树(Decision Tree),又称判定树或分类树,目的是根据给定的分层条件,逐层深入,最终得到一个判定结果。
决策树决策的过程从根节点开始,选择一个特征作为当前节点的分裂标准,自上而下生成子节点,直到到达叶子节点得到分类决策的结果。

状态机的全称是有限状态自动机,优点是简单,关系直接,缺点是没有层次,难以分解和扩展。

行为树是(Behavior Tree)专注于行为的执行过程,在给定的条件下,角色应该优先或随机执行哪些行为,用来控制复杂的动作逻辑。
优点是相较于状态机,逻辑更加扁平清晰,容易维护和扩展。

行为树相当于一个更扁平的分层的状态机,它将状态机中的每个状态变成了一个持续的行为节点,状态与状态之间的转换的判断条件,变成的平行的优先级更高的选择节点。
从一个状态变成另一个状态的过程,就转化为了高层行为树的行为切换。

寻路算法:

除了A*,还有哪些寻路算法?
迪杰斯特拉,无启发函数的全局寻路。
Recast + detour 三角面+转向行为控制算法
流场寻路,群体寻路

什么是多线程数据的数据原子性,可见性,有序性

可见性:一个线程对一个共享变量的修改,能及时地被其他线程得知。Java的内存模型是在变量修改后将新的值从线程工作内存同步回主内存。
synchronized :线程加锁时,将清空工作内存共享变量的值,从主内存中读取最新值;
线程解锁时,将共享变量最新值刷新到主内存中。

原子性:当一个线程访问一个变量时,该操作不会被中断,保证数据操作是以原子方式进行的;
volatile不能保证原子性,可保证可见性;volatile修饰的变量不允许线程内部缓存和重排序;

有序性:在单个线程内部,所有的操作都是有序的。

进程与线程的区别,死循环与内核态

进程是资源分配的最小单位,线程是CPU调度的最小单位。

进程在执行过程中拥有独立的内存单元,而多个线程共享进程的内存。(资源分配给进程,同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段(代码和常量),数据段(全局变量和静态变量),扩展段(堆存储)。但是每个线程拥有自己的栈段,栈段又叫运行时段,用来存放所有局部变量和临时变量。)

操作系统面试

C++与Java的区别和特点

Java没有指针,对开发者隐藏了指针。Java自带内存垃圾回收机制。

简述IO多路复用

同步非阻塞(NIO)
异步非阻塞
异步阻塞

Select/poll
Epoll

Linux 上多路复用方案有 select、poll、epoll这几种。

文件描述符就是操作系统记录的文件描述符表fd_table 的下标,所以是一个数字。

epoll 实现原理 https://www.zhihu.com/question/486578358
https://mp.weixin.qq.com/s/OmRdUgO1guMX76EdZn11UQ

poll与select 需要将进程关心的fd集合从用户态拷贝到内核态,当文件描述符(fd)较多时,开销比较大。内核每次都需要遍历这些文件描述符,对每个socket执行recvfrom检查是否可读,效率很低,状态切换的开销也较大。

epoll使用事件机制,在内核中维护了一颗红黑树结构和一个就绪链表,来保存用户关心的socket。当接收到数据时,将对应的socket放到就绪链表中。进程每次检查只需要看就绪链表有没有需要处理的socket即可。(红黑树的查找效率,插入效率和内存开销等比较均衡)

select缺点:
(1)每次调⽤用select,都需要把fd集合从⽤用户态拷贝到内核态,这个开销在fd很多时会很⼤大
(2)同时每次调⽤用select都需要在内核遍历传递进来的所有fd,这个开销在fd很多时也很⼤大
(3)select⽀支持的⽂文件描述符数量太⼩小了,默认是1024

windows下iocp
微软提出 IO完成端口(实质是一个io事件队列)模型的初衷,就是为了解决这种”one-thread-per-client”的缺点的,它充分利用内核对象的调度,只使用少量的几个线程来处理和客户端的所有通信,消除了无谓的线程上下文切换,最大限度的提高了网络通信的性能(等到有用户请求来到的时候,就把这些请求都加入到一个公共消息队列中)

IOCP模型与EPOLL模型的比较
https://www.cnblogs.com/lancidie/archive/2013/05/02/3054063.html

Netty的特点
NIO网络封装,零拷贝 https://blog.csdn.net/weixin_42096901/article/details/103017044
FileChannel.transferTo()

Websocket与 HTTP2 的区别

都是应用层协议,都是长链接。

HTTP主要是请求式的方式获取信息,服务器无法主动推送。

WebSocket是基于HTTP1.1的协议,可以简单理解为创建了一条TCP连接,可以让双方主动进行消息通信。

HTTP2虽然支持服务器推送资源到客户端,但那不是应用程序可以感知的,主要是让浏览器(用户代理)提前缓存静态资源,所以我们不能指望HTTP2可以像WebSocket建立双向实时通信。

HTTPS 与 HTTP的区别
HTTPS用的443端口,并且使用SSL对传输的数据进行加密。需要服务器持有CA证书(公钥与私钥,非对称加密),可以防止中间人攻击。HTTPS会与服务器进行多次握手,先请求公钥,然后生成对称秘钥,然后通过公钥加密将对称秘钥发送给服务器,再与服务器通过对称秘钥通信。导致请求资源的时间变长。
HTTP用的是80端口,请求时明文传输,可以被中间人攻击。

简述常用设计模式

单例模式,观察者模式,代理,装饰,命令,组合,命令
工厂模式,抽象工厂模式

装饰器模式和代理模式的区别是:装饰器使用外部对象,代理模式内部处理所有细节,对外暴露接口。

Java实现单例模式,通过类加载机制来实现,避免双重检查锁(DCL,Double Check Lock),并且双重检查锁存在指令重排问题。

Reactor与观察者模式的区别

线程池的核心参数

核心线程数量,最大线程数量,空闲保活时间,线程安全的任务队列。

数据结构与算法

链表与跳表

快速排序的时间复杂度:最好的情况是O(n log n) 最差是 O(n^2)
快速排序不是稳定的排序,不稳定性发生在指针交换元素时,位于数组中间的元素可能交换到更前面,导致值相等的顺序发生变化。

常用Hash表的实现原理
Hash冲突的处理方式一般有两种:
链表法:将具有相同Hash地址的元素组成一个链表,可以进一步优化为红黑树。(Java HashMap的方式)
开放寻址法:当发生冲突时,重新探测一个空闲位置。删除操作比较麻烦,由于是通过位置空闲来判定是否需要向后查找。所以不能直接删除元素,需要将其标记为已删除。(Java ThreadLocalMap使用开放寻址-线性探测,Python 字典采用的是二次探测序列 i=(5*i)+1+perturb )
线性探测法会每次向后查找一个位置;二测探测使用其他的偏移计算;

当Hash表已满需要扩容时,可以采用渐进式rehash方式减少重新分配的延迟。

Python3.6之后的字典已经默认会记录插入顺序,不在需要OrderedDict,但是类似LinkedHashMap,其只是提供了遍历的顺序,由于是使用双端链表实现,没有提供根据索引获得第N个插入项的方法,只能遍历。

如何知道一个整数的二进制位中有多少个1
1 n&1 按位与,然后右移,数1的个数
2 n&(n-1),直到n==0
3 查表,记录一个byte的所有情况,然后将int 拆分为多个byte,然后查表相加

求平均值:

return a/2 + b/2 + (a&b&1);

return low + (high - low) / 2;

Java如何判断和解除线程死锁

通过top指令查看进程PID,然后通过jstack查看进程的线程堆栈,如果有线程死锁,会有日志显示。

Java中HashMap的实现原理

与n取模其实就是和n-1相与,取模(NUM 对N取模)就是 看NUM除以N后的余数,从二进制的角度来看,其实就是在找NUM的log2(N)位是多少。

当n是2的倍数时,x%n === x&(n-1)

帧同步与状态同步的区别

状态同步与帧同步 https://www.cnblogs.com/sanyejun/p/9069165.html

帧同步的战斗逻辑在客户端,多台客户端之间表现要实时一致,容易产生作弊等行为,服务器主要是转发操作数据。操作是客户端先行。
状态同步的逻辑和数值在服务端,安全性比较高,但是计算压力比较大。

Mysql B+树与红黑树的区别

Mysql的 JOIN 与 UNION,INNER JOIN 与LEFT JOIN

union只是将两个表的相同字段的查询结果作为像集合一样合并在一起,而join是将条件相同的数据合并为一行。

LEFT JOIN 会返回左边表中所有的行,以及右边表中满足条件的行;
RIGHT JOIN 会返回右边表中所有的行,以及左边表中慢速条件的;。
INNER JOIN 只会返回两个表都满足条件的行;

红黑树有哪些应用?
linux 进程调度器用红黑树(所有可运行进程都按等待时间在一个红黑树中排序,按照等待CPU的时间排序,进行相对公平的CPU时间调度)
epoll 红黑树,c++ map默认使用增序红黑树(与之对应的是unordered_map,Hash表)
Java TreeMap 是红黑树实现,HashMap中也用到了红黑树。

压测的性能指标

TPS(每秒处理的事务数,第一个请求发送到接收到最后一个请求的响应的过程,以此来计算使用的时间和完成的事务个数。)

QPS(每秒查询率,一台服务器每秒能够响应的查询次数(数据库中的每秒执行查询sql的次数),只能显示单一事务的处理效率,不够全面)
平均响应时间,消息的最大耗时,平均耗时
平均发送流量,接受流量
服务器的CPU占用率,内存使用量(是否有内存泄漏)

计算服务器可承受的最大在线人数

压测常见的问题及优化方法

  1. 消息堵塞的压力,通过减小消息中转流程来降低压力:比如聊天消息放到Redis上缓存,然后聊天服务器自取;
  2. AOI消息包过多,导致客户端处理速度下降:合并数据包;
  3. 数据量大,起服缓慢:多线程加载,必要的数据字段增加索引;8线程,20分钟优化到2分钟。
  4. 登陆速度慢:登陆加载数据较多,造成吞吐量低。邮件,个人商店,好友列表等改为异步加载。结合其他优化,TPS从30提升到300,登陆平均耗时从200ms到6毫秒;
  5. 消息转发瓶颈:聊天消息需要发到游戏服填充玩家信息,然后到公会服获取公会成员数据,然后到聊天服转发,流程复杂,直接数据缓存到Redis,然后消息直接发到聊天服。
  6. CPU瓶颈问题,CPU未跑满,但是吞吐量(TPS)上不去,可能是大部分线程都在等待网络IO或系统调用(比如锁释放)?
  7. 公平锁问题,DBPool连接池应设置为非公平锁模式。公平锁的性能较低。

Zookeeper 是一个用来提供分布式程序协调服务器的,可以提供配置管理,分布式锁,节点状态管理,Leader选举等。
Dubbo 阿里开源的高性能RPC调用框架,支持负载均衡和服务自发现和注册。
Etcd: ETCD是使用Go语言编写的分布式强一致性的KV存储系统,是比zookeeper更优秀的管理工具。可以提供分布式配置管理,服务发现,分布式队列,分布式锁,分布式Leader选举等功能。Etcd:原理与实践

Etcd如何保证强一致性呢?Raft算法通过选举来保证共识一致,通过二阶段提交来保证强一致性。二阶段提交就是事务执行只需要一半以上的成员同意,就会认为提交成功,强制执行。Etcd背后的Raft一致性算法原理

Etcd默认心跳间隔时间是100ms,默认竞选超时时间为1000ms,Raft为了优化选票被瓜分导致选举失败的问题,引入随机数,每个节点等待发起选举的时间点不完全一致,
优雅的解决了潜在的竞争活锁,同时易于理解。

k8s全称kubernetes,是一个用于管理分布式容器的管理工具。

GDB自动化操作技术

常用的Jvm调优操作:

-Xms 和-Xmx -XX:-MaxNewSize 和 -XX:NewSize,-XX:MetaSpaceSize 和 -XX:MaxMetaSpaceSize 设置为相同大小,避免出现其动态缩扩容引发系统停顿。
通过观察GC日志,来判定是否要进行JVM调优,如出现频繁的fullGC,说明要么JVM配置的内存不够用,要么年轻代配置的空间比例太小,导致大量临时对象生存到了老年代,需要调大一点。

linux内核每次创建一个网络连接时,都为为它分配一个发送缓冲区和一个接收缓冲区。这个发送缓冲区的大小就是net.core.wmem,对于tcp连接,则会使用覆盖的net.ipv4.tcp_wmem,接收缓冲区大小则是net.core.rmem,对于tcp连接,则会使用覆盖的net.ipv4.tcp_rmem,从上面的结果来看,发送缓冲区默认是16384字节,接收缓冲区默认是87380字节。对于tcp连接而言,随着连接数的上升,这些缓冲区大小会逐渐减少,最后接近或等于net.ipv4.tcp_wmem/net.ipv4.tcp_rmem的最小值。同理,连接数减少时,缓存区大小会逐渐增大,最后接近或等于net.ipv4.tcp_wmem/net.ipv4.tcp_rmem的最大值。

每一个tcp连接占用的内存计算可以简化为:tcp写(发送)缓存+tcp读(接收)缓存。
nr_open就是linux系统一个进程能够打开的最大文件描述符数量。多数linux默认设置nr_open是 1024k,也就是1048576,最大不能超过4096k,所以, 想要支持超过100k,还需要在/etc/sysctl.conf中重新上配置fs.nr_open的值

布隆过滤器
通过一个超长的比特数组,对于插入的每个元素计算多个hash值槽位,将对应的数组位置置位1。
优点是:不需要存储key值,比较节省空间。
缺点是:无法删除元素,且判定key存在时,有一定概率key其实并不存在。(因为可能有许多其他值覆盖了对应的索引。)

过滤器的长度和Hash值的个数直接影响过滤器的误报率和执行效率。但是由于其索引的重复性,导致其无法进行删除,只能添加。

应用场景主要是用来防止缓存穿透。比如一个资源并不存在,但是缓存逻辑是不存在就去DB拿数据,但其实DB也没有。还有比如列表非常长的白名单之类的。

广度优先搜索算法
广度优先搜索使用队列来实现,将新元素放入队列尾部,每次从头部取数据。

迪杰斯特拉和最小生成树都使用了广度优先搜索的原理

深度优先搜索算法
深度优先搜索使用栈来实现,每次从尾部压栈,然后从尾部弹出,取下一级数据。

裴波那切数列的算法复杂度分析
F(n) = F(n-1) + F(n-2)
对于每个F(n) 都被拆分为两倍的同数量级的复杂度,一直持续 N-2 次这种计算,也就是 2^(n-2),近似于 O(2^n)的复杂度。区分于O(n^2)的复杂度。

闭包和匿名函数
闭包:闭包是一个函数和该函数被定义时的词法环境的组合。

python 的 async 和 await 对象

async 用于定义异步函数,这个定义会让函数的结果变成一个 Promise 对象。

await 用于阻塞代码,暂停当前 async function 的执行,等待右侧b表达式中 Promise 的返回结果。类似于java中的CompletableFuture。这个对象的底层通过异步执行得到一个运算结果,回填给 Promise 对象。resolve的最终结果作为await表达式值,然后继续执行async function的后续逻辑。如果等待的计算出现异常,await 会把异常结果抛出。

为什么普通的三色标记GC需要STW?为什么go 1.8 之后的混合写屏障GC不需要STW?

为什么JVM的CMS垃圾回收过程中需要写屏障?
CMS并发标记清除过程:

  1. 初始化标记(STW):遍历GC ROOT直接可达的对象,将其压入标记栈(mark_stack),然后恢复线程。
  2. 并发标记
  3. 重新标记(STW)
  4. 并发清除
  5. 并发重置

JAVA GC 安全点的选择:一般是选择一些执行时间比较长的指令作为安全点,比如:循环的跳转,异常跳转,方法调用和返回等。线程每执行到安全点时检查安全标志。对于已经sleep和block的线程的方式是字节码检查引用关系不会发生变化的地方作为安全区域,每次进入安全区域时会修改自己的标志位已进入安全区,GC时可忽略。

写屏障有两种类型:
插入时写屏障:对堆内存新增引用的对象,标记为灰色,重标记阶段再次STW遍历;
删除时写屏障:对堆内存减少引用的对象,标记为灰色,重标记阶段,再次STW进行快照差异对比
混合写屏障:结合上述两种情况,将新增引用和减少引用的对象,全部标记为灰色。

为什么需要写屏障:当GC线程进行并发操作时,应用程序可能会进行新增对象、删除对象、变更对象引用等一系列操作。这种情况有可能造成一些对象的引用丢失,导致内存被误回收。写屏障就是监测,当引用改写时,进行记录。因此需要监测这些引用的变动。CMS在并发标记结束后需要对占空间进行重新标记,以确定哪些引用发生了变动,因此需要STW。

go语言1.8开始采用混合写屏障,在运行时可以与业务并发的时候依次对每个goroutine栈空间做快照,相当于没有STW。Golang 混合写屏障原理

MySql 的binlog是什么及怎么保存?redolog和undolog?

堆排序及二叉堆

二叉堆本质上是一种完全二叉树,完全二叉树适合使用数组来存储,可以通过坐标找到节点的左右子节点。
大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小丁对:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

零拷贝
RocketMQ 提升文件读写使用MMap零拷贝:
四次拷贝变成3次拷贝:
网络设备缓冲区 -> DMA拷贝到socket缓冲区(内核页) -> CPU拷贝到进程内存(用户态) —> cpu拷贝到文件缓冲区(内核页) —> DMA拷贝到文件

// 操作系统将文件映射为内存映像(DMA),跳过CPU拷贝过程
fileChannel.map 方法

关于数据库连接池的数量:

结论:连接池数量 = ((核心数 * 2) + 有效磁盘数)
https://blog.csdn.net/weiguang102/article/details/115701622

JUC:java.util.concurrent 包
JMH:Java 精细基准测试工具包,1.9自带,早起版本需要另外下载jar包。

高并发的Actor模型与 CSP模型
Actor模型与CSP模型

CSP模型是go语言框架下强大的并发编程模型。中文叫通信顺序进程(Communication Sequential Process),是基于go语言的goroutine和chan来实现的。

Actor模型的核心是Actor对象,Actor之间只能通过消息传递进行通信,外部不可以修改Actor的状态,Actor可以阻塞自己,但不会阻塞线程。

Actor与Actor之间可以直接通信,而Coroutine之间通过channel通信。

Aoi的实现机制与问题

https://github.com/sundream/aoi

九宫格
优点: cpu消耗小
缺点: 内存开销大,内存消耗不仅和实体数有关,还和场景大小成正比

十字链表
优点: 内存开销小,内存消耗仅和实体数有关,和场景大小无关
缺点: cpu消耗高,每次移动都需要计算视野差,当实体在小区域堆积严重时效率更差

CI/CD 与 DevOps

CI/CD 持续集成,持续发布
DevOps 开发即运维


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com

文章标题: 常用热点知识回顾

文章字数: 6,556

本文作者: Jun

发布时间: 2021-06-24, 18:32:00

最后更新: 2022-06-13, 17:35:04

原始链接: http://yoursite.com/2021/06/24/常用热点知识回顾/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏