Transcript Centrifuge: Integrated Lease Management and

Centrifuge: Integrated Lease Management
and Partitioning for Cloud Services
Atul Adya†, John Dunagan*, Alec Wolman*
†Google, *Microsoft Research
7th USENIX conference on Networked systems design and implementation, 2010 (NSDI’10)
Seminar Presentation for CSE 708 by Ruchika Mehresh
Department of Computer Science and Engineering
22nd February, 2011
1
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
2
Problem statement
Managing and operating on a large number of inmemory state while maintaining the responsiveness of
a cloud service.
Microsoft’s Live Mesh service defined the requirements
and constraints for solving this problem.
3
Microsoft Live’s Mesh service
• Large scale commercial cloud service
• In operation since April 2008
• As of March 2009, Centrifuge was actively used by 5
Live Mesh component services (List)
4
Terminology
• Lease
– Technique to ensure that only one server at a time is
responsible for a given piece of state.
• Partitioning
– Process of assigning each piece of state to an in-memory
server; requests are then sent to the appropriate servers.
5
Sample Application
Cloud based rendezous service
Request
is D1’sis IP
Request
(D1)(D2)
: My: What
IP address
x address?
Response
(D2) : x
Front-end web
server
Front-end web
server
Front-end web
server
Response
(D2) : x
Request (D1) : My Request
IP address
is x: What
(D2)
is D1’s IP address?
Back-end
application server
Back-end
application server
Back-end
application server
6
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
7
Requirements
•
•
•
•
•
•
•
Large number of small objects
Every object can be handled by one server
Memory is expensive – no replication
Effective partitioning
Freedom from fine- grained leasing
Load balancing
Easy addition, removal or crash handling of servers.
8
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
9
Architecture
• Manager-directed
The
Servers
front-end
that hold
servers
object
take
leases
care
of partitioning
incoming
leasing
and
Logically
centralized
•service
requests
Holdsimplemented
objects
and forward
in-memory
using
•a replicated
them
Process
to requests
the
back-end
state
machine
servers
10
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
11
Manager Service
• Executes manager-directed leasing
– Manager controls how the key space is partitioned and
leases are assigned.
• Key space mapped to variable-length range using
consistent hashing
– One range lease per virtual node
– 64 virtual nodes per owner library (Question)
• Every leased range has a lease generation number
12
Manager Service
Live deployment
Standby
servers
Only
the current
leader
interacts
executes with
the logic
• Runs
Paxos
• 3 standby servers
for
partitioning
Lookups
and
lease
Owners
management
• Serves
as state
store
• 5 Paxos-running servers
• Executes leader election protocol
• Can tolerate 2 machine failures
13
Manager Service – Leader Election
•
•
•
•
Changes to leader applied to Paxos group first
Standby servers check for candidacy periodically
New leader reads in the state from Paxos group
Lookups/Owners contact leader directly
– What happens when leader does not respond?
• Server addition and removal
– Leader calculates the desired (re)assignments, recalls leases,
then grant the new ones
– 60 second leases
14
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
15
Lookup library
• Maintains complete copy of the lease table
– 200KB per lease table (100X64X32 B)
• Advantages
– Local objects to owner mapping
– When remote confirmation at owner misses (due to
change in lease number), a loss notification is generated
• Incremental changes copied from manager every
30 seconds (Question)
16
Lookup-Manager Protocol
Entries in the change log are truncated every 5 minutes
Manager sends entire lease table when lookup’s LSN is too old
Or Size(change log) > Size(lease table)
17
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
18
Owner Library
• Owners send lease request/renews messages to
Manager every 15 seconds
– 3 consecutive lost/delayed requests lose the lease
• Manager
responds
with
the
(complete)
renewed/granted lease information
• Why are lease grants different from renewals?
19
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
20
Other issues
• Dealing with clocks
– Clock rate synchronization
• Dealing with Message Races
– Solution: Add two sequence numbers
(Senders’s and owner’s seq no.)
– Drop the racing message
– Random backoff, send again
21
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
22
API
• OwnershipChangeUpcall():
Semantics of Lookup() are that it returns hints
• To
If hint
fails, data
callerstructures
retries after
a short
backoff
initialize
when
some
new range of the key space has
• been
New lease
generation
number
(without
flag) at Owner
granted,
or to garbage
collect
the associated
staterepresents node
crash
• Caller resends the earlier subscribe message
• All lookup libraries signal a LossNotificationUpcall() on appropriate
ranges
23
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
24
Performance Evaluation
• Observation of Centrifuge in production for 2.5
months (Dec 2008 to March 2009)
• 130 Owners; 1,000 Lookups; 8 Manager servers
• Questions
– Is Centrifuge manager a bottleneck in steady-state?
– How well does Centriuge handle high-churn events?
– How stable are production servers?
25
Performance Evaluation
v
•1.5
Low
CPU
and activity
network
month
of steady
in steady
10utilization
leases lost
over state
this
for all server
period
v
v
v
v
v
•Conclusions
Slightly higher for the
leader
• current
Unplanned
owner failures
are quite rarebursts
• Network
on
• 12/16/2008
Owner
recovery
is
and 1/15/2009
reasonably
rapidover (7
when
standbys take
Owners recovered in <10
• Security
min) patches rolled out
these two
daysare very
• on
Message
races
rare in steady state (12
drops in 1.5 months) 26
Performance Evaluation
v
v
v
v
v
v
v
v
•Conclusion:
2.5 hour window during on
• second
Burst insecurity
network rollout
traffic
period
due to lookup servers
copying
lease
• 9:20
pm: entire
Servers
1 tables
and 3
• restarted,
During server
high 2churn,
the
took over
observed load at the leader
• 9:45
pm: Server
2 restarted,
(Manager
service)
is small
1 took
• server
During
the over
(quiet) period
Jan 8 toof
Jandip
13in, API
success
• Number
owners
at
rate is 100%
over 53
million
periodic
intervals
because
invocations
patch
is applied to group of
servers at regular intervals.
27
Performance Evaluation
• Testbed
– Around 2k front-end server instances, maintaining 10:1
Lookups:Owners ratio
– Restarted more rapidly than in production environment
At Manager Leader
28
Outline
Structure
Problem statement
Requirements
Architecture
API
Manager service
Lookup library
Owner library
Other issues
Performance evaluation
Conclusion
29
Conclusion
• Simplifies building scalable application tiers with inmemory state
• Combining leasing and partitioning to handle
massive number of objects
– Freedom from fine-grained leases.
• Manager-directed leasing that scales well
– Avoids lease fragmentation
• Non-traditional API where,
– Clients can not request leases
30
Questions-1
(Santoshb)
• Any reasons for choosing 64 virtual nodes per owner library?
Can this be increased in more complex systems?
• Most of these measurements were experimentally derived.
Though they haven’t directly mentioned about this choice, it
is most likely the optimum choice considering the work load.
Adding more number of virtual nodes can adversely affect the
performance. Consider installing too many virtual machines
on one server.
Back
31
Questions-2
(Santoshb)
• What are the bottlenecks to extend the current design across
multiple data centers?
• Centrifuge is designed to work within a datacenter (Refer to
section 2.4). However, if it has to be extended to multiple
datacenters, network reliability will be the first and foremost
issue.
I believe it is not an issue of bottlenecks, but feasibility.
If there are too many message races, or latencies involved,
Centrifuge can not work efficiently. Besides, maintaining strict
clock rate synchronization across datacenters will also be a
challenge. And this is just the tip of the iceberg.
32
Questions-3
(Fatih)
• Each lookup library has a replicated copy of the lease table
and these lookups can have stale data. How does the system
handle this stale data?
• In slides.
Back
33
Questions-4
(Lavone_R)
• What do you think the drawbacks and short comings of
centrifuge are in regards to its lease mechanism policies, its
partitioning implementation and its infrastructure that
enables services to be ran on pools of in-memory servers?
• Centrifuge works well within a datacenter, so we can not
move copies of replicas close to the site and make one a
primary copy (like in Pnuts). Also, need fine-grained leases for
such applications.Synchronization requirement is strict
Chubby is better for loosely-coupled distributed systems.
For the problem specification, Centrifuge seems to be the
best option. Chubby handles different kind of problem (file
system, session).
34
Questions-5
(Yong Wang)
• In section 2 :“each object can be fully handled by one
machine holding an exclusive”, is that mean the reading or
writing of each object is serializable? Why that simplify
design? Is there any consideration about keeping consistency?
• Yes, the requests are inherently serializable because only one
server is responsible for applying changed to a particular
object. (Refer to Section 4.2)
This assumption simplifies design because if a server could
not handle a popular object from within a lease range, there
would be additional lease reassignments and this will make
No issues of consistency here (Refer to Section 4.2)
35
Thank You !!
36
List of Live Mesh Services
1.
2.
3.
4.
5.
File sharing and synchronization across devices
Notifications of activity on these shared files
A virtual desktop that is hosted in the datacenter
File manipulation through a web browser
Connectivity to remote devices
Back
37