分布式系统复习

这啥玩意都没讲的课要考了。。。

1. 云计算与大数据

1.1 云计算的3个服务模型

IaaS，基础设施即服务

PaaS，平台即服务

SaaS，软件即服务

云计算的3中服务模型之间的关系：IaaS提供虚拟化的硬件资源，支撑PaaS对平台的虚拟化，而PaaS又支撑了SaaS对软件的虚拟化。

1.2 DIKW体系

Data（数据）、Information（信息）、Knowledge（知识）、Wisdom（智慧）

数据：对客观事物性质、状态等特点进行记录的可识别抽象物理符号；

信息：数据在传递过程中的形态；

知识：对数据进行挖掘，有价值的事物沉淀下来后形成的部分；

智慧：针对已有知识进行分析，获得的找出解决问题的能力。

1.3 数据思维

处理全部数据，关注相关性，而非因果性。

3. 分布式一致性算法

3.1 分区

垂直分区：按列分割

水平分区：按行分割，假设所有数据以键值对形式存储。

范围分区：根据key将数据分为若干连续范围

哈希分区：根据key的哈希值分区

一致性哈希：将所有哈希值排成一个环，将机器均匀放在上面，新来的哈希值找最近的机器，即将机器与哈希值解耦。

3.2 复制

单主复制：主从复制。

同步复制、异步复制、半同步复制：根据回复时有没有同步全部节点分类。

多主复制：多个节点处理写请求

无主复制：将写请求发给多个不固定的节点。

基于Quorum（法定人数）的数据冗余机制：用于决定究竟向几个节点发送请求。假设有3台机器，每次往里写2台，从2台读，考虑加入时间戳，总能读到最新数据。

在一个由N个节点组成的系统中，我们要求至少W个节点写入成功，并且需要同时从R个节点中读取数据，只要W+R>N且W>N/2，则读取的R个返回值中至少包含一个最新的值。

证明：W+R>N，读写有交集。第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候，它必须要获得V_w个冗余拷贝的许可。而剩下的数量是V-V_w 不够V_r，因此不能再有读请求过来了。同理，当读请求已经获得了V_r个冗余拷贝的许可时，写请求就无法获得许可了。第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。

W值越大R值越小，系统的读操作性能就越好。反之写操作的性能越好。

3.3 CAP定理

Consistency（一致性）、Availability（可用性）、Partition Tolerance（分区容错性）

CAP不能同时满足。

证明用反证法。

3.4 一致性

以下一致性由强到弱。

线性一致性：给定一个执行历史（若干读写操作），执行历史根据并发操作可以扩展为多个顺序历史，只要从中找到一个合法的（读写值对的上）顺序历史，那么该执行历史就是线性一致性。

注：执行历史是并行的，并不知道具体前后；顺序历史根据约束将其排成一条线。

约束：在将执行历史转变成顺序历史的过程中，如果两个操作是顺序关系，那么它们的先后关系必须保持相同；如果两个操作是并发关系，则它们可以按任何顺序排列。

顺序一致性：顺序一致性只要求同一个客户端（或进程）的操作在排序后保持先后顺序不变，但不同客户端（或进程）之间的先后顺序是可以任意改变的。即，两条时间线不必有全局时钟。

有时候顺序一致性更有用。例如，在一个社交网络应用中，一个人通常不关心他看到的所有朋友的帖子的顺序，但对于具体的某个朋友，仍然以正确的顺序显示该朋友发的贴子会更符合逻辑。

因果一致性：因果一致性要求，必须以相同的顺序看到因果相关的操作，而没有因果关系的并发操作可以被不同的进程以不同的顺序观察到。

最终一致性：最后能返回一个相同、最新的结果就很厉害了。

3.5 隔离级别

脏读幻读不可重复读略。

更新丢失：x=10; 　　A：x+=1;　　B：x+=2;　　res：x=11

读偏斜：假设数据的约束是X+Y=100，并发事务B一开始读到了X的值为50，同时事务A将X和Y的值分别修改为30和70，接着事务B读到Y的值为70。在事务B看来，X+Y=50+70，这显然违反了数据约束，这破坏了事务的一致性。

4. 分布式系统协调管理

4.1 原子提交

所有的操作要么都执行，要么都不执行。

--TBC--