Mit 6.824 (三）_6.824项目面试

分布式系统笔记（三）

lecture 7 Fault Tolerence Raft

Raft的一些规则：
应该接受应该使用日志时间最长的服务器作为领导者；
提出一个问题：why not longest log as leader?

选举限制 election restriction
对某些候选人发送赞成票，仅在候选人具有更高的任期在上一个日志条目中或相同的上一个术语相同的上一个日志条目，并且日志条目大于等于接收到的服务器请求

日志备份加速策略
如果追随者follower拒绝追加条目，则条目会回复
持久性 persistence —易失性non-volatile storage
持久性的含义是：如果您更改其中一项，你应该将其标记为持久性，并将其写入服务器或磁盘中等其他非易失性存储。这将确保如果服务器重新启动，它将能够找到这些信息并将其重新加载到内存中，这使得我们允许服务器在发生崩溃时就能从中断处继续取回。

一个常见的故障模式是整个集群的电源故障，当发生电源故障后，我们希望在恢复电源后我们的整个集群可以恢复到断电前的状态，要求重新启动服务器所需的状态，这是观察持久性情况的一种方式。

保留日志的原因是：这是应用程序状态的唯一记录。
the cose of synchronous 同步成本

人们除了保持同步，另一个经常使用的技巧是尝试批量处理；

提出问题：为什么提交索引会持续应用到下一个索引并匹配索引

---

日志压缩和快照 log compaction and snapshots
日志中的某些点的状态是可以互换的
日志中有很多空间，但也可以将其压缩为一个表中的条目
因此我们添加了raft是否要求应用程序提供的快照引用

线性化能力 linearize ability
执行历史记录（一个序列）是可线性化的
读取在写入之后进行

---

lecture 8 Zookeeper

Zookeeper: 分布式应用程序协调服务软件，以Fast Paxos算法为基础；
ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby一个开源的实现，是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件，提供的功能包括：配置维护、域名服务、分布式同步、组服务等。
ZooKeeper的目标就是封装好复杂易出错的关键服务，将简单易用的接口和性能高效、功能稳定的系统提供给用户。
ZooKeeper包含一个简单的原语集，提供Java和C的接口。
ZooKeeper代码版本中，提供了分布式独享锁、选举、队列的接口

---

可线性化 linearizable
谈论的是写入和读取 数据的顺序
规则：只有一个总的操作顺序，不允许不同的客户看到；
服务器检测重复数据的机制：重新发送服务器最初发送的上一个答案和问题

1、API的外观问题，不确定名称
2、Performance 性能

Zookeeper有两个线性化的保证guarantees：
1、linearizable rights 权限线性化。Zookeeper不是严格的读写
2、FIFO 客户端顺序
读取的含义：如果客户端以某种顺序再次发出读取序列。客户会依次读取事件，先第一件事，再第二件事，再第三件事…这些读取发生在日志中的某个特定点，读取的过程中要注意观察这些点的位置

命令读取的内容只能按时间前进或仅按时间前进；
权限是读取和写入FIFO客户端命令适用于所有客户端
在读取信息的过程中，某些副本的某些内容必须等到是 leader 才可以进行读操作；因此导致Zookeeper的工作方式不保证我我们看到最新的数据

我们需要做的是让客户端请求按顺序获取数据

主服务器要首先更新配置文件，它所要做的是删除准备好的文件，然后将各种文件写入到Zookeeper并保存配置数据的文件，当更新为完全组成该配置文件的时候，再次创建就绪文件；
每个客户端请求都必须适合日志中的某个位置，我们在日志中设置了watch，并且保证会收到如果有人删除了该文件并且我们可以通知（触发通知）的话，通知将在读取之前在客户端出现，日志中随后的所有内容都会在我们获得

---

lecture 9 More Replication CRAQ

重点讨论的内容：不太好的关于Zookeeper的关于其API（应用程序接口）的设计
Zookeeper要成为一个真正的分布式服务系统需要执行的重要任务

Zookeeper的接口可以确保每个副本与所有副本一次又一次的处理权限流、以相同的顺序执行权限、以便副本在其中进行排序；
Zookeepe实际上为我们提供了编写容错测试和设置的工具；

Z节点
Zookeeper公开的RPC接口的操作是排序的，我们希望对文件进行的操作是在其中创建RPC的地方创建RPC名称，确实是一个完整的路径名称、一些初识数据和一些组合

放置键值对
选举是适应未知数的合理策略
可以通过删除文件来释放锁；
读取发生在权限之间的确定点上；

命名系统：
第一步：创建一个顺序文件
（文件死亡后，会自动删除其临时文件）
一般都会选择检查所有的内容，防止意外的事情发生
线程系统的不同上下文和可伸缩锁
线程的随机死亡 ，每个人都会正确使用互斥锁，我们将获得原子序列的原子性；持有锁和释放锁

系统链

针对网络分区，如果没有针对拆分的防御措施，意味着它在实践中是无法使用的；
配置管理器：工作是监视程序的活跃性
链复制 chain replication ；
客户端发出的请求都会收到最慢的服务器的限制 ；

---

lecture 10 Cloud Replicated DB Aurora

获得高性能可靠的数据库作为云基础架构的一部分
我们还可以使用通用存储来提高性能和容错能力；
Elastic cloud 弹性云
通常网站是由一组无状态的网络服务器组成的，当它们需要获得数据时，开始与后端数据库进行对话
EBS 弹性块存储

事务和崩溃恢复
数据库通常具有页面缓存
每一个新加的日志存储都必须附加到存储中
数据库服务器需要执行仲裁输入
亚马逊将数据库分为六个单元，每10G的数据需要20G的数据库来存储；

---

lecture 11 Cache（缓存） Consistency（一致性） Frangipani

分布式事务和分布式崩溃恢复
分布式系统本质上是由一堆服务器拆分而成
虚拟磁盘
共享文件系统
右向缓存
用初始化的方式分配了索引节点
文件的所有逻辑和技术都必须坐落在我们自己的工作站及设计中；
在添加用户时将工作站添加到系统，会自动获得更多的CPU容量来运行这些新用户文件，因为大多数文件系统操作仅发生在本地缓存中。
系统在每次添加工作站时，都具有一定程度的自然扩展可伸缩性；

一致性问题我们会遇到的问题是：
文件和目录是共享的，我们会遇到两种情况
1、不同的工作站同时在修改同一目录；

crash 崩溃 crash recovery 崩溃恢复

---

一些挑战：
1、cache coherence 缓存一致性

实际上，缓存一致性是由其使用的锁驱动的，实际上是锁和崩溃恢复
但是我们接下来讨论的是使用块Block来驱动缓存一致性，来保证工作站缓存的是最新的数据；

锁定服务器：逻辑上至少是一台单独的计算机，其中每个文件都有一个锁（互斥锁）
首先锁定服务器，然后获取需要的数据，在完成系统调用后释放锁
没有锁就没有缓存数据，不加锁就不要缓存数据；
释放锁之前，缓存中的数据必须写回数据；
从工作站到锁服务器的单向网络消息；
无法在正确写入数据的同时读取过时的数据；

2、如何实现原子性：操作原子化
原子性：指事务的不可分割性，一个事务的所有操作要么全部被执行，要么一个也不执行；
对共享内存中的数据进行操作的过程中，必须保证整个过程中都持有锁；
使用锁的目的是防止同一时刻有两个以上的客户端对同一块数据进行访问，导致读取的数据不一致；
通过使用锁可以保证缓存一致性；

3、崩溃恢复 crash recovery
处理崩溃的方式之一是不释放处理崩溃的锁，让需要这些崩溃的文件的人一直等待；
循环的日志条目
日志实际上是一个序列，要将日志写入到锁所覆盖的数据；
工作站在崩溃恢复后会重放日志；不能盲目的重播日志条目；
文件系统操作不会降低现有工作站的速度；

---

lecture 12 Distributed Transactions 分布式交易

并发控制 （传统的数据库问题）
系统会试图隐藏将数据拆分为多个数据的复杂性，服务器尝试向应用程序的程序员隐藏它；
原子提交在抽象上称为交易；
一般有两个交易，
第一个称为T1 是程序员应该标记的传输标记；这种交易以Begin交易开始，然后对两个记录中的两个余额进行操作，对余额进行增加减少的操作；
第二个称为T2 这次交易也得标记起点和终点，但是这次我们只是在阅读，只读交易，我们需要获取所有账户的当前余额，不做任何操作；

事务的ACID属性；
A 原子性：一个事务中的所有操作，要么全部执行，要么全部不执行；
C 一致性 ：事务执行前后的完整性必须保持一致；
I 隔离性：多个用户并发访问数据库时，数据库为每一个用户开启的事务，不能被其他事务的操作数据作干扰，多个并发事务之间相互隔离；
D 持久性 一个事务一旦被提交，它对数据库中数据的改变是永久的

serializeable:可序列化指的是结果可序列化

分片系统：并行的分离数据
在事务的中间出现错误，通常称为中止 Abort；
并发控制：concurrency control

实现并发控制的两种方式：

1、悲观主义者，通常是锁定
一个锁定系统，可以阻止用户以影响其他用户的方式修改数据。如果用户执行的操作导致应用了某个锁，只有这个锁的所有者释放该锁，其他用户才能执行与该锁冲突的操作。这种方法之所以称为悲观并发控制，是因为它主要用于数据争用激烈的环境中，以及发生并发冲突时用锁保护数据的成本低于回滚事务的成本的环境中。
优缺点：对数据进行加锁可以保证对数据的访问不会出现冲突，保证了数据的正确性；但是频繁的写锁释放锁会造成损耗，性能下降；

2、乐观主义者
在乐观并发控制中，用户读取数据时不锁定数据。当一个用户更新数据时，系统将进行检查，查看该用户读取数据后其他用户是否又更改了该数据。如果其他用户更新了数据，将产生一个错误。一般情况下，收到错误信息的用户将回滚事务并重新开始。这种方法之所以称为乐观并发控制，是由于它主要在以下环境中使用：数据争用不大且偶尔回滚事务的成本低于读取数据时锁定数据的成本。
优缺点：不频繁的写锁释放锁会节省内存损耗，可以提高一定程度的操作性能，但是在高并发的情况下，会造成大量的请求冲突，冲突会导致大多数操作无法实现而浪费资源，因此在高并发的情况下，建议使用悲观主义策略；
（粒度：粒度就是同一维度下，数据统计的粗细程度，计算机领域中粒度指系统内存扩展增量的最小值。粒度问题是设计数据仓库的一个最重要方面。粒度是指数据仓库的数据单位中保存数据的细化或综合程度的级别。细化程度越高，粒度级就越小；相反，细化程度越低，粒度级就越大。数据的粒度一直是一个设计问题。）

主题是如何建立分布式事务
在分布式系统中，会有一台机器负责统筹协调各机器的工作；

参与者也将是我们Raft复制集群中的代表集群；
来回交换信息链；
分片数据库；