Consistency for multiple-objects, multiple-servers
- 多对象，多分布式服务器
- 假设：我们会忽略失败
- 在当今的一致性机制的情况下，为了容错，大多数系统使用一种记录形式，在操作之前将信息写下来，从简单故障中恢复。
- 我们将在课程后面讨论失败/恢复问题，就像我们如何使用日志记录重放并恢复到一致状态一样。
Case I: Single Server
- 背景：数据库研究人员
- 定义：“事务”
- 读取+写入全局状态的集合
- 作为单一的“不可分割的”操作出现
- 用于可靠存储的标准模型
- 事务的理想特征
- 原子性，一致性，隔离性，耐久性
- 也被称为“ACID”首字母缩写！
事务：ACID属性
-
Atomicity：每笔交易完全完成，或被中止。如果中止，应该对共享的全局状态没有影响。
- 示例：更新多台服务器上的帐户余额
-
Consistency：每个事务保存一组关于全局状态的不变量。 （确切的性质是依赖于系统的）。
- 例如：在一个银行系统中，保守法则是$$
Isolation：也意味着可串行化。 每个事务都像是唯一具有RD / WR共享全局状态的事务一样执行。
Durability：一旦事务完成或“提交”，就不会有回头。 换句话说，没有“撤消”。
事务也可以嵌套
“Atomic Operations” => Atomicity + Isolation
A Transaction Example: Bank
- Array Bal[i] stores balance of Account “i”
- Implement: xfer, withdraw, deposit
转账
取款
存钱
- Bal[x] = 100, Bal[y]=Bal[z]=0
- Two transactions => T1:xfer(x,y,60), T2: xfer(x,z,70)
- ACID Properties: T1 or T2 in some serial order
- T1; T2: T1 succeeds; T2 Fails. Bal[x]=40, Bal[y]=60
- T2; T1: T2 succeeds; T1 Fails. Bal[x]=30, Bal[z]=70
- 如果我们不注意ACID？ 有没有比赛条件？
- 用读/写交错T1，T2更新Bal [x]
- Bal[x] = 30 or 40; Bal[y] = 60; Bal [z] = 70
- 为了一致性，sumbalance()
- State invariant sumbalance=100 violated! We created $$
image.png
-
使用锁来包装xfer
image.png
由于全局锁定所有帐户而出现连续瓶颈！
image.png
这能改善吗？不能！
为什么？ 提早释放锁定可能会导致一致性违规。 一些其他交易（例如，sumbalance）可以看到账户i的递减值，但计数j的未递增值。
image.png
fix：当所有状态变量的更新完成时释放锁定。
我们完成了吗？
不，死锁：Bal [x] = Bal [y] = 100。 xfer（x，y，40）和xfer（y，x，30）
image.png
通常规定：根据一致的全局顺序获得锁定
2-Phase Locking
image.png
- 为锁的状态建立一个“等待”图。 顶点代表交易。 如果事务i正在等待事务j持有的锁，则从顶点i到顶点j的边。
- 在这种情况下，会发生什么？ =>周期是一个死锁
- 用它的锁ID标记边缘。 对于任何循环，都必须有一对边（i，j），（j，k）用值x和y标记，使得x> y。 这意味着事务j持有锁x，并且想要锁y，其中x> y。 这意味着j没有按照正确的顺序获得锁定。
- 一般方案称为2阶段锁定
- More precisely: strong strict two phase locking
2-Phase Locking
-
一般的两阶段锁定
- 阶段1：获取或升级锁定（例如读取=>写入）
- 阶段2：释放或解除锁定
-
严格的2阶段锁定
- 阶段1:(和以前一样）
- 阶段2：只在事务结束时释放WRITE锁
-
强严密的2阶段锁定
- 阶段2：仅在事务结束时释放所有锁。
- 最常见的版本，需要ACID属性
-
为什么不总是使用 strong-string 2-phase locking？
-
事务可能不会提前知道它需要的锁
image.png
-
-
其他方法来处理死锁
- 锁管理器建立一个“等待”图。 找到一个循环，选择违规交易和强制中止
- 使用超时：交易应该很短。 如果碰到时间限制，找到等待锁的交易并强制中止。
交易 - 分为两个阶段
-
阶段1：准备工作：
- 确定要做什么，如何改变状态，而不是实际改变状态。
- 生成锁定设置“L”
- 生成更新列表“U”
-
阶段2：提交或中止
- 一切正常，然后更新全局状态
- 事务不能完成，按原样的全局状态离开
- 在任何一种情况下，RELEASE ALL LOCKS
Example
image.png
Question: So, what would “commit” and ”abort” look like?
commit.png
abort.png
