[ceph.git] / ceph / src / rocksdb / monitoring / histogram.cc

//  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
//  This source code is licensed under both the GPLv2 (found in the
//  COPYING file in the root directory) and Apache 2.0 License
//  (found in the LICENSE.Apache file in the root directory).
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#ifndef __STDC_FORMAT_MACROS
#define __STDC_FORMAT_MACROS
#endif

#include "monitoring/histogram.h"

#include <inttypes.h>
#include <cassert>
#include <math.h>
#include <stdio.h>

#include "port/port.h"
#include "util/cast_util.h"

namespace rocksdb {

HistogramBucketMapper::HistogramBucketMapper() {
  // If you change this, you also need to change
  // size of array buckets_ in HistogramImpl
  bucketValues_ = {1, 2};
  valueIndexMap_ = {{1, 0}, {2, 1}};
  double bucket_val = static_cast<double>(bucketValues_.back());
  while ((bucket_val = 1.5 * bucket_val) <= static_cast<double>(port::kMaxUint64)) {
    bucketValues_.push_back(static_cast<uint64_t>(bucket_val));
    // Extracts two most significant digits to make histogram buckets more
    // human-readable. E.g., 172 becomes 170.
    uint64_t pow_of_ten = 1;
    while (bucketValues_.back() / 10 > 10) {
      bucketValues_.back() /= 10;
      pow_of_ten *= 10;
    }
    bucketValues_.back() *= pow_of_ten;
    valueIndexMap_[bucketValues_.back()] = bucketValues_.size() - 1;
  }
  maxBucketValue_ = bucketValues_.back();
  minBucketValue_ = bucketValues_.front();
}

size_t HistogramBucketMapper::IndexForValue(const uint64_t value) const {
  if (value >= maxBucketValue_) {
    return bucketValues_.size() - 1;
  } else if ( value >= minBucketValue_ ) {
    std::map<uint64_t, uint64_t>::const_iterator lowerBound =
      valueIndexMap_.lower_bound(value);
    if (lowerBound != valueIndexMap_.end()) {
      return static_cast<size_t>(lowerBound->second);
    } else {
      return 0;
    }
  } else {
    return 0;
  }
}

namespace {
  const HistogramBucketMapper bucketMapper;
}

HistogramStat::HistogramStat()
  : num_buckets_(bucketMapper.BucketCount()) {
  assert(num_buckets_ == sizeof(buckets_) / sizeof(*buckets_));
  Clear();
}

void HistogramStat::Clear() {
  min_.store(bucketMapper.LastValue(), std::memory_order_relaxed);
  max_.store(0, std::memory_order_relaxed);
  num_.store(0, std::memory_order_relaxed);
  sum_.store(0, std::memory_order_relaxed);
  sum_squares_.store(0, std::memory_order_relaxed);
  for (unsigned int b = 0; b < num_buckets_; b++) {
    buckets_[b].store(0, std::memory_order_relaxed);
  }
};

bool HistogramStat::Empty() const { return num() == 0; }

void HistogramStat::Add(uint64_t value) {
  // This function is designed to be lock free, as it's in the critical path
  // of any operation. Each individual value is atomic and the order of updates
  // by concurrent threads is tolerable.
  const size_t index = bucketMapper.IndexForValue(value);
  assert(index < num_buckets_);
  buckets_[index].store(buckets_[index].load(std::memory_order_relaxed) + 1,
                        std::memory_order_relaxed);

  uint64_t old_min = min();
  if (value < old_min) {
    min_.store(value, std::memory_order_relaxed);
  }

  uint64_t old_max = max();
  if (value > old_max) {
    max_.store(value, std::memory_order_relaxed);
  }

  num_.store(num_.load(std::memory_order_relaxed) + 1,
             std::memory_order_relaxed);
  sum_.store(sum_.load(std::memory_order_relaxed) + value,
             std::memory_order_relaxed);
  sum_squares_.store(
      sum_squares_.load(std::memory_order_relaxed) + value * value,
      std::memory_order_relaxed);
}

void HistogramStat::Merge(const HistogramStat& other) {
  // This function needs to be performned with the outer lock acquired
  // However, atomic operation on every member is still need, since Add()
  // requires no lock and value update can still happen concurrently
  uint64_t old_min = min();
  uint64_t other_min = other.min();
  while (other_min < old_min &&
         !min_.compare_exchange_weak(old_min, other_min)) {}

  uint64_t old_max = max();
  uint64_t other_max = other.max();
  while (other_max > old_max &&
         !max_.compare_exchange_weak(old_max, other_max)) {}

  num_.fetch_add(other.num(), std::memory_order_relaxed);
  sum_.fetch_add(other.sum(), std::memory_order_relaxed);
  sum_squares_.fetch_add(other.sum_squares(), std::memory_order_relaxed);
  for (unsigned int b = 0; b < num_buckets_; b++) {
    buckets_[b].fetch_add(other.bucket_at(b), std::memory_order_relaxed);
  }
}

double HistogramStat::Median() const {
  return Percentile(50.0);
}

double HistogramStat::Percentile(double p) const {
  double threshold = num() * (p / 100.0);
  uint64_t cumulative_sum = 0;
  for (unsigned int b = 0; b < num_buckets_; b++) {
    uint64_t bucket_value = bucket_at(b);
    cumulative_sum += bucket_value;
    if (cumulative_sum >= threshold) {
      // Scale linearly within this bucket
      uint64_t left_point = (b == 0) ? 0 : bucketMapper.BucketLimit(b-1);
      uint64_t right_point = bucketMapper.BucketLimit(b);
      uint64_t left_sum = cumulative_sum - bucket_value;
      uint64_t right_sum = cumulative_sum;
      double pos = 0;
      uint64_t right_left_diff = right_sum - left_sum;
      if (right_left_diff != 0) {
       pos = (threshold - left_sum) / right_left_diff;
      }
      double r = left_point + (right_point - left_point) * pos;
      uint64_t cur_min = min();
      uint64_t cur_max = max();
      if (r < cur_min) r = static_cast<double>(cur_min);
      if (r > cur_max) r = static_cast<double>(cur_max);
      return r;
    }
  }
  return static_cast<double>(max());
}

double HistogramStat::Average() const {
  uint64_t cur_num = num();
  uint64_t cur_sum = sum();
  if (cur_num == 0) return 0;
  return static_cast<double>(cur_sum) / static_cast<double>(cur_num);
}

double HistogramStat::StandardDeviation() const {
  uint64_t cur_num = num();
  uint64_t cur_sum = sum();
  uint64_t cur_sum_squares = sum_squares();
  if (cur_num == 0) return 0;
  double variance =
      static_cast<double>(cur_sum_squares * cur_num - cur_sum * cur_sum) /
      static_cast<double>(cur_num * cur_num);
  return sqrt(variance);
}
std::string HistogramStat::ToString() const {
  uint64_t cur_num = num();
  std::string r;
  char buf[1650];
  snprintf(buf, sizeof(buf),
           "Count: %" PRIu64 " Average: %.4f  StdDev: %.2f\n",
           cur_num, Average(), StandardDeviation());
  r.append(buf);
  snprintf(buf, sizeof(buf),
           "Min: %" PRIu64 "  Median: %.4f  Max: %" PRIu64 "\n",
           (cur_num == 0 ? 0 : min()), Median(), (cur_num == 0 ? 0 : max()));
  r.append(buf);
  snprintf(buf, sizeof(buf),
           "Percentiles: "
           "P50: %.2f P75: %.2f P99: %.2f P99.9: %.2f P99.99: %.2f\n",
           Percentile(50), Percentile(75), Percentile(99), Percentile(99.9),
           Percentile(99.99));
  r.append(buf);
  r.append("------------------------------------------------------\n");
  if (cur_num == 0) return r;   // all buckets are empty
  const double mult = 100.0 / cur_num;
  uint64_t cumulative_sum = 0;
  for (unsigned int b = 0; b < num_buckets_; b++) {
    uint64_t bucket_value = bucket_at(b);
    if (bucket_value <= 0.0) continue;
    cumulative_sum += bucket_value;
    snprintf(buf, sizeof(buf),
             "%c %7" PRIu64 ", %7" PRIu64 " ] %8" PRIu64 " %7.3f%% %7.3f%% ",
             (b == 0) ? '[' : '(',
             (b == 0) ? 0 : bucketMapper.BucketLimit(b-1),  // left
              bucketMapper.BucketLimit(b),  // right
              bucket_value,                   // count
             (mult * bucket_value),           // percentage
             (mult * cumulative_sum));       // cumulative percentage
    r.append(buf);

    // Add hash marks based on percentage; 20 marks for 100%.
    size_t marks = static_cast<size_t>(mult * bucket_value / 5 + 0.5);
    r.append(marks, '#');
    r.push_back('\n');
  }
  return r;
}

void HistogramStat::Data(HistogramData * const data) const {
  assert(data);
  data->median = Median();
  data->percentile95 = Percentile(95);
  data->percentile99 = Percentile(99);
  data->max = static_cast<double>(max());
  data->average = Average();
  data->standard_deviation = StandardDeviation();
  data->count = num();
  data->sum = sum();
  data->min = static_cast<double>(min());
}

void HistogramImpl::Clear() {
  std::lock_guard<std::mutex> lock(mutex_);
  stats_.Clear();
}

bool HistogramImpl::Empty() const {
  return stats_.Empty();
}

void HistogramImpl::Add(uint64_t value) {
  stats_.Add(value);
}

void HistogramImpl::Merge(const Histogram& other) {
  if (strcmp(Name(), other.Name()) == 0) {
    Merge(
        *static_cast_with_check<const HistogramImpl, const Histogram>(&other));
  }
}

void HistogramImpl::Merge(const HistogramImpl& other) {
  std::lock_guard<std::mutex> lock(mutex_);
  stats_.Merge(other.stats_);
}

double HistogramImpl::Median() const {
  return stats_.Median();
}

double HistogramImpl::Percentile(double p) const {
  return stats_.Percentile(p);
}

double HistogramImpl::Average() const {
  return stats_.Average();
}

double HistogramImpl::StandardDeviation() const {
 return stats_.StandardDeviation();
}

std::string HistogramImpl::ToString() const {
  return stats_.ToString();
}

void HistogramImpl::Data(HistogramData * const data) const {
  stats_.Data(data);
}

} // namespace levedb
Commit	Line	Data
7c673cae	1	// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
11fdf7f2 TL	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).
7c673cae FG	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"
11fdf7f2	22	#include "util/cast_util.h"
7c673cae FG	23
	24	namespace rocksdb {
	25
11fdf7f2 TL	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;
7c673cae	43	}
11fdf7f2 TL	44	maxBucketValue_ = bucketValues_.back();
11fdf7f2 TL	45	minBucketValue_ = bucketValues_.front();
7c673cae FG	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_);
11fdf7f2 TL	93	buckets_[index].store(buckets_[index].load(std::memory_order_relaxed) + 1,
11fdf7f2 TL	94	std::memory_order_relaxed);
7c673cae FG	95
7c673cae FG	96	uint64_t old_min = min();
11fdf7f2 TL	97	if (value < old_min) {
	98	min_.store(value, std::memory_order_relaxed);
	99	}
7c673cae FG	100
7c673cae FG	101	uint64_t old_max = max();
11fdf7f2 TL	102	if (value > old_max) {
	103	max_.store(value, std::memory_order_relaxed);
	104	}
7c673cae	105
11fdf7f2 TL	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);
7c673cae FG	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");
11fdf7f2	205	if (cur_num == 0) return r; // all buckets are empty
7c673cae FG	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),
11fdf7f2 TL	213	"%c %7" PRIu64 ", %7" PRIu64 " ] %8" PRIu64 " %7.3f%% %7.3f%% ",
11fdf7f2 TL	214	(b == 0) ? '[' : '(',
7c673cae FG	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();
11fdf7f2 TL	238	data->count = num();
11fdf7f2 TL	239	data->sum = sum();
494da23a	240	data->min = static_cast<double>(min());
7c673cae FG	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) {
11fdf7f2 TL	258	Merge(
11fdf7f2 TL	259	*static_cast_with_check<const HistogramImpl, const Histogram>(&other));
7c673cae FG	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