AnomalyTracker.h revision 857aaa520804d846a050e1eeb85d82977c983666
1e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac/* 2e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * Copyright (C) 2017 The Android Open Source Project 3e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * 4e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * Licensed under the Apache License, Version 2.0 (the "License"); 5e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * you may not use this file except in compliance with the License. 6e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * You may obtain a copy of the License at 7e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * 8e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * http://www.apache.org/licenses/LICENSE-2.0 9e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * 10e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * Unless required by applicable law or agreed to in writing, software 11e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * distributed under the License is distributed on an "AS IS" BASIS, 12e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * See the License for the specific language governing permissions and 14e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * limitations under the License. 15e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac */ 16e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 17e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#pragma once 18e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 19e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include <gtest/gtest_prod.h> 20e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include "AnomalyMonitor.h" 218f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz#include "config/ConfigKey.h" 22e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include "frameworks/base/cmds/statsd/src/statsd_config.pb.h" // Alert 23e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include "stats_util.h" // HashableDimensionKey and DimToValMap 24e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 25e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include <memory> // unique_ptr 26e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include <stdlib.h> 27e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include <utils/RefBase.h> 28e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 29e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macnamespace android { 30e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macnamespace os { 31e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macnamespace statsd { 32e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 33e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macusing std::unordered_map; 34e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macusing std::shared_ptr; 35e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 36cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz// Does NOT allow negative values. 37e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macclass AnomalyTracker : public virtual RefBase { 38e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macpublic: 398f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz AnomalyTracker(const Alert& alert, const ConfigKey& configKey); 40e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 41e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac virtual ~AnomalyTracker(); 42e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 43e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Adds a bucket. 44e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Bucket index starts from 0. 45e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac void addPastBucket(std::shared_ptr<DimToValMap> bucketValues, const int64_t& bucketNum); 46e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac void addPastBucket(const HashableDimensionKey& key, const int64_t& bucketValue, 47e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const int64_t& bucketNum); 48e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 49e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Returns true if detected anomaly for the existing buckets on one or more dimension keys. 50e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac bool detectAnomaly(const int64_t& currBucketNum, const DimToValMap& currentBucket); 51e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac bool detectAnomaly(const int64_t& currBucketNum, const HashableDimensionKey& key, 52e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const int64_t& currentBucketValue); 53e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 54e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Informs incidentd about the detected alert. 55cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz void declareAnomaly(const uint64_t& timestampNs); 56e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 57e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Detects the alert and informs the incidentd when applicable. 58cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz void detectAndDeclareAnomaly(const uint64_t& timestampNs, const int64_t& currBucketNum, 59e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const DimToValMap& currentBucket); 60cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz void detectAndDeclareAnomaly(const uint64_t& timestampNs, const int64_t& currBucketNum, 61e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const HashableDimensionKey& key, 62e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const int64_t& currentBucketValue); 63e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 64857aaa520804d846a050e1eeb85d82977c983666Bookatz // Init the AnomalyMonitor which is shared across anomaly trackers. 65857aaa520804d846a050e1eeb85d82977c983666Bookatz virtual void setAnomalyMonitor(const sp<AnomalyMonitor>& anomalyMonitor) { 66857aaa520804d846a050e1eeb85d82977c983666Bookatz return; // Base AnomalyTracker class has no need for the AnomalyMonitor. 67e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 68e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 69e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Helper function to return the sum value of past buckets at given dimension. 70e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac int64_t getSumOverPastBuckets(const HashableDimensionKey& key) const; 71e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 72e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Helper function to return the value for a past bucket. 73e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac int64_t getPastBucketValue(const HashableDimensionKey& key, const int64_t& bucketNum) const; 74e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 75e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Returns the anomaly threshold. 76e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac inline int64_t getAnomalyThreshold() const { 77e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac return mAlert.trigger_if_sum_gt(); 78e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 79e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 80857aaa520804d846a050e1eeb85d82977c983666Bookatz // Helper function to return the timestamp of the last detected anomaly. 81857aaa520804d846a050e1eeb85d82977c983666Bookatz inline int64_t getLastAnomalyTimestampNs() const { 82857aaa520804d846a050e1eeb85d82977c983666Bookatz return mLastAnomalyTimestampNs; 83e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 84e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 85cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz inline int getNumOfPastBuckets() const { 86cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz return mNumOfPastBuckets; 87e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 88e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 89cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // Declares an anomaly for each alarm in firedAlarms that belongs to this AnomalyTracker, 90cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // and removes it from firedAlarms. Does NOT remove the alarm from the AnomalyMonitor. 91857aaa520804d846a050e1eeb85d82977c983666Bookatz virtual void informAlarmsFired(const uint64_t& timestampNs, 92857aaa520804d846a050e1eeb85d82977c983666Bookatz unordered_set<sp<const AnomalyAlarm>, SpHash<AnomalyAlarm>>& firedAlarms) { 93857aaa520804d846a050e1eeb85d82977c983666Bookatz return; // The base AnomalyTracker class doesn't have alarms. 94857aaa520804d846a050e1eeb85d82977c983666Bookatz } 95cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz 96e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macprotected: 97e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // statsd_config.proto Alert message that defines this tracker. 98e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const Alert mAlert; 99e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1008f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz // A reference to the Alert's config key. 1018f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz const ConfigKey& mConfigKey; 1028f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz 103cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // Number of past buckets. One less than the total number of buckets needed 104cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // for the anomaly detection (since the current bucket is not in the past). 105cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz int mNumOfPastBuckets; 106e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 107e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // The exisiting bucket list. 108e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac std::vector<shared_ptr<DimToValMap>> mPastBuckets; 109e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 110e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Sum over all existing buckets cached in mPastBuckets. 111e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac DimToValMap mSumOverPastBuckets; 112e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 113e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // The bucket number of the last added bucket. 114e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac int64_t mMostRecentBucketNum = -1; 115e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 116e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // The timestamp when the last anomaly was declared. 117857aaa520804d846a050e1eeb85d82977c983666Bookatz int64_t mLastAnomalyTimestampNs = -1; 118857aaa520804d846a050e1eeb85d82977c983666Bookatz 119857aaa520804d846a050e1eeb85d82977c983666Bookatz void flushPastBuckets(const int64_t& currBucketNum); 120e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 121e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Add the information in the given bucket to mSumOverPastBuckets. 122e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac void addBucketToSum(const shared_ptr<DimToValMap>& bucket); 123e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 124e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Subtract the information in the given bucket from mSumOverPastBuckets 125e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // and remove any items with value 0. 126e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac void subtractBucketFromSum(const shared_ptr<DimToValMap>& bucket); 127e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 128857aaa520804d846a050e1eeb85d82977c983666Bookatz bool isInRefractoryPeriod(const uint64_t& timestampNs) const; 129cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz 130e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Calculates the corresponding bucket index within the circular array. 131e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac size_t index(int64_t bucketNum) const; 132e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 133cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // Resets all bucket data. For use when all the data gets stale. 134857aaa520804d846a050e1eeb85d82977c983666Bookatz virtual void resetStorage(); 135e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 136d1fd2425f744ab46a87dec4ed4d3f0680e819dbcBookatz // Informs the incident service that an anomaly has occurred. 137d1fd2425f744ab46a87dec4ed4d3f0680e819dbcBookatz void informIncidentd(); 138d1fd2425f744ab46a87dec4ed4d3f0680e819dbcBookatz 139e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(AnomalyTrackerTest, TestConsecutiveBuckets); 140e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(AnomalyTrackerTest, TestSparseBuckets); 141e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(GaugeMetricProducerTest, TestAnomalyDetection); 142e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(CountMetricProducerTest, TestAnomalyDetection); 143e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac}; 144e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 145e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac} // namespace statsd 146e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac} // namespace os 147e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac} // namespace android 148