prosody
ca6a43fe0231
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 @ 12579:ca6a43fe0231 0.12

util.jsonschema: Fix validation to not assume presence of "type" field MattJ reported a curious issue where validation did not work as expected. Primarily that the "type" field was expected to be mandatory, and thus leaving it out would result in no checks being performed. This was likely caused by misreading during initial development. Spent some time testing against https://github.com/json-schema-org/JSON-Schema-Test-Suite.git and discovered a multitude of issues, far too many to bother splitting into separate commits. More than half of them fail. Many because of features not implemented, which have been marked NYI. For example, some require deep comparisons e.g. when objects or arrays are present in enums fields. Some because of quirks with how Lua differs from JavaScript, e.g. no distinct array or object types. Tests involving fractional floating point numbers. We're definitely not going to follow references to remote resources. Or deal with UTF-16 sillyness. One test asserted that 1.0 is an integer, where Lua 5.3+ will disagree.
author Kim Alvefur <zash@zash.se>
date Fri, 08 Jul 2022 14:38:23 +0200
parent 11208:96429946a742
child 12795:87424cbedc55
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
10005
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 = {};
11208
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
3 for _, node_name in ipairs(nodes) do
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
4 for replica = 1, num_replicas do
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
5 local replica_hash = hash(node_name..":"..replica);
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
6 new_ring[replica_hash] = node_name;
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
7 table.insert(new_ring, replica_hash);
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
8 end
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
9 end
96429946a742 util.hashring: Normalize indentation to tabs
Kim Alvefur <zash@zash.se>
parents: 10005
diff changeset
10 table.sort(new_ring);
10005
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 }