The Design of Scalable, Consistent, Autonomic, and Elastic ...

The Design of Scalable, Consistent, Autonomic, and Elastic ...

Albatross: Lightweight Elasticity in Shared Storage Databases for the Cloud using Live Data Migration Sudipto Das1, Shoji Nishimura2, Divyakant Agrawal1, and Amr El Abbadi1 Computer Science, UC Santa Barbara 2NEC Laboratories, Japan 1 Sponsor Web replacing Desktop Sudipto Das {[email protected]} 2 Paradigm shift in Infrastructure Sudipto Das {[email protected]} 3 Cloud application platforms Serve

thousands of applications (tenants) AppEngine, Azure, Force.com Tenants are (typically) Small SLA sensitive Erratic load patterns Subject to flash crowds Support for multitenancy is critical Our focus: DBMSs serving these platforms Sudipto Das {[email protected]} 4 Optimize operating cost Put $ in the y-axis Traditional systems only optimize performance Incentive

to aggressively consolidate tenant databases How to deal with surge in load? Aggressive consolidatio n Sudipto Das {[email protected]} 5 Elasticity in the Database tier Load Balancer Application /Web/ Caching tier Database tier Sudipto Das {[email protected]} 6 Live database migration Migrate

a tenant (or database partition) in a live system A critical operation to support elasticity Optimize operating cost Resource orchestration in multitenant systems Different from Migration between software versions Migration in case of schema evolution This paper: Decoupled storage architectures Shared nothing: see our SIGMOD 2011 paper Sudipto Das {[email protected]} 7 Decoupled storage abstraction Tenant Applications Controlle r DBMS Nodes

Query Router DBMS Node Tenant CellTenant (TM Tenant (TM +Cell DM) +Cell DM)(TM + DM) Tenant Cached Cell DB State Transacti on State Log Manager Network Attached Storage (NAS) Sudipto Das {[email protected]} 1/30/20

8 VM migration for DB elasticity One tenant-per-VM Pros: allows fine-grained load balancing Cons Performance overhead Poor consolidation ratio [Curino et al., CIDR 2011] Multiple VM VM VM Hypervisor tenants in a VM Pros: good performance

Cons: Migrate all tenants Coarse-grained load balancing Sudipto Das {[email protected]} VM Hypervisor 9 Live database migration Multiple tenants share the same database process Shared process multitenancy Migrate individual tenants ondemand in a live system Virtualization in the database tier Straightforward solution Stop serving tenant at the source Migrate to destination Start serving at the destination

Expensive! Sudipto Das {[email protected]} 10 Migration cost measures Service un-availability Time the tenant is unavailable Number of failed requests Number of operations failing/transactions aborting Performance overhead Impact on response times Additional data transferred Sudipto Das {[email protected]} 11

Why is live DB migration hard? Migrating a live tenant database How to ensure no transaction aborts? How to minimize performance impact? Nodes can fail during migration How to guarantee correctness during failures? Transaction atomicity and durability Recover migration after failure Transactions execute during migration How to guarantee serializability? Transaction correctness equivalent to normal operation Sudipto Das {[email protected]} 12

Our approach: Albatross Migrate DB cache and transaction state Make a snapshot of the cache and migrate Source continues serving transactions destination lags source Iteratively copy the database cache Copy transaction state in final step Transactions resume at destination Destination start warm Low performance impact and no aborted transactions Migrate transactions on-the-fly Transactions start at source and complete at destination Sudipto Das {[email protected]} 13

Normal operation Transacti ons Cache Source T11, T12, T13, 172 183 124 231 123 142 182 192 197 130

149 84 Tenant/DB Partition Sudipto Das {[email protected]} Destinatio 14 Phase I: Begin migration Transacti ons T11, T12, T13, 172 183 124 231 Cache

123 142 182 192 Snapsho t of the cache 197 130 149 84 Source Tenant/DB Partition 172, 124, 231, 123,

142, 182, 192, 130, 84 Sudipto Das {[email protected]} Tenant/DB Partition Destinatio 15 Phase I: Begin migration Transacti ons Track changes Source T11, T12, T13, 123, 142, 182, 192, 130, 84

172 183 124 231 123 142 182 192 197 130 149 84 Tenant/DB Partition 172

23 12 1 17 4 2 Sudipto Das {[email protected]} 124 231 Tenant/DB Partition Destinatio 16 Phase I: Begin migration Transacti ons Track changes Source

T11, T12, T13, 172 183 124 231 172 124 231 123 123 142 182 192 84 142

182 192 197 130 105 149 287 84 130 Tenant/DB Partition Sudipto Das {[email protected]} Tenant/DB Partition Destinatio 17 Phase II: Iterative phase

Transacti ons Track changes Source -84 T21, T22, T23, 130 172 172 , 183 124 231 105 84 123 142 182 192 , 287 130 197 105 149 287 ,

183 Tenant/DB , Partition 142 , 192 , 197 , 149 Sudipto Das {[email protected]} 124 231 123 142 182 192 Tenant/DB Partition Destinatio

18 Phase II: Iterative phase Transacti ons Track changes Source T21, T22, T23, 172 3 183 124 231 172 124 231 123

123 142 182 192 287 84 142 182 192 197 212 105 149 287 105 130

183 197 149 Tenant/DB Partition Sudipto Das {[email protected]} Tenant/DB Partition Destinatio 19 Phase III: Atomic handover Transacti ons Source T31, T32, T33, 3 183

124 231 123 142 182 192 212 105 149 287 Tenant/DB Partition 172 , 197 , 3,

212 , 123 142 , 231 Sudipto Das {[email protected]} T31, T32, T33, 172 3 124 231 123 287 142 182 192 105

183 212 197 149 Tenant/DB Partition Destinatio 20 Normal operation Transacti ons Source T31, T32, T33, T31, T32, T33, 3 183 124

231 172 3 124 231 123 123 142 182 192 287 142 182 192 212

105 149 287 105 183 212 197 149 Tenant/DB Partition Sudipto Das {[email protected]} Tenant/DB Partition Destinatio 21 Correctness Safety:

Exactly one owner for a tenant Atomic handover protocol: guarantees safety of ownership handover Serializability: Transaction state copied during migration guarantees serializability Durability: Changes from aborted transactions are not persisted Changes from committed transactions are never lost Transaction logs synchronized to guarantee durability Independent recovery in most cases Sudipto Das {[email protected]} 22 Implementation Implemented in ElasTraS, a scalable multitenant database system Append-only storage layout Separate read and write caches

Optimistic concurrency control Storage layout consists of SSTables An SSTable is a collection of blocks with in an internal index Read cache is a set of the blocks Snapshot: Read the block ids cached Changes maintained incrementally Termination copy read and write sets of transactions and flush write cache Sudipto Das {[email protected]} 23 Evaluation Evaluated against two baseline techniques Stop and Migrate (S&M) Stop serving tenant at source Flush changes Migrate control to destination and restart Flush and Migrate (F&M) Flush changes while continuing to serve tenant

Final stop and migrate Evaluated using two benchmarks TPC-C and YCSB Sudipto Das {[email protected]} 24 Experimental methodology System Controlle r Migrat e Metada ta Default transaction parameters: 10 operations per transaction 80% Read, 15% Update, 5% Inserts

Workload: 12K Txns Hardware: 2.4 Ghz Intel Core 2 Quads, 8GB RAM, 7200 RPM SATA HDs with 32 MB Cache, Gigabit ethernet Default DB Size: 1 GB Default Cache size: 250 MB Sudipto Das {[email protected]} 25 Results overview Unavailability window Albatross: 300-800ms S&M: 2-4 second unavailability, F&M: 200-500ms Failed requests Albatross: Zero S&M and F&M: hundreds Increase

in transaction latency Albatross: 15-30% Negligible performance impact during migration S&M and F&M: 200-400% increase in latency Data transferred: Albatross:1.3-1.6 times database cache S&M and F&M: approximately the size of the cache Sudipto Das {[email protected]} 26 Impact on latency Minimal impact on latency as a result of migration Sudipto Das {[email protected]} 27 Unavailability window Sudipto Das {[email protected]} 28

Failed requests Sudipto Das {[email protected]} 29 Adversarial scenario Working set does not fit in cache Sudipto Das {[email protected]} 30 Adversarial scenario Continues to have minimal performance impact Sudipto Das {[email protected]} 31 More experiments Sudipto Das {[email protected]} 32 Highlights

Live database migration critical for lightweight elasticity as a first class notion Albatross low cost live migration for shared storage architectures No transactions aborted No service interruption <15% increase in transaction latency immediately after migration Guaranteed safety in the presence of failures Sudipto Das {[email protected]} 33 Thank you! [email protected] http://www.cs.ucsb.edu/~sudipto http://www.cs.ucsb.edu/~dsl Back-up Sudipto Das {[email protected]} 35 Challenge: Lightweight Elasticity

Provisioning on-demand and not for peak Capacity Demand Resources Resources Optimize operating cost! Capacity Demand Time Time Traditional Infrastructures Deployment in the Cloud Unused resources Slide Credits: Berkeley RAD Lab Sudipto Das {[email protected]} 36 Albatross

DBMS Node Transaction State Transaction State Cached DB State Cached DB State Tenant/DB Partition Source Tenant/DB Partition Destination Persiste nt Image Sudipto Das {[email protected]} 37 Albatross Ownershi

p Steady State Time Source (Nsrc) 1. Begin Migration Initiate Migration Snapshot cache at Nsrc Initialize tenant at Ndst Nsrc continues 1/30/20 executing 2. Iterative Copying Destination (Ndst) 3. Atomic Handover

Synchronize and Catchup Track changes to DB State at Nsrc Iteratively synchronize state changes Sudipto Das {[email protected]} Steady State Finalize Migration Stop serving Tenant at Nsrc Synchronize cache Migrate transaction state 38 Transfer ownership to Impact on latency Sudipto Das {[email protected]} 39 Impact on throughput Minimal impact on throughput both

during and after migration Sudipto Das {[email protected]} 40

Recently Viewed Presentations

  • Chapter 4

    Chapter 4

    ARISTOTLE. Aristotle did not think there was a limit to the number of times matter could be divided. ... Building from Bohr's Model scientists now know that electrons move in a much more unpredictable manner than Bohr proposed.
  • RAP: Recycled Asphalt Pavement

    RAP: Recycled Asphalt Pavement

    AASHTO T 324 - Hamburg Wheel-Track Testing. ASTM D 6931 - Indirect Tensile Strength (IDT) Brand and type of anti-stripping additive, certificate of compatibility. Specification . Updates. Optional See GSP. 2014 Updates.
  • Algebra I End-of-Course Open Ended Scoring

    Algebra I End-of-Course Open Ended Scoring

    Algebra I End-of-Course Open Ended Scoring. Michael Luke NJDOE. 609-984-9637. [email protected] ... (see letter from Acting Commissioner Hendricks dated September 24, 2010) Raw Cut Scores 2009. Basic 18 (387, scale 300-850) Proficient 26 (44.8% ... Algebra I End-of-Course Open Ended...
  • Physical and Chemical Properties - TitanScience

    Physical and Chemical Properties - TitanScience

    Physical and Chemical Properties. Blue Color. Blue Color. Physical property. Density. Density. Physical property. Flammability. Flammability. Chemical property- The original substance is fundamentally changed. Solubility- (dissolves into a liquid to make a solution)
  • CS267: Introduction

    CS267: Introduction

    Implementation of Smoothness-Increasing Accuracy-Conserving Filters for DIscontinuous Galerkin Methods on the GPU, James King, Bharathan Rajaram, Supraja Jayakumar 8. Material Composites Optimization on GPU, Jonathan Bronson, Sheeraj Jadhav, Jihwan Kim 9. Grid-Based Fluid Simulation, Kyle Madsen, Ryan McAlister 10.
  • Illinois Department of Human Services State Opioid Response

    Illinois Department of Human Services State Opioid Response

    10 point font acceptable for charts, tables, and footnotes. Use page numbers on entire narrative, including appendices. ... Each section must have a heading that corresponds to the headings in Section E. of the NOFO (Application Review Information).
  • Interference and Diffraction Huygens Principle Any wave (including

    Interference and Diffraction Huygens Principle Any wave (including

    Phases When you combine two (or more) waves, you need to know the phase shift between them: The angle is the phase shift When the phase shift is zero, the waves add constructively The result is bigger Same thing for...
  • Total Member Involvement TMI & Personal Ministries The

    Total Member Involvement TMI & Personal Ministries The

    "Christ's method alone will give true success in reaching the people. The Saviour mingled with men as one who desired their good. He showed His sympathy for them, ministered to their needs, and won their ... PowerPoint Presentation Last modified...