命题作业 5-1 【C++ 实现版本】

发布于: 5 小时前

1.实现一致性Hash算法

要解决的问题:

一个分布式的存储系统中,通过一致性Hash算法将数据存储到具体的节点上,给出一个数据,将其存储到某个节点上,返回存储节点的ID。

问题分析:

对于分布式存储系统而言,其一致性Hash算法仅工作在路由节点,所做的工作仅仅是将数据请求路由到合适的数据节点中,该算法的输入应该是一个数据的key,输出应该是该数据所在的数据节点的ID。

对于一个数据节点而言,在路由节点中实际上以多个虚拟节点的形式存在,对于每一个虚拟节点,需要保存该虚拟节点对应实际节点的ID、该节点的虚拟ID和该节点Hash之后的值(对应一致性Hash环上的值,该值由实际节点ID+虚拟节点ID一同Hash后获得)。

一致性Hash算法对于每个数据key,计算其Hash后的值,然后从虚拟节点的有序队列中找到第一个比该值大的虚拟节点,该虚拟节点对应的物理节点就是数据所在的数据节点。

下面代码中省略了关于MD5的实现代码,网上随便搜一下就能找到MD5的实现。

//----cat hash.h-------
#include <string>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
using string=std::string;
struct DataNode{
int nodeID;
int nodeVirtualID;
string nodeHashValue;
DataNode(int id,int vid, const string& hash):nodeID(id),nodeVirtualID(vid),nodeHashValue(hash)
{}
};
struct DataNodeCompare{
bool operator()(const DataNode& lhs, const DataNode& rhs) const
{
return lhs.nodeHashValue<rhs.nodeHashValue;
}
};
class CacheManager{
std::map<int,int> virtualID;
std::set<DataNode, DataNodeCompare> ring;
CacheManager(){}
public:
static CacheManager& GetInstance()
{
static CacheManager manager;
return manager;
}
void addNode(int nodeID);
void Init(int nodeNum,int virtualnodeNum);
int getDataID(const string& dataKey);
void showRing()
{
for(auto x:ring)
std::cout<<"nodeid is "<<x.nodeID<<" nodevid is"<<x.nodeVirtualID<<" hash value is"<<x.nodeHashValue<<std::endl;
}
};
class Statistics
{
std::map<int,int> map;
int avg;
Statistics(){}
public:
void SetAvg(int a)
{
avg = a;
}
static Statistics& GetInstance()
{
static Statistics imp;
return imp;
}
void HitNode(int nodeID)
{
if(map.find(nodeID)!=map.end())
map[nodeID]++;
else
map[nodeID]=1;
}
double CalcResult();
void Clear()
{
map.clear();
}
void ShowResult()
{
for(auto x:map)
std::cout<<"nodeid "<<x.first<<" node time"<<x.second<<std::endl;
}
};
class Log
{
std::ofstream file;
Log()
{
file.open("log.csv",std::ios::out|std::ios::trunc);
file<<"虚拟节点个数,标准差"<<std::endl;
}
~Log()
{
file.close();
}
public:
static Log& GetInstance()
{
static Log imp;
return imp;
}
void GetLog(int vnum, double sqrt)
{
file<<vnum<<","<<sqrt<<std::endl;
}
};
//----cat hash.cpp-------
#include "hash.h"
#include "md5.h"
#include <math.h>
#include <sstream>
using stringstream=std::stringstream;
void CacheManager::addNode(int nodeID)
{
int vid = 0;
if(virtualID.find(nodeID)!=virtualID.end())
{
vid = virtualID[nodeID]++;
}
else
{
virtualID[nodeID] = 1;
}
stringstream str;
str<<nodeID<<"-"<<vid;
DataNode node(nodeID, vid, MD5(str.str()).toString());
ring.insert(node);
}
void CacheManager::Init(int nodeNum, int virtualnodeNum)
{
virtualID.clear();
ring.clear();
for(size_t i=0;i<nodeNum;i++)
for(size_t j=0;j<virtualnodeNum;j++)
addNode(i);
}
int CacheManager::getDataID(const string& dataKey)
{
//获取哈希值
string hash=MD5(dataKey).toString();
//寻找虚拟节点
auto itr=ring.upper_bound(DataNode(0,0,hash));
//得到物理节点ID
if(itr!=ring.end())
return itr->nodeID;
return 0;
}
void TestCache(const string& tmp)
{
int id = CacheManager::GetInstance().getDataID(tmp);
//std::cout<<"data is"<<tmp<<" id is"<< id << std::endl;
Statistics::GetInstance().HitNode(id);
}
void ShowRing()
{
CacheManager::GetInstance().showRing();
}
double Statistics::CalcResult()
{
//标准差定义是总体各单位标准值与其平均数离差平方的算术平均数的平方根。它反映组内个体间的离散程度。
//s=sqrt(((x1-x)^2 +(x2-x)^2 +......(xn-x)^2)/(n-1))
double sum=0;
for(auto x:map)
sum+=((x.second-avg)*(x.second-avg)/map.size());
return sqrt(sum);
}
int main()
{
for(int m=100;m<201;m++)
{
CacheManager::GetInstance().Init(10,m);
for(int i=0;i<1000000;i++)
{
stringstream str;
str<<i;
TestCache(str.str());
// ShowRing();
}
Statistics::GetInstance().SetAvg(100000);
Log::GetInstance().GetLog(m,Statistics::GetInstance().CalcResult());
Statistics::GetInstance().Clear();
}
}

2.测试100万kv数据,10个服务器节点的情况下,kv数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

这里测试了虚拟节点100-200之间的标准差,列举部分结果如下:

| 虚拟节点个数 | 标准差 |

| ------------ | ------- |

| 152 | 2920.12 |

| 131 | 3125.51 |

| 127 | 3182.4 |

| 122 | 3183.34 |

| 132 | 3265.98 |

| 153 | 3329.46 |

| 125 | 3341.5 |

| 156 | 3405.56 |

| 188 | 3411.85 |

| 155 | 3442.51 |

| 184 | 3461.02 |

| 198 | 3465.2 |

| 194 | 3468.12 |

| 154 | 3476.89 |

| 121 | 3485.38 |

| 126 | 3502.73 |

| 151 | 3509.79 |

| 150 | 3515.16 |

| 191 | 3541.62 |

发布于: 5 小时前 阅读数: 8
用户头像

天之彼方

关注

还未添加个人签名 2020.05.30 加入

还未添加个人简介

评论

发布
暂无评论
命题作业5-1 【C++实现版本】