client-libraries/scala/src/main/scala/com/redis/HashRing.scala

   1 package com.redis
   2
   3 /**
   4  * Hash Ring
   5  *
   6  */
   7
   8 import java.util.zip.CRC32
   9 import scala.collection.mutable.ArrayBuffer
  10 import scala.collection.mutable.Map
  11
  12 trait HashRing {
  13
  14   val replicas: Int
  15
  16   var sortedKeys: List[Long] = List()
  17   var cluster = new ArrayBuffer[Redis]
  18   val ring = Map[Long, Redis]()
  19
  20   // Adds the node to the hashRing
  21   // including a number of replicas.
  22   def addNode(node: Redis) = {
  23     cluster += node
  24     (1 to replicas).foreach{ replica =>
  25       val key = calculateChecksum(node+":"+replica)
  26       ring += (key -> node)
  27       sortedKeys = sortedKeys ::: List(key)
  28     }
  29     sortedKeys = sortedKeys.sort(_ < _)
  30   }
  31
  32   // get the node in the hash ring for this key
  33   def getNode(key: String) = getNodePos(key)._1
  34
  35   def getNodePos(key: String): (Redis, Int) = {
  36     val crc = calculateChecksum(key)
  37     val idx = binarySearch(crc)
  38     (ring(sortedKeys(idx)), idx)
  39   }
  40
  41   // TODO this should perform a Bynary search
  42   def binarySearch(value: Long): Int = {
  43     var upper = (sortedKeys.length -1)
  44     var lower = 0
  45     var idx   = 0
  46     var comp: Long = 0
  47
  48     while(lower <= upper){
  49       idx = (lower + upper) / 2
  50       comp = sortedKeys(idx)
  51
  52       if(comp == value) { return idx }
  53       if(comp < value)  { upper = idx -1 }
  54       if(comp > value)  { lower = idx +1 }
  55     }
  56     return upper
  57   }
  58
  59   // Computes the CRC-32 of the given String
  60   def calculateChecksum(value: String): Long = {
  61     val checksum = new CRC32
  62     checksum.update(value.getBytes)
  63     checksum.getValue
  64   }
  65 }
  66