Class: Gizzard::Rebalancer

Inherits:
Object
  • Object
show all
Defined in:
lib/gizzard/rebalancer.rb

Defined Under Namespace

Classes: Bucket, TemplateAndTree

Instance Method Summary collapse

Constructor Details

#initialize(forwardings_to_trees, dest_templates_and_weights, wrapper) ⇒ Rebalancer

steps for rebalancing.

  1. get a list of forwarding/template associations

  2. get a list of destination templates and weights

  3. order shards by weight. (ascending or descending)

  4. put shards in destinations based on reducing number of copies required.

5.



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/gizzard/rebalancer.rb', line 23

def initialize(forwardings_to_trees, dest_templates_and_weights, wrapper)
  @copy_dest_wrapper = wrapper
  @shards = forwardings_to_trees.map do |forwarding, tree|
    TemplateAndTree.new(tree.template, forwarding, tree)
  end.flatten

  @dest_templates      = dest_templates_and_weights.keys

  total_shards = @shards.length
  total_weight = dest_templates_and_weights.values.inject {|a,b| a + b }

  @result = dest_templates_and_weights.map do |template, weight|
    weight_fraction = weight / total_weight.to_f
    approx_shards   = total_shards * weight_fraction

    Bucket.new template, approx_shards, Set.new
  end
end

Instance Method Details

#bucket_disparity ⇒ Object 



110
111
112
113
 
# File 'lib/gizzard/rebalancer.rb', line 110

def bucket_disparity
  ordered = ordered_buckets
  ordered.last.balance - ordered.first.balance
end

#home! ⇒ Object 



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
 
# File 'lib/gizzard/rebalancer.rb', line 42

def home!

  # list of [template, shards] in descending length of shards
  templates_to_shards =
    @shards.inject({}) do |h, shard|
      (h[shard.template] ||= []) << shard; h
    end.sort_by {|(_,ss)| ss.length * -1 }

  templates_to_shards.each do |(template, shards)|
    descendants = memoized_concrete_descendants(template)

    most_similar_buckets = []
    last_cost = nil

    @result.each do |bucket|
      cost      = (memoized_concrete_descendants(bucket.template) - descendants).length
      last_cost = cost if last_cost.nil?

      if cost == last_cost
        most_similar_buckets << bucket
      elsif cost < last_cost
        last_cost = cost
        most_similar_buckets = [bucket]
      end
    end

    dest_bucket = most_similar_buckets.sort_by {|b| b.balance }.first

    dest_bucket.merge shards
  end
end

#memoized_concrete_descendants(t) ⇒ Object 



105
106
107
108
 
# File 'lib/gizzard/rebalancer.rb', line 105

def memoized_concrete_descendants(t)
  @memoized_concrete_descendants ||= {}
  @memoized_concrete_descendants[t] ||= t.concrete_descendants
end

#move_shard(template, shard) ⇒ Object 



115
116
117
118
119
120
121
122
123
 
# File 'lib/gizzard/rebalancer.rb', line 115

def move_shard(template, shard)
  @result.each do |bucket|
    if bucket.template == template
      bucket.add shard
    else
      bucket.delete shard
    end
  end
end

#ordered_buckets ⇒ Object 



101
102
103
 
# File 'lib/gizzard/rebalancer.rb', line 101

def ordered_buckets
  @result.sort_by {|bucket| bucket.balance }
end

#rebalance! ⇒ Object 



74
75
76
77
78
79
 
# File 'lib/gizzard/rebalancer.rb', line 74

def rebalance!
  while bucket_disparity > 1
    ordered = ordered_buckets
    move_shard ordered.first.template, ordered.last.set.each {|e| break e }
  end
end

#transformations ⇒ Object 



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/gizzard/rebalancer.rb', line 81

def transformations
  return @transformations if @transformations

  home!
  rebalance!

  @transformations = {}
  @result.each do |bucket|
    bucket.set.each do |shard|
      trans = Transformation.new(shard.template, bucket.template, @copy_dest_wrapper)
      forwardings_to_trees = (@transformations[trans] ||= {})

      forwardings_to_trees.update(shard.forwarding => shard.tree)
    end
  end

  @transformations.reject! {|t, _| t.noop? }
  @transformations
end