《云数据管理:挑战与机遇》2.3.1 预备知识
预备知识
数据库由对象的集合组成,如x、y、z。假设每个对象都有一个值,所有对象的值构成了数据库的状态。通常情况下,这些状态必须满足数据库的一致性约束。数据库对象支持两种原子操作:针对x的读和针对x的写,或者r[x]和w[x]。事务的概念在数据库系统中至关重要。一个事务是按照一定偏序执行的操作的集合。事务ti执行的操作记作ri[x]和wi[x]。如果一个事务是正确的,即,如果一个事务在一致数据库上单独执行,那么该事务可以将数据库转换成另外一个一致状态。
事务的执行必须是原子的,即必须满足如下两个属性:
1. 事务之间互不干扰。
2. 事务中的操作要么全部执行,要么都不执行。
事务ti以commit(ci)或abort(ai)操作结束。并发控制协议可以确保并发执行的事务彼此之间互不影响。恢复协议可以确保all-or-nothing属性。
如果两个操作的执行顺序对结果有影响,即,如果其中一个是写操作,那么这两个操作是冲突的。给定一个事务集合T,T上的一个历史H是针对所有事务操作的偏序,该顺序反映了操作执行的顺序(事务顺序和冲突操作顺序)。
数据库管理系统必须满足ACID特性,即
原子性(atomicity):每个事务要么全部执行,要么都不执行,即all-or-none属性。
一致性(consistency):每个事务是一个一致的执行单位。
隔离型(isolation):事务之间互不影响。
持久性(durability):事务的效果是永久的。
当一个并发事务集合执行时,事务的正确性概念必须以每一个事务都是一致的(ACID中的C)为前提,因此,如果事务是隔离执行的,数据库将从一个一致状态转换成另外一个一致状态。因此,如果事务集合串行执行,那么可以保证其正确性。特别是,对于一个调度H中的任意两个事务ti和tj,如果ti的所有操作在H中都位于tj的所有操作之前,或者相反,那么H是串行的。
为了允许事务之间在一定程度上并发执行,产生了可串行化的概念。如果一个历史的执行结果与一个串行历史的执行结果等价,那么该历史是可串行化的。如果两个历史产生相同的结果,即所有的事务写入相同的值,我们认为这两个历史是等价的。由于我们不知道哪些事务执行写操作,事务就需要从相同的事务中读数据,最终写入的值也相同。不幸的是,识别可串行化的历史是NP完全问题[Papadimitriou, 1979]。因此,产生了一个更强的可串行性概念,称之为冲突可串行性。
回想一下,如果针对相同对象的两个操作中,至少有一个是写操作,那么这两个操作是冲突的。如果两个历史H1和H2定义在相同的操作集合之上(相应的事务集合也相同),并且这两个历史中所有的冲突操作的顺序都一致,那么H1和H2是冲突等价的。如果一个历史H和某一个串行历史Hs是冲突等价的,那么H就是冲突可串行化的。既然串行执行是正确的,那么就可以保证冲突可串行化历史也是正确的相关文章
- 从SQL改写到SQL重写,什么样的SQL才是好SQL?
- MariaDB新版本实力逆袭,不仅仅是MySQL的替代品
- 如何基于日志,同步实现数据的一致性和实时抽取?
- 如何利用Redis扩展数据服务、实现分片及高可用?
- 达梦、GBase、星瑞格,你用了哪个?
- 使用快照策略和镜像备份数据
- 风向标:数据库技术趋势解读
- 微店MySQL自动化运维体系的构建之路
- DBA呢?我的数据库又双叒叕连不上了!
- 比大数据还要可怕的是什么?没有数据!
- 15年老司机的DPM数据库性能分析产品研发之路
- 在Oracle专家眼中,MySQL sys Schema是怎样一种存在?
- 数据也会说谎:常见的数据造假三种形态!
- 巧用利器Powershell,让数据库自动化运维事半功倍
- 记一次区域DB突发变慢的SQL优化博弈
- 为什么我们用的系统这么烂?谁的锅?
- 罕见故障!数据库对象编号达到最大值,必须重新建库!
- 炉石传说罕见数据库事故!丢失30%数据,疑似误操作?
- 未来:数据是商品,你就是猎物
- 从小型网站到超大规模网站的MySQL参考架构