Software /
code /
prosody
Annotate
util/hashring.lua @ 13182:c48ae06e24d6
util.datamanager: Fix indexing first item if not at the very start
If the first item does not start at position 0 then the index function
produces a phantom first entry covering position zero until where the
real first item starts. When using the index, this would make it either
appear as the first item was missing or cause an off-by-one issue with
remaining items.
author | Kim Alvefur <zash@zash.se> |
---|---|
date | Mon, 10 Jul 2023 17:19:05 +0200 |
parent | 12975:d10957394a3c |
rev | line source |
---|---|
12975
d10957394a3c
util: Prefix module imports with prosody namespace
Kim Alvefur <zash@zash.se>
parents:
12795
diff
changeset
|
1 local it = require "prosody.util.iterators"; |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
2 |
10005
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 = {}; |
11208
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
5 for _, node_name in ipairs(nodes) do |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
6 for replica = 1, num_replicas do |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
7 local replica_hash = hash(node_name..":"..replica); |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
8 new_ring[replica_hash] = node_name; |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
9 table.insert(new_ring, replica_hash); |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
10 end |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
11 end |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10005
diff
changeset
|
12 table.sort(new_ring); |
10005
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 |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
33 function hashring_methods:add_node(name, value) |
10005
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
34 self.ring = nil; |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
35 self.nodes[name] = value == nil and true or value; |
10005
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; |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
42 local iter = pairs; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
43 if nodes[1] then -- simple array? |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
44 iter = it.values; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
45 end |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
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:
11208
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:
11208
diff
changeset
|
48 self.nodes[node_name] = node_value == nil and true or node_value; |
10005
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; |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
57 if self.nodes[node_name] ~= nil then |
10005
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); |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
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:
11208
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:
11208
diff
changeset
|
80 end |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
81 clone_hashring.ring = nil; |
10005
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) |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
86 local node; |
10005
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 |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
90 node = self.ring[replica_hash]; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
91 break; |
10005
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 |
12795
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
94 if not node then |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
95 node = self.ring[self.ring[1]]; |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
96 end |
87424cbedc55
util.hashring: Support associating arbitrary data with nodes
Matthew Wild <mwild1@gmail.com>
parents:
11208
diff
changeset
|
97 return node, self.nodes[node]; |
10005
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 } |