← Back to branch summary

~ubuntu-branches/ubuntu/quantal/ceph/quantal

« back to all changes in this revision

Viewing changes to src/crush/CrushTester.cc

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-07-16 09:56:24 UTC
  • mfrom: (0.3.11)
  • mto: This revision was merged to the branch mainline in revision 17.
  • Revision ID: package-import@ubuntu.com-20120716095624-azr2w4hbhei1rxmx
Tags: upstream-0.48
Import upstream version 0.48

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/crush/CrushTester.cc
1
1
 
2
2
#include "CrushTester.h"
3
3
 
 
4
//chi squared stuff
 
5
#include <math.h>
 
6
 
 
7
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
8
# include <boost/math/distributions/chi_squared.hpp>
 
9
# include <boost/accumulators/statistics/variance.hpp>
 
10
# include <boost/accumulators/accumulators.hpp>
 
11
# include <boost/accumulators/statistics/stats.hpp>
 
12
 
 
13
//random number generator
 
14
# include <boost/random/mersenne_twister.hpp>
 
15
# include <boost/random/discrete_distribution.hpp>
 
16
# include <boost/random/uniform_int_distribution.hpp>
 
17
 
 
18
// needed to compute chi squared value
 
19
using boost::math::chi_squared;
 
20
using boost::accumulators::stats;
 
21
using boost::accumulators::variance;
 
22
using boost::accumulators::accumulator_set;
 
23
 
 
24
// create a random number generator to simulate placements
 
25
 
 
26
// use the mersenne twister as our seed generator
 
27
typedef boost::mt19937 generator;
 
28
 
 
29
generator gen(42); // repeatable
 
30
//generator gen(static_cast<unsigned int>(std::time(0))); // non-repeatable (ish)
 
31
 
 
32
// create another random number generator to pick buckets when we want to mark devices down
 
33
generator bucket_gen(42);
 
34
 
 
35
#endif
 
36
 
 
37
 
4
38
void CrushTester::set_device_weight(int dev, float f)
5
39
{
6
40
  int w = (int)(f * 0x10000);
11
45
  device_weight[dev] = w;
12
46
}
13
47
 
 
48
void CrushTester::adjust_weights(vector<__u32>& weight)
 
49
{
 
50
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
51
  //err << "start " << weight << std::endl;
 
52
 
 
53
  if (mark_down_device_ratio > 0) {
 
54
    // active buckets
 
55
    vector<int> bucket_ids;
 
56
    for (int i = 0; i < crush.get_max_buckets(); i++) {
 
57
      int id = -1 - i;
 
58
      if (crush.get_bucket_weight(id) > 0) {
 
59
        bucket_ids.push_back(id);
 
60
      }
 
61
    }
 
62
 
 
63
    // get buckets that are one level above a device
 
64
    vector<int> buckets_above_devices;
 
65
    for (unsigned i = 0; i < bucket_ids.size(); i++) {
 
66
      // grab the first child object of a bucket and check if it's ID is less than 0
 
67
      int id = bucket_ids[i];
 
68
      if (crush.get_bucket_size(id) == 0)
 
69
        continue;
 
70
      int first_child = crush.get_bucket_item(id, 0); // returns the ID of the bucket or device
 
71
      if (first_child >= 0) {
 
72
        buckets_above_devices.push_back(id);
 
73
      }
 
74
    }
 
75
 
 
76
    // create the uniform distribution on the number of buckets to visit
 
77
    boost::random::uniform_int_distribution<> bucket_choose(0, buckets_above_devices.size() - 1);
 
78
 
 
79
    // permute bucket list
 
80
    for (unsigned i = 0; i < buckets_above_devices.size(); i++) {
 
81
      unsigned j = bucket_choose(bucket_gen);
 
82
      std::swap(buckets_above_devices[i], buckets_above_devices[j]);
 
83
    }
 
84
 
 
85
    // calculate how many buckets and devices we need to reap...
 
86
    int num_buckets_to_visit = (int) (mark_down_bucket_ratio * buckets_above_devices.size());
 
87
 
 
88
    for (int i = 0; i < num_buckets_to_visit; i++) {
 
89
      int id = buckets_above_devices[i];
 
90
      int size = crush.get_bucket_size(id);
 
91
      vector<int> items;
 
92
      for (int o = 0; o < size; o++)
 
93
        items.push_back(crush.get_bucket_item(id, o));
 
94
 
 
95
      // permute items
 
96
      boost::random::uniform_int_distribution<> item_choose(0, size - 1);
 
97
      for (int o = 0; o < size; o++) {
 
98
        int j = item_choose(bucket_gen);
 
99
        std::swap(items[o], items[j]);
 
100
      }
 
101
 
 
102
      int local_devices_to_visit = (int) (mark_down_device_ratio*size);
 
103
      for (int o = 0; o < local_devices_to_visit; o++){
 
104
        int item = crush.get_bucket_item(id, o);
 
105
        //err << "device " << item << " in bucket " << id << " weight " << crush.get_bucket_item_weight(id, o) << std::endl;
 
106
        weight[item] = 10;
 
107
      }
 
108
    }
 
109
  }
 
110
#else
 
111
  err << "WARNING: boost::random not compiled in, mark down ratios not working" << std::endl;
 
112
#endif
 
113
}
 
114
 
14
115
int CrushTester::test()
15
116
{
16
117
  if (min_rule < 0 || max_rule < 0) {
22
123
    max_x = 1023;
23
124
  }
24
125
 
25
 
  // all osds in
 
126
  // initial osd weights
26
127
  vector<__u32> weight;
27
 
  for (int o = 0; o < crush.get_max_devices(); o++)
28
 
    if (device_weight.count(o))
 
128
  for (int o = 0; o < crush.get_max_devices(); o++) {
 
129
    if (device_weight.count(o)) {
29
130
      weight.push_back(device_weight[o]);
30
 
    else
 
131
    } else if (crush.check_item_present(o)) {
31
132
      weight.push_back(0x10000);
32
 
  if (verbose>1)
 
133
    } else {
 
134
      weight.push_back(0);
 
135
    }
 
136
  }
 
137
  if (output_utilization_all)
33
138
    err << "devices weights (hex): " << hex << weight << dec << std::endl;
34
139
 
 
140
  // make adjustments
 
141
  adjust_weights(weight);
 
142
 
 
143
  int num_devices_active = 0;
 
144
  for (vector<__u32>::iterator p = weight.begin(); p != weight.end(); ++p)
 
145
    num_devices_active++;
 
146
 
 
147
  if (output_choose_tries)
 
148
    crush.start_choose_profile();
 
149
  
35
150
  for (int r = min_rule; r < crush.get_max_rules() && r <= max_rule; r++) {
36
151
    if (!crush.rule_exists(r)) {
37
 
      if (verbose>0)
38
 
        err << "rule " << r << " dne" << std::endl;
 
152
      if (output_statistics)
 
153
        err << "rule " << r << " dne" << std::endl;
39
154
      continue;
40
155
    }
41
156
    int minr = min_rep, maxr = max_rep;
43
158
      minr = crush.get_rule_mask_min_size(r);
44
159
      maxr = crush.get_rule_mask_max_size(r);
45
160
    }
46
 
 
47
 
    if (verbose>0)
 
161
    
 
162
    if (output_statistics)
48
163
      err << "rule " << r << " (" << crush.get_rule_name(r)
49
 
          << "), x = " << min_x << ".." << max_x
50
 
          << ", numrep = " << minr << ".." << maxr
51
 
          << std::endl;
 
164
      << "), x = " << min_x << ".." << max_x
 
165
      << ", numrep = " << minr << ".." << maxr
 
166
      << std::endl;
 
167
 
52
168
    for (int nr = minr; nr <= maxr; nr++) {
53
169
      vector<int> per(crush.get_max_devices());
54
170
      map<int,int> sizes;
55
 
      for (int x = min_x; x <= max_x; x++) {
56
 
        vector<int> out;
57
 
        crush.do_rule(r, x, out, nr, weight);
58
 
        if (verbose)
59
 
          if (verbose>1)
60
 
            err << " rule " << r << " x " << x << " " << out << std::endl;
61
 
        for (unsigned i = 0; i < out.size(); i++)
62
 
          per[out[i]]++;
63
 
        sizes[out.size()]++;
64
 
      }
65
 
      for (unsigned i = 0; i < per.size(); i++)
66
 
        if (verbose>1)
67
 
          err << "  device " << i << ":\t" << per[i] << std::endl;
 
171
      
 
172
      int num_objects = ((max_x - min_x) + 1);
 
173
      float num_devices = (float) per.size(); // get the total number of devices, better to cast as a float here 
 
174
 
 
175
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
176
      float test_chi_statistic = 0.0; // our observed chi squared statistic
 
177
      
 
178
      // look up the maximum expected chi squared statistic for the 5% and 1% confidence levels
 
179
      float chi_statistic_five_percent = quantile(complement(chi_squared(num_devices_active-1), 0.05));
 
180
      float chi_statistic_one_percent = quantile(complement(chi_squared(num_devices_active-1), 0.01));
 
181
#endif
 
182
      
 
183
      // create a map to hold batch-level placement information
 
184
      map<int, vector<int> > batchPer; 
 
185
      vector <float> deviceTestChi (per.size() );
 
186
      
 
187
      int objects_per_batch = num_objects / num_batches;
 
188
      
 
189
      int batch_min = min_x;
 
190
      int batch_max = min_x + objects_per_batch - 1;
 
191
      
 
192
      
 
193
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
194
      // placeholders for the reference values, we will probably SEGFAULT if we try zero degrees of freedom
 
195
      float batch_chi_statistic_five_percent = -1.0;
 
196
      float batch_chi_statistic_one_percent = -1.0;
 
197
      
 
198
      if (num_batches > 1) {
 
199
        // look up the chi squared statistic for the 5% and 1% confidence levels
 
200
        batch_chi_statistic_five_percent = quantile(complement(chi_squared(num_batches-1), 0.05));
 
201
        batch_chi_statistic_one_percent = quantile(complement(chi_squared(num_batches-1), 0.01));
 
202
      }
 
203
#endif
 
204
 
 
205
      // get the total weight of the system
 
206
      int total_weight = 0;
 
207
 
 
208
      for (unsigned i = 0; i < per.size(); i++)
 
209
        total_weight += weight[i];
 
210
 
 
211
      // compute the expected number of objects stored per device in the absence of weighting
 
212
      float expected_objects = min(nr, num_devices_active) * num_objects;
 
213
 
 
214
      // compute each device's proportional weight
 
215
      vector<float> proportional_weights( per.size() );
 
216
 
 
217
      for (unsigned i = 0; i < per.size(); i++)
 
218
        proportional_weights[i] = (float) weight[i] / (float) total_weight;
 
219
      
 
220
 
 
221
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
222
      // create a random number generator with the device weights to use for simulating placements
 
223
      boost::random::discrete_distribution<> dist(proportional_weights);
 
224
#endif
 
225
      
 
226
      // compute the expected number of objects stored per device when a device's weight is considered
 
227
      vector<float> num_objects_expected(num_devices);
 
228
 
 
229
      for (unsigned i = 0; i < num_devices; i++)
 
230
        num_objects_expected[i] = (proportional_weights[i]*expected_objects);
 
231
 
 
232
 
 
233
      for (int currentBatch = 0; currentBatch < num_batches; currentBatch++) {
 
234
        if (currentBatch == (num_batches - 1)) {
 
235
          batch_max = max_x;
 
236
          objects_per_batch = (batch_max - batch_min + 1);
 
237
        }
 
238
 
 
239
        float batch_expected_objects = min(nr, num_devices_active) * objects_per_batch;
 
240
        vector<float> batch_num_objects_expected( per.size() );
 
241
 
 
242
        for (unsigned i = 0; i < per.size() ; i++)
 
243
          batch_num_objects_expected[i] = (proportional_weights[i]*batch_expected_objects);
 
244
 
 
245
        // create a vector to hold placement results temporarily 
 
246
        vector<int> temporary_per ( per.size() );
 
247
 
 
248
        for (int x = batch_min; x <= batch_max; x++) {
 
249
 
 
250
          // create a vector to hold the results of a CRUSH placement or RNG simulation
 
251
          vector<int> out;
 
252
          
 
253
          if (use_crush) {
 
254
            if (output_statistics)
 
255
              err << "CRUSH"; // prepend CRUSH to placement output
 
256
            crush.do_rule(r, x, out, nr, weight);
 
257
          } else {
 
258
            if (output_statistics)
 
259
              err << "RNG"; // prepend RNG to placement output to denote simulation
 
260
 
 
261
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
262
            // fill our vector with random numbers representing an OSD ID
 
263
            // one day we'll worry about duplicate entries, probably
 
264
            for (int j = 0; j < nr; j++)
 
265
              out.push_back( dist(gen) );
 
266
#endif
 
267
          }
 
268
 
 
269
 
 
270
          if (output_statistics)
 
271
            err << " rule " << r << " x " << x << " " << out << std::endl;
 
272
          for (unsigned i = 0; i < out.size(); i++) {
 
273
            per[out[i]]++;
 
274
            temporary_per[out[i]]++;
 
275
          }
 
276
 
 
277
          batchPer[currentBatch] = temporary_per;
 
278
          sizes[out.size()]++;
 
279
 
 
280
          if (output_bad_mappings && out.size() != (unsigned)nr) {
 
281
            cout << "bad mapping rule " << r << " x " << x << " num_rep " << nr << " result " << out << std::endl;
 
282
          }
 
283
        }
 
284
 
 
285
        // compute chi squared statistic for device examining the uniformity this batch of placements
 
286
        for (unsigned i = 0; i < per.size(); i++)
 
287
          deviceTestChi[i] += pow( (temporary_per[i] - batch_num_objects_expected[i]), 2) /
 
288
            batch_num_objects_expected[i];
 
289
 
 
290
        batch_min = batch_max + 1;
 
291
        batch_max = batch_min + objects_per_batch - 1;
 
292
      }
 
293
 
 
294
      for (unsigned i = 0; i < per.size(); i++)
 
295
        if (output_utilization && !output_statistics)
 
296
          err << "  device " << i
 
297
              << ":\t" << per[i]
 
298
              << std::endl;
68
299
      for (map<int,int>::iterator p = sizes.begin(); p != sizes.end(); p++)
69
 
        if (verbose>0 || p->first != nr)
70
 
          err << "rule " << r << " (" << crush.get_rule_name(r) << ") num_rep " << nr
71
 
              << " result size == " << p->first << ":\t"
72
 
              << p->second << "/" << (max_x-min_x+1) << std::endl;
73
 
    }
74
 
  }
 
300
        if ( output_statistics || p->first != nr)
 
301
          err << "rule " << r << " (" << crush.get_rule_name(r) << ") num_rep " << nr
 
302
              << " result size == " << p->first << ":\t"
 
303
              << p->second << "/" << (max_x-min_x+1) << std::endl;
 
304
 
 
305
 
 
306
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
307
      // compute our overall test chi squared statistic examining the final distribution of placements
 
308
      for (unsigned i = 0; i < per.size(); i++)
 
309
          if (num_objects_expected[i] > 0)
 
310
            test_chi_statistic += pow((num_objects_expected[i] - per[i]),2) / (float) num_objects_expected[i];
 
311
 
 
312
      int num_devices_failing_at_five_percent = 0;
 
313
      int num_devices_failing_at_one_percent = 0;
 
314
      
 
315
      for (unsigned i = 0; i < per.size(); i++) {
 
316
        if (deviceTestChi[i] > batch_chi_statistic_five_percent)
 
317
          num_devices_failing_at_five_percent++;
 
318
        if (deviceTestChi[i] > batch_chi_statistic_one_percent)
 
319
          num_devices_failing_at_one_percent++;
 
320
      }
 
321
#endif      
 
322
 
 
323
      if (output_statistics)
 
324
        for (unsigned i = 0; i < per.size(); i++) {
 
325
          if (output_utilization && num_batches > 1){
 
326
            if (num_objects_expected[i] > 0 && per[i] > 0) {
 
327
              err << "  device " << i << ":\t"
 
328
                  << "\t" << " stored " << ": " << per[i]
 
329
                  << "\t" << " expected " << ": " << num_objects_expected[i]
 
330
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
331
                  << "\t" << " X^2 " << ": " << deviceTestChi[i]
 
332
                  << "\t" << " critical (5% confidence) " << ": " << batch_chi_statistic_five_percent
 
333
                  << "\t" << " (1% confidence) " << ": " << batch_chi_statistic_one_percent
 
334
#endif
 
335
                  << std::endl;
 
336
            }
 
337
          } else if (output_utilization_all && num_batches > 1) {
 
338
            err << "  device " << i << ":\t"
 
339
                << "\t" << " stored " << ": " << per[i]
 
340
                << "\t" << " expected " << ": " << num_objects_expected[i]
 
341
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
342
                << "\t" << " X^2 " << ": " << deviceTestChi[i]
 
343
                << "\t" << " critical X^2 (5% confidence) " << ": " << batch_chi_statistic_five_percent
 
344
                << "\t" << " (1% confidence) " << ": " << batch_chi_statistic_one_percent
 
345
#endif
 
346
                << std::endl;
 
347
          }
 
348
        }
 
349
 
 
350
#ifdef HAVE_BOOST_RANDOM_DISCRETE_DISTRIBUTION
 
351
      err << " chi squared = " << test_chi_statistic
 
352
          << " (vs " << chi_statistic_five_percent << " / "
 
353
          << chi_statistic_one_percent
 
354
          << " for 5% / 1% confidence level) " << std::endl;
 
355
      if (output_utilization || output_utilization_all)
 
356
        err << " total system weight (dec) = " << (total_weight / (float) 0x10000) << std::endl;
 
357
 
 
358
      if (num_batches > 1 && output_statistics) {
 
359
        err << " " << num_devices_failing_at_five_percent << "/" << num_devices_active << " ("
 
360
            << (100.0*((float) num_devices_failing_at_five_percent / (float) num_devices_active))
 
361
            << "%) devices failed testing at 5% confidence level" << std::endl;
 
362
        err << " " << num_devices_failing_at_one_percent << "/" << num_devices_active  << " ("
 
363
            << (100.0*((float) num_devices_failing_at_one_percent / (float) num_devices_active))
 
364
            << "%) devices failed testing at 1% confidence level" << std::endl;
 
365
      }
 
366
#endif
 
367
    }
 
368
  }
 
369
 
 
370
  if (output_choose_tries) {
 
371
    __u32 *v = 0;
 
372
    int n = crush.get_choose_profile(&v);
 
373
    for (int i=0; i<n; i++) {
 
374
      cout.setf(std::ios::right);
 
375
      cout << std::setw(2)
 
376
           << i << ": " << std::setw(9) << v[i];
 
377
      cout.unsetf(std::ios::right);
 
378
      cout << std::endl;
 
379
    }
 
380
 
 
381
    crush.stop_choose_profile();
 
382
  }
 
383
 
75
384
  return 0;
76
385
}