数据库中的回滚和调度？

Question

如果我们在以下调度中使用时间戳排序来进行并发控制：

我的助教说T2、T3、T5是运行的，而T4、T1是回滚的。我不这么认为，请问有专家能帮我们吗？（即在此调度中哪些事务回滚，哪些是完成的？）

更新：所有工作完成后，所有事务都提交。

- user4591951

---

我不明白你所问的问题。你是展示在单个会话中发生的一系列操作吗？还是多个会话？如果是多个会话，有多少个？事务隔离级别是什么？ - Justin Cave

因为你标记了Oracle，所以可以假设"write(n)"操作会立即执行COMMIT吗？或者COMMIT的顺序没有定义吗？ - ruudvan

@ruudvan 具体来说，这是一个旧的竞赛问题，也许对于Oracle没有假设，并且可能在每次写入后进行提交 :) 没有提到。 - user4591951

我认为这让很多人感到困惑，因为你将它标记为Oracle。在计算机科学中，有许多并发控制方法，不同的数据库使用不同的策略。从你问题的第一行开始，似乎你对基于时间戳的并发控制感兴趣。是这样吗？也许我们可以通过这个帮助你更进一步。但我建议你去掉Oracle标签，因为我认为它不适用于这里。 - ruudvan

是的，我是指你的链接 @ruudvan，如果不清楚请原谅。 - user4591951

Answer 1

通常情况下，读者不会阻塞写入者，写入者也不会阻塞读者。

第一个会话写入行并在提交或回滚之前持有行锁，此时其他会话将受此锁的阻塞以防止其写入，但仍可进行读取。

基于上述内容：

- T1 可以写入（y），因为没有其他会话写入 y，并且随后持有 y 上的锁。 - T2 永远不会写入，因此永远不会被阻塞。 - T3 在 T1 写入 y 后尝试写入 y，因此被阻塞。 - T4 写入（x），T5 的读取不会受到影响。 - T5 尝试写入 y，但被 T1 持有的锁阻塞。

尽管如此，这些都不应该导致回滚，并假设未发出显式提交或回滚。

- David Aldridge

---

这个问题有点棘手，但原则很简单。读者不会阻塞写者，写者也不会阻塞读者，写入需要独占锁。 - David Aldridge

Answer 2

我认为你用oracle标签把大家都搞糊涂了。我觉得你想要基于问题的第一行的基于时间戳的并发控制算法，这是计算机科学理论中相当常见的算法。 更易理解的链接。

另外，你对回滚的使用不正确，因为事务没有回滚而是重新启动。（这在oracle中也会发生）

该算法的工作原理如下 -

每当一个事务开始时，它都会被赋予一个时间戳。这样我们就可以知道应该应用事务的顺序。所以给定两个影响同一对象的事务，具有较早时间戳的事务应该在另一个事务之前应用。但是，如果错误的事务实际上首先呈现，它将被中止并必须重新启动。

基于此，让我们给我们的事务一个时间戳，如t = 1,2,3,4,5...

• T5在t=1开始。
• T2在t=2开始。
• T1在t=3开始。
• T3在t=4开始。
• T4在t=5开始。
• T5在t=6时有另一个操作，但其时间戳仍为t=1，因为时间戳是根据事务开始的时间分配的。

接下来，

数据库中的每个对象都有一个读取时间戳，在读取对象的数据时更新，以及一个写入时间戳，在更改对象的数据时更新。

一开始，X和Y的读取和写入时间戳都为0。

读取请求按以下方式处理：

If TS < W-ts(x) then
    reject read request and abort corresponding transaction
    else
    execute transaction
    Set R-ts(x) to max{R-ts(x), TS}

一个写请求的处理方式如下:

  If TS < R-ts(x) or TS < W-ts(x) then
   reject write request
   else
   execute transaction
   Set W-ts(x) to TS. 

让我们遍历对象并应用这些规则。

1. T5开始并读取X。TS₅=1。执行顺利。设置RTS（x）= 1。
2. T2开始并读取Y。TS₂=2。执行顺利。设置RTS（Y）= 2。
3. T1开始并写入Y。TS₁=3。RTS（Y）= 1。WTS（Y）=0。写入完成。设置WTS（Y）= 3。
4. T3开始并写入Y。TS₃=4。RTS（Y）= 1。WTS（Y）= 3。写入完成。设置WTS（Y）= 4。
5. T4开始并写入X。TS₄=5。RTS（x）= 1。WTS（x）=0。写入完成。设置WTS（x）= 5。
6. T5进行写入（y）。TS₅=1。RTS（y）= 1。WTS（y）= 4。TS₅< WTS（y）。事务被回滚并以新的时间戳重新启动。（可能是t = 7）

因此，这给我们提供了一个不同于您的TA的答案，即仅T5被回滚并重新启动。

我很想得到纠正，并了解为什么T4和T1被中止并重新启动。

- ruudvan

Answer 3

"读者不阻塞写作者，写作者也不会阻塞读者"，正如@DavidAldridge所说。因此，事务3将等待事务1，而事务5将等待事务1和3。它们可以根据数据库设置的参数长时间等待，等待n秒或根本不等待。在Oracle中，就是这样工作的。由于这是一个竞赛问题，我假设逻辑并跟进。"

这段内容涉及解释和尝试遵循给定信息。此处给出的信息是：时间戳排序用于并发控制。然后他给出了T1、T2直到T5。我认为T1首先执行，然后是T2等等，因为事务总是被序列化执行：一个接一个，基于它们的时间戳。我认为，如果一个人认为“T5读取（x）”是第一个事务，仅仅因为文本的排列方式，那么就是添加了不存在的信息。它说时间戳排序，并给出了T1、T2……逻辑上意味着一个接一个。没有任何事务会回滚，它们只是等待，不仅因为一个事务可能持有锁，而其他事务也试图获取锁，就会自动回滚。在Oracle中，只有在死锁的情况下事务才会自动回滚。既然情况似乎不是这样，那么就没有回滚。

- Eliandro

---

哪一个是回滚操作，哪一个不是？ - user4591951

Answer 4

不必用我自己的话来解释，这里有一个有用的MSDN链接，展示了ROLLBACK TRANSACTION及其工作原理。

https://msdn.microsoft.com/en-us/library/ms181299.aspx?f=255&MSPPError=-2147217396

任何问题都可以随时问我。

- Clayton C

Answer 5

关于锁，它取决于您的数据库所设置的隔离级别。

微软对隔离级别的定义如下： 事务隔离级别控制： 1. 在读取数据时是否会被锁定，以及请求何种类型的锁。 2. 读取锁定的时间长度。 3. 是否阻塞读操作，以引用其他事务修改的行： a. 直到该行的独占锁被释放。 b. 检索语句或事务开始时存在的已提交版本的行。 c. 读取未提交的数据修改。

来源：https://technet.microsoft.com/en-us/library/ms189122(v=sql.105).aspx 例如，如果您的隔离级别设置为REPEATABLE READ： "指定语句不能读取其他事务已修改但尚未提交的数据，并且在当前事务完成之前，没有其他事务可以修改当前事务已读取的数据。"

来源：https://technet.microsoft.com/zh-cn/library/ms173763(v=sql.105).aspx

- Peheje