Class

Sustain $\lfloor \frac{n-1}{3} \rfloor$ failures $f$ don’t response $f$ response but cannot tell if faulty node respond or not need $f$ + 1 to out number Provide safety and liveness Safety: all non faulty replicas agree on a total order for the execution of requests despite failures. System Model Network drop, delay, out of order, duplicate Faulty node behave arbitrarily Independent node failures $D(m)$ = digest of m $\langle m \rangle _{\sigma_i}$ = message sign by node $i$ Adversary can coordinate faulty nodes delay correct nodes cannot delay correct nodes indefinitely quantum compute Algorithm Terms replicas move through a succession of view primary of a view is $p = v \mod |R|$ $p$ primary replica $v$ view number $|R|$ total replicas $f$ max # to fail Replica = all servers Primary, Backup Process Client send request to primary primary multicasts all backups Replicas execute request and reply to client client wait for $f + 1$ same replies Client Client $c$ send $\langle REQUEST, o, t, c \rangle_{\sigma_c}$ to master $t$ timestamp $o$ operation to be executed Master broadcast to backups Replicas reply $\langle REPLY,v,t,c,i,r \rangle$ $r$ result $i$ replica number $v$ view number Client wait for $f + 1$ replies with same $t$ and $r$ If timeout Client broadcast request to all replica If already processed re-send reply (remember) If not processed & not primary redirect to primary Normal Case Replica state message log current view Three-phase atomic broadcast Pre-prepare Multicast to all backup and write to log $\langle \langle PRE-PREAPRE, v, n, d \rangle_{\sigma_p}, m \rangle$ $m$ is the client’s request (message)?...

很高的那些 Latency (? Ref Tail Latency Might Matter More Than You Think - Marc’s Blog (brooker.co.za) Why you should measure tail latencies | Roberto Vitillo’s Blog

Paxos issues Also apply to Chubby ZooKeeper All requests go to master Bad scalability High latency when geo-replicate (remote master) Sensitive to load spikes & network delay Master down -> system down (for a while) EPaxos Goal Optimal commit latency in the wide area Optimal load balancing across all replicas Graceful performance degradation So… Every replica need to act as proposers or else the latency will be high imply no leader Minimize proposer’s communication with remote Quorum composition must be flexible to avoid slow nodes Key Ordering Old: Leader choose order or choose pre ordered command slot EPaxos: dynamic & decentralized Not necessary to enforce a consistent ordering for non-interfering commands Non-interfering 1 RTT Need fast-past quorum of node $F + \lfloor\frac{F+1}{2}\rfloor$ $F$ = min# tolerable node failure R1: PreAccept C1 R5: PreAccept C2 R2, 3, 4: OK => Commit Interfering 2 RTT quorum size $F+1$ R5: PreAccept C4 R3: OK C4 R1: PreAccept C3 R3: OK C3 should go after C4 R1: Receive inconsistent response, second phase R1: Accept C3 -> C4 R 2 3: OK, Commit Protocol Commit Protocol (Unoptimized version, fast-path quorum = $2F$) Replica $L$ receive a request Replica choose the next available instance Attach attrs deps: list of all instances that interfere seq: number for breaking dependency cycles, larger than max(seq deps) Replica forwards command and attr to at least fast-path quorum of nodes (PreAccept) If quorum responds and attr same => commit else update attr (union deps, set max seq) => tell simple majority to accept => commit Execution Algorithm find strongly connected components topo sort bla bla bla Paper 4....

Introduction No blocking primitives (e.g. locks) FIFO Client ordering of all operations linearizable writes leader-based atomic broadcast - Zab ZooKeeper Service Hierarchy Regular/Ephemeral node Watch trigger if data changed Data model Simplify Full read/write filesystem API Offer async and sync access via full path setData delete contain a version para ignore if not match Example Leader configuration change New leader delete ready node New leader async update configuration nodes Leader create ready node Clients check if ready exist Configuration Management Processes share same configuration node Rendezvous Master want to share info with worker but master does not know info until started Master pass node path to worker and write to the node Group Membership Create parent node Children in node = member Simple Lock Clients create Ephemeral lock fail Only one will succeed Others watch Implementation idempotent transaction Read - Any servers weak consistency use sync if needed Write - forward to a single server leader calculate state Client server exchange zxid (last transaction id) Client connect only to servers with same or greater zxid VS Chubby No lock No blocking primitives Chubby blocks update while invalidating others’ cache Access via full path (vs fh) Chubby redirect all operations to master Chubby stricter consistency Chubby slower

Rationale Easier to migrate (from non-high-available to HA) Store/Fetch small files More familiar to programmers Reduce number of servers Lock Coarse-grained Hold for hours or days Lock-acquisition rate weakly related to client transaction rate Rare acquisition ->Temp lock server unavailability -> No big deal Should not lost lock when lock server reboot System Structure Client + Lib (Link) <-> Server (5 node) Chubby servers called replicas elect a master ask any replicas where the master is all replicas maintain identical database Only master read/write ack write after majority write read by master only Add new replica is one does not recover after a few hours Files Name ex: /ls/foo/wombot/pouch ls: common prefix (lock service) foo: name of a Chubby cell special name: local (local chubby cell) Operations Only whole file read No moving files from one directory (may served by different Chubby master) No soft/hard link Ephemeral Node (tmp files) Metadata ^a9d075 instance number: greater than any previous with same name content generation (files only): change when file are written lock generation number: increase when lock free -> hold ACL generation number: increase when ACL name change 3 ACL Name Checksum File handle ^e25fcd Check digit (No forging handle) Sequence number (if handle generate by previous master?...