System and method for perennial distributed data back up

0001The present invention relates to the field of computer networks and the backup of digital data on such networks.

0002The present invention relates more particularly to a method, a system and a device for the distributed backup of data on a network not comprising a server dedicated to backup operations. The proposed invention ensures a distribution of the backup tasks over all the storage elements connected to the network, while implementing mechanisms for perpetuating the command and control data as well as the stored digital data.

0003The goal is to create a peer-to-peer network, where many terminals connected to the Internet work together to provide a durable storage service. Each microcomputer will act as a storage device. If the microcomputer is broken down, stolen or damaged, its replacement by a new one will nevertheless allow the stored information to be found.

0004The prior art already knows, from the US patent application <patcit id="pcit0001" dnum="US20040049700A"><text>US 2004/0 049 700 </text></patcit>(Takeo Yoshida), a low-cost data storage method using the available capacities of personal computers connected to the network. When a backup client of a user PC receives an instruction to save a file from a user, the backup client makes a backup request to the backup command server. This server divides and encrypts the file to be saved into a plurality of encrypted pieces, transfers the encrypted pieces to the user PCs and stores the encrypted piece in the hard disk of the user PCs. When the distributed backed up file is to be extracted, the user PC obtains each encrypted coin from the other user PCs where it was stored, and combines them and decrypts the coins to restore the original file.

0005The proposed solution is to distribute the data storage by dispersing the data over a set of devices connected to the network. However, this system requires high availability of peripherals, or at least that they can be activated remotely, to access the data. The other disadvantage of this system is that it cannot deal with the failure of storage devices, and the loss of data on a storage device is irrecoverable. Finally, this system does not scale up because storage coordination is ensured by a server through which all the data passes.

0006The prior art also knows, from the patent application <patcit id="pcit0002" dnum="WO02063484A"><text>PCT WO 02/063 484</text></patcit> (SS8 Networks), a distributed data storage system with a highly scalable and highly available architecture. In one embodiment of the invention, this distributed data storage system comprises a plurality of data storage units which are controlled by an object management system. This object management system selects data storage units to perform file access requests as a function of the inputs / outputs with which these file access requests are associated. In response to a request to create a file associated with an external input of a distributed data storage unit, the object management system preferably creates a data file in that distributed data storage unit. In response to a file location request associated with a data file and an external output from a distributed data storage unit, the object management system preferably returns a host name and a host name. accessing a copy of the data file that is stored in this distributed data storage unit. This object management system also makes redundant copies of data files in different units to provide high availability.

0007In this patent application, the system provides redundant distributed storage nevertheless requiring a centralized management system comparable to a management server. The proposed solution is not viable without the presence of this server, which makes it extremely dependent on the proper functioning of the server.

0008It is also known, from the American patent application <patcit id="pcit0003" dnum="US20020114341A"><text>US 2002/0 114 341 (Andrew Sutherland et al)</text></patcit>, a peer-to-peer memory system comprising a memory coordinator centrally managing distributed memory resources according to system rules administered through a central administrative console. Memory resources are unused portions of storage media, for example, hard drives that are included in devices such as personal computers, workstations, laptops, file servers, etc., which are connected to a computer network.

0009This patent application proposes storage distributed over a network requiring the presence of a storage coordinator (<i>storage coordinator</i>), a kind of server, which distributes the data to be stored on the various devices or nodes of the network.

0010Likewise, the US patent application <patcit id="pcit0004" dnum="US2004064693A"><text>US 2004 / 064,693 (Akhil K. Arora and others) </text></patcit>addresses a distributed indexing mechanism for indexing and retrieving authentication information in peer-to-peer networks. A distributed index, of the DHT type, can be used to store identity information in a decentralized manner on a plurality of even nodes. Identity information can be used, for example, to authenticate users. Distributed indexes allow identity information to be broadcast across multiple peer nodes such that the load is broadcast among many peer nodes.

0011This request proposes to use DHT to set up a distributed identification mechanism (users or other). The peers of a DHT are made active (by requests for authentication information) so as not to restrict storage to simple passive storage, but their use does not go beyond this framework and does not allow the detection of faults on a other node.

0012Peer-to-peer networks (<i>peer to peer</i>) using distributed hash tables, also called DHT (<i>Distributed Hash Table</i>) such as Chord, CAN, Pastry or Tapestry, to achieve distributed data storage.

0013The use of DHTs in such networks provides a mechanism for routing between peers through an over-network or <i>overlay</i> fault tolerant and greater resistance to attacks linked to the routing-overlay association. It also offers a distributed and redundant dictionary on this super-network: each entry in this dictionary is made up of a key and an associated object (for example a digital data file). The object is inserted into the DHT which replicates it to different nodes in order to ensure a certain level of fault tolerance. The use of DHT also offers a logical organization of the data: a unique identifier is assigned to each of the peers, ideally the identifiers are chosen in such a way that they are as dispersed as possible in the space of available names, and a function (eg identity) projects the key space from the dictionary into the namespace of peers. When inserting a new object in the DHT dictionary, the peer that will store it is the one that will be reached by the routing algorithm based on the object's projected key in the namespace; in general, the routing algorithm designates the peer which has the identifier closest to the projection of the key. The inserted object is replicated by DHT to cope with the disappearance of peers. Typically, each peer maintains a list of peers which have a “neighbor” identifier (in the sense of the routing algorithm) in the namespace, the object is then duplicated on these peers. The known mechanisms associated with DHTs make it possible to manage data by simple primitives such as<i>search, put, get, free,</i> ...

0014Another limitation concerns the "heavy" use of DHTs: they store data, which consequently increases the traffic on the network when requests are sent.

0015The state of the art also knows the document <nplcit id="ncit0001" npl-type="s"><text>“OceanStore: An Architecture for Global-Scale Persisent Storage” by Kubiatowicz et al., XP002993765</text></nplcit>, or the document <nplcit id="ncit0002" npl-type="s"><text>“Tapestry: An Infrastructure for FAult-tolerant Wide-Area Location and Routing” by Zhao BY et al., XP002995768</text></nplcit>. However, these two proposals do not allow, in particular, management of failures of the nodes of the DHT.

0016The present invention intends to remedy the drawbacks of the prior art by proposing a backup method distributed over a computer network based on the use of distributed hash tables to permanently store the command and control or storage management information. . The term “command and control or management information” is understood to mean all the data associated with the data to be stored, with the nodes of the network which are used during the storage or during the retrieval of the data.

0017The method according to the present invention responds particularly well to the problems of current computer networks: evolution of the network by adding / removing new nodes, security against attacks, data protection, redundancy of storage information, data sustainability during breakdowns or failures. .

0018To this end, the invention relates in its most general sense to a distributed backup method of a block B of digital data on a computer network as defined by the subject of claim 1.

0019According to one embodiment, said method comprises, following said division step, a step of calculating s redundancy fragments calculated from said r fragments F.

0020According to a particular embodiment, said fragments are stored, during the storage step, on all different nodes.

0021Particularly, DHT contains only control data and no data fragments.

0022According to one implementation, said method further comprises a step of periodically sending by each of said nodes activity information to a set of nodes selected by the DHT.

0023Particularly, said method further comprises a step of reconstructing the data stored on said failed node C_breakdown and updating, in the DHT, the list of nodes storing at least one fragment of said B block.

0024In one embodiment, the fragments reconstructed during said reconstruction step are each stored on at least one other healthy node.

0025The invention also relates to a distributed data backup device for implementing the method comprising a processor, a storage memory, network connection means and distributed data control means, of the DHT distributed hash table type. .

0026According to one embodiment, said device is in the form of an external box which is added to an already existing computer station.

0027The invention also relates to a distributed backup system comprising at least two preceding devices connected to each other by a computer network.

0028Particularly, said system comprises a plurality of devices according to one of claims 6 or 7, said devices being connected to several interconnected networks.

0029The invention will be better understood with the aid of the description, given below for purely explanatory purposes, of an embodiment of the invention, with reference to the appended figures:<ul id="ul0001" list-style="bullet" compact="compact"><li>the <figref idref="f0001">figure 1</figref> represents the overall architecture of a peer-to-peer network according to the present invention;</li><li>the <figref idref="f0002">figure 2</figref> illustrates the software architecture of the system;</li></ul><ul id="ul0002" list-style="dash" compact="compact"><li>the <figref idref="f0003">figure 3</figref> illustrates the architecture of the distributed storage device;</li><li>the <figref idref="f0004">figure 4</figref> represents an example of the structure of the distributed hash table;</li><li>the <figref idref="f0005">figure 5</figref> illustrates the replication and decomposition of a block of data before distributed storage;</li><li>the <figref idref="f0006">figure 6</figref> illustrates the monitoring of network peers by dynamically updating the DHT by each peer;</li><li>the <figref idref="f0007">figure 7</figref> illustrates the exchanges between the different elements of the network during the initialization of the network;</li><li>the <figref idref="f0008">figure 8</figref> illustrates the exchanges during the writing (saving) of data on the network according to the present invention;</li><li>the <figref idref="f0009">figure 9</figref> illustrates the exchanges during the data recovery step in the network;</li><li>the <figref idref="f0010">figure 10</figref> represents the exchanges between the various elements of the network during the reconstruction of the “lost” data of a faulty peer.</li></ul>

0030The present invention provides a method, system and device for distributed and perennial peer-to-peer data storage using the disk space available on peers to store user data therein. The proposed solution makes it possible to propose a storage system independent of the robustness of local components (typically the hard disk). The data are protected from accidental (fire) or other deterioration (theft of equipment for example).

0031Data availability is also guaranteed by the system, which implements its replication process as soon as it is connected to the network. The real-time backup property and data availability are not guaranteed in most backup systems which make copies of the data to be protected at regular intervals (incremental type backup on CD-Rom or network).

0032Sustainability is ensured by fault tolerance properties, implemented in particular by data fragmentation and the addition of redundancy, all associated with a fault detection mechanism and dynamic fragment repair. lost.

0033The <figref idref="f0001">figure 1</figref> illustrates the architecture of peer-to-peer systems according to the present invention. A plurality of peers (1) are connected to a network (2) constituting a mesh network. The digital data to be saved can circulate on all branches of the network. The control data (all the data management information stored in a distributed manner) circulate on the same network by a suitable mechanism: that of the DHTs as described in the prior art. Any request on the DHT is carried out by any path of the network in the same way that data is sent on the network. The term “peer” is understood to mean any node of the network which may simply be a computer. Peer-to-peer networks are based on equality between all the nodes of the network, that is to say that each of the computer stations plays the same role as the others. This system does not include any server centralizing any operation or storage management. Certain servers dedicated to other tasks can be present on the network without altering the operation of the invention: they are seen as simple peers of the network.

0034The network (2) used may simply be a corporate network, but ideally will be the Internet. In this case, the present invention offers a storage solution distributed throughout the planet.

0035The <figref idref="f0002">figure 2</figref> illustrates the software architecture of the system at the level of a client workstation (network node).

0036The system according to the present invention consists of two main entities: a <b>Customer</b> (20) which is a space requester and a <b>Provider</b> (21) which allocates and manages the space. The invention achieves low-level storage: the system can be seen as a virtual hard disk. The Client can be a specific file system (CFS, NFS, Fuse, ...) interfaced with the network to allow the user to manage his data in the form of a file. The network according to the present invention is interoperable with other storage systems, such as IBP (<i>Internet Backplane Protocol</i>), Past...

0037Take for example a user who sends his file (26) to the file system, interfaced with the present invention. This file is split into blocks (25) which are then sent to the<b>Distributor</b> (22). The latter holds information on the available resources by querying the<b>Resource Manager</b> (24). The dispatcher cuts the blocks into fragments including redundancy and correction fragments (Reed-Salomon). Finally, it distributes these fragments among peers dedicated to storage, the<b>Storage</b> (23), which locally save the fragments.

0038The management of shared storage space is therefore based on three different applications:<ul id="ul0003" list-style="none" compact="compact"><li>▪ the <b>Customer</b> (20) is the user interface to request to store blocks, to recover them or to delete them;</li><li>▪ the <b>Distributor</b> (22) is the service provider, it holds and manages the information on the resources; and</li><li>▪ the <b>Storer</b> (23) is the peer that saves the data as fragments on the local hard drive.</li></ul>

0039Each of the nodes of the network has these three applications since they are all likely to play the role of requestor or storer.

0040The Resource Manager (24) is the central body for the management of the system. It memorizes the state of each Storer (it knows the list of all the fragments archived on the Storages), takes care of the detection of dead nodes and activates the reconstruction of the fragments when the Storerooms disappear. In the prior art, the Resource Manager (24) is based on dedicated servers: the management of the system is concentrated on the Resource Manager and therefore constitutes a weak point in the architecture of the system since its central position makes it a target. privileged for an attack of <i>Denis from Service.</i> The present invention proposes to distribute the functions of the Resource Manager (24) on all the clients (nodes) of the network in order to improve the resistance of the system to the simultaneous failure (intentional or accidental) of a large number of peers. . These distributed means memorize the state of each Storekeeper, have a list of all the fragments archived on the Storekeepers, take charge of the detection of dead nodes and activate the reconstruction of the fragments when this is necessary to preserve the sustainability of the data.

0041In an embodiment illustrated by <figref idref="f0003">figure 3</figref>, the storage device (30) according to the present invention consists of a processor CPU (31) controlling a random access memory (33) of the RAM type <i>(Random Access Memory),</i> a hard disk type storage memory (32) and network connection means (36), for example a network card. An operating system (34) is executed on the processor and allows the aforementioned applications (35) to be executed. For example, a motherboard of small dimension and low consumption, with an x86 type processor, a RAM, a hard disk and a network card (for example<i>fast ethernet</i>)<i>.</i> Everything is integrated into a small-sized box. The box is connected to the company's local network and can also access the network of other similar boxes (for example on the Internet) to provide storage service.

0042This device can be integrated into an already existing computer. To guarantee the security of the invention, the device may consist of an external box added to a node of the network, the box being able to use, depending on the embodiment chosen, certain resources of the computer (network connection for example).

0043The present invention proposes a mechanism making it possible to distribute the previously mentioned Resource Manager (24). This mechanism tends to focus all resource management on the peers of the network. New architectures propose routing mechanisms between peers based on an over-network (<i>overlay</i>) and as well as resource management systems based on distributed hash tables or DHT (<i>Distributed Hash Table</i>). As discussed in the prior art, the use of DHTs for distributed storage provides data replication to ensure fault tolerance.

0044In a DHT, the communication complexity is a function of the number of peers and of the data, which generates a significant additional cost in terms of communication in the network. Especially when the size of the data is considerable, which is the case for a distributed backup network. It is for this reason that DHT according to the present invention is used only for storing metadata, which is much smaller in size than the data itself. By metadata is meant the storage distribution control data (data relating to nodes, data fragments on each node, etc.). DHT also has a memory cache role in order to increase the overall performance of the system.

0045Illustrated by the <figref idref="f0004">figure 4</figref>, the distributed hash table has six objects:<ul id="ul0004" list-style="none" compact="compact"><li>▪ <b>DNSlike</b> : this object makes the link between the NodeID (the identifier of the node) and the physical address (the IP address) of each peer;</li><li>▪ Life cycle <b>(LifeCycle)</b> : each peer, represented by its NodeID, regularly stores a presence message, this message represents its life cycle;</li><li>▪ <b>RootID</b> : when storing a block, the Client peer stores its RootID which represents the pointer to the Root Block containing all the information necessary to retrieve all of the client's blocks;</li><li>▪ <b>Action</b> : the dispatcher stores the commands that have not yet been executed. In the event of a breakdown of the Distributor, it can always re-execute pending commands. The most common example is the deletion of the blocks: if Storage Cabinets are not available, it is necessary to be able to re-execute the command later;</li><li>▪ <b>Fragments</b> : each Storekeeper stores the list of all its fragments within a DHT; and</li><li>▪ <b>Blocks</b> : when storing a block, the client peer stores the list of NodeIDs containing the fragments of the block identified by its BlocID (unique identifier of the block).</li></ul>

0046The first four objects are intended to collect functional and behavioral information from peers, while the last two relate to the storage of data on different peers.

0047The different steps implemented in the present invention are as follows:<ul id="ul0005" list-style="none" compact="compact"><li>▪ The initialization step when a new peer incorporates the network is illustrated by the <figref idref="f0007">figure 7</figref>. Each client that will serve as entry points to the<i>overlay</i> calculates its NodeID according to a certain metric, for example according to its geolocation. This identifier is kept for the life of the peer. Peers are added one by one in<i>the overlay.</i> Each peer in the process of joining the network calculates a unique NodeID. The peers contact the nearest entry point numerically in the list they know and insert according to their NodeID in the<i>overlay</i> and reconstructs its own routing table using its neighbors. At the birth of a peer, in addition to its unique identifier the NodeID, the peer obtains a list of BlocID. The various nodes of the network update (71) the Resource Manager, ie the DHT.</li><li>▪ The maintenance step which consists of each peer storing or updating within the DHT its DNSlike object which contains information concerning the association of its NodeID with its IP, as well as its life cycle. In this way to know when a peer disconnects or if it is down, just read the DHT. Since it is possible to recover the list of fragments that a peer has: reconstruction of fragments lost by the loss of a peer is always possible.</li><li>▪ The step of storing a block is illustrated by <figref idref="f0008">figure 8</figref> : a peer P_i want to store a block B_i. Illustrated by the<figref idref="f0005">figure 5</figref>, the block to be stored (50) can be replicated in several blocks (50a, 50b and 50c) to allow fault tolerance (here two blocks can be lost without altering the data). It calculates a virtual group number based on the BlocID. Then peer P_i obtains by the DHT the list of NodeIDs of the Storage units corresponding to the virtual group GV_i= {P₁; ...; P_f}. A virtual group is a set of f pairs selected so as to minimize the correlation of simultaneous death. In more detail:<ul id="ul0006" list-style="dash" compact="compact"><li>Client: The peer client P_i send a block B_i to a Distributor (81).</li><li>Distributor: The Distributor cuts the received block (50) B_i in f fragments: s segmentation fragments (51) and r redundancy fragments (52) (for example a Reed-Salomon redundancy), as illustrated on <figref idref="f0005">figure 5</figref>. Then the dispatcher sends a request (83) to search for a peer, from P₁ up to P_f. The NodeIDs obtained (84) will be used for the composition of the virtual group associated with the storage of block B_i. The Dispatcher stores (85) the fragments on the indicated peers, called Storageers.</li><li>Storer: it stores fragments from various blocks. The Storerooms update their list of fragments and communicate it to the DHT. Each Storer sends an acknowledgment to the Dispatcher upon receipt of a fragment.</li><li>Dispatcher: after validation of the previous operations by acknowledgments, the Dispatcher stores (86) in a DHT, with the BlocID as a key, the NodeIDs corresponding to the Storage Cabinets storing the BlocID. Finally, the Dispatcher informs (82) the customer of the good progress of the storage of his block B_i by sending an acknowledgment.</li></ul></li><li>▪ The step of recovering / receiving a block is illustrated by <figref idref="f0009">figure 9</figref> : a peer P_i would like to receive his block B_i previously stored. The action takes place as follows:<ul id="ul0007" list-style="dash" compact="compact"><li>Client: The client peer sends a request to receive (91) block B_i to the dispatcher.</li><li>Dispatcher: The Dispatcher sends a request to the DHT (95) to request the corresponding BlocID, the DHT sends it (96) the list of NodeIDs storing the fragments making up the blocks. The Dispatcher then interrogates the DHT to find out the IPs of the Storage Cabinets according to the given NodeIDs. The Dispatcher requests the fragments from the Storage Stores corresponding to the NodeIDs provided:</li><li>Storer: At the request of the Dispatcher (93), it sends (94) the stored fragment.</li><li>Dispatcher: When the Dispatcher has received s fragments among the s + r, the fragments are then used to reconstruct block B_i. The dispatcher sends block B_i to the Client (92).</li></ul></li></ul>

0048The present invention also relates to mechanisms making it possible to constantly monitor the state of the network and of the peers, and to proceed, if necessary, to the reconstruction of data lost by the failure of one or more elements of the network.

0049Peer monitoring always relies on DHT, and more specifically on the object <b>LifeCycle</b> of each of the peers, as illustrated by <figref idref="f0006">figure 6</figref>. The DHT sets up the process of duplicating control data which causes several peers to receive the "life cycle". The peer regularly sends its life cycle to peers selected by the DHT, which thereby monitors the activity of this peer.

0050Failure detection is ensured as follows: each peer, for example N8, communicates to the DHT at regular intervals a message which feeds the “LifeCycle” life cycle of the peer into the DHT. This object is sent according to the NodeID of the peer on the closest neighbors (N1, N21, N56, ...) (for example, the closest neighbors are those whose NodeID is closest to that of the peer N8) of the pair NodeID N8.

0051If the peer is not down, the object concerning its life cycle is stored at home and in the k-1 peers numerically closer to its NodeID, by the data replication mechanisms inherent in DHT (k is a parameter which allows to fix the fault tolerance of k-1 elements).

0052We can notice that if the peer disconnects in a software way, an update of its life cycle is sent before the effective disconnection of the peer. Thus, the k-1 peers can analyze in the local DHT (without communication), the life cycle state of the given peer. In this way, each peer reads the lifecycle of other peers associated by routing within the DHT.

0053When a peer N21 detects an anomaly concerning the life cycle of peer N8 (absence of the last update), it refers to the k-1 other peers designated by <i>the overlay.</i> The peer N21 enters a phase of consultation with the k-1 peers and depending on the information communicated to it, the peer initiating the request may or may not trigger a reconstruction of the “lost” data of the node N8. This concertation step can be carried out by an algorithm known as Byzantine generals to deal with malicious peers in decision-making. Several phases of total information exchange between the peers are carried out, in which each communicates its opinion on the failure of the peer concerned. The multiple phases make it possible to detect inconsistent peers and to make a good decision with a certain level of guarantee: the best-known algorithms tolerate the maliciousness of up to a third of the peers.

0054If a reconstruction is requested when it is not necessary, this is not detrimental to the system. However, it will be necessary to manage the fact that the detection is unreliable, by constantly monitoring the reconstruction process.

0055Illustrated by the <figref idref="f0010">figure 10</figref>, the reconstruction of the “lost” data of the faulty peer N8 is triggered by the peer N21 which detected the fault. N21 requests (101) from the DHT the fragments stored by the failed peer N8. In one embodiment of the invention, the routing and naming mechanisms allow the peer itself to hold some of the information specific to the data that it contains and that its close neighbors contain. Thus, this operation cannot require any communication, only the consultation of the DHT table.

0056The search is performed based on the NodeID of the failed peer. A request (102) is then launched to recover these fragments. Once the list of fragments has been recovered (103), the peer deduces all the damaged blocks and requests the reconstruction of the lost fragments. These fragments are reconstructed using the redundancy mechanism and they are stored on peers selected by the same method as during the initial storage of the block. When the operation is complete, the peer updates the list of NodeIDs for the BlocID, in the DHT.

0057The present invention also implements additional mechanisms making it possible to increase the security of the system.

0058Among other things, securing peer-to-peer communications concerns:<ul id="ul0008" list-style="none" compact="compact"><li>▪ the connection of (new) peers on the network which is based on a list of trusted nodes which are the dedicated servers;</li><li>▪ peer identification in order to avoid connecting a malicious node to the network. This identification is based on public key authentication systems;</li><li>▪ transaction confidentiality implements encryption (encryption, scrambling, transposition) of transaction data between peers by using a secret key encrypted by the public key of the peer.</li></ul>