面试题整理

1.spark实现左关联

1)将两张表的value打上标识

2)union all

3)group by

4)根据标识切分value,对右表value为空则添加以一个空值

5)对key内部切分出来的值进行笛卡尔积

2.spark-sql实现join的三种方式

1)broadcast join

2)hash join

3)sort merge join

3.数据倾斜处理方式

1)设置spark.sql.shuffle.partitions增加shuffle并行度

2)使用mapjoin将小表广播在各个节点上进行join

3)对包含少数几个数据量过大的key的那个RDD，通过sample算子采样出一份样本来，然后统计一下每个key的数量，

计算出来数据量最大的是哪几个key。然后将这几个key对应的数据从原来的RDD中拆分出来，形成一个单独的RDD，

并给每个key都打上n以内的随机数作为前缀，而不会导致倾斜的大部分key形成另外一个RDD。接着将需要join的另一个RDD，

也过滤出来那几个倾斜key对应的数据并形成一个单独的RDD，将每条数据膨胀成n条数据，这n条数据都按顺序附加一个0~n的前缀，

不会导致倾斜的大部分key也形成另外一个RDD。再将附加了随机前缀的独立RDD与另一个膨胀n倍的独立RDD进行join，

此时就可以将原先相同的key打散成n份，分散到多个task中去进行join了。而另外两个普通的RDD就照常join即可。

最后将两次join的结果使用union算子合并起来即可，就是最终的join结果

4.RDD，DataFrame，Dataset区别

rdd不支持sparksql操作

与RDD和Dataset不同，DataFrame每一行的类型固定为Row

Dataset，可自定义了case class确定字段名和类型

性能

DataSet以Catalyst逻辑执行计划表示，并且数据以编码的二进制形式被存储，不需要反序列化就可以执行sorting、shuffle等操作。

DataSet创立需要一个显式的Encoder，把对象序列化为二进制，可以把对象的scheme映射为Spark.SQl类型，然而RDD依赖于运行时反射机制。

通过上面两点，DataSet的性能比RDD的要好很多

5.HDFS写数据和读数据流程

HDFS数据存储

HDFS client上传数据到HDFS时，首先，在本地缓存数据，当数据达到一个block大小时。请求NameNode分配一个block。

NameNode会把block所在的DataNode的地址告诉HDFS client。 HDFS client会直接和DataNode通信，把数据写到DataNode节点一个block文件里。

核心类DistributedFileSystem

HDFS写数据流程

客户端要向HDFS写数据，首先要跟namenode通信以确认可以写文件并获得接收文件block的datanode，然后，

客户端按顺序将文件逐个block传递给相应datanode，并由接收到block的datanode负责向其他datanode复制block的副本。

具体流程如下：

1、与namenode通信请求上传文件，namenode检查目标文件是否已存在，父目录是否存在

2、namenode返回是否可以上传

3、client请求第一个 block该传输到哪些datanode服务器上

4、namenode返回3个datanode服务器ABC

5、client请求3台dn中的一台A上传数据（本质上是一个RPC调用，建立pipeline），A收到请求会继续调用B，然后B调用C，将整个pipeline建立完成，逐级返回客户端

6、client开始往A上传第一个block（先从磁盘读取数据放到一个本地内存缓存），以packet为单位，A收到一个packet就会传给B，B传给C；A每传一个packet会放入一个应答队列等待应答

7、当一个block传输完成之后，client再次请求namenode上传第二个block的服务器。

HDFS读数据流程

1、读取文件名称

2、向namenode获取文件第一批block位置，这个block会根据副本数返回对应数量的locations数，依据网络拓扑结构排序，距离client端的排在前面，

　 从原理来说，是通过DistributedFileSystem对象调用getFileBlockLocations来获取locations

3、获取距离clinet最近的datanode并与其建立通信，数据会源源不断的写入clinet端，假设第一个block读取完成，则关闭指向该datanode的连接，接着读取下一个block，以此类推。

　 假设所有的块都读取完了，则把所有的流都关闭。

　 实际上，也是通过DistributedFileSystem来open一个流对象，将其封装到DFSInputStream对象当中，block读取可以查看接口BlockReader.

4、如果读取的过程出现DN出现异常（比如通信异常），则会尝试去读取第二个优先位置的datanode,并且记录该错误的datanode，剩余的blocks读取的时候直接跳过该datanode

　DFSInputStream也会检查block数据校验和，假设发现一个坏的block,就会先报告到namenode节点，然后DFSInputStream在其它的datanode上读该block的镜像。

6.Spark内存管理

堆内内存的大小，由 Spark 应用程序启动时的 –executor-memory 或 spark.executor.memory 参数配置。

Executor 内运行的并发任务共享 JVM 堆内内存，这些任务在缓存 RDD 数据和广播（Broadcast）数据时占用的内存被规划为存储（Storage）内存，

而这些任务在执行 Shuffle 时占用的内存被规划为执行（Execution）内存，剩余的部分不做特殊规划，那些 Spark 内部的对象实例，

或者用户定义的 Spark 应用程序中的对象实例，均占用剩余的空间。

java

1.map类

1)非顺序map类

hashmap非线程安全

ConcurrentHashMap线程安全 CompareAndSwap 数组+链表+红黑树

HashTable线程安全 synchronized 数组+链表

2)顺序map类

LinkedHashMap

TreeMap

2.volatile作用

确保可见性，将一个域声明为volatile，那么对这个域产生了写操作，所有的读操作都能看到这个修改，

即使使用了本地缓存，情况也会如此，volatile域会被立即写到主存中，而读操作就发生在主存中

3.CAS算法

CAS，全称为 Compare and Swap，即比较-替换。假设有三个操作数：内存值 V、旧的预期值 A、要修改的值 B，当且仅当预期值 A 和内存值 V 相同时，

才会将内存值修改为 B 并返回 true，否则什么都不做并返回 false，进行自旋更新，即循环更新。当然 CAS 一定要 volatile 变量配合，

这样才能保证每次拿到的变量是主内存中最新的那个值，否则旧的预期值 A 对某条线程来说，永远是一个不会变的值 A，

只要某次 CAS 操作失败，永远都不可能成功。

ABA问题，添加版本号

自旋一直占用cpu资源

4.线程同步机制

1)synchronized

2)lock

3)原子类

5.jvm垃圾回收

1)引用计数，效率慢，无法解决循环引用

2)根搜索

遍历虚拟机栈或静态区域中的引用所指向的对象，并对对象标记为或对象，然后继续遍历对象成员变量中的对象引用，将其标记为活对象，然后一层一层的

遍历下去，直到找不到更多的对象，所有标记的就是活对象。

与引用计数不同这是stop-the-world垃圾回收，因为这个方法需要对应用线程进行堆栈遍历。

3)标记-清除

算法将垃圾回收分为两个阶段：标记阶段和清除阶段。一种可行的实现是，在标记阶段首先通过根节点，标记所有从根节点开始的较大对象。

因此，未被标记的对象就是未被引用的垃圾对象。然后，在清除阶段，清除所有未被标记的对象。该算法最大的问题是存在大量的空间碎片，

因为回收后的空间是不连续的。在对象的堆空间分配过程中，尤其是大对象的内存分配，不连续的内存空间的工作效率要低于连续的空间。

4)停止-复制

将现有的内存空间分为两快，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后，

清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾回收。如果系统中的垃圾对象很多，复制算法需要复制的存活对

象数量并不会太大。因此在真正需要垃圾回收的时刻，复制算法的效率是很高的。又由于对象在垃圾回收过程中统一被复制到新的内存

空间中，因此，可确保回收后的内存空间是没有碎片的。该算法的缺点是将系统内存折半。

5)标记-整理

应用于老年代，标记过程与标记-清除一样，但后续步骤不是直接对可回收对象进行清理

而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存

6)分代收集

一个新的对象首先是分配在Eden space中，当Eden space的空间满了会进行一次minor gc，

minor gc会把Eden space中回收后剩下的对象以及from survivor中剩下的对象

copy到to survivor中，并且清空Eden space和from survivor。下一次minor gc时

执行同样的操作。也就是说两个survivor space永远有一个是空的。

当一个对象在两个survivor中来回复制了N次后，这个对象会被promote到old generation中。

这个N可以配置-XX:MaxTenuringThreshold=n， 默认是15次。

当old generation 占满时会造成major gc(full gc)。

6)CMS

初始标记

并发标记

重新标记

并发清除

其中初始标记和重新标记两个步骤任需要"stop the world"。初始标记仅仅只是标记一下GC roots能直接关联到的对象，速度很快，

并发标记就是进行GC roots tracing的过程，

而重新标记阶段是为了修正并发标记期间，因用户程序继续运行而导致标记产生变动的那一部分对象的标记记录，这个阶段会比初始标记长一些，

但远比并发标记时间短。

7)G1

首先在内存划分上，G1垃圾收集器依然是基于分代收集的。不同的是G1收集器将整个堆划分为一个个大小相同的区块（Region），

每一块的内存是连续。和分代收集算法一样，G1中每个块回充当Eden、Survivor、Eden三种角色。不同的是他们是固定的，

这使得内存使用非常灵活。

执行垃圾收集时，和 CMS 一样，G1 收集线程在标记阶段和应用程序线程并发执行，标记结束后，

G1 也就知道哪些区块基本上是垃圾，存活对象极少，G1 会先从这些区块下手，因为从这些区块能

很快释放得到很大的可用空间，这也是为什么 G1 被取名为 Garbage-First 的原因。

G1收集器收集器的收集活动主要包括四种

新生代垃圾收集

后台收集，并发周期

混合式垃圾收集

以及必要时Full GC

6.java锁

1)悲观锁，乐观锁

悲观锁：认为自己在使用数据的时候一定有别的线程来修改数据，在获取数据的时候会先加锁，确保数据不会被别的线程修改

锁实现：关键字synchronized，接口Lock的实现类

适用场景：写操作较多，先加锁可以保证写操作时数据正确

乐观锁：认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据

锁实现：CAS算法，例如AtomicInteger类的原子自增是通过CAS自旋实现

适用场景：读操作较多，不加锁的特点能够使其读操作的性能大幅提升

2)自旋锁

是指当一个线程在获取锁的时候，如果所已经被其他的线程获取，那么线程将循环等待，然后不断的判断锁是否能够被成功获取，

自旋直到获取到锁才会退出循环。

不放弃cpu资源

3)可重入锁reentrantLock

可多次加锁

state：记录锁被上锁的次数

exclusiveOwnerThread：锁所在的线程

head-tail：获取锁的线程队列

4)synchronized锁的膨胀升级

1.无锁

同步对象在刚生成后还没有线程访问时，是无锁状态

2.偏向锁

第一个线程访问同步锁后锁升级为该线程的偏向锁

锁偏向于第一个访问的线程，如果在运行过程中，同步锁只有一个线程访问，不存在多线程争用的情况，则线程是不需要触发同步的，

这种情况下，就会给线程加一个偏向锁

大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入偏向锁

如果一个线程在进入同步锁后释放并消亡，其他线程再进入同步锁依然能将所改为自己的偏向锁

3.轻量级锁

如果线程在访问一个偏向锁时偏向锁的线程ID不指向该线程，且使用CAS获取偏向锁失败，则表示由竞争。当达到全局安全点时(safepoint)时获得

偏向锁的线程被挂起，偏向锁审计为轻量级锁

轻量级锁即在五金正的情况下使用CAS操作小区同步锁使用的互斥量

4.重量级锁

一个线程在尝试获取一个轻量级锁失败后，会启用自旋锁，即循环使用CAS获取轻量级锁，如果依旧失败，会升级为重量级锁。

计算机基础

1.三次握手四次挥手

三次握手

客户端发送一个SYN=1，seq=x的连接请求报文，

服务端收到后发回一个SYN=1，ACK=1，seq=y,ack=x+1的连接请求&连接确认的报文，

然后客户端收到后发送一个ACK=1，seq=x+1，ack=Y+1的连接确认报文，然后就连接建立，可以开始发数据

四次挥手

客户端发送一个FIN=1，seq=u的断开连接请求报文

服务端发一个ACK=1，seq=v，ack=u+1的确认报文

但是如果你还有数据没有发送完成，则可以不必急着关闭socket，可以继续发送数据。

所以你先发送ACK，告诉Client端，你的请求我收到了，但我还没准备好，请你继续等我的消息

这时候客户端就进入FIN_WAIT状态，继续等待服务端的FIN报文，

当服务端确定数据发送完成了，则向客户端发送FIN报文，告诉客户端，我的数据发送完了，准备好关闭连接了。

客户端收到FIN报文后，就知道可以关闭连接了，但是他还是不相信网络，怕服务端不知道要关闭，所以法师部分ACK后进入TIME_WAIT状态

如果服务端没有收到ACK则可以重传。

服务端收到ACK后就知道可以断开连接了。

客户端等待了2MSL后依然没有收到回复，则证明服务端已正常关闭，客户端也关闭连接。

2.https建立连接

客户端发送支持的加密协议及版本SSL，TLS给服务端

服务端从中筛选适合的加密协议，返回证书，证书中有公钥

客户端使用根证书验证证书合法性

客户端生成对称秘钥，通过证书中的公钥加密，发送到服务端

3.二叉树的遍历

前中后序遍历 栈

层序遍历 队列

4.进程间通信

1)unix进程间通信

管道：一种特殊的文件，父子进程间，半双工

命名管道：非父子进程，文件

2)xsi ipc机制

信号量集；用于实现进程间的同步和互斥

共享内存：进程间高效的共享数据，适用于数据量大，速度要求高的场景

消息队列：进程间传递数据的一种简单方式

3)不同主机间进程间通信

RPC：远程过程调用

socket：tcp/ip网络套接字

机器学习

word2vec