Week5

发布于: 2020 年 07 月 08 日

作业1 一致性hash

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

Node

#ifndef __CNODE__HPP
#define __CNODE__HPP
#include<string>
#include<cassert>
class CNode
{
public:
CNode()
{
m_data = nullptr;
m_nodeCount = 0;
}
CNode(char* pIden, int pVNodeCount, void* pData)
{
SetCNode(pIden, pVNodeCount, pData);
}
/*获取结点标示*/
const char* GetIden()
{
return m_iden;
}
/*获取实体结点的虚拟结点数量*/
int GetVNodeCount()
{
return m_nodeCount;
}
/*设置实体结点数据值*/
void SetData(void* data)
{
m_data = data;
}
/*获取实体结点数据值*/
void* GetData()
{
return m_data;
}
~CNode()
{
}
private:
void SetCNode(char* pIden, int pVNodeCount, void* pData)
{
assert(pIden != NULL && pVNodeCount > 0);
strcpy_s(m_iden, pIden);
m_nodeCount = pVNodeCount;
m_data = pData;
}
char m_iden[100];/*结点标示串*/
int m_nodeCount; /*虚拟结点数目*/
void* m_data;/*数据结点*/
};
#endif // !__CNODE__HPP

VirtualNode

#ifndef __VIRTUALNODE__HPP
#define __VIRTUALNODE__HPP
#include "CNode.hpp"
#include<iostream>
/*虚拟结点*/
class VirtualNode
{
public:
/*构造函数*/
VirtualNode()
{
m_node = NULL;
}
VirtualNode(CNode * pNode)
{
SetNode(pNode);
}
/*设置虚拟结点所指向的实体结点*/
void SetNode(CNode* pNode)
{
assert(pNode != NULL);
m_node = pNode;
}
/*获取虚拟结点所指向的实体结点*/
CNode* GetNode()
{
return m_node;
}
/*设置虚拟结点hash值*/
void SetHash(long pHash)
{
m_hash = pHash;
}
/*获取虚拟结点hash值*/
long GetHash()
{
return m_hash;
}
~VirtualNode()
{}
private:
long m_hash; /*hash值*/
CNode* m_node; /*虚拟结点所指向的实体结点*/
};
#endif // !__VIRTUALNODE__HPP

ConHash

#ifndef __ConHash__HPP
#define __ConHash__HPP
#include "IHashFun.h"
#include "CNode.hpp"
#include "CRBTree.h"
#include "VirtualNode.hpp"
#include <iostream>
#include <string>
#include <cassert>
/*辅助函数,虚拟结点转化为红黑树结点*/
util_rbtree_node_t* VNode2RBNode(VirtualNode* vnode)
{
if (vnode == NULL) return NULL;
util_rbtree_node_t* rbNode = new util_rbtree_node_t();
rbNode->key = vnode->GetHash();
rbNode->data = vnode;
return rbNode;
}
class ConHash
{
public:
ConHash(IHashFun* pFunc)
{
/*设置hash函数*/
SetFunc(pFunc);
m_nodeCount = 0;
/*初始化红黑树*/
m_vnodeTree = new util_rbtree_s();
util_rbtree_init(m_vnodeTree);
}
/*设置hash函数*/
void SetFunc(IHashFun* pFunc)
{
assert(pFunc != nullptr);
m_func = pFunc;
}
/*增加实体结点 , 0代表成功 , -1代表失败*/
int AddNode(CNode* pNode)
{
if (pNode == NULL) return -1;
int vCount = pNode->GetVNodeCount();
if (vCount <= 0) return -1;
VirtualNode* virtualNode;
util_rbtree_node_t* rbNode;
char str[1000];
char num[10];
strcpy(str, pNode->GetIden());
long hash = 0;
/*生成虚拟结点并插入到红黑树中*/
for (int i = 0; i < vCount; i++)
{
virtualNode = new VirtualNode(pNode);
/*采用str+“i”的方法产生不同的iden串,用于后面的hash值计算*/
_itoa(i, num, 10);
strcat(str, num);
hash = m_func->GetHashVal(str);
virtualNode->SetHash(hash);
if (!util_rbtree_search(m_vnodeTree, hash))
{
/*生成红黑树结点*/
rbNode = VNode2RBNode(virtualNode);
if (rbNode != NULL)
{
/*将该结点插入到红黑树中*/
util_rbtree_insert(m_vnodeTree, rbNode);
this->m_nodeCount++;
}
}
}
return 0;
}
/*删除实体结点 , 0代表成功 , -1代表失败*/
int DeleteNode(CNode* pNode)
{
if (pNode == NULL) return -1;
util_rbtree_node_t* rbNode;
char str[1000];
char num[10];
strcpy(str, pNode->GetIden());
int vCount = pNode->GetVNodeCount();
long hash = 0;
VirtualNode* node = NULL;
/*将该实体结点产生的所有虚拟结点进行删除*/
for (int i = 0; i < vCount; i++)
{
_itoa(i, num, 10);
strcat(str, num);/*采用该方法产生不同的iden串*/
hash = m_func->GetHashVal(str);
rbNode = util_rbtree_search(m_vnodeTree, hash);
if (rbNode != NULL)
{
node = (VirtualNode*)rbNode->data;
if (node->GetNode() == pNode && node->GetHash() == hash)
{
this->m_nodeCount--;
/*将该结点从红黑树中删除*/
util_rbtree_delete(m_vnodeTree, rbNode);
delete rbNode;
delete node;
}
}
}
return 0;
}
/*查找实体结点*/
CNode* LookupNode(const char* object)
{
if (object == NULL || this->m_nodeCount == 0) return NULL;
util_rbtree_node_t* rbNode;
int key = this->m_func->GetHashVal(object);
/*在红黑树中查找key值比key大的最小的结点*/
rbNode = util_rbtree_lookup(m_vnodeTree, key);
if (rbNode != NULL)
{
return ((VirtualNode*)rbNode->data)->GetNode();
}
return NULL;
}
/*获取一致性hash结构的所有虚拟结点数量*/
int GetVNodes()
{
return m_nodeCount;
}
~ConHash()
{}
private:
/*虚拟结点总个数*/
int m_nodeCount;
/*Hash函数*/
IHashFun* m_func;
/*存储虚拟结点的红黑树*/
util_rbtree_t* m_vnodeTree;
};
#endif // !__ConHash__HPP

作业2 总结

用户头像

丿淡忘

关注

还未添加个人签名 2018.05.23 加入

还未添加个人简介

评论

发布
暂无评论
Week5