RendezvousHashTest.cpp File Reference

#include <folly/Conv.h>
#include <folly/container/Foreach.h>
#include <folly/portability/GTest.h>
#include <map>
#include <vector>
#include <proxygen/lib/utils/RendezvousHash.h>

Go to the source code of this file.

Functions
	TEST (RendezvousHash, Consistency)
	TEST (RendezvousHash, ConsistencyWithNewNode)
	TEST (RendezvousHash, ConsistencyWithIncreasedWeight)
	TEST (RendezvousHash, ConsistentFlowToIncreasedWeightNode)
	TEST (RendezvousHash, ConsistentFlowToDecreasedWeightNodes)
	TEST (RendezvousHash, ConsistentFlowToDecreasedWeightNode)
	TEST (RendezvousHash, ConsistencyWithDecreasedWeight)
	TEST (ConsistentHashRing, DistributionAccuracy)
	TEST (RendezvousHash, selectNUnweighted)

Function Documentation

TEST	(	RendezvousHash	,
		Consistency
	)

Definition at line 20 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_EQ, FOR_EACH_KV, proxygen::RendezvousHash::get(), and i.

                                  {
  RendezvousHash hashes;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < 10; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), 1);
  }
  hashes.build(nodes);

  for (size_t rank = 0; rank < nodes.size() + 2; rank++) {
    std::map<uint64_t, size_t> mapping;
    for (int i = 0; i < 10000; ++i) {
      mapping[i] = hashes.get(i, rank);
    }

    FOR_EACH_KV(key, expected, mapping) {
      EXPECT_EQ(expected, hashes.get(key, rank));
    }
  }
}

TEST	(	RendezvousHash	,
		ConsistencyWithNewNode
	)

Definition at line 40 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_TRUE, FOR_EACH_KV, proxygen::RendezvousHash::get(), i, and uint64_t.

                                             {
  RendezvousHash hashes;
  int numNodes = 10;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), 1);
  }
  hashes.build(nodes);
  std::map<uint64_t, size_t> mapping;
  for (uint64_t i = 0; i < 10000; ++i) {
    mapping[i] = hashes.get(i);
  }
  hashes = RendezvousHash();
  // Adding a new node and rebuild the hash
  nodes.emplace_back(folly::to<std::string>("key", numNodes), 1);
  hashes.build(nodes);
  // traffic should only flow to the new node
  FOR_EACH_KV (key, expected, mapping) {
    size_t id = hashes.get(key);
    EXPECT_TRUE(expected == id || numNodes == int(id));
  }
}

TEST	(	RendezvousHash	,
		ConsistencyWithIncreasedWeight
	)

Definition at line 63 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_EQ, FOR_EACH_KV, proxygen::RendezvousHash::get(), i, and uint64_t.

                                                     {
  RendezvousHash hashes;
  int numNodes = 10;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i);
  }
  hashes.build(nodes);

  std::map<uint64_t, size_t> mapping;
  for (uint64_t i = 0; i < 10000; ++i) {
    mapping[i] = hashes.get(i);
  }

  // Increase the weight by 2
  nodes.clear();
  hashes = RendezvousHash();
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i*2);
  }
  hashes.build(nodes);

  // traffic shouldn't flow at all
  FOR_EACH_KV (key, expected, mapping) {
    EXPECT_EQ(expected, hashes.get(key));
  }
}

TEST	(	RendezvousHash	,
		ConsistentFlowToIncreasedWeightNode
	)

Definition at line 91 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_TRUE, FOR_EACH_KV, proxygen::RendezvousHash::get(), i, and uint64_t.

                                                          {
  RendezvousHash hashes;
  int numNodes = 10;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i);
  }
  hashes.build(nodes);

  std::map<uint64_t, size_t> mapping;
  for (uint64_t i = 0; i < 10000; ++i) {
    mapping[i] = hashes.get(i);
  }

  nodes.clear();
  // Increase the weight for a single node
  hashes = RendezvousHash();

  nodes.emplace_back(folly::to<std::string>("key", 0), 10);

  for (int i = 1; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i);
  }
  hashes.build(nodes);
  // traffic should only flow to the first node
  FOR_EACH_KV (key, expected, mapping) {
    size_t id = hashes.get(key);
    EXPECT_TRUE(expected == id || 0 == int(id));
  }
}

TEST	(	RendezvousHash	,
		ConsistentFlowToDecreasedWeightNodes
	)

Definition at line 122 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_TRUE, FOR_EACH_KV, proxygen::RendezvousHash::get(), i, and uint64_t.

                                                           {
  RendezvousHash hashes;
  int numNodes = 18;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), 100);
  }
  hashes.build(nodes);
  std::map<uint64_t, size_t> mapping;
  for (uint64_t i = 0; i < 10000; ++i) {
    mapping[i] = hashes.get(i);
  }

  nodes.clear();
  hashes = RendezvousHash();

  // decrease the weights for 5 nodes
  for (int i = 0; i < 5; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), 50);
  }

  // keep the weights for the rest unchanged
  for (int i = 5; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), 100);
  }

  hashes.build(nodes);
  FOR_EACH_KV (key, expected, mapping) {
    // traffic should only flow to nodes with decreased nodes
    size_t id = hashes.get(key);
    EXPECT_TRUE(expected == id || id >= 5);
  }
}

TEST	(	RendezvousHash	,
		ConsistentFlowToDecreasedWeightNode
	)

Definition at line 156 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_TRUE, FOR_EACH_KV, proxygen::RendezvousHash::get(), i, and uint64_t.

                                                          {
  RendezvousHash hashes;
  int numNodes = 10;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i);
  }
  hashes.build(nodes);
  std::map<uint64_t, size_t> mapping;
  for (uint64_t i = 0; i < 10000; ++i) {
    mapping[i] = hashes.get(i);
  }

  // Increase the weight for a single node
  nodes.clear();
  hashes = RendezvousHash();

  for (int i = 0; i < numNodes - 1; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i);
  }

  // zero the weight of the last node
  nodes.emplace_back(folly::to<std::string>("key", numNodes-1), 0);
  hashes.build(nodes);
  FOR_EACH_KV (key, expected, mapping) {
    // traffic should only flow from the zero weight cluster to others
    size_t id = hashes.get(key);
    if (expected == (uint64_t)numNodes-1) {
       EXPECT_TRUE(expected != id);
    } else {
       EXPECT_TRUE(expected == id);
    }
  }
}

TEST	(	RendezvousHash	,
		ConsistencyWithDecreasedWeight
	)

Definition at line 191 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_EQ, FOR_EACH_KV, proxygen::RendezvousHash::get(), i, and uint64_t.

                                                     {
  RendezvousHash hashes;
  int numNodes = 10;
  std::vector<std::pair<std::string, uint64_t> > nodes;
  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i*2);
  }
  hashes.build(nodes);
  std::map<uint64_t, size_t> mapping;
  for (uint64_t i = 0; i < 10000; ++i) {
    mapping[i] = hashes.get(i);
  }

  // Decrease the weight by 2
  nodes.clear();
  hashes = RendezvousHash();

  for (int i = 0; i < numNodes; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), i);
  }
  hashes.build(nodes);

  // traffic shouldn't flow at all
  FOR_EACH_KV (key, expected, mapping) {
    EXPECT_EQ(expected, hashes.get(key));
  }
}

TEST	(	ConsistentHashRing	,
		DistributionAccuracy
	)

Definition at line 219 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_LE, FOR_EACH_RANGE, proxygen::RendezvousHash::get(), i, max, and uint64_t.

                                               {
  std::vector<std::string> keys =
    {"ash_proxy", "prn_proxy", "snc_proxy", "frc_proxy"};

  std::vector<std::vector<uint64_t>> weights = {
    {248, 342, 2, 384},
    {10, 10, 10, 10},
    {25, 25, 10, 10},
    {100, 10, 10, 1},
    {100, 5, 5, 5},
    {922337203685, 12395828300, 50192385101, 59293845010}
  };

  for (auto& weight: weights) {
    RendezvousHash hashes;
    std::vector<std::pair<std::string, uint64_t> > nodes;
    FOR_EACH_RANGE (i, 0, keys.size()) {
      nodes.emplace_back(keys[i], weight[i]);
    }
    hashes.build(nodes);

    std::vector<uint64_t> distribution(keys.size());

    for (uint64_t i = 0; i < 21000; ++i) {
      distribution[hashes.get(i)]++;
    }

    uint64_t totalWeight = 0;

    for (auto& w: weight) {
      totalWeight += w;
    }

    double maxError = 0.0;
    for (size_t i = 0; i < keys.size(); ++i) {
      double expected = 100.0 * weight[i] / totalWeight;
      double actual = 100.0 * distribution[i] / 21000;

      maxError = std::max(maxError, fabs(expected - actual));
    }
    // make sure the error rate is less than 1.0%
    EXPECT_LE(maxError, 1.0);
  }
}

TEST	(	RendezvousHash	,
		selectNUnweighted
	)

Definition at line 264 of file RendezvousHashTest.cpp.

References proxygen::RendezvousHash::build(), EXPECT_EQ, EXPECT_GT, EXPECT_LT, i, seed, proxygen::RendezvousHash::selectNUnweighted(), and folly::size().

                                        {
  RendezvousHash hashes;
  std::vector<std::pair<std::string, uint64_t>> nodes;
  int size = 100;
  for (int i = 0; i < size; ++i) {
    nodes.emplace_back(folly::to<std::string>("key", i), 1);
  }
  hashes.build(nodes);
  auto seed = 91484253;

  // rank > size
  auto select = hashes.selectNUnweighted(seed, size + 10);
  EXPECT_EQ(select.size(), size);
  for (int i = 0; i < size; i++) {
    EXPECT_EQ(select[i], i);
  }

  // check valid index in selection
  int rank = size / 4;
  select = hashes.selectNUnweighted(seed, rank);
  EXPECT_EQ(select.size(), rank);
  std::set<size_t> uniqueIndex;
  for (auto index : select) {
    EXPECT_EQ(uniqueIndex.count(index), 0);
    uniqueIndex.insert(index);
    EXPECT_LT(index, size);
  }

  // change seed, check different selection
  for (int i = 1; i < 100; i++) {
    select = hashes.selectNUnweighted(seed + i, rank);
    int different = 0;
    for (auto index : select) {
      if (uniqueIndex.count(index) == 0) {
        different++;
      }
    }
    EXPECT_GT(different, 0);
  }
}