一致性哈希算法的简单实现和在redis集群的应用

项目中需要搭建一个简单的redis集群，用来存储系统中的特征值，利用到一致性哈希算法，简介可以看一致性哈希算法，本文简单实现了一致性哈希的算法，主要阐述一下应用场景和一些感想。

#ifndef _CONSISTENTHASH_H
#define _CONSISTENTHASH_H

#include<vector>
#include<map>
#include<utility>
#include<string>

using namespace std;

class ConsistentHash
{

public:
    ConsistentHash();
	~ConsistentHash();
    ConsistentHash(int cachedNodeNum, int virtualNodeNum);
    int getCachedNodeId(uint64_t key);
    int getCachedNodeId(string key);
private:
    void getVirtualNodeForString(int cachedNodeNum, int virtualNodeNum, string &virtualNodeString);
private:
    vector<uint64_t> vHashValues;
    map<uint64_t, pair<int int=""> > mVirtualNodeMap;
    int cachedNodeNum;
    int virtualNodeNum;
};
#endif

#include"ConsistentHash.h"
#include"city.h"
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
ConsistentHash::ConsistentHash()
{
}

ConsistentHash::~ConsistentHash()
{
}

/*
 * cachedNodeNum:cache节点的数量
 * virtualNodeNum:虚拟节点的个数
 * 根据cache节点数量和虚拟节点个数生成环
 */
ConsistentHash::ConsistentHash(int cachedNodeNum, int virtualNodeNum)
{
    this->cachedNodeNum = cachedNodeNum;
    this->virtualNodeNum = virtualNodeNum;
    for(int i = 0; i < cachedNodeNum; ++i)
    {
        for(int j = 0; j < virtualNodeNum; ++j)
        {
			string hashStr = "";
            uint64 hashInt = 0;
			//可以根据节点信息计算hash值
            getVirtualNodeForString(i, j, hashStr);
			//利用Google的CityHash算法计算hash值
            hashInt = CityHash64(hashStr.c_str(), hashStr.size());
            vHashValues.push_back(hashInt);
            mVirtualNodeMap[hashInt] = make_pair(i, j);
        }
    }
    sort(vHashValues.begin(), vHashValues.end());
}

/*
 * key:要存储的字符串
 * 获取该字符串要存储的cache节点id
 */
int
ConsistentHash::getCachedNodeId(string key)
{
    vector<uint64_t>::iterator low;
    uint64_t hashInt = CityHash64(key.c_str(), key.size());
    low = lower_bound(vHashValues.begin(), vHashValues.end(), hashInt);
    uint64_t nextHash;
    if(low == vHashValues.end())
    {
        nextHash = vHashValues[0];
	}
    else
    {
        nextHash = vHashValues[low - vHashValues.begin()];
    }
    return mVirtualNodeMap[nextHash].first;
}

int
ConsistentHash::getCachedNodeId(uint64_t key)
{
    vector<uint64_t>::iterator low;
    uint64_t hashInt = key;
    low = lower_bound(vHashValues.begin(), vHashValues.end(), hashInt);
    uint64_t nextHash;
    if(low == vHashValues.end())
    {
        nextHash = vHashValues[0];
	}
    else
    {
        nextHash = vHashValues[low - vHashValues.begin()];
    }
    return mVirtualNodeMap[nextHash].first;
}

void
ConsistentHash::getVirtualNodeForString(int cachedNodeNum, int virtualNodeNum, string &virtualNodeString)
{
    virtualNodeString = ("node:" + cachedNodeNum);
    virtualNodeString += ":vnode:";
    virtualNodeString = virtualNodeString + ("" + virtualNodeNum);
}

以上代码比较简单的实现了一致性哈希的算法。算法对来自客户端的请求进行分发，实现数据的存储和读取。redis也提供了相关的备份机制，但是是以牺牲了一部分的性能为代价的，结合我们的应用场景，并没有采用相关的备份机制，即使redis挂了，将模型重新计算和相关的特征值存入就可以了，因为特征值丢失的代价是我们可以承受的，而且模型更新的间隔比较短，所以就没有采用相关的备份机制，后续我们加入了双写的功能，即一份数据存储到不同的两个节点上，只需要在原有代码基础上稍加改动就行了，这样即使一个redis挂了，可以到另一个节点读取数据。