如何实现软件事务内存？

发布于 2024-08-08 13:13:16 字数 281 浏览 4 评论 0原文

就实际的低级原子指令和内存栅栏（我假设它们被使用）而言，您如何实现STM？

对我来说神秘的部分是，给定一些任意的代码块，您需要一种方法来返回并确定每个步骤中使用的值是否有效。您如何做到这一点以及如何有效地做到这一点？这似乎也表明，就像任何其他“锁定”解决方案一样，您希望使关键部分尽可能小（以减少冲突的可能性），对吗？

另外，STM 是否可以简单地检测“在执行计算时另一个线程进入该区域，因此计算无效”，或者它是否可以实际检测是否使用了破坏值（因此幸运的是，有时两个线程可以同时执行相同的关键部分，而无需需要回滚）？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

回忆躺在深渊里 2024-08-15 13:13:16

有些论文可能确实很难阅读，但有两篇非常清晰简洁：

事务锁定II，Dave Dice，Ori Shalev，Nir Shavit，用任何语言描述了“TL2”STM 算法。

Deuce：Java 中的非侵入式软件事务内存，Guy Korland、Nir Shavit、Pascal Felber< /a> 它解释了一个加载时类转换器，它将常规 java 类转换为内存中的类，这些类具有额外的字节码来执行 STM。这与问题相关，因为本文解释了如何将没有 STM 的代码机械地转换为任何 OO 语言中执行 STM 的代码。

Deuce 框架允许您插入您想要使用的实际算法；包括TL2算法。由于 Deuce 框架是 Java，因此以下讨论使用 Java 术语，但仅假设您使用 OO 语言编写。

下面将概述 TL2 方法。这些论文提供了替代方法的链接，但研究一种算法可以回答很多问题。

如何实施 STM？对我来说神秘的部分是，给定一些任意的代码块，您需要一种方法来返回并确定每个步骤中使用的值是否有效。

关于 TL2 如何执行 STM 的一个简短答案是“簿记”，然后仅在提交时使用写锁。请阅读论文以了解详细信息，但板刷轮廓如下。您可以在原始代码中使用的每个属性都有一个 getter 和 setter。在转换后的代码中，还会有属性的版本号以及添加到 getter 和 setter 的附加代码。您需要将事务中读取的每个属性的版本记录为事务“读取集”。您可以通过让每个 getter 将看到的属性版本添加到线程本地链表中来实现此目的。您还需要将写入缓冲为线程本地中的“写入集”，直到提交为止。请注意，getter 方法需要检查并返回给定字段的线程本地写入集值（如果有）。这样，您可以在读取中看到未提交的写入，但在您提交之前没有其他线程会看到它们。

在提交时，您对要写入的每个属性进行写锁。当你有锁时，请仔细检查你的读取集是否仍然有效；您在事务中读取的属性尚未被其他事务更新到更高版本。如果是这样，那么您的业务逻辑可能无效，因为您可能会出现不一致的读取，因此您需要回滚整个事务。如果最终检查通过，则您可以通过刷新写集、更改这些属性的版本、释放写锁并最终清除写集和读集线程本地列表来提交。

该论文解释说，如果算法检测到自交易开始以来正在读取的属性已被写入，则该算法可以提前中止。该论文提出了一些加速只读事务的巧妙技巧。它甚至有一个技巧来确定哪些块是只读的，哪些是读写的。任何对此类事情感兴趣的人都应该喜欢这两篇论文。

上面论文中的 Deuce 框架展示了如何通过在加载时将新的 java 字节码注入到类中来更改所有 getter 和 setter。其他语言可能有一个特殊的编译器或预处理器，它们执行将普通代码转换为支持 STM 的代码的相同机械转换。具体来说，使用 Deuce，您的源代码对象可以具有简单的 getter setter 对，但在运行时转换的类已经丰富了完成书本工作的 getter setter。

将常规代码转换为 STM 代码（尤其是在运行时）很有趣，但如果您需要实际编写支持 STM 的数据结构，则不需要任何魔法。相反，只需创建一个带有 get() 和 set(x) 的 Ref 类，并构成数据结构对象之间的每个关系Ref 句柄。在 Ref 类的 get 和 set 中，您可以完成线程本地工作。然后，您可以实现“TL2”的简单版本或任何其他适合您的数据结构以及读写并发性的算法。

这似乎也表明，就像任何其他“锁定”一样
您希望使关键部分尽可能小的解决方案
（减少冲突的可能性），我说得对吗？

TL2有一个关键期，即持有写锁，然后进行最终检查和写入，这很容易理解和优化，无需了解应用程序业务逻辑。如果为每个属性分配一个唯一的编号，则可以通过按升序锁定来轻松避免死锁。重要的是要注意，所有业务逻辑都是假设提交检查将通过而推测地完成的。当您执行任意缓慢的业务逻辑时，您不会持有锁。您可以执行多个 Web 服务查找或缓慢的数据库调用，并且在提交之前不会获取任何锁定。显然，专业人士将彻底调整通用关键部分。

该论文明确指出，该算法可能会比特定业务逻辑所需的更频繁地中止。通用算法不知道特定的脏读是否不会影响实际的写入结果。了解实际业务逻辑的手写逻辑可以知道当给定的脏读集不需要回滚时的特殊情况。然而，如果您有大量代码需要编写，并且应用程序回滚的可能性非常低，那么通用机械 STM 方法可能会导致错误更少并且性能良好。

此外，STM 是否可以简单地检测“另一个线程在
计算正在执行，因此计算无效”
或者它实际上可以检测是否使用了破坏的值（因此
幸运的是，有时两个线程可能会执行相同的关键部分
同时无需回滚）？

TL2 方法涉及读取或写入的数据，而不是执行该操作的代码。重要的是你所得到和设置的；以及在刷新所有写入之前是否有任何其他线程踩到您的脚趾。代码所需要的只是在业务逻辑中有一个 begin()、commit() 和 rollback() 来启动，结束并中止事务。甚至可以生成代码。使用 Java，您可以在方法上使用 @Transactional 注释来标记您的方法，然后生成将您的方法调用包装在 try/catch/finally 中的代码，该代码将开始/提交/回滚作为惯用的 java.lang.Transactional 方法。 Deuce 在类加载时注入此类逻辑。

再次强调，您不需要这样的魔法来在您自己的支持 STM 的数据结构中开始/提交/回滚。您可以明确地将所有这些内容直接放入数据结构逻辑代码中，以任何 OO 语言创建您自己的显式支持 STM 的类。

Some papers can be really difficult to read but two which are very clear and concise are:

Transactional Locking II, Dave Dice, Ori Shalev, Nir Shavit which describes the "TL2" STM algorithm in terms of any language.

Deuce: Noninvasive Software Transactional Memory in Java, Guy Korland, Nir Shavit, Pascal Felber which explains a load time class transformer which transforms regular java classes into in-memory classes which have additional bytecode to do STM. This is relevant to the question as the paper explains how code without STM can be mechanically transformed into code which is doing STM in any OO language.

The Deuce framework lets you plugin the actual algorithm you wish to use; including the TL2 algorithm. As the Deuce framework is Java the following discussion uses java terminology but is only assuming that you are writing in an OO language.

Below will outline the TL2 approach. The papers have links to alternative approaches but studying one algorithm answers a lot of questions.

how do you implement STM? The part that's mysterious to me is that given some arbitrary chunk of code, you need a way to go back afterward and determine if the values used in each step were valid.

One short answer for how TL2 does STM is "bookkeeping" and then only using write locks at commit time. Read the paper for the fine detail but a board brush outline is as follows. Every property that you can use in the original code would have a getter and setter. In the transformed code there would also be a version number of the property and additional code added to the getter and setter. You need to record the version of every attribute you read within the transaction as the transaction "read-set". You can do this by having every getter add the version of the attribute seen into a threadlocal linkedlist. You also need to buffer the writes as the "write-set" in a threadlocal until you commit. Note that the getter methods need to check and return a threadlocal write-set value for a given field if you have one. That way you see your uncommitted writes in your reads but no other thread is going to see them until you commit.

At commit time you take write locks against every attribute you are about to write. Whilst you have the locks you double check that your read-set is still valid; that the attributes you read in your transaction have not been updated to a higher version by another transaction. If so then your business logic may not be valid as you can have inconsistent reads so you need to rollback the whole transaction. If the final checks pass then you commit by flushing your write-set, bump the versions of those attributes, release the write locks, and final clear both the write-set and read-set threadlocal lists.

The paper explains that the algorithm can abort early if it detects that an attribute being read has been written to since the tx started. The paper has some neat tricks to speed up read-only transactions. It even has a trick to work out which blocks are read-only and which are read-write. Anyone expressing an interest in such things really should enjoy the two papers.

The Deuce framework in the paper above shows how to change all your getters and setters by injecting new java bytecode into your classes at load time. Other languages could have a special compiler or preprocessor which perform the same mechanical transformation of normal code into STM enabled code. Specifically with Deuce your source code objects can have simple getter setter pairs but transformed classes at runtime have enriched getter setters which do the bookwork.

Transforming regular code into STM code (particularly at runtime) is interesting but if you need to actually write a STM enabled data structure you don't need any magic sauce. Instead just create a Ref class with a get() and a set(x) and make every single relationship between your data structure objects made up of Ref handles. In the get and set of your Ref class you can do the threadlocal bookwork. Then you can implement a simple version of "TL2" or any other algorithm which works well for your data structures and your concurrency of read versus write.

This would also seem to suggest that just like any other 'locking'
solution you want to keep your critical sections as small as possible
(to decrease the probability of a conflict), am I right?

TL2 has a critical period in holding the write locks then doing final checks and writes which is easy to comprehend and optimise without any understanding of the application business logic. If you assign each property a unique number you can trivially avoid deadlock by taking locks in ascending order. It is important to note that all your business logic is done speculatively assuming that the commit checks will pass. You don't hold locks whilst you are doing arbitrary slow business logic. You can be doing multiple web service lookups or slow database calls and you won't take any locks until the commit. Clearly the professionals are going to tune the heck out of the generic critical section.

The paper makes it clear that the algorithm may be aborting more often that the specific business logic requires. The generic algorithm does not know whether specific dirty reads would not affect the actual write outcome. Handwritten logic which understands the actual business logic could know special cases when a rollback is not needed for a given sets of dirty reads. If however you have lots of code to write and an application where the likelihood of rollback is very low a generic mechanical STM approach may lead to less bugs and perform well.

Also, can STM simply detect "another thread entered this area while
the computation was executing, therefore the computation is invalid"
or can it actually detect whether clobbered values were used (and thus
by luck sometimes two threads may execute the same critical section
simultaneously without need for rollback)?

The TL2 approach as all about the data read or written not about the code which does it. It is what you get and set and which counts; and whether any other thread trod on your toes before you flush all the writes. All that is required of the code is that you have a begin(), commit() and rollback() in the business logic to start, end and abort the transaction. Even that can be generated code. With Java you could mark your methods with the @Transactional annotation on methods then generate code which wrap your method invocations in a try/catch/finally that does the begin/commit/rollback as idiomic java. Deuce injects such logic at class load time.

Once again you don't need such magic sauce to begin/commit/rollback in your own STM enabled data structures. You can be explicit and put in all that right into your data structure logic code to create your own explicitly STM enabled classes in any OO language.

回复收藏 0 原文

明月松间行 2024-08-15 13:13:16

最简单的答案是“这取决于”。有大量完全不同的实现以几乎任何可以想象的方式工作。

对我来说神秘的部分是，给定一些任意的代码块，您需要一种方法来返回并确定每个步骤中使用的值是否有效。您如何做到这一点？如何有效地做到这一点？

一种解决方案是使用版本控制。每次修改对象时，其版本号都会更新。当事务运行时，您验证每个访问对象的版本，当事务提交时，您验证这些对象仍然有效。
此验证可以是简单的整数比较（如果 transaction_start_version >= object_version，则该对象有效），因此可以相当有效地完成。

这似乎也表明，就像任何其他“锁定”解决方案一样，您希望使关键部分尽可能小（以减少冲突的可能性），我是对的吗？

很有可能。我认为一些实现已经走上了假设/要求一切都是事务的路线，但是，是的，在大多数实现中，事务是专门标记的代码块，并且事务运行的时间越长，越大发生可能导致事务回滚的冲突的可能性。

此外，STM 是否可以简单地检测“在执行计算时另一个线程进入该区域，因此计算无效”，或者它是否可以实际检测是否使用了破坏值（因此幸运的是，有时两个线程可能会执行相同的关键操作）同时部分而不需要回滚）？

后者。请记住，TM 的理念是保护数据，而不是代码。

不同的代码路径可以在不同的事务中访问相同的变量。这必须由 TM 系统检测到。没有“这个区域”的真正概念，因为它指的是代码，而不是数据。 TM 系统并不关心正在执行什么代码，而是跟踪正在修改什么数据。这样，它与关键部分（保护代码而不是数据）完全不同

The simplest answer is "it depends". There are tons of radically different implementations working in pretty much any way imaginable.

The part that's mysterious to me is that given some arbitrary chunk of code, you need a way to go back afterward and determine if the values used in each step were valid. How do you do that, and how do you do it efficiently?

One solution is to use versioning. Every time an object is modified, its version number is updated. While the transaction is running, you validate each accessed object's version, and when the transaction commits, you verify that the objects are still valid.
This validation can be a simple integer comparison (if transaction_start_version >= object_version, the object is valid), so it can be done fairly efficiently.

This would also seem to suggest that just like any other 'locking' solution you want to keep your critical sections as small as possible (to decrease the probability of a conflict), am I right?

Very likely. I think a few implementations have gone the route of assuming/requiring everything to be a transaction, but yes, in most implementations, transactions are specially marked chunks of code, and the longer a transaction runs, the larger the chance of a conflict that may cause transactions to roll back.

Also, can STM simply detect "another thread entered this area while the computation was executing, therefore the computation is invalid" or can it actually detect whether clobbered values were used (and thus by luck sometimes two threads may execute the same critical section simultaneously without need for rollback)?

The latter. Keep in mind that the idea in TM is to protect data, rather than code.

Different code paths may access the same variable in different transactions. This has to be detected by the TM system. There's no real notion of "this area", since that refers to code, rather than data. The TM system doesn't care what code is executing, it tracks what data is being modified. In that way, it differs entirely from critical sections (which protect code, rather than data)

回复收藏 0 原文