Gecko: Contention-Oblivious Disk Arrays for Cloud Storage

Gecko: Contention-Oblivious Disk Arrays for Cloud Storage Ji-Yong Shin Cornell University In collaboration with Mahesh Balakrishnan (MSR SVC), Tudor Marian (Google), and Hakim Weatherspoon (Cornell) FAST 2013

Cloud and Virtualization What happens to storage? Guest VM Guest VM Guest VM Guest VM SEQUENTIAL VMM 4-Disk RAID0 350 350 RANDOM Seq - VM+EXT4 Seq - VM+EXT4 300 300 Throughput (MB/s) Throughput (MB/s) Rand - VM+EXT4 Rand - VM+EXT4 250 250 Shared Disk Shared Disk Shared Disk Shared Disk 200 200 150 150 100 100 50 50 I/O CONTENTION causes throughput collapse 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 # of Seq Writers # of Seq Writers 2

Existing Solutions for I/O Contention? I/O scheduling: reordering I/Os Entails increased latency for certain workloads May still require seeking Workload placement: positioning workloads to minimize contention Requires prior knowledge or dynamic prediction Predictions may be inaccurate Limits freedom of placing VMs in the cloud 3

Log-structured File System to the Rescue? [Rosenblum et al. 91] Log all writes to tail Write Write Write Addr 0 1 2 Log Tail N Shared Disk 4

Challenges of Log-Structured File System Garbage collection is the Achilles Heel of LFS [Seltzer et al. 93, 95; Matthews et al. 97] Garbage Collection (GC) from Log Head Read GC Log Tail N Head Log Shared Disk Shared DiskShared GC and read still cause disk seek Disk 5

Challenges of Log-Structured File System Garbage collection is the Achilles Heel of LFS 2-disk RAID-0 setting of LFS GC under write-only synthetic workload Max Sequential Throughput RAID 0 + LFS 250 Throughput (MB/s) 200 150 GC Throughput falls by 10X during GC 100 Aggregate 50 App 0 1 9 121 25 105 113 17 33 41 49 57 65 73 81 89 97 Time (s) 6

Problem: Increased virtualization leads to increased disk seeks and kills performance RAID and LFS do not solve the problem 7

Rest of the Talk Motivation Gecko: contention-oblivious disk storage Sources of I/O contention New technique: Chained logging Implementation Evaluation Conclusion 8

What Causes Disk Seeks? Write-write Read-read Write-read VM 1 VM2 Read Write Write Write Read Read 9

What Causes Disk Seeks? Write-write Read-read Write-read VM 1 VM2 Read Write GC Logging Write-GC read Read-GC read 10

Principle: A single sequentially accessed disk is better than multiple randomly seeking disks 11

Geckos Chained Logging Design Separating the log tail from the body Eliminates write-write and reduces write-read contention Eliminates write-GC read contention Garbage collection Log Tail GC from Log Head to Tail Physical Addr Space Disk 0 Disk 0 Disk 1 Disk 1 Disk 2 Disk 2 GC reads do not interrupt the sequential write 1 uncontended drive >>faster>> N contended drives 12

Geckos Chained Logging Design Smarter Compact-In-Body Garbage Collection Garbage collection Log Tail GC from Log Head to Tail Physical Addr Space Disk 0 Disk 1 Disk 2 Garbage collection from Head to Body 13

Gecko Caching Reduces write-read contention What happens to reads going to tail drives? Reduces read-read contention Read Read Read Write Tail Cache LRU Cache RAM Hot data Body Cache (Flash ) MLC SSD Warm data Disk 0 Disk 1 Disk 2 14

Gecko Properties Summary No write-write contention, No GC-write contention, and Reduced read-write contention Reduced read-write and read-read contention Read Read Write Tail Cache Body Cache (Flash ) Fault tolerance + Read performance Disk 0 Disk 1 Disk 2 Mirroring/ Striping Disk 0 Disk 0 Disk 1 Disk 1 Power saving w/o consistency concerns Disk 2 15

Gecko Implementation Primary map: less than 8 GB RAM for a 8 TB storage 4-byte entries Logical-to-physical map (in memory) WW R W W head tail 4KB pages Data (in disk) R W W Disk 0 Disk 1 Disk 2 empty filled Physical-to-logical map (in flash) head tail Inverse map: 8 GB flash for a 8 TB storage (written every 1024 writes) 16

Evaluation 1. How well does Gecko handle GC? 2. Performance of Gecko under real workloads? 3. Effect of varying Gecko chain length? 4. Effectiveness of the tail cache? 5. Durability of the flash based tail cache? 17

Evaluation Setup In-kernel version Implemented as block device for portability Similar to software RAID User-level emulator For fast prototyping Runs block traces Tail cache support Hardware WD 600GB HDD Used 512GB of 600GB 2.5 10K RPM SATA-600 Intel MLC (multi level cell) SSD 240GB SATA-600 18

How Well Does Gecko Handle GC? 2-disk setting; write-only synthetic workload Gecko Log + RAID0 250 250 GC Throughput (MB/s) Throughput (MB/s) 200 200 Max Sequential Throughput of 1 disk = Max throughput Aggregate Aggregate throughput Max Sequential 150 150 Throughput of 2 disks App GC 100 100 Aggregate Throughput collapses 50 50 App 0 0 34 1 11 21 31 41 51 61 71 81 91 1 12 23 45 56 67 78 89 101 111 100 111 122 Time (s) Time (s) Gecko s aggregate throughput always remains high 3X higher aggregate & 4X higher application throughput 19

How Well Does Gecko Handle GC? Gecko 250 250 GC Throughput (MB/s) Throughput (MB/s) 200 200 Aggregate 150 App 150 100 100 50 50 0 0 1 11 21 31 41 51 61 71 81 91 101 111 No GC Move- to-Tail GC Compact- in-Body GC Time (s) App throughput can be preserved using smarter GC 20

MS Enterprise and MSR Cambridge Traces Estimated Addr Space Total Data Accessed (GB) Total Data Read (GB) Total Data Written (GB) TotalIOReq Trace Name NumReadReq NumWriteReq prxy 136 2,076 1,297 779 181,157,932 110,797,984 70,359,948 src1 820 3,107 2,224 884 85,069,608 65,172,645 19,896,963 proj 4,102 2,279 1,937 342 65,841,031 55,809,869 10,031,162 Exchange 4,822 760 300 460 61,179,165 26,324,163 34,855,002 usr 2,461 2,625 2,530 96 58,091,915 50,906,183 7,185,732 LiveMapsBE 6,737 2,344 1,786 558 44,766,484 35,310,420 9,456,064 MSNFS 1,424 303 201 102 29,345,085 19,729,611 9,615,474 DevDivRelease 4,620 428 252 176 18,195,701 12,326,432 5,869,269 prn 770 271 194 77 16,819,297 9,066,281 7,753,016 [Narayanan et al. 08, 09] 21

What is the Performance of Gecko under Real Workloads? Mix of 8 workloads: prn, MSNFS, DevDivRelease, proj, Exchange, LiveMapsBE, prxy, and src1 6 Disk configuration with 200GB of data prefilled Log + RAID10 Gecko 200 200 Read Write Read Write Throughput (MB/s) Throughput (MB/s) 150 150 100 100 50 50 0 0 1 9 1 9 41 17 17 25 33 49 57 65 73 81 89 97 25 33 41 49 57 65 73 81 89 97 113 105 113 105 Time (s) Time (s) Gecko Mirrored chain of length 3 Tail cache (2GB RAM + 32GB SSD) Body Cache (32GB SSD) Gecko showed less read-write contention and higher cache hit rate Gecko s throughput is 2X-3X higher Log + RAID10 Mirrored, Log + 3 disk RAID-0 LRU cache (2GB RAM + 64GB SSD) 22

What is the Effect of Varying Gecko Chain Length? Same 8 workloads with 200GB data prefilled 180 160 Read Write 140 Throughput (MB/s) errorbar = stdev 120 100 80 60 40 20 RAID 0 0 Single uncontended disk Separating reads and writes better performance 23

How Effective Is the Tail Cache? Read hit rate of tail cache (2GB RAM+32GB SSD) on 512GB disk 21 combinations of 4 to 8 MSR Cambridge and MS Enterprise traces 100 100 90 80 90 70 Hit Rate (%) Hit Rate (%) 60 80 50 40 70 30 20 60 10 0 50 1 3 5 7 11 13 15 17 19 21 Application Mix 9 100 200 300 400 500 SSD Amount of Data in Disk (GB) RAM At least 86% of read hit rate RAM handles most of hot data Amount of data changes hit rate Still average 80+ % hit rate Tail cache can effectively resolve read-write contention 24

How Durable is Flash Based Tail Cache? Static analysis of lifetime based on cache hit rate Use of 2GB RAM extends SSD lifetime 700 700 600 600 SSD Lifetime (Days) SSD Lifetime (Days) 500 500 400 400 300 300 200 200 Lifetime at 40MB/s 100 100 0 0 1 2 3 4 5 6 7 8 9 101112131415161718192021 Application Mix Application Mix 1 2 3 4 5 6 7 8 9 101112131415161718192021 2X-8X Lifetime Extension 25

Conclusion Gecko enables fast storage in the cloud Scales with increasing virtualization and number of cores Oblivious to I/O contention Gecko s technical contribution Separates log tail from its body Separates reads and writes Tail cache absorbs reads going to tail A single sequentially accessed disk is better than multiple randomly seeking disks 26

Question? 27