ceph/src/rocksdb/monitoring/histogram.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #ifndef __STDC_FORMAT_MACROS
  11 #define __STDC_FORMAT_MACROS
  12 #endif
  13
  14 #include "monitoring/histogram.h"
  15
  16 #include <inttypes.h>
  17 #include <cassert>
  18 #include <math.h>
  19 #include <stdio.h>
  20
  21 #include "port/port.h"
  22 #include "util/cast_util.h"
  23
  24 namespace rocksdb {
  25
  26 HistogramBucketMapper::HistogramBucketMapper() {
  27   // If you change this, you also need to change
  28   // size of array buckets_ in HistogramImpl
  29   bucketValues_ = {1, 2};
  30   valueIndexMap_ = {{1, 0}, {2, 1}};
  31   double bucket_val = static_cast<double>(bucketValues_.back());
  32   while ((bucket_val = 1.5 * bucket_val) <= static_cast<double>(port::kMaxUint64)) {
  33     bucketValues_.push_back(static_cast<uint64_t>(bucket_val));
  34     // Extracts two most significant digits to make histogram buckets more
  35     // human-readable. E.g., 172 becomes 170.
  36     uint64_t pow_of_ten = 1;
  37     while (bucketValues_.back() / 10 > 10) {
  38       bucketValues_.back() /= 10;
  39       pow_of_ten *= 10;
  40     }
  41     bucketValues_.back() *= pow_of_ten;
  42     valueIndexMap_[bucketValues_.back()] = bucketValues_.size() - 1;
  43   }
  44   maxBucketValue_ = bucketValues_.back();
  45   minBucketValue_ = bucketValues_.front();
  46 }
  47
  48 size_t HistogramBucketMapper::IndexForValue(const uint64_t value) const {
  49   if (value >= maxBucketValue_) {
  50     return bucketValues_.size() - 1;
  51   } else if ( value >= minBucketValue_ ) {
  52     std::map<uint64_t, uint64_t>::const_iterator lowerBound =
  53       valueIndexMap_.lower_bound(value);
  54     if (lowerBound != valueIndexMap_.end()) {
  55       return static_cast<size_t>(lowerBound->second);
  56     } else {
  57       return 0;
  58     }
  59   } else {
  60     return 0;
  61   }
  62 }
  63
  64 namespace {
  65   const HistogramBucketMapper bucketMapper;
  66 }
  67
  68 HistogramStat::HistogramStat()
  69   : num_buckets_(bucketMapper.BucketCount()) {
  70   assert(num_buckets_ == sizeof(buckets_) / sizeof(*buckets_));
  71   Clear();
  72 }
  73
  74 void HistogramStat::Clear() {
  75   min_.store(bucketMapper.LastValue(), std::memory_order_relaxed);
  76   max_.store(0, std::memory_order_relaxed);
  77   num_.store(0, std::memory_order_relaxed);
  78   sum_.store(0, std::memory_order_relaxed);
  79   sum_squares_.store(0, std::memory_order_relaxed);
  80   for (unsigned int b = 0; b < num_buckets_; b++) {
  81     buckets_[b].store(0, std::memory_order_relaxed);
  82   }
  83 };
  84
  85 bool HistogramStat::Empty() const { return num() == 0; }
  86
  87 void HistogramStat::Add(uint64_t value) {
  88   // This function is designed to be lock free, as it's in the critical path
  89   // of any operation. Each individual value is atomic and the order of updates
  90   // by concurrent threads is tolerable.
  91   const size_t index = bucketMapper.IndexForValue(value);
  92   assert(index < num_buckets_);
  93   buckets_[index].store(buckets_[index].load(std::memory_order_relaxed) + 1,
  94                         std::memory_order_relaxed);
  95
  96   uint64_t old_min = min();
  97   if (value < old_min) {
  98     min_.store(value, std::memory_order_relaxed);
  99   }
 100
 101   uint64_t old_max = max();
 102   if (value > old_max) {
 103     max_.store(value, std::memory_order_relaxed);
 104   }
 105
 106   num_.store(num_.load(std::memory_order_relaxed) + 1,
 107              std::memory_order_relaxed);
 108   sum_.store(sum_.load(std::memory_order_relaxed) + value,
 109              std::memory_order_relaxed);
 110   sum_squares_.store(
 111       sum_squares_.load(std::memory_order_relaxed) + value * value,
 112       std::memory_order_relaxed);
 113 }
 114
 115 void HistogramStat::Merge(const HistogramStat& other) {
 116   // This function needs to be performned with the outer lock acquired
 117   // However, atomic operation on every member is still need, since Add()
 118   // requires no lock and value update can still happen concurrently
 119   uint64_t old_min = min();
 120   uint64_t other_min = other.min();
 121   while (other_min < old_min &&
 122          !min_.compare_exchange_weak(old_min, other_min)) {}
 123
 124   uint64_t old_max = max();
 125   uint64_t other_max = other.max();
 126   while (other_max > old_max &&
 127          !max_.compare_exchange_weak(old_max, other_max)) {}
 128
 129   num_.fetch_add(other.num(), std::memory_order_relaxed);
 130   sum_.fetch_add(other.sum(), std::memory_order_relaxed);
 131   sum_squares_.fetch_add(other.sum_squares(), std::memory_order_relaxed);
 132   for (unsigned int b = 0; b < num_buckets_; b++) {
 133     buckets_[b].fetch_add(other.bucket_at(b), std::memory_order_relaxed);
 134   }
 135 }
 136
 137 double HistogramStat::Median() const {
 138   return Percentile(50.0);
 139 }
 140
 141 double HistogramStat::Percentile(double p) const {
 142   double threshold = num() * (p / 100.0);
 143   uint64_t cumulative_sum = 0;
 144   for (unsigned int b = 0; b < num_buckets_; b++) {
 145     uint64_t bucket_value = bucket_at(b);
 146     cumulative_sum += bucket_value;
 147     if (cumulative_sum >= threshold) {
 148       // Scale linearly within this bucket
 149       uint64_t left_point = (b == 0) ? 0 : bucketMapper.BucketLimit(b-1);
 150       uint64_t right_point = bucketMapper.BucketLimit(b);
 151       uint64_t left_sum = cumulative_sum - bucket_value;
 152       uint64_t right_sum = cumulative_sum;
 153       double pos = 0;
 154       uint64_t right_left_diff = right_sum - left_sum;
 155       if (right_left_diff != 0) {
 156        pos = (threshold - left_sum) / right_left_diff;
 157       }
 158       double r = left_point + (right_point - left_point) * pos;
 159       uint64_t cur_min = min();
 160       uint64_t cur_max = max();
 161       if (r < cur_min) r = static_cast<double>(cur_min);
 162       if (r > cur_max) r = static_cast<double>(cur_max);
 163       return r;
 164     }
 165   }
 166   return static_cast<double>(max());
 167 }
 168
 169 double HistogramStat::Average() const {
 170   uint64_t cur_num = num();
 171   uint64_t cur_sum = sum();
 172   if (cur_num == 0) return 0;
 173   return static_cast<double>(cur_sum) / static_cast<double>(cur_num);
 174 }
 175
 176 double HistogramStat::StandardDeviation() const {
 177   uint64_t cur_num = num();
 178   uint64_t cur_sum = sum();
 179   uint64_t cur_sum_squares = sum_squares();
 180   if (cur_num == 0) return 0;
 181   double variance =
 182       static_cast<double>(cur_sum_squares * cur_num - cur_sum * cur_sum) /
 183       static_cast<double>(cur_num * cur_num);
 184   return sqrt(variance);
 185 }
 186 std::string HistogramStat::ToString() const {
 187   uint64_t cur_num = num();
 188   std::string r;
 189   char buf[1650];
 190   snprintf(buf, sizeof(buf),
 191            "Count: %" PRIu64 " Average: %.4f  StdDev: %.2f\n",
 192            cur_num, Average(), StandardDeviation());
 193   r.append(buf);
 194   snprintf(buf, sizeof(buf),
 195            "Min: %" PRIu64 "  Median: %.4f  Max: %" PRIu64 "\n",
 196            (cur_num == 0 ? 0 : min()), Median(), (cur_num == 0 ? 0 : max()));
 197   r.append(buf);
 198   snprintf(buf, sizeof(buf),
 199            "Percentiles: "
 200            "P50: %.2f P75: %.2f P99: %.2f P99.9: %.2f P99.99: %.2f\n",
 201            Percentile(50), Percentile(75), Percentile(99), Percentile(99.9),
 202            Percentile(99.99));
 203   r.append(buf);
 204   r.append("------------------------------------------------------\n");
 205   if (cur_num == 0) return r;   // all buckets are empty
 206   const double mult = 100.0 / cur_num;
 207   uint64_t cumulative_sum = 0;
 208   for (unsigned int b = 0; b < num_buckets_; b++) {
 209     uint64_t bucket_value = bucket_at(b);
 210     if (bucket_value <= 0.0) continue;
 211     cumulative_sum += bucket_value;
 212     snprintf(buf, sizeof(buf),
 213              "%c %7" PRIu64 ", %7" PRIu64 " ] %8" PRIu64 " %7.3f%% %7.3f%% ",
 214              (b == 0) ? '[' : '(',
 215              (b == 0) ? 0 : bucketMapper.BucketLimit(b-1),  // left
 216               bucketMapper.BucketLimit(b),  // right
 217               bucket_value,                   // count
 218              (mult * bucket_value),           // percentage
 219              (mult * cumulative_sum));       // cumulative percentage
 220     r.append(buf);
 221
 222     // Add hash marks based on percentage; 20 marks for 100%.
 223     size_t marks = static_cast<size_t>(mult * bucket_value / 5 + 0.5);
 224     r.append(marks, '#');
 225     r.push_back('\n');
 226   }
 227   return r;
 228 }
 229
 230 void HistogramStat::Data(HistogramData * const data) const {
 231   assert(data);
 232   data->median = Median();
 233   data->percentile95 = Percentile(95);
 234   data->percentile99 = Percentile(99);
 235   data->max = static_cast<double>(max());
 236   data->average = Average();
 237   data->standard_deviation = StandardDeviation();
 238   data->count = num();
 239   data->sum = sum();
 240   data->min = static_cast<double>(min());
 241 }
 242
 243 void HistogramImpl::Clear() {
 244   std::lock_guard<std::mutex> lock(mutex_);
 245   stats_.Clear();
 246 }
 247
 248 bool HistogramImpl::Empty() const {
 249   return stats_.Empty();
 250 }
 251
 252 void HistogramImpl::Add(uint64_t value) {
 253   stats_.Add(value);
 254 }
 255
 256 void HistogramImpl::Merge(const Histogram& other) {
 257   if (strcmp(Name(), other.Name()) == 0) {
 258     Merge(
 259         *static_cast_with_check<const HistogramImpl, const Histogram>(&other));
 260   }
 261 }
 262
 263 void HistogramImpl::Merge(const HistogramImpl& other) {
 264   std::lock_guard<std::mutex> lock(mutex_);
 265   stats_.Merge(other.stats_);
 266 }
 267
 268 double HistogramImpl::Median() const {
 269   return stats_.Median();
 270 }
 271
 272 double HistogramImpl::Percentile(double p) const {
 273   return stats_.Percentile(p);
 274 }
 275
 276 double HistogramImpl::Average() const {
 277   return stats_.Average();
 278 }
 279
 280 double HistogramImpl::StandardDeviation() const {
 281  return stats_.StandardDeviation();
 282 }
 283
 284 std::string HistogramImpl::ToString() const {
 285   return stats_.ToString();
 286 }
 287
 288 void HistogramImpl::Data(HistogramData * const data) const {
 289   stats_.Data(data);
 290 }
 291
 292 } // namespace levedb