问基于多版本时间戳的并发控制

EN

假设T_i先发生，T_j先发生。假设T_i也写入x。t_j的第二次读取应该失败，因为T_i已经使用了x的值。T_i比T_j年轻，如果T_j使用最后提交的x版本，则如果T_i写入x将导致使用陈旧的值。

您需要在读、写或提交时中止写入事务t_j，因为可能会使用过时的值。如果写入事务没有中止，而且其他人读取和使用了旧值，则数据库不可序列化。因为如果您以不同的顺序运行事务，则会得到不同的结果。这就是所引用的文本所指的时间戳顺序。

任何两个同时读取相同值的数据都是危险的，因为它会导致数据库的视图不准确，从而显示不可串行化的顺序。如果三个事务正在运行，并且所有事务都使用x，则可序列化顺序未定义。您需要一次执行一次对x的读取，这将强制事务为单个文件，并查看最后一个事务的x。因此，t_i然后是t_j，然后是t_k，然后在下一个事务开始之前完成。

想一想，即使t_j不编写，它也会使用一个在技术上不存在于过时的数据库中的值，如果t_i编写的话，它就会忽略t_i的结果。

如果三个事务都读取x而不写x，那么同时运行它们是安全的。您需要预先知道所有三个事务都不会写入x。

正如白皮书可序列化快照隔离所证明的那样，这种危险的结构是两个读写依赖关系。但是读-写x和读x后面的读x也是危险的，因为如果两个事务同时运行，它需要可序列化的值是陈旧的，所以您会中止第二读x，因为使用x的事务比较年轻。

我写了一个仿真中的多版本并发实现。我的模拟模拟了100个线程，它们都试图读取和写入两个数字，A和B。它们希望将数字增加1。在模拟开始时，我们将A设置为1，B设置为2。

期望的结果是，在模拟结束时，A和B应该设置为101和102。只有在由于多版本并发控制而存在锁定或序列化的情况下，才能发生这种情况。如果您没有并发控制或锁定，由于数据竞争，这个数字将小于101和102。

当线程读取A或B时，我们遍历键A或B的版本，以查看是否有一个版本是<= transaction.getTimestamp()和committed.get( key ) ==。如果成功，它将该值的读取时间戳设置为上次读取该值的事务。rts.put("A"，事务)

在提交时，我们检查Rts.get(A).getTimestamp() != committingTransaction.getTimestamp()。如果此检查为真，则中止事务，然后重试。

我们还检查有人自交易开始以来 -我们不想覆盖他们的提交。

我们还检查每一次写入是否其他写入事务比我们年轻，然后我们中止。if语句位于一个名为shouldRestart的方法中，它在读取和提交时以及在所有涉及值的事务上调用。

public boolean shouldRestart(Transaction transaction, Transaction peek) {
    boolean defeated =  (((peek.getTimestamp() < transaction.getTimestamp() ||
            (transaction.getNumberOfAttempts() < peek.getNumberOfAttempts())) && peek.getPrecommit()) ||
            peek.getPrecommit() && (peek.getTimestamp() > transaction.getTimestamp() ||
                    (peek.getNumberOfAttempts() > transaction.getNumberOfAttempts() && peek.getPrecommit())
                    && !peek.getRestart()));

    return defeated;
}

请看这里的代码 && peek.getPrecommit()意味着，如果一个较晚的事务提前，而后一个事务尚未重新启动(中止)，则较年轻的事务可以中止。

在读取密钥期间，我们检查RTS，以查看它是否低于事务处理的读取值。如果是这样，我们中止事务并重新启动--队列中有人在我们前面，他们需要提交。

在大约300事务中止后，系统平均达到101和102。随着许多跑完远远低于200次尝试。

编辑:我更改了计算哪些事务获胜的公式。因此，如果另一个事务较年轻，或者其他事务的尝试次数较多，则当前事务将中止。这减少了尝试的次数。

编辑:之所以有较高的中止计数，是因为一个提交线程会被读取线程饿死，这些线程会因为提交线程而中止重新启动。当由于提前事务导致读取失败时，我添加了一个Thread.yield，这将重新启动计数减少到<200。