CHOAM

Experiments with composable lock-free concurrency

Overview

The type Rxn[-A, +B] is similar to an effectful function from A to B (that is, A => F[B]), 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 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.

Modules

• choam-core:
  • core types, like Rxn and Ref
  • integration with synchronous effect types in Cats Effect
• choam-data: concurrent data structures:
  • queues
  • stacks
  • hash- and ordered maps and sets
  • counter
• choam-async:
  • Integration with asynchronous effect types in Cats Effect:
    • The main integration point is a Promise, which can be completed as a Rxn, and can be waited on as an async F[_]:

      trait Promise[F[_], A] {
        def complete: Rxn[A, Boolean]
        def get: F[A]
      }
      

    • Asynchronous (dual) data structures can be built on this primitive
  • Async data structures; some of their operations are semantically blocking (i.e., fiber blocking ), and so are in an async F[_] (note, that these F[A] operations are – obviously – not lock-free):
    • queues
    • stacks
    • CountDownLatch
• choam-stream: integration with FS2 Streams
• choam-laws: properties fulfilled by the various Rxn combinators
• 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-skiplist: a concurrent skip list map for internal use

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

Related work

• Our Rxn is an extended version of reagents, described in Reagents: Expressing and Composing Fine-grained Concurrency . (Other implementations or reagents: Scala, OCaml, 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 ("pure functional" / "programs as values") API.
  • 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:
  • A Practical Multi-Word Compare-and-Swap Operation (an earlier version used this algorithm)
  • Efficient Multi-word Compare and Swap (Mcas.Emcas implements a variant of this algorithm; this is the default algorithm we use on the JVM)
  • A simple, non-lock-free algorithm from the Reagents paper (see above) is implemented as Mcas.SpinLockMcas (we use it for testing)
• Software transactional memory (STM)
  • A Rxn is somewhat similar to a memory transaction, but there are important differences:
    • A Rxn is lock-free by construction (but see below); STM transactions are not (necessarily) lock-free (e.g., STM "retry").
    • As a consequence of the previous point, Rxn cannot be used to implement "inherently not 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., dev.tauri.choam.async.AsyncQueue.unbounded is a queue with enqueue in Rxn and deque in, e.g., IO or another async F[_]).
    • The implementation (the Rxn interpreter) is also lock-free; STM implementations are usually not (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 an r: Ref[A] can only be accessed from inside a Rxn (although there is a read-only almost "escape hatch": r.unsafeDirectRead).
  • Similarities between Rxns and STM transactions include the following:
    • atomicity
    • consistency
    • isolation
    • Rxn also provides a correctness property called opacity; a lot of STM implementations also guarantee this property (e.g., scala-stm), 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: scala-stm, cats-stm, ZSTM.
    • 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.

Compatibility and assumptions

"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 for APIs which are
  • inside *.internal.* packages (e.g., dev.tauri.choam.internal.mcas);
  • called unsafe* (e.g., Rxn.unsafe.retry or Ref#unsafeCas).
• There is no backwards compatibility for these modules:
  • choam-laws
  • choam-stream
  • choam-profiler
  • (and all unpublished modules)
• There is no backwards compatibility for "hash" versions (e.g., 0.4-39d987a; these are not even SemVer compatible).

Supported platforms:

• Platforms:
  • JVM:
    • versions ⩾ 11
    • tested on OpenJDK, Graal, and OpenJ9 (but should work on others)
    • Rxn.secureRandom and UUIDGen both need either the Windows-PRNG or (/dev/random and /dev/urandom) to be available
  • Scala.js:
    • works, but not really useful (we assume no multithreading)
    • provided to ease cross-compiling
• Scala versions: cross-compiled for 2.13 and 3.3

Lock-freedom

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

• No "inifinite loops" are created (e.g., by 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 certain JVM operations are lock-free:
  • VarHandle operations (e.g., compareAndSet)
    • in practice, this is true only on 64-bit platforms
  • GC and classloading
    • in practice, this is not true
  • ThreadLocalRandom, ThreadLocal
• Certain Rxn operations require extra assumptions:
  • Rxn.secureRandom and UUIDGen use the OS RNG, which may block (although we really try to use the non-blocking ones)
  • operations in F[_] might not be lock-free (an obvious example is Promise#get)
  • in choam-async we assume that calling a CE Async callback is lock-free (in cats.effect.IO, as of version 3.5.4, this is not technically true)
• Executing a Rxn with a Rxn.Strategy other than Rxn.Strategy.Spin is not lock-free
• Only Mcas.DefaultMcas is lock-free, other Mcas implementations may not be