prosody
1266efb7101c
util/hashring.lua

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

Software / code / prosody

Annotate

util/hashring.lua @ 13191:1266efb7101c

editorconfig: Add link to format description
author Kim Alvefur <zash@zash.se>
date Sat, 15 Jul 2023 10:22:37 +0200
parent 12975:d10957394a3c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 }