The Ring

JustinDB applies modified version of Consistent Hashing to map objects along the edge of a circle (the ring).

Just to recall JustinDB is a key-value database so you can think about it as a big distributed hashtable. Every single data we save is identifiable in the system by its key (UUID actually).

But how exactly JustinDB know what node is responsible for handling request (storing/fetching value)? This is where already mentioned Consistent Hashing algorithm take place. 👍

Consistent Hashing

Let visualise cluster of 5 nodes size. This is our space we can cover with data. JustinDB employs such algorithm to uniform data distribution. This space is divided into equal partitions called “vnodes”. These vnodes are evenly distributed amongst participating physical nodes in the cluster.

JustinDB uses very simplistic version of mapping data UUID key to particular vnode.

object UUID2RingPartitionId extends ((UUID, Ring) => Ring.RingPartitionId) {
  override def apply(id: UUID, ring: Ring): RingPartitionId = scala.math.abs(id.hashCode()) % ring.size
}

Participating nodes in a JustinDB cluster are homogeneous - every node in the cluster knows where data should reside within the cluster. Requests for data can target any node. It will horizontally access data from the proper nodes, and return the result.

Ring is represented as a wrapper around Map datastructure that know what vnode (other name: ring’s partitionId) belongs to which cluster node.

class Ring(private val ring: Map[RingPartitionId, NodeId])

You can find these snippets here. 💪