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

There are two aspects that differentiate Bengal from other STM implementations:

• Bengal runtime scheduler: The Bengal runtime uses a custom scheduler that is not blindly optimistic. Transactions are scheduled based on a fast, static analysis of the transaction variable domain to lower the chances of transactions needing to be retried. This ensures consistent performance, even for highly-contentious transactional variables/maps.
• Transactional Maps: In addition to transactional variables, the implementation includes performant transactional maps as a core API data structure. This data structure provides performance benefits above wrapping an entire map in a transactional variable.

As there are already many solid references on STM, I will not dive into STM theory here. However, I do highly recommend the writeup in Beautiful Concurrency for those interested in learning about this concurrency pattern.

To use Bengal-STM in an existing SBT project with Scala 2.12 or a later version, add the following dependency to your build.sbt:

libraryDependencies += "ai.entrolution" %% "bengal-stm" % VERSION

See the Maven badge above for the latest version.

Note in the below that the better-monadic-for compiler plugin is used to expose the STM runtime as an implicit in the monadic computation. This is avoids the use of unsafeRunSync to expose the runtime instance, while not requiring the runtime to be explicitly passed to the sub-programs.

import bengal.stm.STM
import bengal.stm.model._
import bengal.stm.syntax.all._

import cats.effect.{IO, IOApp}

import scala.concurrent.duration._

object Main 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 {
          accounts.toList.foreach { acc =>
            println(s"${acc._1}: ${acc._2}")
          }
        }
      } 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 ()
  }
}

Take a look at the Medium article on PR FAQs for a good overview of the concept. I have taken some liberties with the formatting, but I generally like the concept of a living FAQ to help introduce products.

I found that blindly optimistic execution strategies led to very poor performance of STM in a number of production scenarios. The situation could only be remedied by sequentially executing queued transactions within a given runtime. I.e. the transactional nature of STM became moot, as I was essentially reducing concurrent execution back down to sequential execution. Thus, I decided to build an STM backed by a scheduler that was more conducive to handling high-contention scenarios, while still being genuinely concurrent.

Beyond the scheduler, I also wanted to explore adding Map as a fundamental transactional data structure to analogise the concept of an index in a DB. This presents some interesting challenges with scheduling around structural (i.e. the 'CRD' in 'CRUD') updates to the map itself, but it's a data structure I just found to be very useful in transactional contexts.

Indeed, cats-stm already exists and provides a nice STM implementation for Cats Effect (Try it!).

Given the requirements I had for the transaction scheduler, I decided that the underpinning implementation would be quite different than cats-stm. In particular, this implementation is based on Free Monads that use different interpreters for static analysis and building the transactional log.

Also, while APIs are quite similar, there are some differences between Bengal and cats-stm. For example, cats-stm has a way to bypass retries with orElse, which is not something present in Bengal (this is an intentional design decision). Also, initialisation of TxnVar and TxnVarMap happen outside the context of the Txn[_] monad.

I wanted waitFor to have a clear semantic delineation from an if statement in the monadic construction. While there is arguably a missed opportunity to define a canonical Semigroup via such a bypass, I have opted for a simpler API (for the time being).

In addition to this, Bengal short-circuits the rest of the monadic evaluation when encountering a failed waitFor predicate. This performance optimisation is not possible if we need to search the computation spec for a waitFor bypass.

Bengals are a very playful and active cat breed. I figured the name worked for something built on Cats ;).