Proposal: ReadWriteLock for cats-effect-std

[stasimus]

std has Mutex and KeyedMutex, but nothing for shared/exclusive locking. The need shows up whenever many fibers read state that gets replaced once in a while: config reload, cache refresh, swapping a connection after re-auth. Mutex works but serializes the readers against each other for no reason. The usual workaround is Semaphore(n) where a reader takes 1 permit and a writer takes all n, which forces an arbitrary bound on concurrent readers and makes writer acquisition O(n).

Proposed API, following Mutex:

trait ReadWriteLock[F[_]] {

  /** Shared lock. Many fibers may hold it at once, as long as no writer holds or awaits the lock. */
  def readLock: Resource[F, Unit]

  /** Exclusive lock. Held by at most one fiber, with no concurrent readers. */
  def writeLock: Resource[F, Unit]

  def mapK[G[_]](f: F ~> G)(implicit G: MonadCancel[G, _]): ReadWriteLock[G]
}

object ReadWriteLock {
  def apply[F[_]](implicit F: Concurrent[F]): F[ReadWriteLock[F]]
  def in[F[_], G[_]](implicit F: Sync[F], G: Async[G]): F[ReadWriteLock[G]]
}

Semantics:

• any number of concurrent readers, writers are exclusive
• write-preferring: once a writer is queued, later readers wait behind it, otherwise a steady stream of readers would starve writers forever; readers arriving while a read batch is active join that batch
• non-reentrant, same as Mutex: writeLock inside readLock (or any nesting that waits on itself) deadlocks
• cancelation safe: a canceled waiter gives up its queue slot and unblocks whoever is behind it

Prior art: java.util.concurrent.locks.ReentrantReadWriteLock, ZIO's TReentrantLock, and ReadWriteRef in evolution-gaming/cats-helper, which has these exact semantics on plain Concurrent and has been running in production for a few years. I'd be happy to contribute the implementation adapted to std conventions. It could probably sit on top of LockQueue, which Mutex and KeyedMutex already share.

Open questions:

• name: ReadWriteLock vs something shorter
• reentrancy: I'd keep it out of scope, consistent with Mutex
• a value-holding variant later (a ReadWriteRef, the way AtomicCell pairs a value with Mutex)? The lock alone seems like the right primitive to start with.

[durban]

We already have an RW-lock implementation inside Hotswap, though it is not accessible publicly. It uses a Semaphore, as you mention. But what do you mean "makes writer acquisition O(n)"? (Also: the "arbitrary bound" is Long.MaxValue, which is... arbitrary, sure, but I'd think it should be plenty.)

I did not yet look at the implementation you propose adding here. Could you please summarize the differences between that and the semaphore-based implementation?

In general, I'm somewhat wary about adding even more lock-variants to std. We already have Mutex, KeyedMutex and Semaphore. After this, the obvious next one could be KeyedReadWriteLock...