一致性哈希算法

以分布式的网络爬虫为例，一致性哈希的基本算法如下：

整个系统里使用相同的Hash算法。首先假定一个2^n的值，比如假定n=32，那么是4294967296。然后对每个节点进行Hash计算（如使用提供服务的IP和端口进行Hash计算），得到每个Cache节点的一个Hash，把这个Hash值放在这个DHT（Distributed Hash Tables）圆里。若有N各节点，则整个圆被分成N部分。待处理的url同样也要进行hash计算，然后从顺时针开始，找到第一个可用的节点，进行服务。

这样做得好处是：一旦某个节点挂掉，那么受影响的只有坏节点和它逆时针的第一个节点之间的数据。

使用scala实现上面的算法

class ConsistentHashNode(num:Int) {
  val urls = mutable.Set.empty[String]

  override def toString = num.toString
}

object ConsistentHashNode extends App {
  val nodes = (1 to 10).map { i =>
    val node = new ConsistentHashNode(i)
    (node, node.hashCode)
  }.sortBy {
    case (node, hash) => hash
  }


  val urls = List("www.baidu.com", "www.google.com", "www.ask.com")

  urls.foreach {
    url =>
      val node = chooseServer(url)
      println(s"$url => node $node")
  }

  nodes.foreach {
    case (node, _) =>
      println(s"$node works ${node.urls mkString ","}")
  }

  def chooseServer(url: String): ConsistentHashNode = {
    val fn = nodes.find {
      case (node, hash) =>
        hash > url.hashCode
    }.getOrElse(nodes.last)._1
    fn.urls+=url
    fn
  }
}

Published: February 25 2015

category:
算法 8