Ruby建议的STM

有人提议在Ruby编程语言中添加软件事务内存(Software Transaction Memory，简称STM)。这是一个更广泛的努力的一部分，目的是在Ruby中增加对并发性和并行性的更好支持，特别是Ractor的想法。佐田光一(Koichi Sasada)提出并实施了一个概念。

本文提供了一些关于STM是什么、如何使用它以及您可能想要使用它的原因的上下文。我们将展示一个非常适合STM的应用程序，我们将用它来讨论它的优点、问题和一些有待解决的问题。

我博士学位的前半部分是关于STM的，后半部分是关于Ruby的，所以我对这两个方面都有相当多的经验，而且它们结合在一起的想法对我来说非常有趣。

假设我们是一家管理多个银行账户的银行。每个帐户都有一个合计。我们得到一个永无止境的请求流，要求将一笔钱m从帐户a转移到帐户b。

关于Ruby，可能并不是每个人都知道x+=y等同于写成t=x；x=t+y，我们将把它完整地写出来，以便让我们自己明白这一点。

循环执行a，b，m=Get_Next_Transfer a_BALANCE=ACCOUNTS[a]ACCOUNTS[a]=a_BALANCE-m b_BALANCE=ACCOUNTS[b]Accounts[b]=b_BALANCE+m end。

我们有很多传输要运行，所以我们将有多个线程来处理这些传输。

vt.的；时代做线条。新循环do a，b，m=Get_Next_Transfer a_BALANCE=ACCOUNTS[a]ACCOUNTS[a]=a_BALANCE-m b_BALANCE=ACCOUNTS[b]ACCOUNTS[b]=b_BALANCE+m END END

我们现在有几个问题。在所有这些线程同时运行的情况下，如果两个线程同时将钱存入您的帐户，会发生什么情况呢？

帐户[a]=100#线程1#线程2余额=帐户[a]#余额=100余额=帐户[a]#余额=100帐户[a]=余额+10#帐户[a]=110帐户[a]=余额+10#帐户[a]=110。

两笔转账已经用完了，但您的余额是110。其他10个已经丢失-这被称为丢失的更新，意思是就好像从未进行过更新一样。

还要考虑一下，如果线程在从a取钱之后，但在将钱放入b之前崩溃，会发生什么情况？这笔转账将部分适用，我们又会赔钱。

我们需要对我们的帐户使用某种同步。Ruby有互斥锁或互斥锁，所以我们可以尝试使用它们。

vt.的；时代做线条。新循环执行a，b，m=get_next_transfer锁[a]。同步DO锁定[b]。同步DO帐户[a]-=m个帐户[b]+=m个结束结束。

这个管用吗？如果我们在处理从帐户1002到1001的转移的同时，同时在一个线程上处理从帐户1001到帐户1002的转移，那么在同一时间从帐户1001转移到帐户1002又会怎么样呢？

第一个线程将尝试锁定1001，然后尝试锁定1002。第二个线程将尝试锁定1002，然后锁定1001。如果第一个线程达到锁定1001，第二个线程达到锁定1002，那么两个线程都将等待相反的锁，并且永远不会释放它们已经拥有的锁。我们将陷入僵局。

如果我们总是以相同的顺序获取锁，通过首先收集它们并对它们进行排序，我们就可以修复这个问题。

vt.的；时代做线条。新循环do a，b，m=get_next_transfer x，y=[a，b]。排序锁[x]。同步DO锁[y]。同步DO帐户[a]-=m个帐户[b]+=m个结束结束。

现在，在这两个转账中，帐户1001首先被锁定，而1002被第二次锁定。那会行得通的。

我们必须编造一个有点人为的要求来解释下一个问题，但请考虑一下，如果我们有很多钱，出于某种充分的理由，我们想转到一个账户，如果我们只有一点钱，我们想转到一个不同的账户。也许如果我们这个月很有钱，我们可以捐钱给慈善机构，否则，不幸的是，我们需要为自己存钱。

现在我们将讨论账户a，b，c，以及资金门槛t。

vt.的；时代做线条。新循环do a，b，c，t，m=get_next_transfer x，y，z=[a，b，c]。排序锁[x]。同步DO锁[y]。同步DO锁[z]。同步DO IF帐户[a]&>t帐户[a]-=m个帐户[b]+=m个其他帐户[a]-=m个帐户[c]+=m个末端结束。

事情开始变得非常复杂了。这锁定的比它需要的更多-它锁定b和c，但随后只使用其中的一个。如果最后使用b，理想情况下，另一个线程可以同时服务到c的传输，但是您已经锁定了它，但是它不能。想象一下，如果不是两个潜在的帐户，而是数千个，并且您必须将它们全部锁定。想象一下，如果您在开始转账之前根本无法计算出要转账到哪个帐户，那么您将永远无法同时处理两个转账。

在这一点上，我们也可能开始尝试对锁和事物进行所有这些锁定和排序时出错。

退一步，把所有的东西都考虑进去，我们可以为我们需要的东西拟定一些要求。

一致性-意味着我们的数据结构始终有效-总金额永远不变。

理想情况下，库或语言可以为我们完成所有这些工作。我们希望能够编写几乎与最初编写的内容相同的代码，但是只需要一个注释，就可以使块中的代码成为原子的、一致的、隔离的，并且结果是持久的。

vt.的；时代做线条。新循环do a，b，m=get_next_transfer原子执行帐户[a]-=m个帐户[b]+=m个end。

这就是事务性内存可以让我们做的事情。它将自动监视您在原子块(即事务)中读取和写入的内容，并将确保它是否完全应用、整个系统的平衡始终保持一致、事务看不到彼此部分应用的结果，以及写入显示并保持不变。

它可以使用我们最终自己得出的代码来实现，或者它也可以做一些其他的事情。在实践中，它通常是如何实现的，即读取和写入存储在日志中，然后事务在结束时计算出是否有其他人具有您已经读取的写入位置。如果有，则您读取的值不再有效，因此您的事务与另一个事务冲突，将中止并重试，再次读取位置。当它最终不与任何其他事务冲突时，它被提交并成功。这意味着您不需要预先锁定所有内容，这意味着您避免了可能需要每个帐户时会发生的问题。预先锁定所有内容称为悲观锁定。我们正在转向乐观锁定。

Koichi为Ruby提议的STM，与他提议的参赛者(类似于演员)结合在一起，看起来就像这样。

帐户=9999。泰晤士报。地图{线程：：TVAR.。新建(100)}n。时代做赛车。新的*帐户执行|*帐户|循环执行a，b，m=Get_Next_Transfer Thread。自动计算帐目[a]。值-=m个帐户[b]。值+=m末端

他使用的是Ractor，但您可以将其视为本文的一条线索。我们现在有一个包含值的TVAR对象数组，而不是帐户余额数组。TVAR是一个事务变量。只有这些变量是事务性的，而不是您读取或写入的任何其他Ruby值。他的设计要求将您要使用的TVAR对象传递给ractor，因为有关共享的规则与本文无关。

让我们考虑一个更大的应用程序，以便进一步说明并讨论一些问题和有待解决的问题。代码可以在GitHub上找到。

假设我们的工作是在电路板上布线。我们得到一个带有焊盘的电路板(连接到安装在电路板上的组件)，以及我们需要在这些焊盘之间绘制的路线列表。有很多焊盘和线路，小电路板上的空间不大，还有一个问题是，让电线相互交叉非常昂贵。比方说，堆叠得越深的电线就越贵。

在这个最小的例子中，我们可以看到两条路由，以及它们如何相互交叉。

这个示例是一个处理器模块，它显示了我们可能想要使用的规模。这块板上有许多更长的路线，更容易发生冲突。

此示例是内存模块。它有许多较短的路线，我们可能希望这些路线冲突较少。

每条路由的布局都有一个算法，它实际上会为个别路由生成最优解，但不是所有路由都是这样。它叫做李的算法，早在1960年就发表了。我们将在这里展示算法的代码，但它稍微简化了一些，即使这样，您也不需要全部遵循。

电路板的状态是栅格，每个方块的值是堆叠在该位置的导线数量。我们依次看一遍我们的路线清单。

在扩展过程中，我们从路线开始，以波阵面形式向外移动，在黑板上的每个位置存储以这种方式铺设路线可能花费的费用。考虑到每条可能的路线，我们从这条路涌出。我们继续前进，直到板上没有一个新位置的成本低于目前路线末端的成本。

定义扩展(电路板，受阻，深度，布线)START_POINT=布线。A端点=路线。B成本=Lee：：矩阵。新(董事会。高度，登机牌。宽度)成本[START_POINT。Y，起点。X]=1 Wavefront=[START_POINT]LOOP DO NEW_WAVEFRONT=[]WAVEFRONT。每个DO|POINT|POINT_COST=COST[POINT。Y，点。访问数/每百万人：Reach.。相邻(板、点)。如果受阻，则每个DO|相邻|下一步[相邻。Y，相邻。X]==1&；&；相邻！=布线。B CURRENT_COST=成本[相邻。Y，相邻。X]NEW_COST=POINT_COST+LEE。成本(深度[相邻。Y，相邻。X])如果CURRENT_COST==0||NEW_COST<；CURRENT_COST COST[相邻。Y，相邻。X]=NEW_COST NEW_WAVEFRONT。推相邻端COST_AT_ROUTE_END=COST[END_POINT]。Y，端点。X]MINIMUM_NEW_COST=NEW_WAVEFRONT。地图{|已标记|成本[已标记。Y，有记号。X]}。如果COST_AT_ROUTE_END>；0&；&；COST_AT_ROUTE_END<；MINIMUM_NEW_COST_COST=NEW_WAVEFRONT END COST END，则最小中断。

在求解阶段，我们从路由末端回溯，沿着成本最低的路径进行扩展。

Def solve(板，路线，成本)START_POINT=路线。B END_POINT=路线。A解决方案=[START_POINT]循环do相邻=Lee。相邻(电路板，解决方案。最后)LOST_COST=相邻。拒绝{|a|成本[a]。Y，A。X]。零？}。Min_by{|a|成本[a.。Y，A。X]}解决方案。如果LOST_COST==END_POINT END，则推送LOST_COST BREAK。

在布设时，我们采用解决方案中的点列表，并增加每个点的深度，以表示该点上现在有另一条导线。

整个算法是展开、求解、铺设，然后根据路径记录解。

冲浪板。路线。每个DO|ROUTE|COST=EXPAND(板材，受阻，深度，布线)解决方案=SOLVE(板材，布线，成本)铺设深度，解决方案[ROUTE]=解决方案结束。

我们可以在测试板上运行它，如果我们打印一些统计数据，我们会看到，例如，我们铺设了203条路线，成本为3304条，使用的最大深度为3，这还不算太差。

Lee的一个问题是，每条路线都有很多工作要做，我们有很多路线要解决，所以我们肯定希望将其并行化，也许可以同时解决多条路线。

事务性内存在这里可以很好地工作。我们可以做的是运行多个线程，每个线程使用STM求解事务内的路由。板的状态将包含TVAR对象，其中包含每个位置的深度。

代码不会有太多更改。我们现在写入的不是Depth[libent.y，adighent.x]，而是Depth[adighent.y，adighent.x].value，因为这些都是事务值。

波前。每个DO|POINT|POINT_COST=COST[POINT。Y，点。访问数/每百万人：Reach.。相邻(板、点)。如果受阻，则每个DO|相邻|下一步[相邻。Y，相邻。X]==1&；&；相邻！=布线。B CURRENT_COST=成本[相邻。Y，相邻。X]NEW_COST=POINT_COST+LEE。成本(深度[相邻。Y，相邻。X]。值)如果CURRENT_COST==0||NEW_COST<；CURRENT_COST COST[相邻。Y，相邻。X]=NEW_COST NEW_WAVEFRONT。推相邻端端端。

我们将单个路由的所有阶段放入一个事务中。对于算法的并行化来说，这些都是非常小的改变！

穿线。原子计算成本=扩展(电路板、障碍物、深度、布线)解决方案=解决(电路板、布线、成本)铺设深度、解决方案结束。

我使用插装实现了这段代码的一个版本，这样我们就可以看到发生了什么。它一次解决两条路线，并手动检查冲突，并可以为我们可视化结果。

这显示了两条同时求解的路由。他们需要阅读的区域(他们的扩展)用阴影标出，最后的路线用非常粗的线条显示。已成功铺设的路由以灰色显示。这两条路线显然是独立的-扩展和路线根本不重叠。求解一条路径所需阅读的内容并未被另一条路径修改。这是一个完美的案例--两条路线都得到了承诺，我们没有浪费时间，而且我们同时成功地解决了它们。

下一个示例显示了两条扩展区域重叠的路由。这意味着要解决这两条路线，在黑板上有一些他们都必须读的位置，但两条路线都没有写出对方读的位置。想想看，如果我们使用在读取任何位置之前锁定的方法-这些路由将不能同时求解，但是因为我们使用了同时考虑两个路由的读取和写入集的STM，所以它们可以并发求解！

接下来，我们可以看到两条明显冲突的路线。它们都写入由对方读取的位置，并且路线也在彼此之上。这将导致一条路由中止，但另一条可以提交，因此我们仍然可以取得进展。

这块板显示了一个非常重要的观点。注意较短路线的下部扩展区域有多大。这条路线将在稍后的过程中解决，因此它所在的地区非常拥挤，扩建必须进一步向外移动，以继续寻找成本最低的解决方案。请注意，在我们开始进行耗时的实际扩建工作之前，我们不可能计算出这个区域将增长到多大。在开始之前，我们无法计算出读取集，这就是我们在银行帐户示例中收集所有锁并对其进行排序时所做的事情。

通过这些示例，我们可以看到我们遇到的问题是如何解决的，以及如何创建额外的并发性。

在我们的仪表化实现中，79对路由是独立的，9对是重叠的，27对是冲突的，需要重试。请注意，现在的成本只是稍有不同-这是因为重试意味着路由将以不同的顺序解决。

还记得我们在哪里猜测主板可能比内存板有更多冲突吗？我们可以在这里的结果中看到这一点。

主要内存路线：15063101独立：6301459重叠：34 41冲突：177 100备件：1 1成本：174128 162917深度：3 3。

我们还可以产生一些极端情况-第一个板将在您试图同时解决的每一对单独的路线上发生冲突，而第二个板永远不会冲突。

实际上，我们还可以在我们的测试板上同时运行Koichi的实现。不过，为了简单起见，我使用的是Thread而不是Ractor。我对要求解的路由列表使用队列。我们这里的流产次数少得令人吃惊--我还不确定为什么会这样。

您必须遵循一些规则才能使用像建议的设计那样的STM。事务性属性仅适用于TVAR对象。如果您修改其他对象，它们将不会成为事务的一部分，如果您的事务被重试，它们将多次运行。这也适用于副作用-如果您在事务中写入文件，这种情况可能会多次发生。例外情况也是需要考虑的情况。

为什么会有这些TVAR对象？为什么不让所有Ruby变量位置都成为事务性的呢？也许这样会更好，这意味着您可以使现有代码成为事务性的。但实际上，MRI的实现并不是为了使这种更改易于实验而设置的。也许在TruffleRuby中进行实验是可能的，TruffleRuby旨在允许数据结构有多种实现，因为这是TruffleRuby优化Ruby代码的一部分。

目前代码中的一个开销是我们有一个包含TVAR对象的Matrix。相反，我们可以拥有数据结构的TArray、THash、TMatrix和其他事务性变体。这可以减少一些簿记费用。

我们可以探索的其他概念包括私有化，这意味着在每条路线开始时拍摄董事会状态的快照，以及提前释放，这意味着如果你知道某个位置对最终结果不重要，那么就放弃你声称已经阅读的位置-所以我们可能会提前释放扩张区域，而不是沿着最终路线。

当我们发现冲突时，我们会怎么做，这是有问题的。我们提交两个事务中的哪一个，中止哪个事务？在Lee中，提交最长的路线，或扩展最大的路线，或花费最长时间解决的路线可能是有意义的。我们能做些什么来减少争执，这样我们首先就会有更少的冲突吗？

然后是关于当人们嵌套事务时我们要做什么的问题，以及大量更多的设计问题。

我们可以用Ruby实现STM的方法有很多种--有大量可能的算法可用于不同的权衡。Koichi正在使用一种名为TL2的算法。我们也可以试试MCRT、巴托克、瑞士、柔道、NOREC、Ring等等。

我们也可以使用特殊的硬件来实现事务性存储器-HTM。英特尔在他们的Haswell内核中增加了对HTM的支持，但由于错误，它不得不被禁用。我相信较新的英特尔架构有它并且可以正常工作，但我不确定有多少人在使用它。AMD已经放弃了类似的想法。HTM的一个问题是，它通常对交易规模有较低的限制。最现实的可能是一种混合事务存储器，它在硬件中有一个内核，但在该内核之上的软件中实现了更广泛的接口。

总体而言，STM和HTM的研究现在似乎已经放缓。大约在2010年，它是一个非常流行的想法，但现在它不那么流行了，尽管关于永久存储器的新想法又回到了它的位置。也许这意味着是时候筛选并找出真正有意义的东西，并将其应用到Ruby等语言中了？

您可能已经猜到STM有一些开销。我们使用的是TVAR对象，而不仅仅是普通值，您知道在内部它必须跟踪读取和写入。事务性内存也可能意味着浪费的工作-如果事务中止并不得不重试，您最终可能会多次执行相同的工作。这可能会增加非常大的开销。

通过将算法并行化，它有望运行得更快。但是由于开销的原因，我们可能不得不在具有非常多内核的机器上运行。

我为STM准备了一个挑战。

.