spec/util_hashring_spec.lua

   1 local hashring = require "util.hashring";
   2
   3 describe("util.hashring", function ()
   4
   5         local sha256 = require "util.hashes".sha256;
   6
   7         local ring = hashring.new(128, sha256);
   8
   9         it("should fail to get a node that does not exist", function ()
  10                 assert.is_nil(ring:get_node("foo"))
  11         end);
  12
  13         it("should support adding nodes", function ()
  14                 ring:add_node("node1");
  15         end);
  16
  17         it("should return a single node for all keys if only one node exists", function ()
  18                 for i = 1, 100 do
  19                         assert.is_equal("node1", ring:get_node(tostring(i)))
  20                 end
  21         end);
  22
  23         it("should support adding a second node", function ()
  24                 ring:add_node("node2");
  25         end);
  26
  27         it("should fail to remove a non-existent node", function ()
  28                 assert.is_falsy(ring:remove_node("node3"));
  29         end);
  30
  31         it("should succeed to remove a node", function ()
  32                 assert.is_truthy(ring:remove_node("node1"));
  33         end);
  34
  35         it("should return the only node for all keys", function ()
  36                 for i = 1, 100 do
  37                         assert.is_equal("node2", ring:get_node(tostring(i)))
  38                 end
  39         end);
  40
  41         it("should support adding multiple nodes", function ()
  42                 ring:add_nodes({ "node1", "node3", "node4", "node5" });
  43         end);
  44
  45         it("should disrupt a minimal number of keys on node removal", function ()
  46                 local orig_ring = ring:clone();
  47                 local node_tallies = {};
  48
  49                 local n = 1000;
  50
  51                 for i = 1, n do
  52                         local key = tostring(i);
  53                         local node = ring:get_node(key);
  54                         node_tallies[node] = (node_tallies[node] or 0) + 1;
  55                 end
  56
  57                 --[[
  58                 for node, key_count in pairs(node_tallies) do
  59                         print(node, key_count, ("%.2f%%"):format((key_count/n)*100));
  60                 end
  61                 ]]
  62
  63                 ring:remove_node("node5");
  64
  65                 local disrupted_keys = 0;
  66                 for i = 1, n do
  67                         local key = tostring(i);
  68                         if orig_ring:get_node(key) ~= ring:get_node(key) then
  69                                 disrupted_keys = disrupted_keys + 1;
  70                         end
  71                 end
  72                 assert.is_equal(node_tallies["node5"], disrupted_keys);
  73         end);
  74
  75         it("should support removing multiple nodes", function ()
  76                 ring:remove_nodes({"node2", "node3", "node4", "node5"});
  77         end);
  78
  79         it("should return a single node for all keys if only one node remains", function ()
  80                 for i = 1, 100 do
  81                         assert.is_equal("node1", ring:get_node(tostring(i)))
  82                 end
  83         end);
  84
  85 end);