架构师 0 期第五周命题作业

// ConsistentHash.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
// ConsistenHash.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <map>
#include <vector>
#include <utility>
#include <time.h>
#if defined(_MSC_VER)
#define FORCE_INLINE    __forceinline
#include <stdlib.h>
#define ROTL32(x,y)    _rotl(x,y)
#define ROTL64(x,y)    _rotl64(x,y)
#define BIG_CONSTANT(x) (x)
// Other compilers
#else    // defined(_MSC_VER)
#define    FORCE_INLINE inline __attribute__((always_inline))
inline uint32_t rotl32(uint32_t x, int8_t r)
{
	return (x << r) | (x >> (32 - r));
}
inline uint64_t rotl64(uint64_t x, int8_t r)
{
	return (x << r) | (x >> (64 - r));
}
#define    ROTL32(x,y)    rotl32(x,y)
#define ROTL64(x,y)    rotl64(x,y)
#define BIG_CONSTANT(x) (x##LLU)
#endif // !defined(_MSC_VER)
FORCE_INLINE uint32_t getblock32(const uint32_t * p, int i)
{
	return p[i];
}
FORCE_INLINE uint64_t getblock64(const uint64_t * p, int i)
{
	return p[i];
}
//-----------------------------------------------------------------------------
// Finalization mix - force all bits of a hash block to avalanche
FORCE_INLINE uint32_t fmix32(uint32_t h)
{
	h ^= h >> 16;
	h *= 0x85ebca6b;
	h ^= h >> 13;
	h *= 0xc2b2ae35;
	h ^= h >> 16;
	return h;
}
//----------
FORCE_INLINE uint64_t fmix64(uint64_t k)
{
	k ^= k >> 33;
	k *= BIG_CONSTANT(0xff51afd7ed558ccd);
	k ^= k >> 33;
	k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
	k ^= k >> 33;
	return k;
}
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;
	uint32_t h1 = seed;
	const uint32_t c1 = 0xcc9e2d51;
	const uint32_t c2 = 0x1b873593;
	//----------
	// body
	const uint32_t * blocks = (const uint32_t *)(data + nblocks * 4);
	for (int i = -nblocks; i; i++)
	{
		uint32_t k1 = getblock32(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;
}
class ServerNode {
public:
	ServerNode(std::string name) :name_(name), hit_(0) {}
	void Insert(std::string key, int value) {
		//printf("KV(%s, %d) insert into server(%s)\n", key.c_str(), value, name_.c_str());
		hit_++;
	}
	void PrintHit() {
		printf("Server(%s) was hit %d times\n", name_.c_str(), hit_);
	}
private:
	int hit_;
	std::string name_;
};
class MapNode {
public:
	MapNode(bool bServer, ServerNode* server = nullptr, int value = 0) :bServer_(bServer), server_(server), value_(value) {}
	bool bServer_;
	ServerNode* server_;
	int value_;
};
class ConsistentHash {
public:
	ConsistentHash() {
		InitServer();
	}
	void InsertKV(std::string key, int value) {
		int pos = GetRingPos(key);
		hashRing_.insert(std::make_pair(pos, MapNode(false, NULL, value)));
		std::map<int, MapNode>::iterator itr = hashRing_.find(pos);
		for (; itr != hashRing_.end(); itr++) {
			if ((*itr).second.bServer_) {
				if ((*itr).second.server_)
					(*itr).second.server_->Insert(key, value);
				break;
			}
		}
	}
	void PrintHit() {
		std::vector<ServerNode>::iterator itr = serverList_.begin();
		for (; itr != serverList_.end(); itr++) {
			(*itr).PrintHit();
		}
	}
	void PrintMap() {
		std::map<int, MapNode>::iterator itr = hashRing_.begin();
		for (; itr != hashRing_.end(); itr++) {
			printf("%d\n", (*itr).first);
		}
	}
private:
	void InitServer() {
		ServerNode srv0("srv0");
		ServerNode srv1("srv1");
		ServerNode srv2("srv2");
		ServerNode srv3("srv3");
		ServerNode srv4("srv4");
		ServerNode srv5("srv5");
		ServerNode srv6("srv6");
		ServerNode srv7("srv7");
		ServerNode srv8("srv8");
		ServerNode srv9("srv9");
		serverList_.push_back(std::move(srv0));
		serverList_.push_back(std::move(srv1));
		serverList_.push_back(std::move(srv2));
		serverList_.push_back(std::move(srv3));
		serverList_.push_back(std::move(srv4));
		serverList_.push_back(std::move(srv5));
		serverList_.push_back(std::move(srv6));
		serverList_.push_back(std::move(srv7));
		serverList_.push_back(std::move(srv8));
		serverList_.push_back(std::move(srv9));
		int interval = LONG_MAX / serverList_.size();
		for (int i = 1; i < serverList_.size(); i++) {
			hashRing_.insert(std::make_pair(interval*i, MapNode(true, &serverList_[i - 1])));
		}
		hashRing_.insert(std::make_pair(LONG_MAX, MapNode(true, &serverList_[serverList_.size() - 1])));
		std::map<int, MapNode>::iterator itr = hashRing_.begin();
		for (; itr != hashRing_.end(); itr++) {
			printf("%d\n", (*itr).first);
		}
	}
	//使用MurMurHash3算法
	int GetRingPos(std::string key) {
		int result = 0;
		MurmurHash3_x86_32(key.c_str(), key.length(), 1000000, (void*)&result);
		if (result < 0) result = -result;
		return result;
	}
	std::map<int, MapNode> hashRing_;
	std::vector<ServerNode> serverList_;
};
int main()
{
	ConsistentHash ch;
	//srand(time(0));
	char buffer[256];
	for (int i = 0; i < 1000000; i++)
	{
		sprintf_s(buffer, "HermanEllinXiaopangxiekey%d", i);
		ch.InsertKV(buffer, 123);
	}
	ch.PrintHit();
	//ch.PrintMap();
	system("pause");
}