分布式期末复习 | Chen0495的空间站

¶第一章 - 分布式计算概述

分布式计算、并行计算的概念
分布式计算指在☞分布式系统上运行的计算, 它是将一个大型计算任务分成很多部分分别交给其他的计算机处理, 并将所有的计算结果合并为原问题的一种计算方式.
并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算.
一个典型的分布式系统构成
分布式系统的特征
CAP理论

[{"url":"https://img.chen0495.top/img/20201223152128.png","alt":""},{"url":"https://img.chen0495.top/img/20201223152105.png","alt":""},{"url":"https://img.chen0495.top/img/20201225124623.png","alt":""}]

分布式计算的核心技术
进程间通信: (interprocess communication，IPC)，即在互相独立的进程（进程是程序的运行时表示）间通信及共同协作以完成某项任务的能力。
分布式存储系统分为哪两个层次
文件级和数据库系统
- ps: 存储还能咋存, 只有文件和数据库了
分布式计算系统
批处理分布式计算、流处理分布式计算、混合计算
🔗流式计算与批量计算有什么区别？🔗

¶第二章 - web框架实现

流行的web框架采用mvc 模式（模式-视图-控制器）
🔗MVC模式简介🔗
web框架的语言
常用的语言有PHP、java、perl、nods.js、go
- ps: PHP是世界上最好的语言
超文本传输协议HTTP
超文本传输协议（英语：HyperText Transfer Protocol，缩写：HTTP）是一种用于分布式、协作式和超媒体信息系统的应用层协议(TCP/IP Model)。HTTP是万维网的数据通信的基础。
HTTP请求消息结构

请求行（例如GET /images/logo.gif HTTP/1.1，表示从/images目录下请求logo.gif这个文件）
消息头（例如Accept-Language: en）
空行(一定要隔开)
实体内容(其他消息体)

HTTP请求方法(8种):

GET

获取一个URL指定的资源,即资源实体.

HEAD

获取一个指定资源的信息(元数据,即“关于该资源的信息”)

POST

向服务器提交数据

PUT

向服务器提交资源, 一般用于更新操作, 其与POST的区别在于: 多次调用同一 PUT 请求将始终产生相同的结果, 而重复调用 POST 请求具有多次创建同一资源的副作用.[^1]

DELETE

请求源服务器删除Request-URI标识的资源

TRACE

网络跟踪. 回显服务器收到的请求，主要用于测试或诊断。

OPTIONS

查询能力, 这个方法可使服务器传回该资源所支持的所有HTTP请求方法。用’*'来代替资源名称，向Web服务器发送OPTIONS请求，可以测试服务器功能是否正常运作。

CONNECT

与PROXY之间的连接管理

响应状态码用于表示服务器对请求的各种不同处理结果和状态，它是一个三位的十进制数。响应状态码可归为5种类别，使用最高位为1到5来进行分类，如下所示：
- 100~199
  - 信息，服务器收到请求，需要请求者继续执行操作
- 200~299
  - 成功，操作被成功接收并处理
- 300~399
  - 重定向，需要进一步的操作以完成请求。例如，请求的资源已经移动一个新地址。
- 400~499
  - 客户端错误，请求包含语法错误或无法完成请求
- 500~599
  - 服务器错误，服务器在处理请求的过程中发生了错误
- 例如:
  - 200（正常）: 表示一切正常，返回的是正常请求结果。
  - 206（部分内容）: 客户发送了一个带有Range头（要求服务器只返回文档中的部分内容）的GET请求，服务器按要求完成了这个请求。
  - 302/307（临时重定向）: 指出被请求的文档已被临时移动到别处，此文档的新的URL在Location响应头中给出。
  - 304（未修改）: 表示客户机缓存的版本是最新的，客户机应该继续使用它。
  - 401（未经授权）: 表示客户机访问的是一个受口令和密码保护的页面，结合使用一个WWW-Authenticate响应头提示客户机应重新发出一个带有Authorization头的请求消息。
  - 404（找不到） : 服务器上不存在客户机所请求的资源。
  - 500（内部服务器错误） : 服务器端的CGI、ASP、JSP等程序发生错误。
WEB会话是指web客户端与服务器的一次连接、中间多次交互到最后断开的过程。由于HTTP协议是无状态的，因此需要会话跟踪技术管理客户端的多次请求的状态信息。会话（Session）跟踪是Web程序中常用的技术，用来跟踪用户的整个会话。常用的会话跟踪技术是Cookie与Session
spring框架
控制反转概念、两种常见实现方式

控制反转:
- 概念: IOC(Inverse Of Control),即把创建对象的权力交给框架, 也就是指☞将对象的创建、对象的处理、对象的管理交给了spring容器. spring容器是spring中的一个核心模块, 用于管理对象.
- 实现方式: 依赖注入, 依赖查找.

¶第三章 - 反向代理与负载均衡

代理有两种, 分别是前向代理和反向代理
因为反向代理放置在web服务器之前，所以有下列作用
- 负载均衡:
- 服务加速:
- 请求鉴权:
常用的负载均衡技术有: DNS负载均衡、硬件负载均衡、软件负载均衡.
- ps: 负载均衡是针对服务器的, 为了缓解服务器压力就需要从3个方面入手, 硬件就是服务器配置好坏, 软件就是通过服务器上专门处理负载的软件来管理, DNS就是在请求到达服务器之前分流到其他服务器处理

¶第四章 - 分布式同步中间件

常见的分布式计算模型有:
消息传递、客户-服务器、p2p模型、消息系统、远程过程调用、分布式对象、网络服务、移动代理、云服务.
🔗五大分类九大范型🔗
比较消息传递模型和分布式对象模型

消息传递范型

消息传递范型是最基本的分布式计算范型，要求参与双方是紧耦合的，交互过程中，进程之间必须直接通信，如果进程之间的通信消息丢失（由于通信链路、系统或某个进程的失败），协作将失败；消息传递范型是面向数据的范型，适用于网络服务和简单网络应用，但是不适合包含大量混合请求和应答的复杂应用。

分布式对象范型

而分布式对象范型是在消息传递模型之上提供抽象的一种范型。与面向数据范型相比，分布式对象范型是面向行为的，它用分布式对象表示网络资源，注重于从网络资源请求服务，请求进程调用分布式对象的某个方法或操作，将数据作为方法参数传递。随后该方法在远程主机上执行，并将结果作为返回值回送给请求进程。

分布式一致性协议
分为基于状态机的复制协议和基于主副本的复制协议:
基于状态机的复制协议的算法有paxos、raft
基于主副本的复制协议的算法有zab、两阶段提交协议
paxos和raft算法原理[^2]

paxos:

Paxos将节点进程分成"发起者"“接收者”“学习者"三类, 论文称每个发起者发起的新的更新为"提议”,
每个提议包含一个数字n和提议内容,算法实现见上图.
首先考虑一种特殊情况，如果在最开始的阶段，所有接收者没有收到任何"提议"，这时发起者发出的提议它们是会直接接受的。
然而每次更新过程中，可能存在多个发起者发送提议，那么初始阶段可能各个接收者接受不同的提议，进而无法达成一致。这就要求一个接收者能够接受不止一个"提议"。这么一来就可能存在多个"提议"被"选择"(被大部分接收者接受)。既然会出现多个"提议"同时被选择的情况，最终如何达成一致呢？把条件设严格一点，如果后面被"选择"的"提议"内容都和第一个一致，那么无论有多少"提议"，最终不就相当于只有一个被选择了嘛！问题又来了，如何使得后面被选择的"提议"内容都和第一个一致呢？很简单，再把条件设严格一些，如果已经有"提议1"被选择，那么后续发起者发送的新"提议"的内容必须与"提议1"一致.

发起者：
    发送数字为n，内容为v的"提议"的预请求给所有接收者：
        从回应中挑出数字小于n且数字最大的"提议"，并将提议内容赋给v
        如果回应中没有"提议"，内容v由发起者指定
    发送数字为n，内容为v的"提议"的接收请求给所有接收者

接收者：
    接收到预请求：
        如果预请求的数字n小于已经接收过的预请求的数字n，continue
        回应发起者，表明自己不会再接收数字小于n的请求以及收到的数字小于n且数字最大的"提议"
    接收到接收请求：
        如果没有收到数字比n大的预请求:
            接受请求

举个栗子(希腊城邦选举):
腊城邦选举的例子，帮助我们理解Paxos算法。城中的一些位高权重的人们(“发起者”)会提出新的"法案"，这些法案需要立法委员(“接收者”)达成一致即多数同意才能通过。于是权贵们会预先给立法委员一些金钱，让他们通过自己的法案，这对应的就是"预请求"，如果立法委员已经收到过更高贿赂的"预请求"，他们会拒绝，否则会同意。权贵们贿赂成功后，会告诉立法委员新的法案，在收到新法案之前，如果立法委员没有收到更高的贿赂，他们会选择接受这个法案，否则会拒绝。很关键的一点是，不要忘了我们是一致性协议，不是真正的立法，因此很关键的一点是如果立法委员在接收到更高的贿赂时已经接受了某个法案，那他会告诉贿赂的权贵这个法案的内容，权贵会将自己发起的法案改成该法案的内容，这样才能够迅速达成一致性。

Raft:
Raft的算法逻辑主要可以分成两个部分，一个是选举部分，另一个是log传输部分。和Paxos部分不同的是，这里的log是连续并且按序传输的。Raft中定义了一个叫term概念，一个term实际上相当于一个时间片，如下图所示，这个时间片被分成两个部分，第一部分是选举部分，第二部分是传输部分。由此Raft的逻辑也可以分成选举和传输前后两个方面进行讲解。

算法逻辑:
在Raft中可以存在多个server，其中每一个server都有机会成为leader，但是真实有效的leader只有一个。于是这个leader的产生需要所有的server去进行竞争。在每个term开始的阶段，众多server需要进行竞选，选出一个有效的leader。每个server被设置了一个300-400ms之间随机的timeout，在如果在timeout内没有收到某一个leader发来的心跳信息，那么这个server就会发起竞选，将自己的term值加一，成为candidate，并寻求其他server的投票。当且仅当某一个candidate收到超过一半的server的票数时，它就成功当选了leader，并开始向每个server发送心跳信息。仅仅这么做其实是存在问题的，如果有多个candidate同时参与竞选，很可能出现选票分散的情况，最终无法选出有效的leader。因而除此之外，Raft还要求如果candidate收到term比自己大的投票请求时将自己的状态修改成follower，这么一来就成了谁的term增加得快的问题，因为timeout是随机的，总会出现更快的server，因此算法最终是收敛的

那么当选举成功后，整个集群进入log传输的状态。client会给leader发送需要传输的log，leader收到后在log上附加log的位置索引值和当前term值。这么一来每个log的索引与term值都是独一无二的。leader中会记录所有待传输给server的log索引值，针对于某个server，如果leader现存的索引数目大于待传输值，leader就会向该server传输新的logs。server收到logs后验证第一个log的term是否与自己同索引log的term一致，如果不一致告知leader匹配失败，leader会将传输的索引值减一，再重新传送。如果server验证后发现一致，则删除冲突索引后的所有log，并将新收到的log续借在该索引后面。

Paxos和Raft的对比:
Paxos算法和Raft算法有显而易见的相同点和不同点。二者的共同点在于，它们本质上都是单主的一致性算法，且都以不存在拜占庭将军问题作为前提条件。二者的不同点在于，Paxos算法相对于Raft，更加理论化，原理上理解比较抽象，仅仅提供了一套理论原型，这导致很多人在工业上实现Paxos时，不得已需要做很多针对性的优化和改进，但是改进完却发现算法整体和Paxos相去甚远，无法从原理上保证新算法的正确性，这一点是Paxos难以工程化的一个很大原因。相比之下Raft描述清晰，作者将算法原型的实现步骤完整地列在论文里，极大地方便了业界的工程师实现该算法，因而能够受到更广泛的应用。同时Paxos日志的传输过程中允许有空洞，而Raft传输的日志却一定是需要有连续性的，这个区别致使它们确认日志传输的过程产生差异。

一些大公司的分布式同步服务系统案列
谷歌的Chubby系统以paxos协议为基础
谷歌的zookeeper系统以ZAB协议为基础
百度的inexus系统以raft协议为基础

¶第五-八章 - 中间件

socket分类

什么是socket?

如图,可简单理解为进程之间负责通信(发送、接收数据)的一个类.

分为:
使用UDP传输的数据包socket(无连接)
使用TCP传输的流式socket(面向连接)

socket提供了两种通信方式
无连接和面向连接

怎么理解面向连接和无连接?
面向连接(TCP)要先建立起连接通道,然后通过通道传输数据.
无连接(UDP)只管往网络上传数据,不管对方是否收得到,大不了多发几次.
想象我和你两个客户端(比如QQ),我给你发了一段话苟利国家生死以,岂因祸福避趋之.,但这段话信息量有点大,必须逐个字地发,所以会出现下面两种情况:
面向连接:
我: 我要给你发段话
你: 发吧
我: ‘苟,这是第一个字’
你: 收到,发下一个
我: ‘利,这是第二个字’
你: Copy,next
我: ‘国,这是第三个字’
我: ‘国,这是第三个字’
我: ‘国’???
你: 洗澡去了,收到,下一个字
我: ‘家’
…
我: 完毕
你: 收到,完毕
无连接:
我: ‘苟利国家生死以,岂因祸福避趋之.’ – 这段话发给枪毙名单上的人
你: 收…(ping999)…到,‘国’,‘苟’,‘之’,‘因’,‘岂’.
你: 我收到了啥玩意?

软件开发通常采用三层结构
数据层、业务层、应用层
RPC和RMI
RPC（Remote Procedure Call Protocol）远程过程调用协议，通过网络从远程计算机上请求调用某种服务。

RMI:远程方法调用(Remote Method Invocation)。能够让在客户端Java虚拟机上的对象像调用本地对象一样调用服务端java 虚拟机中的对象上的方法。
- ps: RPC: 发送请求,远程服务期执行后返回结果.
- ps: RMI: 远程方法在本地虚拟机内有映射(虚拟方法)
面向连接通信和无连接通信的比较
无连接方式将以任意顺序到达，而有连接方式则以发送顺序按序到达
- ps: 见2
比较本地过程调用和远程过程调用
本地过程调用，主要是指本地进程间通信，是运行在同一块内存区域之内的进程间的互相通信，通常由系统IPC接口（如消息队列，信号量，共享存储等）来实现，也可以通过本地套接字方式实现。而远程过程调用，则是在本地过程调用的基础上实现远程进程之间的通信，一般由网络套接字来编程实现，远程过程调用会被物理网络的通信状况有所限制，也增加了安全问题，但是不再受本地内存空间以及系统资源的限制。
常用的数据库访问中间件两种形式
客户端程序库和数据库代理服务器
有名的数据库访问中间件
MYSQL代理、Cobar、TDDL、MyCAT
服务调用中间件
阿里的Dubbo、谷歌的gRPC、facebook的Thrift、新浪的Motan、百度的sofa-pbrpc、Navi-pbrpc
消息服务中间件
领英的kafka、阿里的RocketMQ、雅虎的Pulsar
跟踪服务中间件
谷歌的Dapper、阿里的EagleEye、twitter公司Zipkin、Naver公司的Pinpoint
客户-服务器通信代码
无连接:

面向连接:

¶第九章 - 分布式文件系统

大型分布式文件系统都是以GFS(Google文件系统, Google File System)为基础
gfs-sosp2003.pdf
分布式文件系统概念
分布式文件系统（Distributed File System，DFS）是指文件系统管理的物理存储资源不一定直接连接在本地节点上，而是通过计算机网络与节点（可简单的理解为一台计算机）相连；或是若干不同的逻辑磁盘分区或卷标组合在一起而形成的完整的有层次的文件系统。DFS为分布在网络上任意位置的资源提供一个逻辑上的树形文件系统结构，从而使用户访问分布在网络上的共享文件更加简便。单独的 DFS共享文件夹的作用是相对于通过网络上的其他共享文件夹的访问点。
- ps:就是文件分割保存在不同服务器,怎么字多怎么来
GFS是怎样保证数据一致性的
加粗是简记.
- 文件加锁: 对于文件(或目录)命名空间的修改(比如创建新文件), GFS 通过加锁保证其原子性.
- 文件增量相同: 每次写操作后, 文件(或目录)最后一个字节的偏移值在各个副本都是一样的.
- 文件位置相同: 每次写操作修改的文件(或目录)位置(即偏移量)都是一样的.
- 单块原子性: 单数据块的写操作保证其原子性,而且结果是确定的
- 一致性、唯一性和不定性: 一致性是指多个副本上都保存有相同的数据, 确定性是指无论几个多数据块写操作同时执行, 其结果是唯一(但不确定)的.
- 追加原子性: 追加操作保证其原子性(不能同时追加?),而且结果是确定的.
HDFS体系结构存在什么问题, 怎么解决?
单点故障问题

解决方案
HDFS 2.x 中增加了一个高可用性功能. 具体做法是:
- 在Hadoop 2.x 中有两个名称节点(NameNode), 其中一个是活动的, 另一个则待机
- 活动名称节点处理所有客户的请求
- 和Hadoop 1.x 一样, 待机名称节点管理元数据(元数据: 文件本身的相关信息,如文件大小)
- 当活动名称节点出现故障, 待机名称节点处理所有的客户请求
- 活动名称节点与待机名称节点的管理和切换通过 Zookeeper 实现
相当于美国总统和副总统的关系, 总统干活, 副总统干点小活, 总统挂了副的顶上, 总统和副总统的任命通过米国人民选举产生.

TFS (Taobao File System,淘宝分布式文件系统,主要针对海量小文件开发)的主要特点:
- TFS 将多个小图像文件存放在大的磁盘文件里(64MB),极大地减小了文件系统的元数据(以前记每个小文件的信息,现在只记这个大磁盘文件), 缩小了存储空间消耗. 每个块存储多份, 类似GFS/HDFS.
- TFS 集群由两个名称服务器(Name Server,一主一备),和多个数据服务器(Data Server)组成. 两个名称服务器的主备管理通过Linux的心跳机制实现.
- 名称服务器处理客户端请求, 管理元数据(如文件与块的对应关系)和数据服务器的加入、退出、心跳等.
- 数据服务器管理数据块.

¶第十一-十三章 - NoSQL数据库

NoSQL 数据库的共性
- 无模式: 与关系型数据库不同,NoSQL没有固定的模式(schema),这就为开发工作提供了很强的灵活性.(关系性数据库存储时必须事先定义’模式’,即要有哪些表格，表中有哪些列，每一列都存放何种类型的数据)
- 非关系型.
- 不支持SQL语言, 尤其不支持连接(join)操作.(都非关系了,怎么连接…)
- 分布式存储.(数据量大,一般采用分布式)
- 采用普通商用硬件,成本较低.
- Linux操作系统(成本考虑,原生linux不要钱,啊这…)
NoSql数据库的类型(根据数据模型划分)及其代表:
- 基于键值对的 - (例如谷歌的levelDB,其存储结构分为内存部分和磁盘部分)
- 基于列存储的 - (谷歌的Bigtable)
- 基于文档的 - (10gen的mongoDB)
- 基于图的 - (neo科技公司的neo4j)
- 基于时间序列的 - (InfluxDB)
与关系型数据库相比,谷歌的Bigtable有哪些优点?
- 属于同一张Bigtable表的内容可以分布在不同节点上.表分布式
- 属于同一个列族的列的数据类型是一样的列族下数据类型相同
- 保证单行数据修改原子性,多行不保证.因此没有了支持连接(join)操作的负担,其拓展性更强.单行原子性
- Bigtable本质是一个分布式的、稀疏的、巨型的哈希表, 其键是一个三元组(行、列、时间),其值是内容.

¶第十四章 - NewSQL数据库

🔗SQL、NoSQL，NewSQL对比🔗

ACID属性
ACID（Atomicity 原子性、Consistency 一致性、Isolation 隔离性、Durability 持久性）
NewSQL系统具有以下特点
- SQL作为和应用程序交互的主要方式
- 支持事务的 ACID 属性
- 使用非阻塞的并发锁(多为MVCC的变种), 这样读者不会与写着竞争
- 与传统的 RDBMS 相比,单节点的硬件配置要高很多(大内存,SSD硬盘)
- 水平扩展,无共享架构
NewSQL怎么做到同时满足一致性和可用性?
资料: 在没有网络分区的情况下可以同时支持一致性和可用性
当网络分区发生时, 选择禁止或允许一些可能导致产生一致性问题的操作, 但是在分区结束后提供冲突解决手段(例如对刚刚恢复的节点进行同步,或者一开始就禁止操作)

¶第十五章 - 云化

云化的技术基础
云化的基础是资源虚拟化,如主机、网络、存储.
其中主机的虚拟化技术有两种: 虚拟机技术,容器技术.
什么是云计算
通过连接运营商提供的云服务器等虚拟资源,在虚拟资源上完成计算得到结果.
云服务的服务类型
基础设施即服务(Iaas , Infrastructure as a Service)
平台即服务(Paas , Platform as a Service)
软件即服务(Saas , Software as a Service)
十多年前的玩意换个皮高大上而已…
Google云计算关键技术
三大核心: GFS, MapReduce, BigTable