CN109815225B - Parallelized prefix data retrieval method and system based on prefix tree structure - Google Patents
Parallelized prefix data retrieval method and system based on prefix tree structure Download PDFInfo
- Publication number
- CN109815225B CN109815225B CN201811511690.1A CN201811511690A CN109815225B CN 109815225 B CN109815225 B CN 109815225B CN 201811511690 A CN201811511690 A CN 201811511690A CN 109815225 B CN109815225 B CN 109815225B
- Authority
- CN
- China
- Prior art keywords
- prefix
- segment
- tree
- retrieval
- network
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 30
- 230000011218 segmentation Effects 0.000 claims description 49
- 238000012545 processing Methods 0.000 claims description 29
- 238000003780 insertion Methods 0.000 claims description 8
- 230000037431 insertion Effects 0.000 claims description 8
- 238000005516 engineering process Methods 0.000 description 6
- 229910002056 binary alloy Inorganic materials 0.000 description 3
- 238000010276 construction Methods 0.000 description 3
- 230000005856 abnormality Effects 0.000 description 2
- 238000009411 base construction Methods 0.000 description 2
- 238000001514 detection method Methods 0.000 description 2
- 238000011161 development Methods 0.000 description 2
- 230000018109 developmental process Effects 0.000 description 2
- 238000005457 optimization Methods 0.000 description 2
- 230000008520 organization Effects 0.000 description 2
- 238000013461 design Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 239000002360 explosive Substances 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000010845 search algorithm Methods 0.000 description 1
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明涉及一种前缀数据检索方法和系统，包括：获取二进制表示的网络前缀，并为该网络前缀构建前缀树，对该前缀树进行分段处理，得到多段分段树；获取二进制表示的待检索网络前缀，将该待检索网络前缀进行分段处理，得到多个分段前缀，在每个分段前缀对应的分段树上进行并发检索，得到检索结果ri，表示在第i段分段前缀在第i段分段树的检索结果，将所有检索结果进行逻辑与操作，并将操作结果作为该待检索网络前缀的检索结果。本发明能够对前缀信息使用分段前缀树结构进行信息库构建，对特定前缀能够进行并行化得前缀匹配查找，实现前缀匹配效率的大幅提升。
The invention relates to a method and system for retrieving prefix data, including: acquiring a network prefix represented by binary, constructing a prefix tree for the network prefix, segmenting the prefix tree to obtain a multi-segment segment tree; Retrieve network prefixes, process the to-be-retrieved network prefixes into segments, obtain multiple segment prefixes, perform concurrent retrieval on the segment tree corresponding to each segment prefix, and obtain the retrieval result r i , indicating that the i-th segment is segmented. For the retrieval result of the segment prefix in the segment tree of the i-th segment, perform a logical AND operation on all retrieval results, and use the operation result as the retrieval result of the network prefix to be retrieved. The invention can use the segmented prefix tree structure to construct the information base for the prefix information, and can perform parallelized prefix matching search for the specific prefix, so as to realize the significant improvement of the prefix matching efficiency.
Description
Technical Field
The invention relates to the field of information retrieval, in particular to a method and a system for retrieving parallelized prefix data based on a prefix tree structure.
Background
With the popularization of networks in the information era and the rapid development of emerging services such as big data and the like, network information shows an explosive growth trend. There is a huge amount of network prefix data in the global internet. In order to perform good management on the internet and perform timely detection and alarm on network abnormality, organization and construction of a network prefix information base become abnormally important.
A network prefix is a collection of a set of IP addresses, each prefix representing a small network. In order to perform good management on the internet and perform timely detection and alarm on network abnormality, organization and construction of a network prefix information base are indispensable.
There are two main ways for constructing the information base of the network prefix:
1. and constructing the information base in a hash table mode. In the mode, the prefix is used as a Key Value, the information to be stored is used as a Value, and the information is stored in a Key Value pair mode;
2. and constructing an information base based on the form of the binary prefix tree. The method expresses prefix information in a binary form and constructs a binary tree for the network prefix information. Each binary tree node represents a network prefix, and data information is stored in the node. The prefix query and matching process is carried out in the binary tree, namely, the branches of the binary tree are selected downwards layer by layer according to the bits of the binary representation of the prefix to be retrieved until the target prefix is found.
For the two modes, when the hash table mode faces massive network prefixes, the occupied storage space is large, byte-by-byte comparison is needed for processing the matching of the sub-prefixes or the longest prefix, and the real-time or quasi-real-time requirements under a big data scene are difficult to meet; the traditional prefix tree construction method solves the problems of the hash table method to a certain extent, but for an IPV4 network, the binary representation of the network prefix is 32 bits, and the binary representation always needs to be searched layer by layer from the root node in the prefix matching process, 8 layers need to be searched for the prefix with the length of 8, and 24 layers need to be searched for the prefix with the length of 24, so that the search time for the prefix with the longer length is longer.
Disclosure of Invention
The invention aims to solve the problems that in the storage and retrieval of massive network prefixes, the traditional prefix information base construction method (a hash table and a traditional prefix tree) has low efficiency in the execution of searching, inserting and deleting operations due to huge data volume, is difficult to maintain and the like, and provides a parallel prefix matching query technology based on a prefix tree structure. The technology of the invention is oriented to massive network prefixes, and the prefix tree structure is segmented to obtain the retrieval entries at each segment at the same time, so that the operations of searching, inserting and deleting are carried out concurrently, and the execution efficiency is greatly improved. The technology can remarkably improve the prefix information retrieval work under massive network prefixes in a parallelization mode, and greatly improves the retrieval efficiency.
In order to solve the above technical problem, an object of the present invention is to provide a prefix data retrieval method, including:
step 2, obtaining the binary expressed network prefix to be retrieved, carrying out segmentation processing on the network prefix to be retrieved to obtain a plurality of segmented prefixes, carrying out concurrent retrieval on the segmented trees corresponding to each segmented prefix to obtain a retrieval result riAnd representing the retrieval result of the ith segment prefix in the ith segment tree, performing logic AND operation on all the retrieval results, and taking the operation result as the retrieval result of the network prefix to be retrieved.
The prefix data retrieval method, wherein the segmentation processing in step 1 specifically includes: segmenting the prefix tree according to the preset segmentation quantity, wherein the obtained segmentation tree quantity is equal to the preset segmentation quantity;
the segmentation treatment in the step 2 specifically comprises the following steps: and segmenting the network prefix to be retrieved, wherein the number of the obtained approximate segmentation prefixes is equal to the preset segmentation number.
The prefix data retrieval method for performing segmentation processing on the prefix tree specifically comprises the following steps: the structure of the prefix tree is divided into one segment according to each 8 layers, wherein the ith segment is a segmented tree, and 256 segments existi-1And the index entry is used for being used as a matching entry of each parallelized segmented prefix during parallel retrieval, the matching entry of the 1 st segmented prefix is a root node of the prefix tree, the matching entry is 0, and the matching entry of the ith segmented prefix except the 1 st segmented prefix is an integer value of binary representation of the preceding (i-1) segment of the segmented prefix.
The prefix data retrieval method further comprises:
and 3, acquiring the network prefix to be inserted, carrying out segmentation processing on the network prefix to be inserted, and respectively carrying out parallel insertion operation on the segmented trees of the corresponding segments.
The prefix data retrieval method is characterized in that the network prefix is an IPV4 network prefix.
The invention also discloses a prefix data retrieval system, which comprises:
the prefix tree segmentation module is used for acquiring a network prefix represented by a binary system, constructing a prefix tree for the network prefix, and performing segmentation processing on the prefix tree to obtain a multi-segment segmented tree;
a retrieval module for obtaining binary expressed network prefix to be retrieved, carrying out segmentation processing on the network prefix to be retrieved to obtain a plurality of segmented prefixes, carrying out concurrent retrieval on the segmented tree corresponding to each segmented prefix to obtain retrieval result riAnd representing the retrieval result of the ith segment prefix in the ith segment tree, performing logic AND operation on all the retrieval results, and taking the operation result as the retrieval result of the network prefix to be retrieved.
In the prefix data retrieval system, the segmentation process in the prefix tree segmentation module specifically includes: segmenting the prefix tree according to the preset segmentation quantity, wherein the obtained segmentation tree quantity is equal to the preset segmentation quantity;
the segmentation processing in the retrieval module specifically comprises: and segmenting the network prefix to be retrieved, wherein the number of the obtained approximate segmentation prefixes is equal to the preset segmentation number.
The prefix data retrieval system, which performs segmentation processing on the prefix tree, specifically includes: the structure of the prefix tree is divided into one segment according to each 8 layers, wherein the ith segment is a segmented tree, and 256 segments existi-1And the index entry is used for being used as a matching entry of each parallelized segmented prefix during parallel retrieval, the matching entry of the 1 st segmented prefix is a root node of the prefix tree, the matching entry is 0, and the matching entry of the ith segmented prefix except the 1 st segmented prefix is an integer value of binary representation of the preceding (i-1) segment of the segmented prefix.
The prefix data retrieval system further includes:
and the inserting module is used for acquiring the network prefix to be inserted, carrying out segmentation processing on the network prefix to be inserted, and respectively carrying out parallel inserting operation on the segmented trees of the corresponding segments.
The prefix data retrieval system, wherein the network prefix is an IPV4 network prefix.
The invention thus has the technical advances comprising:
the network prefix and the segmentation representation method of the prefix tree structure can carry out segmentation representation on the traditional prefix tree structure, and a retrieval inlet of each segment can be determined; the parallelization prefix matching technology provided by the invention can perform prefix matching and searching in parallel on each section of prefix tree structure, thereby realizing the efficiency improvement of approximate linearity. The general technical effect is that the information base construction can be carried out on the prefix information by using a segmented prefix tree structure, the specific prefix can be parallelized to obtain prefix matching search, and the prefix matching efficiency is greatly improved.
Drawings
FIG. 1 is a schematic diagram of a segmented prefix tree;
FIG. 2 is a flow chart of the method of the present invention.
Detailed Description
When the inventor conducts prefix tree algorithm optimization research, the matching search algorithm of the traditional prefix tree is found to be highly efficient for processing prefixes with short length, and the processing time is gradually increased along with the increase of the prefix length. Now, with the improvement of CPU performance and the rapid development of parallel computing, the computing power of a computer is no longer the bottleneck of improving system efficiency, and parallel programming becomes a fundamental and important part of system design. The inventors consider applying parallel programming to algorithmic optimization of prefix trees. For all prefixes, each plurality of bits is divided into a plurality of sections, and index entries in each section can be found through the prefixes during prefix matching, so that parallel searching, inserting and deleting operations can be performed on each section, and the retrieval time of the prefixes with the length of 8 can be approximated even if the longest prefixes are matched, and the retrieval efficiency is improved.
In practical application, the invention can process matching query of massive network prefixes. The technology provided by the invention firstly segments the network prefix information so as to complete a prefix information base and store the prefix information in a segmented prefix tree; when searching and inserting a new prefix, the parallelization prefix matching technology is used for operating in the prefix tree to complete the parallelization matching query of the prefix.
As shown in fig. 2, the method of the present invention comprises: step 1, segmented representation of network prefixes and prefix tree structures. And acquiring a network prefix represented by a binary system, constructing a prefix tree for the network prefix, and performing segmentation processing on the prefix tree to obtain a multi-segment segmented tree.
And performing binary representation on the network prefix, and dividing each plurality of bits into a plurality of sections. Taking IPV4 network prefix as an example, each 8 bits is a segment, and its binary representation and corresponding prefix tree structure have 32 levels, it is divided into 4 segments, i.e. the prefix tree structure is also divided into 4 segments each 8 levels, where the 32 levels is determined by the network prefix itself of IPV 4. The network binary of IPV4 requires 32 bits, namely 32 layers; if 8 bits are taken as 1 segment, 4 segments are needed; for segments where i is a positive integer, there are 256i-1An index entry, and for a particular prefix its index entry is specified by an integer number of binary representations of the first (i-1) segment prefix. In fig. 1, a prefix tree structure divided into 4 segments is shown, with dashed lines indicating the index of each segment and numbers above the nodes indicating the cable entries. 256 are leaf nodes of a full binary tree with a depth of 8. For a prefix tree with 32 layers of depth, every 8 layers are one segment, and the number of leaf nodes is 256, and the total number is 4 segments. Segment 1 has a root node as an index entry, 2561-11 inlet; paragraph 2 depends on the leaf node index of the first paragraph for a total of 2562-1256 inlets; similarly, the 3 rd section and the 4 th section respectively have 2563-1、2564-1An inlet. The index entry serves as a matching entry for each part (i.e., segment) of the parallelization when performing parallelization prefix matching.
The specific prefix refers to a target prefix given to be retrieved by a query. Taking 124.26.3.0/24, a 24-bit decimal network prefix as an example, because the length is 24, the invention only needs to consider the first 3 segments for each 8 bits: the 1 st segment index entry is the root node, and the index position (matching entry) is 0; the 2 nd segment index entry depends on the integer value of the 1 st segment, the index entry position is 124-1-123, the 3 rd segment index entry depends on the previous two segments, and the index entry position is 124-26-1-3223. Note: the index position value starts from 0.
And (3) representing the network prefix by segments, correspondingly segmenting the prefix tree, finding a retrieval inlet of each segment, and laying a foundation for parallel searching and matching. The tree structure layering is the operation corresponding to the prefix segmentation, and aims to perform parallelization retrieval on each layer after layering; it is the network prefix that is segmented that naturally leads to tree structure layering. The tree structure and the network prefix are in a corresponding relationship, and the 32-bit prefix corresponds to 32 layers of the tree structure. Every 8 bits of the prefix is a segment, and every 8 layers of the corresponding tree structure are segments.
The prefix tree is used as a storage structure for storing network prefixes, and the structure supports insertion and retrieval of prefixes. The prefix tree may be different in content in different scenarios. For example, a system needs a large amount of network prefix information to construct a prefix tree, and then prefixes used for constructing the prefix tree in the early stage are few (in an extreme case, the prefix tree is empty initially); the prefixes stored in the tree then grow progressively over time. At any point in time, a search can be made in the prefix tree.
And 2, matching parallelized prefixes. Based on the constructed segmented prefix tree structure, when a given prefix is subjected to matching query, concurrent search can be performed on each segment of the prefix tree structure, and after the search of each segment is completed, the search result of each segment is operated to obtain a final result. Obtaining binary expressed network prefix to be retrieved, carrying out segmentation processing on the network prefix to be retrieved to obtain a plurality of segmented prefixes, carrying out concurrent retrieval on the segmented trees corresponding to each segmented prefix to obtain retrieval result riAnd representing the retrieval result of the ith segment prefix in the ith segment tree, performing logic AND operation on all the retrieval results, and taking the operation result as the retrieval result of the network prefix to be retrieved.
The step 2 specifically comprises the following steps: and step 21, parallelizing prefix search. Segmenting prefixes to be searched, respectively searching on prefix trees of corresponding segments, and respectively obtaining results ri(i is 1,2,3 … N, N is the number of segments of the prefix division, and if 8 bits are one segment, N is 4), the search is performed in parallel, and the segments are performed simultaneously. Still taking the prefix 124.26.3.0/24, 8 bits as a segment as an example, the specific search process:segment 1 search 124, binary represented as 01111100, sequentially finds whether nodes exist in the segment 1 prefix tree, if so, the result r1Returning true, otherwise false; the 2 nd section and the 3 rd section are simultaneously carried out in the same way to obtain r2And r3. "corresponding" refers to a segment corresponding to a prefix segment to be searched. r isiRepresenting the search result in the ith segment, true represents that the search is successful, false represents that the search is failed, and the final search result is:
r＝r1&&r2&&r3…&&rN
wherein "& &" represents a logical AND.
And 3, parallelizing prefix insertion. And segmenting the prefix to be inserted, and respectively performing insertion operation on the prefix trees of the corresponding segments. Taking the prefix 124.26.3.0/24 to be inserted, 8 bits as a segment, the specific insertion process is as follows: inserting 124 the 1 st segment, inserting 01111100 binary representation bits into the 1 st segment prefix tree according to 0/1, if the node exists, then continuing downward without repeated insertion; similarly, the 2 nd and 3 rd sections are inserted with 26(00011010) and 3(00000011) at the same time. Thus, the parallelized insert operation is complete. The method and the device realize the matching query of the prefixes by segmentation and concurrence, realize the parallelization search and insertion operation and improve the operation efficiency.
The following are system examples corresponding to the above method examples, and this embodiment can be implemented in cooperation with the above embodiments. The related technical details mentioned in the above embodiments are still valid in this embodiment, and are not described herein again in order to reduce repetition. Accordingly, the related-art details mentioned in the present embodiment can also be applied to the above-described embodiments.
The invention also discloses a prefix data retrieval system, which comprises:
the prefix tree segmentation module is used for acquiring a network prefix represented by a binary system, constructing a prefix tree for the network prefix, and performing segmentation processing on the prefix tree to obtain a multi-segment segmented tree;
retrieval module for obtaining a binary representation to be examinedNetwork prefix is required, the network prefix to be retrieved is segmented to obtain a plurality of segmented prefixes, concurrent retrieval is carried out on the segmented tree corresponding to each segmented prefix to obtain a retrieval result riAnd representing the retrieval result of the ith segment prefix in the ith segment tree, performing logic AND operation on all the retrieval results, and taking the operation result as the retrieval result of the network prefix to be retrieved.
In the prefix data retrieval system, the segmentation process in the prefix tree segmentation module specifically includes: segmenting the prefix tree according to the preset segmentation quantity, wherein the obtained segmentation tree quantity is equal to the preset segmentation quantity;
the segmentation processing in the retrieval module specifically comprises: and segmenting the network prefix to be retrieved, wherein the number of the obtained approximate segmentation prefixes is equal to the preset segmentation number.
The prefix data retrieval system, which performs segmentation processing on the prefix tree specifically includes that the structure of the prefix tree is divided into one segment according to each 8 layers, wherein the ith segment of the segmented tree has 256 segmentsi-1And the index entry is used for being used as a matching entry of each parallelized segmented prefix during parallel retrieval, the matching entry of the 1 st segmented prefix is a root node of the prefix tree, the matching entry is 0, and the matching entry of the ith segmented prefix except the 1 st segmented prefix is an integer value of binary representation of the preceding (i-1) segment of the segmented prefix.
The prefix data retrieval system further includes:
and the inserting module is used for acquiring the network prefix to be inserted, carrying out segmentation processing on the network prefix to be inserted, and respectively carrying out parallel inserting operation on the segmented trees of the corresponding segments.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811511690.1A CN109815225B (en) | 2018-12-11 | 2018-12-11 | Parallelized prefix data retrieval method and system based on prefix tree structure |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811511690.1A CN109815225B (en) | 2018-12-11 | 2018-12-11 | Parallelized prefix data retrieval method and system based on prefix tree structure |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109815225A CN109815225A (en) | 2019-05-28 |
| CN109815225B true CN109815225B (en) | 2021-07-09 |
Family
ID=66602856
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811511690.1A Expired - Fee Related CN109815225B (en) | 2018-12-11 | 2018-12-11 | Parallelized prefix data retrieval method and system based on prefix tree structure |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109815225B (en) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103064841A (en) * | 2011-10-20 | 2013-04-24 | 北京中搜网络技术股份有限公司 | Retrieval device and retrieval method |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7440461B2 (en) * | 2003-12-23 | 2008-10-21 | Intel Corporation | Methods and apparatus for detecting patterns in a data stream |
| CN101430755A (en) * | 2008-11-13 | 2009-05-13 | 王新锋 | Label recognition anti-collision processing method in radio frequency recognition technology |
| US8160069B2 (en) * | 2009-01-30 | 2012-04-17 | Palo Alto Research Center Incorporated | System for forwarding a packet with a hierarchically structured variable-length identifier |
| US8880507B2 (en) * | 2010-07-22 | 2014-11-04 | Brocade Communications Systems, Inc. | Longest prefix match using binary search tree |
| CN105005621A (en) * | 2015-07-23 | 2015-10-28 | 张真 | Method for constructing distributed storage and parallel indexing system for big data |
| CN107967219B (en) * | 2017-11-27 | 2021-08-06 | 北京理工大学 | A high-speed search method for large-scale strings based on TCAM |
-
2018
- 2018-12-11 CN CN201811511690.1A patent/CN109815225B/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103064841A (en) * | 2011-10-20 | 2013-04-24 | 北京中搜网络技术股份有限公司 | Retrieval device and retrieval method |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109815225A (en) | 2019-05-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110083601B (en) | Key value storage system-oriented index tree construction method and system | |
| JP6028567B2 (en) | Data storage program, data search program, data storage device, data search device, data storage method, and data search method | |
| US7499912B2 (en) | Search method using coded keys | |
| US11630864B2 (en) | Vectorized queues for shortest-path graph searches | |
| US10671586B2 (en) | Optimal sort key compression and index rebuilding | |
| CN111801665B (en) | Hierarchical Locality Sensitive Hashing (LSH) Partitioned Indexes for Big Data Applications | |
| US10545915B2 (en) | Recursive multi-threaded file system scanner for serializing file system metadata exoskeleton | |
| CN113946580B (en) | A middleware for retrieval of massive heterogeneous log data | |
| CN102484610A (en) | Method and device for establishing routing table and method and device for searching routing table | |
| CN105975587A (en) | Method for organizing and accessing memory database index with high performance | |
| CN106777003B (en) | An index query method and system for Key-Value storage system | |
| CN105930345A (en) | Hierarchical indexing method based on distributed real-time database system (DRTDBS) | |
| US20170024439A1 (en) | Accelerated detection of matching patterns | |
| WO2025060127A1 (en) | Method and apparatus for constructing generative neural network tree structure, and storage medium | |
| CN102867049A (en) | Chinese PINYIN quick word segmentation method based on word search tree | |
| EP4022429A2 (en) | Vectorized hash tables | |
| CN109815225B (en) | Parallelized prefix data retrieval method and system based on prefix tree structure | |
| KR102388458B1 (en) | Method and apparatus for conversing data key value | |
| WO2013097065A1 (en) | Index data processing method and device | |
| CN1235169C (en) | Data storage and searching method of embedded system | |
| CN114090570A (en) | A data storage method and device based on the combination of radix tree and hash table | |
| CN118672501B (en) | A variable data caching method and system for NetCDF files | |
| CN115470208B (en) | A data storage method, device and storage medium based on dynamic HASH | |
| CN114443866B (en) | Data processing method, device, computing equipment and medium | |
| CN117540056B (en) | Method, device, computer equipment and storage medium for data query |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20210709 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |