Distributed System IV

Distributed System IV

这一篇讲分布式系统下的互斥锁和同步控制。介绍了一些同步算法和2PC。Lamport和2PC是重点介绍的内容，在实际应用中也很广泛。

Distributed Mutual Exclusion

介绍了许多算法。

首先Mutual Exclusion Requirements:

• Correctness/Safety: At most one process holds the lock/enter C.S. at a time
• Fairness: Any process that makes a request must be granted lock

Distributed Requirements (focus on 1-3):

• Low message overhead
• No bottlenecks
• Tolerate out-of-order messages
• Allow processes to join protocol or to drop out
• Tolerate failed processes
• Tolerate dropped messages

袭来一大波Mutual Exclusion算法。

Centralized Mutual Exclusion

If server available send Grant to i	If server unavailable add i to Q	If Q not empty, remove i and send Grant
Clinet sends require to coordinator and wait for reply	————————————-	Client send release to coordinator

• Correctness: safe, fairness depends on queuing policy
• Performance: 3 messages/cycle (request, grant, release)
• Coordinator bottleneck

Bully Leader Election

• The Bully Algorithm
  • P sends an ELECTION message to all processes withhigher numbers.
  • If no one responds, P wins the election and becomescoordinator.
  • If one of the higher-ups answers, it takes over. P’s jobis done.

• Goal: anyone can trigger election whichautomatically determines a unique new leader

  

  ​

Decentralized Mutual Exclusion

Assume that there are n coordinators

• Get a majority vote from m > n/2 coordinators
• Reply immediately with GRANT or DENY

Problems: node failure, starvation(less than majority votes)

Request	Reply

Totally-Ordered Multicast

Assumption: all messages sent by one sender are received in the order they were sent and that no messages are lost.

Process:

• Multicast messages + local timestamp-ordered queue
• Multicasts an ACK to all other processes
• Process only if both at queue head and ACK’ed

​

• Key point from Lamport: the timestamp of the received message is lower than the timestamp of the ACK.
  • All processes will eventually have the same copy of the local queue consistent global ordering.

Lamport Mutual Exclusion

被DS白日梦破碎击垮。已经开始无脑写了。

• Based on Lamport TO-multicast
• ACK only to requestor
• Release after finished

• For single process send: n-1 request, n-1 reply, n-1 release

Ricart & Agrawala Mutex

• Relies on Lamport totally ordered clocks.

• When node i wants to enter C.S., it sends time-stamped request to all other nodes. These othernodes reply (eventually). When i receives n-1 replies, then can enter C.S.
• Trick: Node j having earlier request doesn’t replyto i until after it has completed its C.S.

• Deadlock free, starvation free
• Each cycle involves 2(n-1) messages

Token Ring Algorithm

Daniel模拟token ring让我们传ppt遥控器, 结果传到一半被藏起来啦2333(´▽｀) Daniel: “?????” 大家都爱Daniel(///▽///)

• Organize the processes involved into a logical ring
• One token at any timepassed from node to node along ring
• Only one process can hold token and pass ring at most once
• Each cycle requires 1~infinity messages, latency between 1&n-1
  • Problem: loss token (Daniel:”Where is the key?” hhhhh)

Compare & Summary

• Lamport algorithm demonstrates how distributedprocesses can maintain consistent replicas of adata structure.
• Ricart & Agrawala’s algorithm demonstrate utilityof logical clocks.
• Centralized & ring based algorithms have muchlower message counts.
• None of these algorithms can tolerate failedprocesses or dropped messages.

Distributed Concurrency Management

重点2PC，这节分别介绍单服务器和分布式背景下并发编程的算法。

Background Knowledge

Transactions 事务:

由一系列数据库操作组成的一个完整的逻辑过程

• Collections of Reads + Writes to global state
• Appear as a single, “indivisible” operation
• Standard Models for Reliable Storage

Desirable Charactics of Transactions: ACID

Atomicity, Consistency, Isolation, Durability

ACID Properitites

Atomicity 原子性: Each transaction completes in its entirely, or is aborted. If aborted, should not have effect on the shared global state. 完全成功/失败

Consistency 一致性: Each transaction preserves a set of invariants about global state. 事务对数据库完整性没有破坏

Isolation 隔离性: Also means serializability. Each transaction executes as if it were the only one with the ability to RD/WR shared global state. 多事务并发无影响

Durability 永久性: Once a transaction has been completed, or “committed” there is no going back. In other words there is no “undo”. 永久修改

Single Server Case

2-Phase Locking

General 2-phase locking

• Phase 1: Acquire or Escalate Locks (e.g. read => write)
• Phase 2: Release or de-escalate lock

Strict 2-phase locking

• Phase 1: (same as before)
• Phase 2: Release WRITE lock at end of transaction only

Strong Strict 2-phase locking

• Phase 1: (same as before)
• Phase 2: Release ALL locks at end of transaction only.
• Most common version, required for ACID properties

Distributed Transactions

为了可扩展性将数据库分布在多个机器上，事务可能涉及到多台机器。

Strawman solution

利用Coordinator来分配不同的事务，可能会违反ACID。

2-Pahse Commit

2PC也是利用一个Coordinator和Client/多个Participants进行通信，Coordinator通过Participant的投票来决定一个Transaction的Commit/Abort

• Phase 1: Prepare & Vote
  • Participants figure out all state changes
  • Each determines if it can complete the transaction
  • Communicate with coordinator
• Phase 2: Commit
  • Coordinator broadcasts to participants: COMMIT / ABORT
  • If COMMIT, participants make respective state changes

哪位大佬知道如何在markdown中调整表格宽度还不用css+html嘛

(1)	(2)	(3)	(4)	(5)

(1). Implemented as a set of messages

(2). Coordinator sends “CanCommit?” to participants

(3). Participants respond: “VoteCommit” or “VoteAbort”

(4). All “VoteCommit”: , Coord sends “DoCommit”, if any “VoteAbort”: abort transaction. Coordinator sends “DoAbort” to everyone => release locks

(5). Coordinator send reply to Client

2PC总结：

• Correctness: Neither can commit unless both agreed to commit
• Performance: 3N messages/transaction
• Deadlocks & Livelocks: timeout -> votes to abort
• 2PC is “blocking protocol”, 3PC is not
• 2PC can become a performance bottleneck

2PC和3PC的一点对比:

For 2-phase commit, if coordinator fails, the transactions would not be done. If participates has time out, the coordinate may wait forever. At this time, either asking other participant or vote for abort would help to get out of blocking. For 3-phase commits , the three phase are vote, prepare and commit. Participates indicate whether they vote for commit or abort. If participates vote for commit, coordinate would inform participates in prepare phase. Even coordinate and participates may lose message, it is indicated that a commit would make. Or an abort would happen.

• Previous
  
• Next