Software Transactional Memory for Cats Effect with intelligent scheduling.

Bengal STM is a library for writing composable concurrency operations based on in-memory transactions. The library handles all aspects of concurrency management including locking, retries, semantic blocking, and optimised transaction scheduling. STM provides a higher-level concurrency abstraction that offers a safe, efficient, and composable alternative to locks, mutexes, and other low-level primitives.

• Intelligent Runtime Scheduler: Unlike blindly optimistic STM implementations, Bengal's runtime uses a custom scheduler that performs fast static analysis of transaction variable domains to reduce retry likelihood. This ensures consistent performance even for highly-contentious transactional variables.

• First-Class Transactional Maps: In addition to transactional variables (TxnVar), Bengal includes performant transactional maps (TxnVarMap) as a core API data structure, providing performance benefits over wrapping an entire map in a transactional variable.

• Cats Effect Integration: Built on Cats Effect for seamless integration with the Typelevel ecosystem.

• Java: 21 or later
• Scala: 2.13.x

Add the following dependency to your build.sbt:

libraryDependencies += "ai.entrolution" %% "bengal-stm" % "<version>"

See the Maven Central badge above for the latest version.

import bengal.stm.STM
import bengal.stm.model._
import bengal.stm.syntax.all._
import cats.effect.{IO, IOApp}

object QuickStart extends IOApp.Simple {
  def run: IO[Unit] =
    for {
      stm     <- STM.runtime[IO]
      counter <- stm.TxnVar.of(0)
      _       <- counter.modify(_ + 1).commit(stm)
      value   <- counter.get.commit(stm)
      _       <- IO.println(s"Counter: $value")
    } yield ()
}

This example demonstrates transactional transfers between accounts with semantic blocking until the bank opens:

import bengal.stm.STM
import bengal.stm.model._
import bengal.stm.syntax.all._
import cats.effect.{IO, IOApp}
import scala.concurrent.duration._

object BankTransfer extends IOApp.Simple {

  def run: IO[Unit] = {
    def createAccount(
        name: String,
        initialBalance: Int,
        accounts: TxnVarMap[IO, String, Int]
    )(implicit stm: STM[IO]): IO[Unit] =
      accounts.set(name, initialBalance).commit

    def transferFunds(
        accounts: TxnVarMap[IO, String, Int],
        bankOpen: TxnVar[IO, Boolean],
        to: String,
        from: String,
        amount: Int
    )(implicit stm: STM[IO]): IO[Unit] =
      (for {
        balance    <- accounts.get(from)
        isBankOpen <- bankOpen.get
        _          <- STM[IO].waitFor(isBankOpen)
        _          <- STM[IO].waitFor(balance.exists(_ >= amount))
        _          <- accounts.modify(from, _ - amount)
        _          <- accounts.modify(to, _ + amount)
      } yield ()).commit

    def openBank(
        bankOpen: TxnVar[IO, Boolean]
    )(implicit stm: STM[IO]): IO[Unit] =
      for {
        _ <- IO.sleep(1000.millis)
        _ <- IO.println("Bank Open!")
        _ <- bankOpen.set(true).commit
      } yield ()

    def printAccounts(
        accounts: TxnVarMap[IO, String, Int]
    )(implicit stm: STM[IO]): IO[Unit] =
      for {
        accounts <- accounts.get.commit
        _ <- IO.println(accounts.toList.map { case (k, v) => s"$k: $v" }.mkString(", "))
      } yield ()

    for {
      implicit0(stm: STM[IO]) <- STM.runtime[IO]
      bankOpen                <- TxnVar.of(false)
      accounts                <- TxnVarMap.of[IO, String, Int](Map())
      _                       <- createAccount("David", 100, accounts)
      _                       <- createAccount("Sasha", 0, accounts)
      _                       <- printAccounts(accounts)
      _                       <- openBank(bankOpen).start
      _                       <- transferFunds(accounts, bankOpen, "Sasha", "David", 100)
      _                       <- printAccounts(accounts)
    } yield ()
  }
}

Note: The example uses the better-monadic-for compiler plugin to expose the STM runtime as an implicit in the for-comprehension.

For an introduction to STM concepts, see Beautiful Concurrency by Simon Peyton Jones.

Blindly optimistic execution strategies can lead to poor performance in high-contention scenarios. In production, this sometimes required falling back to sequential transaction execution, negating the benefits of STM. Bengal addresses this with a scheduler that performs static analysis to reduce contention, enabling genuine concurrency even in high-contention scenarios.

Additionally, Bengal treats Map as a fundamental transactional data structure (analogous to a database index), which presents interesting scheduling challenges around structural updates but proves very useful in practice.

cats-stm is an excellent STM implementation for Cats Effect. Bengal differs in:

• Implementation: Bengal uses Free Monads with different interpreters for static analysis and building transactional logs
• API design: cats-stm has orElse for bypassing retries; Bengal intentionally omits this for clearer waitFor semantics
• Initialization: TxnVar and TxnVarMap initialization occurs outside the Txn[_] monad

waitFor is designed to have clear semantic delineation from conditional if statements. Bengal short-circuits monadic evaluation on failed waitFor predicates as a performance optimization, which wouldn't be possible if bypass mechanisms needed to be checked.

Bengals are a very playful and active cat breed. The name fits a library built on Cats.

Contributions are welcome! Please see CONTRIBUTING.md for guidelines.

Bengal STM is licensed under the Apache License 2.0.

Copyright 2023 Greg von Nessi