Enhancing Cloud Data Transactions with Deuteronomy
undefined
Justin Levandoski*
University of Minnesota
David Lomet
Microsoft Research
Mohamed Mokbel*
University of Minnesota
Kevin Zhao*
University of California San Diego
Deuteronomy: Transaction Support
for Cloud Data
*work done while at Microsoft Research
Motivation
2
Want ACID transactions for data anywhere in cloud
Currently, cloud providers support:
Transactions for data
guaranteed
to exist on the same node
Eventual consistency
Currently no support for transactions “across the cloud”
Application Motivation – Transactions Anywhere
The Cloud
My new mobile application
3
What We Want
Begin Transaction
1. Add me to Dave’s friend list
2. Add Dave to my friend list
End Transaction
What We Have Today
Eventual consistency*
click
*Thanks to Divy Agrawal for example
4
Application Motivation – Transactions Anywhere
Talk Outline
Application Motivation
Technical Motivation
Deuteronomy Architecture
Transaction Component Implementation
Performance
Wrap Up
5
Technical Motivation
CIDR 2009:
“Unbundling Transaction Services in the Cloud”
(Lomet et al)
Partition storage engine into two components
Transactional component (TC): transactional recovery and concurrency
control
Data component (DC): tables, indexes, storage, and cache
6
TC
DC
1
DC
2
CIDR 2011:
“Deuteronomy: Transaction Support for Cloud Data”
Reduce number of round trips between TC and DC
Large latencies (Network overhead, context switching)
No caching at the TC
Application
Technical Motivation
CIDR 2009 required logging before sending operation to DC
Drawback: requires two messages and/or double logging to perform
operation (e.g., update)
7
TC
DC
1
1. Request before image
2. Return image
3. Log operation (generateLSN)
4. Send operation
5. Perform operation
6. Log operation success
Our new protocol logs
after
operation returns from DC
TC
DC
1
2. Send operation
3. Perform operation
and send back before
image
4. Log operation
1. Locking (generate LSN)
Must deal with LSNs out of order on log
Also required us to rethink TC/DC control protocol
Talk Outline
Application Motivation
Technical Motivation
Deuteronomy Architecture
Transaction Component Implementation
Performance
Wrap Up
8
Deuteronomy Architecture
Transaction Component (TC)
1.
Guarantee ACID Properties
2.
No knowledge of physical data
storage
Logical locking and logging
Client Request
Interaction Contract
1.
Reliable messaging
“At least once execution”
2.
Idempotence
“At most once execution”
3.
Causality
“If DC remembers message, TC must also”
4.
Contract termination
“Mechanism to release contract”
9
Client
Logical
locking
Cloud Storage
Local Storage
Record/ Table
operations
. . .
Session 1
. . .
Session N
Session 2
Logical
logging
Data Component 2
Data Component N
Transaction Component
Cloud Storage
Session
Data Component 1
Client
Talk Outline
Application Motivation
Technical Motivation
Deuteronomy Architecture
Transaction Component Implementation
Performance
Wrap Up
12
Record Manager – An Insert Operation Example
13
Receive request and dispatch
a session thread
Call to lock manager
Lock resource
Generate Log Sequence
Number (LSN)
Sends LSN & operation to DC
Call to log manager
Log operation with LSN
TC Record
Manager
Lock
Manager
Log
Manager
DC
Client &
Session
Manager
1
2
3
4
Lock Manager
14
Deuteronomy locking hierarchy:
Support locking of range read by using partitions, not
next
key locking
SELECT * FROM Employees
WHERE id > 10 AND id < 40
Partitions to lock [0, 30], [30, 60]
So that inserts DO NOT have to know or test the lock on
next key
In charge of generating LSN before sending operation to
data components
Table
Record
Partition
Log Manager
15
Different from conventional log manager in two aspects:
Need to coordinate TC’s log with DC’s cache
Write Ahead Logging
: Which updates are
allowed to be
made stable at DC
Log truncation
: Which updates
must be
made stable at
DC
Complexity: LSNs are stored
out-of-order
on TC’s log,
but DC only understands LSN
Control Operations: End-Of-Stable-Log
16
TC sends an LSN value
eLSN
from TC to all DCs
For DC:
Updates with LSN <= eLSN
can
be made stable.
Updates with LSN > eLSN
must not
be made stable and
must be forgettable.
For TC: all log records with LSN <= eLSN must be flushed.
The Deuteronomy Project
17
Built TC, DCs, test environment, and performed experiments
Different “flavors” of DCs implemented
Cloud DC
Windows Azure used as cloud storage
Collaborators: Roger Barga, Nelson Araujo, Brihadish Koushik, Shailesh Nikam
Flash DC
Storage manager from Communications and Collaboration Systems group at
MSR
Collaborators: Sudipta Sengupta, Biplob Debnath, and Jin Li
Windows Azure
Cloud
DC
Buffer Pool
Flash
DC
Flash Storage
TC
Operation Log
Talk Outline
Application Motivation
Technical Motivation
Deuteronomy Architecture
Transaction Component Implementation
Performance
Wrap Up
18
Performance of TC
19
Adapted TPC-W benchmark
Controlled DC latencies from 2ms to 100ms
High latency requires high level of multithreading, which
appears to impact throughput
Ideas on improving throughput
Threading mechanism
Implementation language from C# to C/C++
Conclusion
20
Application & Technical Motivations
Overview of project, teams, and development
Architecture of our multithreaded TC
A new TC:DC interface protocol to suit the cloud scenario
Experiments that show good performance and the impact
of cloud latency on performance
Deuteronomy aims to provide ACID transactions for cloud data, addressing the current limitations of transactions in cloud environments. The motivation, technical aspects, and implementation of Deuteronomy are discussed, highlighting the need for efficient transaction support across the cloud. Through innovative approaches and components, Deuteronomy enhances the transactional capabilities for cloud data storage.
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
Deuteronomy: Transaction Support for Cloud Data Justin Levandoski* University of Minnesota David Lomet Microsoft Research Mohamed Mokbel* University of Minnesota Kevin Zhao* University of California San Diego *work done while at Microsoft Research
Motivation Want ACID transactions for data anywhere in cloud Currently, cloud providers support: Transactions for data guaranteed to exist on the same node Eventual consistency Currently no support for transactions across the cloud 2
Application Motivation Transactions Anywhere My new mobile application The Cloud 3
Application Motivation Transactions Anywhere What We Have Today What We Want Begin Transaction Eventual consistency* click 1. Add me to Dave s friend list 2. Add Dave to my friend list End Transaction Free World Map *Thanks to Divy Agrawal for example 4
Talk Outline Application Motivation Technical Motivation Deuteronomy Architecture Transaction Component Implementation Performance Wrap Up 5
Technical Motivation CIDR 2009: Unbundling Transaction Services in the Cloud (Lomet et al) Partition storage engine into two components Transactional component (TC): transactional recovery and concurrency control Data component (DC): tables, indexes, storage, and cache DC1 TC Application DC2 CIDR 2011: Deuteronomy: Transaction Support for Cloud Data Reduce number of round trips between TC and DC Large latencies (Network overhead, context switching) No caching at the TC 6
Technical Motivation CIDR 2009 required logging before sending operation to DC Drawback: requires two messages and/or double logging to perform operation (e.g., update) TC DC1 2. Return image 1. Request before image 3. Log operation (generateLSN) 4. Send operation 5. Perform operation 6. Log operation success Our new protocol logs after operation returns from DC TC DC1 1. Locking (generate LSN) 3. Perform operation and send back before image 2. Send operation 4. Log operation Must deal with LSNs out of order on log Also required us to rethink TC/DC control protocol 7
Talk Outline Application Motivation Technical Motivation Deuteronomy Architecture Transaction Component Implementation Performance Wrap Up 8
Deuteronomy Architecture Client Request Interaction Contract Transaction Component (TC) 1. 2. Guarantee ACID Properties No knowledge of physical data storage 1. Reliable messaging At least once execution 2. Idempotence At most once execution Logical locking and logging Control Operations Record Operations 3. Causality If DC remembers message, TC must also Data Component (DC) 1. 2. 3. Physical data storage Atomic record modifications Data could be anywhere (cloud/local) 4. Contract termination Mechanism to release contract Storage 9
http://t3.gstatic.com/images?q=tbn:Jugn1tET8k8jYM:http://www.pc-net.co.cc/images/desktop-computer.jpghttp://t3.gstatic.com/images?q=tbn:Jugn1tET8k8jYM:http://www.pc-net.co.cc/images/desktop-computer.jpg Client Transaction Component Session Manager Log Manager Lock Manager . . . Session 1 Session 2 Session N Session Table Manager Record Manager Meta-data Management TC-DC Control Operations TC-DC Control Operations TC-DC Control Operations TC-DC Control Operations . . . Record/ Table Operations Record/ Table Operations Record/ Table Operations Data Component 1 Data Component N Data Component 2 Cloud Storage Cloud Storage Local Storage
http://t3.gstatic.com/images?q=tbn:Jugn1tET8k8jYM:http://www.pc-net.co.cc/images/desktop-computer.jpghttp://t3.gstatic.com/images?q=tbn:Jugn1tET8k8jYM:http://www.pc-net.co.cc/images/desktop-computer.jpg Client Thread forking and pooling Transaction Component Session Manager Log Manager Protect data structures Lock Manager . . . Session 1 Session 2 Session N Protect lock data from race condition. Thread aware and Session some thread management Block committing threads for log flush Logical locking Logical logging Table Manager Record Manager Block threads for conflict Meta-data Management Record/ Table operations Record/ Table Operations Record/ Table Operations . . . Record/ Table Operations Data Component 1 Data Component N Data Component 2 Cloud Storage Cloud Storage Local Storage
Talk Outline Application Motivation Technical Motivation Deuteronomy Architecture Transaction Component Implementation Performance Wrap Up 12
Record Manager An Insert Operation Example Receive request and dispatch a session thread 1 Client & Session Manager 2 insert record Call to lock manager Lock resource Generate Log Sequence Number (LSN) 1 Log Record LSN 4 Lock Lock TC Record Manager Log Manager Manager LSN 2 3 insert record , LSN Sends LSN & operation to DC 3 DC Call to log manager Log operation with LSN 4 13
Lock Manager Deuteronomy locking hierarchy: Table Record Partition Support locking of range read by using partitions, not next key locking SELECT * FROM Employees WHERE id > 10 AND id < 40 Partitions to lock [0, 30], [30, 60] So that inserts DO NOT have to know or test the lock on next key In charge of generating LSN before sending operation to data components 14
Log Manager Different from conventional log manager in two aspects: Need to coordinate TC s log with DC s cache Write Ahead Logging: Which updates are allowed to be made stable at DC Log truncation: Which updates must be made stable at DC Complexity: LSNs are stored out-of-orderon TC s log, but DC only understands LSN TC LSN 5 LSN 4 LSN 3 LSN 2 LSN 1 DC DC DC TC Physical Log LSN 4 LSN 1 LSN 2 LSN 5 LSN 3 What can DC write to stable storage? Log flushed Not flushed 15
Control Operations: End-Of-Stable-Log TC sends an LSN value eLSN from TC to all DCs For DC: Updates with LSN <= eLSN can be made stable. Updates with LSN > eLSN must not be made stable and must be forgettable. For TC: all log records with LSN <= eLSN must be flushed. Flushed (stable) Not flushed Physical Log LSN 4 LSN 1 LSN 2 LSN 6 LSN 3 LSN Vector LSN 1 LSN 2 LSN 5 LSN 6 LSN 3 LSN 4 eLSN=2 16
The Deuteronomy Project Built TC, DCs, test environment, and performed experiments Different flavors of DCs implemented Cloud DC Windows Azure used as cloud storage Collaborators: Roger Barga, Nelson Araujo, Brihadish Koushik, Shailesh Nikam Flash DC Storage manager from Communications and Collaboration Systems group at MSR Collaborators: Sudipta Sengupta, Biplob Debnath, and Jin Li TC Flash DC Cloud DC Buffer Pool Operation Log Windows Azure Flash Storage 17
Talk Outline Application Motivation Technical Motivation Deuteronomy Architecture Transaction Component Implementation Performance Wrap Up 18
Performance of TC Adapted TPC-W benchmark Controlled DC latencies from 2ms to 100ms 18000 2ms 16000 Operations per Second 14000 5ms 12000 10ms 10000 8000 20ms 6000 4000 40ms 2000 0 60ms 0 200 400 600 800 1000 100ms Number of Clients High latency requires high level of multithreading, which appears to impact throughput Ideas on improving throughput Threading mechanism Implementation language from C# to C/C++ 19
Conclusion Application & Technical Motivations Overview of project, teams, and development Architecture of our multithreaded TC A new TC:DC interface protocol to suit the cloud scenario Experiments that show good performance and the impact of cloud latency on performance 20
