Consistency for multiple-objects, multiple-servers

1. 多对象，多分布式服务器
2. 假设：我们会忽略失败
   • 在当今的一致性机制的情况下，为了容错，大多数系统使用一种记录形式，在操作之前将信息写下来，从简单故障中恢复。
   • 我们将在课程后面讨论失败/恢复问题，就像我们如何使用日志记录重放并恢复到一致状态一样。

Case I: Single Server

1. 背景：数据库研究人员
2. 定义：“事务”
   • 读取+写入全局状态的集合
   • 作为单一的“不可分割的”操作出现
   • 用于可靠存储的标准模型
3. 事务的理想特征
   • 原子性，一致性，隔离性，耐久性
   • 也被称为“ACID”首字母缩写！

事务：ACID属性

1. Atomicity：每笔交易完全完成，或被中止。如果中止，应该对共享的全局状态没有影响。

   • 示例：更新多台服务器上的帐户余额

2. Consistency：每个事务保存一组关于全局状态的不变量。 （确切的性质是依赖于系统的）。

   • 例如：在一个银行系统中，保守法则是$$

3. Isolation：也意味着可串行化。 每个事务都像是唯一具有RD / WR共享全局状态的事务一样执行。

4. Durability：一旦事务完成或“提交”，就不会有回头。 换句话说，没有“撤消”。

5. 事务也可以嵌套

6. “Atomic Operations” => Atomicity + Isolation

A Transaction Example: Bank

1. Array Bal[i] stores balance of Account “i”
2. Implement: xfer, withdraw, deposit

转账 取款 存钱

3. 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

4. 使用锁来包装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

1. 为锁的状态建立一个“等待”图。 顶点代表交易。 如果事务i正在等待事务j持有的锁，则从顶点i到顶点j的边。
2. 在这种情况下，会发生什么？ =>周期是一个死锁
3. 用它的锁ID标记边缘。 对于任何循环，都必须有一对边（i，j），（j，k）用值x和y标记，使得x> y。 这意味着事务j持有锁x，并且想要锁y，其中x> y。 这意味着j没有按照正确的顺序获得锁定。
4. 一般方案称为2阶段锁定
   • More precisely: strong strict two phase locking

2-Phase Locking

1. 一般的两阶段锁定

   • 阶段1：获取或升级锁定（例如读取=>写入）
   • 阶段2：释放或解除锁定

2. 严格的2阶段锁定

   • 阶段1:(和以前一样）
   • 阶段2：只在事务结束时释放WRITE锁

3. 强严密的2阶段锁定

   • 阶段2：仅在事务结束时释放所有锁。
   • 最常见的版本，需要ACID属性

4. 为什么不总是使用 strong-string 2-phase locking？

   • 事务可能不会提前知道它需要的锁

     
     image.png

5. 其他方法来处理死锁

   • 锁管理器建立一个“等待”图。 找到一个循环，选择违规交易和强制中止
   • 使用超时：交易应该很短。 如果碰到时间限制，找到等待锁的交易并强制中止。

交易 - 分为两个阶段

1. 阶段1：准备工作：

   • 确定要做什么，如何改变状态，而不是实际改变状态。
   • 生成锁定设置“L”
   • 生成更新列表“U”

2. 阶段2：提交或中止

   • 一切正常，然后更新全局状态
   • 事务不能完成，按原样的全局状态离开
   • 在任何一种情况下，RELEASE ALL LOCKS

Example

image.png

Question: So, what would “commit” and ”abort” look like?

commit.png abort.png