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 



149
150
151
152
153
154
155
156
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 149

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) 


256
257
258
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 256

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

#add(node, weight: 1) ⇒ Ring

Add a node to the ring with an optional weight multiplier.

Parameters:

  • node (Object) —

    the node identifier to add

  • weight (Integer) (defaults to: 1) —

    multiplier applied to the replica count for this node (default: 1)

Returns:

  • (Ring) —

    self for chaining



31
32
33
34
35
36
37
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 31

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

  @nodes[node] = weight
  rebuild_ring
  self
end

#balance_score ⇒ Object 



158
159
160
161
162
163
164
165
166
167
168
169
170
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 158

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) ⇒ Hash{Object => Integer}

Count how many of the supplied keys route to each node.

Parameters:

  • keys (Enumerable) —

    the keys to route through the ring

Returns:

  • (Hash{Object => Integer}) —

    a mapping of node to the number of keys routed to it



89
90
91
92
93
94
95
96
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 89

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) 


81
82
83
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 81

def empty?
  @nodes.empty?
end

#get(key) ⇒ Object?

Find the node responsible for a given key using consistent hashing.

Parameters:

  • key (Object) —

    the key to route (coerced to String)

Returns:

  • (Object, nil) —

    the node responsible for the key, or nil if the ring is empty



55
56
57
58
59
60
61
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 55

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 



63
64
65
66
67
68
69
70
71
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 63

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 



262
263
264
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 262

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

#hash_for(key) ⇒ Object 



244
245
246
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 244

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

#hotspots(keys, threshold: 1.5) ⇒ Object 



203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 203

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

#load_factor(keys) ⇒ Float

Measure the balance of key distribution as a coefficient of variation.

For each key, determines which node it routes to and counts the per-node distribution. Returns the standard deviation of those counts divided by their mean. Lower values indicate a more uniform distribution (0.0 = perfectly balanced).

Parameters:

  • keys (Enumerable) —

    the keys to route through the ring

Returns:

  • (Float) —

    the coefficient of variation of per-node key counts, or 0.0 when ‘keys` is empty or the ring has 0 or 1 nodes



108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 108

def load_factor(keys)
  return 0.0 if @nodes.size < 2

  key_list = keys.to_a
  return 0.0 if key_list.empty?

  dist = distribution(key_list)
  counts = @nodes.keys.map { |node| dist[node] || 0 }
  mean = counts.sum.to_f / counts.size
  return 0.0 if mean.zero?

  variance = counts.sum { |c| (c - mean)**2 } / counts.size.to_f
  Math.sqrt(variance) / mean
end

#migration_plan(other_ring) ⇒ Object 



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 123

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 



73
74
75
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 73

def nodes
  @nodes.keys
end

#nodes_for_keys(keys) ⇒ Object 



172
173
174
175
176
177
178
179
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 172

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 



221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 221

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) ⇒ Ring

Remove a node and all of its virtual replicas from the ring.

Parameters:

  • node (Object) —

    the node identifier to remove

Returns:

  • (Ring) —

    self for chaining



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

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

  @nodes.delete(node)
  rebuild_ring
  self
end

#replicas_for(key, count) ⇒ Object 



248
249
250
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 248

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

#size ⇒ Object 



77
78
79
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 77

def size
  @nodes.size
end

#stats(keys) ⇒ Object 



181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 181

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 



141
142
143
144
145
146
147
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 141

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

#virtual_nodes ⇒ Object 



238
239
240
241
242
 
# File 'lib/philiprehberger/hash_ring/ring.rb', line 238

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