精华内容
下载资源
问答
  • 一致性哈希的使用与优缺点分析

    千次阅读 2019-03-14 17:19:44
    最近用到了一致性哈希,写一写总结一下。 一致性哈希常用在的负载均衡方面。 比如:在服务器的服务节点选择,线程池中线程的选择,路由等等。 我们可以将一致性哈希分配的单个节点看做是某个单个服务器,某一条...

    最近用到了一致性哈希,写一写总结一下。

    一致性哈希常用在的负载均衡方面。

    比如:在服务器的服务节点选择,线程池中线程的选择,路由等等。

    我们可以将一致性哈希分配的单个节点看做是某个单个服务器,某一条线程,某一个单独的路由目标。

    一致性哈希在负载均衡方面效果很好,因为它的设计目标是为了解决因特网中的热点(hot spot)问题。

    但是一致性哈希在某些特殊情况下的均衡效果反而不是特别的好(比如小规模节点的负载均衡)。

    具体原因我们来看实现代码。

    代码如下:

    头文件:

    /*
     * consistent_hash.h
     *
     *  Created on: Mar 7, 2019
     *      Author: clh01s
     */
    
    #ifndef CONSISTENT_HASH_H_
    #define CONSISTENT_HASH_H_
    
    #include <iostream>
    #include <string>
    #include <string.h>
    #include <list>
    #include <map>
    #include <unistd.h>
    #include <syscall.h>
    
    //自定义哈希工具
    typedef uint32_t (*CalcHashValFunc)(std::string key);
    
    /*
     * 一致性哈希节点实现的接口类
     */
    class ConNode
    {
    public:
    	ConNode(int nodeValue){_nodeValue = nodeValue;}
        /*
         * 生成节点key值的自定义函数:
         * virId 即此节点虚拟化编号;
         * 每一组其内部虚拟节点的key值相关性越低越好, 偏差越大越好, 这直接决定了负载的均衡性.
         */
    	 std::string getKeyCode(size_t virId)
    	 {
    		    char luck[128];
    		    unsigned long int r = random();
    		    //获取线程id
    		    size_t nTid = ::syscall(SYS_gettid);
    		    //组合一个随机的key
    		    snprintf(luck, sizeof(luck), "%lx%d%x", r, nTid, virId);
    
    		    return std::string(luck, strlen(luck));
    
    	 }
    	 int getNodeValue(){return _nodeValue;}
    private:
    	 int _nodeValue = 0;
    };
    
    class ConsistentHash
    {
    public:
    	ConsistentHash(std::list<ConNode*> nodes);
    	~ConsistentHash();
    
    	/**设定虚拟化倍数
    	 * */
    	inline void setVirtualSize(size_t size)
    	{
    		if(0 < size && size < sizeof(size_t))
    		{
    			_VirSize = size;
    		}
    	}
    
    	/*
    	 * 设定哈希算法
    	 */
    
    	inline void setHash(CalcHashValFunc func)
    	{
    		_Calc = func;
    	}
    
    	/*
    	 * 建立散列环
    	 */
    	int createRing();
    
    	/*
    	 * 计算key值的亲附节点
    	 */
    	ConNode* calc(std::string Key);
    public:
    	//哈希算法
    	static uint32_t MurmurHash(std::string key);
    private:
    	size_t _VirSize;//虚拟化倍数
    	std::list<ConNode*> _Nodes;//哈希节点列表
    	std::map<size_t, ConNode*> _Ring;//散列环
    	CalcHashValFunc _Calc;//生成哈希值的自定义函数
    };
    
    
    #endif /* CONSISTENT_HASH_H_ */
    

    cpp文件:

    /*
     * consistent_hash.cpp
     *
     *  Created on: Mar 13, 2019
     *      Author: clh01s
     */
    
    #include "consistent_hash.h"
    
    #define getblock(p, i) (p[i])
    
    #define FORCE_INLINE __attribute__((always_inline)) inline
    static FORCE_INLINE uint32_t rotl32 ( uint32_t x, int8_t r )
    {
      return (x << r) | (x >> (32 - r));
    }
    
    #define	ROTL32(x,y)	rotl32(x,y)
    
    static FORCE_INLINE uint32_t fmix32 ( uint32_t h )
    {
      h ^= h >> 16;
      h *= 0x85ebca6b;
      h ^= h >> 13;
      h *= 0xc2b2ae35;
      h ^= h >> 16;
    
      return h;
    }
    
    ConsistentHash::ConsistentHash(std::list<ConNode*> nodes)
    {
    	_VirSize = 10;
    	_Nodes = nodes;
    }
    
    ConsistentHash::~ConsistentHash()
    {
    
    }
    
    int ConsistentHash::createRing()
    {
    	if(_Calc == nullptr)
    	{
    		return -1;
    	}
    
    	for(auto it =  _Nodes.begin(); it != _Nodes.end(); ++it)
    	{
    		for(size_t i = 0; i < _VirSize; ++i)
    		{
    			ConNode* node = *it;
    			std::string hashkey = node->getKeyCode(i);
    			int hashval = _Calc(hashkey);
    //			std::cout<<"hashval = "<<hashval<<std::endl;
    			_Ring.insert(std::pair<size_t, ConNode*>(hashval, node));
    		}
    	}
    
    	return 0;
    }
    
    void MurmurHash3_x86_32 ( const void * key, int len,
                              uint32_t seed, void * out )
    {
      const uint8_t * data = (const uint8_t*)key;
      //const int nblocks = len / 4;
      const int nblocks = len >> 2;
      int i;
    
      uint32_t h1 = seed;
    
      uint32_t c1 = 0xcc9e2d51;
      uint32_t c2 = 0x1b873593;
    
      //----------
      // body
    
      const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
    
      for(i = -nblocks; i; i++)
      {
        uint32_t k1 = getblock(blocks,i);
    
        k1 *= c1;
        k1 = ROTL32(k1,15);
        k1 *= c2;
    
        h1 ^= k1;
        h1 = ROTL32(h1,13);
        h1 = h1*5+0xe6546b64;
      }
    
      //----------
      // tail
    
      const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
    
      uint32_t k1 = 0;
    
      switch(len & 3)
      {
      case 3: k1 ^= tail[2] << 16;
      case 2: k1 ^= tail[1] << 8;
      case 1: k1 ^= tail[0];
              k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
      };
    
      //----------
      // finalization
    
      h1 ^= len;
    
      h1 = fmix32(h1);
    
      *(uint32_t*)out = h1;
    }
    
    
    ConNode* ConsistentHash::calc(std::string hashkey)
    {
        if (_Ring.size() == 0)
        {
            return nullptr;
        }
    
        //计算出key的hash值
        size_t hashVal = _Calc(hashkey);
    //    std::cout<<"calc hashVal = "<<hashVal<<std::endl;
        //返回最接近该hash值的节点
        auto it = _Ring.lower_bound(hashVal);
        //如果最接近的节点为end(也就是说没有)则返回begin节点,如果不是则返回最接近的节点
        ConNode* node = (it == _Ring.end()) ? _Ring.begin()->second : it->second;
        return node;
    }
    
    
    
    uint32_t ConsistentHash::MurmurHash(std::string key)
    {
        uint32_t hash[4];                /* Output for the hash */
        uint32_t seed = 42;              /* Seed value for hash */
        MurmurHash3_x86_32(key.c_str(), key.length(), seed, hash);
        return hash[0];
    }
    
    
    int main()
    {
    	std::list<ConNode*> nodeList;
    	//创建5个真实节点
    	for(int i = 0; i < 5; ++i)
    	{
    		nodeList.push_back(new ConNode(i));
    	}
    	ConsistentHash Chash(nodeList);
    	Chash.setHash(ConsistentHash::MurmurHash);//设定使用的哈希算法
    	//创建哈希环
    	Chash.createRing();
    	//获取节点
    	auto node1 = Chash.calc("a");
    	std::cout<<"node1 获取到的节点是:"<<node1->getNodeValue()<<std::endl;
    	auto node2 = Chash.calc("aa1");
    	std::cout<<"node2 获取到的节点是:"<<node2->getNodeValue()<<std::endl;
    	auto node3 = Chash.calc("ca2");
    	std::cout<<"node3 获取到的节点是:"<<node3->getNodeValue()<<std::endl;
    	auto node4 = Chash.calc("ba3");
    	std::cout<<"node4 获取到的节点是:"<<node4->getNodeValue()<<std::endl;
    	auto node5 = Chash.calc("aa4");
    	std::cout<<"node5 获取到的节点是:"<<node5->getNodeValue()<<std::endl;
    	return 0;
    }
    

    执行结果:

    现在我们来讨论一致性哈希在池中只有少节点情况下的问题:

    可以看到我们在代码中设置了五个节点,而我们执行了3轮(每轮分配5次)一共分配15次,被使用的节点只有0、1、2、3号4个节点。而4号节点一次都没有分配出去,如果是在需要服务器负载调整的情况下,那么4号节点的服务器将处于完全空闲的状态(因为一次都没有被分配到任务)。

    但是我们相信只要执行的次数够多,总的负载最终都会均衡。

    由此我们可以得出结论一致性哈希在大批量的负载请求的情况下效果很好,但是在短期,少量的负载请求的情况下,会出现单位时间内某个节点完全空闲的情况出现。

    结论:

    如果你的执行情况是上述情况,可以考虑另外的负载分配方案。

    注:在本次代码中使用的哈希生成算法为murmur3哈希算法。

    ps:在这篇文章中完全没有说明一致性哈希的原理以及实现细节。需要读者自行查看代码。

    ps2:如果有时间的话,我可能会写一篇关于一致性哈希原理以及实现细节的文章。

    展开全文
  • 集群: 是一个提供多个Redis(分布式)节点间共享数据的程序集。 集群部署 Redis 集群的键空间被分割为 ...Redis Cluster在设计中没有使用一致性哈希(Consistency Hashing),而是使用数据分片引入哈希槽(hash
    集群:
    
    是一个提供多个Redis(分布式)节点间共享数据的程序集。
    集群部署
    Redis 集群的键空间被分割为 16384 hash个槽(slot), 集群的最大节点数量也是 16384 个

    关系:cluster>node>slot>key

    分片:
    Redis Cluster在设计中没有使用一致性哈希(Consistency Hashing),而是使用数据分片引入哈希槽(hash slot)来实现;

    一个 Redis Cluster包含16384(0~16383)个哈希槽,存储在Redis Cluster中的所有键都会被映射到这些slot中,

    集群中的每个键都属于这16384个哈希槽中的一个,集群使用公式slot=CRC16(key)/16384来计算key属于哪个槽,其中CRC16(key)语句用于计算key的CRC16 校验和。

    按照槽来进行分片,通过为每个节点指派不同数量的槽,可以控制不同节点负责的数据量和请求数.


    当前集群有3个节点,槽默认是平均分的:
    节点 A (6381)包含 0 到 5499号哈希槽.
    节点 B (6382)包含5500 到 10999 号哈希槽.
    节点 C (6383)包含11000 到 16383号哈希槽.
    这种结构很容易添加或者删除节点. 比如如果我想新添加个节点D, 我需要从节点 A, B, C中得部分槽到D上. 如果我像移除节点A,需要将A中得槽移到B和C节点上,然后将没有任何槽的A节点从集群中移除即可. 由于从一个节点将哈希槽移动到另一个节点并不会停止服务,所以无论添加删除或者改变某个节点的哈希槽的数量都不会造成集群不可用的状态.

    数据迁移
    数据迁移可以理解为slot(槽)和key的迁移,这个功能很重要,极大地方便了集群做线性扩展,以及实现平滑的扩容或缩容。

    现在要将Master A节点中编号为1、2、3的slot迁移到Master B节点中,在slot迁移的中间状态下,slot 1、2、3在Master A节点的状态表现为MIGRATING(迁移),在Master B节点的状态表现为IMPORTING(入口)。



    此时并不刷新node的映射关系

    IMPORTING状态

    被迁移slot 在目标Master B节点中出现的一种状态,准备迁移slot从Mater A到Master B的时候,被迁移slot的状态首先变为IMPORTING状态。

    键空间迁移


    键空间迁移是指当满足了slot迁移前提的情况下,通过相关命令将slot 1、2、3中的键空间从Master A节点转移到Master B节点。此时刷新node的映射关系。



    复制&高可用:
    集群的节点内置了复制和高可用特性。


    特点:1、节点自动发现
    2、slave->master 选举,集群容错
    3、Hot resharding:在线分片
    4、基于配置(nodes-port.conf)的集群管理
    5、客户端与redis节点直连、不需要中间proxy层.
    6、所有的redis节点彼此互联(PING-PONG机制),内部使用二进制协议优化传输速度和带宽.




    展开全文
  • 10分钟带你了解一致性hash算法

    千次阅读 多人点赞 2019-03-30 18:33:10
    文章目录环境描述场景描述以下是运算原理图:一致性hash算法概念一致性hash算法的优点hash环偏斜问题虚拟节点 环境描述 在了解hash算法之前先去了解一下缓存中的一个应用场景,再来理解一致性hash算法就会简单很...

    环境描述

    在了解hash算法之前先去了解一下缓存中的一个应用场景,再来理解一致性hash算法就会简单很多。

    场景描述

    假设,公司有三台缓存服务器,用于缓存图片,这三台缓存服务器的编号为0号,1号,2号,现在有三万张图片需要缓存,希望这么多的缓存数据能均匀的缓存到3台服务请求上去(也就是说每台机器上平均分配1万左右的数据),以便能够分摊缓存的压力

    • 此处的问题:

    那么应该怎么做?如果我们没有任何规律的将3万张图片平均的缓存到3台服务器上,可不可以满足需求?

    • 答案:

    可以!但是如果这么做,当我们需要访问某个和缓存选项时,则需要遍历3台服务器,从这3万个缓存项中找到需要访问的缓存,整个遍历下来的过程时间长,效率低,这样也就失去了缓存存在的价值和意义,缓存存在的目的就是提高速度,改善用户的体验,减轻后端服务器的压力,如果每次都要遍历整个缓存集群服务器,不用想都能累死.

    • 好一点的做法:

    原始的做法是对缓存项的键进行hash,将hash后的结果对缓存服务器数量进行取模操作,通过取模后结果,决定缓存项要缓存在那一台服务器上,举例说明:假设以我们使用的图片名称作为访问图片的key,假设图片名称不能重复,那么我们可以使用以下公式,及计算出图片应该存放在那台服务器上。

    • 公式:hash(图片名称)% N

    因为图片名称是不能重复的,所以,当我们对同一个图片名称做相同的hash运算时得出的结果应该是不变的,如果有3台服务器,使用hash运算后的结果对3取余,那么余数也一定是0、1、2,正号跟之前服务器编号相同,如果求余的结果为1,就把图片名称对应的图片缓存在1号服务器上,2就和缓存到2号服务器上,那么当我们访问任意一个图片的时候,只要再次对图片名称进行运算即可得出对应的图片应该被放在那台缓存服务器上,只需要去对应的服务器上去查找即可,如果图片在对应的服务器上不存在,证明没有被缓存(接着会把这张图片缓存在这个服务器上),也不用再去遍历其他缓存服务器了。通过此方法可以把3万图片随机分布到3台缓存服务器上,下次访问某张图片时,直接能够判断出该图片应该存放在那台缓存服务器上了。可以把上述算法称为:HASH算法还活着是取模算法

    以下是运算原理图:

    Alt text

    但是使用上述hash算法进行缓存时会出现一些缺陷,如果3台并不能满足我们的需求时那么应该怎么做?肯定是增加几台服务器就可以了,假设我们增加1台服务器,服务器的数量由3变成了4,此时仍然用上述方法对同一张图片进行缓存,那么这张图片所在的服务器的编号必定是与原来的3台服务器所在的 编号是不同的,因为除数3变成了4,被除数不变的情况下,余数肯定不同,这情况带来的结果就是当服务器数量变动时,所有和缓存的位置都要发生改变,也就是说缓存服务器数量发生改变时,所有缓存数据在一定时间是失效的,当应用无法从缓存中和获取数据时,则会向后端服务器请求数据,同理,如果3台缓存服务器中突然有一台出现了故障,,无法进行缓存数据,那么需要移除故障机器,但是如果移除了一台缓存服务器后,数量从3变成了2,如果想访问有一张图片,这张图片缓存为位置必定发生改变,以前缓存的图片也会失去缓存的作用和意义,由于==**`大量缓存在同一时间失效,造成了缓存的雪崩(血崩),此时前端缓存已经无法起到成端部分压力的作用,后端服务器将会承担所有巨大压力,会导致整个系统可能会被压垮,==所以为了避免这类情况的发生,一致性hash算法诞生了!

    • 综合一下上述出现的问题:

    第一个问题:
    当缓存服务器数量发生变化时,会引起缓存的血崩,可能引起整体系统压力过大而崩溃(大量缓存同一时间失效),
    第二个问题:
    当缓存服务器数量发生变化时,几乎所有缓存的数据都会发生改变,怎么才能尽量减少受影响的缓存?

    一致性hash算法概念

    其实一致性hash算法也是取模运算,只是,上面描述的取模算法是对服务器数量进行取模,而一致性hash是对2^32取模

    • 插入小知识:
      为什么非得对2^32取余?

    对232取余是有依据的IPV4最大数量就是232,所以这样就能保证所有的ip的地址进行取余时不会重复—对应hash环上面的正数。

    1. 首先把2^32想象成有一个大大的圆,就像钟表上由60个点组成的圆,如图:
      Alt text由2^32个点组成的圆环称为hash环。

    圆环的正上方代表0,0点右侧第一个1以此类推2,3,4,5,6……一直到最后2^32-1。
    假设我们有3台缓存服务器,服务器A,B,C,然后用他们各自的IP地址进行hash计算,使用hash后的结果改过对2^32取模。hash(服务器A的IP地址) % 2^32
    通过上面的计算结果一定是一个0到232-1之间的一个整数,我们就用这个整数代表服务器A,既然这个整数肯定处于0到232-1之间,那么必定与hash环的上一个点与这个整数对应。刚才已经说明,使用这个整数代表服务器A,那么服务器A就可以映射到这个环上。

    Alt text

    1. 同理服务器B和C也是相同的方法映射到hash环中
      计算公式:

    hash(服务器B的IP地址) % 2^32
    hash(服务器C的IP地址) % 2^32

    算出结果然后将服务器映射到hash环上去。如图所示:
    Alt text假设3台服务器均匀到映射到hash环上,(这是理想得到情况)

    1. 假设,我们需要使用缓存服务器缓存图片

    而且仍然使用图片的名称作为找到图片的Key,那么我们使用以下公式可以将图片映射到上图中的hash环上。
    hash(图片名称) % 2^32

    映射后得到的结果如下图:(红点点代表图片)
    Alt text
    那么问题来了,图片和服务器都被映射到了hash环上,那么上图的图片到底应该缓存到那一台缓存服务器上呢?
    答:

    应该被缓存到A服务器上,为什么?
    因为从图片开始的位置开始,沿着顺时针方向遇到的第一个服务器就是A服务器,所以会被缓存到A服务器上。如下图:

    Alt text

    1. 一致性hash算法说明:

    通过一致性hash算法这种方法,判断一个对象应该被缓存到那台服务器上的,将缓存服务器与被缓存对象都映射到hash环上以后,从被缓存对象的位置出发,沿着顺时针方向遇到的第一个服务器,就是当前对象将要缓存的服务器,由于被缓存对象与服务器hash后的值都是固定的,所以服务器不变的情况下,一张图片必定会被缓存到固定的服务器上,那么,当下次访问这张图片时,只要再次使用相同的算法进行计算,即可算出这张图片被缓存在那个服务器上,直接去对应的服务器上查找即可。

    假设有4张图片需要缓存,如下图:
    Alt text1、2图片缓存到A上,3缓存到B上,4缓存到C

    一致性hash算法的优点

    一致性hash算法能够解决之前出现的问题吗?如果进行简单的取模,当服务器数量发生变化时,会产生缓存的雪崩,从而导致系统崩溃,那么用一致性hash能够避免这个问题吗?

    1. 继续模拟测试实验!!
      假设服务器B出现故障,需要移除B,如下图:
      Alt text
      在服务器B没有移除时,图片3应该缓存到B中,可是移除后,按照一致性hash算法是规则,3应该被缓存到C中,因为从3的位置顺时针除法遇到的第一个服务器节点是C,也就是说如果B出现故障移除后,3的缓存位置发生改变。
      Alt text
      这里的一致性hash算法的优点就体现出来了!
      图片4依然会被缓存到C中,图片1和2突然缓存到A中,与移除B之前没有任何区别,这就是优点!

    1)如果使用hash算法:当服务器数量发生改变时,所有的服务器缓存在同一时间失效了
    2)而使用一致性hash算法:服务器数量发生改变时,并不是所有都会失效,而只有部分缓存失效,前端的缓存仍然能分担整个系统的压力,而不至于所有压力都在同一个时间集中到后端服务器上。

    hash环偏斜问题

    在最开始介绍概念年的时候,说的是在理想的情况下是**均匀的分布到hash环上!**如下图
    Alt text
    但是理想是很丰满的,我们想象的和现实往往是不同的!
    Alt text
    在实际映射中,服务器可能会被映射成一下模样
    Alt text
    那么被缓存的对象很有可能大部分集中缓存到某一台服务器上如下图:
    Alt text

    图上2、3、4、5、6、都很会存储到A服务器上,1会存到B上,C服务器一张也没有,三台服务器并没有合理的平均充分的利用,缓存分布极度不均匀,重要的是如果A出现故障,会导致失效的数量也将达到最大值。在极端的情况下依然会出现系统崩溃的问题!

    以上情况被称之为hash环偏斜,那么如何防止hash环偏斜呢?

    虚拟节点

    “虚拟节点”是“实际节点”(实际的物理服务器)在hash环上的复制品,一个实际节点可以对应多个虚拟节点。如下图:
    Alt text
    ABC三台服务分别虚拟出一个虚拟节点(也可以虚拟出更多的虚拟节点)引入虚拟节点的概念后,缓存的分布就均衡的多了,上图中3、4、5、的图片都被放到了节点A中如果不放心可以虚拟出更多的虚拟节点,以便减少hash环偏斜所带来的影响,虚拟节点越多,hash环上的节点就越多,缓存均匀分布的概率就越大!!!

    展开全文
  • 一致性hash和普通hash区别?

    千次阅读 2020-07-29 15:31:22
    普通hash 定义 Hash函数:一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。 碰撞(冲突):如果两个关键字通过hash函数得到...

    普通hash

    定义

    Hash函数:一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。
    碰撞(冲突):如果两个关键字通过hash函数得到的值是一样的,就是碰撞或冲突。
    Hash表(散列表):根据散列函数和冲突处理将一组关键字分配在连续的地址空间内,并以散列值记录在表中的存储位置,这种表成为散列表。

    常用算法

    直接寻址法:即取关键字或关键字的线性函数为散列地址:H(key)=key或H(key)=a*key+b;
    数字分析法:即分析一组数据后采用的方法:如人的出生年月为92-09-03则前三位重复的几率比较大,容易产生碰撞,所以应该采用后三位作为hash值好点
    平方取中法:取关键字平方的后几位。
    折叠法:把关键字分割成位数相同的几部分,最后一部分可以位数不同,然后取这几部分的叠加值
    随机数法:以关键值作为生成随机数的种子生成散列地址,通常适用于关键字长度不同的场合。
    除留余数法:取关键字被某个不大于散列表长度m的数p除后所得的余数为散列地址:H(key)=key%p(p<=m);不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生碰撞。

    什么是一致性Hash算法

    1. 为什么要使用Hash算法
    举个例子,我们在使用Redis的时候,为了保证Redis的高可用,提高Redis的读写性能,最简单的方式我们会做主从复制,,或者搭建Redis集群,进行数据的读写分离,当数据量很大的时候(标准可能不一样,要看Redis服务器容量)我们同样可以对Redis进行类似数据库的操作,就是分库分表。如图所示
    在这里插入图片描述
    假若采用随机分配的方式,那么我们保存到一条数据都有可能存储在任何一组Redis中,如果我们需要查询某一条数据,由于我们不清楚数据保存在哪一个redis服务器中,因此需要遍历了所有的Redis服务器,这显然不是我们想要的结果。
    如果我们使用Hash的方式,每一张图片在进行分库的时候都可以定位到特定的服务器,示意图如下:
    在这里插入图片描述
    上图中,假设我们查找的是”a.png”,由于有4台服务器(排除从库),因此公式为hash(a.png) % 4 = 2 ,可知定位到了第2号服务器,这样的话就不会遍历所有的服务器,大大提升了性能!

    2. 使用Hash带来的问题
    上述的方式虽然提升了性能,我们不再需要对整个Redis服务器进行遍历!但是,使用上述Hash算法进行缓存时,会出现一些缺陷,主要体现在服务器数量变动的时候,所有缓存的位置都要发生改变!

    试想一下,如果4台缓存服务器已经不能满足我们的缓存需求,那么我们应该怎么做呢?很简单,多增加几台缓存服务器不就行了!假设:我们增加了一台缓存服务器,那么缓存服务器的数量就由4台变成了5台。那么原本hash(a.png) % 4 = 2 的公式就变成了hash(a.png) % 5 = ? , 可想而知这个结果肯定不是2的,这种情况带来的结果就是当服务器数量变动时,所有缓存的位置都要发生改变!换句话说,当服务器数量发生改变时,所有缓存在一定时间内是失效的,当应用无法从缓存中获取数据时,则会向后端数据库请求数据!

    同样的,假设4台缓存中突然有一台缓存服务器出现了故障,无法进行缓存,那么我们则需要将故障机器移除,但是如果移除了一台缓存服务器,那么缓存服务器数量从4台变为3台,也是会出现上述的问题!

    所以,我们应该想办法不让这种情况发生,但是由于上述Hash算法本身的缘故,使用取模法进行缓存时,这种情况是无法避免的,为了解决这些问题,Hash一致性算法(一致性Hash算法)诞生了!

    3. 一致性hash算法原理
    一致性Hash算法也是使用取模的方法,只是,刚才描述的取模法是对服务器的数量进行取模,而一致性Hash算法是对2^32取模,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,将各个服务器使用Hash进行一个哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中四台服务器使用IP地址哈希后在环空间的位置如下:
    在这里插入图片描述

    每次根据要缓存的key计算得到hash值,在hash环上顺时针查找距离最近的缓存服务器节点,
    在这里插入图片描述
    根据一致性Hash算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

    一致性Hash算法的容错性和可扩展性
    现假设Node C不幸宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性Hash算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响,如下所示:
    在这里插入图片描述
    下面考虑另外一种情况,如果在系统中增加一台服务器Node X,如下图所示:

    在这里插入图片描述
    此时对象Object A、B、D不受影响,只有对象C需要重定位到新的Node X !一般的,在一致性Hash算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

    综上所述,一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

    4. Hash环的数据倾斜问题
    一致性Hash算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题,例如系统中只有两台服务器,其环分布如下:
    在这里插入图片描述
    此时必然造成大量数据集中到Node A上,而只有极少量会定位到Node B上。为了解决这种数据倾斜问题,一致性Hash算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。
    例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:
    在这里插入图片描述
    同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

    总结

    在分布式系统中一致性hash起着不可忽略的地位,无论是分布式缓存,还是分布式Rpc框架的负载均衡策略都有所使用。分布式系统每个节点都有可能失效,并且新的节点很可能动态的增加进来的情况,如何保证当系统的节点数目发生变化的时候,我们的系统仍然能够对外提供良好的服务,这是值得考虑的!

    一致性哈希算法能尽可能减少了服务器数量变化所导致的缓存迁移。

    consistent(一致性) hash算法能够在一定程度上改善缓存的雪崩问题,它能够在移除/添加一台缓 存服务器时,尽可能小的改变已存在的key映射关系,避免大量key的重新映射。

    先构造一个长度为2 32次方的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 23 2次方-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 2 32次方-1]),接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点,完成Key到服务器的映射查找。

    这种算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

    展开全文
  • 一致性哈希算法解决了分布式下数据分布问题。比如在缓存系统中,通过一致性哈希算法把缓存键映射到不同的节点上,由于算法中虚拟节点的存在,哈希结果一般情况下比较均匀。而且增减节点时,只需要重新映射部分键值,...
  • 分布式一致性hash算法

    千次阅读 2018-01-01 11:44:40
    写在前面  在学习Redis的集群内容时,看到这么一句话:Redis并没有使用一致性hash算法,而是引入哈希槽的概念。而分布式缓存Memcached则是使用分布式一致性hash算法来实现分布式存储。所以就专门学习了一下什么是...
  • 一致性hash算法原理及golang实现

    千次阅读 2016-08-15 23:56:17
     一致性hash如上文所言,其新增一个节点的实效率仅为N/(N+1),通过一致性hash最大程度的降低了实效率。同时相比于槽映射的方式,不需要引人槽来做中间对应,最大限度的简化了实现。 4. 基于golang的...
  • 一致性 hash 分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢? 强哈希 考虑到单...
  • 有时候想想,分布式领域真的很多东西都差不多,大家都会碰到,所以今天这个一致性hash是用在什么场景呢? 解决什么问题 场景一:如果一个数据库表已经分库分表,有4张表,那么现在如何实现扩容,扩容到8张表? 场景...
  • hash和一致性hash

    千次阅读 2019-07-25 09:19:45
    hash;简单的hash取余 优点: 计算简单,快速定位 缺点: 容错和扩展差,任何的增加机器或减少...一致性hash:hash环 想象一个环,共有2^(32-1) 个节点,如果有五台机器缓存,那么就将这五台的ip分别hash后对2^(32...
  • 从redis源码看一致性hash算法

    千次阅读 2018-03-05 15:32:19
    官方在Redis 3也正式推出了集群技术,不同于传统的散列映射的集群方案,jedis(redis的java客户端)支持Redis Sharding功能,结合缓存池ShardJedisPoo和一致性hash算法实现了高效hash。下面就结合redis的使用详细...
  • session一致性架构设计实践 原创:58沈剑架构师之路2017-05-18 一、缘起 什么是session? 服务器为每个用户创建一个会话,存储用户的相关信息,以便多次请求能够定位到同一个上下文。 Web开发中,web-...
  • 分布式一致性hash算法简介 当你看到“分布式一致性hash算法”这个词时,第一时间可能会问,什么是分布式,什么是一致性,hash又是什么。在分析分布式一致性hash算法原理之前,我们先来了解一下这几个概念。 分布式...
  • 负载均衡中的一致性Hash算法详解

    千次阅读 2020-06-08 19:54:58
    优点: 生成足够简单,本地生成无网络消耗,具有唯一 缺点: 无序的字符串,不具备趋势自增特性 没有具体的业务含义 长度过长16 字节128位,36位长度的字符串,存储以及查询对MySQL的性能消耗较大,MySQL官方明确...
  • 实现方式:一致性hash分片,利用一个分片节点对应一个或者多个虚拟hash桶的思想,,尽可能减少分片扩展时的数据迁移。 优点:有效解决了分布式数据库的扩容问题。 缺点:在横向扩展的时候,需要迁移部分数据;...
  • 文章目录一、一致性hash算法二、问题的引入?2.1 解决方案1 HashSet2.2 解决方案2 TreeSet 里面2.3 使用集合存储字符串数据的优缺点三、引入位集合3.1 图示3.2 特点四、Hash4.1 hash4.2 hash 和hashCode4.3 怎么解决...
  • MemCache超详细解读(一致性hash

    千次阅读 2016-10-25 18:19:31
    这个问题有解决方案,解决步骤为: (1)在网站访问量低谷,通常是深夜,技术团队加班,扩容、重启服务器 (2)通过模拟请求的方式逐渐预热缓存,使缓存服务器中的数据重新分布 2、一致性Hash算法 一致性Hash算法...
  • redis集群方案-一致性hash算法

    万次阅读 2016-08-18 20:05:27
    节点之间怎么据的同步,如何做到数据一致性。一主一备的模式,可以用 Redis 内部实现的主从备份实现数据同步。但节点不断增多,存在多个 master 的时候,同步的难度会越大。如何做到负载均衡?请求量大的时候,如何...
  • 在redis底层有一套算法叫做Hash一致性算法, 在里面有这样几个特性。  1.均衡性:  尽可能的让信息数据均匀的落入不同的节点中,如果根据hash计算,获取的数据量不是均匀分片的则采用虚拟节点重新进行划分,...
  • MyCat生产实践--一致性hash分片&扩容

    千次阅读 2017-04-26 09:37:58
    MyCat生产实践–一致性hash分片&扩容1、 mycat一致性hash算法分片测试结果配置el_user_user_info表使用一致性hash算法进行分片。 schema.xml <!DOCTYPE mycat:schema SYSTEM "schema.dtd"> ...
  • 一致性hash算法的应用研究学习

    千次阅读 2017-07-19 10:37:04
    一致性哈希算法 在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网...一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance):平衡性
  • nginx的hash和一致性hash的区别

    千次阅读 2017-06-12 20:46:07
    hash  nginx的负载均衡时有一个hash $request_uri的选项,这个是类似于LVS的dh。是针对客户端访问的uri来做的绑定。这样客户端访问同一个uri的时候,会被分配到同一个服务器... 缺点:如果一个节点挂了,那么整个
  • 负载均衡与一致性哈希

    千次阅读 2019-07-28 16:24:41
    假设有三台缓存服务器s0,s1,s2,同时有三万张图片需要缓存,最好图片可以均匀的缓存到服务器上,这样可以分担缓存的压力,对缓存下的键进行hash计算,哈希后的值是个整数,再用缓存服务器的数量对这个值进行取模计算...
  • 三年前在《一致性hash基础知识》文章中,曾提到 google 有一个算法简单的计算就做到了一致性哈希需要做到的事情。 上个月在《一致性HASH技术的困境》文章的留言中,也有小伙伴提到,有一个 Jump consistent hash ...
  • 一致性Hash算法的实现

    千次阅读 2017-04-15 17:20:00
    一致性hash作为一个负载均衡算法,可以用在分布式缓存、数据库的分库分表等场景中,还可以应用在负载均衡器中作为作为负载均衡算法。在有多台服务器时,对于某个请求资源通过hash算法,映射到某一个台服务器,当增加...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,375
精华内容 26,550
关键字:

一致性hash缺点