/
histogram.py
161 lines (130 loc) · 5.66 KB
/
histogram.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
# Copyright 2017, Google LLC All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from __future__ import absolute_import, division
MIN_ACK_DEADLINE = 10
MAX_ACK_DEADLINE = 600
class Histogram(object):
"""Representation of a single histogram.
The purpose of this class is to store actual ack timing information
in order to predict how long to renew leases.
The default implementation uses the 99th percentile of previous ack
times to implicitly lease messages; however, custom
:class:`~.pubsub_v1.subscriber._consumer.Consumer` subclasses
are free to use a different formula.
The precision of data stored is to the nearest integer. Additionally,
values outside the range of ``MIN_ACK_DEADLINE <= x <= MAX_ACK_DEADLINE`` are stored
as ``MIN_ACK_DEADLINE`` or ``MAX_ACK_DEADLINE``, since these are the boundaries of
leases in the actual API.
"""
def __init__(self, data=None):
"""Instantiate the histogram.
Args:
data (Mapping[str, int]): The data strucure to be used to store
the underlying data. The default is an empty dictionary.
This can be set to a dictionary-like object if required
(for example, if a special object is needed for
concurrency reasons).
"""
# The data is stored as a dictionary, with the keys being the
# value being added and the values being the number of times that
# value was added to the dictionary.
#
# This is depending on the Python interpreter's implicit ordering
# of dictionaries, which is a bitwise sort by the key's ``hash()``
# value. Because ``hash(int i) -> i`` and all of our keys are
# positive integers (negatives would be a problem because the sort
# is bitwise), we can rely on this.
if data is None:
data = {}
self._data = data
self._len = 0
def __len__(self):
"""Return the total number of data points in this histogram.
This is cached on a separate counter (rather than computing it using
``sum([v for v in self._data.values()])``) to optimize lookup.
Returns:
int: The total number of data points in this histogram.
"""
return self._len
def __contains__(self, needle):
"""Return True if needle is present in the histogram, False otherwise.
Returns:
bool: True or False
"""
return needle in self._data
def __repr__(self):
return "<Histogram: {len} values between {min} and {max}>".format(
len=len(self), max=self.max, min=self.min
)
@property
def max(self):
"""Return the maximum value in this histogram.
If there are no values in the histogram at all, return ``MAX_ACK_DEADLINE``.
Returns:
int: The maximum value in the histogram.
"""
if len(self._data) == 0:
return MAX_ACK_DEADLINE
return next(iter(reversed(sorted(self._data.keys()))))
@property
def min(self):
"""Return the minimum value in this histogram.
If there are no values in the histogram at all, return ``MIN_ACK_DEADLINE``.
Returns:
int: The minimum value in the histogram.
"""
if len(self._data) == 0:
return MIN_ACK_DEADLINE
return next(iter(sorted(self._data.keys())))
def add(self, value):
"""Add the value to this histogram.
Args:
value (int): The value. Values outside of
``MIN_ACK_DEADLINE <= x <= MAX_ACK_DEADLINE``
will be raised to ``MIN_ACK_DEADLINE`` or reduced to
``MAX_ACK_DEADLINE``.
"""
# If the value is out of bounds, bring it in bounds.
value = int(value)
if value < MIN_ACK_DEADLINE:
value = MIN_ACK_DEADLINE
elif value > MAX_ACK_DEADLINE:
value = MAX_ACK_DEADLINE
# Add the value to the histogram's data dictionary.
self._data.setdefault(value, 0)
self._data[value] += 1
self._len += 1
def percentile(self, percent):
"""Return the value that is the Nth precentile in the histogram.
Args:
percent (Union[int, float]): The precentile being sought. The
default consumer implementations consistently use ``99``.
Returns:
int: The value corresponding to the requested percentile.
"""
# Sanity check: Any value over 100 should become 100.
if percent >= 100:
percent = 100
# Determine the actual target number.
target = len(self) - len(self) * (percent / 100)
# Iterate over the values in reverse, dropping the target by the
# number of times each value has been seen. When the target passes
# 0, return the value we are currently viewing.
for k in reversed(sorted(self._data.keys())):
target -= self._data[k]
if target < 0:
return k
# The only way to get here is if there was no data.
# In this case, just return the shortest possible deadline.
return MIN_ACK_DEADLINE