Source-linked AI summary
Logram: Efficient Log Parsing Using n-Gram Dictionaries
Hetong Dai, Heng Li, Weiyi Shang, Tse-Hsun Chen, Che-Shao Chen
TL;DR
Large, growing logs make efficient parsing important, but parsing is difficult when source-code templates are unavailable. Logram uses n-gram dictionaries to identify static and dynamic content; on 16 datasets it was faster than comparison approaches while achieving higher accuracy, and it also supported scalable and online parsing.
Problem
Log parsing must recover templates and variables from raw logs even though source-code templates are often inaccessible, and growing log volumes make efficiency important.
Source: §2.1 · p. 2, §1 · p. 2Method
Logram stores n-gram frequencies in dictionaries and uses them to distinguish static text from dynamic variables.
Source: §1 · p. 2Results
On 16 datasets, Logram was 1.8 to 5.1 times faster than the second-fastest approaches and achieved higher accuracy than the best existing approaches.
Source: §1 · p. 2Takeaways & Limitations
Logram’s dictionaries can be constructed in parallel and updated online, supporting scalable parsing and streaming scenarios.
Source: §8 · p. 11The evaluation covers 16 benchmark datasets, and the authors cannot ensure high accuracy on other log datasets not tested.
Source: §7 · p. 10
Abstract
from arXiv · showhide
Software systems usually record important runtime information in their logs. Logs help practitioners understand system runtime behaviors and diagnose field failures. As logs are usually very large in size, automated log analysis is needed to assist practitioners in their software operation and maintenance efforts. Typically, the first step of automated log analysis is log parsing, i.e., converting unstructured raw logs into structured data. However, log parsing is challenging, because logs are produced by static templates in the source code (i.e., logging statements) yet the templates are usually inaccessible when parsing logs. Prior work proposed automated log parsing approaches that have achieved high accuracy. However, as the volume of logs grows rapidly in the era of cloud computing, efficiency becomes a major concern in log parsing. In this work, we propose an automated log parsing approach, Logram, which leverages n-gram dictionaries to achieve efficient log parsing. We evaluated Logram on 16 public log datasets and compared Logram with five state-of-the-art log parsing approaches. We found that Logram achieves a similar parsing accuracy to the best existing approaches while outperforms these approaches in efficiency (i.e., 1.8 to 5.1 times faster than the second fastest approaches). Furthermore, we deployed Logram on Spark and we found that Logram scales out efficiently with the number of Spark nodes (e.g., with near-linear scalability) without sacrificing parsing accuracy. In addition, we demonstrated that Logram can support effective online parsing of logs, achieving similar parsing results and efficiency with the offline mode.
1 INTRODUCTION
Logram parses logs with n-gram dictionaries because growing log volumes and demand for low-latency analysis make efficiency important. On 16 datasets, it was faster than state-of-the-art approaches while achieving higher accuracy, and it also supports Spark scalability and online parsing.
1 INTRODUCTION
- Logram stores n-gram frequencies in dictionaries, treating frequent n-grams as more likely static text and rare ones as more likely dynamic variables.The dictionaries can be constructed in O(n) and queried in O(1).Source: §1 · p. 2
- The approach targets the efficiency concern raised by rapidly growing log sizes and increasing demand for low-latency log analysis.Logs support runtime understanding and failure diagnosis, but may reach tens or hundreds of gigabytes.Source: §1 · pp. 1–2
- On 16 datasets, Logram was 1.8 to 5.1 times faster than the second-fastest approaches and achieved higher accuracy than the best existing approaches.The evaluation compared Logram with five state-of-the-art log parsing approaches.Source: §1 · p. 2
- Logram scales out on Spark with near-linear scalability for some logs without sacrificing parsing accuracy.The paper also reports that online parsing achieves results and efficiency similar to offline parsing.Source: §1 · p. 2
- Logram automatically determines an n-gram occurrence threshold to distinguish static and dynamic parts of log messages.Source: §1 · p. 2
2 BACKGROUND
Log parsing extracts static templates and dynamic variables from raw logs, while n-grams provide the basis for Logram’s frequency-based approach. The section introduces the parsing challenge and n-gram properties relevant to the method.
2.1 Log Parsing
- Parsing must separate static templates from changing variables, although source-code logging templates are often inaccessible and log vocabularies are large.The goal also includes extracting header information such as timestamp, level, and logger.Source: §2.1 · p. 2
- Regular expressions require substantial effort to develop and maintain across large, evolving collections of log templates.Modern systems can contain tens of thousands of templates.Source: §2.1 · p. 2
2.2 n-grams
- An n-gram is a subsequence of length n; Logram uses n-gram frequencies because frequent sequences are more likely static text and rare ones more likely dynamic variables.N-gram dictionaries can be constructed in parallel and updated online as logs arrive.Source: §2.2 · p. 3
3 RELATED WORK
This section surveys log-parsing approaches and their use in log analysis tasks. It covers rule-based, source-code-based, and data-mining methods, then relates parsing accuracy and efficiency to downstream analysis.
3.1 Prior Work on Log Parsing
- Prior log parsers include hand-crafted rules, source-code extraction of templates, frequency-based mining, and clustering or other data-mining approaches.Rule-based methods require effort to maintain evolving rules, while source-code methods depend on access to logging statements.Source: §3.1 · p. 3
- Drain had the best accuracy and efficiency in a prior evaluation, while Logram is reported to parse faster with comparable accuracy.Source: §3.1 · p. 4
3.2 Applications of Log Parsing
- Log parsing is a prerequisite for tasks including anomaly detection and failure diagnosis, and its accuracy is critical to successful log analysis.High parser efficiency is also important for timely analysis as log files grow.Source: §3.2 · p. 4
4 APPROACH
Logram builds dictionaries of n-gram frequencies, then uses those frequencies to distinguish static text from dynamic variables and generate log templates.
4.1 Overview of Logram
- Logram has two steps: build n-gram frequency dictionaries from logs, then parse messages using those dictionaries.Each message is converted into n-grams whose occurrence counts inform the static-versus-dynamic distinction.Source: §4.1 · p. 4
4.2.1 Pre-processing logs
- A regular expression extracts log content and common headers, whitespace splits content into tokens, and LogPai expressions identify common dynamic formats.The expressions for common dynamic formats come from the LogPai benchmark.Source: §4.2.1 · p. 4
4.2.2 Generating an n-gram dictionary
- 2-grams and 3-grams balance dynamic-variable repetition against message-specific phrases; neighboring-message tokens are included to reduce boundary bias.The dictionary records each n-gram’s occurrence count, including n-grams that cross message boundaries.Source: §4.2.2 · pp. 4–5
4.3.1 Identifying n-grams that may contain dynamic variables
- Low-frequency n-grams are recursively shortened until low-frequency 2-grams remain as candidates for containing dynamic variables.The running example illustrates this dictionary-based parsing process.Source: §4.3.1 · p. 5, Figure 3 · p. 5
4.3.2 Identifying dynamically and statically generated tokens
- A token is identified as dynamic when it occurs in two low-frequency 2-grams, one ending with it and one beginning with it; other tokens are treated as static.For message-boundary tokens, additional n-grams combine them with neighboring messages to address under-counting.Source: §4.3.2 · pp. 5–6
4.3.3 Automatically determining the threshold of n-gram occurrences
- The occurrence threshold is estimated by smoothing the frequency distribution with loess and clustering its derivatives to find a breakpoint.The breakpoint separates derivative groups associated with static and dynamic n-grams.Source: §4.3.3 · p. 6
4.3.4 Generating log templates
- Logram generates templates from the tokens classified as static or dynamic, using the LogPai benchmark’s template format.The example converts “Found block rdd 42 20 locally” into “Found block $1 locally, $1=rdd 42 20”.Source: §4.3.4 · p. 6
5 EVALUATION
The evaluation compares Logram with five established parsers across LogPai benchmark logs, assessing accuracy, efficiency, stabilization, and scalability.
5 EVALUATION
- The evaluation measures parsing accuracy, efficiency, ease of stabilization, and scalability against Drain, Spell, AEL, Lenma, and IPLoM.These five parsers were selected based on a prior benchmark finding that they had the highest accuracy and efficiency among evaluated parsers.Source: §5 · p. 6
5.1 Subject log data
- LogPai benchmark datasets cover open-source and industrial systems across domains; 2,000 labeled messages per dataset support accuracy evaluation, while full logs support the other measures.The subject-data table presents the datasets used.Source: §5.1 · p. 6, Table 2 · p. 6
5.2 Accuracy
- Parsing accuracy requires correct identification of all static text and dynamic variables, not merely grouping messages by event template.The authors manually check whether each message’s static and dynamic components are correctly parsed.Source: §5.2 · p. 7
Results
Logram’s accuracy exceeds or matches existing parsers across the evaluated datasets, while the authors identify several recurring sources of parsing errors.
Results
- 0.825 average parsing accuracy for Logram versus 0.748 for Drain, with Logram best or above 0.9 on 12 of 16 datasets.The accuracy table compares Logram with other parsers across the 16 datasets.Source: Results · p. 7
- Grouping messages correctly can still miss dynamic-variable boundaries; Spell’s Hadoop host-name parsing illustrates this distinction.Spell’s parsing accuracy on Hadoop logs is 0.192 despite grouping messages with the same host-name string together.Source: Results · p. 7
- Logram’s reported error sources are mis-split tokens, preprocessing errors, and frequently appearing dynamic values that resemble static text.For a property-file path that never changes in the logs, practitioners can include contextual information in preprocessing.Source: Results · p. 7
5.3 Efficiency
The efficiency evaluation measures end-to-end parsing time across five datasets and varied input sizes; Logram is faster than the compared parsers and remains stable through 1 GB.
5.3 Efficiency
- The test uses random chunks from Android, BGL, HDFS, Windows, and Spark logs, ranging from 300 KB to 1 GB, on a specified desktop system.The comparison includes Drain, Spell, and AEL, selected for high accuracy and prior benchmark efficiency.Source: §5.3 · pp. 7–8
Results
- 1.8 to 5.1 times faster than the second-fastest approaches across five datasets and varied sizes, including dictionary construction in elapsed time.Figure 4 plots parsing time against log-data size with both axes on a log scale.Source: Figure 4 · p. 8, Results · p. 8
- For studied logs up to 1 GB, increasing input size 1,000-fold increased Logram’s running time by a factor of 773 to 1039.The authors attribute this stability to consistent n-gram lookup time as dictionary size changes.Source: Results · p. 8
- Lenma could not finish parsing 500 MB or 1 GB datasets within hours, while Spell crashed on 1 GB Windows and Spark logs due to memory issues.Drain did not show lower efficiency on larger logs in this evaluation.Source: Results · p. 8
5.4 Ease of stabilisation
Logram’s dictionary can produce parsing results that closely agree with those obtained using all logs, even when built from a small portion of the data. The section also describes its Spark-based scalability evaluation.
5.4 Ease of stabilisation
- The stabilization evaluation built dictionaries from the first 5% of logs, then added logs in 5% increments until agreement reached 100%.It covered 14 datasets, excluding the two largest, Windows and Thunderbird; agreement required identical parsing results for each message.Source: §5.4 · p. 8
Results
- Five other datasets contained periods with drastically different events, lowering agreement until the dictionary learned n-grams from those periods.The authors suggest monitoring parsing results to identify when the dictionary may need updating.Source: Results · p. 9
- In 9 of 14 datasets, a dictionary built from less than 30% of the logs yielded over 90% agreement; Spark reached 95.5% using the first 5%.Agreement is measured against parsing with a dictionary generated from all logs.Source: Results · p. 8, Figure 5 · p. 9
5.5 Scalability
- Logram’s Spark implementation builds n-gram dictionaries in a word-count-style step and parses each log message independently.The dictionary-building and parsing steps are migrated to Spark separately.Source: §5.5 · p. 9
- The scalability evaluation measured parsing throughput on a Spark cluster using 1–5 workers, or 4–20 cores; Figure 6 plots running times across core counts.The evaluation repeated throughput measurements 10 times per dataset.Source: Figure 6 · p. 9, §5.5 · p. 9
Results
Logram’s Spark throughput increased nearly linearly for some logs, while scalability varied by dataset; parsing accuracy remained unchanged as nodes increased.
Results
- Throughput rose by up to 5.7 times when Spark nodes increased fivefold, with parsing accuracy unchanged.The authors report near-linear scalability for some logs, but less scalability for others.Source: Results · pp. 9–10
- Throughput measurements had low variance across 10 repeated runs for each log dataset.Figure 6 presents throughput as box plots.Source: Results · p. 9
- Increasing Logram from one node to five increased throughput 5.7 to 4.8 times for HDFS and Windows, respectively, indicating near-linear or even super-linear scalability; BGL and Spark rose 3.3 and 2.7 times.Source: Results · p. 10
6 MIGRATING Logram TO AN ONLINE PARSER
The online version updates Logram’s n-gram dictionary as log messages arrive, rather than requiring all logs before parsing. It produced nearly the same parsing results and efficiency as offline Logram.
6 MIGRATING Logram TO AN ONLINE PARSER
- Unlike offline Logram, which requires all dictionary-building logs before parsing, an online parser processes incoming logs line by line.The paper identifies real-time log streaming as a setting where online parsing is helpful.Source: §6 · p. 10
- Online Logram parses each message with the existing dictionary, then updates that dictionary using the message’s tokens.The first message is parsed with an empty dictionary before Logram creates a dictionary from its n-grams.Source: §6 · p. 10
Results
- Online and offline parsing agreed on 95.0%–100.0% of results, while their efficiency difference ratio ranged from -3.0% to 8.9%.The comparison used five large datasets; positive efficiency difference means online parsing took longer.Source: Table 4 · p. 10, Results · p. 10
- The authors conclude that online Logram can parse streaming logs in real time with results and efficiency similar to offline Logram.In some cases, online parsing was faster because smaller, incomplete dictionaries were quicker to query.Source: Results · p. 10
7 THREATS TO VALIDITY
The authors identify limits to generalizing accuracy, optimizing thresholds, and comparing Logram with all existing parsers.
7 THREATS TO VALIDITY
- Logram’s accuracy exceeded 0.9 on about half of 16 benchmark datasets, and the authors cannot ensure high accuracy on untested logs.The evaluation used datasets from 16 systems across different domains.Source: §7 · p. 10
- Automatically generated thresholds may not be optimal, so the reported accuracy may be below what Logram could achieve with further threshold optimization.Source: §7 · p. 11
- The comparison omitted some parsers, including LKE, because manually verifying each approach’s accuracy requires substantial human effort.The authors compared against five existing approaches and selected best-performing parsers evaluated in a recent benchmark.Source: §7 · p. 11
8 CONCLUSION
Logram uses n-gram dictionaries for efficient log parsing, with parallel dictionary construction and online updates. Evaluation on 16 public datasets supports its accuracy, efficiency, scalability, and online-parsing performance.
8 CONCLUSION
- Logram outperforms state-of-the-art approaches in efficiency and achieves better parsing accuracy than existing approaches.The evaluation covered 16 public log datasets.Source: §8 · p. 11
- Parallel dictionary construction and online updates support parsing continuously generated logs with results and efficiency similar to offline mode.The paper also reports parallel construction without sacrificing parsing accuracy.Source: §8 · p. 11
- Logram achieved high accuracy and efficiency while parsing logs in a stable and scalable manner across the evaluation.Source: §8 · p. 11
- The paper presents Logram as the first work to use n-grams in log analysis.Source: §8 · p. 11