Unique ID Generation

Info

This example is for Challenge #2: Unique ID Generation

In this challenge we generate globally-unique IDs in a distributed network

Imports

import com.bilalfazlani.zioMaelstrom.*
import zio.json.{JsonDecoder, JsonEncoder}
import zio.{ZIO, Ref, ZLayer}

Here, we define the protocol of the node. It includes messages which the node can handle and messages it can send

Message definitions

case class Generate(msg_id: MessageId) extends NeedsReply derives JsonDecoder
case class GenerateOk(id: String, in_reply_to: MessageId, `type`: String = "generate_ok")
    extends Sendable,
      Reply derives JsonEncoder

Unlike echo, this node has some state which we have modeled using Ref[Int]. We increment the Int every time we generate a new Id. To make it unique across the cluster, we append the node Id to the generated id.

Why use a Ref?

Using a Ref ensures that I can update the state in a thread-safe manner. This is important because the messages are received and processed concurrently

Node application

object Main extends MaelstromNode {

  val program = receive[Generate] { case request =>
    for {
      generated <- ZIO.serviceWithZIO[Ref[Int]](_.updateAndGet(_ + 1))
      combinedId = s"${me}_${generated}" // (1)!
      _ <- reply(GenerateOk(id = combinedId, in_reply_to = request.msg_id))
    } yield ()
  }.provideSome[MaelstromRuntime](ZLayer(Ref.make(0)))
}

1. me method returns the NodeId of self node. It's a context function which is only available inside receive block

I have used ZLayer to inject the state and also to make sure the same Ref is used across the codebase in case we want to make the code more modular.

Tip

Note the use of .provideSome to provide Ref[Int] layer to the program. This method provides all the layers except MaelstromRuntime.

Note

Source code for this example can be found on Github