author | Kim Alvefur <zash@zash.se> |
Fri, 27 May 2022 14:45:35 +0200 | |
branch | 0.12 |
changeset 12530 | 252ed01896dd |
parent 11212 | 96429946a742 |
child 12799 | 87424cbedc55 |
permissions | -rw-r--r-- |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
1 |
local function generate_ring(nodes, num_replicas, hash) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
2 |
local new_ring = {}; |
11212
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
3 |
for _, node_name in ipairs(nodes) do |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
4 |
for replica = 1, num_replicas do |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
5 |
local replica_hash = hash(node_name..":"..replica); |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
6 |
new_ring[replica_hash] = node_name; |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
7 |
table.insert(new_ring, replica_hash); |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
8 |
end |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
9 |
end |
96429946a742
util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents:
10009
diff
changeset
|
10 |
table.sort(new_ring); |
10009
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
11 |
return new_ring; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
12 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
13 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
14 |
local hashring_methods = {}; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
15 |
local hashring_mt = { |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
16 |
__index = function (self, k) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
17 |
-- Automatically build self.ring if it's missing |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
18 |
if k == "ring" then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
19 |
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
|
20 |
rawset(self, "ring", ring); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
21 |
return ring; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
22 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
23 |
return rawget(hashring_methods, k); |
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 |
}; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
26 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
27 |
local function new(num_replicas, hash_function) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
28 |
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
|
29 |
end; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
30 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
31 |
function hashring_methods:add_node(name) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
32 |
self.ring = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
33 |
self.nodes[name] = true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
34 |
table.insert(self.nodes, name); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
35 |
return true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
36 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
37 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
38 |
function hashring_methods:add_nodes(nodes) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
39 |
self.ring = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
40 |
for _, node_name in ipairs(nodes) do |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
41 |
if not self.nodes[node_name] then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
42 |
self.nodes[node_name] = true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
43 |
table.insert(self.nodes, node_name); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
44 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
45 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
46 |
return true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
47 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
48 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
49 |
function hashring_methods:remove_node(node_name) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
50 |
self.ring = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
51 |
if self.nodes[node_name] then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
52 |
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
|
53 |
if node_name == stored_node_name then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
54 |
self.nodes[node_name] = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
55 |
table.remove(self.nodes, i); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
56 |
return true; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
57 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
58 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
59 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
60 |
return false; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
61 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
62 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
63 |
function hashring_methods:remove_nodes(nodes) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
64 |
self.ring = nil; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
65 |
for _, node_name in ipairs(nodes) do |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
66 |
self:remove_node(node_name); |
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 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
69 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
70 |
function hashring_methods:clone() |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
71 |
local clone_hashring = new(self.num_replicas, self.hash); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
72 |
clone_hashring:add_nodes(self.nodes); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
73 |
return clone_hashring; |
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:get_node(key) |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
77 |
local key_hash = self.hash(key); |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
78 |
for _, replica_hash in ipairs(self.ring) do |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
79 |
if key_hash < replica_hash then |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
80 |
return self.ring[replica_hash]; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
81 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
82 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
83 |
return self.ring[self.ring[1]]; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
84 |
end |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
85 |
|
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
86 |
return { |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
87 |
new = new; |
409ff72c501c
util.hashring: Implementation of hashring data structure
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
88 |
} |