chubby and paxos
Download
Report
Transcript chubby and paxos
CHUBBY
and
PAXOS
Sergio Bernales
Dennis Kafura – CS5204 – Operating Systems
1
chubby and paxos
Overview
Chubby
Why?
How?
More precise how
Paxos
Why?
How?
More precise why
Dennis Kafura – CS5204 – Operating Systems
2
chubby and paxos
10 – 30,000 Clients
Different client services
Who is in charge?
Guarantee it?
What if you go down?
i.e. DNS Server
Dennis Kafura – CS5204 – Operating Systems
3
chubby and paxos
Service Requirements
Easy for client developers (of the variety kind)
Reliable and Available
Master is clear –hint, hint Paxos
Thousands of clients, tiny things
Growing clients = growing transactions
Dennis Kafura – CS5204 – Operating Systems
4
chubby and paxos
Chubby
Coarse-grained lock service
Caching
Event Notification
Access Control Lists
/ls/foo/wombat/pouch
Dennis Kafura – CS5204 – Operating Systems
5
chubby and paxos
System Structure
Cache: data, metadata, absent file, handles
(invalidated when data is changed)
Dennis Kafura – CS5204 – Operating Systems
6
chubby and paxos
Files, Directories, Handles
/ls/foo/wombat/pouch
ACL
Controls: reading, writing, ACL changes
ACL authentication in RPC
Meta-data of node (64 bits entries)
Instance Number
Content generation number
Lock generation
ACL generation
Dennis Kafura – CS5204 – Operating Systems
7
chubby and paxos
Sequencer
Sequence numbers provided only for interactionc
that use locks
Request sequencer
Name of lock
Acquisition mode (exclusive, shared)
Lock generation number
Lock delay
Dennis Kafura – CS5204 – Operating Systems
8
chubby and paxos
API (1 of 2)
Open(/ls/foo/wombat/pouch )*
Close()
GetContentAndStats()
getStat()
ReadDir()
SetContents()
Poison()
Compare and swap
Delete()
Acquire(), TryAcquire(), Release()
Dennis Kafura – CS5204 – Operating Systems
9
chubby and paxos
API (2 of 2)
GetSequencer()
SetSequencer()
CheckSequencer()
Dennis Kafura – CS5204 – Operating Systems
10
chubby and paxos
Sessions
Keeps locks active
Data consistent
Survives failures
KeepAlives
Most calls are KeepAlives
Dennis Kafura – CS5204 – Operating Systems
11
chubby and paxos
Events
Subcribe to
Contents modified
Child node added
Chubby master fail
Handle has become invalid
Lock acquired
Conflicting lock request
Dennis Kafura – CS5204 – Operating Systems
12
chubby and paxos
Efficiency
Atomic operations
No current directories
No last access times
Proxies
KeepAlive replies used to transmit events and
cache invalidations
Dennis Kafura – CS5204 – Operating Systems
13
chubby and paxos
Back to the DNS Server
Chubby caches
Chubby batches
Don’t use as fileserver
Do use for config files, elect masters
Dennis Kafura – CS5204 – Operating Systems
14
chubby and paxos
Master Fail - Over
Dennis Kafura – CS5204 – Operating Systems
15
chubby and paxos
Recover
1.
2.
3.
4.
5.
6.
7.
8.
9.
Pick a new client epoch number(sent by clients)
Master responds to master location requests
Rebuilds session memory strucuture
KeepAlives allowed
Notifies clients of failure
Master waits sessions syncs
Fully operational
While operating, handles are verified
Ephemeral files removed
Dennis Kafura – CS5204 – Operating Systems
16
chubby and paxos
Intro Paxos
1.
2.
3.
A consensus algorithm
Only a value that has been proposed may be
chosen
Only a single value is chosen
Unless value actually chosen, process don’t
learn about it
If someone disagrees, no one has agreed
Dennis Kafura – CS5204 – Operating Systems
17
chubby and paxos
Paxos
Proposers, Acceptors, Learners
Multiples of each
System assumes failure
Data never corrupted
Dennis Kafura – CS5204 – Operating Systems
18
chubby and paxos
Choosing a Value
P1- An acceptor must accept the first proposal
it receives
Problem
Several values proposed, none chosen
Possible to accept multiple
A solution: number proposals
Dennis Kafura – CS5204 – Operating Systems
19
chubby and paxos
Choosing a Value
P2- If a proposal with value v is chosen, then
every higher numbered proposal that is chosen
has value v
P2a- If a proposal with value v is chosen, then
every higher accepted by any proposer has
value v
P2b- If a proposal with value v is chosen, then
every higher accepted by any proposer has
value v
Dennis Kafura – CS5204 – Operating Systems
20
chubby and paxos
Choosing a Value
P2c- For any v and n, if a proposal with value
v and number n is issued, then there is a set S
consisting of a majority of acceptors such that
either (a) no acceptor in S has accepted any
proposal numbered less than n, or (b) v is the
value of the highest-numbered proposal among
all proposals numbered less than n accepted by
the acceptors in S
P1a- An acceptor can accept a proposal, iff if
has not reponded to a prepare request having a
number greater than n
Dennis Kafura – CS5204 – Operating Systems
21
chubby and paxos
Algorithm
Phase 1
a)
b)
Proposer selects proposal number n and sends
prepare request to majority of acceptors
If acceptor receives request number n greater
than that of any other prepare request it has
accepted, it sends back promise not to accept any
more and also it’s last n
Phase 2
a)
b)
Proposer receives prepare request form majority of
acceptors, then sends the proposal number n plus
the actual value v
If acceptor receives accept request for proposal n,
accepts it only if it has not responded to another
prepare request.
Dennis Kafura – CS5204 – Operating Systems
22
chubby and paxos
Learn a Chosen Value
Chosen value propagated
All acceptors send messages to learners
Distinguished learner gets the message, passes it
on
Distinguished learnerS
Learner ask acceptors
Distinguished Acceptors
Dennis Kafura – CS5204 – Operating Systems
23