aboutsummaryrefslogtreecommitdiffstats
path: root/util
diff options
context:
space:
mode:
authorMatthew Wild <mwild1@gmail.com>2019-05-13 10:03:46 +0100
committerMatthew Wild <mwild1@gmail.com>2019-05-13 10:03:46 +0100
commita9d08911dc2534d7cbfc898c7a0b4fb3fab88cf4 (patch)
treeb4ba1536c225119db178c32b6c5452b627f94c38 /util
parent037fc25b4c87c9ee1168635335c3ac5ee3af7353 (diff)
downloadprosody-a9d08911dc2534d7cbfc898c7a0b4fb3fab88cf4.tar.gz
prosody-a9d08911dc2534d7cbfc898c7a0b4fb3fab88cf4.zip
util.hashring: Implementation of hashring data structure
Diffstat (limited to 'util')
-rw-r--r--util/hashring.lua88
1 files changed, 88 insertions, 0 deletions
diff --git a/util/hashring.lua b/util/hashring.lua
new file mode 100644
index 00000000..322bc005
--- /dev/null
+++ b/util/hashring.lua
@@ -0,0 +1,88 @@
+local function generate_ring(nodes, num_replicas, hash)
+ local new_ring = {};
+ for _, node_name in ipairs(nodes) do
+ for replica = 1, num_replicas do
+ local replica_hash = hash(node_name..":"..replica);
+ new_ring[replica_hash] = node_name;
+ table.insert(new_ring, replica_hash);
+ end
+ end
+ table.sort(new_ring);
+ return new_ring;
+end
+
+local hashring_methods = {};
+local hashring_mt = {
+ __index = function (self, k)
+ -- Automatically build self.ring if it's missing
+ if k == "ring" then
+ local ring = generate_ring(self.nodes, self.num_replicas, self.hash);
+ rawset(self, "ring", ring);
+ return ring;
+ end
+ return rawget(hashring_methods, k);
+ end
+};
+
+local function new(num_replicas, hash_function)
+ return setmetatable({ nodes = {}, num_replicas = num_replicas, hash = hash_function }, hashring_mt);
+end;
+
+function hashring_methods:add_node(name)
+ self.ring = nil;
+ self.nodes[name] = true;
+ table.insert(self.nodes, name);
+ return true;
+end
+
+function hashring_methods:add_nodes(nodes)
+ self.ring = nil;
+ for _, node_name in ipairs(nodes) do
+ if not self.nodes[node_name] then
+ self.nodes[node_name] = true;
+ table.insert(self.nodes, node_name);
+ end
+ end
+ return true;
+end
+
+function hashring_methods:remove_node(node_name)
+ self.ring = nil;
+ if self.nodes[node_name] then
+ for i, stored_node_name in ipairs(self.nodes) do
+ if node_name == stored_node_name then
+ self.nodes[node_name] = nil;
+ table.remove(self.nodes, i);
+ return true;
+ end
+ end
+ end
+ return false;
+end
+
+function hashring_methods:remove_nodes(nodes)
+ self.ring = nil;
+ for _, node_name in ipairs(nodes) do
+ self:remove_node(node_name);
+ end
+end
+
+function hashring_methods:clone()
+ local clone_hashring = new(self.num_replicas, self.hash);
+ clone_hashring:add_nodes(self.nodes);
+ return clone_hashring;
+end
+
+function hashring_methods:get_node(key)
+ local key_hash = self.hash(key);
+ for _, replica_hash in ipairs(self.ring) do
+ if key_hash < replica_hash then
+ return self.ring[replica_hash];
+ end
+ end
+ return self.ring[self.ring[1]];
+end
+
+return {
+ new = new;
+}