架构师训练营 Week 05 作业

发布于: 2020 年 07 月 06 日

1 一致性散列的实现

namespace ConsistenHashing
{
typedef uint32_t HashCode_t;
template <typename T, typename K>
struct hash
{
virtual T operator()(const K &key) = 0;
};
struct stdhash
: public hash<HashCode_t, std::string>
{
HashCode_t operator()(const std::string &key)
{
std::size_t hash = std::hash<std::string>{}(key);
return static_cast<HashCode_t>(hash & 0xffff'ffff);
}
};
class HashRing
{
public:
void addNode(const std::string &nodeKey, int virtualNodeNumber)
{
for (int i = 0; i < virtualNodeNumber; i++)
{
nodeMap.emplace(std::experimental::randint(0x0000'0000u, 0xffff'ffffu), nodeKey);
}
}
void removeNode(const std::string &nodeKey)
{
auto finder = [&](decltype(nodeMap)::const_reference pair) { return nodeKey == pair.second; };
auto it = nodeMap.begin();
while ((it = std::find_if(it, nodeMap.end(), finder)) != nodeMap.end())
{
nodeMap.erase(it++);
}
}
std::string getNode(const std::string &key)
{
return getNode(key, stdhash());
}
template <typename T>
std::string getNode(const std::string &key, T hash)
{
if (nodeMap.empty())
return "";
// Maybe we could use a binary search to improve efficiency.
auto biggerThan = [&](decltype(nodeMap)::const_reference pair) { return std::get<0>(pair) > hash(key); };
auto firstBiggerThan = std::find_if(nodeMap.begin(), nodeMap.end(), biggerThan);
if (nodeMap.end() != firstBiggerThan)
{
return firstBiggerThan->second;
}
else
{
return nodeMap.begin()->second;
}
}
private:
std::map<HashCode_t, std::string> nodeMap;
};
} // namespace ConsistenHashing

2 测试用例

100万KV数据,10个服务器节点的情况下,KV数据在服务器的分布标准差。所模拟的KV数据,使用随机数作为键值。

using namespace std;
using namespace ConsistenHashing;
int main(int argc, char **argv)
{
// Host IPs
vector<string> nodeList{
"192.168.100.101",
"192.168.100.102",
"192.168.100.103",
"192.168.100.104",
"192.168.100.105",
"192.168.100.106",
"192.168.100.107",
"192.168.100.108",
"192.168.100.109",
"192.168.100.110"};
// Create a hash ring
HashRing hashRing;
for (auto &node : nodeList)
{
hashRing.addNode(node, 200);
}
//
map<string, int> counting;
for (auto &node : nodeList)
{
counting.emplace(node, 0);
}
// Hitting test
for (int i = 0; i < 1000'000; i++)
{
string dataKey = to_string(random());
string nodeKey = hashRing.getNode(dataKey);
auto hittedItem = counting.find(nodeKey);
hittedItem->second++;
}
// Calculate standard deviation
double sum = 0;
for_each(counting.begin(), counting.end(), [&](decltype(counting)::const_reference item) { sum += item.second; });
double mean = sum / counting.size();
double variance = 0.;
for_each(counting.begin(), counting.end(), [&](decltype(counting)::const_reference item) { variance += pow(item.second - mean, 2.); });
variance = variance / counting.size();
double standardDeviation = sqrt(variance);
// Output results
for (auto &item : counting)
{
cout << item.first << ", hits: " << item.second << endl;
}
cout << "Standard deviation: " << standardDeviation << endl;
return 0;
}

3 运行结果

重复运行5次

192.168.100.101, hits: 101018
192.168.100.102, hits: 99021
192.168.100.103, hits: 100774
192.168.100.104, hits: 108384
192.168.100.105, hits: 97576
192.168.100.106, hits: 100946
192.168.100.107, hits: 100591
192.168.100.108, hits: 106041
192.168.100.109, hits: 93585
192.168.100.110, hits: 92064
Standard deviation: 4697.14

192.168.100.101, hits: 109828
192.168.100.102, hits: 96799
192.168.100.103, hits: 97387
192.168.100.104, hits: 94861
192.168.100.105, hits: 95711
192.168.100.106, hits: 109251
192.168.100.107, hits: 109405
192.168.100.108, hits: 88827
192.168.100.109, hits: 103269
192.168.100.110, hits: 94662
Standard deviation: 7046.42

192.168.100.101, hits: 95055
192.168.100.102, hits: 99710
192.168.100.103, hits: 95899
192.168.100.104, hits: 102031
192.168.100.105, hits: 101242
192.168.100.106, hits: 100267
192.168.100.107, hits: 96923
192.168.100.108, hits: 96643
192.168.100.109, hits: 99462
192.168.100.110, hits: 112768
Standard deviation: 4807.73

192.168.100.101, hits: 101022
192.168.100.102, hits: 100371
192.168.100.103, hits: 102724
192.168.100.104, hits: 101764
192.168.100.105, hits: 102202
192.168.100.106, hits: 92734
192.168.100.107, hits: 100429
192.168.100.108, hits: 92704
192.168.100.109, hits: 109290
192.168.100.110, hits: 96760
Standard deviation: 4685.88

192.168.100.101, hits: 104872
192.168.100.102, hits: 99339
192.168.100.103, hits: 101201
192.168.100.104, hits: 106546
192.168.100.105, hits: 111950
192.168.100.106, hits: 98133
192.168.100.107, hits: 91796
192.168.100.108, hits: 96460
192.168.100.109, hits: 83000
192.168.100.110, hits: 106703
Standard deviation: 7927.93

用户头像

Wancho

关注

还未添加个人签名 2020.02.28 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 Week 05 作业