ceph/src/test/old/testcrush.cc

   1 #include "../crush/crush.h"
   2 using namespace crush;
   3
   4 #include <math.h>
   5
   6 #include <iostream>
   7 #include <vector>
   8 using namespace std;
   9
  10 void make_disks(int n, int& no, vector<int>& d)
  11 {
  12   d.clear();
  13   while (n) {
  14     d.push_back(no);
  15     no++;
  16     n--;
  17   }
  18 }
  19
  20 Bucket *make_bucket(Crush& c, vector<int>& wid, int h, int& ndisks, int& nbuckets)
  21 {
  22   if (h == 0) {
  23     // uniform
  24     Hash hash(123);
  25     vector<int> disks;
  26     for (int i=0; i<wid[h]; i++)
  27       disks.push_back(ndisks++);
  28     UniformBucket *b = new UniformBucket(nbuckets--, 1, 0, 10, disks);
  29     b->make_primes(hash);
  30     c.add_bucket(b);
  31     return b;
  32   } else {
  33     // mixed
  34     MixedBucket *b = new MixedBucket(nbuckets--, h+1);
  35     for (int i=0; i<wid[h]; i++) {
  36       Bucket *n = make_bucket(c, wid, h-1, ndisks, nbuckets);
  37       b->add_item(n->get_id(), n->get_weight());
  38     }
  39     c.add_bucket(b);
  40     return b;
  41   }
  42 }
  43
  44 int make_hierarchy(Crush& c, vector<int>& wid, int& ndisks, int& nbuckets)
  45 {
  46   Bucket *b = make_bucket(c, wid, wid.size()-1, ndisks, nbuckets);
  47   return b->get_id();
  48 }
  49
  50
  51
  52 int main()
  53 {
  54   Hash h(73232313);
  55
  56   // crush
  57   Crush c;
  58
  59   // buckets
  60   vector<int> disks;
  61   int root = -1;
  62   int nbuckets = -1;
  63   int ndisks = 0;
  64
  65   if (0) {
  66     make_disks(12, ndisks, disks);
  67     UniformBucket ub1(-1, 1, 0, 30, disks);
  68     ub1.make_primes(h);
  69     cout << "ub1 primes are " << ub1.primes << endl;
  70     c.add_bucket(&ub1);
  71
  72     make_disks(17, ndisks, disks);
  73     UniformBucket ub2(-2, 1, 0, 30, disks);
  74     ub2.make_primes(h);
  75     cout << "ub2 primes are " << ub2.primes << endl;
  76     c.add_bucket(&ub2);
  77
  78     make_disks(4, ndisks, disks);
  79     UniformBucket ub3(-3, 1, 0, 30, disks);
  80     ub3.make_primes(h);
  81     cout << "ub3 primes are " << ub3.primes << endl;
  82     c.add_bucket(&ub3);
  83
  84     make_disks(20, ndisks, disks);
  85     MixedBucket umb1(-4, 1);
  86     for (int i=0; i<20; i++)
  87       umb1.add_item(disks[i], 30);
  88     c.add_bucket(&umb1);
  89
  90     MixedBucket b(-100, 1);
  91     b.add_item(-4, umb1.get_weight());
  92   }
  93
  94   if (0) {
  95     int bucket = -1;
  96     MixedBucket *root = new MixedBucket(bucket--, 2);
  97
  98     for (int i=0; i<5; i++) {
  99       MixedBucket *b = new MixedBucket(bucket--, 1);
 100
 101       int n = 5;
 102
 103       if (1) {
 104         // add n buckets of n disks
 105         for (int j=0; j<n; j++) {
 106
 107           MixedBucket *d = new MixedBucket(bucket--, 1);
 108
 109           make_disks(n, ndisks, disks);
 110           for (int k=0; k<n; k++)
 111             d->add_item(disks[k], 10);
 112
 113           c.add_bucket(d);
 114           b->add_item(d->get_id(), d->get_weight());
 115         }
 116
 117         c.add_bucket(b);
 118         root->add_item(b->get_id(), b->get_weight());
 119       } else {
 120         // add n*n disks
 121         make_disks(n*n, ndisks, disks);
 122         for (int k=0; k<n*n; k++)
 123           b->add_item(disks[k], 10);
 124
 125         c.add_bucket(b);
 126         root->add_item(b->get_id(), b->get_weight());
 127       }
 128     }
 129
 130     c.add_bucket(root);
 131   }
 132
 133
 134   if (1) {
 135     vector<int> wid;
 136     for (int d=0; d<5; d++)
 137       wid.push_back(10);
 138     root = make_hierarchy(c, wid, ndisks, nbuckets);
 139   }
 140
 141   // rule
 142   int numrep = 1;
 143
 144   Rule rule;
 145   if (0) {
 146     rule.steps.push_back(RuleStep(CRUSH_RULE_TAKE, -100));
 147     rule.steps.push_back(RuleStep(CRUSH_RULE_CHOOSE, numrep, 0));
 148   }
 149   if (1) {
 150     rule.steps.push_back(RuleStep(CRUSH_RULE_TAKE, root));
 151     rule.steps.push_back(RuleStep(CRUSH_RULE_CHOOSE, 1, 0));
 152     rule.steps.push_back(RuleStep(CRUSH_RULE_EMIT));
 153   }
 154
 155   int pg_per = 100;
 156   int numpg = pg_per*ndisks/numrep;
 157
 158   vector<int> ocount(ndisks);
 159   cout << ndisks << " disks, " << 1-nbuckets << " buckets" << endl;
 160   cout << pg_per << " pgs per disk" << endl;
 161   cout << numpg << " logical pgs" << endl;
 162   cout << "numrep is " << numrep << endl;
 163
 164
 165   int place = 1000000;
 166   int times = place / numpg;
 167   if (!times) times = 1;
 168
 169   cout << "looping " << times << " times" << endl;
 170
 171   float tvar = 0;
 172   int tvarnum = 0;
 173
 174   int x = 0;
 175   for (int t=0; t<times; t++) {
 176     vector<int> v(numrep);
 177
 178     for (int z=0; z<ndisks; z++) ocount[z] = 0;
 179
 180     for (int xx=1; xx<numpg; xx++) {
 181       x++;
 182
 183       c.do_rule(rule, x, v);
 184
 185       bool bad = false;
 186       for (int i=0; i<numrep; i++) {
 187         ocount[v[i]]++;
 188         for (int j=i+1; j<numrep; j++) {
 189           if (v[i] == v[j])
 190             bad = true;
 191         }
 192       }
 193       if (bad)
 194         cout << "bad set " << x << ": " << v << endl;
 195     }
 196
 197     cout << "collisions: " << c.collisions << endl;
 198     cout << "r bumps: " << c.bumps << endl;
 199
 200
 201     float avg = 0.0;
 202     for (int i=0; i<ocount.size(); i++)
 203       avg += ocount[i];
 204     avg /= ocount.size();
 205     float var = 0.0;
 206     for (int i=0; i<ocount.size(); i++)
 207       var += (ocount[i] - avg) * (ocount[i] - avg);
 208     var /= ocount.size();
 209
 210     cout << "avg " << avg << "  var " << var << "   sd " << sqrt(var) << endl;
 211
 212     tvar += var;
 213     tvarnum++;
 214   }
 215
 216   tvar /= tvarnum;
 217
 218   cout << "total variance " << tvar << endl;
 219 }