Return to site

MIT’s 6.824 Distributed Systems && Project info

10 lectures and 3 labs.

The first three labs were all the same, but the fourth lab (persistence and failure recovery) is already built into Raft.

Week 1 notes

从去年年12⽉月份开始做 6.824 2015,⼤大概看了了10个lecture,做了了3个lab,顺便便学了了下go语 ⾔言,⼤大概达到能够熟练写代码的程度吧。

上周末仔细对⽐比了了2016和2015的内容,发现2016 Paper新很多,决定从2016重新看起。之 前看2015的时候经常⼀一个周末只能做⼀一个lab或是读⼀一篇⽐比较⻓长的论⽂文,这次决定完全跟着 课程进度,⼤大概15周搞定这⻔门课程。

Week 1共三部分:

1. MapReduce论⽂文,顺带看了了2015 lecture 13的内容;

2. labrpc,课程为了了学习rpc⾃自⾏行行开发的⼀一个简单的rpc库,⽤用channel模拟了了network, endpoint,server,dispatch等内容,同时需要区分 at-least-once和at-most-once的区别。 看这个前,终于把effective-go看完了了;labrpc还有⼀一个⽬目的,即注⼊入故障(⽹网络重传、延 时、丢包等),⽤用在后边的lab⾥里里的test case⾥里里。这⾥里里对于学习分布式系统如何测试也有⼀一 定的借鉴意义。

3. Lab 1,实现⼀一个单机版本的MapReduce lab。做完后,加上test,⼀一共1050+⾏行行代码,⾮非 常简单。实验主要是 1) 写了了两个map reduce task (词频统计和倒排索引); 2) 实现doMap/ doReduce两个函数,⽤用于输⼊入输出,⽤用json作为数据交换的格式; 3)实现schedule,分 别实现⽆无错误和容错两个版本的distributed⽅方法。 总体来说,⽐比2016的同⼀一个lab内容要丰富⼀一些。

单机版本的MapReduce扩充到分布式环境,尚需要有⼀一个任务调度系统(类似borg), ⼀一个⽹网络⽂文件系统(GFS);

2016和2015 lab上的主要区别是,⽤用实现raft(raft lab -> kv based on raft -> shared kv based on raft)替代了了实现了了paxos,甚⾄至连paxos的lecture也从schedule中删掉了了。 raft在 出现后短短⼏几年年就进⼊入了了顶级名校的分布式系统课程(在lab中出现是个巨⼤大的进步),隐 隐觉得其会成为后续解决分布式系统⼀一致性问题的主流协议。

下周: 1. GFS 2 Primary-Backup Replication 3 做些lab 2 raft的前期⼯工作。 Week 2 notes

GFS

1. 设计⽬目标

1) 同传统的分布式⽂文件系统的: 性能、可扩展性、可靠性以及可⽤用性

2) 新的挑战:

a)组件失败是常⻅见的,⽽而⾮非exception 可能的原因:app bug\operation system bug\human error\the failure of disks\memory\connectors\networking\pow supplies 因⽽而需要常态化的监控、错误检测、容错、⾃自动恢复。

b)按照传统标准看,⽂文件巨⼤大,因⽽而需要revisit很多设计假设以及相关参数,⽐比如I/O操 作、block size、不不针对⼩小⽂文件做优化等;

c)⼤大部分是追加操作,⽽而⾮非overwrite。⼀一个⽂文件内部的随机写⼏几乎不不存在,⼀一旦写了了,⽂文 件变成只读,经常是顺序读。因⽽而需要,追加操作是主要的性能优化点,并提供原⼦子性保 证,在客户端缓存数据没有什什么吸引⼒力力;

d)同时设计应⽤用和⽂文件系统的API,增⼤大了了我们的灵活性,GFS提供的是放松的⼀一致性模 型。 atomic append,多个客户端可以并发的追加同⼀一个⽂文件,⽽而⽆无需外部的同步。 客户端数和服务器器数在同⼀一个数量量级上,并⾮非“⾼高并发”;

2. 基本假设:既有机会⼜又有挑战

1)2)4)略略。

3)⼯工作负载:两种读操作,⼤大的流式读以及⼩小的随机读,性能敏敏感的应⽤用经常batch and sort their small reads。

5)⽂文件经常⽤用于⽣生产者消费者队列列或者⽤用于多路路归并;

6)⾯面向⾼高带块,⽽而⾮非低延迟;

3. Interface 按照⽬目录、层级组织⽂文件,提供create\delete\open\close\read\write\snapshot,以很低的 代价创建⽂文件或者⽬目录的拷⻉贝。record append

4. Architecture

1)单master,多chuck server,多clients

2)⽂文件被划分为固定⼤大⼩小的chunk,通过⼀一个不不可修改、全局唯⼀一的64 bit chunk handle标 识,master在创建chunk时分配该标识。

3)chunk server在本地磁盘上作为linux⽂文件存储chunk。读写chunk数据通过制定chunk handle和byte range,每个chunk在多个chunk server上复制。

4)master存储所有⽂文件系统的元数据:命名空间、访问控制信息、⽂文件到chunk的映射、 chunk的当前位置; 提供chunk租约管理理、孤⼉儿chunk的垃圾回收、chunk迁移等功能;

5) Heart Beat,指令和状态汇报;

6) GFS提供client lib;

7) client和chunk server均不不缓存数据(client会缓存元数据),chuck server直接利利⽤用linux buffer cache。 客户端向最近的chunk server请求数据,通过batch、缓存、预读进⼀一步减少 client和master之间的交互;

5. chunk size 64M,使⽤用lazy space allocations解决内部碎⽚片的问题。 带来的好处:

a) 减少client\master交互

b) 通过保持TCP⻓长连接减少⽹网络负载

c) 允许master将所有元信息保存在内存之中 带来的问题:⼀一个⼩小⽂文件包含的chunk很少,可能会成为热点;

6. meta data 三类元数据: a) file chunk namespace b) ⽂文件到chunk的映射 c)每个chunk replica的位置 信息 a、b通过log持久化并同步给备master c通过master启动时或chunk server加⼊入集群时询问每个chunk server 各个chunk所在的位置 chunk location不不持久化的好处,避免master和chunk server之间同步这些信息的问题。

7. operation log 不不仅⽤用于持久化还⽤用于操作定序,本地和远程均持久化后才会应答客户端。间隔的做 checkpoint,checkpoint实现上是个压缩的b-tree,可以⽤用于快速恢复。

8. ⼀一致性模型 GFS提供⼀一个放松的⼀一致性模型

1) GFS提供的保证:⽂文件命名空间的修改(⽂文件创建等)是原⼦子的

2)关于consistent\defined\undefined but consistent\inconsistent(必然意味着undefine)

3)由应⽤用负责区分defined区域和undefined的区域

4)write操作,由应⽤用指定offset; record append操作,atomically at least once,由GFS选定 修改位置;追加写操作会将 offset返回给客户端,这个offset作为保持这个record的⼀一个 defined region的开头,GFS可能会在这中间插⼊入padding或重复的记录;在⼀一系列列成功的修 改后,系统状态为defined并且包含最后的成功写;

5)在所有副本按照同样的顺序apply修改操作;

6)通过chunk version检测stale chunk,client由于meta cache可能⽆无法⽴立即区分stale replica,但也没有关系;

7)checksum

8)如果发现有chunk replica损坏,会尽快拷⻉贝⼀一个新的replica; 9. ⼀一致性模型对应⽤用的影响 应⽤用应该依赖于append ⽽而⾮非overwrite 定期做checkpoint 应⽤用应该写可以⾃自验证和⾃自标识的记录 典型应⽤用:

a) 单个写,然后在写完所有数据后,原⼦子性的重命名;

b) 阶段性的做checkpoint,在checkpoint中包含应⽤用层的checksum,Reader只读到最新的 checkpoint。

10. 系统交互 设计⽬目标之⼀一:最⼩小化master的参与 包括:数据修改、原⼦子性的record append、snapshot 每个修改操作均在所有的replica上执⾏行行。使⽤用lease在所有副本之间维护⼀一个⼀一致的修改顺 序。 master -> primary : a chunk lease 由primary决定所有操作的修改顺序; lease超时时间60s。 在⼼心跳消息中顺带着携带了了lease的request;

11. data flow 客户端按照任意的顺序将数据push到所有的replica 每个chunkserver在⼀一个内部的LRU cache中存储数据 基于⽹网络拓拓扑push数据,提升data flow的性能 在所有chunk server收到数据后,push write request 由primary分配⼀一个连续的序列列号 任何⼀一个replica写失败,这次写操作将会处于⼀一种不不⼀一致的状态 并发写成功仍可能会导致undefined and consistent状态(在客户端把⼀一个写操作拆成多个 操作的情况下) data flow设计⽬目标:充分利利⽤用机器器带宽、避免⽹网络瓶颈和⾼高延时链接、最⼩小化延时

12. atomic record append 由primary做⼀一些特殊处理理,可能会padding

13. snapshot copy-on-write,对⼀一个⽂文件或是⼀一个⽬目录树做快照

1)⾸首先回收将要快照⽂文件相关chunk的所有lease,保证后续的写操作都要经过master;

2) master log the operation to disk 在内存中执⾏行行快照操作,通过duplicate 元数据的⽅方式,新创建的快照⽂文件指向同样的 chunk; 3) 后续新的请求,master在发现所有的引⽤用计数⼤大于1时,构造⼀一个新的句句柄,然后创建所 有replica副本。

14. master operation

1) Namespace Management and Locking 允许多个Operation是活跃的,使⽤用锁保护不不同的区域 GFS内存对象是⼀一个查找表,⽤用于表示namespace full path names to meta data 每个namespace的node都有⼀一把读写锁 通过锁机制保证操作不不会冲突,通过按层次和⽂文件名顺序加锁来避免死锁

2) replica placement 多层(机器器、机架甚⾄至于数据中⼼心)使得chunk的负载分布变的复杂 chunk的放置策略略两个优化⽬目标:

a)最⼤大化数据可靠性和可⽤用性;

b)最⼤大化⽹网络带宽利利⽤用率;(trade off)

3) 创建副本考虑的因素

a) 按照磁盘空间利利⽤用率,放置在⼩小于平均值的server上;

b) 限制每个chunk server最近新创建chunk的数量量;

c) 副本应在机架之间分布;

4) 垃圾回收 在⼀一个⽂文件被删除后,GFS不不会⽴立即回收可⽤用的物理理内存空间; file and chunk levels, lazy garbage collection file和chunk层⾯面分别回收; 在file被删除后,对应的元信息也被删除,相应的chunk变成孤⼉儿chunk,进⽽而被删除; 通过⼼心跳消息和chunk server交互消息;

5) stale replica detection chunk version number在每次授予lease时通知chunk server,master和chunk server均持久 化这个值。

15. High Availablity

1) 快速恢复

2) chunk replication

3) master replication shadow master也会通过和chunk server通信监控chunk server状态

16. Data Integrity 64KB的⽤用户数据对应于32 bit的checksum。像其他元数据⼀一样,checksum的值和⽤用户数据 分开存储。有后台线程定期检查scan and verify the contents of inactive chunks

17.?如何使⽤用rpc logs as traces for load testing and performance analysis 18. Measurements 每个⽂文件在master上的metadata⼤大概100 bytes.

a)⽤用前缀压缩的形式存储filename;

b)⽂文件属主以及权限;

c)从⽂文件到chunk的映射;

d)每个chunk的当前版本;

e)每个chunk 保存位置信息以及引⽤用计数(⽤用于copy on write) 启动时间,30~60s⽤用于收集位置信息;

GFS的论⽂文从7、8年年前第⼀一次读,到现在应该读过不不下10遍了了吧,每次读都有收获。

FT virtual machines

1. 通过复制状态机的⽅方式实现replication;

2. 少于10%的性能损耗;

3. 真实应⽤用,少于20Mbit/s的带宽

为何物理理机复制困难⽽而虚拟机复制相对容易易? 由于hypervisor完整控制VM执⾏行行,所以可以捕获所有关于⾮非确定性操作的必要信息。 deterministic replay & FT 当前只⽀支持单处理理器器应⽤用 使⽤用共享存储 All input通过log channel由主发往备 检测主/备失败:通过udp⼼心跳以及监控log channel上的流量量

deterministic replay implementation capture -> apply don’t degrade performance

使⽤用共享存储来避免脑裂问题 在go live之前,在共享存储上执⾏行行⼀一个test and set操作,若执⾏行行失败,则⾃自杀。 若⽆无法访问共享存储,则不不断重试直到可以访问。使⽤用共享存储解决脑裂问题不不会引⼊入额外 的不不可⽤用。

design alternatives

1) shared vs non-shared disk

2) whether excuting disk reads on the backup VM

Lab 2&3&4 略略读 ⾸首先实现Raft,然后在Raft的基础上实现kvserver,然后实现shard kvserver。shared kvserver允许在shard之前迁移。

实验中并未真正的做持久化操作,分布式系统的实验刻意避免了了磁盘操作。 Lab 2 ⾸首先实现Election,然后实现Log Replication

thesecretlivesofdata.com/raft/

下周: Raft through section 5,Lab 2要完成。

Week 3 notes

这周主要是按照课程安排重读了了raft论⽂文的前半部分,以及把lab 2做完了了。raft论⽂文看过很多 遍,这⾥里里只随便便记录⼀一些重读时做的笔记。之前看的时候梳理理过⼀一些问题,这⾥里里列列出来。这 周花了了很多时间做lab 2,感觉⽐比去年年paxos的实验要难⼀一些,实现上的优化必须考虑,否则 test肯定会不不稳定。

raft (through section 5)

1. 实现分布式系统⼀一致性的关键属性,leader election,log replication, safety

2. 减少需要考虑的状态数,以及不不确定性;

3. novel features: a) strong leader b) leader election c) membership changes

4. GFS\HDFS\RAMCloud均使⽤用复制状态机来管理理leader选举以及存储配置信息;这些信息 在leader crash时仍可保存 -> chubby, zookeeper;

5.arch: consensus module在收到来⾃自客户端的command后,add them to its log,和其他 server上的⼀一致性模块通信,确保每个⽇日志最终包含同样顺序的同样请求;state machine按 照顺序处理理命令,输出被返回给客户端;

6. 1) 在⾮非拜占庭条件下,确保安全,network delay, partitions, packet loss, duplication, reordering

2) 只有多数派存活且可互相通信,系统即可⽤用;

3) 不不依赖于timing,错误的时钟最多引起可⽤用性问题;

4) 少数慢server不不影响整体性能;

7. Paxos”两宗罪”

1) 围绕⽇日志本身设计系统将是更更加简单和⾼高效的;new entries被严格按照顺序追加;

2) Paxos使⽤用某种程度的点对点协议作为核⼼心(⼀一个weak leadership只作为⼀一种性能优 化);

8. Raft

1) a complete and practical foundation for system building

2) 在所有条件下都是安全的;

3) 在绝⼤大多数条件下是可⽤用的;

4) 对通常的操作⾜足够⾼高效(协议上等价于multi-paxos)

5) understandability

a) problem decomposition b) simplify the state space by reducing the number of states to consider

9. Raft三种状态,Follower Candidate Leader Follower不不会主动发消息;Leader处理理所有客户端的请求;Candidate⽤用于选出⼀一个新的 Leader;

10. divide time into terms of arbitrary length. Terms are numbered with consecutive integers. Each Term begins with an election. Terms act as a logical clock in Raft. 使得 Leader可以很⽅方便便的检测过期的信息,如stale leaders;

11. Request Vote RPC/ Append Entries RPC

12. 在某段时间内未收到响应则重试, issue RPC parallel for best performance

13. log entry提交条件:创建这条log entry的leader已经将这条⽇日志复制到多数派; leader 记录他所知道的最⼤大已提交⽇日志的index,在后续所有Append Entries RPC(包括⼼心跳 RPC)中,记录这个index值; leader强制follower复制它的⽇日志;

14. SRM == state machine replication

15. GFS and VMWare FT均使⽤用了了复制状态机,eg: configuration server, like MapReduce or GFS master, key/value storage server

16. 使⽤用状态机复制的⽅方法:1)⽆无单点失败; 2)在分区情况下,⽆无脑裂;(⼀一个实际⼯工程 上的约束,多个replica仍不不能相距太远,⽐比如跨城市如深圳、杭州,否则rt不不可控)

17. the log is the sequence of commands so far, it’s equivalent to state — starting state + log = final state. log也给出了了⼀一个⽅方便便的numbering schema, ⽤用于对操作定序。

18. if a server has executed a command in a given entry number, no other server will execute a different command for that entry.

附之前总结过的raft论⽂文的⼀一些问题:

1. 什什么是复制状态机

2. Raft vs Paxos

3. Raft的设计⽬目标understandability,为达到设计⽬目标在做设计时如何权衡

4. 有稳定leader时的⾏行行为:

a) 如何确保不不同副本之间的数据⼀一致;

b) ⼀一条⽇日志何时可以在状态机上执⾏行行;

5. 如何选举? 在Leader切换时必须避免的: a) 双主(split brain) b) ⻓长时间⽆无主(选主是否可收敛) c) 丢 失已确认⽇日志 d) 主备数据不不⼀一致

6. split vote如何处理理?

7. 如何选择超时时间?

8. 真的没可能同时存在两个Leader吗?如果有两个副本同时认为⾃自⼰己是Leader,对读写操 作各会造成什什么影响?

9. 对选举是否还有其他约束?为了了达成什什么⽬目的。如果没有这个限制,bad case

10. 是否形成多数派的⽇日志⼀一定是已提交的⽇日志?Raft的设计为什什么会存在这个问题。

12. nop⽇日志的作⽤用,如果只考虑写操作,是否必须有nop⽇日志?

13. Raft实现的性能瓶颈,如何解决? lab 2,⽤用go语⾔言实现⼀一个raft协议,我这完成后的代码是640+⾏行行,其中有很多调试时加的⽇日 志,下周需要再花时间梳理理⼀一下(对⽐比下某⾦金金融级分布式数据库系统,实现multi-paxos⽤用 于commit log,不不算测试已经3w+⾏行行C++代码了了 :) ,当然这个对⽐比没什什么意义)。课程给的 test case,有好⼏几个都⾮非常不不好过,列列⼀一些可能的实现上的坑,仅作备忘。

1. election⼀一定要实现random timeout,否则⼀一定会遇到split vote。我实现时偷懒,超时时 间直接⽤用150+rf.me * 70 ms,结果⼀一个case死活过不不去,查了了很久。记住这样写是错 的!!!

2. log要⼀一次追加⼀一批;

3. AppendEntriesReply要返回本replica的matchIndex和predictedIndex(要⽀支持⼀一次回溯多 条⽇日志,不不仅要处理理⽇日志有冲突的情况,还要处理理follower就是⽐比leader⽇日志少的情况);

4. revoke时要区分是Candidate还是收到了了更更⾼高Term的Request,两者处理理不不同;

5. 测试都是要统计对形成多数派的command,实际已经reply (commit to channel)的replica 数⽬目,因此对于Leader写的最后⼀一条⽇日志,记得⽤用heartbeat将commitIndex发下去,触发 Follower的⽇日志replay;

6. rpc不不要发给⾃自⼰己,在循环遍历peers时;

7. 对每个rpc请求,单独⽤用⼀一个goroutine。希望⽤用⼀一个goroutine处理理⼀一轮所有replica的RPC 是不不⾏行行的,因为⽹网络不不稳定,同步RPC的超时时间不不可控,会导致执⾏行行⼀一轮操作的整体时 间变得不不可控,特别是对于选举来说;

8. 对于Unreliable的测试case,同步RPC可以⼀一直重试到ok == true,因为操作都是幂等 的,暂时没看到什什么副作⽤用;

9.reply中明确指明term⽐比currentTerm⼤大的,及时revoke;

10. 有⼀一个case是专⻔门测试总体RPC数不不会⽐比协议设计的超过太多,为了了通过这个case有两 个地⽅方需要注意 1)heartbeat超时时间不不能太短; 2) Start后判断nextIndex[server],再确 定这条⽇日志是否要发给这个server;

11. 还是print⽤用于调试最靠谱了了;

⼀一晚上case跑了了100遍,可以稳定通过 [:/data/10/gowork/src/raft]fgrep “ok” /tmp/2 |wc -l 100

1 Test: initial election …

2 … Passed 3 Test: election after network failure …

4 … Passed 5 Test: basic agreement …

6 … Passed 7 Test: agreement despite follower failure …

8 … Passed 9 Test: no agreement if too many followers fail … 10 … Passed

11 Test: concurrent Start()s …

12 … Passed 13 Test: rejoin of partitioned leader …

14 … Passed 15 Test: leader backs up quickly over incorrect follower logs …

16 … Passed 17 Test: RPC counts aren’t too high …

18 … Passed 19 Test: basic persistence …

20 … Passed 21 Test: more persistence …

22 … Passed 23 Test: partitioned leader and one follower crash, leader restarts … 24 … Passed 25 Test: Figure 8 …

26 … Passed 27 Test: unreliable agreement …

28 … Passed 29 Test: Figure 8 (unreliable) …

30 … Passed 31 Test: churn …

32 … Passed 33 Test: unreliable churn …

34 … Passed 35 PASS 36 ok raft 163.425s

下周:

1. 重新梳理理下lab 2代码,修改很多调试时加⼊入的代码;看test_test.go,很多case设计值得 学习;

2. raft论⽂文剩余部分;

3. go内存模型

Week 4 notes

Raft (Section 6 to end) 1. 成员变更更,需要的场景:

a) 替换出问题的机器器;

b) 改变degree of replication 2. 需要保证的

a) 针对同⼀一个term,不不会选出两个主; 3. 由于不不可能同时切换所有server的config,因此成员变更更需要使⽤用⼀一个两阶段的⽅方法, joint consensus; a) Log Entries are replicated to all servers in both configuration;

b) Any server from either configuration may serve as leader;

c) Agreement (for elections and entry commitment) requires seperate majorities from both the old and new configurations;

4. three more issues

a) new server初始化不不会保存任何⽇日志内容 the new server join the cluster as non-voting members;

b) 当前集群的leader可能不不是新配置的⼀一部分 -> the leader steps down ( return to follower state) ⼀一旦它已经提交了了Cnew entry,在这之 前,有⼀一段时间leader正在管理理⼀一个不不包括它⾃自⼰己的集群(即不不记⾃自⼰己的投票); 只有在这个时候,才能够保证后续选出的leader⼀一定在Cnew之中

c) 被删掉的server不不断的election timeout,可能导致当前的leader被revoke 这个server不不会takeover,是因为Cnew不不会发给它,但Cnew已经形成了了多数派,根据5.4.1 election restricted,它不不可能在Cnew中形成多数派(⽽而它上任的条件,是要求在两个集合 均形成多数派) 这个问题的解决办法:当收到⼼心跳后,并未超时前,认为当前leader是存在的,因此可忽略略 RequestVote RPC leader也应该⽆无视这个消息,但可以通过Append Entries的reply得知更更⼤大的term,在把⾃自⼰己 卸任; Cnew及之后的⽇日志应该只在Cnew的集合中写,避免后续被下掉的server被选为主,旧 leader在发现Cnew形成多数派后即把⾃自⼰己转成备。

5. Snapshotting is the simplest approach to compaction;

6. 在快照中,当前整个系统状态被写到stable storage的⼀一个快照,chubby和zookeeper均 使⽤用快照的⽅方式;

7. 另外,还有LSM tree和log cleaning的做compaction的⽅方式;

8. snapshot总是操作⼀一个完整的数据集合;在快照⽅方法中需要保存部分meta data,last included index & last included term,⽤用于⽀支持Append Entries的⼀一致性检查;在快照中也 保存截⽌止到当前的成员组;

9. ⼀一旦⼀一个server写完了了快照,可以把⽆无⽤用的⽇日志和旧版本的快照删除;follower可以⾃自⾏行行 做快照,因为此时consensus已经达成;

10. 触发快照的时机:

a) 当⽇日志达到⼀一个固定的尺⼨寸时;

b) 需要使⽤用copy-on-write技术,在⽣生成快照时也可以提供服务;

11. client interaction,需要保证linerizable semantics

a) 每个操作就像是⽴立即执⾏行行;

b) 每个操作均确切的执⾏行行⼀一次;

c) 操作在发起调⽤用和收到响应之间某点执⾏行行;

12. 客户端为每个命令分配独⼀一⽆无⼆二的序列列号,保证command只执⾏行行⼀一次,状态机跟踪每个 客户端所执⾏行行的最新的序列列号;如果收到⼀一个command,对应的序列列号已经执⾏行行,则⽴立即 reply; 13. Linearizable reads保证⼀一定不不会返回过期的数据 a) leader,在它的term写no-op entry,保证可以知道哪些entries已经提交;

b) leader必须在处理理⼀一个只读请求之前检查是否已经被deposed

i) exchange heartbeat messages with a majority of the cluster before responding to read- only requests; ii) lease rely on the heartbeat mechanism -> rely on timing for safety

14. 在⼯工程实践中如何对raft做性能优化/不不同的应⽤用类型对性能有何种需求;

Go Memory Model

1. Go is an answer to problems of scale at Google.

百万量量级的服务器器规模 etc 。 solution: great support for concurrency (channels, goroutines) design and engineer a language for large code bases (simple, understandable, efficient, great tool support)

2. more cores ; hardware, complier optimization change program behaviors

3. Memory (consistency) model defines:

a) which programs are valid;

b) what those valid programs can do;

c) therefore what programmers can expect;

d) therefore what complier writers mush ensure/can do

4. 顺序⼀一致性(by lamport): 所有处理理器器的操作按照某种特定的顺序执⾏行行,某个特定的处理理器器

执⾏行行的操作就像它按照程序指明的顺序执⾏行行⼀一样; 5. Message Passing

T1 T2 x=1 r1=y y=1 r2=x 程序有可能看到r1=1,r2=0吗

在顺序⼀一致性的硬件(没有线程局部的写缓存)上,no x86(Total Store Order,有线程局部的写缓存), no (T2看到T1的写必须时按顺序 的) ARM/POWER(全排列列架构),yes 6. Store Buffering T1 T2 x=1 y=1 r1 = y r2 = x 程序有可能看到 r1 = 0, r2 = 0吗?

在顺序⼀一致性的硬件上,no 在x86上,yes,T1的本地写可能不不会⽴立即在T2上可⻅见; 在ARM/POWER,yes on java (using volatiles): no, volatiles results must be as in some total ordering(both stores and loads) T1 T2 x=1 y=1 fence fence r1 = y r2 = x 不不可能再看到r1 = 0, r2 = 0,因为memory fence强制要求在T read之前,T write操作已经 全局可⻅见了了 7. Independent Reads of Indep. Writes T1 T2 T3 T4 x = 1 y = 1 r1=x r3 = y r2 = y r4 = x 有可能看到 r1 = 1, r2 = 0, r3 = 1, r4 = 0吗? 在顺序⼀一致性硬件上, no

在x86上,no,there is a total order over all stores to main memory 在ARM/POWER, yes,不不同的线程可能按照不不同的顺序收到不不能的写操作 8. Coherence T1 T2 T3 T4 x=1 x= 2 r1=x r3=x r2 =x r4=x 有可能看到r1=1,r2=2,r3=2,r4=1吗?

no, no, no,线程必须确定哪个写覆盖哪个写。

9. 同步模型:⼀一系列列关于内存访问的限制的集合,指明什什么时候、怎样需要完成同步操 作;

10. weakly ordering,Hardware针对某种同步模型weakly ordering,只要它对遵守这种模型 的程序均表现出顺序⼀一致性;

11. DRF:不不同线程访问统⼀一位置或者both reads 或者通过sync operation分割,one happens before the other

12. compiler优化:!!!重写代码

13. Don’t be clever :)

14. semantics based on happens-before:

a) if p imports q, q’s init happens beofre p’s

b) pacakge mains init happends before main.main

c) the go statement happens before the created goroutine’s execution

d) a send(or close) on a channel happens before the receive;

e) unlock happens before subsequent lock

下周: 1. zookeeper;

2. 分布式事务;

3. lab 3 Part A

Week 5 notes

ZooKeeper

1. from Yahoo!, Wait-free coordination , Internet-scale system

2. 协调分布式应⽤用进程的服务

3. zk是关键架构的⼀一部分,⽬目标是提供⼀一个简单⾼高效的核⼼心,可以在客户端⽤用于建⽴立更更复 杂的协调原语;

4. 1) group messaging 2) shared registers 3) distributed lock services in a replicated, centralized service

5. zk provides a per client guarantee of FIFO execution of requests and linearizability for all request that change the zookeeper state

6. 1) 配置服务是最基本的coordination

2) 在分布式系统中,Group membership and leader election are also common,进程需 要知道哪些其他进程活着,以及他们分别负责什什么;

3) Lock

7. 设计我们的协调服务时,并⾮非在server侧实现特定的原语,⽽而是优先暴暴露露API使得应⽤用开 发者能够实现他们⾃自⼰己的原语;

8. move away from blocking primitives, such as locks

9. 操纵简单的wait-free数据对象,这些对象像⽂文件系统⼀一样按照层次结构组织;

10. zk seems to be chubby without the lock methods, open and close;

11. wait-free property/FIFO client ordering of all operations/linearizable writes;

12. zookeeper client library, 管理理client和zk server之间的⽹网络连接;client/server/znode(an in-memory data node)/data tree; client在连接到zk时确⽴立⼀一个session,当发出请求时获得 ⼀一个session handle;

13. zk包含⼀一组server,使⽤用复制来达到⾼高可靠和⾼高性能;

14. 层次结构/临时节点/watch语义/session

15. Data Model with a simplified API and only full data reads and writes;

16. znodes also have associated meta-data with timestamps and version counters, 允许客 户端跟踪对znode的改变以及基于znode的版本号进⾏行行有条件的更更新;

17. 1) create(path, data, flags) ->regular, ephemeral, set the sequential flag

2) delete(path, version)

3) exists(path, watch)

4) getData(path, watch)

5) setData(path, data, version)

6) getChildren(path, watch)

7) sync(path) 上述API均有同步和异步两个版本,异步调⽤用,zk client保证按照操作被调⽤用的顺序执⾏行行 回调; 所有更更新操作均有版本号,可决定是否做版本检查

18. 通过watch保证不不会有误读config的情况发⽣生;通过sync解决两个client可能私下通信不不 满⾜足外部⼀一致性的问题; zk’s ordering guarantees allow efficient reasoning about system state, and watches allow for efficient waiting

19. group membership -> 使⽤用 ephemeral nodes to implement group membership

20. chubby vs zk chubby也有⼀一个类似于⽂文件系统的接⼝口,它也使⽤用⼀一种特定的协议保证副本之间的⼀一致 性;however,zk不不是⼀一种锁服务,它可以⽤用于实现锁,但是在API中没有锁操作。zk允许 客户端连接任意⼀一个zk server,不不只是leader,zk client可以使⽤用local replica来服务数据以 及管理理watch,因为它的⼀一致性模型⽐比chubby更更放松;

Efficient Optimistic Concurrency Control Using Loosely Synchronized Clocks

1. 分布式系统,对象在客户端被缓存和操作,server端提供持久化和事务⽀支持;

2. 可串串⾏行行化 & 外部⼀一致性(if transaction S committed before T begins (in real time), S is ordered before T) -> 已提交事务

3. 借助loosely synchnonized clocks实现全局可串串⾏行行化,每个对象只保存⼀一个单⼀一的版本, 避免对每个对象维护任何并发控制信息;

4. 跟踪每个客户端最近的invalidations,有很低的内存空间消耗,没有每个对象的磁盘负 载;

5. 在合适的负载压⼒力力下,我们的机制更更好;在⾼高的负载下,我们的机制可能导致更更多的 abort;

6. The scheme use timestamps generated from local clocks to define the serial order of transactions;

7. truncate transaction history: 通过本地时钟,预计⼀一个事务可能提交的时间戳范围,只 在这个范围内的信息需要保存;

8. 论⽂文中的⽅方法依赖时间戳同步只是在性能上的考虑,如果时钟不不同步,则⼀一些本应该可 以提交的事务也许会回滚,但本应回滚的事务绝不不会提交。除了了标准的两阶段提交协议要求 的消息外,不不会有额外的消息;

9. 两阶段提交协议:1)读写事务; 2)只读事务;

10. invalidation msg的⽤用处;对cached set的处理理;通过piggback,heartbeat等,避免额外 的⽹网络带宽消耗;

11. new way to order transaction, use timestamp taken from real clocks;

12. loose synchonzation: 在⽹网络中不不同节点的时钟,最多只有很⼩小的偏差(⼏几⼗十ms),因 此我们可以做出依赖于时钟的设计决策,以及解释我们⽅方法性能;

13. 由协调者分配⼀一个时间戳T.ts,保证全局唯⼀一,T.ts = <time, server_id>,事务按照时间 戳顺序串串⾏行行化; prepare msg中包含 T.ts, T.ReadSet, T.WriteSet, the identity of the client; 收到上述消息后,每个参与者执⾏行行检查,保证冲突的事务按照时间戳顺序串串⾏行行化;

14. VQ: validation queue, 保存所有成功validated transactions;

15. checks against later transactions: 已经确认的事务有更更⼤大的时间戳, later-confict check, version_check, invalid sets(如何使⽤用invalid checks实现version set,如何保证 version set⾜足够⼩小);

lab 3- Part A ⼀一些实现的tips:

1. 对回放的处理理,要保证顺序回放,因此最简单的实现⽅方式就是在Start时启动⼀一个线程不不 断的从channel中获取已经确认的msg;Get/PutAppend函数中只检查index

2. 在⽹网络不不可靠的时候,有可能会重复的Append,⽐比较简单的去重⽅方式是允许重复提交⽇日 志,但在回放的时候过滤,保证相同⼀一次请求(基于rpc_id去重)只执⾏行行⼀一次,这⾥里里应该有 更更好的实现⽅方式; 3. PutAppend/Get⽅方法实现中要注意判断状态,避免在分区的场景下出现死循环;

下周:

1. revisit Efficient Optimistic Concurrency Control Using Loosely Synchronized Clocks

2. FARM(No compromises: distributed transactions with consistency, availability, and performance,对分布式事务的性能优化)

3. 花些时间稍微看下lab 3 Part B

Week 6 notes

lab2-A 上周⽇日晚上跑了了100遍test case,发现有16次失败,失败的原因均是在10分钟内最后⼀一个 case未执⾏行行完,golang的测试框架会主动杀掉test进程。花了了前两天的空余时间分析了了失败 的原因,最开始以为是死锁,或是在分区的情况下不不断重试导致⽆无法切到有主的majority, 后来加了了很多⽇日志来定位,发现原因就是在执⾏行行最后⼀一个case的时候⽆无法稳定的选出⼀一个 主,每次主刚上任就被⼀一个更更⾼高term的candidate revoke掉了了。通过增加raft选举的超时时间 以及随机性解决,test case可以稳定的跑过了了。这个数值的选择和lab中使⽤用的labrpc加⼊入的 有意的延⻓长消息递送时间由很⼤大关系,真实场景中没必要设的特别⼤大。这也在⼀一定程度上说 明了了raft的可⽤用性对时间以及环境有很微妙的依赖关系。

Efficient Optimistic Concurrency Control Using Loosely Synchronized Clocks

1. local client caches and no locking messages;

2. 在客户端缓存命中时,事务执⾏行行阶段不不需要查询server;在客户端缓存cache miss时,从 server取数据;

3. 乐观并发控制,事务提交之前读写的只是本地的copy,当事务想要提交时,将读\写info 发送server,⽤用于validation决定是否可以提交(判断是否可以找到⼀一个可⽤用的串串⾏行行化的顺 序); 如果可以,update server’data,并让客户端缓存失效;如果不不可以,abort, discard writes;

4. 乐观(执⾏行行本身不不担⼼心可串串⾏行行性);悲观(lock,check each access);

5. validation,查看已提交的和正在提交的事务读写是否可以找出⼀一种序列列化执⾏行行等价于并 ⾏行行执⾏行行;

6. occ is the best when conflicts are rare;

7. 对只读事务也要做validation校验,其他的occ⽅方案可以通过维护多版本避免对只读事务做 校验(但是否仍能够保持严格的可串串⾏行行化?)

8. distributed occ validation, TC(客户端可以作为TC)

9. TC 负责分配⼀一个时间戳(可以使⽤用本地时间戳),分布式事务所有参与者要求检查是否 可以按照时间戳顺序满⾜足可串串⾏行行化(时钟同步, or, 冲突很少); 10. 可以使⽤用每个对象的版本号代替值⽤用于做有效性检查(是否后⼀一个事务保证读取了了前⼀一 个事务的写),使⽤用写事务的时间戳来做版本号;

FaRM (No compromises: distributed transactions with consistency, availability, and performance)

1. From MicroSoft

2. (分布式)事务(强⼀一致&⾼高可⽤用)在实现分布式系统中⾮非常重要,但由于之前实现的糟糕 的性能,使得系统设计者避免使⽤用(分布式)事务,弱化⼀一致性保证 or 只提供单机事务, 要求程序员Partition Data;

3. FaRM,分布式内存计算平台,提供分布式事务,严格的可串串⾏行行性,⾼高性能,持久化,⾼高 可⽤用;

4. 90台server,140 million TATP tps, 4.9 TB database,平均每台机器器⼀一百万以上的tps, 50G的数据,恢复时间低于50ms;惊⼈人的TPS,真正的⿊黑科技;

5. 事务、复制、恢复协议均采⽤用了了全新的设计⽅方式,leverage 1) commodity networks with RDMA 2)providing non-volatile DRAM;

6. how do they get high performance?

a) 数据可以完全放在RAM中(没有磁盘读);

b) non-volative RAM(没有磁盘写)(write RAM 200ns vs write hard drive 10ms vs write SSD 100us )

c) fast net(传统RPC⽅方式,调⽤用栈太⻓长,RPC达到10万以上⾮非常难(应该是指单线程), CPU是瓶颈;代替⽅方案,使⽤用one-sided RDMA,hardware ack,单server吞吐可到1千万, 延时5us,基本不不消耗接收端的CPU,使⽤用poll替代interrupt)

d) ⾼高效的CPU使⽤用率,绝⼤大部分是⽹网络相关的消耗;

e) 必须同时解决上述所有的,只解决⼀一个,会发现很快被其他的限制;

7. 使⽤用异步(event-driven)的API,取代同步阻塞式的API(否则上百万的tps可能意味着上百 万的线程,线程的切换开销是很⼤大的,需要数us,⽽而RDMA只需要5us)

8. one primary,f backups,要求消息在primary + f backups均写成功,⽽而不不是常⽤用的 majority⽅方案。有意为之,减少必要的消息数,提⾼高效率;

9. LOCK/VALIDATE/COMMIT-BACKUP/COMMIT-PRIMARY

10. to be continued (recovery章节需要再细看下)

由于解决lab2-A遗留留的问题,这周没有开始看lab2-B

下周:

1. 分布式计算相关的⼏几个⼀一致性问题

2. lab2-B开始

3. 如果有时间,把FaRM的recovery章节需要细看下;

Week 7 notes 上个周末,利利⽤用五⼀一假期,开始写⼀一系列列⽂文章“分布式数据库系统⼀一致性⼯工程实践”,所以 week 7 notes没有及时更更新。幸好按照课程安排,有⼀一个spring break,所以现在贴出来也 不不算晚。

# Week 7 Notes

## Consistency: DSM

- Two key ideas:

* Lazy-release consistency * Version vectors

- DSM plan:

* 程序员写并⾏行行程序(threads, shared variables, locks &c) * DSM 系统可以让线程运⾏行行在⼀一组机器器上 * 构建⼀一个单个共享内存的抽象模型

- What is a memory model?

* It explains how program reads/writes in different threads interact. * A contract:

- It gives the complier/runtime/hardware some freedom to optimize.

- It gives the programmer some guarantees to rely on * 有许多内存模型,在性能优化和使⽤用便便利利上做权衡,经常被称作⼀一致性模型

- 可线性化 vs 顺序⼀一致性 * 两者均要求, load results和所有操作按照某种特定顺序one at a time执⾏行行相⼀一致 * 可线性化要求保证外部⼀一致性(我看到我的存储操作完成,电话告诉你,你读取同样的 数据,则⼀一定可以读到我写⼊入的结果)

- 严格可串串⾏行行化 vs 可串串⾏行行化 * 针对事务操作的两个概念 * 严格可串串⾏行行化要求:如果我看到我的事务执⾏行行完成,然后你开启你的事务,则你的事务 可以看到我的写操作;

- previous DSM problems:

* false sharing: 两个machines 读写同⼀一个⻚页⾯面上的不不同变量量

- 写放⼤大:⼀一个byte的写操作导致整个⻚页⾯面的transfer * First Goal: 消除写放⼤大

- Big idea: write diffs

- write diff是否改变了了顺序⼀一致性

- 最多⼀一个写copy, 所以写操作被排序

- 当任何copy只读时,没有写操作,所以没有stale reads — 只读copies时最新的,所以没有stale reads

- Next goal: 允许并发的读写 * to copy with false sharing

- 当⼀一个机器器执⾏行行写操作时,并不不将其他⼈人标记为⽆无效

- 当其他机器器读时,并不不讲⼀一个机器器降级成读操作

- ⼀一个⻚页⾯面同时有多个不不同的copies * a reader look at which? diffs help: can merge writes to same page

- Big idea: release consistency (RC) * 不不持锁不不允许执⾏行行读操作

- 这⾥里里可以假设有⼀一个锁服务器器 * 在release时,将write diffs分发出去

- Big idea: lazy release consistency (LRC) * 只将write diff发给released lock的下⼀一个申请者,⽽而⾮非每个⼈人 * 性能上的优化:

- 如果你不不在某个object上申请锁,你将不不会看到对它所进⾏行行的更更新操作

- 如果只使⽤用⼀一个page上的⼀一些变量量,则不不会看到对其他变量量的写操作

- 更更少的⽹网络traffic

- 为了了让真实的程序⼯工作,Threadmarks必须⽀支持因果⼀一致性 * 当你查看⼀一个值时,你必须也同时看到可能影响这个值计算的其他的值(典型的如指针 所指的对象)

- How to track which writes influenced a value?

* interval numbers — 每次机器器做releases,分配⼀一个Number * 每个机器器track它已经从其他机器器看到的最⾼高的写操作,a “Vector timestamp” * Tag each releasw with current VT * 在申请加锁时,告诉之前的锁holder,你的当前VT

## 最终⼀一致性: Bayou

- 什什么时候需要最终⼀一致性 * replicas, fast local read/write, synchronization * 当连接不不可靠时⾮非常有⽤用

- 有哪些问题 * apps 初始只写本地副本 * 不不⽤用的users可以看到不不同的数据 * ⼀一些写操作可能是互相冲突的 (how to resolve)

- 最终⼀一致性是相当普遍的 * git, iPhone sync, Dropbox, Amazon Dynamo

- Why aren’t we satisfied with central server?

* 想要在断⽹网的情况下,仍可以使⽤用room scheduler * 因此需要在每个节点都有⼀一个DB replica * 在任何⼀一个节点均可以做读写操作 * 节点直接可以间歇性的连到⽹网络,也可以彼此之间通过蓝⽛牙等⽅方式通信

- 可能的⽅方式1:DB merge * 同步数据库,⽐比较期间的差异,做merge操作 * 可能在DB merge时,⽤用户不不能恰好参与,因此需要⾃自动的merge⼿手段

- Idea for conflicts: update functions * Applications提供⼀一个函数,⽽而不不是⼀一个简单的值 * Update functions可以在⽤用户不不在的情况下⾃自动解决冲突; * Sync exchanges functions, not DB content;

- Idea : ordered update log * Ordered log of updates at each node * Sync 确保不不同节点之间按照同样的顺序执⾏行行同样的更更新 * DB是按照特定顺序应⽤用更更新操作的结果 * same log => same order => same DB content * DB and log of operations:两种状态表示实际是等价的

- How can nodes agree on update order?

* Timestamp : <T, I> to every Update * Roll back and replay * the log holds the truth, the DB is jush an optimization * 时间戳定义了了⼀一个total order 并且更更新操作是确定性的

- Will update order be consistent with wall-clock time?

* \<10, A\> first, \<9, B\> second, 由于不不同节点之间的时钟可能不不完全⼀一致,因此顺序可 能是乱的 * Not “externally consistent”

- Will update order be consistent with causality?

* Lamport logical clocks * if node observes E1, then generates E2, then TS(E2) \> TS(E1) * Lamport clock:

- Tmax = 从所有节点中所看到的最⼤大的时间戳 — T = max(Tmax + 1, wall-clock time) to generate a timestamp * 在同⼀一个节点上,E1 then E2 => TS(E1) \< TS(E2), 但是反之不不成⽴立

- tentative -\> stable * ⼀一个节点被标记为primary replica

* primary replica给每个更更新操作分配⼀一个 CSN(Commit Sequence Number) * \<CSN, local-time, node-id\> * 未提交的更更新操作排在已提交的更更新操作后边

* ⼀一旦⼀一个更更新操作有了了⼀一个CSN,之前的更更新操作的集合是固定的 * 提交顺序是否和tentative order完全匹配? * 提交之后app就可以通知⽤用户哪些⽇日程安排不不会再改变了了;

- version vector — it summarizes log content

- Summary:

* Eventual consistency via sync and timestamp order * Causal consistency via Lamport-clock timestamps * Stability via primary assigning CSN * Conflict resolution via log of write functions * Quick log comparison via version vectors * Trim version vectors when nodes die via clever node IDs.

- application-specific 冲突解决办法(⽽而不不是简单的最后更更新者胜)

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly