Operating Systems
Distributed Systems
4160 – Distributed and Parallel Computing
Chain Replication
Copyright By PowCoder代写 加微信 powcoder
Goal: Replication
– Run all operations through leader
– Remember, since writes have to get the majority, more replicas, slower writes
• Chain Replication
– A kind of primary/backup replication
– Very simple and elegant
– Need Raft’s help to maintain meta-data (e.g., who is the head/tail)
Chain Replication
• Write to the HEAD
– Propagate to the next in chain
– When writes reach the TAIL • Things are committed
• Reply clients ‘ok’
• Read the TAIL
R1 [head]->
• Only v1 is committed
• On R1 crash:
– R2 becomes the new head; ask client to resend v3
• Decided by
– the “centralized” service (Raft)
– Not by R2 (otherwise split brain if it is just network partitioning between R1 and R2; where R2 receives ‘no heartbeat’)
• On R2 crash:
– Head needs to resend v2 to R3
• On R3 crash:
– R2 becomes the new tail
Configuration Change
• Add a replica live
– E.g., add R4
– Checkpoint = what R3 now currently has
• R3 keeps serving as the tail
• R4 starts copying up to checkpoint – When R4 copy done
– R4 becomes the new tail
» With all copied values also ‘committed’
• R3 simply sends the remaining uncommitted values to R4
• Advantage:
– Write and Read workloads are separated to two different servers
– No split brain, no stale read, …àlinearizable
– Head (leader if you like this name more) sends network
messages out to 1 node only
– Very simple to implement (after you have Raft as the service)
• Disadvantage:
– One node fails, halt serving writes until crash handling done
• Raft works as long as the majority work
– Write latency (all replicas) is longer than Raft (majority)
To increase read parallelism
• Three logical chains
– Objects A to H -> Chain 1
– Objects I to P -> Chain 2 – Objects Q to Z -> Chain 3
• Chain1: S1->S2->S3
• Chain2: S2->S3->S1
• Chain3: S3->S1->S2
• Then good load balance + linearizability
Amazon EBS uses CR
– User-level like dropbox
– Save you files in multiple data centers – Dynamo KV in the back
– For system-level applications like DB
– Chain replication in same data centers
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com