Making Implemetation More Generic With Scala and Cats

Question

I have this in-memory implementation of a simple Cache in Scala using cats effects.

Here is my trait:

trait Cache[F[_], K, V] {
  def get(key: K): F[Option[V]]
  def put(key: K, value: V): F[Cache[F, K, V]]
}

import cats.effect.kernel.Async

case class ImmutableMapCache[F[_]: Async, K, V](map: Map[K, V]) extends Cache[F, K, V] {
  override def get(key: K): F[Option[V]] =
    Async[F].blocking(map.get(key))

  override def put(key: K, value: V): F[Cache[F, K, V]] =
    Async[F].blocking(ImmutableMapCache(map.updated(key, value)))
}

object ImmutableMapCache {
  def empty[F[_]: Async, K, V]: F[Cache[F, K, V]] =
    Async[F].pure(ImmutableMapCache(Map.empty))
}

Is this a good enough implementation? I'm restricting my effect to Async. Can I make it even more generic to work with other effect types in my ImmutableMapCache?

What other pitfalls are there with my approach?

EDIT:

Is this a better implementation where I wrap the Map in a Cats Ref context?

import cats.effect.{Ref, Sync}
import cats.syntax.all._

class SimpleCache[F[_]: Sync, K, V] extends Cache[F, K, V] {
  private val cache: Ref[F, Map[K, V]] = Ref.unsafe[F, Map[K, V]](Map.empty)

  override def put(key: K, value: V): F[Unit] = cache.update(_.updated(key, value))

  override def get(key: K): F[Option[V]] = cache.get.map(_.get(key))
}

Why are you using an Immutable Map for something like a cache which you would want to support high performance mutations ? Also... if are you using blocking in the Async context then why even use Async ? In creating an Immutable Cache... you are likely to be updating the variable holding the cache to the new cache on every put... but this is opening the doors for race conditions when accessed by multiple threads. You are doing a lot of things which you would absolutely not want from a Cache implementation. — sarveshseri
– sarveshseri, Commented Sep 11, 2023 at 9:28
Ref uses AtomicReference underneath so it is safe to use in multithreaded context. — Mateusz Kubuszok
– Mateusz Kubuszok, Commented Sep 11, 2023 at 14:48

Luis Miguel Mejía Suárez · Accepted Answer · 2023-09-11 18:30:57Z

2

First of all, the right answer is not to reinvent the wheel, and just use a library that already does all this, like mules.

However, for the sake of learning, let's take a look to some of the things you could improve.

Interface. Especially put

def put(key: K, value: V): F[Cache[F, K, V]]

If putting a new value in the Cache returns a new one, it means it is immutable, if it is immutable there is no need for effects, meaning it is just a simple Map.
You want your put to mutate something; but in a concurrent-safe way. So it could actually be used to share data between different Fibers. Thus, put should be defined like this:

def put(key: K, value: V): F[Unit]

Creation. Since a Cache is a mutable state, its creation must be an effect as well; like your original example but unlike your attempt with Ref

def empty[F[_], K, V]: F[Cache[F, K, V]]

Implementation. Your intuition was right, we want to use a mutable reference to an immutable Map. Now, in order to make it concurrent safe, we need to either look the access to it, or use a CAS loop. cats-effect provides both options: AtomicCell and Ref respectively. In this case is better to just use a CAS loop so we go with Ref

object Cache {
  def empty[F[_], K, V]: F[Cache[F, K, V]] =
    Ref[F].of(Map.empty[K, V]).map { ref =>
      new Cache[F[_], K, V] {
        override def get(key: K): F[Option[V]] =
          ref.get.map(map => map.get(key))

        override def put(key: K, value: V): F[Unit] =
          ref.update(map => map.updated(key, value))
      }
    }
}

The constraints, the above code needs a constraint on F to actually work. But actually, we don't need all the Async power, but rather just Concurrent, since all we need is to create a Ref :)

def empty[F[_] : Concurrent, K, V]: F[Cache[F, K, V]] = ...

edited Sep 11, 2023 at 18:30

answered Sep 11, 2023 at 16:22

Luis Miguel Mejía Suárez

23k4 gold badges31 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

joesan Over a year ago

Thanks for the explanation. So with that addition of the empty method, I can get rid of the local val cache that I create using Ref. Correct?

Luis Miguel Mejía Suárez Over a year ago

@joesan yes, especially because that one was "technically" wrong :)

joesan Over a year ago

Ok, so that empty method definition goes in the trait. Correct? I guess I also do not need the type constraint on the empty method as I have it on the trait.

Luis Miguel Mejía Suárez Over a year ago

@joesan no, it would go on the companion object, it is a factory.

Collectives™ on Stack Overflow

Making Implemetation More Generic With Scala and Cats

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related