欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 后台管理


新闻资讯

MENU

软件开发知识
原文出处: koala bear

简介

为了办理漫衍式 web 中的热点问题,David Karger 于 1997 年提出 一致性哈希(Consistent Hashing),论文请见 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web(较难领略)。一致性哈希遍及的运用于多种漫衍式系统中,如 memcache/redis,gluster file system, zookooper 等。

  • Swift: Building a Consistent Hashing Ring
  • Cassandra: Consistent Hashing in Cassandra
  • Redis/Memcache: Memcache的一致性hash算法利用
  • 本文主要先容一致性哈希的道理。

    道理

    去中心与程度扩展

    以 web 为例,cache 节点(如 Redis, Memcache)遍及用于 web 中,以晋升机能。跟着 web 局限扩大,单个节点无论是从机能上照旧容量上都无法支撑大局限的业务,所以需要用多个节点以晋升机能和容量。

    在多个节点下,给定某个 object,客户端如何知道它存储在哪个节点呢?最简朴的做法是选取某个节点做为元数据处事器,记录每个 object 存放的节点,每次会见该 object 时,客户端首先会见元数据处事器,获取其所存放的节点,最后从该节点获取 object。元数据处事器需要维护所有 object 的位置信息,而且每次会见 object 都需要先会见元数据处事器,如此,元数据处事器容易成为机能和容量的瓶颈,倒霉于大局限扩展。

              1. Fetch       +-----------------+
    client  ------------->   | Metadata Server |   bottleneck
               Location      +-----------------+
           
              2. Access      +-----------------+
            ------------->   | Cache Server X  |
             Cache Server    +-----------------+

    去中心化的系统最大利益之一就是易程度扩展,那是否有步伐可以去除上述元数据处事器呢。谜底是必定的,好比计较 object 的 hash 值,然后匀称的漫衍到各个节点上。

    hash(object) mod N        个中 N 为节点数目

    可是假如某个节点宕机,剔除宕机节点后数目为 N – 1,此时映射干系变为:

    hash(object) mod (N - 1)

    别的,大概由于负载过高,需要新增一个节点,此时映射干系为:

    hash(object) mod (N + 1)

    无论是增加照旧淘汰节点,都有大概会改变映射干系,造成大量请求的 miss。那是否能制止大量的 miss 呢?谜底也是必定的,一致性哈希办理了节点增减造成大量 hash 重定位的问题。

    道理与增删节点

    一致性哈希的道理如下:

  • 将每个节点(node)映射到数值空间 [0, 2^32 - 1],映射的法则可为 IP、hostname 等。
  • 将每个 object 映射到数值空间 [0, 2^32 - 1]。
  • 对付某个 object,对付所有满意 hash(node) <= hash(object) 的节点,选择 hash(node) 最大的节点存放 object。假如没有满意上述条件的节点,选择 hash(node) 最小的节点存放该 object,如下图。
  • hash ring

    当某个节点宕机时,仅有该节点的工具被重哈希到相邻节点上。

    hash ring delete

    与此雷同,当新增一个节点时,仅有一个节点的部门 object 需要重哈希。

    hash ring add

    虚节点与均衡性

    节点的位置是由自身哈希值抉择的,它们的漫衍并非匀称,出格当节点数目很少时,容易造成 object 的漫衍不匀称,即均衡性低,譬喻:

    unbalance

    为了办理这个问题,我们引入虚拟节点,虚拟节点实际上是物理节点的复成品,一个物理节点包括多个虚拟节点,我们将这些虚拟节点映射到数值空间 [0, 2^32 - 1],对付某个 object,昆山软件公司,我们按照上节步调计较该 object 存放的虚拟节点,进而得出物理节点。如下图共有 2 个物理节点,每个物理节点有三个虚拟机节点。当虚拟节点越多,昆山软件开发,虚拟节点的位置漫衍越匀称,相应的,映射到物理节点的 object 数目也越匀称,提高了均衡性。

    virtual node

    总结

    通过一致性哈希,客户端可以在当地计较 object 的存放位置,去除了中心节点,使得系统容易程度扩展,便于按需晋升/低落整体的容量和机能,同时制止了每次增删节点造成大量哈希重定位的问题,最大化的淘汰了数据迁移。为使 object 可以或许尽大概平衡的分手在各个节点上,一致性哈希引入了虚节点,昆山软件开发,以提高均衡性。