Experiments with composable lock-free concurrency

The type Rxn[+A] is an effect type with result type A. Thus, it is similar to, e.g., IO[A], but:

• The only effect it can perform is lock-free updates to Refs (mutable memory locations with a pure API).
  • For example, if x is a Ref[Int], then x.update(_ + 1) is a Rxn[Unit] which (when executed) will increment its value.
• Multiple Rxns can be composed (by using various combinators), and the resulting Rxn will update all affected memory locations atomically.
  • For example, if y is also a Ref[Int], then x.update(_ + 1) *> y.update(_ + 1) will increment both of them atomically.

libraryDependencies += "dev.tauri" %%% "choam-core" % "0.5.0-RC4"

The choam-core module contains the fundamental types for working with Rxns. For more modules, see below.

The complete version of the example above, (which increments the value of two Refs) is as follows:

import dev.tauri.choam.core.{ Rxn, Ref }

def incrBoth(x: Ref[Int], y: Ref[Int]): Rxn[Unit] = {
  x.update(_ + 1) *> y.update(_ + 1)
}

As an example, we can execute it with cats.effect.IO like this (the choam-ce module is also needed):

import cats.effect.{ IO, IOApp }
import dev.tauri.choam.ce.RxnAppMixin

object MyMain extends IOApp.Simple with RxnAppMixin {
  override def run: IO[Unit] = for {
    // create two refs:
    x <- Ref(0).run[IO]
    y <- Ref(42).run[IO]
    // increment their values atomically:
    _ <- incrBoth(x, y).run[IO]
    // check that it happened:
    xv <- x.get.run[IO]
    yv <- y.get.run[IO]
    _ <- IO {
      assert(xv == 1)
      assert(yv == 43)
    }
  } yield ()
}

As noted below, Rxn is not a full-featured STM implementation (notably, it lacks Haskell-style "modular blocking"). However, the dev.tauri.choam.stm package contains a full-blown STM, built on top of Rxn. For now, this package is experimental (i.e., no backwards compatibility), and also lacks some basic features, but it does have modular blocking (Txn.retry and Txn#orElse).

• choam-core:

  • core types, like Rxn and Ref
  • integration with effect types implementing the Cats Effect typeclasses (specifically Sync/Async)
  • experimental software transactional memory (STM) built on Rxn

• choam-data: concurrent data structures built on Rxn

  • Examples: queues, stacks, hash- and ordered maps and sets

• choam-async:

  • Asynchronous data structures; some of their operations are semantically blocking (i.e., fiber blocking ), and so are in an F[_] : Async (note, that these F[A] operations are – obviously – not lock-free)
  • These data structures (typically) also have some (lock-free) Rxn operations; thus they provide a "bridge" between the (synchronous, lock-free) Rxn "world", and the (asynchronous) F[_] "world".
  • The simplest example is the data type dev.tauri.choam.async.Promise, which can be completed as a Rxn, and can be waited on as an async F[_]:

    trait Promise[A] { // simplified API
      def complete(a: A): Rxn[Boolean]
      def get[F[_]]: F[A]
    }

• choam-stream: integration with fs2.Streams

• choam-ce: integration with cats.effect.IOApp (for convenience)

• choam-zi: integration with zio.ZIOApp (for convenience)

• choam-profiler: JMH profiler "plugin" for Rxn statistics/measurements; enable it with -prof dev.tauri.choam.profiler.RxnProfiler.

• Internal modules (don't use them directly):

  • choam-mcas: low-level multi-word compare-and-swap (MCAS/k-CAS) implementations
  • choam-internal: a concurrent skip list map and other utilities for internal use
  • choam-laws: properties fulfilled by the various Rxn combinators

JARs are on Maven Central. Browsable Scaladoc is available here.

• Our Rxn is an extended version of reagents, described in the Reagents paper¹ (originally implemented in Scala; see also other implementations in OCaml and in Racket.) The main diferences from the paper are:
  • Only lock-free features (and a few low-level ones) are implemented.
  • Rxn has a referentially transparent ("purely functional" / "programs as values") monadic API. (A limited imperative API is also available in the dev.tauri.choam.unsafe package.)
  • The interpreter (that executes Rxns) is stack-safe.
  • We also support composing Rxns which modify the same Ref (thus, an Rxn is closer to an STM transaction than a reagent; see below).
  • Reads are always guaranteed to be consistent (this is called opacity, see below).

• Multi-word compare-and-swap (MCAS/k-CAS) implementations:
  • In an earlier version we used CASN by Harris et al.²
  • The current version uses EMCAS by Guerraoui et al.³; Mcas.Emcas implements a variant of this algorithm, this is the default algorithm we use on the JVM; on JS we use a trivial single-threaded algorithm.
  • A simple, non-lock-free algorithm from the Reagents paper¹ is implemented as Mcas.SpinLockMcas (we use it for testing).

• Software transactional memory (STM)
  • A Rxn is somewhat similar to a memory transaction, but it has some differences to typical STMs:
    • A Rxn is lock-free by construction (but see below); STM transactions are not (necessarily) lock-free (see, e.g., the "retry" STM operation, called "modular blocking" in Haskell⁴).
    • As a consequence of the previous point, Rxn cannot be used to implement "inherently non-lock-free" logic (e.g., asynchronously waiting on a condition set by another thread/fiber/similar). However, Rxn is interoperable with async data types which implement Cats Effect typeclasses (see the choam-async module). This feature can be used to provide such "waiting" functionality (e.g., with the dev.tauri.choam.async.Promise type, see above).
    • The implementation (the Rxn interpreter) is also lock-free; STM implementations usually use fine-grained locking (although there are exceptions).
    • STM transactions usually have a way of raising/handling errors (e.g., MonadError); Rxn has no such feature (but of course return values can encode errors with Option, Either, or similar).
    • Some STM systems allow access to transactional memory from non-transactional code; Rxn doesn't support this, the contents of a Ref[A] can only be accessed from inside a Rxn.
  • Similarities between Rxns and STM transactions include the following:
    • Atomicity, consistency and isolation.
    • Rxn also provides a correctness property called opacity⁵; see a short introduction here. A lot of STM implementations also guarantee this property (e.g., ScalaSTM), but not all of them. Opacity basically guarantees that all observed values are consistent with each other, even in running Rxns (some STM systems only guarantee such consistency for transactions which actually commit).
  • Some STM implementations:
    • Haskell: Control.Concurrent.STM.
    • Scala: Cats STM, kyo-stm, ScalaSTM, ZSTM.
    • Kotlin: arrow-fx-stm.
    • OCaml: Kcas.
    • TL2⁶ and SwissTM⁷: the system which guarantees opacity (see above) for Rxns is based on the one in SwissTM (which is itself based on the one in TL2). However, TL2 and SwissTM are lock-based STM implementations; our implementation is lock-free.
    • We also use some ideas from the Commit Phase Variations paper⁸.

"Early" SemVer 2.0.0 binary backwards compatibility, with the following exceptions:

• The versions of choam- modules must match exactly (e.g., don't use "choam-data" % "0.4.1" with "choam-core" % "0.4.0").
  • In sbt ⩾ 1.10.0 this can be ensured like this:

    csrSameVersions += Set(sbt.librarymanagement.InclExclRule("dev.tauri", "choam-*"))

• There is no backwards compatibility when:
  • using APIs which are non-public in Scala (even though some of these are public in the bytecode);
  • inheriting sealed classes/traits (even though this may not be enforced by the bytecode);
  • using *.internal.* packages (e.g., dev.tauri.choam.internal.mcas);
  • using unsafe APIs (e.g., Rxn.unsafe.retry or the contents of the dev.tauri.choam.unsafe package).
  • using the contents of the dev.tauri.choam.stm package (our STM is experimental for now)
• There is no backwards compatibility for these modules:
  • choam-ce
  • choam-zi
  • choam-mcas
  • choam-internal
  • choam-laws
  • choam-stream
  • choam-profiler
  • choam-docs
  • (and all unpublished modules)
• There is no backwards compatibility for "hash" versions (e.g., 0.4-39d987a or 0.4.3-2-39d987a).
• See also the next section (platforms).

• Platforms:
  • JVM:
    • versions ⩾ 11
    • tested on OpenJDK, Graal, and OpenJ9 (but should work on others)
    • for secure random number generation, either the Windows-PRNG or (/dev/random and /dev/urandom) need to be available
  • Scala.js:
    • works, but not really interesting (we assume no multithreading)
    • provided to make cross-compiling easier for projects which use CHOAM
    • for secure random number generation, a java.security.SecureRandom implementation needs to be available (see here)
  • Scala Native:
    • support is completely experimental
    • support on Windows is even more experimental
    • no backwards compatibility
• Scala versions: cross-compiled for 2.13 and 3.3

Rxns are lock-free by construction, if the following assumptions hold:

• No "infinite loops" are created (e.g., by infinitely recursive flatMaps)
• No unsafe operations are used (e.g., Rxn.unsafe.retry is obviously not lock-free)
• We assume instances of FunctionN to be pure and total
• We assume that no dynamic type tests are performed on objects provided by CHOAM
  • i.e., the dynamic type of these objects is not part of their public API
  • e.g., don't do this:

    def foo(ref: Ref[String]) = ref match { // DON'T do this
      case ar: java.util.concurrent.atomic.AtomicReference[_] =>
        ... // use `ar`
    }

• We assume that certain JVM operations are lock-free; some examples are:
  • VarHandle operations (e.g., compareAndSet)
    • in practice, this is true on 64-bit platforms
    • on 32-bit platforms some of these might use a lock
  • GC and classloading
    • in practice, the GC sometimes probably uses locks
    • and classloaders sometimes also might use locks
  • ThreadLocalRandom, ThreadLocal
• Certain Rxn operations require extra assumptions:
  • Rxn.slowRandom and UUIDGen use the OS RNG, which might block (although we really try to use the non-blocking ones)
  • in AsyncReactive we assume that calling a Cats Effect Async callback is lock-free (in cats.effect.IO, as of version 3.6.3, this is not technically true)
• Executing a Rxn with a Rxn.Strategy other than Rxn.Strategy.Spin is not necessarily lock-free
• Only the default Mcas is lock-free, other Mcas implementations may not be

Also note, that while Rxn operations are lock-free (if these assumptions hold), operations in an async F[_] effect might not be lock-free (an obvious example is Promise#get, which is an async F[A], not a Rxn).