锁(Locks):保证了并发控制(CC)的正确性但又限制了系统的扩展性（Scalability）怎么办？
锁 (Locks): 保证了并发控制 (CC) 的正确性 但又限制了系统的扩展性 (Scalability) 怎么办？ 1
计算机系统本质是什么？，提供计算，通讯和数据处理的通用基础设施（包括硬件和软件）·不再只是操作系统和CPU芯片·也不是为特殊应用专制的硬件或开发的软件·除操作系统以外的主流系统有：·存系统·数据管理系统·虚拟机系统·互联网系统·有大规模应用软件系统，如微信，云系统中的资源分享和调度系统。。·计算机系统的开发和应用具有很严格的基础性·很多系统上创新都是来源于对系统基本结构的深刻认识·系统资源管理和社会分配体制有共性·思考和分析问题不应只限于技术层面·所有的算法和解决方案都可以在社会和日常生活中找到·系统研究的最终目的"Theproofofasystem'svalueisitsexistence."AlanPerlis
计算机系统本质是什么？ • 提供计算，通讯 和数据处理的通用基础设施（包括硬件和软件） • 不再只是操作系统和CPU芯片 • 也不是为特殊应用专制的硬件或开发的软件 • 除操作系统以外的主流系统有： • 存贮系统 • 数据管理系统 • 虚拟机系统 • 互联网系统 • 有大规模应用软件系统，如微信，云系统中的资源分享和调度系统 。 • 计算机系统的开发和应用具有很严格的基础性 • 很多系统上创新都是来源于对系统基本结构的深刻认识 • 系统资源管理和社会分配体制有共性 • 思考和分析问题不应只限于技术层面 • 所有的算法和解决方案都可以在社会和日常生活中找到 • 系统研究的最终目的 • “The proof of a system’s value is its existence.” Alan Perlis
Throughput drops after reaching peak (MysQl)sysbench,PKlookupsKernal mutexinSQLisa150000synchronization lock.Thisisexperimentselectsprimarykeysin5millions1rows eachbyusingthelock.PeakTX=154,236(64pros)50000·AfterthenTXdrops14%·7timeslowerthanthepeak(1024processes)256128882645121024ThreadsPerconaDBPerformance
Throughput drops after reaching peak (MySQL) 3 Kernal_mutex in SQL is a synchronization lock. This is experiment selects primary keys in 5 millions rows each by using the lock. • Peak TX =154,236 (64 pros) • After then TX drops 14% • 7 times lower than the peak (1024 processes) PerconaDB Performance
Latencyincreases as #threads increaseto contend locksSeirtcolFree(MPMC)600065004threadsusing5000spinlock running on4500IntelXeonL5640fora4000write-readworkload(dasp)aae3500comparedwiththe3000sameworkloadinlock2500freestyle200015001000ACMQueue,June20135000.20.30.60.70.10.40.50.80.9Quantile
Latency increases as # threads increase to contend locks 4 4 threads using spinlock running on Intel Xeon L5640 for a write-read workload compared with the same workload in lockfree style ACM Queue, June 2013
System Performance: High Throughput and Low LatencyOptimal PointLatency (locality)Throughput(parallelism)NumberofConcurrentProcesses
Number of Concurrent Processes Optimal Point Throughput (parallelism) Latency (locality) System Performance: High Throughput and Low Latency
Two Major Issues of Lock Usage.Waysof acquiringlocks:Minimizing network bandwidth:Minimizing overhead of waiting for locks:Maintaining a constant # of remote memory accesses per lockacquisition.Locksinconcurrencycontrol·Minimizing oreliminating unnecessary usage of locks·Minimizing execution and access latency inside critical section· Minimizing the size of the data structure to be locked·Maximizing scalability subject to serialized execution
Two Major Issues of Lock Usage • Ways of acquiring locks • Minimizing network bandwidth • Minimizing overhead of waiting for locks • Maintaining a constant # of remote memory accesses per lock acquisition • Locks in concurrency control • Minimizing or eliminating unnecessary usage of locks • Minimizing execution and access latency inside critical section • Minimizing the size of the data structure to be locked • Maximizing scalability subject to serialized execution 6
Distributed locks in production systemsFor each lock acquisition ina distributed system1. Entering the queue waiting for the lock (a remote access)2. Local spin to wait without consuming network bandwidth3. The process is informed for its turn (a remote access)4. Acquiring the lock entering the critical section (a remoteaccess).Constant number of remote accesses perlock acguisition:Network contention is minimized
Distributed locks in production systems For each lock acquisition in a distributed system 1. Entering the queue waiting for the lock (a remote access) 2. Local spin to wait without consuming network bandwidth 3. The process is informed for its turn (a remote access) 4. Acquiring the lock entering the critical section (a remote access) • Constant number of remote accesses per lock acquisition • Network contention is minimized 7
Two Phase Locking (2PL)·DBMsmustlockatuplebeforeatransactionreadsorwritesto it: Two types of locks: shared lock (read) & exclusive lock (write):Phase1:growingphase.Transaction can obtainlocksbut cannotreleaselocks.Phase2:Shrinkingphase.Transactioncanreleaselocksbutcannotobtainlocks.Variants of 2PL (based on how to avoid deadlocks):2PL-deadlockdetecfion:Abortsatransactionwhendeadlockhappens2PL-waitanddie.Oldtransactioncanwaityoungtransaction,notviceversa.2PL-woundwait:Immediatelyaborts atransactionifitslockingreguestis denied
Two Phase Locking (2PL) • DBMS must lock a tuple before a transaction reads or writes to it • Two types of locks: shared lock (read) & exclusive lock (write) • Phase 1: growing phase • Transaction can obtain locks but cannot release locks • Phase 2: Shrinking phase • Transaction can release locks but cannot obtain locks • Variants of 2PL (based on how to avoid deadlocks) • 2PL - deadlock detection • Aborts a transaction when deadlock happens • 2PL - wait and die • Old transaction can wait young transaction, not vice versa • 2PL – wound wait • Immediately aborts a transaction if its locking request is denied 8
Concurrency Control (CC).CC ensurescorrectresultsforconcurrentoperations·AbasiccomponentinOs,Ds,multiprocessors,databases,PL:Ensures serializability of data accesses to the shared data sets.Get results fast for high throughput and scalability·Optimistic Concurrency Control (OCC, Kung and Johnson,1981) has been used in several production systems: E.g., Microsoft Hekaton, Google App Engine, CoucDB, Silo,
Concurrency Control (CC) • CC ensures correct results for concurrent operations • A basic component in OS, DS, multiprocessors, databases, PL, . • Ensures serializability of data accesses to the shared data sets • Get results fast for high throughput and scalability • Optimistic Concurrency Control (OCC, Kung and Johnson, 1981) has been used in several production systems • E.g., Microsoft Hekaton, Google App Engine, CoucDB, Silo, . 9
Occ: How It Works.OCC executes g transaction in three phases:.Phase1:concurrentlocalprocessing:Reads tuples into aread set.Buffers writes into a write set.Phase 2:Validation in critical section.Validates whether serializability is guaranteed:Has any tuple in the read set been modified?.Phase 3:Commit the results in critical section or abort:Aborts: aborts the transaction if validationfails. Commits: installs the write set and commits thetransaction10
• OCC executes a transaction in three phases: • Phase 1: concurrent local processing • Reads tuples into a read set • Buffers writes into a write set • Phase 2: Validation in critical section • Validates whether serializability is guaranteed: Has any tuple in the read set been modified? • Phase 3: Commit the results in critical section or abort • Aborts: aborts the transaction if validation fails • Commits: installs the write set and commits the transaction OCC: How It Works 10