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 #pragma once 11 #include "rocksdb/statistics.h" 12 13 #include <cassert> 14 #include <string> 15 #include <vector> 16 #include <map> 17 #include <mutex> 18 19 namespace ROCKSDB_NAMESPACE { 20 21 class HistogramBucketMapper { 22 public: 23 24 HistogramBucketMapper(); 25 26 // converts a value to the bucket index. 27 size_t IndexForValue(uint64_t value) const; 28 // number of buckets required. 29 BucketCount()30 size_t BucketCount() const { 31 return bucketValues_.size(); 32 } 33 LastValue()34 uint64_t LastValue() const { 35 return maxBucketValue_; 36 } 37 FirstValue()38 uint64_t FirstValue() const { 39 return minBucketValue_; 40 } 41 BucketLimit(const size_t bucketNumber)42 uint64_t BucketLimit(const size_t bucketNumber) const { 43 assert(bucketNumber < BucketCount()); 44 return bucketValues_[bucketNumber]; 45 } 46 47 private: 48 std::vector<uint64_t> bucketValues_; 49 uint64_t maxBucketValue_; 50 uint64_t minBucketValue_; 51 std::map<uint64_t, uint64_t> valueIndexMap_; 52 }; 53 54 struct HistogramStat { 55 HistogramStat(); ~HistogramStatHistogramStat56 ~HistogramStat() {} 57 58 HistogramStat(const HistogramStat&) = delete; 59 HistogramStat& operator=(const HistogramStat&) = delete; 60 61 void Clear(); 62 bool Empty() const; 63 void Add(uint64_t value); 64 void Merge(const HistogramStat& other); 65 minHistogramStat66 inline uint64_t min() const { return min_.load(std::memory_order_relaxed); } maxHistogramStat67 inline uint64_t max() const { return max_.load(std::memory_order_relaxed); } numHistogramStat68 inline uint64_t num() const { return num_.load(std::memory_order_relaxed); } sumHistogramStat69 inline uint64_t sum() const { return sum_.load(std::memory_order_relaxed); } sum_squaresHistogramStat70 inline uint64_t sum_squares() const { 71 return sum_squares_.load(std::memory_order_relaxed); 72 } bucket_atHistogramStat73 inline uint64_t bucket_at(size_t b) const { 74 return buckets_[b].load(std::memory_order_relaxed); 75 } 76 77 double Median() const; 78 double Percentile(double p) const; 79 double Average() const; 80 double StandardDeviation() const; 81 void Data(HistogramData* const data) const; 82 std::string ToString() const; 83 84 // To be able to use HistogramStat as thread local variable, it 85 // cannot have dynamic allocated member. That's why we're 86 // using manually values from BucketMapper 87 std::atomic_uint_fast64_t min_; 88 std::atomic_uint_fast64_t max_; 89 std::atomic_uint_fast64_t num_; 90 std::atomic_uint_fast64_t sum_; 91 std::atomic_uint_fast64_t sum_squares_; 92 std::atomic_uint_fast64_t buckets_[109]; // 109==BucketMapper::BucketCount() 93 const uint64_t num_buckets_; 94 }; 95 96 class Histogram { 97 public: Histogram()98 Histogram() {} ~Histogram()99 virtual ~Histogram() {}; 100 101 virtual void Clear() = 0; 102 virtual bool Empty() const = 0; 103 virtual void Add(uint64_t value) = 0; 104 virtual void Merge(const Histogram&) = 0; 105 106 virtual std::string ToString() const = 0; 107 virtual const char* Name() const = 0; 108 virtual uint64_t min() const = 0; 109 virtual uint64_t max() const = 0; 110 virtual uint64_t num() const = 0; 111 virtual double Median() const = 0; 112 virtual double Percentile(double p) const = 0; 113 virtual double Average() const = 0; 114 virtual double StandardDeviation() const = 0; 115 virtual void Data(HistogramData* const data) const = 0; 116 }; 117 118 class HistogramImpl : public Histogram { 119 public: HistogramImpl()120 HistogramImpl() { Clear(); } 121 122 HistogramImpl(const HistogramImpl&) = delete; 123 HistogramImpl& operator=(const HistogramImpl&) = delete; 124 125 virtual void Clear() override; 126 virtual bool Empty() const override; 127 virtual void Add(uint64_t value) override; 128 virtual void Merge(const Histogram& other) override; 129 void Merge(const HistogramImpl& other); 130 131 virtual std::string ToString() const override; Name()132 virtual const char* Name() const override { return "HistogramImpl"; } min()133 virtual uint64_t min() const override { return stats_.min(); } max()134 virtual uint64_t max() const override { return stats_.max(); } num()135 virtual uint64_t num() const override { return stats_.num(); } 136 virtual double Median() const override; 137 virtual double Percentile(double p) const override; 138 virtual double Average() const override; 139 virtual double StandardDeviation() const override; 140 virtual void Data(HistogramData* const data) const override; 141 ~HistogramImpl()142 virtual ~HistogramImpl() {} 143 144 private: 145 HistogramStat stats_; 146 std::mutex mutex_; 147 }; 148 149 } // namespace ROCKSDB_NAMESPACE 150