# Log Pattern Mining for Distributed System Maintenance

Authors: Jia Chen; Peng Wang; Shiqing Du; Wei Wang
Journal: Complexity
 (2020)

---

## Abstract

Due to the complexity of the network structure, log analysis is usually necessary for the maintenance of network-based distributed systems since logs record rich information about the system behaviors. In recent years, numerous works have been proposed for log analysis; however, they ignore temporal relationships between logs. In this paper, we target on the problem of mining informative patterns from temporal log data. We propose an approach to discover sequential patterns from event sequences with temporal regularities. Discovered patterns are useful for engineers to understand the behaviors of a network-based distributed system. To solve the well-known problem of pattern explosion, we resort to the minimum description length (MDL) principle and take a step forward in summarizing the temporal relationships between adjacent events of a pattern. Experiments on real log datasets prove the efficiency and effectiveness of our method.


---

## Body

## 1. Introduction

With the increasing demand for computing power, many network-based distributed systems have emerged, such as the popular distributed storage system and HDFS. Distributed system utilizes multiple machine nodes to complete tasks based on the network. Since the network may be complex and each node in the network may report anomalies, to maintain the network-based distributed application, instead of monitoring each node of the network, experts usually analyze the node logs to evaluate the health of the system. Logs record the running status and significant events such as the starting and ending of a task of the system. Mining information from log sequences is a useful way to understand network-based distributed system behaviors.Many researchers have proposed different log analysis approaches in recent years. Some try to sketch the operation process of the system [1–3], and some devote to functional tasks, such as anomaly detection and problem diagnosis [4, 5]. In this paper, we treat the timestamped log messages as an event sequence produced by a black-box system. We target on the problem of mining informative patterns from temporal log sequence data. Here, by informative, we mean a set of patterns that can summarize the log sequence well. The discovered patterns can help the operation engineers to have a better understanding of the system behaviors and serve as an excellent source of information for online monitoring and anomaly detection. Our work is motivated by the well-known distributed file system HDFS. Many informative patterns are generated during system operation, corresponding to different system behaviors.As the centerpiece of the HDFS, one important function of the NameNode is to determine the mapping of blocks of a file to DataNodes when a new file is written to the HDFS. For the NameNode, the write operation regularly generates a pattern as shown in Table1. Normally, when a new data block is allocated, three copies of this block are created in different DataNodes, and after creating required replicas, NameNode updates the block map. This typical system behavior can be represented by a sequential pattern P=132,134,134,134.Table 1
Log file example indicating a meaningful pattern.
Event typeTimestampLog message1322018-07-05 16:25:03,718StateChange: BLOCK∗ allocate blk_1073741825_1001 for /hbase/.tmp/hbase.version1342018-07-05 16:25:03,959BlockStateChange: BLOCK∗ addStoredBlock: blockMap updated: 10.141.208.49:50010 is added to blk_1073741825_10011342018-07-05 16:25:03,961BlockStateChange: BLOCK∗ addStoredBlock: blockMap updated: 10.141.208.43:50010 is added to blk_1073741825_10011342018-07-05 16:25:03,988BlockStateChange: BLOCK∗ addStoredBlock: blockMap updated: 218.193.132.35:50010 is added to blk_1073741825_1001Based on capturing this type of patterns, we can further implement several log analysis applications. For example, with the increasing amount of log data generated by the complex system, it is rather difficult for engineers to check the log messages one by one. Compressing the log data to a smaller size without losing the important information is of high demand. Since the pattern represents the semantic of the data block allocating behavior, we can reduce the number of logs greatly by encoding the original log sequence with the discovered patterns. Besides, we can investigate the historical condition of the cluster by counting the number of newly added data blocks in the last week.Sequential pattern mining has become an important data mining problem for decades. Dozens of research efforts focus on the problem of finding sequential patterns effectively [6–8]. However, traditional mining approaches often generate a huge number of patterns that confuse users a lot. To solve the well-known problem of pattern explosion [9], we resort to the minimum description length (MDL) principle [10], which has been used in several previous works [9, 11, 12]. The MDL principle provides a good balance between the complexity of the result pattern set and its ability to represent the data.Although our work is not the first work that discovers patterns by utilizing the MDL principle, we take a step forward in summarizing the temporal relationships among events of a pattern. Logs monitor repetitive behaviors corresponding to execution traces of several program statements. It is a common case that there exist significant temporal regularities in system logs. Consider an example in Figure1, which shows simplified log messages for two behaviors of the NameNode. We use capitals to represent event types and lowercase characters to represent corresponding occurrences. There exist two patterns: P1=ABC, where B is generated after A every 2 or 5 seconds and C is generated after B every 3 seconds. P2=DD, where the interval between D is 1 or 2 seconds. Obviously, patterns summarizing the temporal relations between adjacent events indicate more information of the running status of the system.Figure 1
Toy example of three possible encodings, DTS, SQS, and CSC, respectively.However, none of these methods fully consider the temporal relationships. From the perspective of handling temporal relations between adjacent events of a pattern, existing approaches can be divided into two groups. GoKrimp [9] and SQS [12] punish gaps by allocating higher cost when encoding patterns with large gaps, which do not consider the regularity of interarrival times at all. CSC [11] considers patterns restricted to fixed intervals and does not allow any event type appearing more than once, which strongly limits the expressiveness of a pattern. The generated patterns of previous methods either mix together and result in high redundancy [9, 12] or are too simple to represent the true behaviors [11].In this paper, we propose an approach DTS (discovering patterns from temporal log sequences) to remedy the defects. To the best of our knowledge, our work is the first work proposed to encode the temporal regularity of patterns in an event sequence. The encoding scheme enables us to discover high-quality patterns with low redundancy.The key contributions of our work include the following:(1)
We formalize how to use histograms to describe the distribution of time intervals between adjacent events in a pattern. Moreover, we design an encoding scheme that compresses the original sequence as well as the temporal regularities with the mined patterns in a lossless way.(2)
We introduce a heuristic algorithm DTS that discovers a set of informative patterns both effectively and efficiently.(3)
Evaluation results on real datasets show that our methods are capable of discovering high-quality patterns with low redundancy.The rest of this paper is organized as follows. In Section2, we give the preliminary knowledge about our work, including the pattern semantic and the problem statement. The encoding scheme for temporal data is described in Section 3. In Section 4, we present the algorithm for mining patterns that best compress the log sequence. We evaluate the effectiveness and efficiency of our approaches in Section 5. We discuss related work in Section 6 and conclude this paper in Section 7.


## 2. Preliminaries

### 2.1. Log Sequence and Log Parsing

A log sequence is a sequence of log entry and timestamp pairs, denoted asSlog=log1,t1,log2,t2,…,logn,tnti≤ti+1,1≤i≤n, where logi is the i-th log entry and ti is the corresponding timestamp. The granularity of timestamps can be set to any level depending on the application.Raw logs are usually unstructured, free-text messages. To analyze log data, a common preprocessing step is to parse unstructured log messages into structured representations [13, 14]. Concretely, log messages printed by the same statement are often highly similar to each other and vice versa [13]. Based on this observation, we can extract two parts of information from a log message: event type and parameters. Event type refers to the constant content shared by all logs generated by the same statement, while parameters are the values of variables that differ from log to log. In this paper, we use Drain [14] to parse the original log messages due to its popularity and excellent performance. For each log message logi, we store its event type and parameters with a structured representation, denoted as a tuple ei,para1,para2,…,parap, where ei refers to an instance of the event type of logi, paraj1≤j≤p refers to the values of the parameters, and p is the number of parameters in logi. We assume that the event types of all logs in Slog come from a finite alphabet Σ=E1,E2,…,El. Therefore, the original log sequence is parsed into a temporal event sequence S=e1,t1,e2,t2,…,en,tn. We use ΔS to denote the time spanned by S, i.e., ΔS=tn−t1. For brevity, we omit the parameters when unnecessary.


### 2.2. Pattern Discovery with the MDL Principle

In this work, our goal is to turn the raw log sequence into a sequence of more informative patterns. Specifically, we aim to discover a set of informative patterns which can (1) represent event relationships and temporal regularities and (2) provide the best lossless compression of the event sequence. This is achieved based on the minimum description length (MDL) principle [10].


#### 2.2.1. A Brief Introduction to MDL

We use MDL as a metric to balance data compression quality and complexity. Specifically, we apply the two-part MDL principle, which can be roughly described as follows. Given a set of modelsℳ, the best model M∈ℳ is the one that minimizes LS,M=LM+LS|M, where LM is the description length of M and LS|M is the description length of sequence S when encoded with M. The description length is computed at the bit level. In this paper, the model refers to a set of patterns P. We will define the encoding scheme as to how to describe S with a set of patterns and how to compute the description length later. Thus, our problem of pattern discovery can be formulated as follows.Problem Definition. Given a temporal log sequenceS, find the set of patterns P that minimizes the description length LS,P=LP+LS|P.


#### 2.2.2. Semantics of the Pattern Language

To use MDL, we first need to specify the pattern language, which determines the “vocabulary” of all possible patterns we can discover givenS. Specifically, the key elements of a pattern Pi are defined as follows:(1)
Content: the content ofPi is denoted as E1,E2,…,Em, where Ej∈Σ1≤j≤m, which can be used as a unique identifier of each pattern. The length of the episode of Pi is m.(2)
Occurrence (set): an occurrence of patternPi in S is denoted as OPi=e1,t1,e2,t2,…,em,tm, a list of events ej ordered by time tj, where ej,tj∈S1≤j≤m with ej denoting an instance of event type Ej∈Pi. The occurrence set of a pattern is denoted as OPi. In this paper, we consider the leftmost occurrences of Pi.(3)
Support: the support of a patternPi is the number of its nonoverlapping occurrences, denoted as suppi. Two occurrences of Pi are nonoverlapping if they do not share common events. We also do not allow overlapping among occurrences of different patterns.(4)
Time interval distribution: given the occurrence set ofPi, we use a histogram hik to describe the distributions of time intervals between adjacent events ek and ek+11≤k≤m−1 in Pi. Specifically, the bin hikb counts the number of time intervals that equal b.


## 2.1. Log Sequence and Log Parsing

A log sequence is a sequence of log entry and timestamp pairs, denoted asSlog=log1,t1,log2,t2,…,logn,tnti≤ti+1,1≤i≤n, where logi is the i-th log entry and ti is the corresponding timestamp. The granularity of timestamps can be set to any level depending on the application.Raw logs are usually unstructured, free-text messages. To analyze log data, a common preprocessing step is to parse unstructured log messages into structured representations [13, 14]. Concretely, log messages printed by the same statement are often highly similar to each other and vice versa [13]. Based on this observation, we can extract two parts of information from a log message: event type and parameters. Event type refers to the constant content shared by all logs generated by the same statement, while parameters are the values of variables that differ from log to log. In this paper, we use Drain [14] to parse the original log messages due to its popularity and excellent performance. For each log message logi, we store its event type and parameters with a structured representation, denoted as a tuple ei,para1,para2,…,parap, where ei refers to an instance of the event type of logi, paraj1≤j≤p refers to the values of the parameters, and p is the number of parameters in logi. We assume that the event types of all logs in Slog come from a finite alphabet Σ=E1,E2,…,El. Therefore, the original log sequence is parsed into a temporal event sequence S=e1,t1,e2,t2,…,en,tn. We use ΔS to denote the time spanned by S, i.e., ΔS=tn−t1. For brevity, we omit the parameters when unnecessary.


## 2.2. Pattern Discovery with the MDL Principle

In this work, our goal is to turn the raw log sequence into a sequence of more informative patterns. Specifically, we aim to discover a set of informative patterns which can (1) represent event relationships and temporal regularities and (2) provide the best lossless compression of the event sequence. This is achieved based on the minimum description length (MDL) principle [10].


### 2.2.1. A Brief Introduction to MDL

We use MDL as a metric to balance data compression quality and complexity. Specifically, we apply the two-part MDL principle, which can be roughly described as follows. Given a set of modelsℳ, the best model M∈ℳ is the one that minimizes LS,M=LM+LS|M, where LM is the description length of M and LS|M is the description length of sequence S when encoded with M. The description length is computed at the bit level. In this paper, the model refers to a set of patterns P. We will define the encoding scheme as to how to describe S with a set of patterns and how to compute the description length later. Thus, our problem of pattern discovery can be formulated as follows.Problem Definition. Given a temporal log sequenceS, find the set of patterns P that minimizes the description length LS,P=LP+LS|P.


### 2.2.2. Semantics of the Pattern Language

To use MDL, we first need to specify the pattern language, which determines the “vocabulary” of all possible patterns we can discover givenS. Specifically, the key elements of a pattern Pi are defined as follows:(1)
Content: the content ofPi is denoted as E1,E2,…,Em, where Ej∈Σ1≤j≤m, which can be used as a unique identifier of each pattern. The length of the episode of Pi is m.(2)
Occurrence (set): an occurrence of patternPi in S is denoted as OPi=e1,t1,e2,t2,…,em,tm, a list of events ej ordered by time tj, where ej,tj∈S1≤j≤m with ej denoting an instance of event type Ej∈Pi. The occurrence set of a pattern is denoted as OPi. In this paper, we consider the leftmost occurrences of Pi.(3)
Support: the support of a patternPi is the number of its nonoverlapping occurrences, denoted as suppi. Two occurrences of Pi are nonoverlapping if they do not share common events. We also do not allow overlapping among occurrences of different patterns.(4)
Time interval distribution: given the occurrence set ofPi, we use a histogram hik to describe the distributions of time intervals between adjacent events ek and ek+11≤k≤m−1 in Pi. Specifically, the bin hikb counts the number of time intervals that equal b.


## 2.2.1. A Brief Introduction to MDL

We use MDL as a metric to balance data compression quality and complexity. Specifically, we apply the two-part MDL principle, which can be roughly described as follows. Given a set of modelsℳ, the best model M∈ℳ is the one that minimizes LS,M=LM+LS|M, where LM is the description length of M and LS|M is the description length of sequence S when encoded with M. The description length is computed at the bit level. In this paper, the model refers to a set of patterns P. We will define the encoding scheme as to how to describe S with a set of patterns and how to compute the description length later. Thus, our problem of pattern discovery can be formulated as follows.Problem Definition. Given a temporal log sequenceS, find the set of patterns P that minimizes the description length LS,P=LP+LS|P.


## 2.2.2. Semantics of the Pattern Language

To use MDL, we first need to specify the pattern language, which determines the “vocabulary” of all possible patterns we can discover givenS. Specifically, the key elements of a pattern Pi are defined as follows:(1)
Content: the content ofPi is denoted as E1,E2,…,Em, where Ej∈Σ1≤j≤m, which can be used as a unique identifier of each pattern. The length of the episode of Pi is m.(2)
Occurrence (set): an occurrence of patternPi in S is denoted as OPi=e1,t1,e2,t2,…,em,tm, a list of events ej ordered by time tj, where ej,tj∈S1≤j≤m with ej denoting an instance of event type Ej∈Pi. The occurrence set of a pattern is denoted as OPi. In this paper, we consider the leftmost occurrences of Pi.(3)
Support: the support of a patternPi is the number of its nonoverlapping occurrences, denoted as suppi. Two occurrences of Pi are nonoverlapping if they do not share common events. We also do not allow overlapping among occurrences of different patterns.(4)
Time interval distribution: given the occurrence set ofPi, we use a histogram hik to describe the distributions of time intervals between adjacent events ek and ek+11≤k≤m−1 in Pi. Specifically, the bin hikb counts the number of time intervals that equal b.


## 3. Data Encoding Scheme

In this section, we present our encoding scheme and the way we compute description lengths. It is worth noting that we are only interested in code length functions instead of actual encodings [10]. All logarithms in this paper are to base 2.


### 3.1. Encoding the Pattern Set

Under the MDL criterion, we need to first encode the model, which is the pattern setP in our paper. Here, we use P to store the elements of all patterns, which comprise the items in the header row of Figure 2. The event sequence S can then be compressed by replacing the occurrences of patterns with the corresponding codes. For each pattern, we need to encode its episode and histograms which describe the distribution of time intervals between adjacent events. Although most of the events in S are covered by patterns, some events can be left out. Each of such events is covered by a special pattern with only one item in its content (namely, the type Ei of the event), which is denoted as a singletonpattern which has no histogram.Figure 2
Toy example of a pattern setP and the description length of pattern P1.As with description length computation, first we discuss how to calculateLPi. We use logΣ bits to describe the content of each event type. Therefore, episode αPi of length m needs m×logΣ bits to describe. We use a unique code, denoted as CPi, to encode each pattern. Intuitively, frequent patterns should have shorter description lengths. Hence, the length of the binary code depends on the pattern’s frequency fi, denoted as fi=suppi/F, where F = ∑Pi∈Psuppi is the sum of all patterns’ support. Here, we consider optimal prefix codes, where the code length is CPi = −logfi.As with the histogramhik, let the number of nonempty bins in hik be cntbins. Since the bin width is set to the time unit of S, the more regular each value of the time interval between adjacent events in Pi is, the less diverse these values are and the smaller cntbins is. Consider the value of the ratio rhk=cntbins/suppi. A smaller value of rhk indicates better temporal regularity between ek and ek+1. This observation allows us to design an encoding scheme that compresses the temporal regularity of pattern Pi’s occurrences.To be specific, the value of a nonempty binhikbj is denoted as cntbj = OPi|tk+1−tk=bj, where bj is the difference between the timestamps of two adjacent events and cntbj is the number of intervals in hikbj. We use logΔS number of bits to encode bj and logsuppi number of bits to encode cntbj. We also need extra bits to identify each nonempty bin, whose length is dependent on the size of hikbj. Concretely, the more intervals that equal bj, the shorter the code length, which is Chikbj=−logcntbj/suppi. Thus, the information of a histogram hik can be described using Lhik=∑j=0cntbinslogΔS+logsuppi+Chikbj bits. To sum up, the description length of a pattern in P is(1)LPi=m×logΣ+CPi+∑k=1m−1Lhik.Figure2 gives a concrete example on how the description length of a pattern is computed. For all patterns in P, the total description length is(2)LP=∑Pi∈PLPi.


### 3.2. Encoding the Event Sequence

Given the encoded pattern setP, we can encode the event sequence S by replacing the occurrences of patterns in P with their codes. Since S is a temporal sequence, for each occurrence of a pattern, we need to cover all events in it as well as their timestamps. In our encoding scheme, we replace an occurrence with the code of the corresponding pattern Pi and the timestamp of its first event. The description length of a timestamp is logΔS. Moreover, we use the codes of histogram bins to specify the time intervals between adjacent events. We individually encode each bin hikbj in hik. The resulting encoding is CPi,ΔSChi1bj1,…,Chim−1bjm−1. For the remaining events that are not covered by any pattern, we simply use singleton patterns Ei to encode them, i.e., CEi,ΔS.As a concrete example, we encode the sequenceS in Figure 1 using the pattern set in Figure 2. Here, S is encoded by replacing the original events and timestamps in each occurrence of each pattern Pi with the corresponding codes. For example, a,0b,2c,5 is an occurrence of P1, and it is replaced by CP1,ΔSCh112Ch123 in the encoded sequence.With this encoding scheme, the description length of sequenceS encoded by P is calculated as follows:(3)LS|P=∑Pi∈P|CPi|+logΔS+∑k=1m−1Chikb.


## 3.1. Encoding the Pattern Set

Under the MDL criterion, we need to first encode the model, which is the pattern setP in our paper. Here, we use P to store the elements of all patterns, which comprise the items in the header row of Figure 2. The event sequence S can then be compressed by replacing the occurrences of patterns with the corresponding codes. For each pattern, we need to encode its episode and histograms which describe the distribution of time intervals between adjacent events. Although most of the events in S are covered by patterns, some events can be left out. Each of such events is covered by a special pattern with only one item in its content (namely, the type Ei of the event), which is denoted as a singletonpattern which has no histogram.Figure 2
Toy example of a pattern setP and the description length of pattern P1.As with description length computation, first we discuss how to calculateLPi. We use logΣ bits to describe the content of each event type. Therefore, episode αPi of length m needs m×logΣ bits to describe. We use a unique code, denoted as CPi, to encode each pattern. Intuitively, frequent patterns should have shorter description lengths. Hence, the length of the binary code depends on the pattern’s frequency fi, denoted as fi=suppi/F, where F = ∑Pi∈Psuppi is the sum of all patterns’ support. Here, we consider optimal prefix codes, where the code length is CPi = −logfi.As with the histogramhik, let the number of nonempty bins in hik be cntbins. Since the bin width is set to the time unit of S, the more regular each value of the time interval between adjacent events in Pi is, the less diverse these values are and the smaller cntbins is. Consider the value of the ratio rhk=cntbins/suppi. A smaller value of rhk indicates better temporal regularity between ek and ek+1. This observation allows us to design an encoding scheme that compresses the temporal regularity of pattern Pi’s occurrences.To be specific, the value of a nonempty binhikbj is denoted as cntbj = OPi|tk+1−tk=bj, where bj is the difference between the timestamps of two adjacent events and cntbj is the number of intervals in hikbj. We use logΔS number of bits to encode bj and logsuppi number of bits to encode cntbj. We also need extra bits to identify each nonempty bin, whose length is dependent on the size of hikbj. Concretely, the more intervals that equal bj, the shorter the code length, which is Chikbj=−logcntbj/suppi. Thus, the information of a histogram hik can be described using Lhik=∑j=0cntbinslogΔS+logsuppi+Chikbj bits. To sum up, the description length of a pattern in P is(1)LPi=m×logΣ+CPi+∑k=1m−1Lhik.Figure2 gives a concrete example on how the description length of a pattern is computed. For all patterns in P, the total description length is(2)LP=∑Pi∈PLPi.


## 3.2. Encoding the Event Sequence

Given the encoded pattern setP, we can encode the event sequence S by replacing the occurrences of patterns in P with their codes. Since S is a temporal sequence, for each occurrence of a pattern, we need to cover all events in it as well as their timestamps. In our encoding scheme, we replace an occurrence with the code of the corresponding pattern Pi and the timestamp of its first event. The description length of a timestamp is logΔS. Moreover, we use the codes of histogram bins to specify the time intervals between adjacent events. We individually encode each bin hikbj in hik. The resulting encoding is CPi,ΔSChi1bj1,…,Chim−1bjm−1. For the remaining events that are not covered by any pattern, we simply use singleton patterns Ei to encode them, i.e., CEi,ΔS.As a concrete example, we encode the sequenceS in Figure 1 using the pattern set in Figure 2. Here, S is encoded by replacing the original events and timestamps in each occurrence of each pattern Pi with the corresponding codes. For example, a,0b,2c,5 is an occurrence of P1, and it is replaced by CP1,ΔSCh112Ch123 in the encoded sequence.With this encoding scheme, the description length of sequenceS encoded by P is calculated as follows:(3)LS|P=∑Pi∈P|CPi|+logΔS+∑k=1m−1Chikb.


## 4. DTS: Discovering Patterns from Temporal Sequences

In this section, we introduce our DTS algorithm for pattern discovery. The problem of discovering a set of patternsP that best compresses S based on MDL has been proven to be NP-hard [9]. Therefore, we resort to discovering informative patterns heuristically instead of pursuing the optimal result. We assume sequence S is encoded by singleton patterns at the very beginning. Our DTS algorithm starts from an empty pattern set P and updates P iteratively until we cannot achieve no more compression.


### 4.1. Overall Process of DTS

We now present an overview of our DTS algorithm. A naïve strategy is to update the pattern setP by inserting the best pattern (the one that can achieve the largest gain in compression) in the current sequence S. However, for system logs, it is common that the execution of a task generates several different branches. For example, Figure 3 shows a simplified process of an HDFS client writing files. Each time the client finishes writing a data block, it will call addBlock() to allocate a new block. Each time the DataNode receives a new block, it will report to the NameNode, thus generating a sequence XYYY. Also, the NameNode sometimes calls fsync() to persist the cached data, thus triggering the log event M. Therefore, another sequence XMYYY can also be generated during the writing process.Figure 3
A simplified process of an HDFS client writing files.The common part of these two sequences, i.e.,XYYY, can be easily discovered and inserted into the set P. Nonetheless, it is much harder to recognize M together with XYYY. In practical maintenance applications, we hope to identify the behavioral patterns more completely. This cannot be achieved using the aforementioned naïve strategy.Faced with this problem, we divide the update operations ofP into two types: the insertion operation and the refinement operation. Their definitions are as follows.Definition 1.
(insertion operation). Insert the newly discovered candidate patternP into P. The pattern set is updated to P∪P.Definition 2.
(refinement operation). Given a patternP=E1E2,…,Em (P∈P), we refine it by adding events of type E at position jj∈0,…,m of P. The result is a new pattern Pr with length m+1. Specifically,(1)
Ifj=0, Pr=EE1E2,…,Em(2)
Ifj∈1,…,m−1, Pr=E1,…,EjEEj+1,…,Em(3)
Ifj=m, Pr=E1E2,…,EmE
The refinement operation is denoted asRPjE, where E is called as the refining event. The pattern set is updated to P\P∪Pm,Pr, where Pm denotes the remaining original pattern. If there are remaining occurrences of the original P, the operation is called a partial refinement; otherwise, it is called a full refinement, and then Pm is null. Figure 4 presents an example of the refinement operation.Figure 4
An example of the refinement operation. (a) Refining an occurrence. (b) Refining a pattern.
(a)(b)The pattern setP is updated iteratively by either inserting a new pattern to P or refining a pattern that is already in P. It is common that an event covered by a candidate pattern P is also a refining event for another pattern P′∈P. We refer to such a case as an event conflict. In each iteration, if there is no event conflict, we can greedily add the best candidate pattern to P. However, if there exists an event conflict, since our encoding scheme does not allow overlap among different patterns, it is necessary to decide which update operation is better. Here, we choose the operation that decreases the description length LP+LS|P more. After choosing an update operation, we encode the events covered by the new patterns with the corresponding codes. The pattern set P is updated iteratively until we cannot decrease the description length any more.The overall process of DTS is divided into two stages: the update stage driven by the event conflict and the update stage containing only refinement. We maintain two data structures to support the two update operations: a candidate pattern setℂℙ for insertion and a candidate refinement map ℂℝ for refinement. ℂℙ stores the candidate patterns in the current sequence dynamically, while ℂℝ stores the possible refinements for each pattern in P. As shown in Figure 5, at the first stage, DTS iteratively compares the compression gain of the candidate pattern and the refinement result, selecting the better one to update P. When ℂℙ becomes empty, namely, we cannot get a valid candidate pattern any more, DTS continues with the second stage, iteratively updating P with the best refinement in ℂℝ until ℂℝ is empty. We now move on to the technical details of our DTS algorithm.Figure 5
Overall process of DTS.


### 4.2. Candidate Pattern Setℂℙ

Concerning the insertion operation, we hope the patternP added to P will best decrease the description length. To this end, we define the compression gain of a pattern P as follows:(4)gainP=LS,P−LS,P∪P.A naive way of selecting the best candidate pattern is to enumerate all possible patterns exhaustively. However, this is time-consuming due to the exponential search space. In practice, instead of searching from scratch in each iteration, we maintain a candidate pattern setℂℙ that stores promising candidate patterns. We initialize ℂℙ with Algorithm 1. For each event type E∈Σ, best growth (α,S,ℰ,P) generates a pattern starting from a singleton pattern P=<E> by appending any event type E′ to the end of α greedily. Since it is computationally intensive to find the optimal occurrence set having the fewest histogram bin, we resolve to a simple approach that finds the leftmost occurrences of P. If the newly generated pattern yields greater compression gain than the previous one, we move on to test the next pattern created by a new growth. The process stops until we cannot get a new pattern better than the previous one. We select the last pattern Plast as the best pattern starting with E and add it to ℂℙ.Algorithm 1:Initialize the candidate pattern set ℂℙ.
Input: singleton event set Σ and sequence SOutput: candidate pattern set ℂℙ(1)
functionInitialize (ℂℙ) (Σ, S)(2)
ℂℙ⟵∅(3)
forE∈Σ do(4)
create a singleton patternP⟵<E>(5)
Plast⟵P(6)
whileP⟵BESTGROWTH (P,S,Σ) ≠nulldo(7)
Plast⟵P(8)
end while(9)
ifgainPlast>0then(10)
addPlast to ℂℙ(11)
end if(12)
end for(13)
sort the patterns inℂℙ by gainP(14)
returnℂℙ(15)
end function


### 4.3. Candidate Refinement Mapℂℝ

Considering the refinement operation, we maintain a candidate refinement mapℂℝ to store the best refinements for each pattern P∈P. Each refinement follows the format RPjE=refined−positionj,event−typeE,remaining−patternPm,refined−patternPr. For example, 1,F,DD,DFD indicates that a pattern DD is partially refined by event F at position 1, generating a new pattern DFD with some occurrences of the original pattern DD remaining. On the contrary, if DD is fully refined by F, the refinement result will be written as 1,F,null,DFD. The refinements in ℂℝ are indexed by the refining event type. In other words, the refinement results with the same event type are grouped together.When the pattern setP is updated by a new pattern P, which is either selected from ℂℙ or generated by a refinement operation, we decide whether there exists a good refinement for each position by Algorithm 2. For each position j, we only store the refinement that best decreases the encoded description length. The compression gain is defined in the following equation:(5)gainRPjE′=LS,P−LS,P\P∪Pm,Pr.Algorithm 2: Obtain the best refinements for pattern P.
Input: pattern P, sequence S, singleton event set Σ and candidate refinement map ℂℝ(1)
function OBTAINREFINEMENTS (P, S, Σ, ℂℝ)(2)
forj=0⟶Pdo(3)
R∗PjE⟵null(4)
forE∈Σ do(5)
RPjE⟵Refine (P,S,j,E)(6)
ifcmpRPjE,R∗PjE>0then(7)
R∗PjE⟵RPjE(8)
end if(9)
end for(10)
ifgainR∗PjE>0then(11)
addR∗PjE to ℂℝ.getE(12)
end if(13)
end for(14)
end functionThe way we obtain a refinementRefine (P,S,j,E) is as follows. The content of the newly refined pattern Pr can be easily obtained by Definition 2. The occurrences of Pr can be obtained from the original occurrence set of P. For each occurrence OP=e1,t1,e2,t2,…,em,tm∈OP, we find the leftmost event instance ei,ti in S that meets the time restriction and refine OP with it.


### 4.4. The Complete DTS Algorithm

In this section, we present the complete DTS algorithm for heuristic discovery of the pattern setP. As is shown in Algorithm 3, we update P iteratively until we cannot decrease the description length of S any more. At the beginning, we initialize the relevant data structures. Lines 4–17 correspond to the update stage driven by the event conflict. During this stage, DTS first gets the best candidate pattern P∗ in ℂℙ. Then, DTS calls the function BestConflictRefinement (P, ℂℝ) to check if there exist one or more refinements in ℂℝ that conflict with P∗ and retrieve the best one R∗P′E. DTS decides which one is better to update the pattern set P by comparing the compression gains of P∗ and R∗P′E with the following equation:(6)cmpP∗,R∗P′E=gainP∗P∗∗OP−gainR∗P′EOPr′.Algorithm 3: DTS: discovering patterns from temporal sequences.
Input: sequence SOutput: pattern set P(1)
functionDTS (S)(2)
Σ⟵ all event types in S, ℙ⟵∅(3)
ℂℙ⟵Initializeℂℙ(Σ, S), ℂℝ⟵newMap(4)
while true do(5)
P∗⟵BestCandidatePattern(ℂℙ)(6)
ifP∗=nullthen(7)
break(8)
end if(9)
R∗P′jE⟵BestConflictRefinement (P, ℂℝ)(10)
ifR∗P′jE=null or cmpP∗,R∗P′jE≥0then(11)
P⟵P∪P∗(12)
Updateℂℙ, Updateℂℝ, Encode (S, P∗)(13)
else(14)
P⟵P\P′∪Pm′,Pr′(15)
Updateℂℙ, Updateℂℝ, Encode (S, Pm′,Pr′)(16)
end if(17)
end while(18)
while (R∗P′jE⟵BestCandidateRefinement (ℂℝ)) ≠nulldo(19)
P⟵P\P∗∪Pm′,Pr′(20)
Updateℂℙ, Updateℂℝ, Encode (S, Pm′,Pr′)(21)
end while(22)
returnP(23)
end functionNote that we compare the compression gains of the two operations at the event level in order to avoid bias towards patterns with longer episodes or greater frequency. A positive value ofcmpP∗,R∗P′E indicates that P has greater compression gain. Otherwise, R∗P′E is better. If P∗ is better or there is no conflicting refinement, P will be updated to P∪P∗; otherwise, it will be updated to P\P′∪Pm′,Pr′.When the function BestCandidatePattern (ℂℙ) returns null which indicates that there is no candidate pattern in the current sequence any more, DTS moves on to the next stage. Lines 18–21 correspond to the update stage containing only refinement. Here, DTS updates P with the best refinement in ℂℝ iteratively.To illustrate, consider the example in Figure6, in which the best current candidate pattern is P1=EF, and there exist two conflicting refinements in ℂℝ, where R∗DDF=1,F,DD,DFD is selected using BestCandidateRefinement (EF). If R∗DDF has greater compression gain, pattern set P will be updated to P′; otherwise, pattern P1=EF will be added to P, resulting in P″.Figure 6
An example of updating a pattern set.The data structuresℂℙ and ℂℝ are maintained dynamically. After each update, we delete invalid elements in them and adjust the patterns that are influenced by the update.


## 4.1. Overall Process of DTS

We now present an overview of our DTS algorithm. A naïve strategy is to update the pattern setP by inserting the best pattern (the one that can achieve the largest gain in compression) in the current sequence S. However, for system logs, it is common that the execution of a task generates several different branches. For example, Figure 3 shows a simplified process of an HDFS client writing files. Each time the client finishes writing a data block, it will call addBlock() to allocate a new block. Each time the DataNode receives a new block, it will report to the NameNode, thus generating a sequence XYYY. Also, the NameNode sometimes calls fsync() to persist the cached data, thus triggering the log event M. Therefore, another sequence XMYYY can also be generated during the writing process.Figure 3
A simplified process of an HDFS client writing files.The common part of these two sequences, i.e.,XYYY, can be easily discovered and inserted into the set P. Nonetheless, it is much harder to recognize M together with XYYY. In practical maintenance applications, we hope to identify the behavioral patterns more completely. This cannot be achieved using the aforementioned naïve strategy.Faced with this problem, we divide the update operations ofP into two types: the insertion operation and the refinement operation. Their definitions are as follows.Definition 1.
(insertion operation). Insert the newly discovered candidate patternP into P. The pattern set is updated to P∪P.Definition 2.
(refinement operation). Given a patternP=E1E2,…,Em (P∈P), we refine it by adding events of type E at position jj∈0,…,m of P. The result is a new pattern Pr with length m+1. Specifically,(1)
Ifj=0, Pr=EE1E2,…,Em(2)
Ifj∈1,…,m−1, Pr=E1,…,EjEEj+1,…,Em(3)
Ifj=m, Pr=E1E2,…,EmE
The refinement operation is denoted asRPjE, where E is called as the refining event. The pattern set is updated to P\P∪Pm,Pr, where Pm denotes the remaining original pattern. If there are remaining occurrences of the original P, the operation is called a partial refinement; otherwise, it is called a full refinement, and then Pm is null. Figure 4 presents an example of the refinement operation.Figure 4
An example of the refinement operation. (a) Refining an occurrence. (b) Refining a pattern.
(a)(b)The pattern setP is updated iteratively by either inserting a new pattern to P or refining a pattern that is already in P. It is common that an event covered by a candidate pattern P is also a refining event for another pattern P′∈P. We refer to such a case as an event conflict. In each iteration, if there is no event conflict, we can greedily add the best candidate pattern to P. However, if there exists an event conflict, since our encoding scheme does not allow overlap among different patterns, it is necessary to decide which update operation is better. Here, we choose the operation that decreases the description length LP+LS|P more. After choosing an update operation, we encode the events covered by the new patterns with the corresponding codes. The pattern set P is updated iteratively until we cannot decrease the description length any more.The overall process of DTS is divided into two stages: the update stage driven by the event conflict and the update stage containing only refinement. We maintain two data structures to support the two update operations: a candidate pattern setℂℙ for insertion and a candidate refinement map ℂℝ for refinement. ℂℙ stores the candidate patterns in the current sequence dynamically, while ℂℝ stores the possible refinements for each pattern in P. As shown in Figure 5, at the first stage, DTS iteratively compares the compression gain of the candidate pattern and the refinement result, selecting the better one to update P. When ℂℙ becomes empty, namely, we cannot get a valid candidate pattern any more, DTS continues with the second stage, iteratively updating P with the best refinement in ℂℝ until ℂℝ is empty. We now move on to the technical details of our DTS algorithm.Figure 5
Overall process of DTS.


## 4.2. Candidate Pattern Setℂℙ

Concerning the insertion operation, we hope the patternP added to P will best decrease the description length. To this end, we define the compression gain of a pattern P as follows:(4)gainP=LS,P−LS,P∪P.A naive way of selecting the best candidate pattern is to enumerate all possible patterns exhaustively. However, this is time-consuming due to the exponential search space. In practice, instead of searching from scratch in each iteration, we maintain a candidate pattern setℂℙ that stores promising candidate patterns. We initialize ℂℙ with Algorithm 1. For each event type E∈Σ, best growth (α,S,ℰ,P) generates a pattern starting from a singleton pattern P=<E> by appending any event type E′ to the end of α greedily. Since it is computationally intensive to find the optimal occurrence set having the fewest histogram bin, we resolve to a simple approach that finds the leftmost occurrences of P. If the newly generated pattern yields greater compression gain than the previous one, we move on to test the next pattern created by a new growth. The process stops until we cannot get a new pattern better than the previous one. We select the last pattern Plast as the best pattern starting with E and add it to ℂℙ.Algorithm 1:Initialize the candidate pattern set ℂℙ.
Input: singleton event set Σ and sequence SOutput: candidate pattern set ℂℙ(1)
functionInitialize (ℂℙ) (Σ, S)(2)
ℂℙ⟵∅(3)
forE∈Σ do(4)
create a singleton patternP⟵<E>(5)
Plast⟵P(6)
whileP⟵BESTGROWTH (P,S,Σ) ≠nulldo(7)
Plast⟵P(8)
end while(9)
ifgainPlast>0then(10)
addPlast to ℂℙ(11)
end if(12)
end for(13)
sort the patterns inℂℙ by gainP(14)
returnℂℙ(15)
end function


## 4.3. Candidate Refinement Mapℂℝ

Considering the refinement operation, we maintain a candidate refinement mapℂℝ to store the best refinements for each pattern P∈P. Each refinement follows the format RPjE=refined−positionj,event−typeE,remaining−patternPm,refined−patternPr. For example, 1,F,DD,DFD indicates that a pattern DD is partially refined by event F at position 1, generating a new pattern DFD with some occurrences of the original pattern DD remaining. On the contrary, if DD is fully refined by F, the refinement result will be written as 1,F,null,DFD. The refinements in ℂℝ are indexed by the refining event type. In other words, the refinement results with the same event type are grouped together.When the pattern setP is updated by a new pattern P, which is either selected from ℂℙ or generated by a refinement operation, we decide whether there exists a good refinement for each position by Algorithm 2. For each position j, we only store the refinement that best decreases the encoded description length. The compression gain is defined in the following equation:(5)gainRPjE′=LS,P−LS,P\P∪Pm,Pr.Algorithm 2: Obtain the best refinements for pattern P.
Input: pattern P, sequence S, singleton event set Σ and candidate refinement map ℂℝ(1)
function OBTAINREFINEMENTS (P, S, Σ, ℂℝ)(2)
forj=0⟶Pdo(3)
R∗PjE⟵null(4)
forE∈Σ do(5)
RPjE⟵Refine (P,S,j,E)(6)
ifcmpRPjE,R∗PjE>0then(7)
R∗PjE⟵RPjE(8)
end if(9)
end for(10)
ifgainR∗PjE>0then(11)
addR∗PjE to ℂℝ.getE(12)
end if(13)
end for(14)
end functionThe way we obtain a refinementRefine (P,S,j,E) is as follows. The content of the newly refined pattern Pr can be easily obtained by Definition 2. The occurrences of Pr can be obtained from the original occurrence set of P. For each occurrence OP=e1,t1,e2,t2,…,em,tm∈OP, we find the leftmost event instance ei,ti in S that meets the time restriction and refine OP with it.


## 4.4. The Complete DTS Algorithm

In this section, we present the complete DTS algorithm for heuristic discovery of the pattern setP. As is shown in Algorithm 3, we update P iteratively until we cannot decrease the description length of S any more. At the beginning, we initialize the relevant data structures. Lines 4–17 correspond to the update stage driven by the event conflict. During this stage, DTS first gets the best candidate pattern P∗ in ℂℙ. Then, DTS calls the function BestConflictRefinement (P, ℂℝ) to check if there exist one or more refinements in ℂℝ that conflict with P∗ and retrieve the best one R∗P′E. DTS decides which one is better to update the pattern set P by comparing the compression gains of P∗ and R∗P′E with the following equation:(6)cmpP∗,R∗P′E=gainP∗P∗∗OP−gainR∗P′EOPr′.Algorithm 3: DTS: discovering patterns from temporal sequences.
Input: sequence SOutput: pattern set P(1)
functionDTS (S)(2)
Σ⟵ all event types in S, ℙ⟵∅(3)
ℂℙ⟵Initializeℂℙ(Σ, S), ℂℝ⟵newMap(4)
while true do(5)
P∗⟵BestCandidatePattern(ℂℙ)(6)
ifP∗=nullthen(7)
break(8)
end if(9)
R∗P′jE⟵BestConflictRefinement (P, ℂℝ)(10)
ifR∗P′jE=null or cmpP∗,R∗P′jE≥0then(11)
P⟵P∪P∗(12)
Updateℂℙ, Updateℂℝ, Encode (S, P∗)(13)
else(14)
P⟵P\P′∪Pm′,Pr′(15)
Updateℂℙ, Updateℂℝ, Encode (S, Pm′,Pr′)(16)
end if(17)
end while(18)
while (R∗P′jE⟵BestCandidateRefinement (ℂℝ)) ≠nulldo(19)
P⟵P\P∗∪Pm′,Pr′(20)
Updateℂℙ, Updateℂℝ, Encode (S, Pm′,Pr′)(21)
end while(22)
returnP(23)
end functionNote that we compare the compression gains of the two operations at the event level in order to avoid bias towards patterns with longer episodes or greater frequency. A positive value ofcmpP∗,R∗P′E indicates that P has greater compression gain. Otherwise, R∗P′E is better. If P∗ is better or there is no conflicting refinement, P will be updated to P∪P∗; otherwise, it will be updated to P\P′∪Pm′,Pr′.When the function BestCandidatePattern (ℂℙ) returns null which indicates that there is no candidate pattern in the current sequence any more, DTS moves on to the next stage. Lines 18–21 correspond to the update stage containing only refinement. Here, DTS updates P with the best refinement in ℂℝ iteratively.To illustrate, consider the example in Figure6, in which the best current candidate pattern is P1=EF, and there exist two conflicting refinements in ℂℝ, where R∗DDF=1,F,DD,DFD is selected using BestCandidateRefinement (EF). If R∗DDF has greater compression gain, pattern set P will be updated to P′; otherwise, pattern P1=EF will be added to P, resulting in P″.Figure 6
An example of updating a pattern set.The data structuresℂℙ and ℂℝ are maintained dynamically. After each update, we delete invalid elements in them and adjust the patterns that are influenced by the update.


## 5. Experiments

In this section, we conduct extensive experiments to verify the effectiveness of our approach. All experiments were executed on a machine with Intel i7-3770 CPU @3.4 GHz, 24 GB of RAM, and Window 10 OS.


### 5.1. Datasets and Settings

#### 5.1.1. Datasets

We use four different log datasets collected from real systems. The basic statistics of these datasets are summarized in Table2. The Zookeeper and OpenStack datasets are collected from the well-known loghub data repository [15], while the NameNode and DataNode logs are collected from our own HDFS cluster.Table 2
Basic statistics of four log datasets.
Log type# log entries# event types%suppE≤50NameNode600,00018075%DataNode1,000,00010688%Zookeeper74,3808568%OpenStack91,447362%These datasets have different characteristics. The NameNode logs have more event types and more complex system behaviors interleaving together as a NameNode manages multiple DataNodes. The DataNode and Zookeeper logs have less event types as well as simpler and more regular behaviors. The OpenStack logs contain only behaviors such as creating a project and other simple tasks, thus having the least event types.For each log dataset, we calculate the ratio of event types which occur less than 50 times. As is shown in Table2, three out of four datasets contain a high percentage of low-support event types (more than 65%). To discover nontrivial patterns in these datasets effectively, we need to set the support threshold to a low value, which can lead to the pattern explosion problem. We will later show that DTS can discover nontrivial patterns while maintaining a low level of redundancy.


#### 5.1.2. Rival Approaches

We compare our approach against four approaches, GoKrimp [9], SQS [12], CSC [11], and ISM [16]. The first three approaches use the MDL principle [10] to discover patterns, while ISM is a probabilistic machine learning approach. We have not included SeqKrimp [9] in our experiments because GoKrimp yields similar results and is more efficient than SeqKrimp. For CSC and our approach, we simply use the entire sequence as the input. For other approaches, the sequences are broken into disjoint sequences of size 10. Our algorithms are implemented in Java, while the implementations of other approaches are obtained from the original authors.


### 5.2. Evaluation of Efficiency

In the first experiment, we compare the efficiencies of all approaches as the length of the log sequences varies on the NameNode and DataNode datasets. The results are shown in Figure7. It is worth noting that although the results of all 5 approaches are plotted in the same figures, the time unit for CSC, GoKrimp, and our approach is in seconds, while that for SQS and ISM is in minutes.Figure 7
Running time on varying length sequences. (a) NameNode. (b) DataNode.
(a)(b)As is shown, CSC is the faster than all other approaches because it has a gap constraint which restricts the size of the search space greatly. However, this constraint dictates that CSC cannot find complex patterns effectively, which will be shown in the next experiment. DTS is slower than GoKrimp as GoKrimp applies a dependency test for speedup. Nonetheless, this prevents GoKrimp from discovering low-frequency patterns.Although DTS takes comparatively longer time, it only needs less than 400 seconds to process a complex sequence with 600,000 events, which is acceptable in real applications. Besides, the running time of DTS increases steadily with the increase of log size, indicating good scalability. On the contrary, SQS and ISM are much slower, with processing times ranging from dozens of minutes to several hours due to their complex iterative computations.The running times on the Zookeeper and OpenStack datasets are shown in Table3, which shows similar results to those on the NameNode and DataNode logs. CSC is still the most efficient, while DTS comes next.Table 3
Running time on the Zookeeper and OpenStack logs (in seconds).
DTSSQSCSCGoKrimpISMZookeeper1966620452040OpenStack19315781523159


### 5.3. Evaluation of Pattern Quality

In this section, we analyze the quality of the patterns returned by different approaches from three aspects: the compression ratioCR, the event coverage EC, and the redundancy among different patterns.


#### 5.3.1. Evaluation of the Compression Ratio

According to the MDL principle, we can encode the sequence with the discovered pattern set. The smaller the description lengthLS,P is, the stronger the expressiveness of the encoding pattern set is. Here, we use compression ratio [9] (denoted as CR) to measure the effectiveness of the encoding. CR is defined as the ratio of the description length of the encoding with only singleton patterns to that with the discovered patterns. The higher the ratio is, the better the expressiveness is. Note that here we only compare the compression ratios for MDL-based approaches.Figure8 shows the compression ratios on all four datasets. As indicated, DTS generally achieves the best compression ratio, thanks to our effective encoding scheme as well as the proposed refinement operations and the heuristic strategy based on the “event conflict.” Among the other 3 comparison algorithms, the iterative searching strategy of GoKrimp is too simple to yield expressive results. Therefore, it generally achieves the lowest compression ratio. CSC has a good performance on the DataNode and Zookeeper logs, yielding similar performance to DTS. This can be attributed to the fact that CSC is suitable for processing log data in which the time intervals between adjacent events are short and constant. On the contrary, for log sequences such as NameNode logs which contain complex patterns, CSC tends to perform poorly. As with SQS, thanks to its complex search strategy, it performs well on more complex data. The problem with SQS is that it generates too many patterns, and thus, the model used to describe the data is too complicated, resulting in greater description length. This can negatively impact the compression ratio of SQS, especially when the patterns in the log data are simple.Figure 8
Compression ratios on different datasets.It is worth noting that while our approach has generally higher compression ratios, this does not mean that it results in more redundancies, on which we will discuss later.


#### 5.3.2. Evaluation of the Event Coverage

In this section, we evaluate whether the patterns returned by different approaches cover various event types adequately. We use the event coverage [17] (denoted as EC) as the metric, which measures the percentage of event types covered by the discovered patterns. A larger EC indicates better performance.Figure9 demonstrates the event coverage of all 5 approaches on the four log datasets. As is shown, except for GoKrimp, all other approaches have event coverage over 80%. By contrast, while GoKrimp achieves an EC of 91% on the OpenStack dataset, it fails to achieve an EC of over 50% on the remaining datasets. This is related to the proportion of rare event types in the log data. As was mentioned before, the search heuristic of GoKrimp is oversimplified, which prevents GoKrimp from discovering patterns with infrequent event types. Therefore, the more infrequent event types contained in the log data, the lower the event coverage of GoKrimp is. By contrast, this factor has little effect on the other five algorithms.Figure 9
Event coverage on different datasets.Overall, our DTS achieves the best coverage on the three of the four log datasets. However, it is slightly inferior to SQS and CSC on the OpenStack logs. This is because there are three event types in the OpenStack dataset which occur randomly in the sequence, exhibiting no significant temporal regularity. Therefore, DTS does not consider these event types as part of any pattern, while CSC and SQS greedily include these event types in some patterns. This showcases the advantage of DTS, which takes the temporal regularities of patterns into consideration, reducing the number of invalid patterns made up of random combinations of unrelated events. This can lead to a far less redundant result than CSC and SQS.


#### 5.3.3. Evaluation of the Pattern Redundancy

The goal of this work is to mine high-quality and low-redundancy pattern sets from log sequences. In previous sections, we have evaluated the pattern qualities using compression rate and event type coverage. We now shift our attention to the evaluation of pattern redundancy. Here, we utilize the following four metrics:(1)
Average intersequence edit distance (AED): this metric measures the edit similarity among the discovered patterns. Concretely, the AED of a pattern set is calculated as follows: for each pattern P in set P, we calculate the edit distance between P and each of the remaining discovered patterns P′P′∈P and normalize the distance with the pattern P’s length. We record the minimum distance between P and all other patterns. AED is obtained by averaging these minimum distances for all patterns in the pattern set. The larger the distance is, the less redundant the pattern set is.(2)
Average count of supersets (ACS): this metric measures the diversity of the event types contained in the discovered pattern set. Concretely, the ACS of a pattern set is calculated as follows: for each pattern P in P, we denote the event type set contained in P as SetP. For each P, we calculate the number of remaining patterns P′P′∈P whose event type set SetP′ is the superset of SetP. ACS is obtained by averaging this number for all patterns in the pattern set. For each pattern, the less patterns whose event type set is its superset, the less redundant the pattern is. Therefore, the smaller the ACS is, the more diverse the event types are and the less redundant the pattern set is.(3)
Number of patterns (No.P): this metric measures the number of discovered patterns.(4)
Average length of patterns (AL): this metric measures the average length of the discovered patterns.Table4 reports the results of four evaluation metrics on different datasets, respectively. As is shown, our approach has a larger intersequence edit distance and a smaller count of supersets on average, which indicate that the patterns generated by our approach have lower redundancy and higher diversity. In terms of the number of patterns, DTS has relatively small No.P values while ensuring adequate coverage of event types and a high level of compression. Overall, the pattern sets discovered by DTS can express the meaningful information of a log sequence with low redundancy.Table 4
Redundancy metrics on different datasets.
NameNodeDataNodeZookeeperOpenStackAEDACSNo. PALAEDACSNo. PALAEDACSNo. PALAEDACSNo. PALDTS0.5381.423529.8460.7510.455336.8180.4460.936476.2550.9110.62587.250SQS0.28222.7583896.4190.30915.3962024.1680.28033.7032395.6780.20115.7612897.467CSC0.28414.5911597.8810.2483.436558.1090.3635.0751074.9720.09112.2699328.548GoKrimp0.4761.569513.0390.5171.333182.6670.4720.955442.6590.4161.417363.250ISM0.3221.9861416.9010.3661.0871036.2140.3572.2011595.1450.4531.273333.333Among the four rival algorithms, GoKrimp yields relatively good performance, generating the smallest number of patterns with relatively low redundancy. However, as was previously shown, the expressiveness of GoKrimp is generally the worst among all methods. As a matter of fact, the search strategy of GoKrimp acts as a double-edged sword. On the one hand, it helps achieve compact results. On the other hand, it limits GoKrimp’s ability to mine meaningful patterns. Overall, this tradeoff is not desirable in practice. As with ISM, it has reasonableAED and ACS values, yet it is inferior when compared against DTS. By contrast, the results of CSC on the Zookeeper and DataNode logs are less redundant, which again manifests the effectiveness of CSC for such type of log data. However, on the NameNode and OpenStack logs, the redundancy of CSC is high. Especially, the values of ACS are more than 10, namely, each combination of event types generates more than 10 patterns on average. As for SQS, it has a high degree of redundancy on every type of log data. This is because the encoding scheme of SQS only considers the support of the patterns and does not fully take into account the temporal regularity. Therefore, any sequential pattern generated by frequent behaviors can result in good compression, which leads to many redundant patterns.


## 5.1. Datasets and Settings

### 5.1.1. Datasets

We use four different log datasets collected from real systems. The basic statistics of these datasets are summarized in Table2. The Zookeeper and OpenStack datasets are collected from the well-known loghub data repository [15], while the NameNode and DataNode logs are collected from our own HDFS cluster.Table 2
Basic statistics of four log datasets.
Log type# log entries# event types%suppE≤50NameNode600,00018075%DataNode1,000,00010688%Zookeeper74,3808568%OpenStack91,447362%These datasets have different characteristics. The NameNode logs have more event types and more complex system behaviors interleaving together as a NameNode manages multiple DataNodes. The DataNode and Zookeeper logs have less event types as well as simpler and more regular behaviors. The OpenStack logs contain only behaviors such as creating a project and other simple tasks, thus having the least event types.For each log dataset, we calculate the ratio of event types which occur less than 50 times. As is shown in Table2, three out of four datasets contain a high percentage of low-support event types (more than 65%). To discover nontrivial patterns in these datasets effectively, we need to set the support threshold to a low value, which can lead to the pattern explosion problem. We will later show that DTS can discover nontrivial patterns while maintaining a low level of redundancy.


### 5.1.2. Rival Approaches

We compare our approach against four approaches, GoKrimp [9], SQS [12], CSC [11], and ISM [16]. The first three approaches use the MDL principle [10] to discover patterns, while ISM is a probabilistic machine learning approach. We have not included SeqKrimp [9] in our experiments because GoKrimp yields similar results and is more efficient than SeqKrimp. For CSC and our approach, we simply use the entire sequence as the input. For other approaches, the sequences are broken into disjoint sequences of size 10. Our algorithms are implemented in Java, while the implementations of other approaches are obtained from the original authors.


## 5.1.1. Datasets

We use four different log datasets collected from real systems. The basic statistics of these datasets are summarized in Table2. The Zookeeper and OpenStack datasets are collected from the well-known loghub data repository [15], while the NameNode and DataNode logs are collected from our own HDFS cluster.Table 2
Basic statistics of four log datasets.
Log type# log entries# event types%suppE≤50NameNode600,00018075%DataNode1,000,00010688%Zookeeper74,3808568%OpenStack91,447362%These datasets have different characteristics. The NameNode logs have more event types and more complex system behaviors interleaving together as a NameNode manages multiple DataNodes. The DataNode and Zookeeper logs have less event types as well as simpler and more regular behaviors. The OpenStack logs contain only behaviors such as creating a project and other simple tasks, thus having the least event types.For each log dataset, we calculate the ratio of event types which occur less than 50 times. As is shown in Table2, three out of four datasets contain a high percentage of low-support event types (more than 65%). To discover nontrivial patterns in these datasets effectively, we need to set the support threshold to a low value, which can lead to the pattern explosion problem. We will later show that DTS can discover nontrivial patterns while maintaining a low level of redundancy.


## 5.1.2. Rival Approaches

We compare our approach against four approaches, GoKrimp [9], SQS [12], CSC [11], and ISM [16]. The first three approaches use the MDL principle [10] to discover patterns, while ISM is a probabilistic machine learning approach. We have not included SeqKrimp [9] in our experiments because GoKrimp yields similar results and is more efficient than SeqKrimp. For CSC and our approach, we simply use the entire sequence as the input. For other approaches, the sequences are broken into disjoint sequences of size 10. Our algorithms are implemented in Java, while the implementations of other approaches are obtained from the original authors.


## 5.2. Evaluation of Efficiency

In the first experiment, we compare the efficiencies of all approaches as the length of the log sequences varies on the NameNode and DataNode datasets. The results are shown in Figure7. It is worth noting that although the results of all 5 approaches are plotted in the same figures, the time unit for CSC, GoKrimp, and our approach is in seconds, while that for SQS and ISM is in minutes.Figure 7
Running time on varying length sequences. (a) NameNode. (b) DataNode.
(a)(b)As is shown, CSC is the faster than all other approaches because it has a gap constraint which restricts the size of the search space greatly. However, this constraint dictates that CSC cannot find complex patterns effectively, which will be shown in the next experiment. DTS is slower than GoKrimp as GoKrimp applies a dependency test for speedup. Nonetheless, this prevents GoKrimp from discovering low-frequency patterns.Although DTS takes comparatively longer time, it only needs less than 400 seconds to process a complex sequence with 600,000 events, which is acceptable in real applications. Besides, the running time of DTS increases steadily with the increase of log size, indicating good scalability. On the contrary, SQS and ISM are much slower, with processing times ranging from dozens of minutes to several hours due to their complex iterative computations.The running times on the Zookeeper and OpenStack datasets are shown in Table3, which shows similar results to those on the NameNode and DataNode logs. CSC is still the most efficient, while DTS comes next.Table 3
Running time on the Zookeeper and OpenStack logs (in seconds).
DTSSQSCSCGoKrimpISMZookeeper1966620452040OpenStack19315781523159


## 5.3. Evaluation of Pattern Quality

In this section, we analyze the quality of the patterns returned by different approaches from three aspects: the compression ratioCR, the event coverage EC, and the redundancy among different patterns.


### 5.3.1. Evaluation of the Compression Ratio

According to the MDL principle, we can encode the sequence with the discovered pattern set. The smaller the description lengthLS,P is, the stronger the expressiveness of the encoding pattern set is. Here, we use compression ratio [9] (denoted as CR) to measure the effectiveness of the encoding. CR is defined as the ratio of the description length of the encoding with only singleton patterns to that with the discovered patterns. The higher the ratio is, the better the expressiveness is. Note that here we only compare the compression ratios for MDL-based approaches.Figure8 shows the compression ratios on all four datasets. As indicated, DTS generally achieves the best compression ratio, thanks to our effective encoding scheme as well as the proposed refinement operations and the heuristic strategy based on the “event conflict.” Among the other 3 comparison algorithms, the iterative searching strategy of GoKrimp is too simple to yield expressive results. Therefore, it generally achieves the lowest compression ratio. CSC has a good performance on the DataNode and Zookeeper logs, yielding similar performance to DTS. This can be attributed to the fact that CSC is suitable for processing log data in which the time intervals between adjacent events are short and constant. On the contrary, for log sequences such as NameNode logs which contain complex patterns, CSC tends to perform poorly. As with SQS, thanks to its complex search strategy, it performs well on more complex data. The problem with SQS is that it generates too many patterns, and thus, the model used to describe the data is too complicated, resulting in greater description length. This can negatively impact the compression ratio of SQS, especially when the patterns in the log data are simple.Figure 8
Compression ratios on different datasets.It is worth noting that while our approach has generally higher compression ratios, this does not mean that it results in more redundancies, on which we will discuss later.


### 5.3.2. Evaluation of the Event Coverage

In this section, we evaluate whether the patterns returned by different approaches cover various event types adequately. We use the event coverage [17] (denoted as EC) as the metric, which measures the percentage of event types covered by the discovered patterns. A larger EC indicates better performance.Figure9 demonstrates the event coverage of all 5 approaches on the four log datasets. As is shown, except for GoKrimp, all other approaches have event coverage over 80%. By contrast, while GoKrimp achieves an EC of 91% on the OpenStack dataset, it fails to achieve an EC of over 50% on the remaining datasets. This is related to the proportion of rare event types in the log data. As was mentioned before, the search heuristic of GoKrimp is oversimplified, which prevents GoKrimp from discovering patterns with infrequent event types. Therefore, the more infrequent event types contained in the log data, the lower the event coverage of GoKrimp is. By contrast, this factor has little effect on the other five algorithms.Figure 9
Event coverage on different datasets.Overall, our DTS achieves the best coverage on the three of the four log datasets. However, it is slightly inferior to SQS and CSC on the OpenStack logs. This is because there are three event types in the OpenStack dataset which occur randomly in the sequence, exhibiting no significant temporal regularity. Therefore, DTS does not consider these event types as part of any pattern, while CSC and SQS greedily include these event types in some patterns. This showcases the advantage of DTS, which takes the temporal regularities of patterns into consideration, reducing the number of invalid patterns made up of random combinations of unrelated events. This can lead to a far less redundant result than CSC and SQS.


### 5.3.3. Evaluation of the Pattern Redundancy

The goal of this work is to mine high-quality and low-redundancy pattern sets from log sequences. In previous sections, we have evaluated the pattern qualities using compression rate and event type coverage. We now shift our attention to the evaluation of pattern redundancy. Here, we utilize the following four metrics:(1)
Average intersequence edit distance (AED): this metric measures the edit similarity among the discovered patterns. Concretely, the AED of a pattern set is calculated as follows: for each pattern P in set P, we calculate the edit distance between P and each of the remaining discovered patterns P′P′∈P and normalize the distance with the pattern P’s length. We record the minimum distance between P and all other patterns. AED is obtained by averaging these minimum distances for all patterns in the pattern set. The larger the distance is, the less redundant the pattern set is.(2)
Average count of supersets (ACS): this metric measures the diversity of the event types contained in the discovered pattern set. Concretely, the ACS of a pattern set is calculated as follows: for each pattern P in P, we denote the event type set contained in P as SetP. For each P, we calculate the number of remaining patterns P′P′∈P whose event type set SetP′ is the superset of SetP. ACS is obtained by averaging this number for all patterns in the pattern set. For each pattern, the less patterns whose event type set is its superset, the less redundant the pattern is. Therefore, the smaller the ACS is, the more diverse the event types are and the less redundant the pattern set is.(3)
Number of patterns (No.P): this metric measures the number of discovered patterns.(4)
Average length of patterns (AL): this metric measures the average length of the discovered patterns.Table4 reports the results of four evaluation metrics on different datasets, respectively. As is shown, our approach has a larger intersequence edit distance and a smaller count of supersets on average, which indicate that the patterns generated by our approach have lower redundancy and higher diversity. In terms of the number of patterns, DTS has relatively small No.P values while ensuring adequate coverage of event types and a high level of compression. Overall, the pattern sets discovered by DTS can express the meaningful information of a log sequence with low redundancy.Table 4
Redundancy metrics on different datasets.
NameNodeDataNodeZookeeperOpenStackAEDACSNo. PALAEDACSNo. PALAEDACSNo. PALAEDACSNo. PALDTS0.5381.423529.8460.7510.455336.8180.4460.936476.2550.9110.62587.250SQS0.28222.7583896.4190.30915.3962024.1680.28033.7032395.6780.20115.7612897.467CSC0.28414.5911597.8810.2483.436558.1090.3635.0751074.9720.09112.2699328.548GoKrimp0.4761.569513.0390.5171.333182.6670.4720.955442.6590.4161.417363.250ISM0.3221.9861416.9010.3661.0871036.2140.3572.2011595.1450.4531.273333.333Among the four rival algorithms, GoKrimp yields relatively good performance, generating the smallest number of patterns with relatively low redundancy. However, as was previously shown, the expressiveness of GoKrimp is generally the worst among all methods. As a matter of fact, the search strategy of GoKrimp acts as a double-edged sword. On the one hand, it helps achieve compact results. On the other hand, it limits GoKrimp’s ability to mine meaningful patterns. Overall, this tradeoff is not desirable in practice. As with ISM, it has reasonableAED and ACS values, yet it is inferior when compared against DTS. By contrast, the results of CSC on the Zookeeper and DataNode logs are less redundant, which again manifests the effectiveness of CSC for such type of log data. However, on the NameNode and OpenStack logs, the redundancy of CSC is high. Especially, the values of ACS are more than 10, namely, each combination of event types generates more than 10 patterns on average. As for SQS, it has a high degree of redundancy on every type of log data. This is because the encoding scheme of SQS only considers the support of the patterns and does not fully take into account the temporal regularity. Therefore, any sequential pattern generated by frequent behaviors can result in good compression, which leads to many redundant patterns.


## 5.3.1. Evaluation of the Compression Ratio

According to the MDL principle, we can encode the sequence with the discovered pattern set. The smaller the description lengthLS,P is, the stronger the expressiveness of the encoding pattern set is. Here, we use compression ratio [9] (denoted as CR) to measure the effectiveness of the encoding. CR is defined as the ratio of the description length of the encoding with only singleton patterns to that with the discovered patterns. The higher the ratio is, the better the expressiveness is. Note that here we only compare the compression ratios for MDL-based approaches.Figure8 shows the compression ratios on all four datasets. As indicated, DTS generally achieves the best compression ratio, thanks to our effective encoding scheme as well as the proposed refinement operations and the heuristic strategy based on the “event conflict.” Among the other 3 comparison algorithms, the iterative searching strategy of GoKrimp is too simple to yield expressive results. Therefore, it generally achieves the lowest compression ratio. CSC has a good performance on the DataNode and Zookeeper logs, yielding similar performance to DTS. This can be attributed to the fact that CSC is suitable for processing log data in which the time intervals between adjacent events are short and constant. On the contrary, for log sequences such as NameNode logs which contain complex patterns, CSC tends to perform poorly. As with SQS, thanks to its complex search strategy, it performs well on more complex data. The problem with SQS is that it generates too many patterns, and thus, the model used to describe the data is too complicated, resulting in greater description length. This can negatively impact the compression ratio of SQS, especially when the patterns in the log data are simple.Figure 8
Compression ratios on different datasets.It is worth noting that while our approach has generally higher compression ratios, this does not mean that it results in more redundancies, on which we will discuss later.


## 5.3.2. Evaluation of the Event Coverage

In this section, we evaluate whether the patterns returned by different approaches cover various event types adequately. We use the event coverage [17] (denoted as EC) as the metric, which measures the percentage of event types covered by the discovered patterns. A larger EC indicates better performance.Figure9 demonstrates the event coverage of all 5 approaches on the four log datasets. As is shown, except for GoKrimp, all other approaches have event coverage over 80%. By contrast, while GoKrimp achieves an EC of 91% on the OpenStack dataset, it fails to achieve an EC of over 50% on the remaining datasets. This is related to the proportion of rare event types in the log data. As was mentioned before, the search heuristic of GoKrimp is oversimplified, which prevents GoKrimp from discovering patterns with infrequent event types. Therefore, the more infrequent event types contained in the log data, the lower the event coverage of GoKrimp is. By contrast, this factor has little effect on the other five algorithms.Figure 9
Event coverage on different datasets.Overall, our DTS achieves the best coverage on the three of the four log datasets. However, it is slightly inferior to SQS and CSC on the OpenStack logs. This is because there are three event types in the OpenStack dataset which occur randomly in the sequence, exhibiting no significant temporal regularity. Therefore, DTS does not consider these event types as part of any pattern, while CSC and SQS greedily include these event types in some patterns. This showcases the advantage of DTS, which takes the temporal regularities of patterns into consideration, reducing the number of invalid patterns made up of random combinations of unrelated events. This can lead to a far less redundant result than CSC and SQS.


## 5.3.3. Evaluation of the Pattern Redundancy

The goal of this work is to mine high-quality and low-redundancy pattern sets from log sequences. In previous sections, we have evaluated the pattern qualities using compression rate and event type coverage. We now shift our attention to the evaluation of pattern redundancy. Here, we utilize the following four metrics:(1)
Average intersequence edit distance (AED): this metric measures the edit similarity among the discovered patterns. Concretely, the AED of a pattern set is calculated as follows: for each pattern P in set P, we calculate the edit distance between P and each of the remaining discovered patterns P′P′∈P and normalize the distance with the pattern P’s length. We record the minimum distance between P and all other patterns. AED is obtained by averaging these minimum distances for all patterns in the pattern set. The larger the distance is, the less redundant the pattern set is.(2)
Average count of supersets (ACS): this metric measures the diversity of the event types contained in the discovered pattern set. Concretely, the ACS of a pattern set is calculated as follows: for each pattern P in P, we denote the event type set contained in P as SetP. For each P, we calculate the number of remaining patterns P′P′∈P whose event type set SetP′ is the superset of SetP. ACS is obtained by averaging this number for all patterns in the pattern set. For each pattern, the less patterns whose event type set is its superset, the less redundant the pattern is. Therefore, the smaller the ACS is, the more diverse the event types are and the less redundant the pattern set is.(3)
Number of patterns (No.P): this metric measures the number of discovered patterns.(4)
Average length of patterns (AL): this metric measures the average length of the discovered patterns.Table4 reports the results of four evaluation metrics on different datasets, respectively. As is shown, our approach has a larger intersequence edit distance and a smaller count of supersets on average, which indicate that the patterns generated by our approach have lower redundancy and higher diversity. In terms of the number of patterns, DTS has relatively small No.P values while ensuring adequate coverage of event types and a high level of compression. Overall, the pattern sets discovered by DTS can express the meaningful information of a log sequence with low redundancy.Table 4
Redundancy metrics on different datasets.
NameNodeDataNodeZookeeperOpenStackAEDACSNo. PALAEDACSNo. PALAEDACSNo. PALAEDACSNo. PALDTS0.5381.423529.8460.7510.455336.8180.4460.936476.2550.9110.62587.250SQS0.28222.7583896.4190.30915.3962024.1680.28033.7032395.6780.20115.7612897.467CSC0.28414.5911597.8810.2483.436558.1090.3635.0751074.9720.09112.2699328.548GoKrimp0.4761.569513.0390.5171.333182.6670.4720.955442.6590.4161.417363.250ISM0.3221.9861416.9010.3661.0871036.2140.3572.2011595.1450.4531.273333.333Among the four rival algorithms, GoKrimp yields relatively good performance, generating the smallest number of patterns with relatively low redundancy. However, as was previously shown, the expressiveness of GoKrimp is generally the worst among all methods. As a matter of fact, the search strategy of GoKrimp acts as a double-edged sword. On the one hand, it helps achieve compact results. On the other hand, it limits GoKrimp’s ability to mine meaningful patterns. Overall, this tradeoff is not desirable in practice. As with ISM, it has reasonableAED and ACS values, yet it is inferior when compared against DTS. By contrast, the results of CSC on the Zookeeper and DataNode logs are less redundant, which again manifests the effectiveness of CSC for such type of log data. However, on the NameNode and OpenStack logs, the redundancy of CSC is high. Especially, the values of ACS are more than 10, namely, each combination of event types generates more than 10 patterns on average. As for SQS, it has a high degree of redundancy on every type of log data. This is because the encoding scheme of SQS only considers the support of the patterns and does not fully take into account the temporal regularity. Therefore, any sequential pattern generated by frequent behaviors can result in good compression, which leads to many redundant patterns.


## 6. Related Work

As an important data source for system management, logs have been widely used in many tasks such as anomaly detectionbib13[5, 13], program workflow modeling [1], failure diagnosis [18], and performance monitoring [19]. These works mostly focus on automatic system maintenance and diagnosis through log analysis. In this paper, we aim at discovering meaningful patterns from raw log sequences. The discovered patterns can provide useful information that can support the aforementioned tasks.Sequential pattern mining was first introduced by Agrawal and Srikant [6]. Since then, various sequential pattern mining algorithms have been proposed, such as PrefixSpan [20], SPAM [21], and BIDE [7]. Traditional pattern mining approaches usually generate a huge number of redundant patterns. This problem is commonly known as pattern explosion. Several restrictions on pattern semantics have been proposed to tackle this problem, such as closed frequent patterns [22] and maximal frequent patterns [23]. However, these measures do not fully resolve the problem. In order to reduce pattern redundancy, modern sequential pattern mining approaches resort to the minimum description length (MDL) principle [10] to select a set of patterns that can best compress the data. KRIMP [24] pioneered the use of MDL in identifying good pattern sets, which mines itemsets that can well describe a transaction database. GoKrimp [9], SQS [12], and CSC [11] extend this methodology to the sequential pattern mining task. The basic idea of these approaches is to cover a sequence database with a set of patterns that can achieve the highest compression. Jianxin Li [25] proposed a parallel approach FCT to efficiently find frequent co-occurring terms in relational data.However, these existing approaches do not take the temporal regularity of timestamped sequences into consideration. By comparison, our approaches can achieve better results by utilizing the event relationships in a pattern as well as the temporal regularities among events and are capable of discovering informative patterns with low redundancy. Instead of designing a MDL-based encoding scheme, ISM [16] presents a subsequence interleaving method based on a probabilistic model of the sequence database, which searches for the most compressed set of patterns. However, this approach, along with the aforementioned SQS, is slow according to our experiments due to its exhaustive nature.


## 7. Conclusions

In this paper, we have proposed a novel approach to discover sequential patterns from log sequences with temporal regularities, which process the log data in a black-box manner and do not need any domain knowledge on the system. Specifically, we have drawn on the MDL principle and formalized an encoding scheme that takes event relationships as well as temporal regularities into consideration. Based on this scheme, we have proposed DTS, an efficient heuristic algorithm, which greedily updates the pattern set. Extensive experiments on real datasets show that the proposed approaches can discover high-quality patterns efficiently.



---

*Source: 6628165-2020-12-01.xml*