由6.824和Hadoop技术资料整理，持续更新中
文章目录
6.824
-
什么是CAP？
一致性 可用性 分区容错性
分区容错是必然要提供的一个特性，如果要保证一致性，那么可用性不能得到保障。
云服务厂商一般提供5个9的可用性保障。 -
简述一下GFS的一致性策略？
元数据的写入是加锁串行的
无并发写一个chunk的时候，当三个副本全部写成功的时候才会返回成功，否则返回失败
这将导致GFS系统中文件的不一致性
有并发的时候由primary决定写的顺序，所有的副本按照这个顺序执行，保证最终一致
注意！串行成功是一致已定义的，并行成功是一致未定义的 -
master恢复
master的历史信息使用快照存储，最近的操作使用日志存储 -
GFS如何进行快照？
首先master取消对当前chunk的租约，保证对chunk的修改通过master进行
之后创建快照 维护对于chunk的引用计数
后续计数>2，则分开独立访问 -
GFS文件系统结构？
GFS组织成树的结构，修改文件需要获得父亲节点的读锁和子节点的读写锁
文件惰性删除，文件重命名为包含时间戳的隐藏文件名，在例行的文件空间扫描中才会删除
这样删除更加可靠，cpu使用更加平衡，为人为的误操作兜底 -
GFS如何保证高可用？
服务快速拉起，master和chunk server都设计成秒级启动
chunk复制策略，保证数据不丢
master节点建设主备，client操作在主master和从master全部落盘后才返回，外部监控进程监控master状态并在master故障后选择新的master升主 -
GFS如何保证数据完整性？
chunk server将chunk切成64KB大小的块，并为每个块维护一个32位的checksum。对读操作，数据返回client之前会检查checksum。对写操作，需要对写范围有覆盖的第一个64KB块和最后一个先进行校验，防止原来存在损坏的数据被本次写隐藏了，然后进行实际写入并重新计算checksum。chunk server空闲时会对所有chunk做整体扫描，尤其针对一个不活动的chunk，防止master认为chunk已经有足够的副本数量了但是实际上副本内容已经损坏。 -
状态备份的两种方式？
状态转移（State transfer） 持续增量同步 Primary 的状态到 Backup，包括CPU、内存、IO设备等等；但是这些状态通常所占带宽很大，尤其是内存变化。
冗余状态机（Replicated State Machine） 将服务器看作是一个具有确定性状态的状态机，只要给定相同初始状态和同样顺序的确定输入，就能保持同样的状态。同步的是外部的事件/操作/输入；同步的内容通常较小，但是依赖主机的一些特性：比如指令执行的确定性（deterministic）。而在物理机上保证确定性很难，但是在 VM 上就简单的多，由于 hypervisor 有对 VM 有完全的控制权，因此可以通过某些手段来额外同步某些不确定性输入（比如类似随机数、系统时钟等）。 -
如何解决复制状态机中primary和backup不一致的问题？
控制输出，保证状态一致后响应成功 -
VM-FT如何解决重复输出的问题？
TCP栈序列号/检验重复的机制 -
VM-FT如何解决split brain？
三方机构Test-and-Set，Test-and-Set服务就是一个仲裁官，决定了两个副本中哪一个应该上线 通过标志位实现 -
raft 如何进行leader选举？
使用随机计时器 -
为什么要有raft？它用来解决什么问题？
raft是一个一致性算法，
复制状态机（replicated state machines）用于对有单个集群leader的大型系统进行leader选举和配置信息的存储。复制状态机通常使用复制日志实现，一致性算法的任务是保证复制日志的一致性。 -
共识算法的特性有哪些？
1.在网络延迟、分区和包丢失、复制和重排序条件下保证安全性（永远返回正确的结果）
2.只要大多数服务器可操作、可通信那么就是完全可用的
3.不依赖时间来保证一致性
4.少数速度较慢的服务器不影响整体系统性能 -
※raft如何实现一致性？
首先选举一位leader leader有管理复制日志的责任，接受来自客户的日志条目，在其它服务器上复制它们。
主要是通过log的read和commit的顺序来实现的
这样就把一致性问题分为了三个子问题：leader选举，日志复制与一致性，安全性 -
brain split如何解决？
在raft中，使用过半票决的方式解决。
如果系统中有2*F+1个服务器，那么，最多可以接受F个服务器出现故障
raft实际上更加依赖于过半服务，因为raft的每一个操作的过半服务器，必然有一个处于上一个操作的过半服务器中，新的过半服务器就会知道旧的过半服务器的term -
raft在分布式数据库中的角色是什么？
中间层，构建多副本日志。只有过半服务器拷贝了操作的副本，才能够继续执行数据库操作 -
raft应用层调用流程？
客户端通过Start函数将请求存放在log中，commit之后，raft通过channel（ApplyCh）通知客户端成功。
包括Log位置，term number等等信息。 -
raft中旧的leader发送消息时故障了，或者新的leader当选之后马上故障了，log如何做恢复？
必须假定所有槽位上的请求都被commit了 -
哪些数据需要持久化存储？
log currentterm votefor
持久化votefor是为了防止脑裂的情况
持久化currentTerm是为了保证一个任期内只有一个leader -
如何确定raft代码的持久化操作成功了？
使用unix的fsync系统调用 -
raft日志快照怎么做？
日志快照是通过key-value表单对于log的压缩 -
什么叫做线性一致？标准是什么？线性一致的代价是什么？
线性一致就是强一致
任何一个客户端读取到了新值之后，之后所有的查询也必然会返回新值 -
什么是zookeeper？
zookeeper是一个通用的协调服务，负责与客户端交互
下面的一层则是与raft类似的管理多副本的Zab -
zookeeper如何通过修改read的方法来保证线性一致的？
实际上，zookeeper不是严格的读线性一致，而保证严格的写线性一致
并且对于单个客户端的请求是线性一致的
如果与客户端交互的副本故障了，新的可用副本对于这个故障副本之前的状态仍然是可见的，并且新的读一定在旧的读之后执行
每个log条目都会被leader打上zxid的标签，就是log对应的条目号，客户端会记住最高的zxid并且在请求中带上这个参数 -
zookeeper如何来弥补它的非线性一致性的？
zookeeper提供了sync来保证下一次读请求看到sync对应的状态，这个状态合理的被认为是最新的，但是这是一个代价很高的操作。 -
zookeeper的配置更新过程是什么样的？
zk用ready-file标志配置可读性，需要更新配置时，首先删除ready-file。
如果客户端在读所有通知之前，如果对于配置有了新的更改，zk使用watch保证在收到删除ready file的通知之前，看到的都是配置更新前的数据 -
zookeeper被期望用来解决什么问题？
1.test-and-set
2.发布其它服务器使用的配置信息
3.选举master -
说一下zookeeper的组织形式和API组成？
zookeeper的组织形式类似于一种文件系统，包含了三种类型的znode，
第一种：regular znodes 一旦创建，就永久存在，除非被删除
第二种：Ephemeral znodes 如果zookeeper认为客户端挂了，就会被删除
第三种：Sequential znodes 递增的文件
暴露的api如下：
create(path,data,flag) 不存在则创建返回true，存在则返回false flag表明文件类型
delete(path,version) 符合版本号则删除
exist(path,watch) watch用于检测文件是否发生了变化
getdata(path,watch)
setdata(path,data,version)
list(path) 列出目录下文件 -
如何用zookeeper实现计数器？
WHILE TRUE:
X, V = GETDATA(“F”)
IF SETDATA(“f”, X + 1, V):
BREAK
这里是用版本号实现顺序一致的 -
上面的方案有什么问题？
1.请求的复杂度是nlogn
2.数据存储在内存中，如果大于内存容量，就会出现很多问题
3.这是一个mini-transaction 不是完整的数据库事务，而是一个简单的提供原子性的事务 -
如何使用zookeeper实现非扩展锁？
WHILE TRUE:
IF CREATE("f", data, ephemeral=TRUE): RETURN
IF EXIST("f", watch=TRUE):
WAIT
将exist函数加上watch=true来监测文件的删除
-
如果在exist执行中文件被删除了，会发生什么？
1.如果在两个写请求之间执行，那么副本会在watch表单中增加一条记录，之后delete 副本会发给exist请求一个通知
2.delete之后执行则会返回false -
非扩展锁意味着什么？
意味着要受到惊群效应的影响，锁争用很重 -
如何用zookeeper实现可扩展锁？
CREATE("f", data, sequential=TRUE, ephemeral=TRUE)
WHILE TRUE:
LIST("f*")
IF NO LOWER #FILE: RETURN
IF EXIST(NEXT LOWER #FILE, watch=TRUE):
WAIT
-
为什么这种方式能防止惊群？
因为只会等待上一个序列号 -
什么叫CRAQ？
Chain Replication with Apportioned Queries 是对于链复制的改进方案，能够在任意副本执行读请求的前提下，保证线性一致性。
链复制将服务器组织成链的形式，从head写入，从tail读出
当请求未到达tail时，请求不会commit
chanin replication既不能抵御网络分区，也不能抵御脑裂
它需要一个外部的权威确保谁是活的和死的，这个权威称为configuration manager 配置管理器
如果有节点挂了，那么将会送出新的配置，这个服务是容错的，不否认自己，当有网络分区时不会出现脑裂（基于raft或者paxos）
CRAQ的一个重要特性就是减轻了leader的负担，而如果有一个慢的副本时，CR就会有性能的问题，因为CR需要经过所有的副本
这时候用raft或者paxos更好 -
什么是EBS？它有什么问题？
EBS是Amazon之前提供的云产品服务。
EC2实例运行一个标准操作系统，在操作系统上运行应用程序，并分配一个硬盘
Amazon为用户提供链复制的EBS来作为EC2的数据库服务
每一个EBS volume只能被一个EC2实例所使用
如果你在EBS上运行一个数据库，那么最终会有大量的数据通过网络来传递，网络负载在这里非常重要
另一个问题是EBS的容错性不是很好，Amazon总是将EBS volume的两个副本存放在同一个数据中心。 -
Amazon RDS架构是怎么样的?有什么问题？
基于开源的MySql redo log构建的关系型数据库
其data page和WAL log存储在EBS中，每一次写操作，除了发送给AZ1的两个EBS副本之外，还需要通过网络发送到位于AZ2的副数据库
问题在于需要传输拷贝的数据量太大，造成性能低。 -
Aurora架构是怎么样的？
在替代EBS的位置，有6个数据的副本，位于3个AZ，每个AZ有两个副本。网络只传递log条目（和RDS不同）。
只要Quorum形成了，也就是任意4个副本确认写入了，数据库就可以继续执行操作。可以忽略最慢的两个服务器。
R+W>N -
Aurora如何做数据分片？如何做数据恢复？
使用protection Group
之后将数据做sharding
如果有修改，则查找对应的PG，之后只发送给对应的6个存储服务器
进行数据恢复时，找到对应的n个（每一个PG对应的块数）服务器，每一个服务器负责分配一个块的数据 -
Aurora 只读数据库了解吗？
只读数据库使用log日志更新，不会看到未commit的数据，会等到数据commit之后再应用。
只读数据库使用微事务和VDL/VCL 将log序列以原子性展示，不显示事务的中间状态 -
Frangipani是什么？它的架构是怎么样的？
Frangipani是一个分布式的文件系统，其文件内容、目录、inode、目录文件列表、块的空闲状态都存放在一个叫做Petal的共享虚拟磁盘服务中 -
Frangipani是如何解决缓存一致性问题的？
Fg中除了工作站和petal之外存在第三种服务器：锁服务器
锁服务器中有一个表单 locks 每一个锁以文件名命名
锁和缓存的规则包括：
工作站不允许持有缓存的数据，除非同时持有与数据相关的锁
只有将修改的数据写回petal之后，才能将锁归还给服务器
Frangipani的缓存一致性协议包括以下几种信息：
Request消息，用于获取锁 -
Frangipani的锁策略是怎么样的？
1.工作站不主动释放锁，而是通过服务器revoke申请释放锁
2.当工作站在创建文件时，锁的状态是busy，而当创建完成时，状态为idle
3.Fg有共享的读锁和排他的写锁，
务器revoke申请释放锁
2.当工作站在创建文件时，锁的状态是busy，而当创建完成时，状态为idle
3.Fg有共享的读锁和排他的写锁， -
fg如何做故障恢复?
预写式日志
在执行写操作之前，必须先追加log条目
只有当log条目完整存在于petal中的时候，才能执行写操作
log在每一个工作站中都存在一份，并且是半私有的，保存在petal中，工作站以环形的方式存储log，并且存储其递增的序列号
log会存储其块号，序列号和修改内容
可以只写入涉及修改的log，其余异步写入 -
什么叫事务的可序列化？
指的是并行的执行一些事务所获得的结果，与串行的顺序来执行这些事务得到的结果一致。
通过与其他尝试使用相同数据的并发事务进行隔离，就可以实现可序列化 -
※如何实现分布式事务？（两阶段提交的过程？）
两阶段提交
每个持有数据的服务器会维护一个锁的表单，用来记录锁被哪个事务所持有。所以对于事务，需要有事务ID（Transaction ID），简称为TID
ID在事务开始的时候，由事务协调器来分配。这样事务协调器会发出消息说：这个消息是事务95的。同时事务协调器会在本地记录事务95的状态，对事务的参与者（例如服务器S1，S2）打上事务ID的标记。
事务协调者会等待来自于每一个参与者的这些Yes/No投票。如果所有的参与者都回复Yes，那么事务可以提交，不会发生错误。之后事务协调者会发出一个Commit消息，给每一个事务的参与者，之后，事务参与者通常会回复ACK -
分布式事务如何做到故障恢复？
恢复yes之前崩溃可以重启并且重新接收事务协调者的请求
在prepare之前，需要将事务中间状态保存，记住所有要做的修改，记住事务所持有的锁，在磁盘上持久化
对于事务协调者，在commit之前，必须先将事务的信息写入到自己的log
commit或者abort是在一个单一的实例，也就是事务协调者中完成的，这保证构建了一个可靠的两阶段提交系统。
缺点在于有block的时间。
如果数据分片在多台服务器上并且需要在事务中支持多条数据，那么就必须支持两阶段提交 -
Spanner是什么？
Google的全球分布式可扩展多版本的负载均衡数据库，底层基于paxos算法
它支持wide-area事务
spanner的快照隔离基于同步时钟
读写事务基于两阶段提交和锁，只读数据使用快照隔离版本化 -
Spanner如何实现快速的只读事务的？
使用快照隔离（类似MVCC）
每个事务都会带上时间戳，只读事务将会带上时间戳请求数据 -
时间戳如何影响spanner只读事务的正确性？
如果时间戳太大了，那么事务将会等待更长时间
如果太小，则会影响外部一致性和正确性
使用类似ntp的技术可以处理分布式时间服务器所带来的时延
spanner使用间隔时间来放松对于时间精度的要求 -
请说明以下Farm如何实现百倍于spanner的性能的？
farm是一个高性能的nosql数据库
1.NVRAM（非易失的RAM）
2.RDMA 远程直接内存访问 访问网络接口卡而不中断（使用kernel bypass，应用可以直接访问mic网络接口卡而不经过内核）
3.可充电电源
4.kernel bypass
5.OCC 乐观并发控制 -
Farm的OCC过程？
分为Execute phase和Commit phase两个部分
第一个部分依靠one-side RDMA 在主节点中进行读取，每次读取5ms左右
第二个部分 是一个两阶段提交
1.由client发送字段的version和value日志到主节点 进行lock（日志起到锁的作用），主节点向客户端进行投票
投票基于version和是否已经锁定 primary使用原子操作对版本号和锁进行位检查
2.第一步成功后进行验证
3.第二步成功之后进行备份
4.提交事务
5.更新所有primary -
两个x+1的事务在OCC中同时执行，什么样的结果是可能的？（X=0）
0，1，2 -
什么是spark？它比map-reduce好在哪里？
mapreduce的扩展
1.map阶段被narrow替代，通过内存的stream读，避免了map阶段对于GFS数据的读取写入的时间
2.reduce阶段被wide转换替代，wide阶段之前的数据被spark按键分区，因此网络通信被避免了
RDD编程模型 -
分析以下pagerank.scala代码
val lines = spark.read.textFile("in").rdd
//map并转换tuple
val links1 = lines.map{ s =>
val parts = s.split("\\s+")
(parts(0), parts(1))
}
//去重
val links2 = links1.distinct()
//
val links3 = links2.groupByKey()
val links4 = links3.cache()
var ranks = links4.mapValues(v => 1.0)
for (i <- 1 to 10) {
val jj = links4.join(ranks)
val contribs = jj.values.flatMap{
case (urls, rank) =>
urls.map(url => (url, rank / urls.size))
}
ranks = contribs.reduceByKey(_ + _).mapValues(0.15 + 0.85 * _)
}
val output = ranks.collect()
output.foreach(tup => println(s"${tup._1} has rank: ${tup._2} ."))
Spark
架构
-
spark架构
计算引擎：
Driver 负责整个集群的作业任务调度
Executor 负责任务的实际执行
资源调度：（spark独立部署的环境）
master
worker
服务调度：
ApplicationMaster 负责在计算引擎和资源调度之间协调 -
Spark三大数据结构
RDD 弹性分布式数据集
累加器 分布式共享只写变量
广博变量 分布式共享只读变量 -
FileInputStream InputStreamReader和bufferedInputStream的区别在哪里？
fileInputStream、InputStreamReader和BufferedReader
经过装饰者模式被包装到一起 -
HadoopRDD的结构是怎么样的？
HadoopRDD负责读取文件内容
HadoopRDD继承MapPartitionsRDD
MapPartitionsRDD负责扁平化 以及 map
MapPartitionsRDD继承自ShuffledRDD
ShuffledRDD负责统计map结果
RDD中间数据不进行存储 -
RDD（弹性分布式数据集）的创建方式有几种？
- 内部创建：parallelize() makeRDD(数据，分区数量)
- 文件创建：textFile() wholeTextFile()(读取结果是一个元组，包括文件路径，文件内容)
-
spark如何持久化？
cache()
persist()可以指定存储级别
checkpoint() 检查点文件作业完成后不会被删除 会执行一遍work来持久化，需要和cache结合使用
持久化操作必须在持久化算子执行时执行
持久化会增加新的依赖，出现问题可以重新读取数据
checkpoint重新建立了新的血缘关系 -
spark如何自定义分区？
partitionBy（自定义分区继承Partitioner） -
为什么需要累加器 分布式共享只写变量
因为序列化传递给executor的是一个数据闭包没有返回
longAccumulator累加器一般放在行动算子中操作 -
自定义累加器
继承AccumulatorV2 -
广播变量
broadcast（变量名）
RDD算子
转换算子
RDD之间转换
map() 类型或值的映射转换 对于单个分区内执行是有序的，不同分区是无序的，对每一个分区的每一个数据每次运行一次
map后的元素数量不会改变
mapPartitions() 类型或值的映射转换 取出单个分区的所有数据之后，进行转换 存在对象的引用，不能用于内存较小的情况
可以增减元素个数，传递一个迭代器并且返回一个迭代器
mapPartitionsWithIndex() 对特定分区做操作，参数为迭代器以及分区数
flatMap() 对每个元素进行操作之后扁平化，进行操作之后的结果只要是可以迭代的集合即可
glom() 将同一分区的数据转换为内存进行处理
groupby()会将数据会被打乱重新组合，一个组的数据放在同一个分区中，称之为shuffle
filter() 数据过滤
sample
从数据源中抽取数据
参数(是否放回，每条数据可能被抽取的概率，种子)
distinct
去重
coalesce
用于缩减数据后，减少分区数量
第二个参数是shuffle，用于将分区数据打乱重新组合
repartition
扩大分区
相当于更大的coalesce+shuffle
mkstring 将集合转化为字符串
交集，并集，补集
拉链(产生两个数据的区间)
reducebykey
分组后，对kv两两聚合
存在shuffle，能够预聚合，性能较高
经过预聚合(shuffle之前在内存中聚合)，之后shuffle能够提高性能
groupbykey
只能分组，不能聚合
也存在shuffle，不能预聚合，性能较低
aggregatebykey
柯里化函数
用于界定分区内和分区间不同的数据
第一个参数列表:
当碰见第一个key的时候，和value做分区内计算
第二个参数列表:
第一个参数表示分区内计算规则，第二个参数表示分区间计算规则
foldbykey
柯里化函数
用于分区内和分区间相同时计算
combinebykey
三个参数，第一个用于类型转换
join leftjoin rightjoin
将相同key的value结合成tuple
不交的key去掉
多个相同，两两匹配
cogroup
先分组再连接
执行算子
collect()方法
reduce
collect
会将不同分区的数据按照分区顺序采集到driver内存中
count
数据源中数据的数量
first
数据源中数据的第一个
take
取n个数据
aggregate
定义分区内和分区间计算并且获取值
foreach
发送给executor端执行
注意此处有序列化的问题，要使用kryo进行轻量级序列化
rdd容错机制?
rdd记录算子操作的关系并且保存起来，用于数据容错和恢复
rdd依赖分类?
宽依赖(shuffle依赖)
窄依赖(onetoone依赖)
窄依赖时分区数=任务数
宽依赖时任务数=操作数*分区数
application
job:一个action算子就会生成一个job
stage:stage等于宽依赖(shuffle次数)的个数+1
task:一个stage中最后一个rdd分区的个数就是task
SparkSQL
-
SparkSQL
1.DataFrame
spark的DSL，封装了select set等操作
也可以直接写sql
可以和RDD相互转换
DataFrame是泛型的DataSet
2.DataSet
DataSet是DataFrame的ORM 可以和dataframe相互转换
3.以上三者之间可以相互转换 -
在涉及到DataFrame时，如果涉及到转换操作，需要引入转换规则
-
spark和hive的关系？
hive是sql化的map-reduce -
spark中UDAF函数的作用是什么？
在sql中自定义函数，还可以自定义强类型和弱类型的聚合函数 -
spark数据读取
默认格式是parquet -
spark和hive什么关系？spark on hive和hive on spark什么关系？
hive是hadoop提供的hdfs的sql计算
hive on spark模式下，数据以table形式存储在hive中，用户处理和分析数据使用的是hive语法规范的hql（hive sql）
提交计算时则会编译以spa
rk作业的形式来运行
spark on hive模式下，以spark来处理存储在hive中的数据
可以使用spark或者hive的api