author | aidan@jmad.org |
Wed, 03 Apr 2024 21:56:03 -0700 | |
changeset 13477 | 9eb081616842 |
parent 12979 | d10957394a3c |
permissions | -rw-r--r-- |
12979
d10957394a3c
util: Prefix module imports with prosody namespace
Kim Alvefur <zash@zash.se>
parents:
12799
diff
changeset
|
1 |
local it = require "prosody.util.iterators"; |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
2 |
|
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
3 |
local function generate_ring(nodes, num_replicas, hash) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
4 |
local new_ring = {}; |
11212
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
5 |
for _, node_name in ipairs(nodes) do |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
6 |
for replica = 1, num_replicas do |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
7 |
local replica_hash = hash(node_name..":"..replica); |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
8 |
new_ring[replica_hash] = node_name; |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
9 |
table.insert(new_ring, replica_hash); |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
10 |
end |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
11 |
end |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
12 |
table.sort(new_ring); |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
13 |
return new_ring; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
14 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
15 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
16 |
local hashring_methods = {}; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
17 |
local hashring_mt = { |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
18 |
__index = function (self, k) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
19 |
-- Automatically build self.ring if it's missing |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
20 |
if k == "ring" then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
21 |
local ring = generate_ring(self.nodes, self.num_replicas, self.hash); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
22 |
rawset(self, "ring", ring); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
23 |
return ring; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
24 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
25 |
return rawget(hashring_methods, k); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
26 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
27 |
}; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
28 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
29 |
local function new(num_replicas, hash_function) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
30 |
return setmetatable({ nodes = {}, num_replicas = num_replicas, hash = hash_function }, hashring_mt); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
31 |
end; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
32 |
|
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
33 |
function hashring_methods:add_node(name, value) |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
34 |
self.ring = nil; |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
35 |
self.nodes[name] = value == nil and true or value; |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
36 |
table.insert(self.nodes, name); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
37 |
return true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
38 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
39 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
40 |
function hashring_methods:add_nodes(nodes) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
41 |
self.ring = nil; |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
42 |
local iter = pairs; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
43 |
if nodes[1] then -- simple array? |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
44 |
iter = it.values; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
45 |
end |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
46 |
for node_name, node_value in iter(nodes) do |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
47 |
if self.nodes[node_name] == nil then |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
48 |
self.nodes[node_name] = node_value == nil and true or node_value; |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
49 |
table.insert(self.nodes, node_name); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
50 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
51 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
52 |
return true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
53 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
54 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
55 |
function hashring_methods:remove_node(node_name) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
56 |
self.ring = nil; |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
57 |
if self.nodes[node_name] ~= nil then |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
58 |
for i, stored_node_name in ipairs(self.nodes) do |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
59 |
if node_name == stored_node_name then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
60 |
self.nodes[node_name] = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
61 |
table.remove(self.nodes, i); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
62 |
return true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
63 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
64 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
65 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
66 |
return false; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
67 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
68 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
69 |
function hashring_methods:remove_nodes(nodes) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
70 |
self.ring = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
71 |
for _, node_name in ipairs(nodes) do |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
72 |
self:remove_node(node_name); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
73 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
74 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
75 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
76 |
function hashring_methods:clone() |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
77 |
local clone_hashring = new(self.num_replicas, self.hash); |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
78 |
for node_name, node_value in pairs(self.nodes) do |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
79 |
clone_hashring.nodes[node_name] = node_value; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
80 |
end |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
81 |
clone_hashring.ring = nil; |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
82 |
return clone_hashring; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
83 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
84 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
85 |
function hashring_methods:get_node(key) |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
86 |
local node; |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
87 |
local key_hash = self.hash(key); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
88 |
for _, replica_hash in ipairs(self.ring) do |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
89 |
if key_hash < replica_hash then |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
90 |
node = self.ring[replica_hash]; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
91 |
break; |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
92 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
93 |
end |
12799
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
94 |
if not node then |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
95 |
node = self.ring[self.ring[1]]; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
96 |
end |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11212
diff
changeset
|
97 |
return node, self.nodes[node]; |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
98 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
99 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
100 |
return { |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
101 |
new = new; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
102 |
} |