CN111639082A - Object storage management method and system of billion-level node scale knowledge graph based on Ceph - Google Patents

Abstract

The invention discloses a Ceph-based object storage management method and system of a billion-level node scale knowledge graph. The method includes: constructing and designing a graph storage architecture, acquiring entity data of multiple entities corresponding to a target business, and generating entity data according to the entity data. The knowledge map corresponding to the target business is stored, and Ceph is used as a distributed resource storage, and an external index background mechanism is added at the same time, and a large task is decomposed into multiple subtasks by using a distributed computing engine, and distributed to different machines for execution. After completion, it is aggregated to provide large-scale data processing capabilities to support OLAP requirements for users to perform data analysis based on knowledge graphs. The invention also provides an object storage management system based on Ceph's billion-level node scale knowledge graph. This solution refers to the distributed resource manager, which has the characteristics of scalability and high availability, and can store and express massive knowledge at the same time. It supports the data volume of billions of nodes, and has the characteristics of reliability, ease of use and high efficiency.

Description

Object storage management method and method for a billion-level node-scale knowledge graph based on Ceph system

technical field

The invention relates to the technical field of information processing, in particular to a Ceph-based object storage management method and system of a billion-level node-scale knowledge graph.

Background technique

Knowledge graph is a kind of visualization technology to describe knowledge resources and their carriers, to mine, analyze, construct, draw and display knowledge and their interrelationships. Knowledge graphs can extract hidden knowledge from large-scale data and build a graph-based data model. In recent years, data mining, big data, artificial intelligence, machine learning, and other popular technologies related to information processing can be assisted by knowledge graphs. The ultimate purpose of these technologies is to collect and organize data into structured, accessible Reusable and reasonable storage can be used for more usage scenarios, and the storage format of knowledge graph can almost perfectly match these requirements. The knowledge graph is designed to describe various entities or concepts existing in the real world and their associations, each of which is identified by a globally unique ID, just like everyone has an ID number; The second is to use attribute-value pairs to describe the internal characteristics of entities, and use relationships to connect two entities and describe the association between them.

The biggest defect of the current graph storage system is that it is not truly distributed. In the era of big data, more and more data can be obtained, and the capacity of a single machine is limited. When the amount of data exceeds the carrying capacity of a single machine, it is difficult to process, and the underlying storage is far from Block storage and object storage have high efficiency, and graph query and graph analysis are inefficient, and the system has poor disaster tolerance and real-time performance. It is difficult to dynamically expand the capacity of hundreds of millions of nodes, and the efficiency of node association query is low.

SUMMARY OF THE INVENTION

The purpose of the present invention is to overcome the deficiencies of the prior art, and to provide a Ceph-based object storage management method and system for a knowledge graph with a scale of one billion nodes, which can process knowledge graph data on a scale of one billion nodes, and support large-scale graph data storage and maintenance. Elastic and linear expansion, high availability and fault tolerance, OLTP and CRUD features, and support for OLAP data analysis and external indexing.

The purpose of this invention is to realize through the following technical solutions:

An object storage management method based on Ceph's billion-level node-scale knowledge graph, the method includes the following steps:

S1: Construction of a graph storage architecture, obtaining entity data of multiple entities corresponding to the target business, and generating and storing the knowledge graph corresponding to the target business according to the entity data, and using Ceph as a distributed resource storage, using Client/Server architecture, a Ceph cluster is built with a small cluster composed of multiple monitors, and multiple OSDs are used to store graph data in a single monitor small cluster;

S2, the construction of an external index backend, which maps the knowledge graph data into a fixed index data structure, uses the Elasticsearch/Solr search engine as an external index plug-in, realizes non-equivalent query, and combines an efficient indexing mechanism to build an external index backend;

S3, integrates the construction of the distributed computing engine architecture, uses the Spark computing engine framework to build a distributed computing engine, and uses the GraphX library to convert the graph relationship into Spark operators. The GraphX library stores the graph data in a distributed RDD in the Ceph cluster. On the node, use vertex RDD and edge RDD to store vertex sets and edge sets respectively;

S4, graph storage architecture management, on the basis of graph storage architecture, external index backend and integrated distributed computing engine, it provides three-tier extension query, data writing, data reading, cluster expansion, metadata backup, metadata Snapshots, online transaction analysis, and online analytical processing operations are implemented to manage graph data for knowledge graphs.

Specifically, the efficient indexing mechanism in the step S2 includes a graph index and a vertex center index. The graph index is a global index structure of the entire knowledge graph; the vertex center index is a local index structure established for each vertex.

Specifically, the step S3 also includes a partition operation, which specifically includes the following sub-steps:

S101, the vertex RDD distributes the vertex data on the cluster in the form of multiple partitions by hash partitioning according to the ID of the vertex;

S102, the edge RDD is partitioned according to the specified partition strategy, and the edge data is distributed on the cluster in the form of multiple partitions;

S103, the routing table that records the partition relationship between the vertices in the RDD partition and all the edge RDD partitions is stored in the partition of the vertex RDD, and when the edge RDD needs vertex data, the vertex RDD sends the vertex data to the edge RDD partition according to the routing table.

Specifically, the data writing step in the step S4 includes the following sub-steps:

S201, the client connects to the Monitor, obtains the cluster Map information, and requests the corresponding main OSD data node;

S202, the master OSD data node writes the data of the other two replica nodes at the same time, and waits for the master node and the other two replica nodes to complete the data writing state. Writing is complete.

Specifically, the cluster expansion step in step S4 includes the following sub-steps:

S301, the Client connects to the Monitor to obtain the cluster map information, and the new master node OSD1 uploads a request to the Monitor, so that the OSD2 node replaces the OSD1 node as the temporary master node;

S302, the temporary master node OSD2 synchronizes the full amount of data to the new master node OSD1, and ClientIO read and write directly connects to the temporary master node OSD2 for data read and write;

S303, the temporary master node OSD2 receives the read and write IO, and writes the data in the other two replica nodes at the same time. After the temporary master node OSD2 and the three copies of the data in the other two replica nodes are all successfully written, a signal is returned to the Client, ClientIO finished reading and writing;

S304, if the data synchronization of the node OSD1 is completed, the temporary master node OSD2 uploads a request to the Monitor, surrenders the master node role, the OSD1 node becomes the master node again, and the OSD2 node becomes a replica node;

S305, at the same time at the graph data level, after the node expansion is realized, the graph data is cut according to the graph data cutting method, and stored on multiple machines respectively.

Specifically, the graph data cutting method includes two cutting methods: point-cutting and edge-cutting; the point-cutting method uses the vertices of the graph to cut the data, the cutting line passes through the vertices of the graph, and each edge is only saved once, and each edge is saved only once. An edge only appears on one machine, and vertices with many neighbor vertices will be distributed to multiple different machines for storage; the data is cut by the edges of the graph according to the edge cutting method, and the cutting line only passes through the edges connecting the vertices. A vertex is stored only once, and the cut edges are distributed to multiple different machines for storage.

Specifically, the metadata snapshot step in the step S4 includes: effectively restoring the previous data state according to the metadata information, and also restoring the program to the system running history state; saving the system data at a specific time point, and generating the system corresponding time point reports; export snapshot data for offline work.

Specifically, the three-layer line expansion query step in the step S4 includes the following sub-steps:

S401, set the user's given vertex set Vset as the basic data of the first-layer line expansion query, set the query filter condition of the first layer as the filter condition ConditionA of the vertex Label/vertex attribute, and perform the first-layer vertex extension line query;

S402, take the vertex set of the edge that satisfies the query filter condition of the first layer as the basic data of the line expansion query of the second layer, and set the query filter condition of the second layer as the filter condition ConditionB of the edge Label/edge attribute at the same time, and perform the second layer query filter condition B. The edge expansion line query;

S403: Use the edge set that satisfies the query filter conditions of the second layer as the basic data of the third layer extension query, set attribute query conditions, perform the attribute extension query of the third layer, and output the query result after the third layer extension query.

An object storage management system based on Ceph's billion-level node-scale knowledge graph. The system includes a graph data storage module, a distributed computing module, an indexing module and a metadata management module. Among them, the graph data storage module is used for distributed storage of object data of large-scale knowledge graph, providing object storage, block device storage and file system services;

The distributed computing module is used to use SparkRDD memory computing to decompose large tasks into multiple sub-tasks, which are deployed to different machines for execution, and aggregated after completion to provide efficient large-scale data processing capabilities to support OLAP requirements for users. Data analysis based on knowledge graph;

The index module is used to map knowledge data into a fixed index data structure, providing users with graph index, vertex center index and external index functions;

The metadata management module is used for metadata backup, metadata snapshot, program recovery, generation of point-in-time reports and system offline work.

Beneficial effects of the present invention: The scheme adds a new distributed data architecture, refers to a distributed resource manager, has main performance features such as scalability and high availability, and is mainly reflected in distributed clusters, external indexes, data reliability, distributed Resource manager aspect. At the same time, it can store and express massive knowledge, support billions of node data, and have the characteristics of reliability, ease of use and high efficiency.

Description of drawings

FIG. 1 is a flow chart of the method of the present invention.

FIG. 2 is an overall distribution architecture diagram of the present invention.

FIG. 3 is a diagram of a distributed resource management architecture of the present invention.

FIG. 4 is an architectural diagram of an integrated distributed computing engine of the present invention.

FIG. 5 is an architecture diagram of an external index plug-in of the present invention.

FIG. 6 is a flow chart of data writing of the present invention.

FIG. 7 is a flow chart of the cluster expansion of the present invention.

FIG. 8 is a system functional block diagram of the present invention.

Detailed ways

In order to have a clearer understanding of the technical features, objects and effects of the present invention, the specific embodiments of the present invention will now be described with reference to the accompanying drawings.

In this embodiment, as shown in Figures 1-2, the Ceph-based object storage management method for a billion-level node-scale knowledge graph includes the following steps:

Step 1: constructing a graph storage architecture, acquiring entity data of multiple entities corresponding to the target business, and generating and storing a knowledge graph corresponding to the target business according to the entity data. As shown in Figure 3, for the overall distributed architecture, Ceph is used as the distributed resource storage, the Client/Server architecture is used, and a Ceph cluster is constructed with a small cluster composed of multiple monitors. At the same time, multiple OSDs are used in a single monitor small cluster. Store graph data.

Step 2: First, map the knowledge graph data into a fixed index data structure. In order to have the ability to process knowledge data of billions of nodes, as shown in Figure 5, an external index background mechanism is added, and the Elasticsearch/Solr retrieval engine is used as an external index. The index plug-in of , realizes that the index can also be used when performing non-equivalent queries, and at the same time combines an efficient indexing mechanism to build an external index background. The external indexing backend and the indexing engine exchange data through API.

Step 3: Integrate the construction of the distributed computing engine architecture, use the Spark computing engine framework to build a distributed computing engine, and use the GraphX library to convert the graph relationship into Spark operators. The GraphX library stores the graph data in the Ceph cluster in a distributed manner as RDD. On the node of , use vertex RDD and edge RDD to store vertex sets and edge sets respectively.

Step 4: Graph storage architecture management. Based on the graph storage architecture, external index backend and integrated distributed computing engine, it provides three-tier extension query, data writing, data reading, cluster expansion, metadata backup, metadata Data snapshots, online transaction analysis, and online analytical processing operations are implemented to manage graph data for knowledge graphs.

In this embodiment, the efficient indexing mechanism includes a graph index and a vertex center index. The graph index is a global index structure of the entire knowledge graph. Better selectivity is obtained by indexing attributes of entities or edges, thereby speeding up graph traversal. Speed, which is equivalently retrieved by a fixed attribute combination consisting of one or a group of attributes. The vertex center index is a local index structure established for each vertex, but when there are thousands or more edges per vertex in a large graph, there will be corresponding edge filtering for traversal of these vertices, and the traversal efficiency is low , so vertex center indexing only supports leftmost matching.

Among them, for the index-based three-layer extension query, first set the vertex set Vset given by the user as the basic data of the first layer extension query, and set the query filter condition of the first layer as the filter condition ConditionA of the vertex Label/vertex attribute , and perform the vertex extension query of the first layer. Then, set the vertex set of the edges that satisfy the query filter conditions of the first layer as the basic data of the second layer extension query, and set the query filter condition of the second layer to the filter condition ConditionB of the edge Label/edge attribute, and perform the second layer query filter condition B. Edge expansion query. The last extended line query only queries the edges that satisfy ConditionB, but the vertices related to these edges only have vertex ID information, and do not contain any attribute information, and it is not sure whether ConditionA is satisfied. Therefore, another attribute query needs to be done. First, take the edge set that satisfies the query filter conditions of the second layer as the basic data of the third layer extension query, set the attribute query conditions, perform the attribute extension query of the third layer, and output the query result after the third layer extension query. Implementing efficient indexing as above comes into play.

In this embodiment, as shown in Figure 4, in order to support the OLA requirement P, a set of high-performance computing framework APIs is also extended to support Spark, and the GraphX library is used to convert graph relationships into Spark operators, and GraphX distributes graph data as RDDs It is stored on the nodes of the cluster in the form of a vertex RDD (VertexRDD) and an edge RDD (EdgeRDD) to store the vertex set and the edge set. Vertex RDD distributes vertex data on the cluster in the form of multiple partitions by hash partitioning by vertex ID. The edge RDD is partitioned according to the specified partition strategy (PartitionStrategy), and the edge data is distributed on the cluster in the form of multiple partitions. In addition, the vertex RDD also has the routing information of the vertex to the edge RDD partition - the routing table. The routing table exists in the partition of the vertex RDD, and it records the relationship between the vertices in the partition and all the edge RDD partitions. When the edge RDD needs vertex data, the vertex RDD will send the vertex data to the edge RDD partition according to the routing table. So far, the graph data is stored as Spark's RDD.

At the bottom layer of Spark, the operator execution starts the SparkContext, and the SparkContext registers with the resource manager and applies to run the Executor resource. The resource manager allocates the Executor resource and starts the StandaloneExecutorBackend (task scheduling). The running status of the Executor will be sent to the resource manager along with the heartbeat. SparkContext builds a DAG graph, decomposes the DAG graph into Stages, and sends the Taskset to the TaskScheduler. Executor applies for Task to SparkContext, TaskScheduler distributes Task to Executor to run, and SparkContext distributes application code to Executor, Task runs on Executor, and all resources are released after running. So as to achieve efficient mapEdges, mapVertices, aggregateMessages and other operations, quickly respond to data analysis needs.

In this embodiment, as shown in FIG. 6 , for data writing, the client (Client) connects to the Monitor, obtains the cluster map information, and requests the corresponding main OSD data node. The main OSD data node simultaneously writes to the other two replica nodes Data, wait for the master node and the other two replica nodes to finish writing the data status. After the master node and the replica node write the status successfully, return it to the Client, and the data writing is completed. The way of data read is the same as that of data write.

In this example, for cluster expansion, the Client connects to the Monitor to obtain the cluster map information. At the same time, since the new master node OSD1 has no PG (Placement Grouops) data, it will actively report to the Monitor, telling the OSD2 node to temporarily replace the master node. The temporary master node OSD2 will synchronize the full data to the new master node OSD1, and ClientIO reads and writes directly to the temporary master node. The node OSD2 reads and writes, the OSD2 node receives the read and write IO, and writes to the other two replica nodes at the same time, waiting for the OSD2 node and the other two replica nodes to be successfully written, and after the three copies of the OSD2 node data are written successfully, a signal is returned to the Client. . At this point, ClientIO has finished reading and writing. If the data synchronization of the OSD1 node is completed, the temporary master node OSD2 uploads a request to the Monitor. The temporary master node OSD2 will hand over the master role, OSD1 will become the master node, and OSD2 will become the replica node. , At the same time, at the graph data level, after the expansion is realized, the graph is cut, that is, the data needs to be divided and stored on multiple machines. The first type of cutting is point-by-point cutting, and the cutting line passes through the vertices of the graph (Vertex), not edges. (Edge). Each edge is only saved once, and each edge only appears on one machine, and vertices with many neighbors will be distributed to different machines; the second type is cut by edge, and the cutting line only passes through the edge connecting the vertices (Edge ), each vertex is saved only once, and the cut edge will be saved to multiple machines, so far the cluster expansion is completed.

In this embodiment, an object storage management system based on Ceph's billion-level node-scale knowledge graph is also provided. The system includes a graph data storage module, a distributed computing module, an index module and a metadata management module.

Among them, the graph data storage module is used for distributed storage of object data of large-scale knowledge graph, and provides object storage, block device storage and file system services.

The distributed computing module is used to use SparkRDD memory computing to decompose large tasks into multiple sub-tasks, which are deployed to different machines for execution, and aggregated after completion to provide efficient large-scale data processing capabilities to support OLAP requirements for users. Data analysis based on knowledge graph.

The index module is used to map knowledge data into a fixed index data structure, providing users with graph index, vertex center index and external index functions.

The metadata management module is used for metadata backup, metadata snapshot, program recovery, generation of point-in-time reports and system offline work.

In this embodiment, the whole specific implementation scheme can be applied to anti-fraud detection scenarios. That is to say, a heterogeneous network is constructed with user information, device information and social relations, and the heterogeneous network graph is applied in user association analysis and anti-fraud detection scenarios. After importing the data, the number of nodes reaches the order of magnitude of 1.1 billion, and the relational data reaches the order of magnitude of about 50 billion, forming a complex heterogeneous network including 11 types of nodes and 13 types of edges. Screen suspicious users through specific rules, and view users with specific associations with suspicious users; view network characteristics and user characteristics of subnets composed of all users with specific associations with suspicious users; analyze what kind of associations specific users can be associated with ; It can analyze data of up to 6 layers of association relationships to complete a series of data analysis tasks. In the graph of this patent with 1.1 billion nodes, compared with the existing graph storage system, the graph traversal and query response time of this solution are improved. 4x to 100x faster. The comparison between this technical solution and the existing map storage solution is as follows:

Table 1 Data Loading

This technical solution NEO4J-OFFLINE NEO4J-CYPHER 45375 seconds Not completed within 24 hours Not completed within 24 hours

Table 2 Data storage size

This technical solution NEO4J-OFFLINE NEO4J-CYPHER 609375MB 275950MB 1276175MB

Table 3 Query performance

This technical solution NEO4J-OFFLINE NEO4J-CYPHER 7.5 ms 55.0 ms 34.1 ms

The basic principles and main features of the present invention and the advantages of the present invention have been shown and described above. Those skilled in the art should understand that the present invention is not limited by the above-mentioned embodiments, and the descriptions in the above-mentioned embodiments and the description are only to illustrate the principle of the present invention. Without departing from the spirit and scope of the present invention, the present invention will have Various changes and modifications fall within the scope of the claimed invention. The claimed scope of the present invention is defined by the appended claims and their equivalents.

Claims (9)

1. An object storage management method based on a billion-level node-scale knowledge graph of Ceph, characterized in that, comprising the following steps: S1: Construction of a graph storage architecture, obtaining entity data of multiple entities corresponding to the target business, and generating and storing the knowledge graph corresponding to the target business according to the entity data, and using Ceph as a distributed resource storage, using Client/Server architecture, a Ceph cluster is built with a small cluster composed of multiple monitors, and multiple OSDs are used to store graph data in a single monitor small cluster; S2, the construction of an external index backend, which maps the knowledge graph data into a fixed index data structure, uses the Elasticsearch/Solr search engine as an external index plug-in, realizes non-equivalent query, and combines an efficient indexing mechanism to build an external index backend; S3, integrates the construction of the distributed computing engine architecture, uses the Spark computing engine framework to build a distributed computing engine, and uses the GraphX library to convert the graph relationship into Spark operators. The GraphX library stores the graph data in a distributed RDD in the Ceph cluster. On the node, use vertex RDD and edge RDD to store vertex sets and edge sets respectively; S4, graph storage architecture management, on the basis of graph storage architecture, external index backend and integrated distributed computing engine, it provides three-tier extension query, data writing, data reading, cluster expansion, metadata backup, metadata Snapshots, online transaction analysis, and online analytical processing operations are implemented to manage graph data for knowledge graphs. 2. the object storage management method based on the billion-level node scale knowledge graph of Ceph according to claim 1, is characterized in that, in described step S2, the efficient indexing mechanism comprises graph index and vertex center index, and graph index is the whole. The global index structure of the knowledge graph; the vertex center index is a local index structure established for each vertex. 3. The object storage management method based on Ceph's billion-level node-scale knowledge graph according to claim 1, is characterized in that, in described step S3, also comprises partition operation, specifically comprises the following sub-steps: S101, the vertex RDD distributes the vertex data on the cluster in the form of multiple partitions by hash partitioning according to the ID of the vertex; S102, the edge RDD is partitioned according to the specified partition strategy, and the edge data is distributed on the cluster in the form of multiple partitions; S103, the routing table that records the partition relationship between the vertices in the RDD partition and all the edge RDD partitions is stored in the partition of the vertex RDD, and when the edge RDD needs vertex data, the vertex RDD sends the vertex data to the edge RDD partition according to the routing table. 4. The object storage management method based on a Ceph-based billion-level node-scale knowledge graph according to claim 1, wherein the data writing step in the step S4 comprises the following sub-steps: S201, the client connects to the Monitor, obtains the cluster Map information, and requests the corresponding main OSD data node; S202, the master OSD data node writes the data of the other two replica nodes at the same time, and waits for the master node and the other two replica nodes to complete the data writing state. Writing is complete. 5. The object storage management method based on Ceph's billion-level node scale knowledge graph according to claim 1, wherein the cluster expansion step in the step S4 comprises the following substeps: S301, the Client connects to the Monitor to obtain the cluster map information, and the new master node OSD1 uploads a request to the Monitor, so that the OSD2 node replaces the OSD1 node as the temporary master node; S302, the temporary master node OSD2 synchronizes the full amount of data to the new master node OSD1, and ClientIO read and write directly connects to the temporary master node OSD2 for data read and write; S303, the temporary master node OSD2 receives the read and write IO, and writes the data in the other two replica nodes at the same time. After the temporary master node OSD2 and the three copies of the data in the other two replica nodes are all successfully written, a signal is returned to the Client, ClientIO finished reading and writing; S304, if the data synchronization of the node OSD1 is completed, the temporary master node OSD2 uploads a request to the Monitor, surrenders the master node role, the OSD1 node becomes the master node again, and the OSD2 node becomes a replica node; S305, at the same time at the graph data level, after the node expansion is realized, the graph data is cut according to the graph data cutting method, and stored on multiple machines respectively. 6. The object storage management method based on a Ceph-based billion-level node-scale knowledge graph according to claim 4, wherein the graph data cutting method comprises two cutting methods: cutting by point and cutting by edge; The cutting method uses the vertices of the graph to cut the data. The cutting line passes through the vertices of the graph. Each edge is only saved once, and each edge only appears on one machine. The vertices with many neighbor vertices will be distributed to multiple different machines. The data is cut by the edge of the graph according to the edge cutting method, the cutting line only passes through the edge connecting the vertices, each vertex is only saved once, and the cut edge is distributed to multiple different machines for storage. 7. The object storage management method based on Ceph's billion-level node-scale knowledge graph according to claim 1, wherein the metadata snapshot step in the step S4 comprises: according to the metadata information, effectively restore to the previous It can also restore the program to the historical state of the system operation; save the system data at a specific time point, and generate a report at the corresponding time point of the system; export snapshot data for offline work. 8. The object storage management method based on Ceph's billion-level node scale knowledge graph according to claim 1, wherein the three-layer extension query step in the step S4 comprises the following substeps: S401, set the user's given vertex set Vset as the basic data of the first-layer line expansion query, set the query filter condition of the first layer as the filter condition ConditionA of the vertex Label/vertex attribute, and perform the first-layer vertex extension line query; S402, take the vertex set of the edge that satisfies the query filter condition of the first layer as the basic data of the line expansion query of the second layer, and set the query filter condition of the second layer as the filter condition ConditionB of the edge Label/edge attribute at the same time, and perform the second layer query filter condition B. The edge expansion line query; S403: Use the edge set that satisfies the query filter conditions of the second layer as the basic data of the third layer extension query, set attribute query conditions, perform the attribute extension query of the third layer, and output the query result after the third layer extension query. 9. An object storage management system based on Ceph's billion-level node-scale knowledge graph, characterized in that it includes The graph data storage module is used for distributed storage of object data of large-scale knowledge graphs, and provides object storage, block device storage and file system services; The distributed computing module is used to use SparkRDD in-memory computing to decompose large tasks into multiple sub-tasks, which are deployed to different machines for execution, and aggregated after completion to provide efficient large-scale data processing capabilities to support OLAP requirements. Users perform data analysis based on knowledge graphs; The index module is used to map knowledge data into a fixed index data structure, providing users with graph index, vertex center index and external index functions; Metadata management module for metadata backup, metadata snapshot, program recovery, generation of point-in-time reports and system offline work.

Images