Class: Philiprehberger::HashRing::Ring

Inherits:
Object
  • Object
show all
Defined in:
lib/philiprehberger/hash_ring/ring.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(nodes = [], replicas: 150, hash: nil) ⇒ Ring

Returns a new instance of Ring.



11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 11

def initialize(nodes = [], replicas: 150, hash: nil)
  if hash
    raise ArgumentError, 'hash must respond to :call' unless hash.respond_to?(:call)

    @custom_hash = hash
  end

  @replicas = replicas
  @nodes = {}
  @ring = []
  @sorted_positions = []

  nodes.each { |node| add(node) }
end

Instance Attribute Details

#replicas ⇒ Object (readonly)

Returns the value of attribute replicas.



9
10
11
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 9

def replicas
  @replicas
end

Class Method Details

.from_json(data) ⇒ Object 



107
108
109
110
111
112
113
114
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 107

def self.from_json(data)
  parsed = JSON.parse(data)
  ring = new([], replicas: parsed['replicas'])
  parsed['nodes'].each do |entry|
    ring.add(entry['name'], weight: entry['weight'])
  end
  ring
end

Instance Method Details

#==(other) ⇒ Boolean Also known as: eql?

Compare two rings for structural equality (same nodes, weights, replicas).

Parameters:

Returns:

  • (Boolean) 


214
215
216
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 214

def ==(other)
  other.is_a?(Ring) && @nodes == other.instance_variable_get(:@nodes) && @replicas == other.replicas
end

#add(node, weight: 1) ⇒ Object 



26
27
28
29
30
31
32
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 26

def add(node, weight: 1)
  return if @nodes.key?(node)

  @nodes[node] = weight
  rebuild_ring
  self
end

#balance_score ⇒ Object 



116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 116

def balance_score
  return 1.0 if @nodes.empty?

  test_keys = (0...10_000).map { |i| "key_#{i}" }
  dist = distribution(test_keys)
  counts = @nodes.keys.map { |node| dist[node] || 0 }
  ideal = 10_000.0 / @nodes.size
  mean = counts.sum.to_f / counts.size
  variance = counts.sum { |c| (c - mean)**2 } / counts.size.to_f
  std_dev = Math.sqrt(variance)
  score = 1.0 - (std_dev / ideal)
  score.clamp(0.0, 1.0)
end

#distribution(keys) ⇒ Object 



72
73
74
75
76
77
78
79
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 72

def distribution(keys)
  result = Hash.new(0)
  keys.each do |key|
    node = get(key)
    result[node] += 1 if node
  end
  result
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


68
69
70
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 68

def empty?
  @nodes.empty?
end

#get(key) ⇒ Object 



42
43
44
45
46
47
48
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 42

def get(key)
  return nil if @ring.empty?

  pos = hash_key(key.to_s)
  idx = binary_search(pos)
  @ring[idx][1]
end

#get_n(key, count) ⇒ Object 



50
51
52
53
54
55
56
57
58
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 50

def get_n(key, count)
  return [] if @ring.empty?

  count = [@nodes.size, count].min
  pos = hash_key(key.to_s)
  idx = binary_search(pos)

  collect_distinct_nodes(idx, count)
end

#hash ⇒ Object 



220
221
222
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 220

def hash
  [@nodes, @replicas].hash
end

#hash_for(key) ⇒ Object 



202
203
204
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 202

def hash_for(key)
  hash_key(key.to_s)
end

#hotspots(keys, threshold: 1.5) ⇒ Object 



161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 161

def hotspots(keys, threshold: 1.5)
  return [] if @nodes.empty?

  dist = distribution(keys)
  total = keys.size.to_f
  total_weight = @nodes.values.sum.to_f

  @nodes.each_with_object([]) do |(node, weight), result|
    count = dist[node] || 0
    ideal_count = if @nodes.values.all? { |w| w == 1 }
                    total / @nodes.size
                  else
                    (weight / total_weight) * total
                  end
    result << node if ideal_count.positive? && count > threshold * ideal_count
  end
end

#migration_plan(other_ring) ⇒ Object 



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 81

def migration_plan(other_ring)
  test_keys = (0...10_000).map { |i| "key_#{i}" }
  moved = []
  summary = Hash.new { |h, k| h[k] = { gained: 0, lost: 0 } }

  test_keys.each do |key|
    from = get(key)
    to = other_ring.get(key)
    next if from == to

    moved << { key_sample: key, from: from, to: to }
    summary[from][:lost] += 1 if from
    summary[to][:gained] += 1 if to
  end

  { moved: moved, summary: summary }
end

#nodes ⇒ Object 



60
61
62
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 60

def nodes
  @nodes.keys
end

#nodes_for_keys(keys) ⇒ Object 



130
131
132
133
134
135
136
137
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 130

def nodes_for_keys(keys)
  result = Hash.new { |h, k| h[k] = [] }
  keys.each do |key|
    node = get(key)
    result[node] << key if node
  end
  result
end

#rebalance_suggestions(keys) ⇒ Object 



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 179

def rebalance_suggestions(keys)
  return [] if @nodes.empty?

  node_stats = stats(keys)
  node_stats.each_with_object([]) do |(node, s), suggestions|
    deviation = s[:percentage] - s[:ideal_percentage]
    next unless deviation.abs > 10.0

    suggestions << {
      node: node,
      action: deviation.positive? ? :decrease : :increase,
      current_pct: s[:percentage],
      ideal_pct: s[:ideal_percentage]
    }
  end
end

#remove(node) ⇒ Object 



34
35
36
37
38
39
40
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 34

def remove(node)
  return unless @nodes.key?(node)

  @nodes.delete(node)
  rebuild_ring
  self
end

#replicas_for(key, count) ⇒ Object 



206
207
208
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 206

def replicas_for(key, count)
  get_n(key, count)
end

#size ⇒ Object 



64
65
66
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 64

def size
  @nodes.size
end

#stats(keys) ⇒ Object 



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 139

def stats(keys)
  return {} if @nodes.empty?

  dist = distribution(keys)
  total = keys.size.to_f
  total_weight = @nodes.values.sum.to_f

  @nodes.each_with_object({}) do |(node, weight), result|
    count = dist[node] || 0
    ideal_pct = if @nodes.values.all? { |w| w == 1 }
                  100.0 / @nodes.size
                else
                  (weight / total_weight) * 100.0
                end
    result[node] = {
      count: count,
      percentage: total.zero? ? 0.0 : (count / total) * 100.0,
      ideal_percentage: ideal_pct
    }
  end
end

#to_json(*_args) ⇒ Object 



99
100
101
102
103
104
105
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 99

def to_json(*_args)
  data = {
    'nodes' => @nodes.map { |node, weight| { 'name' => node, 'weight' => weight } },
    'replicas' => @replicas
  }
  JSON.generate(data)
end

#virtual_nodes ⇒ Object 



196
197
198
199
200
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 196

def virtual_nodes
  @nodes.each_with_object({}) do |(node, weight), result|
    result[node] = @replicas * weight
  end
end