CN101751309B - Optimized transcript distributing method in data grid - Google Patents

Abstract

The invention relates to an optimized transcript distributing method in a data grid, belonging to the field of grid computation, and concretely relates to a grid system, in particular to a transcript distributing method in the data grid system. The invention provides a distributed dynamic self-adaptive transcript distributing method in the data grid, aiming at reducing the access cost of the resource request party, and comprising the following steps of: calculating the transcript amount through the response time of resources; and determining proper transcript place via comprehensive consideration of factors of load factor, node performance, real-time bandwidth, and the like so that the transcript distribution can be dynamically suitable for variation of access request and the network communication state. Compared with the existing method for simply requiring transcript amount to improve the data access performance, the invention evaluates the transcript amount and the optimum transcript place from the overall situation of the system, thereby effectively balancing the relationship between the transcript amount and the transcript maintenance cost. The method is not only suitable for data grid systems of read-only resources and particularly suitable for data grid systems with read-write data resources.

Description

A kind of copy location mode of optimization in the data grids

Technical field

A kind of copy location mode of optimization in the main design data grid of the present invention belongs to grid computing (Grid) field, is specifically related to grid system, especially the distribution problem of copy in the data grids system.

Background technology

As a kind of new network computing platform, the purpose of grid is for the dynamic Virtual Organization of structure on the Internet resources environment of distribution, isomery, autonomy, and portion realizes striding the resource sharing and the resource collaboration in autonomous territory within it.Data grids are gridding technique application and realizations aspect data management, towards the wide area network isomerous environment, by the several data resource that distributes on the integrated network, the isomerism of shielding bottom physical resource, for upper layer application provides general and reliable data, services, realize integrated visit, storage and the service architecture of distribution, isomery, mass data.

The copy technology is to improve the important technology of availability of data, data access performance and the fault-tolerant ability of data grids system.On the one hand, the node in the data grids system has the height dynamic, adds at any time and leaves system, and the copy technology can improve the property obtained and the System Fault Tolerance of data; On the other hand,, can reduce access delay, eliminate the focus bottleneck and realize load balancing, effectively improve grid system performance by to being duplicated, provide a plurality of data trnascriptions by the data resource of frequent access in the data grid.

Copy creating strategy in the data grids can be divided into dynamic copies construction strategy and static copy creating strategy, and static copy creating strategy is not considered practical situations, creates a Copy general less use in advance on a plurality of nodes of appointment.The dynamic copies construction strategy can satisfy data grids system dynamics and large-scale requirement better.

Dynamic copies is created can be divided into two kinds of different strategies of centralized copy creating and distributed copies establishment again.Napster and Gnutella are the canonical systems that adopts centralized copy management method, because single point failure and extendability is bad is difficult to be applied in the large-scale distributed system.The distributed copies construction strategy of comparative maturity is to be six kinds of dynamic replication strategies of basis proposition with the Data Grid by Ranganathan and Foster: no replication policy, best client's replication strategy, waterfall replication strategy, simple cache policy, buffer memory add waterfall strategy, rapid diffusion strategy.These strategies are primarily aimed at the system features of Data Grid, and the reproduction process of utilization stratification is created copy, does not consider the cost that source data distribution, network communications capability, node storage capacity and copy upgrade.Another kind of dynamic copies construction strategy is based on the copy creating strategy of economic model, mainly the problem of Xie Jueing is to utilize the establishment of some economic model judgment data copies whether can bring " profit " to local system, and determines whether create a Copy in this locality with this.

In addition, in the available data grid system, usually the data resource shared of supposition is static with read-only, if the renewal of data resource is arranged, then occur, so the copy technology creates a Copy on each node in the path of query resource mostly, perhaps create a Copy at the two ends in path as new read-only resource, only consider the difference on the copy amount, do not consider the difference of deposit position.

For the read-only data resource, the many more performances that just can obtain more of copy amount.But, but in having the data grids system of write data resource, use the copy consistency maintenance costs that these methods will be brought unnecessary resources duplication and great number.For example for a data grids system of sharing and be made as main application with the multimedia phonotape and videotape, all nodes have formed a jumbo virtual media storage system under the grid system service support, each node both provided stores service for other node, also can download the making of multimedia file, participation multimedia file and upgrade, the people that are in diverse geographic location can cooperate jointly and finish the multimedia making task.In such data grids system, owing to need safeguard the data consistency of copy, pursuing copy amount merely can greatly increase the cost that copy consistency is safeguarded.

Therefore, for the data grids system that has read-write data resource, the position of copy and quantity can directly have influence on the access performance of resource.Need be optimized distribution to the data copy from system's overall situation angle, determine suitable copy amount and distributing position, the relation between the access performance that the expense that the balance copy is safeguarded and many copies bring promotes improves the overall data access performance.

For content of the present invention is described better, below at the network structure of data grids system do following explanation:

(1) connects with full distribution mode between all nodes in the network,, can be divided into super node and ordinary node according to the network bandwidth of node and the otherness of processing power.The super node do as one likes can be born by node good, that bandwidth is high, line duration is long, other resources, also will bear the management function of the normal operation of maintenance system in sharing own resource, access system.Under the management of super node, network structure presents the tree structure of hierarchy type, and the leaf node in the tree construction is an ordinary node, and other nodes in the tree construction are super nodes.Especially, interior all nodes of tree have formed the territory in the tree structure, and the root node of tree is called the territory super node.

Fig. 1 has shown the network structure example of a super node.For the ease of performance, 1 simplification of accompanying drawing has embodied the administrative relationships between super node and the ordinary node, and the full distribution of having ignored between the node connects.Node set shown in dotted lines in Figure 1 is the territory.

(2) shared resource of each super node ordinary node that local shared resources (LSR) and it are managed is born the responsibility of replica management, is responsible to define the copy Distribution Strategy of optimization.All data resource set notes of super node P management are LR, wherein LR={LR ₀, LR ₁..., LR _n, n is the number of the data resource be in charge of of super node P.

(3) each node in the network is all safeguarded a local replica catalogue, preserves the copy information of self shared resource.In the local replica catalogue of super node, except the copy information of local shared resources (LSR), also comprise duplicate directory information by all nodes of its management.The replica management service arrangement provides the replica management service on super node, all information of transcript visit comprise request which node initiates, visited which copy, resource response time, and the information such as real-time network bandwidth of node.These data will distribute for the optimization of copy provides sufficient foundation.

Summary of the invention

The objective of the invention is to be applied in the data grids for solving existing copy technology, when shared resource is read-write resource, the copy consistency maintenance cost is big, the problem of access performance difference, and provide a kind of copy location mode of optimization, the visit situation of data resource is calculated quantity and position, the variation of dynamically adapting for data request of access and the network communication situation of copy according to node.This method can the active balance copy amount and the copy maintenance costs between relation, be not only applicable to the data grids system of read-only resource, be particularly useful for having the data grids system of read-write data resource.

A kind of copy location mode of optimization in the data grids of the present invention, as shown in Figure 2, concrete steps are as follows:

Step 1. in whole grid system scope, determine to need to place all territories of copy

Determine that principle is: if the data resource LR that the node visit super node P in certain territory is managed _j(time of 0≤j＜n) surpasses resource LR in the total system _jAverage response time, then need in this territory, create a Copy.

(1) super node P calculates data resource LR in the total system _jAverage response time.Resource LR _jAverage response time (Average Response Time ART) is defined as in the unit interval access resources LR _jThe ratio of response time sum and access times of all copies.Computing formula is as follows:

${\mathrm{ART}}_j=\frac{\underset{k=0}{\overset{{\mathrm{Time}}_j}{\mathrm{\Σ}}}{\mathrm{RT}}_k}{{\mathrm{Time}}_j}$ (formula 1)

Wherein, Time _jResource LR in the representation unit time interval _jThe number of times that all copies are accessed, RT _kThe k time access resources LR in the representation unit time interval _jThe response time of copy.

(2) super node P is according to the data resource LR that writes down in the local replica catalogue _jThe visit situation of all copies, (note is D to add up not same area _k, k=0,1 ..., m, m are the numbers of system's internal area) interior node visit resource LR _jThe territory average response time.Computing method are as follows:

${\mathrm{ART}}_{j,D_k}=\frac{\underset{P_i\∈D_k}{\mathrm{\Σ}}{\mathrm{RT}}_{j,i}}{{\mathrm{Time}}_{j,D_k}}$ (formula 2)

Wherein, RT _{J, i}Be territory D _kInterior nodes P _iAccess resources LR _jResponse time,

Be unit interval internal area D _kInterior all node visit data resource LR _jNumber of times.

(3) if

Be territory D _kInterior nodes access resources LR _jAveraging time greater than resource LR in the total system _jAverage response time, territory D then is described _kInterior copy amount is very few, need be at territory D _kIn create a Copy.

Step 2. need in need placing the territory of copy, each to determine the copy amount created

According to territory D _kInterior all request resource LR _jActual response time calculate the number create a Copy.

Introduce mark: in the unit interval, territory D _kIn node visit resource LR _jCopy number note be count, need the quantity note of newly-increased copy to be Δ count, T _AvgThe representative domain interior nodes is to resource LR _jMean access time, T _LowThe representative domain interior nodes is to resource LR _jThe minimum access time.

Consider that the purpose that increases copy amount is to reduce territory D _kInterior to resource LR _jMean access time T _Avg, make T _AvgCan be as far as possible near territory D _kInterior to resource LR _jThe minimum access time T _LowIf minimum access time T _LowWith mean access time T _AvgDiffer bigger, then need to create many copy amounts.Therefore, the quantity of newly-increased copy should satisfy following formula:

$\frac{T_{\mathrm{avg}}}{\mathrm{count}}=\frac{T_{\mathrm{avg}}-T_{\mathrm{low}}}{\mathrm{\Δcount}}$ (formula 3)

The computing formula that can derive the copy amount Δ count that needs create according to formula 3 is as follows:

(formula 4)

Step 3. the place of in each need place the territory of copy, determining to be fit to place copy

In the wide area network scope, because network bandwidth characteristics such as dynamic limited, node make Network Transmission postpone to become the most important index that influences data access performance, the processing time of the CPU of node itself and I/O is negligible by contrast.Definition replicator (RF) is used for weighing node and is fit to place resource LR _jThe degree of copy.Node P _iThe computing formula of replicator as follows:

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

Wherein, Memory _iBe node P _iFree memory, filesize is resource LR _jThe size that is taken up space, AvgBW _iBe node P _iAverage available bandwidth.

Because super node P does not have territory D _kSo the information of interior all nodes is territory D _kTerritory D is transferred in definite work of interior copy position _kThe territory super node finish.Node P sends a request message, notice territory D _kThe territory super node place of determine placing copy.

Territory D _kThe territory super node receive request message after, finish following work: territory D _kIn do not have resource LR _jThe node of copy belongs to place to be selected, and the territory super node calculates the replicator of each node to be selected, and the replicator value of node is big more, and suitable more this copy of placement of this node is described.Select Δ count to have the place of the node of maximum replicator as copy creating.According to the definition of replicator, on these nodes, place copy as can be known, can effectively reduce the access time of resource.Territory D _kThe territory super node node address that Δ count is fit to place copy is returned to super node P.

Step 4. the copy placement location in appointment creates a Copy

Be responsible for creating a Copy on the place of Δ count suitable placement copy by super node P, the copy of finishing optimization distributes.

Beneficial effect

The copy location mode of the dynamic self-adapting that the present invention provides, calculate the number of newly-increased copy by the average response time of resource, variation and network communication situation according to request of access are calculated the copy placement location, can and reduce between the copy consistency maintenance costs in the minimizing resource response time to obtain active balance.Its rationality, advantage and good effect are as follows:

(1) the resource access situation in the statistical unit time is visited the average response time of this resource to each territory computational fields interior nodes.In the territory average response time can this territory interior nodes of concentrated expression to the deficiency extent and the visit temperature of data resource.The distribution copy can greatly improve or reduce the cost of data access in the big territory of average response time.

(2) calculate the quantity of newly-built copy according to the average response time of territory interior nodes access resources, can effectively control the quantity of copy, reduce the cost that copy consistency is safeguarded.

(3) notion of proposition replicator is calculated the best place that is fit to place copy according to user capture feature and node real-time bandwidth data etc., realizes the optimization distribution of copy.

(4) be suitable for and any data grids system with super node, not only be suitable for the system that has the read-only data resource, especially be fit to have the system of read-write data resource, application is wide, has solved existing grid copy technology and has not been suitable for the defective that has read-write data resource.

(5) simple to operate, do not rely on center control nodes, only can finish by simple coordination between the super node.

(6) the method run cost is little, and majority operation is finished in super node this locality, seldom takies the wide area network bandwidth.

Description of drawings

Fig. 1 is the schematic network structure with data grids system of super node;

Fig. 2 is the operational flowchart of copy location mode;

Fig. 3 is resource LR _jCopy distribution situation synoptic diagram;

Fig. 4 be in the unit interval node in the grid system to resource LR _jVisit situation example.

Embodiment

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

Each super node is responsible to define the copy Distribution Strategy of optimization to self shared resource and the shared resource of the self-administered ordinary node responsibility of bearing replica management.When the visit situation of all copies under the self-administered data resource of the periodic record of super node comprises, which node in which territory sent request, visited which copy, the response time of resource etc.These copy visit informations are recorded in the local replica catalogue of super node.

For example, resource LR _jThe copy distribution situation as shown in Figure 3, shown two territories among the figure, the territory super node is respectively node A and Node B.Resource LR _jHave 4 copies, be placed on respectively on node A1, node A12, node A2 and the Node B 11.Resource LR _jBe the shared resource of node A12, because node A12 is an ordinary node, so the father node P of node A12 is responsible for resource LR _jReplica management, record resource LR in the local replica catalogue of node P _jAll copy informations, shown in dotted line in the accompanying drawing 3.

Fig. 4 has shown that the node in the grid system is to resource LR in the unit interval _jThe visit situation, among Fig. 4 with the band arrow line segment represent that all are to resource LR _jRequest of access, the line segment initiating terminal represents that resource initiates a some territory, place, the key head indication is represented the concrete copy of visiting.The response time of the numeral resource on line segment next door.

Suppose the data resource LR that super node P is in charge of _jNeed create a Copy, then super node P carries out following operation:

1. in whole grid system scope, determine to need to place all territories of copy

Node P is according to resource LR in the unit interval _jResponse time, according to formula 1 computational resource LR _jAverage response time be 118, promptly

${\mathrm{ART}}_j=\frac{60*4+200*3+120*3+200+20}{12}\≈118$

According to formula 2 computational fields A interior nodes access resources LR _jAverage response time be 60, promptly

${\mathrm{ART}}_{j,A}=\frac{60+60+60+60}{4}=60$

Territory B interior nodes access resources LR _jThe average access cost be 140, promptly

${\mathrm{ART}}_{j,B}=\frac{200+200+200+120+120+120}{6}=160$

Territory C interior nodes access resources LR _jThe average access cost be 200, promptly

${\mathrm{ART}}_{j,C}=\frac{200+200}{2}=200$

Because ART _{J, A}＜ART _j, ART _{J, B}＞ART _j, ART _{J, C}＞ART _jSo, need be in territory C and territory B establishing resource LR _jCopy.

2. in need placing the territory of copy, each determines the quantity that creates a Copy

According to the copy amount that needs in formula 4 calculating accompanying drawings 4 examples to create.The copy number of visiting in the B of territory is 2, and then the copy number that need create in the B of territory is:

The copy number of visiting in the C of territory is 1, and the copy number that need create at territory C is:

3. the place of in each need place the territory of copy, determining to be fit to place copy

Node P sends a request message, the place that the territory super node B of notice territory B and the territory super node C of territory C determine to place copy.Because Node B and node C have the information of all nodes in the territory, computational resource LRj is placed on the replicator (RF) on each node to be selected respectively.2 nodes with maximum replicator are as the copy creating place in the Node B selection territory; 1 node with maximum replicator is as the copy creating place in the node C selection territory.At last, Node B and the node C node address that will be fit to place copy returns to super node P.

4. the nodal information that returns according to territory super node B and territory super node C of node P is created two latest copys respectively respectively on the node of territory B appointment, creates a latest copy on the C specified node of territory.

Claims (1)

1. copy location mode in the data grids of an optimization is characterized in that: at the data grids system with super node, at first by super node P self-administered all resources are monitored in real time, when needs are resource LR _jWhen creating a Copy, resource LR in the super node P statistical unit time interval _jThe visit situation, calculate resource LR in the total system _jAverage response time and each territory in all node visit resource LR _jAverage response time, specifically adopt computing formula

Calculate resource LR in the total system _jAverage response time ART _j, Time wherein _jResource LR in the representation unit time interval _jThe number of times that all copies are accessed, RT _kThe k time access resources LR in the representation unit time interval _jThe response time of copy; Adopt computing formula

Computational fields D _kInterior nodes access resources LR _jAverage response time

RT wherein _{J, i}Be territory D _kInterior nodes P _iAccess resources LR _jResponse time, Be unit interval internal area D _kInterior all node visit data resource LR _jNumber of times; If certain territory D _kInterior nodes access resources LR _jAverage response time

Greater than resource LR in the total system _jAverage response time ART _j, resource LR then is described _jAt territory D _kInterior copy amount is very few, need be at territory D _kIn create a Copy, wherein, 0≤j＜n, n are the numbers of resource in the whole data grids system; K=0,1 ..., m, m are the numbers of data grids system internal area, i=0, and 1 ..., t, t are territory D _kThe number of interior nodes;

Secondly, at the territory D that needs create a Copy _kIn, if territory D in the unit interval _kIn node visit resource LR _jCopy number note be count, then territory D _kThe quantity that needs newly-increased copy

Wherein, T _AvgRepresentative domain D _kInterior nodes access resources LR _jMean access time, T _LowRepresentative domain D _kInterior nodes access resources LR _jThe minimum access time;

Then, the D that creates a Copy by needs _kThe copy placement location that be responsible for to determine is fit to of territory super node; Territory D _kIn do not have resource LR _jThe node of copy belongs to node to be selected, and the territory super node calculates each node P to be selected _iReplicator

Memory wherein _iBe node P _iFree memory, filesize is resource LR _jThe size that is taken up space, AvgBW _iBe node P _iAverage available bandwidth, the replicator value of node is big more, and suitable more this copy of placement of this node is described, selects Δ count the node with maximum replicator as the optimal node that is fit to place copy;

At last, the optimal node at determined suitable placement copy creates a Copy.

Images