Operating Systems
Distributed Systems
4160 – Distributed and Parallel Computing
DB background • Data
Copyright By PowCoder代写 加微信 powcoder
– The unit is “page”, 8KB
• You update 1 item, you update a page
– Hot page in data buffer and full data (index/row/column) on data disk
• Unless MVCC, otherwise in-place update
– Data Buffer full? Flush updates to data disk in batch
• May flush updates from in-flight transaction to disk • WAL (Write-Ahead Logging)
– Any write to the data disk MUST write the update log to the log disk first
•
– Write to data disk vs log disk: random vs sequential write
More DB background
• On txn T commit: must flush log entries of T to log
– Note: Updates on the data may NOT flush to the data disk even it is committed
– Keep hot items in data buffer is fine (as log is persisted) • Crash and recovery:
– UNDO incomplete transactions with persisted partial updates
– REDO completed transactions with un-flushed updates
Amazon Cloud DB
• 1st generation
– MySQL on EC2
• Fault tolerance
– HDD dies… • 2nd generation
Physical Server
(not for cust. data)
• Too much network traffic HDD
• For performance reason
– Chain Replication (EBS) is within the same data center
– But then can’t survive data-center level crash CR
Physical Server
3rd generation – RDS • EBS on 4 data centers
• Network issue
– Too slow (writing log and data…)
CR CR CR CR
SG Taipei Tokyo Local
Physical Server
4rd generation – Aurora
• A new DB that is natively designed for the cloud
• 2 replicas x 3 availability zone • But even faster, how?
Physical Server
R3 R4 R1 R2
• Traditional DB: ship log entries to remote log disk on commit, ship data updates to remote data disk on buffer full
• Aurora: ship log entries and reconstruct the index/data from log at the destination
– “The log is the database”
– Though trivial, need to write a new DB software
• Use Quorum-based replication
Replication Scheme in DB
• Synchronous
• Asynchronous • Quorum-based
Synchronous replication
lWrite-all Read any lWrite latency:
nDetermined by the slowest one
lStrong durability: nN fresh copies
l Availability:
na node die?
l writes all available; read any available
Asynchronous replication
lWrite-primary
lasync write-sets to secondaries
lFast response time
lIf nothing goes wrong, eventually all replicas are
consistent
Quorum-Based replication
l N replicas, each has a vote
l A read has to obtain R votes to proceed l A write has to obtain W votes to proceed
l Two constraints to ensure R ∩ W is non-empty l W+R > N
l W > N/2 l Example:
l N=6, W=4, R=3 //Aurora l N=6, W=5, R=2
l Write returns only when it successfully writes to a quorum W of replicas l Updated item has a new version number
l Read from a quorum R of replicas
l So, the latest copy must be there
l Return the copy with the highest version number l Aurora optimization:
n In normal operation, it keeps tabs of which replica(s) have the latest version of a page and just go straight to that replica for higher efficiency
l WW conflict:
l Since only 1 write can get the quorumàget serialized
Read-only queries are the majority
lSetup a R/O secondary DB instance to read-only (get read quorum etc)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com