1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
# frozen_string_literal: true
require 'zlib'
class RedisClient
class HashRing
POINTS_PER_SERVER = 160
class << self
attr_writer :digest
def digest
@digest ||= begin
require 'digest/md5'
Digest::MD5
end
end
end
attr_reader :nodes
def initialize(nodes = [], replicas: POINTS_PER_SERVER, digest: self.class.digest)
@replicas = replicas
@ring = {}
@digest = digest
ids = {}
@nodes = nodes.dup.freeze
nodes.each do |node|
id = node.id || node.config.server_url
if ids[id]
raise ArgumentError, "duplicate node id: #{id.inspect}"
end
ids[id] = true
replicas.times do |i|
@ring[server_hash_for("#{id}:#{i}".freeze)] = node
end
end
@sorted_keys = @ring.keys
@sorted_keys.sort!
end
# get the node in the hash ring for this key
def node_for(key)
hash = hash_for(key)
idx = binary_search(@sorted_keys, hash)
@ring[@sorted_keys[idx]]
end
def nodes_for(*keys)
keys.flatten!
mapping = {}
keys.each do |key|
(mapping[node_for(key)] ||= []) << key
end
mapping
end
private
def hash_for(key)
Zlib.crc32(key)
end
def server_hash_for(key)
@digest.digest(key).unpack1("L>")
end
# Find the closest index in HashRing with value <= the given value
def binary_search(ary, value)
upper = ary.size
lower = 0
while lower < upper
mid = (lower + upper) / 2
if ary[mid] > value
upper = mid
else
lower = mid + 1
end
end
upper - 1
end
end
end
|
