Method for detecting abnormal load in cloud computing oriented online service

• US 10,581,961 B2
• Filed: 10/17/2017
• Issued: 03/03/2020
• Est. Priority Date: 07/16/2015
• Status: Active Grant

• Current Assignee: Tsinghua University
• Original Assignee: Tsinghua University
• Inventors: Zhou, Yuezhi, Liu, Jinzhao, Zhang, Di, Zhang, Yaoxue
• Primary Examiner(s): Chea, Philip J
• Assistant Examiner(s): Solomon, Ruth
• Application Number:
  US15/786,426
• Publication Number:
  US 20180041573A1
• Time in Patent Office: 868 Days
• CPC Class Codes: G06F 11/2066 Optimisation of the communication load
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

Disclosed are a method and device for detecting an abnormal load. The method includes: collecting data of each load item in all hosts; pre-processing to obtain a second sequence corresponding to each load item; obtaining a coefficient matrix and a detail vector; computing a weighted mean of abnormal load probabilities of all the coefficient vectors, to obtain an abnormal load probability of each second sequence; comparing the abnormal load probability with a confidence interval, and judging whether there is an abnormal load, and judging that there is no abnormity in the corresponding second sequence if the abnormal load probability of each second sequence is in the confidence interval; judging whether there is an abnormal load according to data of all load items and the abnormal load probability of each second sequence; and finding a bearing host that has the abnormal load from the current online service.

Claims

1. A method for detecting an abnormal load in a cloud computing oriented online service comprising:

step 1, collecting data of each load item in all hosts that bears a current online service with a fixed sampling period;

step 2, pre-processing the data of each load item in all hosts to obtain a first sequence with a fixed time interval, and merging first sequences of all hosts for each load item to obtain a second sequence corresponding to each load item;

step 3, obtaining a coefficient matrix and a detail vector by performing a discrete wavelet transform to each second sequence, and computing an abnormal load probability for each coefficient vector of the coefficient matrix by performing a statistical analysis to each coefficient vector of the coefficient matrix;

step 4, computing a weighted mean of the abnormal load probabilities of all the coefficient vectors of the coefficient matrix with a weighted formula, to obtain an abnormal load probability of each second sequence;

step 5, comparing the abnormal load probability of each second sequence with a confidence interval given by a confidence function, and judging whether there is an abnormal load, and judging that there is no abnormity in the corresponding second sequence if the abnormal load probability of each second sequence is in the confidence interval;

step 6, judging whether there is an abnormal load in the current online service according to data of all load items of the current online service and the abnormal load probability of each second sequence of the current online service, and comprising steps of;

step 6.1, obtaining second sequences of all load items that have the abnormity in the current online service according to a judging result of step 5; and

step 6.2, for each load item that has the abnormity, recording a time point corresponding to a last point in the second sequence of each load item as an occurring time point of the abnormal load, and storing the recorded items into the online service data base; and

step 7, finding a bearing host that has the abnormal load from the current online service by using K-means clustering algorithm;

wherein step 3 comprises;

step 3.1, performing a one-dimensional discrete wavelet transform to the second sequence to obtain the coefficient matrix cA and the detail vector cD according to following formula;

cA,cD=DWT([S₁^x,S₂^x, . . . ,S_n^x],L,‘

haar’

),

where Haar wavelet is taken as wavelet basis of the one-dimensional discrete wavelet transform, and transform level L is set according to a difference between the fixed time interval T₁ and an abnormal detection period T_s, wherein S₁^x, S₂^x, . . . , S_n^x represents the second sequence;

step 3.2, filtering coefficient vectors out from the coefficient matrix, performing a statistical analysis based on a normal distribution to each coefficient vector, and computing the abnormal load probability of the second sequence, wherein a mean value of the normal distribution is 0, a variance of the normal distribution is an estimated variance of values of the load item in past time of T_s×

m, m is an experience value, the abnormal load probability of the second sequence is a largest value of cumulative distribution probabilities of values of the load item at each time point in T_s, and computed according to following formula of;

2. The method according to claim 1, wherein step 2 further comprises:

step 2.1, if data at a time point of a load item in a host is null, interpolating a value of the data at the time point of the load item in the host according to a mean algorithm.

3. The method according to claim 1, wherein step 5 comprises:

step 5.1, obtaining the second sequence in the current online service, and obtaining the abnormal load probability of the second sequence;

step 5.2, computing a standard deviation of the second sequence, and obtaining the confidence interval by taking the standard deviation as a parameter of the confidence function, wherein the confidence function is defined as following;

4. The method according to claim 1, wherein step 7 comprises:

step 7.1, obtaining data with an abnormal state in all load items from the current online service;

step 7.2, judging whether there is an abnormity in the current online service, if yes, ending the step, otherwise executing step 7.3;

step 7.3, obtaining abnormal load data of all bearing hosts that have an abnormity from the current online service, and normalizing the abnormal load data;

step 7.4, taking the normalized abnormal load data of each bearing host as a vector, and clustering the vectors corresponding to all the bearing hosts with K-means clustering algorithm and Euclidean distance;

step 7.5, comparing standard deviations of two of the clusters, taking a cluster that has a larger standard deviation as an abnormal cluster, wherein there is an abnormity load in all hosts bearing the online service in the abnormal cluster, and the standard deviation is computed as follows;

for each cluster, obtaining standard deviations of the second sequences of all load items in the cluster, computing a mean value of the obtained standard deviations, and taking the mean value as the standard deviation of the cluster;

step 7.6, if there is an online service not processed, executing step 1, otherwise ending the step.

5. The method according to claim 1, wherein the data of each load item is denoted as (d₁^x, d₂^x, . . . , d_i^x, . . . , d_n^x), where i=1, 2, . . . , n, n is a positive integer, x represents the load item, the load item comprises a Central Processing Unit CPU usage rate, a memory usage rate, a disk I/O usage rate or a network I/O usage rate, d_i^x is a value of the load item x at an i^th time point.

6. The method according to claim 5, wherein pre-processing the data of each load item in all hosts to obtain a first sequence with a fixed time interval comprises:

obtaining an element of the first sequence by a formula of

s_i^x=average(d<sub>(i−

1)×

k+1</sub>^x,d<sub>(i−

1)×

k+2</sub>^x, . . . ,d<sub>(i−

1)×

k+k</sub>^x)

where the first sequence corresponding to each load item is denoted as (s₁^x, s₂^x, . . . , s_i^x, . . . , s_n^x), s_i^x represents the element of the first sequence, k is a ratio of the fixed time interval to the fixed sampling period.

7. The method according to claim 6, wherein merging first sequences of all hosts for each load item to obtain a second sequence corresponding to each load item comprises:

obtaining an element of the second sequence by a formula of

8. The method according to claim 5, wherein the weighted formula is:

9. A device for detecting an abnormal load in a cloud computing oriented online service comprising:

a processor; and

a memory for storing instructions executable by the processor,

wherein the processor is configured to;

collect data of each load item in all hosts that bears a current online service with a fixed sampling period;

pre-process the data of each load item in all hosts to obtain a first sequence with a fixed time interval, and merge first sequences of all hosts for each load item to obtain a second sequence corresponding to each load item;

obtain a coefficient matrix and a detail vector by performing a discrete wavelet transform to each second sequence, and compute an abnormal load probability for each coefficient vector of the coefficient matrix by performing a statistical analysis to each coefficient vector of the coefficient matrix;

compute a weighted mean of the abnormal load probabilities of all the coefficient vectors of the coefficient matrix with a weighted formula, to obtain an abnormal load probability of each second sequence;

compare the abnormal load probability of each second sequence with a confidence interval given by a confidence function, and judge whether there is an abnormal load, and judge that there is no abnormity in the corresponding second sequence if the abnormal load probability of each second sequence is in the confidence interval;

obtain second sequences of all load items that have the abnormity in the current online service according to a judging result of whether there is an abnormal load, and judging that there is no abnormity in the corresponding second sequence if the abnormal load probability of each second sequence is in the confidence interval; and

for each load item that has the abnormity, record a time point corresponding to a last point in the second sequence of each load item as an occurring time point of the abnormal load, and store the recorded items into the online service data base; and

find a bearing host that has the abnormal load from the current online service by using K-means clustering algorithm;

perform a one-dimensional discrete wavelet transform to the second sequence to obtain the coefficient matrix cA and the detail vector cD according to following formula;

cA,cD=DWT([S₁^x,S₂^x, . . . ,S_n^x],L,‘

haar’

),

where Haar wavelet is taken as wavelet basis of the one-dimensional discrete wavelet transform, and transform level L is set according to a difference between the fixed time interval T₁ and an abnormal detection period T_s, wherein S₁^x, S₂^x, . . . , S_n^x represents the second sequence;

filter coefficient vectors out from the coefficient matrix, perform a statistical analysis based on a normal distribution to each coefficient vector, and compute the abnormal load probability of the second sequence, wherein a mean value of the normal distribution is 0, a variance of the normal distribution is an estimated variance of values of the load item in past time of T_s×

m, m is an experience value, the abnormal load probability of the second sequence is a largest value of cumulative distribution probabilities of values of the load item at each time point in T_s, and computed according to following formula of;

10. A non-transitory computer-readable storage medium having stored therein instructions that, when executed by a processor of an intelligent terminal, causes the intelligent terminal to perform a method for loading a theme application, the method comprising:

step 1, collecting data of each load item in all hosts that bears a current online service with a fixed sampling period;

step 2, pre-processing the data of each load item in all hosts to obtain a first sequence with a fixed time interval, and merging first sequences of all hosts for each load item to obtain a second sequence corresponding to each load item;

step 3, obtaining a coefficient matrix and a detail vector by performing a discrete wavelet transform to each second sequence, and computing an abnormal load probability for each coefficient vector of the coefficient matrix by performing a statistical analysis to each coefficient vector of the coefficient matrix;

step 4, computing a weighted mean of the abnormal load probabilities of all the coefficient vectors of the coefficient matrix with a weighted formula, to obtain an abnormal load probability of each second sequence;

step 5, comparing the abnormal load probability of each second sequence with a confidence interval given by a confidence function, and judging whether there is an abnormal load, and judging that there is no abnormity in the corresponding second sequence if the abnormal load probability of each second sequence is in the confidence interval;

step 6.1, obtaining second sequences of all load items that have the abnormity in the current online service according to a judging result of step 5; and

step 6.2, for each load item that has the abnormity, recording a time point corresponding to a last point in the second sequence of each load item as an occurring time point of the abnormal load, and storing the recorded items into the online service data base; and

step 7, finding a bearing host that has the abnormal load from the current online service by using K-means clustering algorithm;

wherein step 3 comprises;

step 3.1, performing a one-dimensional discrete wavelet transform to the second sequence to obtain the coefficient matrix cA and the detail vector cD according to following formula;

cA,cD=DWT([S₁^x,S₂^x, . . . ,S_n^x],L,‘

haar’

),

where Haar wavelet is taken as wavelet basis of the one-dimensional discrete wavelet transform, and transform level L is set according to a difference between the fixed time interval T₁ and an abnormal detection period T_s, wherein S₁^x, S₂^x, . . . , S_n^x represents the second sequence;

step 3.2, filtering coefficient vectors out from the coefficient matrix, performing a statistical analysis based on a normal distribution to each coefficient vector, and computing the abnormal load probability of the second sequence, wherein a mean value of the normal distribution is 0, a variance of the normal distribution is an estimated variance of values of the load item in past time of T_s×

m, m is an experience value, the abnormal load probability of the second sequence is a largest value of cumulative distribution probabilities of values of the load item at each time point in T_s, and computed according to following formula of;