prosody
87424cbedc55
util/hashring.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Comparison

util/hashring.lua @ 12795:87424cbedc55

util.hashring: Support associating arbitrary data with nodes In this API, a 'node' is always a simple text string. Sometimes the caller may have a more complex structure representing a node, but the hash ring is really only concerned with the node's name. This API change allows :add_nodes() to take a table of `node_name = value` pairs, as well as the simple array of node names previously accepted. The 'value' of the selected node is returned as a new second result from :get_node(). If no value is passed when a node is added, it defaults to `true` (as before, but this was never previously exposed).
author Matthew Wild <mwild1@gmail.com>
date Fri, 02 Dec 2022 20:32:36 +0000
parent 11208:96429946a742
child 12975:d10957394a3c
comparison
equal deleted inserted replaced
12794:249b01adc54a 12795:87424cbedc55
1 local it = require "util.iterators";
2
1 local function generate_ring(nodes, num_replicas, hash) 3 local function generate_ring(nodes, num_replicas, hash)
2 local new_ring = {}; 4 local new_ring = {};
3 for _, node_name in ipairs(nodes) do 5 for _, node_name in ipairs(nodes) do
4 for replica = 1, num_replicas do 6 for replica = 1, num_replicas do
5 local replica_hash = hash(node_name..":"..replica); 7 local replica_hash = hash(node_name..":"..replica);
26 28
27 local function new(num_replicas, hash_function) 29 local function new(num_replicas, hash_function)
28 return setmetatable({ nodes = {}, num_replicas = num_replicas, hash = hash_function }, hashring_mt); 30 return setmetatable({ nodes = {}, num_replicas = num_replicas, hash = hash_function }, hashring_mt);
29 end; 31 end;
30 32
31 function hashring_methods:add_node(name) 33 function hashring_methods:add_node(name, value)
32 self.ring = nil; 34 self.ring = nil;
33 self.nodes[name] = true; 35 self.nodes[name] = value == nil and true or value;
34 table.insert(self.nodes, name); 36 table.insert(self.nodes, name);
35 return true; 37 return true;
36 end 38 end
37 39
38 function hashring_methods:add_nodes(nodes) 40 function hashring_methods:add_nodes(nodes)
39 self.ring = nil; 41 self.ring = nil;
40 for _, node_name in ipairs(nodes) do 42 local iter = pairs;
41 if not self.nodes[node_name] then 43 if nodes[1] then -- simple array?
42 self.nodes[node_name] = true; 44 iter = it.values;
45 end
46 for node_name, node_value in iter(nodes) do
47 if self.nodes[node_name] == nil then
48 self.nodes[node_name] = node_value == nil and true or node_value;
43 table.insert(self.nodes, node_name); 49 table.insert(self.nodes, node_name);
44 end 50 end
45 end 51 end
46 return true; 52 return true;
47 end 53 end
48 54
49 function hashring_methods:remove_node(node_name) 55 function hashring_methods:remove_node(node_name)
50 self.ring = nil; 56 self.ring = nil;
51 if self.nodes[node_name] then 57 if self.nodes[node_name] ~= nil then
52 for i, stored_node_name in ipairs(self.nodes) do 58 for i, stored_node_name in ipairs(self.nodes) do
53 if node_name == stored_node_name then 59 if node_name == stored_node_name then
54 self.nodes[node_name] = nil; 60 self.nodes[node_name] = nil;
55 table.remove(self.nodes, i); 61 table.remove(self.nodes, i);
56 return true; 62 return true;
67 end 73 end
68 end 74 end
69 75
70 function hashring_methods:clone() 76 function hashring_methods:clone()
71 local clone_hashring = new(self.num_replicas, self.hash); 77 local clone_hashring = new(self.num_replicas, self.hash);
72 clone_hashring:add_nodes(self.nodes); 78 for node_name, node_value in pairs(self.nodes) do
79 clone_hashring.nodes[node_name] = node_value;
80 end
81 clone_hashring.ring = nil;
73 return clone_hashring; 82 return clone_hashring;
74 end 83 end
75 84
76 function hashring_methods:get_node(key) 85 function hashring_methods:get_node(key)
86 local node;
77 local key_hash = self.hash(key); 87 local key_hash = self.hash(key);
78 for _, replica_hash in ipairs(self.ring) do 88 for _, replica_hash in ipairs(self.ring) do
79 if key_hash < replica_hash then 89 if key_hash < replica_hash then
80 return self.ring[replica_hash]; 90 node = self.ring[replica_hash];
91 break;
81 end 92 end
82 end 93 end
83 return self.ring[self.ring[1]]; 94 if not node then
95 node = self.ring[self.ring[1]];
96 end
97 return node, self.nodes[node];
84 end 98 end
85 99
86 return { 100 return {
87 new = new; 101 new = new;
88 } 102 }