Probabilistic CAP and Adaptive Key-value Stores: Revolution in NoSQL
Explore the groundbreaking research on probabilistic CAP and adaptive key-value stores by Prof. Indranil Gupta and team, shedding light on the evolution of distributed storage systems like NoSQL. Discover key concepts such as the CAP Theorem, hard vs. soft partitions, and the critical balance between consistency and availability in cloud environments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
PCAP Project: Probabilistic CAP and Adaptive Key-value Stores Indranil Gupta Associate Professor Dept. of Computer Science, University of Illinois at Urbana-Champaign Joint work with Muntasir Raihan Rahman, Lewis Tseng, Son Nguyen, Nitin Vaidya Distributed Protocols Research Group (DPRG) http://dprg.cs.uiuc.edu 1
Key-value/NoSQL Storage Systems Key-value/NoSQL stores: $3.4B sector by 2018 Distributed storage in the cloud Netflix: video position (Cassandra) Amazon: shopping cart (DynamoDB) And many others NoSQL = Not Only SQL 2
Key-value/NoSQL Storage Systems (2) Necessary API operations: get(key) and put(key, value) And some extended operations, e.g., CQL in Cassandra key-value store Lots of open-source systems (startups) Cassandra (Facebook) Riak (Basho) Voldemort (LinkedIn) Closed-source systems with papers Dynamo 3
Key-value/NoSQL Storage: Fast and Fresh Cloud clients expect both Availability: Low latency for all operations (reads/writes) 500ms latency increase at Google.com costs 20% drop in revenue each extra ms $4 M revenue loss Consistency: read returns value of one of latest writes Freshness of data means accurate tracking and higher user satisfaction Most KV stores only offer weak consistency (Eventual consistency) Eventual consistency = if writes stop, all replicas converge, eventually Why eventual? Why so weak? 4
CAP Theorem NoSQL Revolution Conjectured: [Brewer 00] Proved: [Gilbert Lynch 02] When network partitioned, system must choose either strong consistency or availability. Kicked off NoSQL revolution Abadi PACELC If P, choose A or C Else, choose L (latency) or C Consistency HBase, HyperTable, BigTable, Spanner RDBMSs Partition-tolerance Availability Cassandra, RIAK, Dynamo, Voldemort /Latency 5
Hard vs. Soft Partitions Hard partition CAP Theorem looks at hard partitions However, soft partitions may happen inside a data- center Periods of elevated message delays Periods of elevated loss rates Data-center 2 (Europe) Data-center 1 (America) CoreSw Congestion at switches => Soft partition ToR ToR 6
Our work: From Impossibility to Possibility C Probabilistic C (Consistency) A Probabilistic A (Latency) P Probabilistic P (Partition Model) Probabilistic CAP Theorem PCAP System to support SLAs (service level agreements) 7
Probabilistic CAP W(2) R(1) W(1) A read is tc-fresh if it returns the value of a write That starts at-most tc time before the read tc time pua is likelihood a read DOES NOT return an answer within ta time units is likelihood that a random host pair has message delay exceeding tp time units pic is likelihood a read is NOT tc-fresh Probabilistic Consistency (pic ,tc) Probabilistic Latency (pua ,ta) Probabilistic Partition ( , tp) PCAP Theorem: Impossible to achieve both Probabilistic Consistency and Latency under Probabilistic Partitions if: tc + ta < tp and pua + pic < Bad network -> High ( , tp) To get better consistency -> lower (pic ,tc) To get better latency -> lower (pua ,ta) 8
Towards Probabilistic SLAs Consistency SLA: Goal is to Meet a desired freshness probability (given freshness interval) Maximizeprobability that client receives operation s result within the timeout Example: Google search application/Twitter search Wants users to receive recent data as search Only 10% results can be more than 5 min stale SLA: (pic , tc)=(0.1, 5 min) Minimize response time (fast response to query) Minimize: pua (Given: ta) 9
Towards Probabilistic SLAs (2) Latency SLA: Goal is to Meet a desired probability that client receives operation s result within the timeout Maximize freshness probability within given freshness interval Example: Amazon shopping cart Doesn t want to lose customers due to high latency Only 10% operations can take longer than 300ms SLA: (pua, ta) = (0.1, 300ms) Minimize staleness (don t want customers to lose items) Minimize: pic(Given: tc) 10
Meeting these SLAs: PCAP Systems KV-store (Cassandra, Riak) CONTROL KNOBS PCAP System ADAPTIVE CONTROL Satisfies PCAP SLA System assumptions: Client sends query to coordinator server which then forwards to replicas (answers reverse path) There exist background mechanisms to bring stale replicas up to date Increased Knob Latency Consistency Read Delay Degrades Improves Read Repair Rate Unaffected Improves Consistency Level Degrades Improves Continuously adapt control knobs to always satisfy PCAP SLA 11
PCAP System Control Loop Architecture Active approach (1) Inject test operations (read and write) (2) Get estimate of current consistency or latency By analyzing operation log Original k-v store PCAP PCAP system Coordinator knobs Passive Approach: Sample ongoing client operations Non-intrusive to client workloads (3) Update control knobs to reach target SLA 12
Meeting Consistency SLA for PCAP Cassandra (pic=0.135) Mean latency = 3 ms | 4 ms | 5 ms Consistency always below target SLA PCAP system Satisfies SLA and close to optimal Optimal envelopes under different Network conditions Lognormal delay variation Setup 9 server Emulab cluster: each server has 4 Xeon + 12 GB RAM 100 Mbps Ethernet YCSB workload (144 client threads) Network delay: Log-normal distribution 13
Summary CAP Theorem motivated NoSQL Revolution But apps need freshness + fast responses Under soft partition We proposed Probabilistic models for C, A, P Probabilistic CAP theorem generalizes classical CAP PCAP system satisfies Latency/Consistency SLAs Integrated into Apache Cassandra and Riak KV stores Distributed Protocols Research Group (DPRG) http://dprg.cs.uiuc.edu 14
MOOC on Cloud Computing Concepts On Coursera Ran Feb-Apr 2015 (just wrapping up) 120K+ students Covered distributed systems and algorithms used in cloud computing Free and Open to everyone https://www.coursera.org/course/cloudcomputing Or do a search on Google for Coursera Cloud Computing (click on first link) Distributed Protocols Research Group (DPRG) http://dprg.cs.uiuc.edu 15
Our Posters at GCASR 15 Consistency-Availability Tradeoffs and SLAs Muntasir Rahman [POSTER HERE] Online Reconfiguration operations: Morphus project [IEEE ICAC 2015] Mainak Ghosh [POSTER HERE] Distributed Protocols Research Group (DPRG) http://dprg.cs.uiuc.edu 16
Summary CAP Theorem motivated NoSQL Revolution But apps need freshness + fast responses Under soft partition We proposed Probabilistic models for C, A, P Probabilistic CAP theorem generalizes classical CAP PCAP system satisfies Latency/Consistency SLAs Integrated into Apache Cassandra and Riak KV stores Distributed Protocols Research Group (DPRG) http://dprg.cs.uiuc.edu 17
