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