Replica identification and collision avoidance in file system replication

A unique file-system node identification (ID) is created for each newly created node in a file system repository by combining a grid identification (ID), a repository identification (ID), and a node identification (ID) to form the unique file-system node ID. The unique file-system node ID is associated with a unique association identification (ID) for creating an association for linking the node from a source repository to a target repository when performing a replication operation between a repository and another repository. The different replication instances of the node in the file system repository are distinguished by the unique association ID assigned to each of the replication instances.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to computers, and more particularly, to replica identification and collision avoidance in file system replication.

2. Description of the Related Art

In today's society, computer systems are commonplace. Computer systems may be found in the workplace, at home, or at school. Computer systems may include data storage systems, or disk storage systems, to process and store data. One such process is data replication. Replicated data systems may externalize various logical data storage entities, such as files, data objects, backup images, data snapshots or virtual tape cartridges. One type of replication is file system replication. File system replication involves maintaining a copy (replica) of a file on a remote storage that may be updated locally. Despite many benefits offered from file system replication, there are accompanying limitations that negatively affect replication efficiency, system performance, data consistency, and additional challenges.

SUMMARY OF THE INVENTION

File-system replication is the process of replicating files, directories and file-systems at a logical level, rather than replicating at the storage block level. Similarly to block-level storage replication, file-system replication can be either synchronous or asynchronous. In synchronous mode, file-system operations at the source repository are blocked until the target repository has acknowledged a successful replication. In asynchronous mode, the file-system's operations, contents, and structure are replicated in parallel with changes taking place in the source repository of the file system.

As such, a need exists for a global unique identification so that each repository may distinguish other repositories data structures, files, and/or objects as compared to the repositories own generated data structures, files, and/or objects when a replication operation is performed to other repositories (in a grid/repository environment). In other words, the file system replication operations need to be able to identify the origin of each object. However, when multiple copies of a file-system node are replicated between repositories that merely identify the origin of the object, such action may be insufficient since the target repository must be capable of discriminating between multiple copies of the same object in the target repository.

Also, a need exists for a solution for discriminating between multiple copies of the same object in the target repository and also for providing a global unique identification. Moreover, a need exists for an additional association on the replicated structural identification of the file-system nodes rather than generating a new and different unique ID for the file-system node replication in the target that could both differentiate but will lose the association to the original node in the source repository. Thus, the file-system replication maintains the ability to compare the same node name and structure between the source and the target repositories.

Accordingly, and in view of the foregoing, various exemplary method, system, and computer program product embodiments for replica identification and collision avoidance in a file-system replication system in a computing environment are provided. In one embodiment, by way of example only, a unique file-system node identification (ID) is created for each newly created node in a file system repository by combining a grid identification (ID), a repository identification (ID), and a node identification (ID) to form the unique file-system node ID. The unique file-system node ID is associated with an unique association identification (ID) for creating an association for linking the node from a source repository to target repository when performing a replication operation in between file-system repositories. The unique association ID allows for a separate and unique association between repositories (e.g., between source repositories and target repositories). In other words, each node may have one or more unique associations. The different replication instances of the node in the target file system repository are distinguished by the unique association ID assigned to each of the replication instances.

DETAILED DESCRIPTION OF THE DRAWINGS

As mentioned previously, file-system replication means replicating files, directories and file-systems at a logical level rather than replicating files at the storage block level. Similarly to block-level storage replication, file-system replication can be either synchronous or asynchronous. In synchronous mode, file-system operations at the source repository are blocked until the target repository has acknowledged their successful replication. In an asynchronous mode, a file-system's operations, contents, and structure are replicated in parallel to the changes taking place in the source repository.

File-system replication systems may yield several benefits. First, since data is captured at the node (e.g., file or directory) level it can make an informed decision on whether to replicate based on the node's attributes (e.g. file type, location, etc.). Thus, unlike block-level storage replication, in which entire volumes need to be replicated, file-system replication systems have the ability to exclude temporary files or sections of the file-system that have no value. Moreover, such file-systems can leverage file data deduplication, since the file-system replication is aware of logical level context. This substantially reduces the bandwidth of the replication as well as decreases the storage capacities on the target repositories.

In one implementation, the file-systems' design provides a clear separation between structure and namespace and the storage or data represented at the block level usually by some form of IDs (e.g. inodes in most UNIX file-systems). In the local repository's file-system, this separation is enough to identify file-system objects (nodes), such as directories and files, because the names are unique, and as such, the location in the file-system structure is uniquely identified. Moreover, the data (block) level of the object is uniquely identified by keeping the node identification's (ID) unique.

However, in the context of file-system replication, this local identification is not enough for global replica identification and collision avoidance within a repository and/or grid. If a global unique identification exits, then each repository can distinguish other repositories received objects from the repositories own generated objects. In other words, the system can identify the origin of each object. In order to address the challenge for global replica identification and collision avoidance within a repository and/or grid, in one embodiment, a repository is created independently of the grids. A grid identification (ID) is computed for the grid. In one embodiment, the computation may be performed by incrementing the value of the grid ID variable maintained by a software entity that corresponds to a grid set (denoted as a grid set manager) and facilitates generation of grids within that grid set. Alternatively, a unique grid ID may be assigned. The repository may subsequently be assigned to a grid, and further migrated between grids in the same grid set (at any given time a repository may be associated with a single grid). Upon assignment of a repository to a grid, the repository is assigned with a unique “repository identification (ID)” computed by incrementing the value of a repository ID variable maintained by a software entity, which corresponds to a grid (denoted as a grid manager) and facilitates affiliation of repositories to that grid. Alternatively, the user may assign a unique repository ID.

However, if a global, unique file-system node identification (ID) exits, then each repository can distinguish between objects received from other repositories as well as the repositories own generated objects. In other words, the file-system repository allows for the identification of the origin of each object. However, when multiple copies of a file-system node are replicated between repositories, global unique identification is insufficient, since the target repository must be capable of discriminating between multiple copies of the same object that are within the target repository. In other words, the target system/repository should be able to discriminate multiple copies of the same object within the target repository in addition to discriminating objects in between repositories within the grid. For example, consider replicating the same node (e.g. file) from repository “S” to repository “D”, but to different target directories. The local identification will not satisfy the need to discriminate within repository D, as both instances will carry the same identification (ID) value. In replication to other repositories (e.g., repositories in a grid environment) there is a need for a global unique file system node identification (ID) so that each repository can distinguish between objects received from other repositories and objects generated from the local (and/or source) repository. In other words, the file-system replication system can distinguish between objects received from other repositories and objects generated from the local repository.

In order to distinguish multiple copies of the same object received from a source repository, as mentioned above, the file-system replication system requires additional information that will provide a differentiation on top of the global (grid-wide) identification. Instead of generating a new and different unique ID for the file-system node replication in a target repository, which could differentiate but lose the association to the origin node in the source repository, an additional association on the replicated structural identification of the file-system nodes is provided. Thus, the embodiments of file-system replication provide for the ability to compare the same node's name and structure between the source and the target repositories.

Furthermore, file-system replication systems need to maintain consistency of structure and data. In other words, the consistency of structure and data refers to the synchronization between file-system structures and the file-system replication systems' replicas at the target repository beyond the data consistency. In order to achieve consistency of structure and data, in the complex domain of file-system operations (e.g. rename, attribute change, restructuring), the replication system must enforce ordering during replication procedures. Thus, the replication procedures must reflect changes in a file-system's structure at the target repository in the order (or sequence) in which the changes were performed in the source repository. Moreover, when initiating a new replication association between the source and target repositories, or adding new file-system nodes to the association's supervision, the association may become unsynchronized, as only new operations on the nodes are sent to the target. Thus, these systems must be able to efficiently verify which file-system structures are indeed synchronized or unsynchronized, and minimize disruption to normal file-system operations and/or the replication procedure.

The mechanisms of the illustrated embodiments seek to provide a solution for efficient replica identification and collision avoidance mechanism in file-system replication. The illustrated embodiments address the following aspects of efficient replication for identification and collision avoidance. (1) The illustrated embodiments provide efficient discrimination between different replicas of the same node within a destination repository (e.g., target repository) thereby avoiding collisions. (2) The illustrated embodiments provide efficient detection of replicas' synchronization within the association. In other words, providing efficient detection of replicas' synchronization without the need of data or structure verification between the original and replication objects. (3) The illustrated embodiments ensure absolute identity (synchronization) between the original and replication nodes. In other words, the probability for a difference between the source and target copies should be zero. (4) The illustrated embodiments provide procedures for replica identification and collision avoidance that are independent of the replication procedures and/or file-system layout and implementation. Thus, replicas are identified, the replica synchronization is verified with the original copies, and collisions are avoided for efficient replication.

The software entities as described above that correspond to a grid set, a grid, a repository, and unique file-system node identification may be implemented, as one skilled in the art will anticipate. For example, a particular software entity may be referred to as a “grid manager.” The grid manager software may assist in managing the various identifications described above. For example, the grid manager may perform a determination as to whether a particular grid ID has been assigned, and assign the grid ID to a new grid. Similarly, the grid manager or other software entity may manage and assign repository ID's and the unique file-system node ID. The grid manager software may be implemented in conjunction with other storage management software, again as one skilled in the art would expect.

Turning now toFIG. 1, exemplary architecture10of a computing system environment is depicted. The computer system10includes central processing unit (CPU)12, which is connected to communication port18and memory device16. The communication port18is in communication with a communication network20. The communication network20and storage network may be configured to be in communication with server (hosts)24and22and storage systems, which may include storage devices14. The storage systems may include hard disk drive (HDD) devices, solid-state devices (SSD) etc., which may be configured in a redundant array of independent disks (RAID). The operations as described below may be executed on storage device(s)14, located in system10or elsewhere and may have multiple memory devices16working independently and/or in conjunction with other CPU devices12. Memory device16may include such memory as electrically erasable programmable read only memory (EEPROM) or a host of related devices. Memory device16and storage devices14are connected to CPU12via a signal-bearing medium. In addition, CPU12is connected through communication port18to a communication network20, having an attached plurality of additional computer host systems24and22. In addition, memory device16and the CPU12may be embedded and included in each component of the computing system10. Each storage system may also include separate and/or distinct memory devices16and CPU12that work in conjunction or as a separate memory device16and/or CPU12.

FIG. 2is an exemplary block diagram200showing a hardware structure of a data storage system in a computer system according to the present invention. Host computers210,220,225, are shown, each acting as a central processing unit for performing data processing as part of a data storage system200. The cluster hosts/nodes (physical or virtual devices),210,220, and225may be one or more new physical devices or logical devices to accomplish the purposes of the present invention in the data storage system200. In one embodiment, by way of example only, a data storage system200may be implemented as IBM® System Storage™ DS8000™. A Network connection260may be a fibre channel fabric, a fibre channel point to point link, a fibre channel over ethernet fabric or point to point link, a FICON or ESCON I/O interface, any other I/O interface type, a wireless network, a wired network, a LAN, a WAN, heterogeneous, homogeneous, public (i.e. the Internet), private, or any combination thereof. The hosts,210,220, and225may be local or distributed among one or more locations and may be equipped with any type of fabric (or fabric channel) (not shown inFIG. 2) or network260to the storage controller240, such as Fibre channel, FICON, ESCON, Ethernet, fiber optic, wireless, or coaxial adapters. Data storage system200is accordingly equipped with a suitable fabric (not shown inFIG. 2) or network260to communicate. Data storage system200is depicted inFIG. 2comprising storage controllers240and cluster hosts210,220, and225. The cluster hosts210,220, and225may include cluster nodes.

To facilitate a clearer understanding of the methods described herein, storage controller240is shown inFIG. 2as a single processing unit, including a microprocessor242, system memory243and nonvolatile storage (“NVS”)216, which will be described in more detail below. It is noted that in some embodiments, storage controller240is comprised of multiple processing units, each with their own processor complex and system memory, and interconnected by a dedicated network within data storage system200. Storage230(labeled as230a,230b, and230ninFIG. 3) may be comprised of one or more storage devices, such as storage arrays, which are connected to storage controller240(by a storage network) with one or more cluster hosts210,220, and225connected to each storage controller240.

In some embodiments, the devices included in storage230may be connected in a loop architecture. Storage controller240manages storage230and facilitates the processing of write and read requests intended for storage230. The system memory243of storage controller240stores program instructions and data, which the processor242may access for executing functions and method steps of the present invention for executing and managing storage230as described herein. In one embodiment, system memory243includes, is in association with, or is in communication with the operation software250for performing methods and operations described herein. As shown inFIG. 2, system memory243may also include or be in communication with a cache245for storage230, also referred to herein as a “cache memory”, for buffering “write data” and “read data”, which respectively refer to write/read requests and their associated data. In one embodiment, cache245is allocated in a device external to system memory243, yet remains accessible by microprocessor242and may serve to provide additional security against data loss, in addition to carrying out the operations as described in herein.

In some embodiments, cache245is implemented with a volatile memory and non-volatile memory and coupled to microprocessor242via a local bus (not shown inFIG. 2) for enhanced performance of data storage system200. The NVS216included in data storage controller is accessible by microprocessor242and serves to provide additional support for operations and execution of the present invention as described in other figures. The NVS216, may also referred to as a “persistent” cache, or “cache memory” and is implemented with nonvolatile memory that may or may not utilize external power to retain data stored therein. The NVS may be stored in and with the cache245for any purposes suited to accomplish the objectives of the present invention. In some embodiments, a backup power source (not shown inFIG. 2), such as a battery, supplies NVS216with sufficient power to retain the data stored therein in case of power loss to data storage system200. In certain embodiments, the capacity of NVS216is less than or equal to the total capacity of cache245.

Storage230may be physically comprised of one or more storage devices, such as storage arrays. A storage array is a logical grouping of individual storage devices, such as a hard disk. In certain embodiments, storage230is comprised of a JBOD (Just a Bunch of Disks) array or a RAID (Redundant Array of Independent Disks) array. A collection of physical storage arrays may be further combined to form a rank, which dissociates the physical storage from the logical configuration. The storage space in a rank may be allocated into logical volumes, which define the storage location specified in a write/read request.

In one embodiment, by way of example only, the storage system as shown inFIG. 2may include a logical volume, or simply “volume,” may have different kinds of allocations. Storage230a,230band230nare shown as ranks in data storage system200, and are referred to herein as rank230a,230band230n. Ranks may be local to data storage system200, or may be located at a physically remote location. In other words, a local storage controller may connect with a remote storage controller and manage storage at the remote location. Rank230ais shown configured with two entire volumes,234and236, as well as one partial volume232a. Rank230bis shown with another partial volume232b. Thus volume232is allocated across ranks230aand230b. Rank230nis shown as being fully allocated to volume238—that is, rank230nrefers to the entire physical storage for volume238. From the above examples, it will be appreciated that a rank may be configured to include one or more partial and/or entire volumes. Volumes and ranks may further be divided into so-called “tracks,” which represent a fixed block of storage. A track is therefore associated with a given volume and may be given a given rank.

The storage controller240may include a replica identification module255, association module257, and a repository module259. The replica identification module255, association module257, and the repository module259may work in conjunction with each and every component of the storage controller240, the hosts210,220,225, and storage devices230. The replica identification module255, association module257, and the repository module259may be structurally one complete module or may be associated and/or included with other individual modules. The replica identification module255, association module257, and the repository module259may also be located in the cache245or other components.

The storage controller240includes a control switch241for controlling the fiber channel protocol to the host computers210,220,225, a microprocessor242for controlling all the storage controller240, a nonvolatile control memory243for storing a microprogram (operation software)250for controlling the operation of storage controller240, data for control and each table described later, cache245for temporarily storing (buffering) data, and buffers244for assisting the cache245to read and write data, a control switch241for controlling a protocol to control data transfer to or from the storage devices230, replica identification module255, association module257, and the repository module259, in which information may be set. Multiple buffers244may be implemented with the present invention to assist with the operations as described herein. In one embodiment, the cluster hosts/nodes,210,220,225and the storage controller240are connected through a network adaptor (this could be a fibre channel)260as an interface i.e., via at least one switch called “fabric.”

In one embodiment, the host computers or one or more physical or virtual devices,210,220,225and the storage controller240are connected through a network adaptor (this could be a fibre channel)260as an interface i.e., via at least one switch called “fabric.” In one embodiment, the operation of the system shown inFIG. 2will be described. The microprocessor242may control the memory243to store command information from the host device (physical or virtual)210and information for identifying the host device (physical or virtual)210. The control switch241, the buffers244, the cache245, the operating software250, the microprocessor242, memory243, NVS216, replica identification module255, association module257, and the repository module259are in communication with each other and may be separate or one individual component(s). Also, several, if not all of the components, such as the operation software250may be included with the memory243. Each of the components within the devices shown may be linked together and may be in communication with each other for purposes suited to the present invention.

As mentioned above, the replica identification module255, association module257, and the repository module259may also be located in the cache245or other components. As such, one or more replica identification module255, association module257, and the repository module259maybe used as needed, based upon the storage architecture and users preferences.

The present invention may utilize the components ofFIG. 1andFIG. 2for replica identification and collision avoidance in the context of a file-system replication, as well as other file-system replication systems (not shown) architectures commonly known in the art. Each repository may distinguish other repository's data structures, files, and/or objects as compared to the repository's own generated data structures, files, and/or objects when a replication operation is performed to other repositories (in a grid environment). In one embodiment, a determination is made as to whether or not each replication is synchronized. The determination is performed without actually verifying the replica's data or structure, and does so without any probabilistic means, whilst remaining independent of the replication procedures, protocol and/or file-system layout, representation and implementation.

It should be noted that for purposes of the illustrated embodiments, a “grid” is defined as a set of repositories whose data entities can be replicated to every other repositories within the grid. A repository may be assigned at any given time to a single grid. Data may be streamed into a repository by way of replication from a remote source repository in the grid, or by any other supported way of receiving incoming data from local sources (e.g. a backup stream).

Second, a node identification (ID) may be associated with a node, which is a file-system object (e.g. directory, file, link etc.). In one embodiment, each newly created node within the file-system in the repository is assigned with an identification value (e.g., the node ID), which is unique in the grid. Such a global, unique file-system node ID is generated by combining unique identification values containing the grid, repository, and the node ID's.

The unique file-system node ID has special traits, which facilitate efficient replica identification in file-system replication. In one embodiment, the unique node ID is enhanced to achieve collision avoidance within the repository. The special traits are illustrated as follows. (1) The unique node ID is independent of the node's physical location in the file-system or the repository, thereby avoiding any constraints on the structure and layout of the file-system where the unique node ID resides. Moreover, the unique node ID is not affected by the data replication implementation. The data blocks composing the node and the data block's associated meta-data are transferred independently of the unique node ID. (2) The unique node ID values are never recycled. Hence the unique node ID generation and management are simple and the possibilities of stale node references are eliminated. (3) The node maintains its own unique node ID throughout its lifetime, from creation to deletion. The unique node ID does not change when the node's data or structure is modified.

In one embodiment, the file-system replication system maintains consistency and synchronization of structure and data by enforcing an ordering operation during a replication procedure. As such, the replication procedures reflect changes in file-system structure at the target repository in the order (or sequence) in which the changes and operations were carried-out in the source repository. Since the file-system replication system maintains an ordered replication of nodes between the source and target repositories, the existence of the unique node ID within a target repository implies that the node is synchronized in between the source and the target repositories.

By tagging each node in the file-system replication system with a unique node ID, together with the ordered replication of nodes between repositories, the file-system replication system achieves efficient synchronization and ensures absolute identity between the original and replication nodes in the source and target repositories (respectively). Moreover, the tagging preserves the traits described previously, and thus do not impair the efficiency, completeness, and/or independence of traits.

File-system replication systems allow for replicating multiple instances of the same node between a source and target repositories pair. For example, replicating the same file (e.g., /xxx/yyy/zzz/file) twice from repository S to repository D, but to different target directories—one instance to /dst1/xxx/yyy/zzz/file and another instance to /dst2/xxx/yyy/zzz/file—means that the unique node ID will not satisfy the local collision avoidance within repository D, as both instances will carry the same ID value “n”. The inability to avoid local collision will cause various file-system management problems, such as staling nodes due to deletion of one of the replica instances.

In one example, a unique association is defined and created for the replication of nodes between a source and target repository. The unique association links a node at the target repository with the originating node in the source, and thus the identification and synchronization is sustained. Moreover, the association between the replica node in the target repository with the originating node in the source repository allows for discrimination between multiple instances of the same node in a repository, as each instance belongs to a different and unique association. By assigning each association with a unique association identification (ID) value in the grid, the file-system replication system achieves collision avoidance. Such a unique association identification (ID) is again generated by combining unique identification values of the grid, repository, and the association. It should be noted that the collision avoidance issue does not occur in a regular creation of a node in a file-system local in the repository (e.g. backup of a new file). This is due to the fact that the local file-system uniquely allocates the node ID, and multiple instances of the same node are not created. Collision avoidance is achieved by the requirement to allocate a unique node ID before the creation of the node and the writing of the node's data blocks. On the other hand, in a global and inter-connected environment, the local repository's file-system does not necessarily control the node ID allocation (e.g. a node replication received from a different repository), and thus the newly created association is required.

Note that following the introduction of multiple associations; the mere existence of a node ID within the repository is not sufficient to ensure synchronization, as multiple node instances can exist in the multiple associations that are not sure to carry the same state. However, the existence of a node ID within an association does ensure each of the node instances are synchronized with the original node in the association.

Turning now toFIG. 3, a flowchart illustrating an exemplary method300for replica identification and collision avoidance in a file system replication. The method300may create a unique file-system node identification (ID) for each newly created node in a file system repository by combining a grid identification (ID), a repository identification (ID), and a node identification (ID) to form the unique file-system node identification (ID) (step304). The method300may associate the unique file-system node ID with a unique association identification (ID) for creating an association for linking the node from a source repository to a target repository when performing a replication operation in the file system repository (step306). In other words, the unique association ID allows for a separate and unique association between repositories (e.g., between source repositories and target repositories). Each node may have one or more unique associations. The different replication instances of the node in the target repository are distinguished by the unique association ID assigned to each of the replication instances.

The method300may distinguish different replication instances of the node in the file system repository by the unique association ID assigned to each of the replication instances (step308). It should be noted that each of the steps within method300may not be happening consecutively one after the other. In short, each of the steps listed above may act as separate, independent procedures, which happen in the system.

As mentioned earlier, each new file-system node created in a repository is assigned with an identification value that is unique in the grid. Such a unique grid identification (ID) is generated as follows. The unique grid identification (ID) is computed by incrementing the value of the grid ID variable maintained by a software entity, which facilitates generation of grids within the global environment.

A repository is created independently of the grids, and may be subsequently assigned to a grid, and further migrated between grids (at any given time a repository may be associated with a single grid). Upon assignment of the repository to a grid, the repository is assigned with the unique repository identification (ID) computed by incrementing the value of a repository ID variable maintained by a software entity, which corresponds to a grid and facilitates affiliation of repositories to that grid.

Turning toFIG. 4, a block diagram400illustrating an exemplary structure of unique file-system node identification is depicted. A node identification (ID)402is computed by incrementing the value of a node ID variable maintained by a software entity, which corresponds to a repository and facilitates allocation of nodes within that repository. A combination of the node ID402with the grid ID406and a repository ID404, is defined as a unique file-system node identification (ID)408(e.g., also shown by way of example only “fs-node-ID” meaning the unique file-system node identification) of a given node, and serves as the unique identifier of that node in the grid and/or file system. Combined together, the grid ID406, node ID402, and the repository ID404form the unique file-system node identification (ID)408.

An association is created within a repository between a source repository and a target repository, and may be subsequently linked with a replication policy, which defines the replication procedure or constraints in the source repository. In other words, an association is a link between a replication policy in a source repository and a single destination target repository of that replication policy. The replication policy will characterize the replication arriving from the source repository in which the policy was configured. The association is assigned with a unique association ID computed by incrementing the value of an association ID variable maintained by a software entity, which corresponds to a repository and facilitates affiliation of new associations to that repository. In one embodiment, by way of example, the association is assigned an fs-node-ID and the association is a directory within the target repository (i.e. an association directory and/or a replication target directory), which will contain the incoming replicated nodes. It should be noted that the replication target directory is one example illustrating a directory for the association within the target repository.

Upon linkage of an association to a replication policy in the source repository, each replicated node is transmitted with the accompanying association ID and thus the replication procedure can determine which replication target directory is to receive the replication node. The values of the fs-node-ID (the unique file-system node identification) and association ID components are never recycled. Therefore, each component representation is defined to be large enough to accommodate continuous processing of a defined time frame. The metadata of the relevant grid is maintained within each associated repository, so that communications may be handled by each repository independently of the software entities and metadata of the grid.

In one example, the following operations are performed for the allocation of an fs-node-ID. When a new file-system node, originating from a locally processed incoming stream of data, is allocated (e.g. a file or directory is created), a new fs-node-ID is also allocated and assigned to that node. However, when a node is received during a replication process, the nodes' fs-node-ID received from the source repository is preserved and used also in the target repository.

The fs-node-ID may also be recorded by performing the following operations. For a node received via a replication process, the fs-node-ID of the node is recorded as received. For a node received via local data processing within a repository, the fs-node-ID node is recorded in the repository such that the node's grid-ID and repository-ID components are set with “special” values. These special values may be predetermined. It should be noted that within a repository, the node-ID component enables unique identification of a node. Upon transmission of such a node to a target repository, the appropriate values of the grid-ID and repository-ID components are added to the node-ID component to form the full fs-node-ID value. This enables easier migration of repositories between grids, since no persistent node level data should be modified when a repository is migrated.

In one example the following operations are performed for allocation, linkage, and removal of an association ID. When a new association is created; a new id is also allocated and assigned to that association. When the association is linked to a single source repository's replication policy, the association ID of the association is recorded in the meta-data of that source repository replication policy. From this point in time, the replication procedure shall transmit the association ID with each replication of a node to the target repository, where the node's identification at the target repository is composed of the node's fs-node-ID (e.g., the unique file-system node identification value) and the node's association ID. Whenever the association is removed, the system may unlink the association ID from the source repository replication policy so as to disable any replication initiation generated from this policy related to the removed association.

The association may be a directory within a target repository receiving incoming replication of nodes. As such, the association has a directory fs-node-ID. However, when the directory is defined to be an association (e.g. a replication target directory), the association/directory is also assigned an association ID. Later, when a linkage occurs between a source repository replication policy and a replication target directory the association ID of that target directory is saved within the replication policy. Subsequent to saving the association ID within the replication policy, any replication process that occurs after the saving operation will transmit the replication target directory ID with each node replication.

Each fs-node-ID is used for identification of node recurrence in the replication processes, consequently saving bandwidth required for replication and storing the nodes in an efficient form (preserved from the source repository without further processing). Each association ID is used to discriminate multiple nodes within a repository after each association ID has been received by an incoming replication. Next, each of the replication processes, and any related processes of the replication, are illustrated below by focusing on the usage of the fs-node-ID and association ID to achieve the previously discussed requirements.

Turning now toFIG. 5, a flow chart diagram500illustrating an exemplary procedure for replication of a file-system node is illustrated. In one example, the method500for the replication of a file-system node is described as follows. In method500, a replication policy initiates the file-system node replication with the association ID of the target repository the association ID was assigned during the linkage procedure described previously (step502). The fs-node-ID and the association ID values of this node are transmitted to the target repository (step504). The target repository receives the fs-node-ID and the association ID values, and searches locally for existence of the fs-node-ID and the association ID values using an fs-node-ID and association ID indices (e.g. databases), and subsequently determines whether the fs-node-ID and the association ID values exist or not (step506). If the association ID does not exist in the target repository, then the replication procedure fails (step508). Otherwise, if the fs-node-ID exists in the target association (step5090, then the target repository signals the source repository that the node should not be replicated (step510) and as such, the procedure is completed with success and a notification may be sent for the success (step511). Terminal state to the procedure. If the fs-node-ID does not exist in the target association (step512), the source repository transmits the data and meta-data associated with the non existing node, in the form in which they are stored (e.g. compressed and/or deduplicated), to the target repository (step513). The (non-existing) node and the meta data is sent to the target repository (step514). The target repository stores the received (non-existing) node (data and possibly the structure) in the received node's form (preserved from the source repository) (step515) and records the fs-node-ID and association ID in the respective indices (step516). After the storing and recording operations, the target repository may send an acknowledgement (step518) to the source repository for indicating a success (step520).

In one embodiment, the following sub-procedure may be performed for recording the fs-node-ID's for a locally generated object. A new fs-node-ID is generated for a new node, and stored within the repository together with other relevant meta-data of the node (e.g. path and name). The grid-ID and repository-ID components are set to invalid within the fs-node-ID. The fs-node-ID is recorded in the repository as a mapping between the node path and name to the internal node (which represents the data storage of the file-system node).

In one embodiment, the following operations may be performed for storing a new node within a repository. A new (non-existing) node may be received via a replication process from other repositories or in the context of locally processed incoming data (e.g. file is created). Although fs-node-ID generation for a new node is different between these cases (as specified before), the data of a new node is stored the same in both cases. Generally, a logical storage segment is allocated to accommodate the meta-data of the node as well as its data blocks, and the new node is stored within the allocated storage segment. This logical storage segment may be physically located anywhere in the repository, depending on the repository's internal logic and optimizations. The replication method proposed, therefore, does not apply any constraints on the structure and layout of the target repositories relative to the source repository.