两篇paper

paper : GFS

需要：
performance → sharding
faults → tolerance → replication → in consistency → low performance

一致性：
strong consisitency：

当有许多reqest时，按顺序处理

c1 wx = 1
c2 wx = 2
c3 rx = ?
c4 rx = ?

如果c1和c2同时写：
①c3和c4读的是1还是2
②c3和c4读的一样吗
③ 如果c1和c2同时向多个s写 （分布独有问题）

要一样。强一致。

GFS可以解决③

  • big | fast | global | automatic | recovery
  • single data centor | internal use | big sequence access | single master

几千个client，一个master

函数

master：
命名文件 & 查询chunk的位置信息

维护了一个chunk列表

（分开）里面有n个chunk，每个chunk有一两个disk

master里两张表：

  1. map：文件名→array of chunk handles（disk）
  2. map: handle → list of chunkserver（not disk）, version （disk）, primaary （not disk）, exptime（not disk）

这些info都在disk里存，写也在disk。

GFS管理方式：log，操作会在log后面追加记录，并建立checkpoint。所以每次写一条就会占一些地方。

and，时不时通过checkpoints将完整状态写入disk。重启时就回滚到最近的checkpoint。

read：

  1. client 发request （filename, offset）→ find pos （offset/(each check size = 64MB)）
  2. master 发 chunk handle，list of service
  3. （client save it in cache）client → service
  4. service -data→ client

write：必须对primary操作

？no primary：

master要 find newest data （包含了最新chunk副本的server set）

（master会分发version id）

matster从中选一个来作为primary chunk(with exp time)。version更新，写入chunk server

** 带过期时间的primary，防止一个primary挂掉，另一个上位，挂掉的重启会冲突

** 只有当master 指定一个新primray时，version才会变；只在primary挂时会发生

now has primary.

primary:接受client的write，send reqs → services

primary让许多2ed写，每个2ed返回yes，

if all 2ed返回yes：
    primary给client返回 succeed
else:
    return no → client 重新发起request

paper: Fault-Tolerant Virtual Machines

Failure：
可以解决fail-stop问题，不能解决bug问题

  • status transfer：状态转移
    将primary的副本发给backup
    ——> transfer的是memory的内容
    size big . 操作简单

  • replicated state machine：（size smal）<—— 单机方案
    ——> send client / 外部输入
    size small . 操作复杂

VMware：
通过LAN 复制content给P和B

log channel：
非确定性事件：non-det. events 通过log channel传递
（它只接受网络数据包形式的input/output）

input —— packets + ch通知已到达的中断信号

weird instruction：
有些指令在不同电脑上有不同结果

multi-core：
多核并行

output rule：
不向客户端承诺不确定的结果
不允许client端生成任何输出。

backup确认它已经接收到了此时所有的log record后才允许primary输出

如果P和B中断通信，但和client仍然连着，那么会产生脑裂：
——>用权威server决定谁 当P

server终止这个网络上的test-and-set服务，send test-and-set给P和B

p和B都必须获取这个test-and-set flag。

为了上线，他俩都向server发送t&s请求，第一个拿到的返回return flag→1

faults tolerance的方式：

  1. mapreduce：对计算进行复制，单点master控制计算
  2. GFS：通过primary-backup scheme复制文件中的实际内容
    单点master选择primary去操作每一块数据
  3. vmware：ft replicates在主备虚拟机上进行计算写入
    当出现问题时，依赖单点test-and-set server帮服务器选择其中一个备成为主

单点故障：
signle point of failure

投票：
server必须是奇数 要2f+1

raft：
以一个库的形式备包含在某些服务应用程序中。

key-value服务器：
* 3 replica

kv表:
raft layer：state：log about 操作
kv server会在raft中进行函数调用，反复通信保持state
state是存了一个关于操作的log

client：
通过有replica服务的多台服务器组成的整体进行通信

将请求发送个当前leader所在的应用层

client 发request给 kv server层，kv层把这个request发给raft层，让它提交至log，完成后return 完成

raft和每个副本通信，直到半数以上副本把这个操作添加入日志，然后return

给kv应用层
这时leader执行这个request，更新kv表
最终return给client

** paper讨论state时，是指对kv表进行操作

** 规则：follower的执行速度落后于leader给出消息的速度

一旦leader server意识到一个request被提交了（log state为已提交），它就要告诉其它副本这件事。so会有一条额外消息

  • leader状态变化时，就要给replica发消息更新
  • client无视replica（的时延），只关注leader。
  • 如果有n个client给server发消息，leader必须制定出某种顺序，确保所有副本都按顺序执行。
  • 在上图s3收到的第一个箭头处，此replica不确定这条操作提交执行了没，所以把log先放在一个备用的地方，直到第二个箭头来。
  • 日志的作用：
    • leader要把它的操作记在日志，（如果follower漏了要重发这条）
    • 如果一台server挂掉重启，会重写它的log

client发送请求后，kv server给raft层发

func start（command）（index， …）{
}

raft层处理好后给kv server 通过applyChannel发applyMsg，包括command，index等等

只有在start函数返回后，即master收到大于半数响应知道replica已经备份好请求了，该client请求对应的消息才会出现在channel中

  1. leader选举的工作方式
    why用leader：更高效
    follower不用知道leader的id，只要知道当前的term号
    每个term至多只有一个leader
    如何选举：
    每个raft server中会有一个election timer 选举计时器，用来记录时间。

    1. 如果一段时间内server没有收到当前leader的消息，它就假定leader挂掉了，并开始新选举。
      ** 网断了或leader很慢也有可能触发选举
    2. term号+1，follower变candidate，发送请求投票的rpc请求
      **一个新候选人总是给它自己投票，只能投一票
    3. 选举获胜的s需要立即向其他s发送AppendEntries
    4. AppendEntries then可以重置每个s的election timer，阻止新选举
      ** 也有可能一个都选不出，比如大部分s都挂了，比如同时有两个timer重置，然后都投了自己，导致没有人获得过半的票数
      —> 所以要【每次都】给timer设置随机的超时时间：random（min，max）
      min：exp time至少要和2此心跳间隔时间一样长。
      max：最大时间影响系统有多快能从故障中恢复，so取决于多高的性能 & 故障发生的频率
      —> 两个s超时的时间间隔gap，要够长完成一次选举，长于rpc请求到响应的时间。
      ** 如果旧leader在少数派网中，它不会影响client收到的讯息

  2. leader如何处理不同副本上的日志
    会产生各种crash的情况，导致log里的讯息各种各样