Thomas 写入规则

引言

在数据系统中，高效且无错误地运行并发事务非常重要。可串行化是帮助我们实现这一目标的方法或概念之一，因为它使并发执行的事务即使按某种串行顺序执行也能给出相同的输出。

可串行化通过各种方法实现，其中之一是时间戳排序（最重要和最有效的方法）。然而，这种时间戳排序的基本过程效率低下，非常保守，甚至会拒绝一些可串行化的调度。因此，为了解决时间戳排序的这一限制，引入了Thomas 写入规则。本文将深入介绍 Thomas 写入规则、条件、工作原理和实际应用。

什么是 Thomas 写入规则？

Thomas 写入规则为协议提供可串行化顺序的保证。它改进了基本的时间戳排序算法。

基本的 Thomas 写入规则如下：

• 如果 TS(T) < R_TS(X)，则事务 T 被中止并回滚，操作被拒绝。
• 如果 TS(T) < W_TS(X)，则不执行事务的 W_item(X) 操作并继续处理。
• 如果条件 1 和条件 2 均未发生，则允许事务 Ti 执行 WRITE 操作，并将 W_TS(X) 设置为 TS(T)。

规则细分

规则 1：因过时读取而中止

因此，假设事务 q 向数据项 X 写入了某些内容，但其时间戳小于上次读取的时间戳，这意味着某个时间戳尚未到来的事务已经读取了 X。如果您现在允许 q 写入，那将意味着事务正在写入的值将出现在时间戳顺序中的读取操作之前，这破坏了可串行化。因此，事务被中止。

规则 2：跳过过时写入

此规则表示，如果 q 的时间戳小于最新写入时间戳，则新事务已写入 X。因此，q 的写入已过时（任何事务都不会读取它）。您可以忽略此写入操作，而不是中止整个事务。

规则 3：执行有效写入

如果以上规则或条件均未满足，则事务 q 的写入是有效的，执行写入操作，然后将 X 的写入时间戳更新为 q 的时间戳。

时间戳排序

在深入了解之前，了解时间戳排序的基本概念至关重要。在这里，每个事务在开始时都被分配一个唯一的时间戳；此分配的时间戳稍后用于确定可串行化的顺序。

每个项目（事务）总共维护两种类型的时间戳

• 读取时间戳 (R_TS(X))：表示成功读取项目 X 的最大时间戳。
• 写入时间戳 (W_TS(X))：表示成功写入项目 X 的最大时间戳。

基本时间戳排序算法确保每个事务遵循一个事务顺序；如果任何事务违反此顺序，则会重新启动或删除。由于此严格规则，您可能实现可串行化，但仍面临许多实际可串行化调度的拒绝。Thomas 写入规则的作用就在于此。

Thomas 写入规则的工作示例

如果我们使用 Thomas 写入规则，那么可以允许一些可串行化调度，这些调度不与可串行化冲突，如下图所示

图：不是冲突可串行化的可串行化调度

在上图中，T1 的读取先于 T1 对同一数据项的写入。此调度不与冲突可串行化。

Thomas 写入规则检查 T2 的写入从未被任何事务看到。如果我们删除事务 T2 中的写入操作，则可以获得冲突可串行化调度，如下图所示。

图：冲突可串行化调度

Thomas 写入规则的优点

• 减少中止：基本时间戳排序导致太多不必要的中止，Thomas 写入规则通过忽略过时的写入来减少中止。
• 提高吞吐量：中止次数减少导致重启次数减少，这意味着开销更少，系统资源利用率更高，从而提高了吞吐量。
• 更高的调度接受度：Thomas 写入规则比普通时间戳排序接受更多的调度，因为它更宽松，这会影响高并发环境。
• 维护可串行化：Thomas 写入规则更宽松，但它也确保所有执行都是可串行化的，从而维护数据一致性。

Thomas 写入规则的局限性

• 时间戳管理：如果您希望 Thomas 写入规则正常工作，则需要维护每个数据项的准确读取和写入；这会带来一些额外的负载。
• 确保可串行化：Thomas 写入规则确保视图可串行化，但不确保冲突可串行化，因为视图可串行化弱于冲突可串行化。
• 写入过时场景：此规则仅适用于在能够找到写入过时场景时才有效，而不适用于事务的写入将来可能被读取的情况。
• 有效性：如果大多数事务是当前事务或时间戳非常接近，则 Thomas 写入规则效果不佳。

协议比较

Thomas 写入规则的应用

Thomas 写入规则主要应用于需要高并发、低事务中止率和最小冲突开销的系统。

它最常用于

• 银行系统，用于减少事务中止，因为这可能导致重大延迟和问题。
• 分布式数据库，方便多个用户访问而没有任何冲突。
• 也用于处理实时数据的分析系统。
• 电子商务事务管理，便于处理事务和高效管理。
• 它也用于现代 NoSQL 数据库，如 Cassandra 和 Google Spanner，以不同的名称，如“最后写入胜出”或“冲突解决”，因为它确定最新的写入并维护一致性。

实际实施注意事项

Thomas 写入规则易于理解，但在实际应用中需要仔细处理和实施。

• 时间戳应唯一分配，为此使用逻辑时钟、系统时钟或混合逻辑时钟。
• 应正确跟踪读取和写入时间戳。
• 应集成适当的恢复系统以应对紧急情况。
• Thomas 写入规则还可以与多版本并发控制 (MVCC) 集成。在 MVCC 中，维护数据项的版本，同样可以丢弃过时的写入。

结论

Thomas 写入规则是一种高效的协议或方法，可以优化调度和事务。它优于基于基本时间戳的并发控制，因为它跳过或忽略过时的写入，并允许事务继续进行而无需不必要的中止。此外，请记住，Thomas 写入规则允许的调度属于视图可串行化（如果调度保留了最终状态和事务的读取，就像在某个串行可串行化中一样，则该调度被视为可串行化）。

常见问题解答

1. 数据库系统中的 Thomas 写入规则是什么？

答： Thomas 写入规则是基本时间戳排序协议的升级或更好的协议。它在允许调度执行方面没有那么严格，因为它通过忽略一些过时的写入操作来允许它们，从而在不损害可串行性的情况下增加了被接受的调度数量。

2. Thomas 写入规则如何优于基本时间戳排序？

答：在基本时间戳排序中，即使对于小的、无害的写入冲突（例如过时的写入），事务也会被中止。然而，Thomas 写入规则跳过或忽略这些类型的无害写入冲突，允许这些调度同时保留可串行性。这减少了那些不必要的中止。

3. Thomas 写入规则的三个主要条件是什么？R_TS(X) 和 W_TS(X) 在此规则的上下文中代表什么？

答案

• 如果 TS(T) < R_TS(X)，中止事务。
• 如果 TS(T) < W_TS(X)，忽略写入操作。
• 否则，执行写入并更新 W_TS(X)。

TS(T)：T 的时间戳

R_TS(X)：读取数据项 X 的事务的最新时间戳。

W_TS(X)：写入数据项 X 的事务的最新时间戳。

4. 什么是写入过时？

答：写入过时意味着由于时间戳排序，任何事务都不会读取该写入。可以忽略或跳过这些类型的写入，因为它们对事务的最终状态或任何其他事务没有影响。

5. Thomas 写入规则是冲突可串行化的吗？

答：不，Thomas 写入规则并非总是冲突可串行化的。此规则允许的调度可能不是冲突可串行化的，但它们始终是视图可串行化的，视图可串行化弱于冲突可串行化，但仍然是可串行化的正确形式。

6. 在哪种类型的系统中 Thomas 写入规则最有利？

答： Thomas 写入规则主要用于对高并发系统有利，例如分布式数据库、电子商务平台、银行数据库和实时分析，在这些系统中，最大程度地减少中止和重启非常重要。

7. Thomas 写入规则如何影响事务吞吐量？

答：通过最大程度地减少事务中止或重启的数量，并允许忽略更多无害的写入操作，它显著提高了系统的整体吞吐量和性能。

8. Thomas 写入规则是否适用于实时或时间关键系统？为什么或为什么不？

答：不总是。虽然它提高了并发性，但实时系统可能不会受益，因为忽略写入可能导致响应时间的不可预测性。这些系统通常需要严格的控制和确定性行为，而 Thomas 写入规则可能会损害这些。