CN101175011A - A Method of Obtaining Highly Available Data Redundancy in DHT-Based P2P System - Google Patents

Abstract

The invention discloses a redundant mechanism method in a P2P system, which bases on DHT and obtains highly available data. The method includes steps mentioned below. Firstly, Erasure Coding is implemented on the original documents. Secondly, the slices obtained in the coding are distributed to the relative nodes for storing. Thirdly, a user puts forward a download requirement and the query is implemented. Fourthly, the user downloads the documents and reserves a part of the documents as copies. Fifthly, the third step is repeated until services are stopped. Sixthly, the method is over. Compared with the prior art, the invention has the obvious advantages of the traditional replication strategies and the slices redundant strategies. The invention can be easily realized. Compared with the traditional redundant strategies, the invention can save more network bandwidths under various network environments. The redundancy is moderate.

Description

A Method of Obtaining Highly Available Data Redundancy in DHT-Based P2P System

1. Technical field

The invention relates to a highly available data redundancy mechanism in a DHT-based P2P system. This data redundancy strategy saves more network bandwidth than the traditional redundancy strategy in various network environments, and the redundancy is moderate (not higher than 9.4 ). The superiority of this strategy is particularly prominent when the average node availability is lower than 0.7 and the file request rate is low relative to the node perturbation frequency. Hybrid strategies not only perform well in low dynamic network environments, but also perform well in highly dynamic networks.

2. Background technology

With the rapid development of Internet and network computing technology, a peer-to-peer computing system based on Distributed Hash Table (DHT) emerges as the times require. DHT is a distributed storage method. In the absence of a server, each client is responsible for a small range of routing and is responsible for storing a small part of data, thereby realizing the addressing and storage of the entire DHT network. DHT provides a deterministic object location service and has been used in many applications. To achieve high availability of data files without guaranteeing 100% availability of nodes requires some kind of data redundancy strategy. Currently, there are two main data redundancy strategies applied to DHT-based P2P systems: replication and erasure coding.

In previous applications, replication and parity schemes (such as RAID) are two commonly used redundancy mechanisms to achieve high data availability. The former will introduce extremely high redundancy; the latter has poor ability to adapt to the dynamics of the environment, and it is difficult to guarantee the availability of data in a highly dynamic network environment.

Shard redundancy overcomes the disadvantage of high replication redundancy. It divides the data object into m slices, and then encodes into n slices (n>m). We define r=n/m as coding redundancy. Encoding with redundancy r means that the storage space occupied by encoding is r times that of the original data. The most important feature of fragment redundancy is that the original file can be reconstructed as long as any m different fragments are obtained, and the sum of the volumes of the m fragments is roughly equal to the original file. For example, when the coding redundancy is r=4, the original data is divided into m=16 pieces, then after encoding, n=64 pieces, and the required storage space is increased by 4 times. Replication and RAID can be seen as special cases of shard redundancy. A replication system with a redundancy of 4 is equivalent to (m=1, n=4) fragment redundancy; RAID levels 1, 4 and 5 are represented by fragment redundancy as) (m=1, n=2 ), (m=4, n=5), (m=4, n=5).

3. Contents of the invention

The purpose of the present invention is to: propose a hybrid data redundancy strategy, a method for obtaining highly available data redundancy in a DHT-based P2P system, which shares files downloaded by users for subsequent downloads like a copy strategy , and use fragmentation redundancy to maintain the availability of files. This hybrid data redundancy strategy can save network bandwidth more than traditional redundancy strategies in various network environments, and the redundancy is moderate.

In order to achieve the above object, the technical solution of the present invention is: the method for obtaining highly available data redundancy in the DHT-based P2P system is characterized in that a hybrid method for obtaining data redundancy is adopted, and the method comprises the following steps: 1. In the P2P system, the original files are coded with fragmentation redundancy Erasure Coding; 2. The coded fragments are allocated to the corresponding nodes of the P2P system for storage; 3. The user makes a download request and performs all node queries; 4. The user starts from the node of the useful file Download the file and save part of the file as a copy; 5. Repeat step 3 until the service stops; 6. End.

Observing the current P2P file sharing system, on the one hand, it is found that hot files are downloaded quite a lot without maintenance, and their availability is automatically maintained at a high level, which shows the feasibility of a hybrid data redundancy strategy. On the other hand, from the perspective of the development trend of computer hardware, the development speed of memory is much higher than the development speed of bandwidth. Compared with storage resources, bandwidth resources are becoming more and more poor, which shows that the research of more effective bandwidth-saving data The need for redundancy strategies.

Beneficial effects of the present invention: Compared with the prior art, the present invention has the remarkable advantages of saving network bandwidth compared with traditional redundancy strategies in various network environments, and the redundancy is moderate (not higher than 9.4). The superiority of this strategy is particularly prominent when the average node availability is lower than 0.7 and the file request rate is low relative to the node perturbation frequency. A hybrid approach or strategy not only works well in low dynamic network environments, but also works well in highly dynamic networks. It not only shares the files downloaded by users for subsequent downloads like a replication strategy, but also maintains the availability of files by using shard redundancy. This hybrid data redundancy strategy can save network bandwidth more than traditional redundancy strategies in various network environments, and the redundancy is moderate.

4. Description of drawings

Figure 1 is the execution flow of the hybrid data redundancy strategy;

Figure 2 shows the change of the theoretical value of redundancy required by the three strategies of replication strategy, fragmentation redundancy strategy and hybrid strategy with the average availability of nodes when the file availability is 0.999.

Figure 3 shows how the redundancy of replication strategy, shard redundancy strategy and hybrid strategy varies with the average availability of nodes when the file availability is 0.999.

Figure 4 shows how the maintenance bandwidth occupancy rate of replication strategy, fragmentation redundancy strategy and hybrid strategy varies with the average availability of nodes when the file availability is 0.999.

Figure 5 shows that when the file availability is 0.999 (Figure 5a) and the average node availability is 0.807 (Figure 5b), the maintenance bandwidth occupancy rate and the number of file transfers during maintenance of the replication strategy, fragmentation redundancy strategy and hybrid strategy vary with the node lifetime. Changes in the average file request rate within a given period.

5. Specific implementation

The hybrid strategy not only shares the files downloaded by users for subsequent downloads like a replication strategy, but also uses fragmentation redundancy to maintain the availability of files. The hybrid strategy automatically treats downloaded files as shared files for subsequent downloads; when repairing a certain file availability level, designate any node that stores a complete copy of the file to generate and distribute new shards. On the one hand, the hybrid strategy shares the files downloaded by users for subsequent downloads like the replication strategy, saving network bandwidth; on the other hand, increasing the same availability, the volume of new data generated by the shard redundancy strategy is smaller than that of the replication strategy , that is, the fragmentation redundancy strategy needs to transmit less data, and the hybrid strategy uses this feature to further save network bandwidth.

File availability and redundancy when using a hybrid strategy can be deduced as follows. First, we assume that the same node does not store copies and shards of the same file, but multiple copies and shards of different files can be stored, and there are no duplicate shards in the system. The availability a of a file can be calculated according to the probability, that is, the probability of obtaining at least one complete copy or any m of n shards. Or subtract the probability from 1 that all copies cannot be obtained and there are not enough fragments to reconstruct the original file (the number of available fragments is less than m):

$\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; m</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\left(\begin{array}{c}\mathrm{<span\; class="notranslate">\; no</span>}\\ \mathrm{<span\; class="notranslate">\; i</span>}\end{array}\right){\mathrm{<span\; class="notranslate">\; p</span>}}^{\mathrm{<span\; class="notranslate">\; i</span>}}{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Here, h is the number of complete copies.

The redundancy of the hybrid strategy can be obtained from the redundancy of superimposed replication and shard redundancy:

$\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; )</span>\sqrt{\frac{\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; m</span>}}}<span\; class="notranslate">\; +</span>\sqrt{\frac{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; a</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; p</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

Here, σ _a (h) is a function of h, and its value corresponds to the availability level a' that shard redundancy needs to achieve

As shown in Table 1.

a σ _a

0.8000.9000.9900.9950.9980.999 0.841.282.482.812.883.10

Table 1. Comparison table of file availability and normal distribution standard deviation

a' can be deduced from formula (1):

${\mathrm{<span\; class="notranslate">\; a</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; m</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\left(\begin{array}{c}\mathrm{<span\; class="notranslate">\; no</span>}\\ \mathrm{<span\; class="notranslate">\; i</span>}\end{array}\right){\mathrm{<span\; class="notranslate">\; p</span>}}^{<span\; class="notranslate">\; \&prime;</span>}{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; a</span>}}{{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; h</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

It can be seen from formula (2) that redundancy is related to m and the number h of complete copies, but has nothing to do with n. Given h, when m increases, the redundancy decreases, but the complexity of the system increases and the download delay increases. The two new shard regeneration strategies of the shard redundancy strategy are still applicable to the hybrid strategy, and the second strategy has more significant advantages in the hybrid strategy.

Figure 2 shows the change of the theoretical value of the redundancy required by the replication strategy, the fragmentation redundancy strategy and the hybrid strategy to achieve a file availability of 0.999 with the average availability of nodes. The redundancy curve of the hybrid strategy is determined by two factors: the average node availability p and the number of complete copies h. For any given value of h, there is a corresponding curve. It can be seen from the figure that when the average availability of nodes is constant, the redundancy of the shard redundancy strategy is the smallest; except when the average availability of nodes is extremely high, the redundancy of the hybrid strategy is slightly higher than that of the shard redundancy strategy, but much lower. in the replication strategy.

The specific steps of steps 2 to 4 are: (2. assign the coded slices to the corresponding nodes of the P2P system for storage; 3. the user makes a download request and queries all nodes; 4. the user downloads the file from the node of the useful file and Save some files as copies;) Each node periodically registers the identifiers of its stored files and fragments to M distributed and independent index nodes. Nodes look up files through two types of indexes: file replica indexes and file shard indexes. When a node requests a file d, it first randomly queries one or more index nodes of d. If the queried inode fails to provide sufficient file copy and shard location information, continue to randomly query other inodes. If all index nodes cannot provide enough file copies and fragment location information, the node will wait for a period of time (for example, 10ms), and then redo the query operation until the query times out. If a complete copy of the file is found, it is downloaded; otherwise, the node moves on to download enough shards and reconstruct the original file. Files downloaded by users are automatically shared as files for subsequent downloads.

Each inode periodically maintains the availability of files and shards registered on it. If the availability of file d is lower than the required level, a node that stores a complete copy of the file is designated to generate and distribute new shards to randomly selected nodes. If there is no complete copy in the current system, first wait for a period of time (for example, 10ms), if a node downloads the fragment and reconstructs the original file, then designate the node to repair the lost redundancy; otherwise, the index node needs to download the fragment by itself , reconstruct the original file, and generate enough new fragments. Experiments show that almost all files have at least one copy in the system, so the hybrid strategy does not need to designate the primary node to keep a permanent copy of the file like the fragmentation redundancy strategy. In this way, the hybrid strategy saves the network bandwidth required to maintain masternodes.

We implement the above three data redundancy strategies on p2psim. The simulated network environment contains 1024 nodes. Each node leaves and rejoins the network alternately, and the time interval between adjacent events is exponentially distributed. When a node fails or leaves, all files, shards and indexes on it are discarded. Each time a node joins the network, it uses a different IP and DHT identifier. The access requests to files are distributed according to Zipf-like, and the files are arranged according to the access frequency from high to low. The access frequency of the i-th file is proportional to 1/i ^α , where α is set to 0.74. We designed two sets of experiments: varying node average availability and varying user request frequency. In the experiment of changing the average availability of nodes, the average availability of nodes varies from 30% to 90%, and other conditions remain unchanged. In the experiment of changing the frequency of user requests, the average number of file requests during the node life span ranges from 2 to 20, and other conditions remain unchanged. Each set of experiments runs the simulator for 6 hours, and only collects data for the second half of the simulation time. Each experiment was repeated 5 times, and the results were averaged. Set m=7, which is the number of fragments required to reconstruct the original file used in CFS. Set the file availability to 0.999, which is the availability that most web services can achieve at present.

Figure 3 shows the curves of redundancy changing with the average availability of nodes for the three redundancy strategies of replication strategy, shard redundancy strategy and hybrid strategy when the file availability is 0.999. The redundancy curve of the shard redundancy strategy in Figure 3 is roughly consistent with that in Figure 2. But the redundancy curve of the replication strategy in Figure 3 is far from that in Figure 2, especially when the average availability of nodes is greater than 0.6. This is because the shard redundancy strategy does not share the files downloaded by the user, and only keeps one shard in the cache, which is less affected by the user's download behavior; but the replication strategy completely shares the files downloaded by the user, and the number of file copies in the network varies with the user. downloads increased. At the same time, the higher the average availability of nodes, the lower the loss rate of file copies in the system. Too many copies remain in the system, causing the redundancy of the replication strategy to not decrease significantly with the increase of the average availability of nodes.

It can be seen from Figure 3 that although the average availability of nodes changes from 0.3 to 0.9, the redundancy of the hybrid strategy does not change significantly, hovering between 8.5 and 9.4. When the disturbance of nodes is strong, that is, when the average availability of nodes is low, there are fewer file copies in the system, and the hybrid strategy mainly uses fragmentation redundancy to save storage space. When the average availability of nodes is high, the redundancy of the hybrid strategy does not decrease but increases, the reason is similar to the replication strategy: too many copies remain in the system. These redundant redundant files or fragments will not cause harm to the stability of the system. Over time, redundant files and fragments will be gradually replaced out of the cache by the nodes.

It can be seen from Figure 4 that when the average node availability is higher than 0.47, the replication strategy saves more maintenance bandwidth than the shard redundancy strategy; when the node average availability is lower than 0.47, the shard redundancy strategy consumes less maintenance bandwidth than the replication strategy. Replication strategies ease the burden of maintenance operations by sharing files downloaded by users. When the average node availability is high, the replication strategy is very effective in saving maintenance bandwidth, because the availability of most files is automatically maintained at the target level depending on the user's download behavior. However, in a highly dynamic network environment, nodes join and leave frequently, so that the user's download speed cannot compensate for the loss of file copies and fragments. In this case, the advantages of the sharding redundancy strategy emerge: consuming the same network bandwidth, the sharding redundancy strategy can improve the file availability level more than the replication strategy; in other words, to improve the same file availability level, the sharding redundancy strategy The redundancy strategy requires less bandwidth than the replication strategy.

The biggest function of Figure 4 is to show that the hybrid strategy has the best overall effect in terms of saving maintenance bandwidth. The hybrid strategy not only shares the files downloaded by users for subsequent downloads like a replication strategy, but also uses fragmentation redundancy to maintain the availability of files. When the average availability of nodes is higher than 0.7, since the availability of most files is automatically maintained at the target level, the maintenance bandwidth consumed by the replication strategy and the hybrid strategy is approximately equal. When the average node availability is lower than 0.7, the superiority of the hybrid strategy appears. The reason why the hybrid strategy is better than the shard redundancy strategy is: first, the files downloaded by users are shared to save maintenance bandwidth; second, there is no need to maintain the master node.

The average availability of nodes shown in Figure 5 is 0.807, which is the network condition we can observe in general companies and universities. It can be seen from Figure 5(a) that the higher the file request rate, the lower the maintenance bandwidth occupancy rate. The maintenance bandwidth occupancy rate is a relative indicator of maintenance bandwidth and file download service bandwidth, and Figure 5(b) shows the absolute value of maintenance bandwidth. It can be seen from Figure 5(b) that as the average file request rate increases, the number of files transferred by the replication strategy and the hybrid strategy to maintain file availability is significantly reduced, but the curve of the fragmentation redundancy strategy only fluctuates within a small range . This phenomenon proves that sharing files downloaded by users for subsequent downloads can effectively reduce maintenance bandwidth overhead.

Figure 5(b) also shows that the hybrid strategy outperforms the other two redundant strategies in saving maintenance bandwidth when the file request rate is low. When the file request rate is greater than 10, the replication strategy and the hybrid strategy maintain very close bandwidth occupancy and are close to the horizontal axis, because the availability of most files is automatically maintained at the target level depending on the user's massive download behavior.

Claims (3)

1. based on the method that obtains high data available redundancy in the P2P system of DHT, it is characterized in that adopting the method for hybrid-type acquisition data redundancy, this method may further comprise the steps: 1), original in the P2P system is carried out the redundant Erasure Coding coding of burst; 2), the burst that coding is obtained is assigned to the respective nodes storage of P2P system; 3), the user proposes downloading request and carries out all querying nodes; 4), the user preserves as copy from the node file in download of useful file and with partial document; 5), repeating step 3) up to service stopping; 6), finish.

2. according to claim 1 a kind of, it is characterized in that step 2 based on obtaining high data available redundancy approach in the P2P system of DHT) to 4) concrete steps be: each node periodically is registered to M dispersion and separate index node with the file of its storage and the identifier of burst; Node passes through two kinds of index search files: duplicate of the document index and file fragmentation index; When certain node demand file d, it is the index node of the one or more d of random challenge at first; If the index node of inquiring about fails enough duplicate of the document and burst positional informations are provided, then continue other index nodes of random challenge; If all index nodes all can not provide enough duplicate of the document and burst positional information, the query manipulation of reforming after this node will wait for a period of time is up to query timeout; If find the complete file copy, then download this copy, otherwise node transfers to download enough burst and reconstruct original; The file of user's download automatically as shared file for follow-up download;

Each index node is periodically safeguarded the file of registration thereon and the availability of burst, if the availability of file d is lower than the requirement level, then specifies the node generation of some storage this document complete copy and distributes new burst to the node of selecting at random; If do not have complete copy in the current system, at first wait for a period of time, if node downloading slicing and reconstruct original are arranged, the redundancy of then specifying this node reparation to lose; Otherwise index node needs own downloading slicing, reconstruct original, the new burst that regeneration is enough.

3. high data available redundancy scheme in a kind of P2P system based on DHT according to claim 1 is characterized in that: in service in system, calculate the availability of current file by following formula:

$a=1-{(1-p)}^h(1-\underset{i=m}{\overset{n}{\mathrm{\&Sigma;}}}\left(\begin{array}{c}n\\ i\end{array}\right)p^i{(1-p)}^{n-i})$

Wherein: a is the availability of file, and p is the mean availability of node, and h is a complete copy quantity, and m is that file can recover required minimum burst quantity, and n is a burst quantity total in the system;

The redundancy of hybrid strategy can be obtained by the redundancy that stack is duplicated with the burst redundancy:

$r=h+\frac{n}{m}=h+{\left(\frac{{\mathrm{\&sigma;}}_a\left(h\right)\sqrt{\frac{p(1-p)}{m}}+\sqrt{\frac{{\mathrm{\&sigma;}}_a^2\left(h\right)p(1-p)}{m}+4p}}{2p}\right)}^2$

Images