STM 介绍

Atomicity(原子性)——在写操作中，我们需要原子更新，这意味着更新操作要么应该立即运行，要么根本不运行。
Consistency(一致性)——在读操作中，我们希望程序状态具有一致的视图，以确保各部分都引用相同的状态，在获得状态时获得相同的值。
Isolated(隔离性)——如果我们有多个同步更新，我们需要在隔离的事务中执行这些更新。每个事务不会影响其他并发事务。无论有多少纤程在运行多少数量的事务，都不必担心其它事务中发生的事情。

ZIO STM API 的灵感来自 Haskell 的 STM库，尽管 ZIO 中的实现完全不同。

问题

让我们从一个简单的inc函数开始，它接受一个 Int 类型的可变引用并增加其 amount：

def inc(counter: Ref[Int], amount: Int) = for {
  c <- counter.get
  _ <- counter.set(c + amount)
} yield c

如果只有一个纤程，那不会有问题。这个函数看上去是正确的。但是，如果在读取计数器的值和设置新值之间，另一个纤程出现并改变了计数器的值，会发生什么？在我们读取计数器之后，另一个纤程恰好更新了计数器。所以这个函数是有竞争条件的，我们可以用下面的程序来测试：

for {
  counter <- Ref.make(0)
  _ <- ZIO.collectAllPar(ZIO.replicate(10)(inc(counter, 1)))
  value <- counter.get
} yield (value)

由于上述程序运行了 10 个并发纤程来增加计数器值。但是，我们不能期望这个程序总是返回结果 10。

为了解决这个问题，我们需要原子地执行 get 和 set 操作。所幸 Ref 数据类型的一些 API，比如 update，updateAndGet和modify 提供了读写同步的原子操作。

def inc(counter: Ref[Int], amount: Int) = counter.updateAndGet(_ + amount)

需要注意的是有关 modify 操作最重要的一点是它不使用悲观锁定。它不对临界区使用任何锁定原语。它对潜在的操作碰撞有一个乐观的假设。

该 modify 函数执行以下三个步骤：

它假设其他纤程在大多数情况下不会改变共享状态并且在多数情况下不会互相干扰。因此它在不使用任何锁定原语的情况下读取共享状态。
你应该为最坏的情况做好准备。如果另一个纤程同时接入，会发生什么？因此，当我们开始写入新值时，应该检查所有可能影响的方面。它应该确保看到全局一致的状态，如果它看到了，那么它才可以改变那个值。
如果它遇到不一致的值，则不应继续。它应该使以上假设变得无效并中止更新共享状态。然后基于被修改过的值重新尝试 modify 操作。

让我们看看在没有任何锁定机制的情况下 Ref 如何实现 modify 功能：

  final case class Ref[A](value: AtomicReference[A]) { self =>
    def modify[B](f: A => (B, A)): UIO[B] = UIO.effectTotal {
      var loop = true
      var b: B = null.asInstanceOf[B]
      while (loop) {
        val current = value.get
        val tuple   = f(current)
        b = tuple._1
        loop = !value.compareAndSet(current, tuple._2)
      }
      b
    }
 }

正如我们所看到的，modify 操作是根据 compare-and-swap 操作来实现的，它帮助我们以原子方式执行读取和更新。

让我们将 inc 函数重命名为以下的 deposit，尝试将钱从一个账户转移到另一个账户的经典问题：

def deposit(accountBalance: Ref[Int], amount: Int) = accountBalance.update(_ + amount)

增加 withdraw 函数：

def withdraw(accountBalance: Ref[Int], amount: Int) = accountBalance.update(_ - amount)

看起来还不错，但是实际上我们要先检查账户中是否有足够的余额可以提现。所以让我们修改它添加一个不变量来检查：

def withdraw(accountBalance: Ref[Int], amount: Int) = for {
  balance <- accountBalance.get
  _ <- if (balance < amount) ZIO.fail("Insufficient funds in you account") else
    accountBalance.update(_ - amount)
} yield ()

如果在检查和更新余额之间，另一条纤程来提取账户中的资金怎么办？所以这个解决方案包含一个错误。它有可能让账户达到负平衡。

假设我们最终达成了一个解决方案来自动退出，但问题仍然存在。我们需要以原子的方式将 withdraw 和 deposit 组合在一起以创建 transfer函数：

def transfer(from: Ref[Int], to: Ref[Int], amount: Int) = for {
  _ <- withdraw(from, amount)
  _ <- deposit(to, amount)
} yield ()

在上面的例子中，即使我们假设 withdraw 和 deposit 各自是原子的，我们也不能组合这两个事务。它们在并发环境中会产生错误。这段代码不能给我们保证 withdraw 都 deposit 两者在同一个原子操作中执行。同时执行此 transfer 方法的其他纤程可以覆盖共享状态并引入竞争条件。

我们需要一个解决方案来原子地组合事务。这就是STM发挥作用的地方。

可组合的并发

软件事务内存为我们提供了一种组合多个事务并在一个事务中执行它们的方法。

让我们继续我们的最后努力，将我们的 withdraw 方法转换为一个原子操作。为了使用 STM 来解决问题，我们将 Ref 替换 TRef. TRef 的含义是Transactional Reference；它是 STM 世界中的可变引用。STM 是一个一元的数据结构，代表一个可以事务化执行的 effect：

def withdraw(accountBalance: TRef[Int], amount: Int): STM[String, Unit] =
  for {
    balance <- accountBalance.get
    _ <- if (balance < amount)
      STM.fail("Insufficient funds in you account")
    else
      accountBalance.update(_ - amount)
  } yield ()

同样 deposit 操作是原子的，但为了能够和 withdraw 组合，我们也需要用 TRef 将其重构并 return STM：

def deposit(accountBalance: TRef[Int], amount: Int): STM[Nothing, Unit] =
  accountBalance.update(_ + amount)

在 STM 的世界中，我们可以组合所有操作，并直到世界的尽头，我们才在一个操作中原子地执行所有这些操作。为了能够让 withdraw 和 deposit 组合在一起，我们需要让它们都保持在 STM 的世界中。因此，我们不对它们中的每一个单独执行STM.atomically 或 STM#commit 方法。

现在我们可以在 STM 的世界中组合这两个函数来定义 transfer，并将它们转换为单一原子的 IO 方法：

def transfer(from: TRef[Int], to: TRef[Int], amount: Int): IO[String, Unit] =
  STM.atomically {
    for {
      _ <- withdraw(from, amount)
      _ <- deposit(to, amount)
    } yield ()
  }

假设我们正在将资金从一个账户转移到另一个账户。如果我们取出第一个账户但没有存入第二个账户，这种中间状态对任何外部纤程都是不可见的。如果不存在任何有冲突的变更，则事务完全成功。如果存在任何冲突或冲突更改，则整个 STM 将被重试。

它是如何工作的

STM 使用了和 Ref#modify 函数相同的思想，但具有可组合性特征。STM 的主要目标是提供一种机制来组合多个事务并在一个原子操作中执行它们。

可组合部分背后的机制是显而易见的。STM 有自己的世界。它有很多有用的 combinators（组合子），例如 flatMap 和orElse 可用于组合多个 STM 并创建更优雅的结果。在我们通过 STM#commit 或 STM.atomically 来启动一个事务后，Runime 会执行以下步骤。这些步骤并不完全准确，但它们勾勒出事务过程中发生的情况：

启动事务——当我们启动事务时，Runetime system 会创建一个虚拟空间来记录事务的日志，该日志用于记录事务将在事务执行步骤期间将执行的读取或暂定写入。
虚拟执行——Runtime 开始演算每次读写事务操作的执行。它有两个内部日志；读取和写入日志。在读日志上，它保存了在中间步骤中读取的所有变量的版本；在写日志上，它保存了事务的中间输出结果。它不会改变主内存上的共享状态。原子块内的任何内容都不会立即执行，而是在虚拟世界中执行，只是将内容放入内部日志而不是主内存中。在这个特定模型中，我们保证所有计算都是相互隔离的。
提交阶段（实际执行）— 当事务结束时，Runtime system 检查它读取的所有内容。它应该确保它看到了全局的一致状态（Consistency），如果它看到了，那么它会原子地提交最终的结果。由于 STM 是乐观的，它假设在事务的执行中间，其他纤程干扰共享状态的机会非常罕见。但它必须为最坏的情况做好准备。它应该在最后阶段验证这个假设。它检查所涉及的事务变量是否被任何其他线程修改。如果它的假设在事务执行过程中失效，它应该放弃事务并重新执行。它使用原始值和默认值跳转到事务的开头并再次尝试直到成功；这是解决冲突所必需的。否则，如果没有冲突，它将最终值原子地提交到内存并成功结束。从其他纤程的角度来看，内存中的所有值都在眨眼之间交换。这都是原子的。

在一个事务中对其他事务所做的一切看起来像是一次性发生的或根本未成发生。因此，无论在事务期间它触及多少块内存。从另一个交易的角度来看，所有这些变化都是同时发生的。

STM 数据类型

有多种事务数据结构可以参与 STM 事务：

TArray – ATArray[A]是可以参与事务的可变引用数组。
TSet – ATSet是一个可以参与事务的可变集合。
TMap – ATMap[A]是一个可以参与事务的可变映射。
TRef – ATRef是对可以参与事务的不可变值的可变引用。
TPriorityQueue – ATPriorityQueue[A]是一个可以参与事务的可变优先级队列。
TPromise – ATPromise是一个可变引用，可以只设置一次并且可以参与事务。
TQueue – ATQueue是一个可以参与事务的可变队列。
TReentrantLock – ATReentrantLock是一个可组合的可重入读/写锁。
TSemaphore – ATSemaphore是可以参与事务的信号量。

由于 STM 非常强调组合性，我们可以在这些数据结构的基础上定义我们自己的并发数据结构。例如，我们可以使用TRef，TMap和TQueue共同构建事务性的优先级队列。

STM 的优点

可组合事务 —— 使用面向锁定的编程组合原子操作几乎是不可能的。ZIO 提供了STM 数据类型，它有很多组合子来组成事务。
Declarative(声明式) —— ZIO STM 完全是声明式的。它不需要我们考虑低级原语。它不会强迫我们考虑锁的顺序。以声明方式推导出并发程序非常简单。我们可以只关注程序的逻辑，并确定它在并发环境中会得到的结果。用户代码也当然因此要简单得多，因为它根本不需要处理并发问题。
乐观并发 —— 在大多数情况下，我们可以保持乐观，除非存在巨大的争用。因此，如果我们没有激烈的争用，那么采用乐观确实是值得的。它允许更高数量的并发事务。
无锁——所有操作都使用无锁算法非阻塞地进行。
细粒度锁定 —— 粗粒度锁定实现起来非常简单，但对性能有负面影响，而细粒度锁定明显具有更好的性能，但即使对于有经验的程序员来说，它也非常繁琐、复杂且容易出错.我们希望拥有粗粒度锁定的易用性，但同时又希望拥有细粒度锁定的效率。 ZIO 提供了几种数据类型，它们是使用并发性的一种非常粗略的方式，但它们的实现就像每个单词都是可锁定的。所以并发的粒度是细粒度的。它提高了性能和并发性。例如，如果我们有两个纤程访问同一个 TArray，其中一个读写我们数组的第一个索引，另一个读写该数组的第二个索引，它们不会冲突。就好像我们锁定了单个索引，而不是整个数组。

使用 STM 的意味着什么

在 STM 内部运行 I/O —— STM 的世界与 ZIO 之间有严格的界限。这个边界传播得更深，因为我们不允许在STM 世界中执行任意的 effect。在事务中执行 side effec 和 I/O 操作是有问题的。STM 内唯一产生的 effect 就是STM 它自己。我们不能在交易中打印某些东西或发射导弹，因为打印动作会不确定地被事务的每次重试重复执行。
大内存分配 —— 我们应该在使用 STM 操作时非常小心地选择最佳的数据结构。例如，如果我们在 TRef 中使用单个数据结构，并且该数据结构占用大量内存。每次我们在事务期间更新此数据结构时，运行时系统都需要此内存块的新副本。
运行昂贵的操作 —— retry 组合子的美妙特性是当我们决定重试事务时，它retry避免了无意义的循环。它会保持等到任何其依赖的事务变量发生变化时才重新执行。但是，我们应该小心多次运行昂贵的操作。

原文链接：https://zio.dev/version-1.x/datatypes/stm/

Post Views: 850

Posted on January 28, 2022in scala, zio, zio中文文档, 数据类型, 泛函

简介

问题

可组合的并发

它是如何工作的

STM 数据类型

STM 的优点

使用 STM 的意味着什么

Leave a Reply Cancel reply