fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <ctime>	// to initialize random number generator
  5. //#include <cstdlib>
  6. #include <unordered_map>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. typedef struct {
  11. 	string name;
  12. 	int weight;
  13. 	int key;	// server key. Used in hashing
  14. } server;
  15.  
  16. vector<float> testConsistentHashingVirtualServer(vector<server> &serverList, int replica) {
  17. 	vector<server> replicaList;
  18. 	int totalWeight = 0;
  19. 	for (int i = 0; i < serverList.size(); i++) {
  20. 		totalWeight += serverList[i].weight;
  21. 		for (int rep = 0; rep < replica*serverList[i].weight; rep++) {
  22. 			server* tmp = new server();
  23. 			tmp->key = rand() % RAND_MAX;
  24. 			tmp->name = serverList[i].name;
  25. 			tmp->weight = 1;
  26. 			replicaList.push_back(*tmp);
  27. 		}
  28. 	}
  29. 	sort(replicaList.begin(), replicaList.end(), [](server a, server b){return a.key < b.key; });
  30. 	unordered_map<string, float> um;
  31. 	for (int i = 0; i < replicaList.size(); i++) {
  32. 		if (i == 0) um[replicaList[0].name] = replicaList[0].key+1;
  33. 		else {
  34. 			um[replicaList[i].name] += replicaList[i].key - replicaList[i - 1].key;
  35. 		}
  36. 	}
  37. 	um[replicaList[0].name] += RAND_MAX - 1 - replicaList.back().key;
  38. 	vector<float> ret;
  39. 	for (int i = 0; i < serverList.size(); i++) {
  40. 		ret.push_back(((float)um[serverList[i].name]) / RAND_MAX * totalWeight);
  41. 	}
  42. 	return ret;
  43. }
  44.  
  45. int main() {
  46. 	srand(time(0));
  47. 	// We simulate 7 servers. Each with different weight (INT value)
  48. 	server s[] = { { "a", 1, 0 }, { "b", 3, 0 }, { "c", 2, 0 }, \
  49. 	               { "d", 4, 0 }, { "e", 6, 0 }, { "f", 8, 0 }, \
  50. 	               { "g", 1, 0 } };
  51. 	vector<server> vs;
  52. 	for (int i = 0; i < sizeof(s) / sizeof(s[0]); i++) vs.push_back(s[i]);
  53. 	// and each server is mapped to 400 replica. In total we simulate 2800 virtual servers.
  54. 	auto ret = testConsistentHashingVirtualServer(vs, 400);
  55. 	for (int i = 0; i < sizeof(s) / sizeof(s[0]); i++) {
  56. 		cout << "Server " << s[i].name << " has weight " << s[i].weight \
  57. 			 << " and is now occuping " << ret[i] << " of all hashing space." << endl;
  58. 	}
  59.  
  60. 	return EXIT_SUCCESS;
  61. }
Success #stdin #stdout 0.01s 3692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Server a has weight 1 and is now occuping 1.00941 of all hashing space.
Server b has weight 3 and is now occuping 2.92019 of all hashing space.
Server c has weight 2 and is now occuping 2.02607 of all hashing space.
Server d has weight 4 and is now occuping 3.95463 of all hashing space.
Server e has weight 6 and is now occuping 5.99777 of all hashing space.
Server f has weight 8 and is now occuping 8.11238 of all hashing space.
Server g has weight 1 and is now occuping 0.979571 of all hashing space.
https://ideone.com/zvjwwJ
Test the consistent hashing algorithm
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!