CN101751309B - An Optimized Replica Distribution Method in Data Grid - Google Patents

Abstract

The present invention mainly designs an optimized copy distribution method in a data grid, belongs to the grid computing (Grid) field, and specifically relates to a grid system, especially the distribution of copies in a data grid system. The invention provides a distributed dynamic self-adaptive copy distribution method in the data network, with the main purpose of reducing the access cost of the resource requester, calculating the number of copies through the response time of the resource; comprehensively considering the load rate of the node and the performance of the node , and factors such as real-time bandwidth to determine the appropriate place to place the replica, so that the replica distribution can dynamically adapt to changes in access requests and network communication conditions. Compared with the existing method of simply pursuing the number of copies to improve data access performance, the present invention evaluates the number of copies and the best place to place copies from the perspective of the overall system, and can effectively balance the relationship between the number of copies and the cost of copy maintenance. This method is not only suitable for data grid systems with read-only resources, but especially suitable for data grid systems with readable and writable data resources.

Description

An Optimized Replica Distribution Method in Data Grid

technical field

The present invention mainly designs an optimized copy distribution method in a data grid, belongs to the grid computing (Grid) field, and specifically relates to a grid system, especially the distribution of copies in a data grid system.

Background technique

As a new type of network computing platform, the purpose of the grid is to construct a dynamic virtual organization on a distributed, heterogeneous, and autonomous network resource environment, and to realize resource sharing and resource collaboration across autonomous domains within it. Data grid is the application and realization of grid technology in data management. Facing the heterogeneous environment of wide area network, it integrates various data resources distributed on the network, shields the heterogeneity of underlying physical resources, and provides general and reliable data for upper-layer applications. Data service, realizing the integrated access, storage and service architecture of distributed, heterogeneous and massive data.

Replica technology is an important technology to improve data availability, data access performance and fault tolerance of data grid system. On the one hand, the nodes in the data grid system are highly dynamic and can join and leave the system at any time. The replica technology can improve the availability of data and the fault tolerance of the system; Resources are replicated and multiple copies of data are provided, which can reduce access delays, eliminate hotspot bottlenecks and achieve load balancing, effectively improving grid system performance.

The replica creation strategy in the data grid can be divided into dynamic replica creation strategy and static replica creation strategy. The static replica creation strategy does not consider the actual application situation, and creates replicas on multiple specified nodes in advance, which is generally seldom used. The dynamic replica creation strategy can better meet the dynamic and large-scale requirements of the data grid system.

Dynamic replica creation can be divided into two different strategies: centralized replica creation and distributed replica creation. Napster and Gnutella are typical systems that adopt centralized copy management methods, but it is difficult to apply them to large-scale distributed systems due to single point of failure and poor scalability. The more mature distributed replica creation strategy is six dynamic replication strategies proposed by Ranganathan and Foster based on the European data grid: no replica strategy, optimal customer replication strategy, waterfall replication strategy, simple caching strategy, caching plus waterfall Strategies, Rapid Diffusion Strategies. These strategies are mainly aimed at the system characteristics of the European data grid, using a hierarchical replication process to create replicas, without considering the distribution of source data, network communication capabilities, node storage capabilities, and the cost of replica updates. Another dynamic replica creation strategy is the replica creation strategy based on economic models. The main problem is to use some economic models to judge whether the creation of data replicas can bring "profit" to the local system, and to decide whether to create replicas locally. .

In addition, in the existing data grid system, it is usually assumed that shared data resources are static and read-only. If there is an update of the data resource, it will appear as a new read-only resource, so the copy technology is mostly in the path of querying resources Create copies on each node of the path, or create copies at both ends of the path, only considering the difference in the number of copies, not the difference in storage location.

For read-only data resources, the greater the number of replicas, the better the performance. However, applying these methods in a data grid system with writable data resources will bring unnecessary resource duplication and high cost of replica consistency maintenance. For example, for a data grid system whose main application is multimedia audio-visual sharing and production, all nodes form a large-capacity virtual media storage system with the support of grid system services. Each node not only provides storage services for other nodes, but also It can download multimedia files, participate in the production update of multimedia files, and people in different geographic locations can work together to complete multimedia production tasks. In such a data grid system, due to the need to maintain the data consistency of the replicas, simply pursuing the number of replicas will greatly increase the cost of replica consistency maintenance.

Therefore, for a data grid system with readable and writable data resources, the location and number of replicas will directly affect the resource access performance. It is necessary to optimize the distribution of data copies from the perspective of the overall system, determine the appropriate number of copies and distribution locations, balance the relationship between the cost of copy maintenance and the access performance improvement brought by multiple copies, and improve the overall data access performance.

In order to better illustrate the content of the present invention, the network structure of the targeted data grid system is described as follows:

(1) All nodes in the network are connected in a fully distributed manner. According to the differences in network bandwidth and processing capabilities of nodes, they can be divided into super nodes and ordinary nodes. Super nodes are undertaken by nodes with good performance, high bandwidth, and long online time. In addition to sharing their own resources and accessing other resources in the system, they also undertake the management function of maintaining the normal operation of the system. Under the management of super nodes, the network structure presents a hierarchical tree structure. The leaf nodes in the tree structure are ordinary nodes, and other nodes in the tree structure are super nodes. In particular, all nodes in the tree form a domain in the tree structure, and the root node of the tree is called a domain super node.

Figure 1 shows an example of the network structure of a super node. For ease of presentation, Figure 1 only simplifies the management relationship between super nodes and ordinary nodes, while ignoring the fully distributed connections between nodes. The set of nodes shown by the dotted line in Figure 1 is the domain.

(2) Each super node undertakes the copy management responsibility for the local shared resources and the shared resources of the ordinary nodes it manages, and is responsible for formulating an optimized copy distribution strategy. The set of all data resources managed by supernode P is recorded as LR, where LR={LR ₀ , LR ₁ , ..., LR _n }, n is the number of data resources managed by supernode P.

(3) Each node in the network maintains a local replica directory to save the replica information of its own shared resources. In addition to the copy information of the local shared resource, the local copy directory of the super node also contains the copy directory information of all nodes managed by it. The copy management service is deployed on the supernode, provides copy management service, and records all information about copy access, including which node initiates the request, which copy is accessed, resource response time, and real-time network bandwidth of the node. These data will provide sufficient basis for the optimal distribution of replicas.

Contents of the invention

The purpose of the present invention is to provide an optimized replica distribution method to solve the problems of high cost of replica consistency maintenance and poor access performance when the shared resources are read-write resources when the existing replica technology is applied in the data grid , calculate the number and location of replicas according to the node's access to data resources, and dynamically adapt to changes in data access requests and network communication conditions. This method can effectively balance the relationship between the number of replicas and the cost of replica maintenance. It is not only suitable for data grid systems with read-only resources, but especially suitable for data grid systems with readable and writable data resources.

An optimized copy distribution method in the data grid of the present invention, as shown in Figure 2, the specific steps are as follows:

Step 1. Identify all domains in the entire grid system where replicas need to be placed

The determination principle is: if the time for a node in a certain domain to access the data resource LR _j (0≤j<n) managed by the supernode P exceeds the average response time of the resource LR _j in the entire system, a copy needs to be created in the domain.

(1) The super node P calculates the average response time of the data resource LR _j in the whole system. The average response time (Average Response Time, ART) of the resource LR _j is defined as the ratio of the sum of the response times of all copies of the access resource LR _j to the number of visits within a unit time interval. Calculated as follows:

${\mathrm{ART}}_j=\frac{\underset{k=0}{\overset{{\mathrm{Time}}_j}{\mathrm{\&Sigma;}}}{\mathrm{RT}}_k}{{\mathrm{Time}}_j}$ (Formula 1)

Among them, Time _j represents the number of times all copies of resource LR _j are accessed within a unit time interval, and RT _k represents the response time of the kth access to a copy of resource LR _j within a unit time interval.

(2) According to the access situation of all copies of the data resource LR _j recorded in the local copy directory, the super node P counts different domains (denoted as D _k , k=0, 1, ..., m, m is the domain in the system The domain average response time of nodes accessing resources LR _j in the number of ). The calculation method is as follows:

${\mathrm{ART}}_{j,{\mathrm{D.}}_k}=\frac{\underset{P_i\&Element;{\mathrm{D.}}_k}{\mathrm{\&Sigma;}}{\mathrm{RT}}_{j,i}}{{\mathrm{Time}}_{j,{\mathrm{D.}}_k}}$ (Formula 2)

是单位时间内域D_k内所有节点访问数据资源LR_j的次数。Among them, RT _j,i is the response time of node P _i accessing resource LR _j in domain D _k ,

is the number of times all nodes in the domain D _k access the data resource LR _j per unit time.

即域D_k内节点访问资源LR_j的平均时间大于整个系统内资源LR_j的平均响应时间，则说明域D_k内的副本数量过少，需要在域D_k内创建副本。(3) if

That is, the average time for nodes in domain D _k to access resource LR _j is greater than the average response time of resources LR _j in the entire system, indicating that the number of replicas in domain D _k is too small, and replicas need to be created in domain D _k .

Step 2. Determine the number of replicas to be created in each domain where replicas need to be placed

Calculate the number of created replicas according to the actual response time of all request resources LR _j in the domain D _k .

Introduce notation: within a unit time interval, the number of copies of resources LR _j accessed by nodes in domain D _k is recorded as count, the number of new copies that need to be added is recorded as Δcount, T _avg represents the average access time of nodes in the domain to resource LR _j , T _low indicates the minimum access time of nodes in the domain to resource LR _j .

Considering that the purpose of increasing the number of replicas is to reduce the average access time T _avg to resource LR _j in domain D _k , so that T _avg can be as close as possible to the minimum access time T _low to resource LR _j in domain D _k . If the difference between the minimum access time T _low and the average access time T _avg is relatively large, it is necessary to create a large number of copies. Therefore, the number of new replicas should satisfy the following formula:

$\frac{T_{\mathrm{avg}}}{\mathrm{count}}=\frac{T_{\mathrm{avg}}-T_{\mathrm{low}}}{\mathrm{\&Delta;count}}$ (Formula 3)

According to Formula 3, the calculation formula for the number of replicas Δcount that needs to be created can be deduced as follows:

(公式4)

(Formula 4)

Step 3. Determine a suitable place to place a replica in each domain that needs to place a replica

In the wide area network, due to the characteristics of limited network bandwidth and node dynamics, network transmission delay becomes the most important indicator affecting data access performance. Compared with the CPU and I/O processing time of the node itself, it is negligible of. Define the replication factor (RF), which is used to measure the degree to which a node is suitable for placing a replica of resource LR _j . The calculation formula of the replication factor of node P _i is as follows:

${\mathrm{RF}}_i=\frac{{\mathrm{Memery}}_i}{\mathrm{filesize}}*\mathrm{Avg}{\mathrm{BW}}_i$ (Formula 5)

Among them, Memory _i is the available memory of node P _i , filesize is the space occupied by resource LR _j , and AvgBW _i is the average available bandwidth of node P _i .

Because the super node P does not possess the information of all the nodes in the domain D _k , the determination of the location of the replica in the domain D _k is done by the domain super node of the domain D _k . Node P sends a request message to notify the domain super node of domain D _k to determine the place to place the copy.

After the domain super node of domain D _k receives the request message, it completes the following work: the nodes in domain D _k that do not have a copy of resource LR _j belong to the candidate site, the domain super node calculates the replication factor of each candidate node, and the replication of the node The larger the factor value, the more suitable the node is to place the copy. Select Δcount nodes with the largest replication factor as the locations for replica creation. According to the definition of replication factor, it can be seen that placing replicas on these nodes can effectively reduce the access time of resources. The domain supernode of domain D _k returns Δcount node addresses suitable for placing replicas to supernode P.

Step 4. Create a copy at the specified copy placement location

The super node P is responsible for creating replicas on Δcount locations suitable for placing replicas, and completes the optimized replica distribution.

Beneficial effect

The dynamic self-adaptive replica distribution method provided by the present invention calculates the number of newly added replicas through the average response time of resources, and calculates the location of replicas according to changes in access requests and network communication conditions, which can reduce resource response time and reduce replica consistency. Effective balance between maintenance costs. Its rationality, advantages and positive effects are as follows:

(1) Statistics resource access situation per unit time, and calculate the average response time of nodes in the domain to access the resource for each domain. The average response time in the domain can comprehensively reflect the lack of data resources and access popularity of nodes in the domain. Distributing replicas in a domain with a large average response time can greatly improve or reduce the cost of data access.

(2) Calculate the number of new replicas based on the average response time of nodes in the domain to access resources, which can effectively control the number of replicas and reduce the cost of replica consistency maintenance.

(3) The concept of replication factor is proposed, and the optimal location for placing replicas is calculated according to user access characteristics and real-time bandwidth data of nodes, so as to realize the optimal distribution of replicas.

(4) It is suitable for any data grid system with super nodes, not only for systems with read-only data resources, but especially for systems with readable and writable data resources. It has a wide range of applications and solves the problem that the existing grid copy technology is not applicable Deficiencies in owning readable and writable data resources.

(5) The operation is simple, does not rely on the central control node, and can be completed only through simple cooperation between super nodes.

(6) The operation cost of the method is low, and most operations are completed locally on the super node, which rarely occupies the bandwidth of the wide area network.

Description of drawings

Fig. 1 is a schematic diagram of the network structure of a data grid system with super nodes;

Fig. 2 is the operation flowchart of replica distribution method;

Fig. 3 is a schematic diagram of the replica distribution of resource LR _j ;

Fig. 4 is an example of access to resource LR _j by nodes in the grid system per unit time.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and specific embodiments.

Each super node undertakes the responsibility of copy management for its own shared resources and the shared resources of ordinary nodes it manages, and is responsible for formulating an optimized copy distribution strategy. The super node periodically records the access status of all copies under the data resources it manages, including when and from which node in which domain the request was sent, which copy was accessed, the response time of the resource, etc. These replica access information are recorded in the super node's local replica directory.

For example, the replica distribution of resource LR _j is shown in Figure 3, which shows two domains, and the domain super nodes are node A and node B respectively. Resource LR _j has 4 copies, which are respectively placed on node A1, node A12, node A2 and node B11. Resource LR _j is a shared resource of node A12, because node A12 is a common node, so node A12's parent node P is responsible for the copy management of resource LR _j , and all copy information of resource LR _j is recorded in the local copy directory of node P, as shown in the attached Shown in dotted line in Figure 3.

Figure 4 shows the access situation of the nodes in the grid system to resource LR _j in unit time. In Figure 4, the lines with arrows represent all the access requests to resource LR _j . The specific copy that the header points to indicates the access. The numbers next to the lines indicate the resource's response time.

Assuming that the data resource LR _j managed by the super node P needs to create a copy, the super node P performs the following operations:

1. Determine all domains that need to place replicas within the entire grid system

According to the response time of resource LR _j in unit time, node P calculates the average response time of resource LR _j according to formula 1 to be 118, namely

${\mathrm{<span\; class="notranslate">\; ART</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 60</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 120</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 20</span>}}{\mathrm{<span\; class="notranslate">\; 12</span>}}<span\; class="notranslate">\; \&ap;</span>\mathrm{<span\; class="notranslate">\; 118</span>}$

According to formula 2, the average response time of nodes accessing resource LR _j in domain A is calculated as 60, namely

${\mathrm{<span\; class="notranslate">\; ART</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; A</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 60</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 60</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 60</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 60</span>}}{\mathrm{<span\; class="notranslate">\; 4</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 60</span>}$

The average access cost for nodes in domain B to access resource LR _j is 140, namely

${\mathrm{<span\; class="notranslate">\; ART</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; B</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 120</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 120</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 120</span>}}{\mathrm{<span\; class="notranslate">\; 6</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 160</span>}$

The average access cost for nodes in domain C to access resource LR _j is 200, namely

${\mathrm{<span\; class="notranslate">\; ART</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; C</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 200</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 200</span>}$

Since ART _{j, A} < ART _j , ART _{j, B} > ART _j , ART _{j, C} > ART _j , a copy of resource LR _j needs to be created in domain C and domain B.

2. Determine the number of replicas to be created in each domain where replicas need to be placed

Calculate the number of replicas that need to be created in the example shown in Figure 4 according to Formula 4. If the number of replicas visited in domain B is 2, the number of replicas to be created in domain B is:

The number of replicas visited in domain C is 1, and the number of replicas to be created in domain C is:

3. Determine a suitable place to place a copy in each domain where a copy needs to be placed

Node P sends a request message to notify domain super node B of domain B and domain super node C of domain C to determine the place to place the replica. Because node B and node C have the information of all nodes in the domain, the replication factor (RF) of resource LRj placed on each candidate node can be calculated respectively. Node B selects two nodes with the largest replication factor in the domain as the replica creation location; node C selects a node with the largest replication factor in the domain as the replica creation location. Finally, node B and node C return the address of the node suitable for placing the replica to super node P.

4. According to the node information returned by domain super node B and domain super node C, node P creates two new replicas on the node specified by domain B and creates a new replica on the node specified by domain C respectively.

Claims (1)

1. An optimized copy distribution method in a data grid, characterized in that: for a data grid system with a super node, first the super node P monitors all the resources managed by itself in real time, and when it is necessary to create a resource LR _j When copying, the super node P counts the access situation of resource LR _j within a unit time interval, calculates the average response time of resource LR _j in the entire system and the average response time of all nodes in each domain accessing resource LR _j , specifically using the calculation formula

Calculate the average response time ART _j of resource LR _j in the entire system, where Time _j represents the number of times all copies of resource LR _j are accessed within a unit time interval, and RT _k represents the response time of the kth access to a copy of resource LR _j within a unit time interval ; using the calculation formula

Calculate the average response time of nodes accessing resource LR _j in domain D _k

where RT _j,i is the response time for node P _i to access resource LR _j in domain D _k , is the number of times all nodes in the domain D _k access the data resource LR _j per unit time; if a node in a certain domain D _k accesses the resource LR _j , the average response time

is greater than the average response time ART _j of resource LR _j in the entire system, it means that the number of replicas of resource LR _j in domain D _k is too small, and replicas need to be created in domain D _k , where 0≤j<n, n is the entire The number of resources in the data grid system; k=0, 1,..., m, m is the number of domains in the data grid system, i=0, 1,..., t, t is the domain D The number of nodes in _k ; Secondly, in the domain D _k that needs to create replicas, if the number of replicas of the resource LR _j accessed by nodes in the domain D _k per unit time is recorded as count, then the number of replicas that need to be added in the domain D _k

Among them, T _avg represents the average access time of nodes in domain D _k to access resource LR _j , and T _low represents the minimum access time of nodes in domain D _k to access resource LR _j ; Then, the domain supernode of D _k that needs to create a replica is responsible for determining the appropriate replica placement location; the nodes in the domain D _k that do not have a copy of resource LR _j belong to the candidate nodes, and the domain supernode calculates the replication of each candidate node P _i factor

Among them, Memory _i is the available memory of node P _i , filesize is the space occupied by resource LR _j , AvgBW _i is the average available bandwidth of node P _i , the larger the replication factor value of the node, the more suitable the node is to place the copy, Select Δcount nodes with the largest replication factor as the best nodes suitable for placing replicas; Finally, a replica is created on the determined optimal node for placing the replica.

Images