您的位置: 首页  >  文章  >  一致性哈希的使用与优缺点分析

一致性哈希的使用与优缺点分析

分类: 文章 • 2023-11-06 21:14:10

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

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

比如：在服务器节电池的服务器节点的选择，线程池中线程的选择，路由等等。

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

一致性哈希在负载均衡方面效果很好，因为它的设计目标是为了解决因特网中的热点（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：如果有时间的话，我可能会写一篇关于一致性哈希原理以及实现细节的文章。

相关推荐