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
Ref
s (mutable memory locations with a pure API).- For example, if
x
is aRef[Int]
, thenx.update(_ + 1)
is aRxn[Unit]
which (when executed) will increment its value.
- For example, if
- Multiple
Rxn
s can be composed (by using various combinators), and the resultingRxn
will update all affected memory locations atomically.- For example, if
y
is also aRef[Int]
, thenx.update(_ + 1) *> y.update(_ + 1)
will increment both of them atomically.
- For example, if
libraryDependencies += "dev.tauri" %%% "choam-core" % choamVersion // see above for latest version
The choam-core
module contains the fundamental types for working with Rxn
s.
For more modules, see below.
The complete version of the example above, (which increments the value of
two Ref
s) 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
).
-
- core types, like
Rxn
andRef
- integration with effect types implementing the
Cats Effect typeclasses
(specifically
Sync
/Async
) - experimental software transactional memory (STM) built on
Rxn
- core types, like
-
choam-data
: concurrent data structures built onRxn
- Examples: queues, stacks, hash- and ordered maps and sets
-
- Asynchronous data structures; some of their operations are
semantically blocking (i.e., fiber blocking
),
and so are in an
F[_] : Async
(note, that theseF[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 aRxn
, and can be waited on as an asyncF[_]
:trait Promise[A] { // simplified API def complete(a: A): Rxn[Boolean] def get[F[_]]: F[A] }
- Asynchronous data structures; some of their operations are
semantically blocking (i.e., fiber blocking
),
and so are in an
-
choam-stream
: integration withfs2.Stream
s -
choam-ce
: integration withcats.effect.IOApp
(for convenience) -
choam-zi
: integration withzio.ZIOApp
(for convenience) -
choam-profiler
: JMH profiler "plugin" forRxn
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) implementationschoam-internal
: a concurrent skip list map and other utilities for internal usechoam-laws
: properties fulfilled by the variousRxn
combinators
JARs are on Maven Central. Browsable Scaladoc is available here.
- Our
Rxn
is an extended version of reagents, described in the Reagents paper1 (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 thedev.tauri.choam.unsafe
package.)- The interpreter (that executes
Rxn
s) is stack-safe. - We also support composing
Rxn
s which modify the sameRef
(thus, anRxn
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.2
- The current version uses EMCAS by Guerraoui et al.3;
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 paper1 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 (see, e.g., the "retry" STM operation, called "modular blocking" in Haskell4). - 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 thechoam-async
module). This feature can be used to provide such "waiting" functionality (e.g., with thedev.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 withOption
,Either
, or similar). - Some STM systems allow access to transactional memory from
non-transactional code;
Rxn
doesn't support this, the contents of aRef[A]
can only be accessed from inside aRxn
.
- A
- Similarities between
Rxn
s and STM transactions include the following:- Atomicity, consistency and isolation.
Rxn
also provides a correctness property called opacity5; 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 runningRxn
s (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.
- TL26 and SwissTM7:
the system which guarantees opacity (see above) for
Rxn
s 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 paper8.
- Haskell:
- A
"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-*"))
- In sbt ⩾ 1.10.0 this can be ensured like this:
- 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 thedev.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
or0.4.3-2-39d987a
).
- 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)
- JVM:
- Scala versions: cross-compiled for 2.13 and 3.3
Rxn
s are lock-free by construction, if the following assumptions hold:
- No "infinite loops" are created (e.g., by infinitely recursive
flatMap
s) - 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 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.secureRandom
andUUIDGen
use the OS RNG, which might block (although we really try to use the non-blocking ones)- in
choam-async
we assume that calling a CEAsync
callback is lock-free (incats.effect.IO
, as of version 3.5.7, this is not technically true)
- Executing a
Rxn
with aRxn.Strategy
other thanRxn.Strategy.Spin
is not necessarily lock-free - Only the default
Mcas
is lock-free, otherMcas
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
).
Footnotes
-
Turon, Aaron. "Reagents: expressing and composing fine-grained concurrency." In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 157-168. 2012. ↩ ↩2
-
Harris, Timothy L., Keir Fraser, and Ian A. Pratt. "A practical multi-word compare-and-swap operation." In Distributed Computing: 16th International Conference, DISC 2002 Toulouse, France, October 28–30, 2002 Proceedings 16, pp. 265-279. Springer Berlin Heidelberg, 2002. ↩
-
Guerraoui, Rachid, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi. "Efficient Multi-Word Compare and Swap." In 34th International Symposium on Distributed Computing. 2020. ↩
-
Harris, Tim, Simon Marlow, Simon Peyton-Jones, and Maurice Herlihy. "Composable memory transactions." In Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pp. 48-60. 2005. ↩
-
Guerraoui, Rachid, and Michal Kapalka. "On the correctness of transactional memory." In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pp. 175-184. 2008. ↩
-
Dice, Dave, Ori Shalev, and Nir Shavit. "Transactional locking II." In International Symposium on Distributed Computing, pp. 194-208. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. ↩
-
Dragojević, Aleksandar, Rachid Guerraoui, and Michal Kapalka. "Stretching transactional memory." ACM sigplan notices 44, no. 6 (2009): 155-165. ↩
-
Zhang, Rui, Zoran Budimlic, and William N. Scherer III. Commit phase variations in timestamp-based software transactional memory. Technical Report TR08-03, Rice University, 2008. ↩