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 总结
﻿
﻿