The SNOW Theorem and Latency-Optimal Read-Only Transactions
This content discusses the SNOW Theorem, focusing on the properties of read-only transactions for optimal latency. It explores the challenges of huge web services, data distribution, consistency in transactions, and the fundamental trade-off between power and latency. Through images and brief insights, it highlights the implications of different transaction types on data handling efficiency and user experience.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
The SNOW Theorem and Latency-Optimal Read-Only Transactions Haonan Lu , Christopher Hodsdon , Khiem Ngo , Shuai Mu , Wyatt Lloyd University of Southern California and Princeton University New York University 1
Web Services Are Huge 2.5 B content items shared 2.7 B likes 300 M photos uploaded 105 TB data scanned 500 TB new data ingested [1][2] [1] Facebook data science. https://www.facebook.com/data [2] How Big Is Facebook s Data? https://goo.gl/bBN2ch 3
Huge Web Services Shard Data Massive amount of data must be distributed across servers Reads dominate the workloads need to be as fast as possible! 4
Simple Reads Are Insufficient Datacenter Storage Tier Servers Web Clients Load Page Read ACL=public ACL=privat e Public Set Private Photo B Not Read Done Private Photo B Done Acceptable! Photo B Photo B Done Photo=A Photo=B 5
Read-Only Transactions Transactions that do not modify data Consistently read data across servers 6
The Power of Read-Only Txn Consistency restricts what can be read Eliminates unacceptable combinations Compatibility enables write transactions Write transactions atomically update data Higher power more useful Stronger consistency higher power Compatibility higher power 7
Fundamental Tradeoff Intuitive Tension High Power Low Latency Reduces anomalies (the ACL Photo example) Better user experience Easier to reason about Higher revenue Our study proves: highest power + lowest latency is impossible 8
The SNOW Properties [S]trict serializability Highest Power [N]on-blocking operations [O]ne response per read Lowest Latency [W]rite transactions that conflict 9
[S]trict Serializability Strongest model: real-time + total order CR SACL SPhoto CW W starts Private ACL := Private Upload Photo B Photo B is private! Photo B W finishes R starts R finishes 10
[S]trict Serializability Strongest model: real-time + total order CR SACL SPhoto CW W starts R starts Photo B ACL := Private Upload Photo B Public + Photo A Photo B is private! Private Public + Photo B Photo A is private! W finishes R finishes 11
[N]on-blocking Operations Do not wait on external events Locks, timeouts, messages, etc. Lower latency Save the time spent blocking 12
[O]ne Response One round-trip No message redirection Centralized components: coordinator, etc. No retries Save the time for extra round-trips One value per response Less time for transmitting, marshaling, etc. 13
[W]rite Transactions That Conflict Compatible with write transactions Richer system model Easier to program 14
The SNOW Theorem: Impossible for read-only transaction algorithms to have all SNOW properties 15
Why SNOW Is Impossible CR SA CW SB W starts A := new B := new Assume SNOW R W invisible Violates property S T W visible RA = new RB = old Wfinishes 16
SNOW Is Tight : COPS-DW S+N+O S : Eiger S+N+W N O S+O+W : Spanner-RO W N+O+W : Spanner-Snap SNOW-optimal: have any 3 properties Latency-optimal: have N and O 17
Study Existing Systems with SNOW SNOW-optimal and latency-optimal System Spanner-Snap [OSDI 12] Yesquel [SOSP 15] MySQL Cluster MySQL Cluster S N O W Spanner-Snap [OSDI 12] Yesquel [SOSP 15] 18
Study Existing Systems with SNOW SNOW-optimal System Eiger [NSDI 13] DrTM [SOSP 15] RIFL [SOSP 15] Sinfonia [SOSP 07] Spanner-RO [OSDI 12] S N O 3 1 2 2 W 19
Study Existing Systems with SNOW Candidates for Improvement System COPS Rococo S N O 2 > 1 W Many more 20
Improve Existing Systems with the SNOW Theorem COPS [SOSP 11] Geo-replicated Causally consistent Read-only txn : S N O W Rococo [OSDI 14] Supports general transactions Strictly serializable Read-only txn : S N O W 21
New Algorithm Designs COPS-SNOW Latency-optimal (N + O) Rococo-SNOW SNOW-optimal (S + O + W) Design insight for optimizing reads: shift the overhead to writes 22
Rococos Read-Only Txn (S + W) CR SA SB CW W starts A := new B := new R: 1st round Gather conflict info A= old EQUAL ? W commits Blocks B= new R: 2nd round W finishes R: Nth round 23
Rococo-SNOW (S+O+W) CR SA R SB CW W starts A := new B := new T S T S A= old Forward TS Strictly Serializable W commits Blocks T S B= old A=old B=old W finishes 24
Evaluation of Rococo-SNOW To understand Latency of read-only transactions Throughput of other types of transactions Experiment configuration Identical to Rococo s TPC-C workloads https://github.com/USC-NSL/Rococo-SNOW 25
Significantly Lower Latency for Read-Only Txn 1200 OCC 1000 Lock Wait Latency (ms) 800 Retries Always 1 round 600 Rococo 400 2PL 200 Rococo -SNOW High Contention 0 0 20 Concurrent requests/server 40 60 80 100 26
Higher Throughput under High Contention 6000 Throughput (new-order/s) 5000 Rococo -SNOW 4000 3000 Rococo 2X throughput (High Contention) 2000 -14% throughput (Low Contention) 2PL 1000 High Contention OCC 0 0 20 Concurrent requests/server 40 60 80 100 27
Conclusion The SNOW Theorem for read-only txns Impossible to have all of the SNOW properties The SNOW Theorem is tight Understands what is possible SNOW helps understand existing systems Many are not yet optimal Rococo-SNOW SNOW Theorem guided SNOW-optimal design Significantly higher throughput and lower latency under high contention 28
