Class: Polyrun::Partition::PlanLptBuckets

Inherits:
Object
  • Object
show all
Defined in:
lib/polyrun/partition/plan_lpt.rb

Overview

LPT greedy binpack for cost strategies (extracted from Plan for size limits).

Instance Method Summary collapse

Constructor Details

#initialize(plan) ⇒ PlanLptBuckets

Returns a new instance of PlanLptBuckets.



7
8
9
 
# File 'lib/polyrun/partition/plan_lpt.rb', line 7

def initialize(plan)
  @plan = plan
end

Instance Method Details

#build ⇒ Object 



11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/polyrun/partition/plan_lpt.rb', line 11

def build
  if @plan.stable_strategy? && @plan.stable_assignment_map&.any?
    stable = build_from_stable_map
    return stable if imbalance_ratio(stable) <= @plan.stable_imbalance_threshold
  end

  buckets = Array.new(@plan.total_shards) { [] }
  totals = Array.new(@plan.total_shards, 0.0)
  forced_pairs, free = partition_forced_and_free
  lpt_apply_forced!(buckets, totals, forced_pairs)
  lpt_balance_free!(buckets, totals, free)
  buckets
end

#build_from_stable_map ⇒ Object 



25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/polyrun/partition/plan_lpt.rb', line 25

def build_from_stable_map
  buckets = Array.new(@plan.total_shards) { [] }
  map = @plan.stable_assignment_map
  @plan.items.each do |item|
    key = @plan.send(:cost_lookup_key, item)
    j = map[key]
    j = Integer(j) if j
    j = fallback_shard_for(item) unless j && j >= 0 && j < @plan.total_shards
    buckets[j] << item
  end
  buckets
end

#fallback_shard_for(item) ⇒ Object 



38
39
40
 
# File 'lib/polyrun/partition/plan_lpt.rb', line 38

def fallback_shard_for(item)
  Hrw.shard_for(path: item, total_shards: @plan.total_shards, seed: @plan.send(:hrw_salt))
end

#imbalance_ratio(buckets) ⇒ Object 



42
43
44
45
46
47
48
49
50
 
# File 'lib/polyrun/partition/plan_lpt.rb', line 42

def imbalance_ratio(buckets)
  totals = buckets.map { |paths| paths.sum { |p| @plan.send(:weight_for, p) } }
  return 1.0 if totals.empty?

  avg = totals.sum / totals.size.to_f
  return 1.0 unless avg.positive?

  totals.max / avg
end