给客户做网站 赚钱吗,网站建设的关键问题,公众号与网站,介绍化工项目建设和招聘的网站Topic1#xff1a;distributed transactions concurrency control atomic commit
传统计划#xff1a;事务
程序员标记代码序列的开始/结束作为事务。
事务示例
x 和 y 是银行余额——数据库表中的记录。x 和 y 位于不同的服务器上#xff08;可能在不同的银行#x…Topic1distributed transactions concurrency control atomic commit
传统计划事务
程序员标记代码序列的开始/结束作为事务。
事务示例
x 和 y 是银行余额——数据库表中的记录。x 和 y 位于不同的服务器上可能在不同的银行。x 和 y 开始时都是 $10。T1 和 T2 是事务。 T1: 从 x 向 y 转账 $1。T2: 审计检查没有钱丢失。
事务操作
T1: T2:
begin_xaction begin_xactionadd(x, 1) tmp1 get(x)add(y, -1) tmp2 get(y)
end_xaction print tmp1, tmp2end_xaction事务的正确行为是什么
通常被称为“ACID”
原子性Atomic - 尽管有失败但要么全部写入成功要么一个也不写。一致性Consistent - 遵守应用程序特定的不变量。隔离性Isolated - 事务之间没有干扰——可串行化。持久性Durable - 提交的写操作是永久的。
什么是可串行化
当您执行一些并发事务并产生结果时“结果”既包括输出也包括数据库中的变化。如果满足以下条件则这些结果是可串行化的
存在一种串行执行事务的顺序这种顺序产生的结果与实际执行的结果相同。
串行意味着一次一个——没有并行执行。
这个定义应该让你想起线性一致性。
您可以通过寻找产生相同结果的顺序来测试执行结果是否是可串行化的。对于我们的例子可能的串行顺序是
T1; T2T2; T1
因此正确的可串行化的结果是
T1; T2x11 y9 “11,9”T2; T1x11 y9 “10,10”
两者的结果不同任何一种都可以接受。没有其他结果是可以接受的。实现可能已经并行执行了T1和T2但它必须仍然产生如同按照串行顺序执行一样的结果。
为什么可串行化很受欢迎
对程序员来说是一个简单的模型 程序员可以编写复杂的事务同时忽略并发性。 它允许对不同记录的事务进行并行执行。
事务可以在出现问题时“中止”
中止会撤销任何记录修改。事务可能会自愿中止 例如如果账户不存在或者y的余额小于等于0。 系统可能会强制中止例如为了打破锁定死锁。一些服务器故障会导致中止。应用程序可能会也可能不会再次尝试事务
分布式事务包含两个主要组成部分
并发控制提供隔离性/可串行化原子提交尽管有失败也能提供原子性
首先让我们谈谈并发控制
正确执行并发事务
事务的并发控制分为两类
悲观并发控制 在使用记录前对其加锁冲突会导致延迟等待锁 乐观并发控制 不加锁地使用记录提交时检查读/写操作是否可串行化冲突会导致中止重试称为乐观并发控制OCC 如果冲突频繁悲观并发控制更快如果冲突罕见乐观并发控制更快
今天的话题是悲观并发控制下周将讨论乐观并发控制FaRM。
“两阶段锁定”是实现可串行化的一种方式
两阶段锁2PL定义 事务在使用记录前必须获取记录的锁事务必须持有其锁直到提交或中止之后
我们例子中的两阶段锁定
假设T1和T2同时开始
事务系统会根据需要自动获取锁因此T1/T2中首先使用x的将获取锁另一个事务将等待直到第一个事务完全结束这阻止了非可串行化的交错执行
详细信息
每个数据库记录都有一个锁如果是分布式的锁通常存储在记录的服务器上 [图表客户端、服务器、记录、锁]但两阶段锁定不太受分布式影响 执行事务需要时获取锁首次使用时 add()和get()隐式获取记录的锁end_xaction()释放所有锁 所有锁都是排他性的在此讨论中没有读/写锁全名是“强严格两阶段锁定”与线程锁定相关例如Go的Mutex但更简单 显式的begin/end_xaction数据库在每条记录首次使用时自动加锁数据库在事务结束时自动解锁数据库可能会自动中止以解决死锁
保持锁直到提交commit或中止abort之后的原因是为了确保事务的整体原子性和一致性。如果在完成记录使用后立即释放锁可能会导致一些问题例如
如果T2在get(x)后立即释放x的锁T1就可以在T2的两次get()操作之间执行。结果T2可能会打印10,9这并不是一个可串行化的执行既不是T1;T2也不是T2;T1的顺序。如果T1写入x然后立即释放x的锁T2可以读取x并打印结果。但如果T1之后中止那么T2使用了一个实际上从未存在过的值。理论上我们应该中止T2这将是一个“级联中止”这样做会非常尴尬。
两阶段锁定2PL可能会导致死锁例如
T1 T2
get(x) get(y)
get(y) get(x)系统必须检测循环锁超时并中止一个事务。
两阶段锁定2PL是否会禁止一个正确的可串行化的执行
是的例如
T1 T2
get(x) get(x)put(x,2)
put(x,1)锁定会禁止这种交错执行但结果x1是可串行化的与T2;T1相同。
问题描述一个情况其中两阶段锁定比简单锁定产生更高的性能。
简单锁定在任何使用之前锁定每个记录在中止/提交后释放。
两阶段锁定2PL比简单锁定Simple Locking表现出更高性能的一个情况是
当事务访问的数据集合较小并且与其他事务的重叠较少时。在这种情况下2PL通过只在需要时锁定记录允许更多的并行执行。事务可以更快地完成其操作并释放资源减少了等待和阻塞的时间从而提高了整体系统性能。相反简单锁定策略要求事务在开始执行任何操作之前锁定其将访问的所有记录这会导致不必要的等待特别是在事务只需要读取一小部分其锁定记录的情况下。这种策略在高并发环境下性能较差因为它限制了并行操作的可能性增加了事务完成时间。
Next topic: distributed transactions versus failures
我们将开发一个称为“两阶段提交”的协议它被分布式数据库用于多服务器事务
我们想要的是“原子提交”
一群计算机在某项任务上合作每台计算机扮演不同的角色想要确保原子性全部执行或者全部不执行挑战故障性能
设置
数据在多个服务器之间分片事务在“事务协调器”TC上运行对于每个读/写TC向相关的分片服务器发送RPC 每个都是一个“参与者”每个参与者管理其数据分片的锁 可能有许多并发事务许多TC TC为每个事务分配唯一的事务IDTID每条消息每个表条目都用TID标记为了避免混淆
无故障时的两阶段提交
TC向AB发送put()get()等RPC 修改是暂定的只有在提交时才会安装。 TC进行到事务的末尾。TC向A和B发送准备PREPARE消息。如果A愿意提交 A回应YES。然后A处于“准备好的”状态。 否则A回应NO。B也是同样。如果A和B都说YESTC向A和B发送提交COMMIT消息。如果A或B任何一个说NOTC发送中止ABORT消息。如果A/B收到TC的提交消息他们将提交。 即他们将暂定记录写入真实数据库。并释放其记录上的事务锁。 A/B确认提交消息。
这个协议试图确保即使在分布式系统中发生故障时事务也能保持原子性确保所有参与的服务器要么都提交事务要么都不提交。 这为什么到目前为止是正确的
除非A和B都同意否则它们都不能提交。
如果B崩溃并重启会怎样
如果B在崩溃前发送了YESB必须记住尽管发生了崩溃因为A可能已经收到了COMMIT消息并提交了。所以B必须能够在重启后提交或不提交。
因此参与者必须写入持久的磁盘上的状态
B在说YES前必须在磁盘上记住包括修改过的数据。如果B重启磁盘显示YES但没有COMMIT B必须询问TC或等待TC重新发送。 与此同时B必须继续持有事务的锁。如果TC说COMMITB将修改的数据复制到真实数据。
如果TC崩溃并重启会怎样
如果TC可能在崩溃前发送了COMMITTC必须记住 因为一个工作者可能已经提交了。 因此TC必须在发送COMMIT消息前将COMMIT写入磁盘。并且如果它崩溃并重启后重复COMMIT 或者如果参与者询问即如果A/B没有收到COMMIT消息。 参与者必须过滤掉重复的COMMIT使用TID。
如果TC从B那里永远得不到YES/NO怎么办
也许B崩溃了并没有恢复也许网络出现了故障。TC可以超时并中止因为没有发送任何COMMIT消息。好处是允许服务器释放锁。
如果B在等待TC的PREPARE时超时或崩溃怎么办
B还没有对PREPARE做出回应所以TC不能决定提交所以B可以单方面中止并释放锁对未来的PREPARE响应NO
如果B回答了PREPARE的YES但没有收到COMMIT或ABORT怎么办
B可以单方面决定中止吗 不可以TC可能已经从两者那里得到了YES并且向A发送了COMMIT但在发送给B之前崩溃了。那么A将提交而B将中止这是错误的。 B也不能单方面提交 A可能已经投了NO。
所以如果B投了YES它必须“阻塞”等待TC的决定。
注意
提交/中止决定由单一实体——TC做出。这使得两阶段提交相对直接。惩罚是A/B在投了YES之后必须等待TC。
TC何时可以完全忘记一个已提交的事务
如果它从每个参与者那里收到了对COMMIT的确认。然后没有参与者会再次需要询问。
参与者何时可以完全忘记一个已提交的事务
在它确认了TC的COMMIT消息之后。如果它再次收到COMMIT并且没有该事务的记录 它必须已经提交并忘记了并且可以再次确认。
两阶段提交的视角
在事务使用多个分片上的数据时在分片数据库中使用但它有不好的声誉 慢多轮消息传递慢磁盘写入在准备/提交交换期间持有锁阻塞其他事务TC崩溃可能导致无限期阻塞同时持有锁 因此通常只在单一小领域中使用 例如不在银行之间不在航空公司之间不在广域网上
Raft和两阶段提交解决的是不同的问题
使用Raft通过复制来获得高可用性 即当一些服务器崩溃时仍能操作服务器都做相同的事情 使用2PC是当每个参与者做不同的事情时 并且所有参与者都必须做他们的部分 2PC不提高可用性 因为所有服务器必须运行才能完成任何事情 Raft不确保所有服务器都做某事 因为只需要大多数活着就可以了
如果你想要高可用性和原子提交怎么办
这里有一个计划。 TC和服务器应该每个都用Raft复制在复制的服务之间运行两阶段提交然后你可以在容忍故障的同时仍然取得进展你将在实验4中构建类似的东西来转移分片下次会议的Spanner使用了这种安排
FAT 为什么事务的原子性如此重要 所谓“事务”意味着事务内的步骤相对于故障和其他事务而言是原子性发生的。这里的原子性意味着“全部或无”。事务是某些存储系统提供的一项功能旨在简化编程工作。事务有用的一个例子是银行转账。如果银行想要从爱丽丝的账户转移100美元到鲍勃的账户如果在此过程中途发生崩溃导致爱丽丝的账户被扣除了100美元但鲍勃的账户未增加100美元这将非常尴尬。因此如果您的存储系统支持事务程序员可以编写如下内容 BEGIN TRANSACTIONdecrease Alices balance by 100;increase Bobs balance by 100;
END TRANSACTION事务系统将确保事务是原子的即使在某处发生故障也要么两者都发生要么都不发生。 两阶段锁定是否会产生死锁 是的。如果两个事务都使用记录R1和R2但以相反的顺序它们将各自获得其中一个锁然后在尝试获取另一个锁时发生死锁。数据库能够检测到这些死锁并解决它们。数据库可以通过锁获取的超时或者在事务之间的等待图中寻找循环来检测死锁。可以通过中止参与的其中一个事务来打破死锁。 可以同时有多个活跃的事务吗参与者如何知道一条消息是指哪个事务 可以有许多并发事务由许多事务协调器TC管理。TC为每个事务分配一个唯一的事务IDTID。每条消息都包括相关事务的TID。TC和参与者用TID标记他们表中的条目这样例如当一个COMMIT消息到达一个参与者时它知道哪些暂定记录要变成永久的以及要释放哪些锁。 如果必须中止一个事务两阶段提交系统如何撤销修改 每个参与者对记录的临时副本进行修改。如果参与者对TC的准备消息回答“是”参与者必须首先将临时记录值保存到其磁盘上的日志中这样如果它崩溃并重启它可以找到它们。如果TC决定提交参与者必须将临时值复制到真实数据库记录中如果TC决定中止参与者必须丢弃临时记录。 可串行化与线性一致性有什么关系 它们是来自不同社区的类似概念。两者都要求最终结果与某些串行执行相同。可串行化通常指的是涉及多个操作的整个事务。线性一致性通常指的是简单的读和写操作。还有一点是线性一致性要求等效的串行执行与实际执行的实时顺序相匹配而可串行化通常不要求这一点。 为什么在我们查看的设计中经常出现日志 一个原因是日志捕获了系统为事务选择的串行顺序这样例如所有副本以相同的顺序执行事务或者服务器在崩溃重启后按照与崩溃前相同的顺序考虑事务。另一个原因是日志是一种高效的方式将数据写入硬盘或SSD因为这两种媒介在顺序写入即追加到日志时要比随机写入快得多。、第三个原因是日志是一种方便的方式让崩溃恢复软件看到系统在崩溃前进行到哪一步以及最后的事务是否在日志中有完整记录因此可以安全地重放。也就是说日志是实现可崩溃恢复的原子事务的一种方便方式通过预写日志write-ahead logging。
