Logs often take up the majority of a company's data assets. Examples of logs include business logs (such as user activity logs), and Operation & Maintenance logs of servers, databases, and network or IoT devices. Logs are the guardian angel of business. On the one hand, they provide system risk alerts and help engineers in troubleshooting. On the other hand, if you zoom them out by time range, you might identify some helpful trends and patterns, not to mention that business logs are the cornerstone of user insights. However, logs can be a handful, because: Every system event or click from user generates a log. A company often produces tens of billions of new logs per day. They flow in like crazy. Logs are supposed to stay. They might not be useful until they are. So a company can accumulate up to PBs of log data, many of which are seldom visited but take up huge storage space. They are bulky. Locating the target log for troubleshooting is literally like looking for a needle in a haystack. People long for real-time log writing and real-time responses to log queries. They must be quick to load and find. Now you can see a clear picture of what an ideal log processing system is like. It should support: It should be able to write blogs in bulk, and make them visible immediately. High-throughput real-time data ingestion: It should be able to store substantial amounts of logs without costing too many resources. Low-cost storage: It should be capable of quick text search. Real-time text search: Common Solutions: Elasticsearch & Grafana Loki There exist two common log processing solutions within the industry, exemplified by Elasticsearch and Grafana Loki, respectively. : It is well-embraced due to its support for full-text search and high performance. The downside is the low throughput in real-time writing and the huge resource consumption in index creation. Inverted index (Elasticsearch) : It is the opposite of inverted index because it boasts high real-time write throughput and low storage cost but delivers slow queries. Lightweight index / no index (Grafana Loki) Introduction to Inverted Index A prominent strength of Elasticsearch in log processing is quick keyword search among a sea of logs. This is enabled by inverted indexes. Inverted indexing was originally used to retrieve words or phrases in texts. The figure below illustrates how it works: Upon data writing, the system tokenizes texts into , and stores these terms in a which maps terms to the ID of the row where they exist. In text queries, the database finds the corresponding of the keyword (term) in the posting list, and fetches the target row based on the row ID. By doing so, the system won't have to traverse the whole dataset and thus improves query speeds by orders of magnitudes. terms posting list row ID In inverted indexing of Elasticsearch, quick retrieval comes at the cost of writing speed, writing throughput, and storage space. Why? Firstly, tokenization, dictionary sorting, and inverted index creation are all CPU- and memory-intensive operations. Secondly, Elasticssearch has to store the original data, the inverted index, and an extra copy of data stored in columns for query acceleration. That's triple redundancy. But without inverted index, Grafana Loki, for example, is hurting user experience with its slow queries, which is the biggest pain point for engineers in log analysis. Simply put, Elasticsearch and Grafana Loki represent different tradeoffs between high writing throughput, low storage cost, and fast query performance. What if I tell you there is a way to have them all? We have introduced inverted indexes in and further optimized it to realize Apache Doris 2.0.0 two times faster log query performance than Elasticsearch with 1/5 of the storage space it uses. Both factors combined, it is a 10 times better solution. Inverted Index in Apache Doris Generally, there are two ways to implement indexes: or . external indexing system built-in indexes You connect an external indexing system to your database. In data ingestion, data is imported to both systems. After the indexing system creates indexes, it deletes the original data within itself. When data users input a query, the indexing system provides the IDs of the relevant data, and then the database looks up the target data based on the IDs. External indexing system: Building an external indexing system is easier and less intrusive to the database, but it comes with some annoying flaws: The need to write data into two systems can result in data inconsistency and storage redundancy. Interaction between the database and the indexing system brings overheads, so when the target data is huge, the query across the two systems can be slow. It is exhausting to maintain two systems. In , we opt for the other way. Built-in inverted indexes are more difficult to make, but once it is done, it is faster, more user-friendly, and trouble-free to maintain. Apache Doris In Apache Doris, data is arranged in the following format. Indexes are stored in the Index Region: We implement inverted indexes in a non-intrusive manner: : As a segment file is written into Doris, an inverted index file will be written, too. The index file path is determined by the segment ID and the index ID. Rows in segments correspond to the docs in indexes, so are the RowID and the DocID. Data ingestion & compaction : If the clause includes a column with inverted index, the system will look up in the index file, return a DocID list, and convert the DocID list into a RowID Bitmap. Under the RowID filtering mechanism of Apache Doris, only the target rows will be read. This is how queries are accelerated. Query where Such non-intrusive method separates the index file from the data files, so you can make any changes to the inverted indexes without worrying about affecting the data files themselves or other indexes. Optimizations for Inverted Index General Optimizations C++ Implementation and Vectorization Different from Elasticsearch, which uses Java, Apache Doris implements C++ in its storage modules, query execution engine, and inverted indexes. Compared to Java, C++ provides better performance, allows easier vectorization, and produces no JVM GC overheads. We have vectorized every step of inverted indexing in Apache Doris, such as tokenization, index creation, and queries. To provide you with a perspective, in inverted indexing, Apache Doris writes data at a speed of 20MB/s per core, which is four times that of Elasticsearch (5MB/s). Columnar Storage & Compression Apache Lucene lays the foundation for inverted indexes in Elasticsearch. As Lucene itself is built to support file storage, it stores data in a row-oriented format. In Apache Doris, inverted indexes for different columns are isolated from each other, and the inverted index files adopt columnar storage to facilitate vectorization and data compression. By utilizing Zstandard compression, Apache Doris realizes a compression ratio ranging from to , faster compression speeds, and 50% less space usage than GZIP compression. 5:1 10:1 BKD Trees for Numeric / Datetime Columns Apache Doris implements BKD trees for numeric and datetime columns. This not only increases performance of range queries, but is a more space-saving method than converting those columns to fixed-length strings. Other benefits of it include: : It is able to quickly locate the target data range in numeric and datetime columns. Efficient range queries : It aggregates and compresses adjacent data blocks to reduce storage costs. Less storage space : BKD trees are scalable and adaptive to multi-dimensional data types, such as GEO points and ranges. Support for multi-dimensional data In addition to BKD trees, we have further optimized the queries on numeric and datetime columns. : We have fine-tuned the compression algorithm for low-cardinality scenarios, so decompressing and de-serializing large amounts of inverted lists will consume less CPU resources. Optimization for low-cardinality scenarios : For high-hit-rate scenarios, we adopt pre-fetching. If the hit rate exceeds a certain threshold, Doris will skip the indexing process and start data filtering. Pre-fetching Tailored Optimizations to OLAP Log analysis is a simple kind of query with no need for advanced features (e.g. relevance scoring in Apache Lucene). The bread and butter capability of a log processing tool is quick queries and low storage cost. Therefore, in Apache Doris, we have streamlined the inverted index structure to meet the needs of an OLAP database. In data ingestion, we prevent multiple threads from writing data into the same index, and thus avoid overheads brought by lock contention. We discard forward index files and Norm files to clear storage space and reduce I/O overheads. We simplify the computation logic of relevance scoring and ranking to further reduce overheads and increase performance. In light of the fact that logs are partitioned by time range and historical logs are visited less frequently. We plan to provide more granular and flexible index management in future versions of Apache Doris: : create index for logs of the past seven days, etc. Create inverted index for a specified data partition : delete index for logs from over one month ago, etc. (so as to clear out index space). Delete inverted index for a specified data partition Benchmarking We tested Apache Doris on publicly available datasets against Elasticsearch and ClickHouse. For a fair comparison, we ensure uniformity of testing conditions, including benchmarking tool, dataset, and hardware. Apache Doris VS Elasticsearch : ES Rally, the official testing tool for Elasticsearch Benchmarking tool : 1998 World Cup HTTP Server Logs (self-contained dataset in ES Rally) Dataset : 32G, 247 million rows, 134 bytes per row (on average) Data Size (Before Compression) :  11 queries including keyword search, range query, aggregation, and ranking; Each query is serially executed 100 times. Query : 3 × 16C 64G cloud virtual machines Environment : Results of Apache Doris Writing Speed: 550 MB/s, 4.2 times that of Elasticsearch Compression Ratio: 10:1 Storage Usage: 20% that of Elasticsearch Response Time: 43% that of Elasticsearch Apache Doris VS ClickHouse As ClickHouse launched inverted index as an experimental feature in v23.1, we tested Apache Doris with the same dataset and SQL as described in the ClickHouse , and compared performance of the two under the same testing resource, case, and tool. blog : 6.7G, 28.73 million rows, the Hacker News dataset, Parquet format Data :  3 keyword searches, counting number of occurrence of the keywords "ClickHouse", "OLAP" OR "OLTP", and "avx" AND "sve". Query : 1 × 16C 64G cloud virtual machine Environment : Apache Doris was faster than ClickHouse in the three queries, respectively. Result 4.7 times, 12 times, 18.5 times Usage & Example : one million comment records from Hacker News Dataset : Specify inverted index to the data table upon table creation. Step 1 : Parameters INDEX idx_comment ( ): create an index named "idx_comment" comment for the "comment" column comment USING INVERTED: specify inverted index for the table PROPERTIES("parser" = "english"): specify the tokenization language to English CREATE TABLE hackernews_1m
(
    `id` BIGINT,
    `deleted` TINYINT,
    `type` String,
    `author` String,
    `timestamp` DateTimeV2,
    `comment` String,
    `dead` TINYINT,
    `parent` BIGINT,
    `poll` BIGINT,
    `children` Array<BIGINT>,
    `url` String,
    `score` INT,
    `title` String,
    `parts` Array<INT>,
    `descendants` INT,
    INDEX idx_comment (`comment`) USING INVERTED PROPERTIES("parser" = "english") COMMENT 'inverted index for comment'
)
DUPLICATE KEY(`id`)
DISTRIBUTED BY HASH(`id`) BUCKETS 10
PROPERTIES ("replication_num" = "1"); Note: You can add index to an existing table via comment . Different from that of smart index and secondary index, the creation of inverted index only involves the reading of the comment column, so it can be much faster. ADD INDEX idx_comment ON hackernews_1m( ) USING INVERTED PROPERTIES("parser" = "english") : Retrieve the words"OLAP" and "OLTP" in the comment column with . The response time here was 1/10 of that in hard matching with . (The performance gap widens as data volume increases.) Step 2 MATCH_ALL like mysql> SELECT count() FROM hackernews_1m WHERE comment LIKE '%OLAP%' AND comment LIKE '%OLTP%';
+---------+
| count() |
+---------+
|      15 |
+---------+
1 row in set (0.13 sec)

mysql> SELECT count() FROM hackernews_1m WHERE comment MATCH_ALL 'OLAP OLTP';
+---------+
| count() |
+---------+
|      15 |
+---------+
1 row in set (0.01 sec) For more feature introduction and usage guide, see documentation: Inverted Index Wrap-up In a word, what contributes to Apache Doris' 10-time higher cost-effectiveness than Elasticsearch is its OLAP-tailored optimizations for inverted indexing, supported by the columnar storage engine, massively parallel processing framework, vectorized query engine, and cost-based optimizer of Apache Doris. As proud as we are about our own inverted indexing solution, we understand that self-published benchmarks can be controversial, so we are open to from any third-party users and see how works in real-world cases. feedback Apache Doris

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Understanding Data Compaction: The Storekeeper's Approach to Efficiency

How We Increased Database Query Concurrency by 20 Times

Join the Apache Doris community on Slack

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

Building A Log Analytics Solution 10 Times More Cost-Effective Than Elasticsearch

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Hands-On Guide to Inverted Indexes: Accelerate Text Searches by 40

10 Best Datasets for Time Series Analysis

12 Best Pre-Installed R Datasets Commonly Used for Statistical Analysis

Import JSON To Google Sheets - 3 Best Ways To Do It

How To Import External Data Into Google Sheets Without Copy/Paste

A Hands-On Guide to Inverted Indexes: Accelerate Text Searches by 40

10 Best Datasets for Time Series Analysis

12 Best Pre-Installed R Datasets Commonly Used for Statistical Analysis

Import JSON To Google Sheets - 3 Best Ways To Do It

How To Import External Data Into Google Sheets Without Copy/Paste

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps