西电分布式系统考试复习

分布式系统复习要点

by Fa1con_JS

考试形式

8-10道问答题，偏重理解，优缺点评判

分布式系统定义

（20年原题，老师强调）基本定义：各个通过网络互联的独立自治的计算节点组成，这些计算节点通过消息传递的机制进行相互协作，以完成共同的目标。在普通用户角度看来，计算节点内聚在一起，是一个整体，用户在使用系统功能时，往往无法察觉到分布式系统的内部构成和节点之间的协作关系！

基本概念：多个计算节点，网络互联（异构网络互联，可无线，可有线），独立自治，相互协作以完成共同目标，消息传递模型（并非内存共享结构模型！）

消息传递节点：出错之间是独立的，无共享架构（相互之间物理上不共享，通过计算机网络共享资源）设计分布式计算算法需要考虑容错（各节点独立自治，网络互联），时钟同步，通信代价（数据量控制，多计算，少交互，尽量避免频繁的通信，与共享结构区分开来），分布式计算和并行计算的关系（子集关系：并行计算包括有分布式计算，分布式计算是并行计算中的一种特殊关系），分布式计算和云计算的关系（严格上说云计算是在用户上看，给用户以一种云的感觉，分布式计算是实现云计算的一个核心技术，但是云计算可以有很多别的实现方式，比如。。。云计算是目标，分布式计算是手段）

构建分布式系统带来的收益

提高计算能力，提高存储能力，提高网络吞吐能力（并发访问能力），提高可靠性（解决局部节点失效问题），提高安全性（解决被局部攻击问题），提高可拓展性（解决瓶颈问题），实现资源共享，实现跨越时空的协同服务（发挥不同节点的优势）

（20年原题）Q.分布式系统的定义

A.见定义模块，这里不再赘述。

（20年原题）Q.同一个物理主机上是否可以包含多个分布式计算节点？为什么？

A:可以包含，因为可以进行虚拟化操作，一台物理设备抽象出多台虚拟设备，虚拟设备之间进行消息传递机制协作，即视为多个分布式计算节点，这些节点统称为分布式虚拟计算节点，也即虚拟节点。

（20年原题）Q.用多个计算节点构成分布式系统可以带来哪些好处？

A.主要包含以下好处：1.提高并发度，提高计算任务完成速率，因为节点变多，各个节点分到的计算任务得到平摊，各任务之间可以并行计算，同时也支持了更多用户同时访问的程度。2.提高容错性：单个节点或局部几个节点失效不会影响整体系统的完善性和正确性，用户只会感觉到系统处理速度变慢，可以通过更换计算设备来进行无缝纠错。3.提高系统可拓展性、开放性及安全性，部分节点被攻击，系统仍然可以正常工作。

(老师强调)用哪些特性衡量分布式系统的优劣

1. 业务层性能：时间复杂度，空间复杂度，通信复杂度（交互复杂度）（以下为分布式特有）
2. 可拓展性（水平可拓展性：用户增加，简单增加服务器就可以提升系统能力）（垂直可拓展性：加CPU，内存（单机系统升级）可以提升系统能力，如果单线程的设计程序，增加CPU核数不能提升系统能力）
3. 容错性：不能因为局部服务器失效就整体失效，网络接触不良，局部错误尽量不能影响整体系统的功能（可用性，可恢复性）
4. 并发性：单个节点可能要和多个其他端交互，多个客户端同时访问单个节点的问题
5. 透明性：在用户看来，分布式系统应该是一个整体的功能逻辑，用户不需要知道服务器的网络拓扑结构、服务器分布和数量及存储位置等。
6. 开放性：允许节点随时接入随时退出
7. 安全性：局部节点被黑客攻击，分布式系统仍可正常工作
8. 可观测性/可维护性：（可观测性）作为维护员，得知道哪一台服务器失效、负载情况等，所有服务器情况都可以被维护员管理到（可能通过一个可视化系统观测到），非常的清晰。（可维护性）替换特别方便，替换故障节点直接进行原地更换，无需通知他人，而且系统无需停机，用户感觉不到正在维护的过程

分布式系统的故障模型

1. 节点故障模型：失效停止，失效停止重启，拜占庭模型：节点失效后（可能被黑客攻击），仍然参与工作，可能发出错误的数据包，扰乱系统的正常工作。企业内部节点：设置故障模型只需为失效停止模型即可；任何系统（联网的）：容忍拜占庭模型
2. 信道故障：传输延迟的不确定性、网络断裂、丢包、数据包乱序（TCP不考虑该问题）
3. 时钟不同步：各个机器的时钟可能不太一样->时间戳（time-stamp）

设计分布式系统的挑战

容错能力，全局视角问题（节点染色方法，部分节点不知道自己在全局的地位，只能通过和相邻节点沟通解决冲突等）

分布式计算任务的分类

OLTP：在线（联机）事务处理系统（拿到任务请求后要迅速完成，高并发设计，实时性需求非常高）

OLAP：在线（联机）分析处理系统（允许延时长，不太强调并发性，方便数据分析）

准实时处理任务（流处理，介于OLAP和OLTP之间）：（比如商品推荐系统，时效性介于两者之间，不用太快，但也不能太慢）

（19年原题，一整道大题）分布式系统架构模式

• C-S模式：负载均衡技术（LB）：如何架构（反向代理），带来的收益（性能，可拓展性提高，容错性提高：某一台设备失效，只是性能会略微下降一点），常用负载均衡算法，要掌握每个负载策略的优劣势和具体的应用场景，例如轮询，随机负载均衡策略（优：编写简单，劣：随机负载会让缓存失效（随机访问），可能导致一些关键缓存被忽略（比如用户登录密码））不同层级实现负载均衡（Nginx：传输层负载均衡。网络层负载均衡（IP地址改变），数据链路层负载均衡（LVS，MAC地址改变），应用层负载均衡（目标程序改变等））
• 主从架构模式（若干从节点，一个主节点，一种C/S结构的模式）（HDFS，MapReduce，Spark等）优点：好设计，从节点宕机不会影响总体功能。由于从节点均服从主节点的调控，安全性较高。缺点：主节点容易成为瓶颈和失效关键节点，解决方式：设计主节点的备份节点
• 总线模式：消息队列，异步通信，无主通信
• 对等模式：运行的程序之类完全相同，又称对等互联网络技术，没有客户端或服务器的概念，只有平等的同级节点，同时对网络上的其他节点充当客户端和服务器。优点：去中心化（比特币的根本出发点），可扩展性强（用户可以随意加入随意离开），健壮稳定性，资源共享，优化传播速度，容错性高。缺点：无法确定用户传输内容的真实、无害性，可能容易受到部分用户的攻击而瘫痪失效，建立连接数太多，消息延迟大，以及消息的重复性消除问题？
• 混合模式（不算单独的，可以视为tradeoff）

（19年原题）常用的负载均衡策略及功能

• 随机
• 轮询
• 固定权重值（总权重和为1）
• （19年考具体原理）IP哈希（一致性哈希）（以上四种为静态负载均衡策略）
• 最少TCP连接数（以下三种是考虑实际负载的均衡策略）
• 最小响应时间
• 基于各服务器实际负载的动态负载均衡算法（CPU，内存，磁盘IO占用情况）

主要功能：实现高并发，高可用性，以及部分安全性，同时也有伸缩性（增加或减少服务器，给用户依旧以整体的感觉）

分布式中间件的概念

中间件在计算机体系结构中的位置（操作系统之上，传输层之下，所以被称为中间件）

中间件的作用

中间件的常见表现形式

分布式节点的通信技术

基于socket的通信技术

基于流式Socket（TCP，SOCKET_STREAM）

基于数据报Socket（UDP，SOCKET_DGRAM）

（19年原题）并发服务技术：多线程（阻塞式IO）（优缺点：编程简单，真正多核并行，创建销毁开销大，线程过多或任务过于繁重时，切换线程的开销很大，适合并发程度不高的情况），线程池(非阻塞式IO)（threadpool）（tradeoff），多路复用（select/poll，短事务高并发推荐！），异步IO，协程（轻量级线程），多进程，多服务器负载均衡，事件驱动（信号驱动）

远程过程调用RPC

RPC实现的基本工作原理：序列化、反序列化，插桩和代理（两端都有），实现RPC语义的应用层协议（出错控制，收发方式等），本质就是socket通信

（老师强调）RPC实现原理：

1. 先在客户端进行插桩（stub），设置远程过程的本地代理（proxy）
2. 然后服务器端也进行插桩，插桩的内容被称为skeleton，代替客户端调用本地方法
3. 客户端和服务器端通过socket在proxy和skeleton之间进行通信
4. 需要注意的是，skeleton模块相当于服务器端，需要早于客户端运行，并且在运行期间持续监听。

（19、20年原题）RPC技术的主要作用：让程序员专注于自己的业务逻辑，无需更换熟悉的编程语言。让被调用者无法区分调用者来自本地或者远程(透明性)。将面向过程的通用编程语言扩展到了分布式环境。实现了跨进程，跨语言，跨网络，跨平台的过程调用。强化了面向接口编程的编程风格。

（同注册中心）RPC中间件的作用：真正实现RPC基本工作原理中的几个功能，在服务端实现并发访问（多采用多线程技术），远程对象的通用标识和生命周期管理，过程服务进程（或远程对象）的集中注册于发现（目录服务），通信过程中的错误处理

（19年、20年均出现过）注册中心的作用（同RPC中间件）：解决了耦合度过紧，改名等的不方便，实现了一个目录服务，各server在实现好服务后，将服务名称注册到注册中心去，而client则在使用时先拿总的泛化方法名称去查询调用方法的名称，注册中心返回具体的方法名称，之后就可用开始使用。松耦合，只需client和server约定好一个宏观的服务名称就可，这样在server发生变化后，只需重新注册，client只需重新发现即可。同样也实现了负载均衡的作用（单一服务多服务节点，可以安排不同节点给client服务）（微服务特别多）注册中心必须保持稳定，有可能引入单点失效的问题（使用Paxos，Raft协议可以避免这种问题（奇数服务器数量），或者用ZAB等自定义的一致性协议）

（20年原题）接口定义语言（IDL）的作用：专门用来定义接口的语言，与具体编程语言分开，与业务逻辑无关，分离了对象的接口与其实现

RPC调用模式：同步调用模式（请求响应模式），异步调用模式

基于HTTP的通信技术

（仅19年考过，后续没有出现，并且老师上课也不再强调）Web Service/SOAP(序列化：XML)：

实现Web Service服务端的一般流程：

1. 用常用高级编程语言（例如Java）定义Web服务接口
2. 根据Java定义的Web服务接口生成WSDL（中间件自动任务）
3. 定义实现接口的Web服务实现类
4. 将Web服务实现类绑定到Web服务器
5. 将Web服务注册到UDDI中心

实现Web Service客户端的一般流程：

1. 从UDDI中心查找目标Web服务的接口定义（WSDL）
2. 根据WSDL生成Web服务代理类（WSDL to Java）
3. 利用Web服务代理类调用Web服务接口中定义的具体方法

Restful API（事实标准）（序列化：JSON）

基于消息队列中间件（MOM）的通信技术

(20年原题)利用消息中间件通信带来的收益：不再需要以阻塞方式等待接收方的消息，不用互相等待，接收者慢不会影响发送者的发送，反之亦然（存在中间件中缓存）；发送者和接收者之间耦合变松（发送者不用知道他的接收者是谁，特别是基于主题-订阅的中间件）；消除峰值流量带来的冲击（消息中间件缓存大量突发数据，然后慢慢进行消化，前端显示上显示“订单处理中”），降低耦合度，实现异步通信，提高容错性（缓存+容忍局部节点失效问题），提高可拓展性（增加，减少生成节点，对消费节点没有影响）

通信模式：消息队列模式：一对一（消息只有一个接收者），一对多（按负载均衡策略投递），主题-订阅

（20年原题）主题/订阅通信模式和消息队列通信模式的区别：前者支持想一个特定的消主题发布消息，该主题的同一批订阅者可以同时接收所以有关主题的消息，实现更为灵活的广播、组播等多对多通信模式。而消息队列只能支持一个消费者读取，一旦被取走就从队列中删除

（20年原题）消费者接收方式（三种）：轮询（查询方式，根据每次poll的时候消息队列中是否存在有消息，如果有，receive，如果没有，继续执行下步操作，问题：poll的频繁程度设置，过高：占CPU时间太长，性能低；过低：很多消息没有办法有效高速接收，容易造成消息的积累）、阻塞（如果没消息，在超时限定时间内一直处于等待）和回调接收（通知接收Notify）

（老师强调）三种投递模式：至多一次（可能丢），至少一次（可能重复发），投递一次且肯定成功一次（需要消息应答及后续处理）

两种缓存模式：持久化、非持久化模式

分布式存储技术

需要达成的目标

提高数据存储容量，提高数据吞吐量，提高可靠性，可用性，降低数据访问延时，提高分布式数据处理系统的运行效率

复制（多副本）技术

多副本复制带来的收益和挑战：收益：复制提供了冗余，可以在一定程度上解决局部数据节点失效的问题，多副本的存储也可以提高数据吞吐率、改善访问性能；挑战：硬件成本++，一致性问题的引入

主从复制技术：单主复制，多主复制，无主复制

（老师详细介绍）同步复制（要求应答不能丢失，单点失效问题，读数据可靠，一致性更容易实现），异步复制（写入速度快，有追随者挂了没有影响，但是读数据不可靠，一致性实现复杂）？（各自优缺点）

分布式一致性模型

快照（Snapshot）：完整保存的某个时间点的本地存储系统情况，该时间点之前的更新日志就可以删除了。

一致性模型的概念（从强到弱，tradeoff，一致性越强，分布式系统实现的代价就越高，性能就越低，操作程序更容易写；一致性越弱，分布式系统实现的代价就越低，操作程序越难写）几乎所有分布式存储系统都支持最终一致性。

强一致性（线性一致性）：用户看来和单点存储系统无差别等等等。(内外表现完全一致，所有操作在时间维度上的实际发生先后顺序完全一致，全局一致的顺序排列（线性化）)

最终一致性和其他弱一致性（顺序一致性，因果一致性等）

CAP定理：高可用性（Availability），网络断裂容忍性（Partition Tolerance），强一致性（Consistency）不可兼得，最多只能达到两个：CA（不允许出现割断容忍性）: RDBMS, CP:（不保证一定可用） Redis, MongoDB, BigTable, AP（不保证一定一致）: CouchDB

BASE理论：基本可用（Basically Availability）：运行部分可用性损失，只需保证核心可用，软状态（Soft State）：允许更新延时，最终一致性（Eventually Consistent）：不可能一直在软状态，在一定期限后要达到数据的最终一致，保持所有副本一致。

分布式共识协议

作用：多副本主从复制，异步通信，容错

复制状态机概念：主节点和备份节点的状态完全一致，以备主节点失效可用迅速转换

两者关系：共识协议：手段，分布式一致性：原理

按容错模式分类：失效停止模式共识协议：Paxos，Raft，ZAB（ZooKeeper），拜占庭模式共识协议：比特币共识协议，PBFT

了解常用的共识协议：Paxos（最多容忍小于n/2个节点失效例如有7个节点，最多容忍3个节点，不允许出现偶数节点，这样会出现浪费，比如8个节点，也只能容忍3个节点）、Raft（两轮广播，半数确认即认为传递成功，leader失效后，经过半数以上的节点投票后，可以确定出新的leader（通过日志长度、新旧程度区分进行投票））、PBFT（实用拜占庭容错模型（Practical Byzantine Fault Tolerance）只能容忍小于n/3个节点的失效）

分区（切片）技术

分区带来的收益：提高吞吐率，提高可靠性，方便实现数据的并行处理

分区的问题：跨区查询，动态分区，负载均衡，分布式事务处理。（偏斜skew，热点hot spot高负载问题）

（和之前LB部分相关联）常用的分区方法：主键范围分区（优：连续查询方便，缺：全局索引维护，单点失效问题）：均匀分区（优缺点），非均匀分区（优缺点）；哈希分区：简单哈希分区（优：简单。缺：新增服务器时数据移动大），一致性哈希（避免大规模数据移动等。。。）。哈希分区的优缺点：优：单点查询效率高，缺：无法带来索引（只要一位数据不同，区域可能完全不在一个区域内），范围查询效率非常低

分区带来的挑战——分布式事务：概念（ACID，类似数据库的），实现分布式事务的方法：2PC（二阶段），3PC（三阶段），TCC，XA，SAGA

分区和复制组合使用

（19、20年原题）经典案例：HDFS分布式文件系统：系统架构，工作原理（读写流程，数据复制实现方法等）>

HDFS通过什么技术提高数据存储的可靠性？

冗余（数据多副本方案）+块扫描+快照机制

NameNode功能：

是整个文件系统的管理节点，维护着整个文件系统的文件目录树，文件/目录的元信息和每个文件对应的数据块/存储该数据块的物理节点IP列表，接收用户的操作请求

DataNode功能：

存储client发来的数据块block，执行数据块的读写操作，在物理层面上支持多备份的底层策略

读取，写入HDFS文件时NameNode和DataNode的交互过程：

读取：

1. 客户端先联系NameNode，传入需要查找的文件的各种参数（比如文件名，偏移等。。。），
2. 接着NameNode查找其存储的两张表（文件名-数据块，数据块-物理节点表），根据目标数据块的各种参数返回一系列包含目标数据块的DataNode的IP地址给客户端，
3. 最后客户端根据最近最佳的IP地址选择DataNode，与其建立Socket连接去进行访问即可。

写入：

1. 客户端先联系NameNode新建文件的请求，然后NameNode根据负载均衡策略去选择三个DataNode的IP地址返回给客户端
2. 然后客户端按照流水线的传输模式将第一个数据块的内容写入流水线
3. 三个DataNode都写完第一个数据块内容后，客户端再向NameNode申请下一个数据块对应的三个DataNode。以此循环直至写完所有需要写入的数据块。

（必出大题，共两道）分布式计算模型

MapReduce： map阶段，shuffle阶段，reduce阶段。利用MapReduce程序实现简单的数据统计分析（编程题），写出各阶段的工作需求即可，可用用伪代码，也可以用自然语言，如何容错？（不停监视从节点的状态，如果很长时间一个从节点没有计算出结果，主节点认为从节点失效，转交该计算子任务给其他从节点进行）

具体代码框架如下：

Mapper:

publicstaticclassMyMapperextendsMapper<Object,Text,Text,MyOwnWritable>{protectedvoidmap(Object key,Text value,Context context)throwsIOException,InterruptedException{String splited = value.toString();//get each lineString[] data = splited.split(",");//use your own split method like "name,score,grade"/*
        use your own mapper method.
        note that you may need to parse when using int or double type
        a solution is like: double xxx = Double.parseDouble(data[?]);
        if using String comparison like equal, use data[?].equals("your own rule")
        */
        context.write(newText(data[?]),newMyOwnWritable(?));//serialization}}

Reducer:

publicstaticclassMyReducerextendsReducer<Text,MyOwnWritable,Text,FinalWritable>{protectedvoidreduce(Text key,Iterable<MyOwnWritable> values,Context context)throwsIOException,InterruptedException{// demo computing the average score of studentsdouble sum =0, count =0;for(MyOwnWritable value : values){
            sum += values.get();//get int/double or String values using get() method
            count +=1.0;}/*
        other your own reduce methods can be applied here
        */double avg = sum / count;
        context.write(newText(key),newFinalWritable(avg));}}

Combiner:不做要求

Spark：主要思想：RDD（弹性数据集，尽量缓存到内存中），DAG任务调度。常用的算子（filter,count,top, mapValue, reduceByValue等，见ppt）。Spark计算框架的主要作用：如何容错，架构模式（主从），利用Spark程序实现简单的数据统计分析（编程题），写出各阶段的工作需求即可，可用用伪代码，也可以用自然语言

具体代码框架如下：

defget_map(x):# use your own split rule
    s = x.split(",")# return which dimension?
    num1 =1
    num2 =3return(s[num1], s[num2])

sc = SparkContext(conf=SparkConf().setMaster("?").setAppName("yourfile"))
textData = sc.textFile("xxx.txt")# filter the data : filter(lambda line : "?" in line) # NOTE: "?" means your own filter rule
filtereddata = textData.filter(lambda x :"your rule"in x)# increase dimension of the values : mapValues(lambda origin_val : increase_valdim(origin_val)) # reduce by key using your own rules : reduceByKey(lambda origin kv1, origin kv2 : get_reduce(kv1, kv2))# mapping using your own rules : map(lambda origin key : get_map(key))# NOTE all functions in lambda's are implemented by yourself or using another lambda function
mappeddata = filtereddata.map(lambda x : get_map(x)).mapValues(lambda x:(x,1)).reduceByKey(lambda x, y :(x[0]+ y[0]),(x[1]+ y[1])).mapValues(lambda x :int(x[0]/x[1]))
mappeddata.saveAsTextFile("output.txt")

复习部分到此结束，祝考试顺利！

后记

今年考试内容总体和提纲接近，但是题目也有一定变化，比如如下几个问题：
Q.适合分布式系统的排序算法是什么算法？
Q.在服务器存在缓存的情况下，最适合采用的负载均衡策略是哪个？最不适合采用的负载均衡策略是哪个？
Q.除了消息队列外，还有哪些分布式通信的方式，请至少列举出两种。
… …
同时需要注意的是，spark和MapReduce的考题每年是有变化的，不能只按部就班的看往年题，要有自己的程序理解，以及对计算算子的掌握。
总的来说，分布式系统这门课确实学到了不少实用的知识，李老师人也很好，在群里一直热心回答同学的问题，不过碍于课时所限，很多内容还是需要自学，比如一些故障处理模型（PBFT等）的原理，同时在之后的实际应用中也需要理解分布式计算的真正内涵，毕竟现在很多时候ubiquitous computing是非常常见的。愿前程似锦！
（p.s. 如果可能的话，最好还是把老师给的ppt和视频认真消化一遍，这样效果更好！）