CN116303763A - Distributed graph database incremental graph partitioning method and system based on vertex degree - Google Patents

Abstract

The invention discloses a distributed graph database incremental graph dividing method and system based on vertex degrees. By tracking the change of the degree of the vertex of the graph, the high-order vertex and the connected edges thereof are rapidly divided, and the online partition decision of each transaction is made in real time while a single OLTP operation is serviced. As clients initiate requests to the graph database, the invention adjusts partitions incrementally in multiple stages according to the increase of related graph information (change of vertex degree), and is mainly divided into three steps: hash partitioning phase, vertex repartitioning phase, edge repartitioning phase. The method is suitable for the OLTP load, continuously updates the local data of the graph, and responds to graph queries of a plurality of clients. The distributed server can be provided with excellent load balancing through smaller system overhead, so that better data locality is realized; thereby increasing the parallelism of access and the throughput of the graph database.

Description

A method and system for incremental graph division of distributed graph database based on vertex degree

technical field

The invention belongs to the field of distributed graph databases, in particular to a method and system for dividing incremental graphs of distributed graph databases based on vertex degrees.

Background technique

The distributed graph database will receive queries from multiple clients at the same time, and an inappropriate incremental graph partitioning method will lead to excessive load on some servers in the cluster and slow down the overall transaction processing speed. A distributed graph database must process transactions quickly, so its graph partitioning algorithm needs to be able to make fast online decisions. When the partitioning algorithm of the distributed graph database is working, it is often impossible to fully grasp the global and local graph structures, and can only perform partitioning calculations based on a small part of the graph information. In addition, in real graph databases, a very sparse graph data is often stored. There are a large number of low-degree nodes in this graph data, but at the same time, some nodes have a large number of connected edges. If these vertices are divided into To the same server, it will greatly reduce the graph traversal speed starting from these vertices, thus reducing the throughput of the graph database.

Existing incremental graph partitioning techniques are divided into point partitioning and edge partitioning. Vertex division divides the vertex set of the graph into several parts, so the edges in the graph may become cut edges because the two vertices are divided into different subgraphs. The size of the cut edge set will directly affect the communication cost of the distributed algorithm. Typical The point division algorithm such as LDG algorithm, Fennel algorithm and so on. Edge division is to divide the edge set of the graph into several parts. Therefore, when the adjacent edges of a vertex are divided into different subgraphs, this point will exist in multiple graph partitions and become a cut point. The cut point set The size of will also affect the communication cost of distributed algorithms, typical edge partitioning algorithms such as Grid algorithm, Greedy algorithm, etc.

The existing incremental graph partitioning methods are not suitable for the above-mentioned characteristics of distributed graph databases. The above graph partitioning algorithm can only be partitioned based on a large amount of graph information, and the decision-making speed is very slow. In addition, the existing graph division vertices do not re-divide the vertices. In a distributed graph database, as the graph structure changes, the original partition may no longer be applicable to the current graph. Existing incremental graph partitioning algorithms cannot properly partition the above-mentioned sparse graph data without resource consumption and significantly reducing the throughput of the graph database.

Existing distributed graph databases, such as Nebula Graph or JanusGraph, use a simple hash algorithm to partition graph data. Although load balancing can be achieved to a certain extent, they lack optimization of the cut set size. That is: this partitioning algorithm cannot control the communication cost between servers.

To sum up, in the field of distributed graph databases, there is no high-performance online graph partitioning method that can serve OLTP transactions.

Contents of the invention

The object of the present invention is to provide a method and system for incremental graph division of a distributed graph database based on the vertex degree to address the deficiencies of the prior art. In many cases, distributed graph databases will receive highly concurrent requests from multiple clients, and ultra-high workloads require distributed graph databases to be able to provide high-quality services for applications. As OLTP operations are performed, i.e., insertion of vertices and edges, the degree of vertices can vary greatly. When a large-degree vertex v is partitioned by an inappropriate graph partitioning method, when the graph traversal or query operation starts from v, it will consume a lot of time to load the connection edges of v, which will reduce the speed of transaction processing, thus reducing the graph database. throughput. This method can respond to the dynamic change of vertex degree in time, improve the parallelism of accessing height vertices, improve data locality, and form more balanced partitions.

The purpose of the present invention is achieved through the following technical solutions: a method for dividing incremental graphs of distributed graph databases based on vertex degrees, the method comprising the steps of:

S1. Initialize the counters in the graph database, initialize the counters maintained in the memory to 0, and the counters are used to record the state of the vertices in each partition of the graph database and the state of the partitions in the server where the storage service is deployed, including the state of the vertices The position, the current split state of the vertex, and the number of connected edges of the vertex on the current server and other servers where the storage service is deployed;

S2. Hash division, obtain the hash value of the vertex id in the current data graph through the hash function, and the hash values of all inserted vertex ids, take the modulus of the total number of servers, and hash the vertices and their connected edges partition while updating the counters stored on the server;

S3. Vertex re-division. With the execution of OLTP transactions, all vertices and related data in the following steps are moved and updated asynchronously; when the number of edges connected to a vertex v exceeds the threshold ThresholdR, the evaluation will move v from the current server to other servers' gains, and move v to the server with the greatest gain; update the counter stored on the server;

S4, edge re-division, when the number of connection edges stored in a certain vertex v in the storage engine exceeds the threshold ThresholdE, without moving the vertex v, redistribute the positions of these connection edges, and the outgoing edges and Its target vertex is split to the same server, and the incoming edge of vertex v and its source vertex are split to the same server; the counter stored on the server is updated.

Further, the counter in the step S1 includes:

On the server that currently stores the vertex v, the value 1 or 0 of the counter split(v) indicates whether the edge of the vertex v has been split;

On the server where the vertex v is originally or currently stored, the exact location of v is indicated by the counter location(v);

Vertex v will have up to four counters, which are used to record the information of the connected edges of the vertex:

The counter acto(v) is used to indicate the number of edges of the target vertex and v stored on the same server in the outgoing edge set of v, and acto(v) is only stored on the machine that actually stores v;

The counter acti(v) is used to indicate the number of edges in v’s incoming edge set where the source vertices and v are stored on the same server, and acti(v) is only stored on the server that actually stores v;

The counter poto(v) is used to indicate the number of edges in v’s outgoing edge set where the target vertex and v are not stored on the same server, and poto(v) is only stored on the server that stores v’s neighbor vertices;

The counter poti(v) is used to indicate the number of edges in v’s incoming edge set where the source vertex and v are not stored on the same server, and poti(v) is only stored on the server that stores v’s neighbor vertices.

On each server, the sum of the total number of vertices and edges for the partitions stored on the server is represented by the counter size.

Further, the steps of updating the stored counter in S2 are as follows:

On the server currently storing vertex v, by calculating the hash value of the target vertex u of the inserted edge e and the location(u) stored in the current server, it can be determined whether the target vertex u and v of the inserted edge e are stored in the same server .

If u and v are on the same server, the value of acto(v) is increased by 1;

If u and v are not on the same server, the value of poti(u) is increased by 1;

Similarly, on the server storing vertex u, the counter will be updated accordingly.

Further, the specific steps of re-dividing the vertices in the step S3 are as follows:

并将v移动到profit最大的服务器，即目标服务器，表示为S_target，收益profit评估公式如下：First evaluate the benefit of moving v from the current server S _now to some other server Si

And move v to the server with the largest profit, that is, the target server, denoted as S _target , and the profit evaluation formula is as follows:

为移动后v出边集中目标顶点和v不存储在同一服务器上的边的数量，/>

为移动后v入边集中源顶点和v不存储在同一个服务器上的边的数量，

为当前服务器v出边集中目标顶点和v存储在同一服务器上的边的数量，

为当前服务器v入边集中源顶点和v存储在同一服务器上的边的数量，/>

和

分别为移动后服务器和当前服务器中存储的分区的顶点和边总数的和。in,

is the number of edges where the target vertex and v are not stored on the same server in the set of v outbound edges after the move, />

is the number of edges whose source vertices and v are not stored in the same server in v's inbound edge set after moving,

For the current server v, the number of edges in the target vertex and v stored on the same server,

For the current server v, the number of edges in the pool of source vertices and v stored on the same server, />

and

are the sum of the total number of vertices and edges of the partitions stored in the moved server and the current server, respectively.

Further, the step of updating the counter stored on the server in the step S3 is as follows:

After completing the re-division of vertex v, it is necessary to update the value of the counter maintained in memory by vertex v and v's neighbor vertices:

Move location(v) from the current server S _now to the target server S _target ;

The size value of the current server S _now is reduced by 1, and the size value of the target server S _target is increased by 1;

In the original server, poto(v) will be updated to the value of acto(v), and the value of poti(v) will be updated to the value of acti(v); in the target server, the value of acto(v) will be updated to poto (v), the value of acti(v) will be updated to the value of poti(v);

For the neighbor vertices of v stored in the original server, the source vertex v _{i and} acto(v _i ) of each edge in v’s incoming edge set are reduced by 1; the target vertex v _j of each edge in v’s outgoing edge set, acti(v _j ) decrease by 1;

For the neighbor vertices stored in the target server, the source vertex v _k of each edge in the v incoming edge set, acto(v _k ) increases by 1; the target vertex v _s of each edge in the v outgoing edge set, acti(v _s ) increase by 1.

Further, the operation of updating the counter in step S4 is: clear all edge counters of vertex v, update split(v), ensure that vertex v will not be redistributed, and update location(v).

Further, in the steps S3 and S4, after updating the counter in the memory, in the current transaction, add the vertex to the pending vertex repartition queue. After the current transaction is completed, immediately stop processing the request related to the vertex, reject the client that initiated the request, and synchronize the state of the vertex with the client. After the client synchronizes the state, it initiates a request to the correct server again.

According to another aspect of the description, a distributed graph database incremental graph partition system based on vertex degree is provided. The system is a graph database and is divided into three service modules, namely, a computing service module, a storage service module and metadata service module;

The computing service module includes several query engines, which are used to analyze the query requests initiated by the client and execute OLTP transactions;

The storage service module includes several storage engines, and each storage engine is divided into multiple graph partitions; it is used to save the outgoing edge set and incoming edge set of each vertex;

The metadata service module includes several metadata service engines, and the metadata service engine includes a metadata manager, a partition manager and other operation and maintenance managers; the metadata service engine obtains the changed vertices or edges, and executes the counter Initialization, hash partitioning, vertex repartitioning, and edge repartitioning.

Advantage of the present invention and beneficial effect are:

This paper proposes an incremental graph partitioning method suitable for distributed graph databases that can quickly respond to changes in the degree of graph vertices. Distributed graph databases generally only perform addition, deletion, modification, and query operations on a small part of the graph. These operations are often issued concurrently by multiple clients and need to complete immediately. By emphasizing the location of high-order vertices and their adjacent edges, the algorithm does not need to obtain the information of the whole graph to determine the location of new vertices or edges.

Ability to quickly partition new vertices and edges with limited resources. With the increase of vertex connectivity in the graph, only a small amount of memory is required, and the present invention can quickly perform fast online decision-making in each OLTP transaction, and re-divide the positions of vertices and edges.

Partition results can serve OLTP operations well. By having the client and server share the same information, most vertices can be accessed with a single hop. The method provided by the invention can improve data locality, realize server load balancing, and increase the client's ability to access high-order vertices in the graph. The present invention can greatly improve the query performance of the graph database only by using a small overhead.

Realize a graph database with higher throughput and concurrent access capabilities. By implementing the method of the present invention in an existing graph database and using an appropriate partition method, the throughput and concurrency of the graph database can be greatly improved.

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is the architectural diagram of the system of the present invention;

FIG. 2 is a schematic diagram of a default division stage in an embodiment of the present invention;

FIG. 3 is a schematic diagram of a vertex re-division stage in an embodiment of the present invention;

Fig. 4 is a schematic diagram of an edge re-partitioning stage in an embodiment of the present invention.

Detailed ways

In order to make the above objects, features and advantages of the present invention more comprehensible, specific implementations of the present invention will be described in detail below in conjunction with the accompanying drawings.

In the following description, a lot of specific details are set forth in order to fully understand the present invention, but the present invention can also be implemented in other ways different from those described here, and those skilled in the art can do it without departing from the meaning of the present invention. By analogy, the present invention is therefore not limited to the specific examples disclosed below.

The present invention provides a method for dividing an incremental graph of a distributed graph database based on vertex degree, and the method includes the following steps:

(1) Counter initialization. Maintain a series of counters in memory to determine the state of the vertices in each partition and the state of the partitions in the server, and initialize all counters to 0.

(1.1) On the server currently storing vertex v, use split(v) to indicate whether the edge of vertex v has been split;

(1.2) On the server that initially or currently stores the vertex v, the exact location of v is represented by location(v);

(1.3) The counter acto(v) is used to indicate the number of edges of the target vertex and v stored on the same server in the outbound edge set of v, and acto(v) is only stored on the machine that actually stores v;

The counter acti(v) is used to indicate the number of edges in v’s incoming edge set where the source vertices and v are stored on the same server, and acti(v) is only stored on the server that actually stores v;

The counter poto(v) is used to indicate the number of edges in v’s outgoing edge set where the target vertex and v are not stored on the same server, and poto(v) is only stored on the server that stores v’s neighbor vertices;

The counter poti(v) is used to indicate the number of edges in v’s incoming edge set where the source vertex and v are not stored on the same server, and poti(v) is only stored on the server that stores v’s neighbor vertices.

On each server, the sum of the total number of vertices and edges for the partitions stored on the server is represented by the counter size.

(2) Hash division stage. Obtain the hash value of the vertex id in the current data graph through the hash function, as well as the hash value of all inserted vertex ids, take the modulus of the total number of servers, divide the vertices and their connected edges by hash, and update the server at the same time Stored counter; take the client to initiate an edge insertion request and successfully insert an edge e (vertex v->vertex u) as an example:

(2.1) On the server currently storing vertex v, by calculating the hash value of u and the location(u) stored in the current server, it can be determined whether the target vertex u of e is stored in the same server.

a) If u is on the same server, the value of acto(v) is increased by 1;

b) If u is not on the same server, increment the value of poti(u) by 1.

(2.2) Similarly, on the server storing vertex u, the counter will be updated accordingly.

(3) Vertex redivision stage. As the client initiates a graph query request and executes OLTP transactions, when the number of connected edges of a certain vertex v exceeds the preset threshold ThresholdR, the position of the vertex is re-divided, and the counter stored on the server is updated at the same time.

并将v移动到/>

最大的服务器，即目标服务器，表示为S_target，收益/>

评估公式如下：(3.1) First evaluate the benefit of moving v from the current server S _now to another server S _i

and move v to />

The largest server, namely the target server, denoted as S _target , yields />

The evaluation formula is as follows:

为移动后v出边集中目标顶点和v不存储在同一服务器上的边的数量，/>

为移动后v入边集中源顶点和v不存储在同一个服务器上的边的数量，

为当前服务器v出边集中目标顶点和v存储在同一服务器上的边的数量，

为当前服务器v入边集中源顶点和v存储在同一服务器上的边的数量，/>

和

分别为移动后服务器和当前服务器中存储的分区的顶点和边总数的和。in,

is the number of edges where the target vertex and v are not stored on the same server in the set of v outbound edges after the move, />

is the number of edges whose source vertices and v are not stored in the same server in v's inbound edge set after moving,

For the current server v, the number of edges in the target vertex and v stored on the same server,

For the current server v, the number of edges in the pool of source vertices and v stored on the same server, />

and

are the sum of the total number of vertices and edges of the partitions stored in the moved server and the current server, respectively.

(3.2) After completing the re-division of vertex v, it is necessary to update the value of the counter maintained in memory by vertex v and v's neighbor vertices:

Move location(v) from the current server S _now to the target server S _target ;

The size value of the current server _Snow is decreased by 1, and the size value of the target server S _target is increased by 1.

In the original server, poto(v) will be updated to the value of acto(v), and the value of poti(v) will be updated to the value of acti(v); in the target server, the value of acto(v) will be updated to poto (v), the value of acti(v) will be updated to the value of poti(v).

For the neighbor vertices of v stored in the original server, the source vertex v _{i and} acto(v _i ) of each edge in v’s incoming edge set are reduced by 1; the target vertex v _j of each edge in v’s outgoing edge set, acti(v _j ) Decrease by 1.

For the neighbor vertices stored in the target server, the source vertex v _k of each edge in the v incoming edge set, acto(v _k ) increases by 1; the target vertex v _s of each edge in the v outgoing edge set, acti(v _s ) increase by 1.

(4) Edge re-division stage. When the number of connected edges of a certain vertex v exceeds the preset threshold ThresholdE, the edges of the vertex v are re-divided (the vertex v is not moved), and the counter maintained in the memory is updated.

(4.1) Split the outgoing edge of vertex v and its target vertex to the same server;

(4.2) Split the incoming edge of vertex v and its source vertex to the same server;

(4.3) Clear all edge counters of vertex v, update split(v), and ensure that vertex v will not go through the reallocation phase again;

(4.4) Update location(v).

(5) In the above steps (3) and (4), in order to avoid blocking OLTP operations, all vertices and related data are moved asynchronously.

(5.1) In stage (3), after determining the target server for vertex movement and updating the counter in the memory, add the vertex to the pending vertex repartition queue, stop providing services about the vertex, and reject the requester client, and synchronize the vertex state with the client.

(5.2) In stage (4), after updating the counter in memory, add the connected edges of this vertex to the pending edge repartition queue, stop providing services about edges that are not stored locally, and refuse to initiate the request , and synchronize the state of the vertex and its connected edges with the client.

As shown in FIG. 1 , an embodiment of the present invention provides a distributed graph database incremental graph partitioning system based on vertex degree. The distributed graph database server is divided into three service modules, namely computing service module, storage service module and metadata service module.

The computing service module includes several query engines, which are used to analyze the query requests initiated by the client and execute OLTP transactions;

The storage service module includes several storage engines, and each storage engine is divided into multiple graph partitions; since the graph database supports bidirectional traversal, the storage engine should save the outgoing edge set and incoming edge set of each vertex.

The metadata service module includes several metadata service engines, and the metadata service engine includes a metadata manager, a partition manager and other operation and maintenance managers; the metadata service engine obtains the changed vertices or edges, and executes the counter Initialization, hash partitioning, vertex repartitioning, and edge repartitioning.

In this embodiment, an example will be used to further illustrate the above-mentioned incremental graph division method of a distributed graph database based on vertex degree.

In this embodiment, it is assumed that the threshold ThresholdR of the vertex re-division stage is 6, and the threshold ThresholdE of the edge re-division stage is 7.

The threshold ThresholdR of the vertex re-division stage and the threshold ThresholdE of the edge re-division stage can be obtained through experiments. In multiple data sets similar to the actual application scene data, use different thresholds to construct graphs, count the edge cutting rate corresponding to each threshold and the number of re-divided vertices or edges as the cost, and select the value with the smallest cost as the actual application. threshold.

Assume that this sample cluster has three servers. At this time, the client sends continuous insert requests, and the figure after the insert is completed is shown in Figure 2. In the initial default division stage, after calculating the hash value for each vertex, it is divided into 3 partitions by modulo 3. The solid line vertex in FIG. 2 indicates that the vertex is stored in the local server, and the dotted line vertex indicates that the vertex is not stored in the local server. In order to realize the two-way traversal of the graph database, each edge will be stored twice. For example, the edge (v->x) is stored as the outgoing edge of vertex v in server 1, and is stored as the incoming edge of vertex x in server 2. Therefore, the server The size of 1 is 8, the size of server 2 is 6, and the size of server 3 is 4.

In server 1, only the side (v->y) represents the actual connection side, so acto(v)=1, acti(y)=1, and other sides are only potential connection relationships, that is, stored in another On the two servers, poti(x)=1, poti(z)=1, poti(u)=1, poti(s)=1, poti(w)=1. In server 2 and server 3, vertex v is not stored, only an index of vertex v is saved.

At this time, the degree of vertex v in server 1 is 6, which has reached the threshold for vertex re-division. Calculate the profit value of server 2 as 2*(2+1)-2*(1+0)+(6-8)=2, and the profit value of server 3 as 2*(1+1)-2*(1+ 0)+(4-8)=-2, so the vertex v will be re-divided from server 1 to server 2, and the partition map after vertex re-division and the counter value stored in the server are shown in Figure 3. In server 1, acti (y)=0, size=7; in server 2, acto(v)=2, acti(v)=0, acto(u)=1, acti(s)=0, acti(x)=1, size= 7; poto(v)=1, poti(v)=1, size=4 in server 3.

The client sends a request to insert an edge (v->t) again. After the transaction is executed, the degree of vertex v in server 1 is 7, which has reached the threshold for edge re-division. As shown in Fig. 4, before splitting, the incoming edge set of the vertex v stored in the graph partition storage engine 1 is (u, z), and the outgoing edge set is (s, t, w, y, x). At this time, all edges are stored on server 1. After splitting, they will be distributed on all three servers according to the positions of their respective target vertices and source vertices. The content stored in the server storage engine is: stored in graph partition storage engine 1 The set of incoming edges of vertex v is (), the set of outgoing edges is (t, y), the set of incoming edges of vertex v stored in graph partition storage engine 2 is (u), and the set of outgoing edges is (s, x), The incoming edge set of the vertex v stored in the graph partition storage engine 3 is (x), and the outgoing edge set is (w).

The current common graph partitioning algorithms Fennel, Hash and the incremental graph partitioning method of the distributed graph database based on the vertex degree in the present invention are respectively applied for testing. The following table 1 shows the multiple performance comparisons between the present invention and other traditional graph division methods. The number of vertices in the graph used in the test is on the order of millions, and the number of edges is on the order of tens of millions.

Table 1 method of the present invention and Fennel, Hash performance contrast

It can be seen from the above table that the graph traversal (four steps) time required by the method provided by the embodiment of the present invention is shorter than that of Fennel and Hash, and the edge cutting rate is also smaller than that of the two methods of Fennel and Hash.

The above descriptions are only preferred embodiments of one or more embodiments of this specification, and are not intended to limit one or more embodiments of this specification. Within the spirit and principles of one or more embodiments of this specification, Any modification, equivalent replacement, improvement, etc. should be included in the scope of protection of one or more embodiments of this specification.

Claims (9)

1. A distributed graph database incremental graph division method based on vertex degree, it is characterized in that, the method comprises the steps: S1. Initialize the counters in the graph database, initialize the counters maintained in the memory to 0, and the counters are used to record the state of the vertices in each partition of the graph database and the state of the partitions in the server where the storage service is deployed, including the state of the vertices The position, the current split state of the vertex, and the number of connected edges of the vertex on the current server and other servers where the storage service is deployed; S2. Hash division, obtain the hash value of the vertex id in the current data graph through the hash function, and the hash values of all inserted vertex ids, take the modulus of the total number of servers, and hash the vertices and their connected edges partition while updating the counters stored on the server; S3. Vertex re-division. With the execution of OLTP transactions, all vertices and related data in the following steps are moved and updated asynchronously; when the number of edges connected to a vertex v exceeds the threshold ThresholdR, the evaluation will move v from the current server to other servers' gains, and move v to the server with the greatest gain; update the counter stored on the server; S4, edge re-division, when the number of connection edges stored in a certain vertex v in the storage engine exceeds the threshold ThresholdE, without moving the vertex v, redistribute the positions of these connection edges, and the outgoing edges and Its target vertex is split to the same server, and the incoming edge of vertex v and its source vertex are split to the same server; the counter stored on the server is updated. 2. the distributed graph database incremental graph division method based on vertex degree according to claim 1, is characterized in that, counter comprises in the described S1: On the server that currently stores the vertex v, the value 1 or 0 of the counter split(v) indicates whether the edge of the vertex v has been split; On the server where the vertex v is originally or currently stored, the exact location of v is indicated by the counter location(v); Vertex v will have at most the following four counters, which are used to record the information of the connected edges of the vertex: The counter acto(v) is used to indicate the number of edges of the target vertex and v stored on the same server in the outgoing edge set of v, and acto(v) is only stored on the server that actually stores v; The counter acti(v) is used to indicate the number of edges in v’s incoming edge set where the source vertices and v are stored on the same server, and acti(v) is only stored on the server that actually stores v; The counter poto(v) is used to indicate the number of edges in v’s outgoing edge set where the target vertex and v are not stored on the same server, and poto(v) is only stored on the server that stores v’s neighbor vertices; The counter poti(v) is used to indicate the number of edges in v’s incoming edge set where the source vertices and v are not stored on the same server, (v) is stored only on servers that store v's neighbor vertices; On each server, the sum of the total number of vertices and edges for the partitions stored on the server is represented by the counter size. 3. the method for dividing the incremental graph of distributed graph database based on vertex degree according to claim 2, is characterized in that, the counter step of updating storage among the described S2 is as follows: On the server currently storing vertex v, by calculating the hash value of the target vertex u of the inserted edge e and the location(u) stored in the current server, it can be determined whether the target vertex u and v of the inserted edge e are stored in the same server ; If u and v are on the same server, the value of acto(v) is increased by 1; If u and v are not on the same server, the value of poti(u) is increased by 1; Similarly, on the server storing vertex u, the counter will be updated accordingly. 4. the method for dividing the incremental graph of distributed graph database based on vertex degree according to claim 1, is characterized in that, the specific steps of re-dividing the vertex in the described S3 are as follows: Evaluate the payoff of moving v from the current server S _now to some other server S _i

And move v to the server with the largest profit profit, that is, the target server, denoted as S _target , and the profit evaluation formula is as follows:

in,

is the number of edges where the target vertex and v are not stored on the same server in the outbound edge set of v after the move,

is the number of edges whose source vertices and v are not stored in the same server in v's inbound edge set after moving,

For the current server v, the number of edges in the target vertex and v stored on the same server,

For the current server v, the number of edges in the pool of source vertices and v stored on the same server, />

and

are the sum of the total number of vertices and edges of the partitions stored in the moved server and the current server, respectively. 5. the method for dividing the incremental graph of distributed graph database based on vertex degree according to claim 4, is characterized in that, in the described S3, the counter step stored on the update server is as follows: After completing the re-division of vertex v, it is necessary to update the value of the counter maintained in memory by vertex v and v's neighbor vertices: Move location(v) from the current server S _now to the target server S _target ; The size value of the current server S _now is reduced by 1, and the size value of the target server S _target is increased by 1; In the original server, the value of poto(v) will be updated to the value of acto(v), and the value of poti(v) will be updated to the value of acti(v); in the target server, the value of acto(v) will be updated is the value of poto(v), the value of acti(v) will be updated to the value of poti(v); For the neighbor vertices of v stored in the original server, the acto(v _i ) corresponding to the source vertex v _i of each edge set of v is reduced by 1; the acti corresponding to the target vertex v _j of each edge set of v (v _j ) decreases by 1; For the neighbor vertices of v stored in the target server, the acto(v _k ) corresponding to the source vertex v _k of each edge set of v is increased by 1; the acti corresponding to the target vertex vs _s of each edge set of v (v _s ) is incremented by 1. 6. the incremental graph division method of distributed graph database based on vertex degree according to claim 2, it is characterized in that, update counter operation among the described S4: clear all edge counters of vertex v, update split(v), To ensure that vertex v will not be reallocated again, update location(v). 7. The incremental graph division method of distributed graph database based on vertex degree according to claim 1, characterized in that, said S3, after determining the target server of vertex movement and updating the counter in the memory, in the current OLTP transaction , add the vertex to the pending vertex repartition queue; after the current transaction is completed, immediately stop processing the request related to the vertex, reject the client that initiated the request, and synchronize the state of the vertex with the client; the client After the state is synchronized, make a request to the correct server again. 8. The incremental graph division method of distributed graph database based on vertex degree according to claim 1, characterized in that, in the step S4, after updating the counter in the memory, in the current transaction, the vertex's The connection edge is added to the pending edge repartition queue; immediately after the current transaction is completed, stop processing requests for edges that are not stored locally, reject the client that initiated the request, and synchronize the vertex and its connections with the client Edge state; after the client synchronizes the state, it initiates a request to the correct server again. 9. A system for implementing the method according to any one of claims 1-8, characterized in that the system is a graph database, which is divided into three service modules, namely, a computing service module, a storage service module, and a metadata service module; The calculation service module includes several query engines, which are used to analyze the query requests initiated by the client and execute OLTP transactions; The storage service module includes several storage engines, and each storage engine stores a plurality of graph partitions for storing the outgoing edge set and incoming edge set of each vertex; The metadata service module includes several metadata service engines, and the metadata service engine includes a metadata manager, a partition manager and an operation and maintenance manager; the metadata service engine is used to obtain the changed vertices or edges , performs counter initialization, hash partitioning, vertex repartitioning, and edge repartitioning.

Images