CN117851537A - Index construction method of time sequence data storage engine - Google Patents

Abstract

The invention provides an index construction method of a time sequence data storage engine, and belongs to the technical field of database storage. The method specifically comprises the following steps: pre-screening the data blocks according to the document frequency of the label keys and the occurrence frequency of the label values; performing feature extraction on the pre-screening set through the historical access frequency of the tag keys to obtain data features and performing machine learning to further screen so as to obtain a target set of index tag groups comprising each time line; extracting target labels from the target set according to a plurality of different indexes in the index label group to obtain a plurality of group label sets; corresponding time lines are put into the group label sets with the same index labels, and a plurality of time line sets are obtained; and allocating a unique group ID to each time line set, establishing an inverted index mapped by the tag key value pair and the group ID, and establishing a leading index mapped by the target tag and the inverted index. The invention can improve the writing efficiency and the index construction efficiency of time sequence data.

Description

An index construction method for a time series data storage engine

Technical Field

The present invention relates to the field of database storage technology, and in particular to an index construction method for a time series data storage engine.

Background technique

With the development of IoT technology, the number and application scope of IoT devices have increased dramatically. In order to ensure the high availability and robustness of IoT devices and Internet services, the need for more precise and comprehensive monitoring of their real-time operating status has emerged. As the storage engine for the above monitoring data, time series databases have received widespread attention from academia and industry in recent years.

Typical time series data generally consists of two parts: timeline data and time point data. Time point data generally consists of a 64-bit integer timestamp and a double-precision floating point (IEEE754 double) indicator value. The representation of timeline data is more complex: it generally consists of a monitoring indicator string (metric) and a series of tag key-value pairs (tagkv pairs), usually called a timeline (serieskey).

The current method for storing and indexing time series data is to build a two-index-layer index structure for retrieving time lines based on tag values, timeline identifiers, and identifier sets, and save the mapping relationship between the creation of tag values and identifier sets, and the creation of a second mapping relationship between timeline identifiers and time lines. However, this method cannot adapt to the expansion of the timeline cardinality of the time series database. When the timeline cardinality expands, the amount of index construction will increase rapidly, thereby affecting the writing efficiency and index construction efficiency of time series data.

Summary of the invention

The present invention aims to solve at least one of the technical problems existing in the related art. To this end, the present invention provides an index construction method for a time series data storage engine.

The present invention provides an index construction method for a time series data storage engine, comprising:

S1: pre-screen the data blocks to be stored according to the document frequency of the tag key and the occurrence frequency of the tag value to obtain a pre-screened set;

S2: extracting features from the pre-screened set based on the historical access frequency of the tag key to obtain data features;

S3: performing machine learning on the data features to obtain a screening function, and screening the pre-screening set by using the screening function to obtain a target set, wherein the target set includes at least an indicator label group for each timeline;

S4: extracting target labels from the target set according to a plurality of different indicators in the indicator label group to obtain a plurality of group label sets;

S5: For a group tag set with the same indicator tag, insert a timeline corresponding to the indicator tag to obtain multiple timeline sets;

S6: Assign a unique group ID to each timeline set, create an inverted index mapping the tag key-value pair to the group ID, and create a pre-index mapping the target tag to the inverted index to complete the index construction of the time series data storage engine.

According to an index construction method for a time series data storage engine provided by the present invention, the data features in step S2 include: document frequency, tag key cardinality, tag key cardinality ranking, tag key cardinality ranking ratio, tag key frequency, tag key frequency ranking and tag key frequency ranking ratio.

According to an index building method for a time series data storage engine provided by the present invention, the machine learning scheme used for the data features in step S3 is an AdaBoost iterative algorithm.

According to an index construction method for a time series data storage engine provided by the present invention, in step S3, each indicator in the indicator tag group uses the indicator name as the tag key and the indicator value as the tag value.

According to an index construction method for a time series data storage engine provided by the present invention, each label key-value pair in the inverted index in step S6 has a corresponding inverted chain, and the inverted chain includes ascending group ID groups.

According to the index construction method of a time series data storage engine provided by the present invention, the pre-index in step S6 is implemented by an algebraic reconstruction method and a dictionary data structure.

According to an index construction method for a time series data storage engine provided by the present invention, in the pre-index in step S6, the algebraic reconstruction method is used to map the tag key to the dictionary data structure address consisting of the corresponding tag value set.

According to an index construction method for a time series data storage engine provided by the present invention, in the pre-index in step S6, the dictionary data structure stores a mapping between a label value and a corresponding postings chain offset.

The present invention provides an index construction method for a time series data storage engine, which selects target tags based on heuristic screening and machine learning schemes, so as to ensure that the index construction amount does not increase rapidly when facing the problem of timeline expansion of today's time series databases, thereby ensuring the writing efficiency and index construction efficiency of time series data; at the same time, the screened target tags are used for predictive grouping, and a complete index structure system is established based on the grouping scheme, which optimizes data storage and index construction without reducing query performance; at the same time, the present invention uses a suitable index structure to optimize query conditions and query requirements of different modes, so that the present invention can still have good performance under the limitations of different data characteristics and different query preferences.

Additional aspects and advantages of the present invention will be given in part in the following description and in part will be obvious from the following description, or will be learned through practice of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the technical solutions in the present invention or the prior art, the drawings required for use in the embodiments or the description of the prior art will be briefly introduced below. Obviously, the drawings described below are some embodiments of the present invention. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying creative work.

FIG. 1 is a flow chart of an index construction method of a time series data storage engine provided by an embodiment of the present invention.

FIG. 2 is a schematic diagram of the structure of a timeline set constructed by an index construction method of a time series data storage engine of the present invention in an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical scheme and advantages of the present invention clearer, the technical scheme of the present invention will be clearly and completely described below in conjunction with the drawings in the present invention. Obviously, the described embodiments are part of the embodiments of the present invention, rather than all the embodiments. Based on the embodiments in the present invention, all other embodiments obtained by ordinary technicians in the field without creative work are within the scope of protection of the present invention. The following embodiments are used to illustrate the present invention, but cannot be used to limit the scope of the present invention.

In the description of the embodiments of the present invention, it should be noted that the terms "center", "longitudinal", "lateral", "up", "down", "front", "back", "left", "right", "vertical", "horizontal", "top", "bottom", "inside", "outside" and the like indicate positions or positional relationships based on the positions or positional relationships shown in the accompanying drawings, and are only for the convenience of describing the embodiments of the present invention and simplifying the description, and do not indicate or imply that the devices or elements referred to must have a specific orientation, be constructed and operate in a specific orientation, and therefore cannot be understood as limitations on the embodiments of the present invention. In addition, the terms "first", "second", and "third" are used for descriptive purposes only and cannot be understood as indicating or implying relative importance.

In the description of the embodiments of the present invention, it should be noted that, unless otherwise clearly specified and limited, the terms "connected" and "connection" should be understood in a broad sense, for example, it can be a fixed connection, a detachable connection, or an integral connection; it can be a mechanical connection or an electrical connection; it can be a direct connection or an indirect connection through an intermediate medium. For ordinary technicians in this field, the specific meanings of the above terms in the embodiments of the present invention can be understood according to specific circumstances.

In the embodiments of the present invention, unless otherwise clearly specified and limited, a first feature being "above" or "below" a second feature may mean that the first and second features are in direct contact, or the first and second features are in indirect contact through an intermediate medium. Moreover, a first feature being "above", "above" or "above" a second feature may mean that the first feature is directly above or obliquely above the second feature, or simply means that the first feature is higher in level than the second feature. A first feature being "below", "below" or "below" a second feature may mean that the first feature is directly below or obliquely below the second feature, or simply means that the first feature is lower in level than the second feature.

In the description of this specification, the description with reference to the terms "one embodiment", "some embodiments", "example", "specific example", or "some examples" etc. means that the specific features, structures, materials or characteristics described in conjunction with the embodiment or example are included in at least one embodiment or example of the embodiments of the present invention. In this specification, the schematic representations of the above terms do not necessarily refer to the same embodiment or example. Moreover, the specific features, structures, materials or characteristics described may be combined in any one or more embodiments or examples in a suitable manner. In addition, those skilled in the art may combine and combine the different embodiments or examples described in this specification and the features of the different embodiments or examples, without contradiction.

In order to better understand the present invention, the terms appearing in the present invention are explained below.

Adaboost is an iterative algorithm. Its core idea is to train different classifiers (weak classifiers) for the same training set, and then combine these weak classifiers to form a stronger final classifier (strong classifier). The algorithm itself is implemented by changing the data distribution. It determines the weight of each sample based on whether the classification of each sample in each training set is correct and the accuracy of the last overall classification. The new data set with modified weights is sent to the lower-level classifier for training, and finally the classifiers obtained from each training are finally fused together as the final decision classifier. Using the adaboost classifier can exclude some unnecessary training data features and put them on the key training data.

Adaptive Radix Tree (ART) is an efficient data structure for storing and retrieving key-value pairs. It is a special radix tree that aims to solve some of the shortcomings of traditional radix trees in terms of memory utilization and performance.

The features of adaptive radix trees include:

Efficient memory utilization: Compared with traditional radix trees, ART selects different node types based on the prefix length of the key, thereby better utilizing memory and reducing the space overhead of nodes. High-performance search and insertion operations: The ART tree uses a variety of node types (4, 16, 48, and 256 leaf nodes), and dynamically selects the node type based on the length of the key, allowing more efficient search and insertion operations in different scenarios. Suitable for high-concurrency environments: The ART tree uses optimistic concurrency control to achieve concurrent access to nodes through lock-free or fine-grained locks, which is suitable for high-concurrency read and write scenarios. Suitable for efficient range queries: The ART tree supports efficient range query operations and can quickly locate a set of key-value pairs that match a prefix.

Adaptive radix tree has a wide range of applications in databases, operating systems, network routing tables and other fields. Its design concept is mainly to optimize memory utilization and improve search efficiency, making it an effective data structure for handling large-scale key-value pair storage and retrieval.

FST is a data structure widely used in natural language processing and speech recognition. In the database field, Lucene introduced it into Lucene Apache and used it as an important index structure to replace traditional data structures such as hash tables. This data structure is essentially a special finite state automaton (FSA). When applied, its structure is similar to a weighted trie that shares not only prefixes but also suffixes. Compared with other data structures, the time complexity of FST when used as a map is Of which/> is the length of the input sequence, which is consistent with the time complexity of the hash table and is the minimum time complexity that can be achieved when a data structure with mapping function performs a single mapping. Therefore, it should be better than space-optimized hash tables such as maps constructed using red-black trees or HAMT (Hash Array Mapped Trie) in terms of query speed. At the same time, compared with Trie, FST has a significantly higher compression rate due to the characteristic of sharing string suffixes, but consistent with dictionary data structures such as Trie, FST stores all information about the string set, that is, by traversing FST, the string set it contains can be restored, which is not available in data structures such as hash tables. This means that FST can support inexact matching modes of input data such as regular matching, wildcard matching, and fuzzy matching.

The embodiment of the present invention is described below with reference to FIG. 1 .

The present invention provides an index construction method for a time series data storage engine, comprising:

First, the following steps S1 to S3 are all the target label selection stages. The target label selection is mainly divided into two stages: the heuristic screening stage and the machine learning screening stage. In the heuristic screening process, the labels are preliminarily screened by predefined rules and corresponding thresholds to generate a pre-screening set with a much smaller cardinality than the original label set, that is, the set of all labels appearing in a data segment. In this process, the data features of the labels contained in the pre-screening set are extracted at the same time. Next, the data features obtained above are used to perform machine learning screening with the historical statistical frequency of past queries as labels, so as to finally generate the target label.

S1: pre-screen the data blocks to be stored according to the document frequency of the tag key and the occurrence frequency of the tag value to obtain a pre-screened set;

In the pre-screening stage, the filtering is mainly based on the document frequency of the tag key and the frequency of occurrence of the tag value.

The document frequency of the tag key, that is, the number of timelines with different indicators in which a certain tag key exists. For the monitoring of different indicators, some tag keys will overlap, and these tag keys constitute the basic data of the monitoring target. Tags with these tag keys should be the main designated conditions for recall. A data segment generally contains 102 tag keys, and the screening threshold is generally set to 30%, that is, after sorting the tag keys according to the document frequency, the top 30% of the tag keys are selected.

The selection of label values mainly uses their frequency of occurrence. After selecting the above label key set, for each label key, there are about 10 to 3000 different label values corresponding to it. After sorting the frequency of occurrence of label values in the data segment, a threshold P is specified (usually 80% or 90%, called P80 or P90 scheme), and the label values with high probability are selected downward until the sum of their frequency of occurrence reaches the threshold P. The selected label values are selected and combined with the above label keys to form a pre-screened label key value pair set.

S2: extracting features from the pre-screened set based on the historical access frequency of the tag key to obtain data features;

The label of each data is generated by the historical query record. Generally, the access frequency of some label keys in the historical query record is much higher than that of other label keys. In the present invention, the Boolean label of these label keys is set to 1, and the other label keys are set to 0. Specifically, similar to the label value screening method in step S1, after sorting the access frequencies of different labels in the historical query record, the P80 or P90 scheme is used for screening, and the selected label keys are Value is set.

The data features in step S2 include: document frequency, tag key cardinality, tag key cardinality ranking, tag key cardinality ranking ratio, tag key frequency, tag key frequency ranking and tag key frequency ranking ratio.

This stage uses the data features extracted in the previous stage to train the machine learning model. The extracted features include:

Tag key cardinality : The cardinality of the tag value set of a tag key;

Tag key cardinality ranking : The ranking of the above cardinality among all tag keys in the timeline set recording the same metric;

Tag key cardinality ranking ratio : The above ranking is the percentage of all tag keys in the timeline set of the same metric;

Tag key frequency : The number of times a tag key appears in a set of timelines recording the same metric;

Tag key frequency ranking : The above frequency is the ranking of all tag keys in the timeline set recording the same metric;

Tag key frequency ranking ratio : The above ranking is the percentage of all tag keys in the timeline set of the same metric;

Document frequency : Document frequency for the tag key.

S3: performing machine learning on the data features to obtain a screening function, and screening the pre-screening set by using the screening function to obtain a target set, wherein the target set includes at least an indicator label group for each timeline;

Among them, the machine learning scheme used for the data features in step S3 is the AdaBoost iterative algorithm.

Wherein, in step S3, each indicator in the indicator tag group uses the indicator name as the tag key and the indicator value as the tag value.

After step S2, a classic machine learning solution, such as AdaBoost, is used to train a function that is more accurate than heuristic screening, through which the final target label can be obtained. The present invention also regards the indicators in the timeline data as a set of labels, that is, its label key is "metric" and the value is the indicator value, such as "metric: cpu". This special set of labels is always the target label, so each group's group label contains and only contains one such label, and all timelines in the group have the same indicator.

S4: extracting target labels from the target set according to a plurality of different indicators in the indicator label group to obtain a plurality of group label sets;

Furthermore, according to the target tag screening results, the target tags contained in each timeline are extracted to form a set, and are placed in a group. Each group has some group tags to form a group tag set. The group tag set is different between different groups and is also the only way to distinguish different groups from each other.

S5: For a group tag set with the same indicator tag, insert a timeline corresponding to the indicator tag to obtain multiple timeline sets;

Furthermore, after obtaining a target tag set of a timeline, the timeline is placed in a group whose group tag set is exactly equivalent to the target tag set of the timeline. If there is no group that meets the requirements, a new group that meets the above requirements is created and the timeline is placed in it.

The present invention divides all timelines in a data segment into different groups. The distribution structure of the data in the group is shown in Figure 2. The timeline group includes indicator 1, indicator 2, indicator 3 and indicator g. Each indicator has corresponding labels 1 to labels kg belonging to the indicator itself. Each group has a unique group label set, and all timelines in the group also contain all labels in the above group label set. The timelines in the group no longer need to store this part of the labels independently, but only need to store the remaining labels they have and their indicator names.

S6: Assign a unique group ID to each timeline set, create an inverted index mapping the tag key-value pair to the group ID, and create a pre-index mapping the target tag to the inverted index to complete the index construction of the time series data storage engine.

Furthermore, based on step S5 and the previous grouping scheme, a pre-index and a reverse index are established for the timeline data, wherein the pre-index indexes the target tag to the reverse index chain, and the reverse index indexes the pre-index result again to the location containing the timeline to be indexed.

Wherein, each tag key-value pair in the inverted index in step S6 has a corresponding inverted chain, and the inverted chain includes ascending group ID groups.

The pre-index in step S6 is implemented by an algebraic reconstruction method and a dictionary data structure.

Among them, in the pre-index in step S6, the algebraic reconstruction method is used to map the tag key to the dictionary data structure address consisting of the corresponding tag value set.

In the preceding index in step S6, the dictionary data structure stores a mapping between label values and corresponding postings chain offsets.

Based on the grouping scheme, the present invention designs a group-level inverted index. For each group in a data segment, after assigning it a unique group id, a mapping from label key-value pairs to group ids is established. This mapping is the group-level inverted index in the present invention. Specifically, each label key-value pair corresponds to an inverted chain, which contains a series of group ids in ascending order. The group label set of the groups corresponding to these ids contains the label key-value pair.

Based on the grouping scheme, the present invention designs a pre-index, which maps the target label to the starting position of its corresponding postings chain. This part of the index will be implemented using a combination of ART algebraic reconstruction method + FST dictionary data structure.

Among them, ART is used to map from a label key to the address of an FST composed of its corresponding label value set. For each different label key in the target label set, it corresponds to a set of label values. The combination of the label key and any label value in the set has appeared at least once in the data segment. For the label value set, the present invention establishes an FST to store it.

In the present invention, an FST stores a mapping from a label value to its corresponding postings list offset. The offset is a positive integer based on the postings list base address. Addition operations can be naturally defined between positive integers, so they can be used as the output of the FST. On the other hand, storing label values in the form of FST can well cope with queries under regular expression conditions.

Different from the pruning search solution proposed by Lucene, thanks to the segmentation mechanism based on time order, the amount of timeline data contained in each data segment is not huge. After using the grouping solution, the amount of index constructed for each data segment is further reduced, so each FST is only about Order of magnitude storage space occupied.

In some embodiments, a method for recalling data stored in an index building method of a time series data engine provided by the present invention is described below.

A typical query mode unit for a time series database is:

query = metric name + {tag key 1: tag value, ..., tag key :label value};

The tag value can be an exact string, a regular expression, or a string with wildcards. The tag key-value pairs are in an AND relationship, that is, the timeline data containing all tags in the query tag set needs to be recalled. The number of tags Generally, there are 2 to 6 items.

When a query comes, ART is queried first. According to each query condition, if the condition hits a target label key, it can be mapped to the corresponding FST; next, the corresponding label value is queried in FST. If the label value is the target label value, one (or more, in the case of regular matching, etc.) return value will be obtained, and the return value is the offset of the inverted index. Next, through the offset obtained above, the inverted index is queried to obtain a series of inverted chains. The inverted chains are intersected to obtain all the group numbers that need to be recalled for this query; finally, the corresponding groups are decompressed in sequence according to the group number, and all the timeline data inside them are returned, and this query is processed.

One possible situation is that a query condition does not hit any target tag key, then this query needs to be filtered. For other query conditions, after finally obtaining all the timeline data of all the groups to be recalled, these data need to be filtered once. The filter conditions are the timeline data of the query conditions that do not hit the target key tag, which are returned after filtering. Note that a metric name is always provided as one of the query conditions in a query, which ensures that there is no query in which all the query conditions provided do not hit any target tag. Therefore, this solution can ensure that there will never be a situation where global filtering is required at the data segment level, thereby ensuring the lower limit of query latency.

Another possible situation is that a query condition hits a target tag key (denoted as ), and successfully obtained its corresponding FST data structure, but in the FST, no label value was hit. In this case, filtering is also required, but the amount of data and time overhead of filtering will be much smaller than the previous filtering. Similarly, after obtaining all the timeline data in all the groups to be recalled, for each timeline, only the timeline needs to be checked. The corresponding tag value is the tag value specified by the query, and the result returned after filtering is the final result of this query.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit it. Although the present invention has been described in detail with reference to the aforementioned embodiments, those skilled in the art should understand that they can still modify the technical solutions described in the aforementioned embodiments, or make equivalent replacements for some of the technical features therein. However, these modifications or replacements do not deviate the essence of the corresponding technical solutions from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (8)

1. A method for constructing an index of a time series data storage engine, comprising: S1: pre-screen the data blocks to be stored according to the document frequency of the tag key and the occurrence frequency of the tag value to obtain a pre-screened set; S2: extracting features from the pre-screened set based on the historical access frequency of the tag key to obtain data features; S3: performing machine learning on the data features to obtain a screening function, and screening the pre-screening set by using the screening function to obtain a target set, wherein the target set includes at least an indicator label group for each timeline; S4: extracting target labels from the target set according to a plurality of different indicators in the indicator label group to obtain a plurality of group label sets; S5: For a group tag set with the same indicator tag, insert a timeline corresponding to the indicator tag to obtain multiple timeline sets; S6: Assign a unique group ID to each timeline set, create an inverted index mapping the tag key-value pair to the group ID, and create a pre-index mapping the target tag to the inverted index to complete the index construction of the time series data storage engine. 2. According to the index construction method of a time series data storage engine described in claim 1, it is characterized in that the data features in step S2 include: document frequency, tag key cardinality, tag key cardinality ranking, tag key cardinality ranking ratio, tag key frequency, tag key frequency ranking and tag key frequency ranking ratio. 3. According to the index construction method of a time series data storage engine according to claim 1, it is characterized in that the machine learning scheme used for the data features in step S3 is an AdaBoost iterative algorithm. 4. The index construction method of a time series data storage engine according to claim 1 is characterized in that, in step S3, each indicator in the indicator label group uses the indicator name as the label key and the indicator value as the label value. 5. According to the index construction method of a time series data storage engine according to claim 1, it is characterized in that each label key-value pair in the inverted index in step S6 has a corresponding inverted chain, and the inverted chain includes ascending group ID groups. 6. The index construction method of a time series data storage engine according to claim 1 is characterized in that the pre-index in step S6 is implemented by an algebraic reconstruction method and a dictionary data structure. 7. According to the index construction method of a time series data storage engine according to claim 6, it is characterized in that in the pre-index in step S6, the algebraic reconstruction method is used to map the label key to the dictionary data structure address consisting of the corresponding label value set. 8. The index construction method for a time series data storage engine according to claim 6, characterized in that in the pre-index in step S6, the dictionary data structure stores a mapping between a label value and a corresponding postings chain offset.