Shulou(Shulou.com)05/31 Report--

What this article shares with you is about how the fast retrieval of the time series database is carried out. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it with the editor.

Elasticsearch achieves faster filtering than relational databases through Lucene's inverted index technology. In particular, it has very good filtering support for multiple conditions, such as combinatorial queries such as ages between 18 and 30 and gender for women. Inverted indexes are introduced in many places, but where are they faster than b-tree indexes in relational databases? Why on earth is it fast?

Generally speaking, an b-tree index is an index structure optimized for writing. When we do not need to support fast updates, we can use pre-sorting and other methods in exchange for smaller storage space, faster retrieval speed and other benefits, at the cost of slow updates. To go further, you still need to look at how the inverted index of Lucene is constructed.

There are several concepts here. Let's look at a practical example, assuming the following data:

Docid

Age

Gender

one

eighteen

Female

two

twenty

Female

three

eighteen

Male

Each line here is a document. Every document has a docid. Then the inverted index for these document is:

Age

Gender

As you can see, the inverted index is per field, and a field has its own inverted index. 181.20 these are called term, and [1J 3] is posting list. A Posting list is an array of int that stores all the document id that conforms to a certain term. So what are term dictionary and term index?

Suppose we have many term, such as:

Carla,Sara,Elin,Ada,Patty,Kate,Selena

If you arrange it in this order, it must be slow to find a particular term, because the term is not sorted and needs to be filtered through all to find a specific term. After sorting, it becomes:

Ada,Carla,Elin,Kate,Patty,Sara,Selena

In this way, we can use binary search to find out the target's term faster than full traversal. This is term dictionary. With term dictionary, you can use the logN secondary disk to find the target. But random reads to the disk are still very expensive (it takes about 10ms time for a random access). So read the disk as little as possible, and it is necessary to cache some data in memory. But the whole term dictionary itself is too big to fit completely in memory. So there is term index. Term index is a bit like a big chapter table of a dictionary. For example:

Term at the beginning of A... . Xxx page

Term at the beginning of C... . Xxx page

Term at the beginning of E... . Xxx page

If all the term are English characters, maybe the term index is really made up of 26 English character tables. But the reality is that term is not necessarily all English characters, term can be any byte array. And 26 English characters may not have an equal term for every character. For example, there may be none of the term at the beginning of the x character, and there are many term at the beginning of the s character. The actual term index is a trie tree:

The example is a trie tree containing "A", "to", "tea", "ted", "ten", "I", "in", and "inn". This tree will not contain all the term, it will contain some prefixes of term. With term index, you can quickly locate an offset in term dictionary, and then look it up sequentially from that location. Coupled with some compression techniques (search Lucene Finite State Transducers) the size of the term index can be only a tenth of the size of all term, making it possible to cache the entire term index in memory. On the whole, this is the effect.

Now we can answer, "Why can Elasticsearch/Lucene search be faster than mysql?" Mysql has only one layer of term dictionary, which is stored on disk in the form of b-tree sorting. Retrieving a term requires several random access disk operations. Lucene adds term index to term dictionary to speed up retrieval, and term index is cached in memory in the form of a tree. After looking up the block location of the corresponding term dictionary from term index, and then looking for term on the disk, the number of random access on the disk is greatly reduced.

Two additional points worth mentioning are that term index is saved in memory in the form of FST (finite state transducers), which is characterized by very memory savings. Term dictionary is saved as block on disk, and Ab can be omitted from a block internal compression using common prefixes, such as words that begin with Ab. This way term dictionary can save more disk space than b-tree.

How to federate index queries?

So the process of giving the query filter condition age=18 is to find the approximate location of 18 in term dictionary from term index, then find the exact term of 18 from term dictionary, and then get a posting list or a pointer to the location of posting list. And then the process of querying gender= women is similar. Finally, it is concluded that the age=18 AND gender= woman is to merge the two posting list into a "and".

This theoretical "and" merger is not easy. For mysql, if you index both the age and gender fields, only the most selective is selected for the query, and then another condition is filtered out in memory while traversing the rows. So how can two indexes be used together? There are two ways:

Use skip list data structures. Traverse the posting list of gender and age at the same time and skip each other

Using the bitset data structure, the bitset is calculated for the two filter of gender and age, and the AN operation is done for the two bitset.

PostgreSQL has supported the joint use of two indexes through bitmap since version 8.4, which makes use of bitset data structures. Of course, some commercial relational databases also support similar federated indexes. Elasticsearch supports the above two federated indexing methods. If the filter of the query is cached in memory (in the form of bitset), then the merge is the AND of two bitset. If the filter of the query is not cached, then traverse the posting list of both on disk in the way of skip list.

Using Skip List to merge

These are three posting list. We now need to merge them with the relationship of AND to get the intersection of posting list. First select the shortest posting list, and then traverse from small to large. The traversal process can skip some elements, for example, when we traverse to the green 13, we can skip the blue 3, because 3 is smaller than 13.

The whole process is as follows

Next-> 2 Advance (2)-> 13 Advance (13)-> 13 Already on 13 Advance (13)-> 13 Matchmakers! Next-> 17 Advance (17)-> 22 Advance (22)-> 98 Advance (98)-> 98 Advance (98)-> 98 matchmakers!

The final intersection is [13998], which takes much faster time than traversing three posting list in its entirety. But the premise is that each list needs to indicate the operation Advance and quickly move to the location. What kind of list can do a frog jump forward with Advance like this? skip list:

Conceptually, for a long posting list, such as:

[1,3,13101105108255256257]

We can divide the list into three block:

[1,3,13] [101105108] [255256257]

You can then build the second layer of skip list:

[1101255]

1101255 points to your own corresponding block. This allows you to quickly move across the block to point to the location.

Lucene will naturally compress the block again. The compression method is called Frame Of Reference coding.

Examples are as follows: considering the frequent occurrence of term (the value of the so-called low cardinality), such as male or female in gender. If there were 1 million documents, there would be 500000 int values in the posting list of male sex. Compressing with Frame of Reference coding can greatly reduce disk footprint. This optimization is very important for reducing the size of the index. Of course, there is a similar posting list thing in mysql b-tree, which has not been compressed in this way.

Because the coding of this Frame of Reference has a decompression cost. With skip list, in addition to skipping the cost of traversal, you can also skip the process of decompressing these compressed block, thus saving cpu.

Using bitset to merge

Bitset is a very intuitive data structure, corresponding to posting list, such as:

[1,3,4,7,10]

The corresponding bitset is:

[1,0,1,1,0,0,1,0,0,1]

Each document is sorted by document id corresponding to one of the bit. Bitset itself has the feature of compression, which can represent 8 documents with one byte. So only 125000 byte are needed for 1 million documents. But given that there may be billions of documents, keeping bitset in memory is still a luxury. And each filter consumes a bitset, for example, if age=18 is cached, it is a bitset,18.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.