CS代写 ECS656U/ECS796P - PowCoder代写

ECS656U/ECS796P
Distributed Systems

What we have seen so far

Consensus:
• Allows collection of machines to work as coherent group
• Continuous service, even if some machines fail
• Distributed consensus algorithm
• Eventual liveness

What this lecture is about
• Introduction to cloud computing

Many slides from Ion Stoica presentation: (https://ucbrise.github.io/cs262a-spring2018/)

Introduction
• Raft is a consensus algorithm
• Primary design goal: understandability (intuition, ease of explanation) • Complete enough that can be easily applicable in real implementations
• This results in a different problem decomposition with respect to Paxos!

Introduction
State Machine
• Consensus algorithms are commonly used in the context of “replicated state machines”
• State machine: a program that respond to an external stimuli and manage an internal state
• Most of today’s services are based on state machines (Memcached, RAMcloud)
• How to build reliable state machines? You replicate them on different servers!

Replicated State Machines
Consensus Module
Consensus Module
State Machine
z¬6 Consensus Module
State Machine
State Machine
x¬3 y¬2 x¬1 z¬6
• The idea: all the machines execute the same set of commands, with the
same stimuli in the same order -> all they must produce the same result
• This shall be so reliable to survive the failure of some machines
• HOW? Keep a replicated log Þ replicated state machine
x¬3 y¬2 x¬1 z¬6
x¬3 y¬2 x¬1 z¬6

Replicated State Machines
Consensus Module
x¬3 y¬2 x¬1 z¬6
Consensus Module
State Machine
z¬6 Consensus Module
Clients Servers
State Machine
State Machine
x¬3 y¬2 x¬1 z¬6
x¬3 y¬2 x¬1 z¬6
• Consensus module ensures proper log replication
• System makes progress provided any majority of servers are up • Failure model: fail-stop (not Byzantine), delayed/lost messages

How to do that? The Paxos answer..
1. Proposers:chooseuniqueproposalnumber(Pn)
2. Acceptors:ifPn>anypreviousstorednumber(Ps),thenreplybackwithPs
and the previously accepted value (V).
3. Proposer:ifitgetsamajoritythenselectvalueV,ifnonechooseownvalue, and send back “accept-request” (Pn,V)
4. Acceptor:isPn>Ps?Ifso,replywithaccept!

Before moving to Raft…
“There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system…the final system will be based on an unproven protocol.”
– Google Engineers
• Paxos has dominated discussion for 25 years
• Hard to understand (why does this work? what is the purpose of each
• Incomplete (only agrees on single value, it does not guarantee that we converge on a value: if it converges, it will be just one value)

Before moving to Raft…
• Hard to implement reliably (how to choose proposal value?)
Hard to understand + Hard to implement reliably = Not a good foundation for practical implementations!

Raft: designing for understandability..
• Main objective of RAFT
• Which design decision is the easiest to understand?
• Techniques that were used include
• Dividing problems into smaller problems (that are easier to understand)
• Reducing the number of system states to consider (removing as much as possible “if statements”

Raft overview
Leader election
• Select one of the servers to act as cluster leader • Detect crashes, choose new leader
Log replication (normal operation)
• Leader takes commands from clients, appends them to its log
• Leader replicates its log to other servers (overwriting inconsistencies)
• Only a server with an up-to-date log can become leader

Raft basics: servers
• A Raft cluster consists of several servers (remember the replicated state machine)
• Each server can be in one of three states: • Follower
• Candidate • Leader

Raft basics: servers
no heartbeat
win election
• Follower is passive but expect regular heartbeats
• Candidate tries to get elected as leader
• Leader replicates its log and send regular heartbeats to maintain leadership

Raft basics: terms
• Terms are epochs of arbitrary length • Start with the election of a leader • End when
Split Vote
Term 4 Term 5
Normal Operation
• Leader becomes unavailable
• No leader can be selected (split vote)
• Servers do not have global view of the entire system. Servers do not have global view of terms and might be see the progressing of terms at different times. How to deal with this?

Raft basics: terms
• Each server:
Split Vote
Term 4 Term 5
Normal Operation
• Keeps what they think the current term is
• Constantly exchange this information
• Every Response-Request message include the Term the server thinks we are on
• If a machine finds out that there is a more updated term, then it has an identity crisis and (1) updates its term and (2) become follower
• If a machine receives a request with an old term, then it replies saying “dude, you are too old now!”

Raft basics: RPC
• RPC: Remote Procedure Call is the request-response protocol used in Raft • Servers communicate though idempotent RPCs
• RequestVote
• Initiated by candidates during elections
• AppendEntry: Initiated by leaders to • Replicate log entries
• Provide a form of heartbeat
• Empty AppendEntry( ) calls

Leader election
• Servers start being followers
• Remain followers as long as they receive valid RPCs from a leader or candidate
• When a follower receives no communication over a period (the election timeout), it starts an election to pick a new leader

Follower Candidate Leader

Follower Candidate Leader
S4 1 ReqVote(2)
increment term, vote itself as a leader and ask everyone else to confirm
S3 timeouts, switch to candidate state,
ReqVote (2)
ReqVote (2)
ReqVote (2)

Follower Candidate Leader
Concurrently S1 timeouts, switch to candidate state,
increment term, vote itself as a leader and ask everyone else to confirm
ReqVote(2)
ReqVote (2)
ReqVote (2)
ReqVote (2)

Follower Candidate Leader
Let’s assume that S4 crashes and S5 grant vote to S1, while S2 grants vote to S3

Follower Candidate Leader

Follower Candidate Leader
Neither candidate gets majority. After a random delay between 150-300ms try
Denied Denied

Follower Candidate Leader
S42 2 S1 initiates another election for term 3
ReqVote (3)
ReqVote (3)
ReqVote (3)
ReqVote (3)

Follower Candidate Leader
S43 3 Everyone grants the vote to S1

Follower Candidate Leader
S43 3 S1 becomes leader for term 3

Election correctness
B can’t also get majority
Voted for candidate A
• Safety (nothing bad happen): allow at most one winner per term • Each server gives only one vote per term
• Majority required to win election
• Liveness (something good happen): some candidate must eventually win • Choose election timeouts randomly in [T, 2T] (e.g., 150-300ms)
• One sever usually times out and wins election before others time out • Works well if T >> broadcast time

So, what does a leader do?

• Accept client command
• Append them to their log (new entry)
• Issue AppendEntry RPCs in parallel to all followers
• Apply the entry to their state machine once it has been safely replicated

• Apply the entry to their state machine once it has been safely replicated. What does this means?
• Once new entry committed (safely replicated)
• Leader executes command in its state machine, returns result to client
• Leader notifies followers of committed entries in subsequent AppendEntries RPCs
• Followers execute committed commands in their state machines

A client sends a request
Client Log
State machine
Leader stores request on its log and forwards it to its followers
State machine

The followers receive the request
Client Log
State machine
State machine
Log State machine
Followers store the request on their logs and acknowledge its receipt

The leader counts followers’ ACKs
Client Log
State machine
State machine
Log State machine
Once it ascertains the request has been processed by a majority of the servers, it consider the entry committed (replicated in enough logs). So, it execute the
command in the state machine

The leader counts followers’ ACKs
Client Log
State machine
State machine
Log State machine
Leader’s heartbeats convey the news to its followers: they update their state machines

Log structure
term command
leader for term 3
• Entry is committed only if it is stored in the majority of the servers (i.e., in this case index = 7)
• This is to guarantee that operations are executed in strictly the same sequential order
committed entries

term command
leader for term 3
• Entry is committed only if it is stored in the majority of the servers (i.e., in this case index = 7)
• This is to guarantee that operations are executed in strictly the same sequential order
Log structure
committed entries
WARNING: Logs are not consistent between servers.

Log matching property
• The goal: high level of consistency between logs
1. Iflogentriesondifferentservershavethesameindexandterm
• They store the same command
• The logs are identical in all the preceding entries (they are committed)
2. Ifagivenentryiscommitted,allprecedingentriesarealsocommitted

Consistency check
• AppendEntries RPCs include of entry preceding new one(s)
• Follower must contain matching entry;
leader follower
AppendEntries succeeds: matching entry

Consistency check
• AppendEntries RPCs include of entry preceding new one(s)
• Follower must contain matching entry; otherwise, it rejects the request
• Leader retries with lower log index
leader follower
leader follower
AppendEntries succeeds: matching entry
AppendEntries fails: mismatch

Safety: leader completeness
• This assumes that the leader is always right! (it has all the entry committed)
• Once log entry committed, all future leaders must store that entry
• Servers with incomplete logs must not get elected
• Candidates include index and term of last log entry in RequestVote • Voting servers denies vote if its log is more up-to-date
• Longs ranked by

Eventual liveness
• Theoretically, competing candidates could cause repeated split votes
• Raft mitigates this by having each participating server individually choose a new
random timeout within each given interval.
• This will lead to a situation, where usually there is only one server awake, which can then win the election while every other server is still asleep.
• This works best if the lower bound of the chosen interval is considerably larger
than the broadcast time

• Consensus key building block in distributed systems
• Raft “similar to” Paxos
• Raft arguably easier to understand than Paxos
• It separates stages which reduces the algorithm state space • Provides a more detailed implementation

Introduction to Cloud Computing

Disclaimer

So, what is it?
• Cloud Computing is a general term used to describe a class of network-based computing that takes place over the Internet
• Simply the renting of servers and/or storage as well as access to these resources via a network
• This an oversimplification but a good starting point

So, what is it? (cont’d)
• These platforms hide the complexity and details of the underlying infrastructure from users and applications by providing a very simple graphical interface or API (Applications Programming Interface)
• The illusion of infinite computing resources available on demand
• ondemandservices,thatarealwayson,anywhere,anytimeandanyplace

So, what is it? (cont’d)
• The ability to use of computing resources on a short-term basis as needed (e.g., processors by the hour and storage by the day) and release them as needed
• Pay for use and as needed
• scale up and down in capacity and functionalities

In summary
• Cloud computing is an umbrella term used to refer to Internet based development and services
• A number of characteristics define cloud data, applications services and infrastructure:
• Remotely hosted: services or data are hosted on remote infrastructure
• Ubiquitous: services or data are available from anywhere
• Commodified: The result is a utility computing model similar to traditional that of traditional utilities, like gas and electricity – you pay for what you would want!

Motivating cloud computing
• Very large data centres can purchase hardware, network bandwidth and power for 1/5 to 1/7 the prices offered to a medium-sized data centre
Data taken from a report made in 2016
https://www.datacenterdynamics.com/news/research-larger-data-centers-make-considerable-savings-on-operating-costs/

Economy of scale..
Data taken from a report made in 2016
https://www.datacenterdynamics.com/news/research-larger-data-centers-make-considerable-savings-on-operating-costs/

This is good for everyone
• Parallel batch processing
• Batch processing and analytics jobs can analyse terabytes of data and take
hours to finish
• If there is enough parallelism, users can use hundreds of servers to complete the job quickly
• Tools such as Hadoop can be used to reduce the complexity of implementing these jobs

This is good for everyone
• The rise of analytics
• A special case of batch processing is business analytics
• A growing share of computing resources is now spent on understanding customers, supply chains and buying habits
• Market Sentiment analysis using Twitter data is a good example of this
convinced?

Cloud architecture
• Three main categories
• Software as a Service (SaaS)
• Platform as a Service (PaaS)
• Infrastructure as a Service (IaaS)
• Other services categories include • Storage as a Service (STaaS)
• Database as a Service (DbaaS)

Software as a Service
• Software is hosted on a cloud and clients typically access the software via a web browser
• Examples: Facebook, Netflix, Youtube
• Software can be licensed on a subscription basis or supported via ad revenue and data services
• Migration of traditional software to SaaS model
• Microsoft Office → Office 365 • DVD Games → Steam

Platform as a Service
• Cloud owners provide a platform for users to develop, run and manage web applications
• Examples: IBM Bluemix, Googles AppEngine, Microsoft Azure
• Developers are restricted to a particular language (Javascript, Python, PHP) or framework (.NET)

Infrastructure as a Service
• Cloud owners provide direct access to virtual (or in rare cases physical) machines which users can configure
• Examples: IBM Bluemix Virtual, Machine and Amazon’s EC2
• Users can select from a wide variety of operating systems and hardware configurations

Quick recap
• SaaS: provides access to application software. No need to worry about the installation, setup and running of the application.
• Examples: Google Apps, Microsoft Office 365

Quick recap
• SaaS: provides access to application software. No need to worry about the installation, setup and running of the application.
• Examples: Google Apps, Microsoft Office 365
• PaaS: provides computing platforms which typically includes operating system,
programming language execution environment, database, web server etc. • Examples: AWS Elastic Beanstalk, Windows Azure, Google App Engine
• IaaS: provides the computing infrastructure, physical or virtual machines and other resources like virtual-machine disk image library, block and file-based storage, firewalls, load balancers, IP addresses, virtual local area networks etc.
• Examples: Amazon EC2, Windows Azure, Google Compute Engine.

IaaS vs PaaS
• IaaS is more powerful as more tools available and customization possible • From great power comes great responsibility
• User responsible for scaling applications (some tools like Amazon’s Autoscaling can help but configuration required)
• User responsible for updating OS and machine image (happens automatically on PaaS)
• In general PaaS less complex as many concepts are abstracted from the user 66

• Abiologylabcreates400GBofdataforeveryexperimentandwantstomove its data processing to the cloud
• Choose a service model (IaaS, PaaS, SaaS) for the lab and explain why you chose this model?

• IaaSisprobablythemostappropriatemodel
• The described data processing might require complex code that may not be easily integrated into a SaaS or even a PaaS service.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts