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]
      }

    • async (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[_]):
    • queues
    • stacks
• choam-stream: integration with FS2 Streams
• choam-laws: properties fulfilled by the various Rxn combinators
• 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 (unless it's infinitely recursive, or an unsafe method was used to create it); 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.ringBuffer 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 (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 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.