mpa2.py

#!/usr/bin/env python

import random
from math import sqrt, log, pow

DEBUG = True
NPGS = 100000 # num PGs
R = 3  # num replicas

if NPGS > 3:
  DEBUG = False

print 'Num PGs:', NPGS
print 'Num Replicas:', R

# OSDs: (id, weight)
# TODO: everything below is hard coded for exactly 4 OSDs
osds = [(0, 2.0), (1, 3.0), (2, 4.0), (3, 1.0)]

weights = {}  # OSD weights.. we might tweak these round by round
orig_weights = {}  # OSD weights. Read only.
total_weight = 0
for id, w in osds:
  weights[id] = float(w)
  orig_weights[id] = float(w)
  total_weight += float(w)

print 'OSDs (id: weight):', weights

# compute the expected # PGs for our 4 OSDs
expected = {
  0: NPGS * R * weights[0]/total_weight,
  1: NPGS * R * weights[1]/total_weight,
  2: NPGS * R * weights[2]/total_weight,
  3: NPGS * R * weights[3]/total_weight,
}

print '\nExpected:  ', expected
for r in xrange(R):
  print '  Replica %d: %s' % (r, [float(v/R) for k,v in expected.iteritems()])

# initialize PG and PG-by-replicanum counters for each OSD
pgs = {
  0: 0,
  1: 0,
  2: 0,
  3: 0,
}
pgs_by_r = [dict(pgs) for r in xrange(R)]

def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w >= r:
         return c
      upto += w
   assert False, "Shouldn't get here"

print "\nSimulating with existing CRUSH\n"

# simple CRUSH
# loop over all PGs, select one with weighted choice, remove that option for the next choice.
for i in xrange(NPGS):
  choices = list(osds)
  for r in xrange(R):
    pick = weighted_choice(choices)
    pgs[pick] += 1
    pgs_by_r[r][pick] += 1
    choices.remove((pick, weights[pick]),)

print 'Observed:   ', pgs
for r in xrange(R):
  print '  Replica %d: %s' % (r, pgs_by_r[r])


print "\nNow trying your new algorithm\n"

# initialize PG and PG-by-replicanum counters for each OSD
pgs = {
  0: 0,
  1: 0,
  2: 0,
  3: 0,
}
pgs_by_r = [dict(pgs) for r in xrange(R)]

# modified CRUSH
# loop over each PG.
# After each replica selection, adjust the remaining choices' weights with your magic value.
for i in xrange(NPGS):
  choices = list(osds)
  picks = []
  for r in xrange(R):
    # loop here to limit time
    while True:
      candidate = weighted_choice(choices)
      if candidate not in picks:
        picks.append(weighted_choice(choices))
        break
  r = 0
  for pick in picks:
    pgs[pick] += 1
    pgs_by_r[r][pick] += 1
    r += 1

print 'Observed:   ', pgs
for r in xrange(R):
  print '  Replica %d: %s' % (r, pgs_by_r[r])