中国人民大学：从根说起—可串行化理论的光与影

从根说起— 可串行化理论的光与影演讲人：李海翔 @那海蓝蓝https://live.csdn.net/room/csdnlive1/8XwRwx6K2023年 1024程序员节1. 第三代分布式数据库（1）--踢球时代2. 第三代分布式数据库（2）--创新之源3. 第三代分布式数据库（3）--一致性八仙图2023年 中国数据库技术大会目录CONTENTS什么是“可串行化理论”？可串行化理论的“光”可串行化理论的“影”凭什么同时保证数据一致性与性能？▶1 什么是“可串行化理论”？我们只是熟悉它（或只是听说过）？ 还是真的掌握了她？1 什么是“可串行化理论”？• 理论层面• 真实含义• 实践层面• 串行能带来数据异常不？123？1 什么是“可串行化理论”？文献年份并发算法采用的冲突模式可串行化实现RWWRWW[247]1976Locking 事务和一致性并发度等概念被Jim Grey提出[245、246]1976Locking———提出2PL协议，定义了被广泛使用的、用于验证事务并发执行正确性的“serial equivalence”标准，对可串行化的概念进行了形式化的描述[229] 1979Locking是是是对于RR模式，读操作施加读锁互斥其它并发事务发生，实现可串行化。采用了RW、WR、WW三种冲突模式是用于弱于可串行化的其它隔离级别[261]1979Locking是是是提出“STRICT SERIALIZABILITY”和冲突图等[166] 1982 OCC+DTA最早DTA是是避免基于锁替代临界区，互斥其它并发事务发生写写冲突，发生了RW、WR冲突则动态调整事务的时间戳范围，基于提交时间戳（通过协商动态获得）进行排序实现可串行化[126]1983TO算法 提出基于时间戳的并发访问控制协议[157]2014OCC+DTAMaaT是是避免基于提交时间戳排序，但时间戳是在RW、WR二种冲突模式种通过协商动态获得；在被写的数据项上加软写锁，避免第二次被写（避免写写冲突），软写锁替代临界区的作用[129]1984OCC/BOCC—是避免基于临界区互斥其它并发事务进入验证阶段避免WW冲突，并先进入临界区者排序在前，完成可串行化排序目的；BOCC已经提交事务的写集和本事务的读集比较；FOCC本事务的写集和活跃事务的读集比较OCC/FOCC是 [113]1995无———对多种数据异常进行了形式化定义，没有提及可串行化实现方式（基于封锁技术定义数据异常和隔离级别）[226]2000无———对多种数据异常进行了形式化定义，没有提及可串行化实现方式（基于封锁、乐观、MVCC技术定义数据异常和隔离级别）[114]2009MVCC/SSI——避免理论方面是通过打破依赖图中的环实现可串行化，实践中是通过破坏双方向的RW冲突发生实现可串行化（双方向的读-写冲突是形成环的必要条件）。读操作基于快照，禁止WW冲突发生[79]2012MVCC/WSI———提交阶段，对于本事务的读集数据，检查是否被其他事务修改，即检查RW冲突（类似FOCC的方式）。读操作基于快照1 什么是“可串行化理论”？目录CONTENTS什么是“可串行化理论”？可串行化理论的“光”可串行化理论的“影”凭什么同时保证数据一致性与性能？▶2.1 “可串行化理论”解决了哪些问题？• 理论层面• 真实含义• 实践层面• 串行能带来数据异常不？123？ü 完整性约束?ü ACID的C？ü 理论和实践不一致2.2 “可串行化理论”的价值在哪里？01STEP02STEP04STEP03STEP解决部分异常现象没有数据异常的全集，就没有好的鉴别力提出普遍认可的算法不能得到高效的并发算法提供提高性能的手段不能认知隔离级别的弊端似乎有理的直观理论不能有效认知可串行化理论的边界与缺陷2.2 “可串行化理论”的价值在哪里？来走路一一个满目疮痍的世界一个满目疮痍的世界2.2 “可串行化理论”的价值在哪里？目录CONTENTS什么是“可串行化理论”？可串行化理论的“光”可串行化理论的“影”凭什么同时保证数据一致性与性能？▶3.1 “可串行化理论” 不能解决哪些问题？经典死锁问题绑匪问题s = W1[x1] W2[y1] W2[x2] W1[y2] W3[x3]s` = W2[y1] W2[x1] W1[x2] W1[y2] W3[x3]s`是一个串行化调度（T2→T1→T3）打电话T1T2T1W1[x1] W2[x2]W2[y1] W1[y2] 3.2 “可串行化理论”的缺陷在哪里？01STEP02STEP04STEP03STEP问题描述不清晰没有数据异常的全集，范围有限解决方法片面盲人摸象式的并发算法不能描述性能用隔离级别解决性能，非王道似诡道理论对产品指导有限不能有效认知可串行化理论的边界与缺陷目录CONTENTS什么是“可串行化理论”？可串行化理论的“光”可串行化理论的“影”凭什么同时保证数据一致性与性能？▶4.1凭什么同时保证数据一致性与性能？用户：要求高性能开发者：用弱隔离级别用户：要求数据正确开发者：主动加锁数据库：性能降低Select…For Update数据库使用怪圈方法：1 量化所有异常2 去掉隔离级别3 量化并发算法4 改变“可串行化理论”—串行思路变为并发思路世界从此变得简单4.1凭什么同时保证数据一致性与性能？01不02破04立03不新并发算法已实现新一致性级别已建立一致性与并发理论将发布所有数据异常已解决分布式数据库理念第6到第8篇，对比阅读更佳；读完一轮后，再返回头重读第一篇和第二篇，重新品味或批评其中的背景和观点，也许更有帮助。1. 第三代分布式数据库（1）--踢球时代2. 第三代分布式数据库（2）--创新之源3. 第三代分布式数据库（3）--一致性八仙图4. 第三代分布式数据库（4）--为什么要100%保证数据的正确性？（上）5. 第三代分布式数据库（4）--为什么要100%保证数据的正确性？（下）6. 第三代分布式数据库（5）--一无是处的MySQL7. 第三代分布式数据库（6）--没有价值的隔离级别8. 第三代分布式数据库（7）--比较拉胯的PostgreSQL 分布式原理1. 分布式原理（1）--CAP始末（上）2. 分布式原理（1）--CAP始末（下）3. 分布式原理（2）--分布式一致性4. 分布式原理（3）--依赖物理时间引发的问题5. 分布式原理（4）--逻辑时钟6. 分布式原理（5）--向量时钟7. 分布式原理（6）--混合逻辑时钟8. 分布式原理（7）--Paxos共识协议9. 分布式原理（8）--Paxos共识协议的改进与扩展10. 布式原理（9）--Raft共识协议11. 分布式原理（10）--再聊一致性谢谢观看