TECHNICAL FIELD

The present disclosure relates generally to the field of data storage, and more specifically, to data storage systems with built-in redundancy, methods of recovering data in data storage systems, and methods for storing data in data storage systems.

BACKGROUND

Several techniques are employed in storage systems to provide fault tolerance (namely, failure tolerance) to the storage systems. When a storage system fails (for example, due to failure of its components, software glitches, and the like), undesirable loss of data occurs. As failures in the storage systems are inevitable, advancements are being made to improve and further develop fault tolerance techniques for the storage systems.

Redundant array of independent disks (RAID) configurations have been popularly used in traditional storage systems. In an example, RAID configurations such as RAID 5 and RAID 6 are used to enable rebuild of lost data in case of one disk failure and two disk failures, respectively. In the RAID 5 and RAID 6 configurations, parity information is distributed amongst all disks. Notably, RAID 5 and RAID 6 require reading all data from all remaining disks in case of disk failure(s). As a result, rebuilding of lost data using RAID 5 or RAID 6 takes a considerable amount of time.

Practically any modern storage system supports RAID 6. However, as the modem storage systems have much larger storage capacities as compared to the traditional storage systems, the RAID configurations are not the most well-suited solution for the modem storage systems, as rebuild times for multi-terabyte modem storage systems could be of the order of several days. This technical problem associated with the RAID configurations limits its use in the modern storage systems. Nowadays, modem storage systems have also started to support modem codes for fault tolerance. These modern codes may or may not be minimum distance separable (MDS) codes. Moreover, the modem codes allow faster rebuild (namely, recovery) of data than the RAID configurations, but require much more storage than optimally needed. In other words, the modern codes are associated with a technical problem of impractically high storage requirements for fast data rebuild. As an example, zig-zag codes are modem codes that allow reading significantly less data in case of a single failure, while also being able to fix more than one disk failure. Unfortunately, the basic encoded unit in the zig-zag codes (and all other codes offering optimal recovery for all nodes) gets exponentially big, and thus they are not practical for systems with more than 10 disk drives.

Therefore, in light of the foregoing discussion, there exists a need to overcome the aforementioned drawbacks associated with existing technologies for rebuilding data in the event of failure of storage systems.

SUMMARY

The present disclosure seeks to provide data storage systems with built-in redundancy, computer-implemented methods of recovering data in data storage systems, and computer- implemented methods for storing data in data storage systems. The present disclosure seeks to provide a solution to the existing problems of long data rebuild times and impractically high storage requirements for fast data rebuild in modem storage systems. An aim of the present disclosure is to provide a solution that overcomes at least partially the problems encountered in prior art and provide a data storage system and methods that enable fast data rebuild with moderate and practically feasible storage requirements.

The object of the present disclosure is achieved by the solutions provided in the enclosed independent claims. Advantageous implementations of the present disclosure are further defined in the dependent claims.

In an aspect, the present disclosure provides a data storage system with built-in redundancy. The data storage system comprises n nodes, k of the n nodes being data nodes, and r of the n nodes being parity nodes, k, n and r being integers and n = k + r. The data storage system is a log based storage system in which data are stored as log entries, each log entry being distributed over all nodes with a sub-packetization of eight or lower. A first set comprises f of the k data nodes are designated fast recovery nodes, and a second set comprises the remaining data nodes. A first one of the parity nodes uses a parity that will enable recovery of a data subpacket whenever any single data node has failed. One or more additional parity nodes use a parity such that for the first set of data nodes, the first parity and the other parities can be used together to recover their data without reading all data from all the data nodes. The data storage system is arranged to store data belonging to logical units for which fast recovery is required in a data node in the first set.

The data storage system beneficially employs an unbalanced regenerating code to provide a redundancy scheme of the data storage system. For the k data nodes of the data storage system, data recovery in case of failure is faster for data nodes in the first set, as compared to data nodes in the second set. This fast data recovery for the data nodes in the first set can be attributed to the parities used by the first parity node and the one or more additional parity nodes, as said parities together facilitate recovery of the data of said data nodes without requiring reading of all data from all remaining nodes. The data storage system can be effectively utilized to store critical and/or important data in the data nodes of the first set, since fast data rebuild capabilities are provided for the data nodes of the first set. In other words, the data storage system enables provision of prioritized logical units with faster data recovery. Moreover, the data storage system can be practically implemented with nominal storage requirements to provide considerable redundancy.

In an implementation form, the first parity node uses XOR parity.

The first parity node is employed for computationally efficient reconstruction of any failed data node. The XOR parity is computationally simple to implement.

In an implementation form, the parity nodes 2, ... , r use a parity given by equation (1) where the index i + m — 1 is to be taken modulo r in the range 1, ..., r, and λ , μ _i are finite field coefficients to be chosen so as to satisfy the Maximum Distance Separable criterion, d _{x y} denotes the y-th subpacket in the x-th data node of the data storage system, and p _{m i} denotes the i-th subpacket in the m-th parity node of the data storage system. The parities for all the parity nodes satisfy the Maximum Distance Separable (MDS) criterion, thereby delivering optimal fault tolerance for the parity nodes. The parities for the parity nodes 2, . . . , r, in conjunction with the parity used by the first parity node, facilitate fast data recovery in case of failure of data nodes of the first set.

In an implementation form, the number of parity nodes is 2, the sub-packetization is 2 and the first parity node and the second parity node are defined by wherein c = X is a generator of a multiplicative group IF* and F = GF(2 ⁸ ) = F ₂ [X]/(X ⁸ + X ⁴ + X ³ + X ² + 1) is a finite field, β ∈ F is a finite field coefficient, and d _{x y} denotes the y- th subpacket in the x-th node of the data storage system.

The low sub-packetization (equal to 2) is beneficial in mitigating input/output overhead during recovery of data in the data storage system. Moreover, the aforesaid parities defined for the first parity node and the second parity node provide an efficient and reliable data reconstruction (namely, data rebuild) scheme that can be employed for fast recovery of data in case of failure of a data node belonging to the first set.

In an implementation form, f = r.

When the number data nodes in the first set equals the number of parity nodes, there is provided an implementation of the data storage system that provides a reasonable, reliable tradeoff between storage requirements for fast data recovery and storage requirements for provision of redundancy.

In an implementation form, n = 10, k = 8 and r = 2.

The data storage system having 10 nodes, out of which 8 nodes are data nodes and 2 nodes are parity nodes is practically implementable as it does not require an exorbitant amount of storage for allowing fast recovery of data. Such a data storage system has high data storage efficiency, is cost-efficient, is space-efficient, and is energy-efficient.

In an implementation form, r is 2 ^X , x being an integer between 1 and 3. Such a number of parity nodes provides a reasonable and practically implementable of redundancy in the data storage system.

In another aspect, the present disclosure provides a computer-implemented method of recovering data in a data storage system, wherein in case of a failure in one of the data nodes in the first set , data can be recovered by reading of the total amount of data.

By virtue of the aforesaid method of recovering data in the data storage system, only a fraction of the total amount of data is required to be read in order to recover from failure in one of the data nodes in the first set. As a result, extremely fast recovery of data is enabled for the data nodes in the first set.

In an implementation form, the steps of recovering include, for a failed node 1 ≤ j ≤ f, determining the unique value of 1 ≤ i ≤ r such that after the step of determining, reading the k symbols P _1,i , d _1,i ... , d _j-1,i + d _1j+1,i + ••• + d _k,i , to recover d _j,i . d _j,i = P _1,i + d _1,i + ••• + d _j-1,i + d _1j+1,i + ••• + d _k,i , after the step of reading the k symbols, reading, for every 2 ≤ m ≤ r, the [f/r] symbols

By virtue of the aforesaid steps of recovering, the data storage system efficiently recovers data belonging to the data nodes in the first set.

In an implementation form, the steps of recovering include, for a failed node 1 ≤ j ≤ [f/2], reading p _1,1 , d _1,1 , ... , d _j-1,1 , d _j+1,1 , ... , d _k,1 to recover d _{j, 1} and then additionally reading P2,1, d _{1 ,2} , ...d _{j -1,2} , d _{j +1,2} , ... , [f/2],2 to recover d _{j 2} , - for a failed node [f/2] + 1 ≤ j ≤ f, reading p _{1, 2} , d _{1, 2} , ...,d _j-1,2, d _j+1,2 , ... , d _k,2 to recover d _j,2 and then additionally reading p _{2 2} , d _[f/2]+1,1 , ...,d _j-1,1, d _j+1,1 , ... , d _f,1 to recover d _j,1 .

By virtue of the aforesaid steps of recovering, the data storage system efficiently recovers data belonging to the data nodes in the first set.

In another aspect, the present disclosure provides a computer-implemented method for storing data in the form of a log entry in a data storage system, comprising the steps of identifying one or more logical units in the data storage system according to a location of prioritized information within the log entry and writing the prioritized information associated with each such logical unit to a data node designated as a fast recovery node.

By virtue of the aforesaid steps for storing data, there is accurately enabled storage of prioritized information at specific logical units that belong to the data node designated as the fast recovery node.

In an implementation form, the computer-implemented method comprises the step of writing information associated with each logical unit not identified as comprising prioritized information to a data node that belongs to the second set.

By virtue of the aforesaid step for storing data, there is accurately enabled storage of the information associated with each logical unit not identified as comprising prioritized information, at specific logical units corresponding to the data node belonging to the second set.

In an implementation form, the present disclosure provides the computer program product for controlling the reading of and/or writing to a data storage system, comprising computer readable code means which when run in a control unit of the data storage system is arranged to cause the control unit to perform the aforesaid method.

The computer readable code means reads data from the data storage system in manner that data can be effectively recovered in case of failure of any data node. The computer readable code means enables faster recovery of data in case of failure of data nodes in the first set, as compared to recovery of data in case of failure of data nodes in the second set. Moreover, the computer readable code means facilitates storing data in the data storage system in a manner that information is selectively written to specific logical units, depending on which logical unit the information is to be written.

It has to be noted that all devices, elements, circuitry, units and means described in the present application could be implemented in the software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof. It will be appreciated that features of the present disclosure are susceptible to being combined in various combinations without departing from the scope of the present disclosure as defined by the appended claims.

Additional aspects, advantages, features and objects of the present disclosure would be made apparent from the drawings and the detailed description of the illustrative implementations construed in conjunction with the appended claims that follow.

BRIEF DESCRIPTION OF THE DRAWINGS

The summary above, as well as the following detailed description of illustrative embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the present disclosure, exemplary constructions of the disclosure are shown in the drawings. However, the present disclosure is not limited to specific methods and instrumentalities disclosed herein. Moreover, those in the art will understand that the drawings are not to scale. Wherever possible, like elements have been indicated by identical numbers.

Embodiments of the present disclosure will now be described, by way of example only, with reference to the following diagrams wherein:

FIG. 1 is a block diagram of a data storage system, in accordance with an embodiment of the present disclosure; FIG. 2 is a schematic illustration of a data storage system comprising 10 nodes, in accordance with an embodiment of the present disclosure;

FIG. 3 is an illustration of a structure of a log entry, in accordance with an embodiment of the present disclosure;

FIG. 4 illustrates a flowchart of a computer-implemented method for storing data in the form of a log entry in a data storage system, in accordance with an embodiment of the present disclosure; and

FIG. 5 illustrates a flowchart of a computer-implemented method of recovering data in a data storage system, in accordance with an embodiment of the present disclosure.

In the accompanying drawings, an underlined number is employed to represent an item over which the underlined number is positioned or an item to which the underlined number is adjacent. A non-underlined number relates to an item identified by a line linking the non- underlined number to the item. When a number is non-underlined and accompanied by an associated arrow, the non-underlined number is used to identify a general item at which the arrow is pointing.

DETAILED DESCRIPTION OF EMBODIMENTS

The following detailed description illustrates embodiments of the present disclosure and ways in which they can be implemented. Although some modes of carrying out the present disclosure have been disclosed, those skilled in the art would recognize that other embodiments for carrying out or practicing the present disclosure are also possible.

FIG. 1 is a block diagram of a data storage system, in accordance with an embodiment of the present disclosure. With reference to FIG. 1, there is shown a block diagram of a data storage system 100 with built-in redundancy. The data storage system 100 comprises n nodes 102, k of the n nodes 102 being data nodes (depicted as k data nodes 104) and r of the n nodes 102 being parity nodes (depicted as r parity nodes 106). Herein, k, n and r are integers and n=k+r. The data storage system 100 is a log-based storage system in which data are stored as log entries, each log entry being distributed over all nodes (i.e. the n nodes 102) with a sub-packetization of eight or lower. In the data storage system 100, a first set 108 comprises f of the k data nodes 104 that are designated fast recovery nodes, and a second set 110 comprises the remaining data nodes of the k data nodes 104. A first one of the parity nodes (i.e. the r parity nodes 106) uses a parity that will enable recovery of a data subpacket whenever any single data node has failed, and one or more additional parity nodes (from amongst the r parity nodes 106) uses a parity such that for the first set 108 of data nodes, the first parity and the other parities can be used together to recover their data without reading all data from all the data nodes (i.e. the k data nodes 104). The data storage system 100 is arranged to store data belonging to logical units for which fast recovery is required in a data node in the first set 108.

Throughout the present disclosure, the term "data storage system" refers to a storage system for storing data. The data storage system 100 has built-in redundancy. In the event of failure of a certain number (for example, less than or equal to r) of the n nodes 102, the data storage system 100 loses data, but is able to effectively recover from the failure by reliably rebuilding lost data using its built-in redundancy. Moreover, this built-in redundancy ensures that in the event of the failure, the data storage system 100 continues to effectively deliver data from the remaining working nodes. In an embodiment, redundancy within the data storage system 100 is concentrated on the r parity nodes 106 of the data storage system 100. The data storage system 100 employs an unbalanced regenerating code, which is a specialized erasure code, to provide a redundancy scheme of the data storage system 100. The unbalanced regenerating code is a (n,k) erasure code, wherein n is the total number of nodes in the data storage system 100 and k is the number of data nodes in the data storage system 100. The unbalanced regenerating code minimizes an amount of data that is required to be read in order to recover data of a failed node. As a result, repair bandwidth required for the data storage system 100 is also reduced.

In an embodiment, the data storage system 100 is capable of tolerating up to n-k node failures. In other words, the data storage system 100 is capable of tolerating up to r node failures.

In an embodiment, the data storage system 100 is implemented as a distributed storage system. Such a distributed storage system has a distributed infrastructure wherein data is stored on multiple storage devices. These multiple storage devices are optionally distributed across one or more data centres.

Throughout the present disclosure, the term "node" refers to a storage device. The n nodes 102 of the data storage system 100 are n storage devices (namely, n storage units) of the data storage system 100. In an embodiment, the n nodes 102 of the data storage system 100 are implemented as block storage devices. The block storage devices are data storage devices that support reading and optionally, writing data in fixed-size blocks. The fixed-size blocks can be understood to be "volumes" of the block storage devices. Optionally, a given block storage device is partitioned into one or more blocks.

Any given node of the data storage system 100 is either a data node or a parity node. Herein, the term "data node" refers to a storage device that is employed to store data, whereas the term "parity node" refers to a storage device that is employed to store parity data (namely, parity information) which is used to provide redundancy of the data stored in the data nodes. In an embodiment, each of the k data nodes 104 stores data subpackets, whereas each of the r parity nodes 106 stores parity subpackets. A given subpacket may be either a data subpacket or a parity subpacket, depending on which node it is stored at.

The number n of the n nodes 102 is a code length of the unbalanced regenerating code employed in the data storage system 100, whereas the number k of the k data nodes 104 is a code dimension of the unbalanced regenerating code.

In an embodiment, a given node of the data storage system 100 is implemented as at least one of a hard-disk drive (HDD), a solid-state drive (SDD), a physical server with one or more HDDs and/or SDDs, a virtual machine with access to one or more HDDs and/or SSDs. It will be appreciated that the aforesaid examples are non-exhaustive, and other types of storage devices may also be employed for implementing the given node of the data storage system 100.

In an example, the data storage system 100 may comprise 20 nodes, 16 of the 20 nodes being data nodes and 4 of the 20 nodes being parity nodes. In another example, the data storage system 100 may comprise 12 nodes, 9 of the 12 nodes being data nodes and 3 of the 13 nodes being parity nodes. It will be appreciated that the aforesaid examples are non-exhaustive, and the data storage system 100 may be implemented by employing other configurations of data nodes and parity nodes.

The data storage system 100 is a log-based storage system. The log-based storage system (namely, log- structured storage system or log- structured file system) is log of append-only sequence of log entries. In the log-based storage system, new data is written to end of the log by way of the log entries. Each log entry comprises data to be stored in the data storage system 100. The log-based storage system is associated with a metadata structure which describes where the data in the log exists. The metadata structure also has a log- structure and is written to either the log of the log-based storage system or to another metadata log. In an embodiment, when the n nodes 102 of the data storage system 100 are implemented as the block storage devices, the log includes writes to the one or more blocks (namely, volumes) of the block storage devices and the metadata structure includes addresses in the block where data was written to. It will be appreciated that the log entries are usually cached and written as one large write which works well even on spindles.

In an embodiment, each log entry in the data storage system 100 has a structure (i.e. a format) corresponding to the log-based storage system. The structure of the log entry is described in more detail in conjunction with FIG. 3.

Each log entry in the log-based storage system is distributed over the n nodes 102 with the sub- packetization of eight or lower. It will be appreciated that lower the sub-packetization, smaller the size of the log entries. Herein, the term "sub-packetization" refers to a number of subpackets into which a unit of data stored in the data storage system 100 is divided. Each unit of data optionally comprises one or more subpackets. Both the data stored in the k data nodes 104 and the parity data stored in the r parity nodes 106 are subject to sub-packetization. In an embodiment, when the n nodes 102 of the data storage system 100 are implemented as block storage devices, the unit of data is a block.

In an example, the sub-packetization may be equal to 2. In other words, each unit of data and parity data is divided into 2 data subpackets and 2 parity subpackets, respectively. In another example, the sub-packetization may be equal to 4. In other words, each unit of data and parity data is divided into 4 data subpackets and 4 parity subpackets, respectively.

It will be appreciated that the level of sub-packetization is indicative of a minimum dimension over which all operations pertaining to the data storage system 100 are performed.

In the data storage system 100, there exists the first set 108 comprising f of the k data nodes 104 that are designated as the fast recovery nodes. In other words, the first set 108 comprises the fast recovery nodes. The term "fast recovery nodes" refers to those nodes amongst the k data nodes 104 for which recovery from failure (i.e. data recovery or data rebuild) is faster as compared to remaining nodes amongst the k data nodes 104. The second set 110 comprises the remaining k-f data nodes of the k data nodes 104 that are not designated as the fast recovery nodes. The data nodes of the second set 110 may be understood to be "regular recovery nodes" . The fast recovery nodes belonging to the first set 108 have a better data reconstruction scheme than the remaining nodes belonging to the second set 110, as an amount of data accessed and transferred for reconstructing the data stored in the fast recovery nodes is lesser than that for reconstructing the data stored in the regular recovery nodes.

In an embodiment, the f data nodes of the first set 108 are selected by a user of the data storage system 100. In another embodiment, the f data nodes of the first set 108 are pre-selected in the data storage system 100.

In an embodiment, the number f of data nodes belonging to the first set 108 lies in a range of 1 to k. Mathematically, 1 ≤ f ≤ k. A minimum of 1 data node may be designated as the fast recovery node, while a maximum of k data nodes may be designated as the fast recovery nodes. The number f may be selected by the user or may be pre-selected in the data storage system 100

The first one of the parity nodes (i.e., the r parity nodes 106) uses a parity that enables efficient recovery of a data subpacket whenever any single data node (amongst the k data nodes 104) has failed. The parity used by the first one of the parity nodes enables optimal recovery of the data subpacket, in minimal time. The "first one of the parity nodes" is referred to as "first parity node", and the parity used by the first parity node is referred to as the "first parity" .

In an embodiment, the first parity node uses XOR parity. The Exclusive OR (XOR) parity enables computationally efficient reconstruction of any failed data node (amongst the k data nodes 104).

In an embodiment, the XOR parity used by the first parity node is given by the equation p _1,i = d _1,i + d _{2, i} +... + d _k , _i , wherein 1 ≤ i ≤ q, q denoting a total number of subpackets in a single data node and wherein p _1,i denotes the i-th subpacket in the first parity node of the data storage system 100. As an example, when q = 2, parity data for first parity subpacket in the first parity node is given as p _1,1 = d _1,1 + d _2,1 + ... + d _k,1 and parity data for second parity subpacket in the first parity node is given as p _1,2 = d _1,2 + d _2,2 + ... + d _k,2 . As another example, each of the n nodes 102 of the data storage system 100 may be partitioned into 3 blocks having sub- packetization equal to 2. In such a case, q is equal to 6, and parity data for 6 parity subpackets in the first parity node may be calculated as described above. In an embodiment, the parity nodes 2, ... , r use a parity given by equation (1) where the index i + m — 1 is to be taken modulo r in the range 1, ..., r, and λ, are finite field coefficients to be chosen so as to satisfy the Maximum Distance Separable criterion, d _x,y denotes the y-th subpacket in the x-th data node of the data storage system 100, and p _m,i denotes the i-th subpacket in the m-th parity node of the data storage system 100.

In this regard, when the finite field coefficients are chosen to satisfy the Maximum Distance Separable (MDS) criterion, data can be efficiently extracted from any k nodes out of the n nodes 102. The MDS criterion applies to all parity nodes 106 together as a whole. The parity given by equation (1) corresponds to the unbalanced regenerating code (employed by the data storage system 100) that is highly efficient in space compared to the number of failures it supports. Moreover, in such a case, the unbalanced regenerating code can be understood to be an MDS code, which enables fast data recovery and is also practical in terms of implementation.

It will be appreciated that the first parity used by the first parity node and the parities given by the equation (1) for the parity nodes 2, ..., r provides the unbalanced regenerating code that enables fast recovery for the data nodes of the first set 108. These parities are defined such that in the event of failure of any data node among the first set 108 of data nodes, accurate and efficient data recovery can be performed without requiring reading all data from all the k data nodes 104. For the data nodes of the second set 110, the unbalanced regenerating code requires full reading of all data from all the k data nodes 104 to achieve recovery. Therefore, the unbalanced regenerating code is unbalanced in terms of recovery time of data in case of failure of the data nodes (i.e. f fast recovery nodes have a lower recovery time than k-f regular recovery nodes).

It will be appreciated that defining the first parity and the other parities (for the one or more additional parity nodes) constitutes an encoding operation wherein the parity data of the r parity nodes 106 is computed from the data of the k data nodes 104.

Throughout the present disclosure, the term "logical unit" refers to a storage area in the data storage system 100, wherein each logical unit comprises one or more blocks. In an embodiment, the data storage system 100 comprises a plurality of logical units, wherein the plurality of logical units comprise logical units for which fast recovery is required and logical units for which fast recovery is not required. The plurality of logical units of the data storage system 100 can be understood to be divided into two groups, wherein logical units of different groups have different (i.e. unbalanced) recovery times. The "logical units for which fast recovery is required" may be understood to be "prioritized logical units", whereas the "logical units for which fast recovery is not required" may be understood to be "unprioritized logical units" .

The data storage system 100 is arranged to store data belonging to the prioritized logical units in a data node in the first set 108. This enables fast recovery of said data in case of failure of the data node on which it is stored. In this way, the prioritized logical units are defined within the data storage system 100 in a manner that the prioritized logical units have fast rebuild. It will be appreciated that precious, sensitive and/or critical data may belong to (i.e. be stored at) the prioritized logical units, as loss of such data for a long time period is undesirable. Moreover, data belonging to the unprioritized logical units is stored in a data node in the second set 110 or in a parity node. The "data belonging to the prioritized logical units" may be understood to be "prioritized data" or "prioritized information" . Likewise, "data belonging to the unprioritized logical units" may be understood to be "unprioritized data" or "unprioritized information" .

It will be appreciated that the unbalanced regenerating code employed by the data storage system 100 enables creation of the prioritized logical units in the data storage system 100. In an example, 25 percent of the k data nodes 104 of the data storage system 100 may be defined (namely, created) as the prioritized logical units, whereas 75 percent of the k data nodes 104 may be defined as the unprioritized logical units.

In an embodiment, a given logical unit is identified by a corresponding identifier. Optionally, the identifier is a logical unit number (LUN). The logical unit number is an identifier used for labelling and designating subsystems of nodes of the data storage system 100.

FIG. 2 is a schematic illustration of an exemplary data storage system comprising 10 nodes, in accordance with an embodiment of the present disclosure. With reference to FIG. 2, there is shown a data storage system 200 comprising 10 nodes (depicted as nodes 202, 204, 206, 208, 210, 212, 214, 216, 218, and 220). Notably, 8 of the 10 nodes are data nodes (depicted as the nodes 202, 204, 206, 208, 210, 212, 214, and 216) and 2 of the 10 nodes are parity nodes (depicted as the nodes 218 and 220). Herein, n, k, and r are integers wherein n equals 10, k equals 8 and r equals 2, and wherein n = k+r. Moreover, a first set 222 comprises 2 of the 8 data nodes 202-216, whereas a second set 224 comprises the remaining 6 data nodes of the 8 data nodes 202-216. In particular, the first set 222 comprises the data nodes 202 and 204, whereas the second set 224 comprises the data nodes 206, 208, 210, 212, 214, and 216. The data nodes 202 and 204 of the first set 222 are designated as fast recovery nodes. The first set 222 corresponds to prioritized logical units in the data storage system 200, whereas the second set 224 corresponds to unprioritized logical units in the data storage system 200.

In an exemplary scenario, when any or both of the fast recovery nodes 202 and 204 fails, data stored in the failed fast recovery node(s) can be recovered by reading only approximately 56 percent of data (with respect to Reed-Solomon (RS) code) in the remaining nodes which have not failed. However, in another exemplary scenario, when any other node(s) amongst regular recovery nodes 206, 208, 210, 212, 214, and 216 fail, data stored in the failed regular recovery node(s) can only be recovered by reading 100 percent of data (with respect to RS code) in the remaining nodes which have not failed.

In an embodiment, the parity node 218 is a first parity node and the parity node 220 is a second parity node.

In an embodiment (depicted, for example, in FIG. 2), the number of parity nodes 218 and 220 is 2, the sub-packetization is 2 and the first parity node 218 and the second parity node 220 are defined by wherein c = X is a generator of a multiplicative group IF* and F = GF(2 ⁸ ) = F ₂ [X]/(X ⁸ + X ⁴ + X ³ + X ² + 1) is a finite field, ∈ F is a finite field coefficient, and d _{x y} denotes the y- th subpacket in the x-th node of the data storage system 200.

In this regard, it is assumed that n ≤ 257 and f ≤ 62. Moreover, when coefficients of d _{x y} are generated in a manner that said coefficients satisfy the MDS criterion. The finite field has been referred above as Galois Field (GF). Moreover, here x lies in a range of 1 to k. In other words, d _{x y} denotes the y-th subpacket in the x-th data node of the data storage system 200. In such a case, β may, for example, be equal to c ¹⁷⁸ . Alternatively, β may have any other suitable value, but for other values of β the maximum allowed value for f (such that the MDS criterion is still satisfied) will be lower. Taking β = 1 is the most computationally efficient, and in this case we have the constraint f ≤ 21.

In an example, the first parity node 218 and the second parity node 220 may be defined by: wherein p _1,1 and p _1,2 correspond to the first parity node 218 and p _2,1 and p _2,2 correspond to the second parity node 220.

In an embodiment, r is 2 ^X , x being an integer between 1 and 3. As an example, x may be equal to 1, and therefore, r may be equal to 2. Such an example is illustrated in FIG. 2. As another example, x may be equal to 2, and therefore, r may be equal to 4. As yet another example, x may be equal to 3, and therefore, r may be equal to 8. Such a number r of parity nodes provides a reasonable and practically implementable amount of redundancy in the data storage system 100, 200

Optionally, the value of x is determined based on the number k (of data nodes). Notably, the value of x directly depends on the number k, as a higher number of parity nodes would be required to store parity data of a higher number of data nodes. It will be appreciated that fewer the number of parity nodes, lesser are storage requirements in the data storage system 100, 200 for storing parity data.

In an embodiment (depicted, for example, in FIG. 2), f = r. In other words, the number f of data nodes designated as fast recovery nodes equals the number r of parity nodes. In the data storage system 200, f equals 2 (as the data nodes 202 and 204 of the first set 222 are designated as fast recovery nodes) and r also equals 2 (as the nodes 218 and 220 are parity nodes). When the number data nodes 202 and 204 in the first set 222 equals the number of parity nodes 218 and 220, there is provided an implementation of the data storage system 200 that provides a reasonable, reliable tradeoff between storage requirements for fast data recovery and storage requirements for provision of redundancy.

In another embodiment f is not equal to r. Optionally, f is lesser than r. It will be appreciated that when f is less than or equal to r, recovery speed for the fast recovery nodes is as fast as possible (i.e. it meets theoretical bounds). Alternatively, optionally, f is greater than r. In such a case, recovery speed for the fast recovery nodes decreases with an increase in the number f. As an example, f may be equal to 1, whereas r may be equal to 2. As another example, f may be equal to 4, whereas r may be equal to 3.

In an embodiment (depicted, for example, in FIG. 2), n = 10, k = 8 and r = 2. In other words, the data storage system 100, 200 comprises a total of 10 nodes, wherein 8 nodes (i.e. the nodes 202, 204, 206, 208, 210, 212, 214, and 216) are data nodes and 2 nodes (i.e. the nodes 218 and 220) are parity nodes. Such a data storage system 100, 200 is practically implementable (as it does not require an exorbitant amount of storage for allowing fast recovery of data), has high data storage efficiency, is cost-efficient, is space-efficient, and is energy-efficient.

It will be appreciated that the values of n, k, r and f are exemplary, and other values of these variables may be employed as required.

FIG. 3 is an illustration of a structure of a log entry, in accordance with an embodiment of the present disclosure. With reference to FIG. 3, there is shown a log entry 300 having three portions 300 A, 300B and 300C. The portion 300 A comprises prioritized information, the portion 300B comprises unprioritized information, and the portion 300C comprises parity information.

In an embodiment, the structure of the log entry 300 is fixed. In other words, an arrangement (namely, an ordering) of the three portions 300A, 300B and 300C in the log entry 300 is fixed. The prioritized information belonging to the logical units for which fast recovery is required is arranged in the portion 300A, as that area of the log entry 300 corresponds to the fast recovery nodes. The unprioritized information belonging to the logical units for which fast recovery is not required is arranged in the portion 300B, as that area of the log entry 300 corresponds to the regular recovery nodes. The parity information is arranged in the portion 300C, as that area of the log entry 300 corresponds to the parity nodes. In this way, the prioritized information, the unprioritized information, and the parity information is ordered to lie in a requisite location (within the log entry 300) corresponding to their logical units. It will be appreciated that a fixed structure of the log entry 300 enables in proper balancing of the prioritized information, the unprioritized information, and the parity information with respect to their corresponding logical units. In the absence of such balance, the prioritized information may, for example, get inaccurately written to logical units corresponding to the unprioritized information, and vice versa. Such inaccuracies in writing information to the data storage system 100, 200 would undesirably defeat the purpose of fast data recovery in the data storage system 100, 200. Therefore, the fixed structure of the log entry 300 orders the information to be written to the data storage system 100, 200 in a systematic manner to facilitate accurate and faster writes to the data storage system 100, 200, and to facilitate optimal fast recovery of the prioritized information from the data storage system 100, 200 when required.

It will be appreciated that when the sub-packetization in the data storage system 100, 200 is low, a size of the log entry 300 is also low. As an example, when sub-packetization equal to 2 is employed in the data storage system 200, there would be a total number of 20 subpackets in the log entry 300. These 20 subpackets include 16 data subpackets to be written to 8 data nodes 202-216, and 4 parity subpackets to be written to 2 parity nodes 218 and 220). If size of each subpacket is 64 kilobytes, the size of the log entry 300 is 1280 kilobytes (as 20*64 kilobytes equals 1280 kilobytes), which is very small. Moreover, 4 data subpackets written to 2 specific data nodes 202 and 204 (of the first set 222) designated as the fast recovery nodes can be recovered faster than other data subpackets on other data nodes 206-216.

Notably, the unbalanced regenerating code employed by the data storage system 100, 200 enables the size of the log entry 300 to be much smaller than log entries corresponding to modern codes such as zig-zag codes. For example, the log entries corresponding to the zig-zag codes include over 1000 subpackets, meaning that a size of such log entries is at least 50 times larger than the size of the log entry 300. The number of subpackets required by the zig-zag code becomes exponentially higher if more data nodes and more parity nodes are required, hence quickly becoming unfeasible in terms of practical implementation.

In an embodiment, a size of a given packet (i.e. a data packet and/or a parity packet) is equal to at least a size of the unit of data stored in the data storage system 100, 200. The size of the given packet is given by multiplying a size of a given subpacket (i.e. a given data subpacket and/or a given parity subpacket) with a value of the sub-packetization. When the unit of data is a block, the size of the given packet is equal to at least a size of the block. However, the size of the given packet is usually larger than the size of the block to allow efficient reading of data even from spindle storage.

FIG. 4 illustrates a flowchart of a computer-implemented method for storing data in the form of a log entry in a data storage system, in accordance with an embodiment of the present disclosure. With reference to FIG. 4, there is shown a flowchart of a computer-implemented method 400 for storing data in the form of a log entry (such as the log entry 300 of FIG. 3) in a data storage system (such as the data storage system 100, 200). The method 400 includes steps 402, 404, and 406

At step 402, one or more logical units are identified in the data storage system 100, 200 according to a location of prioritized information within the log entry 300. In an embodiment, the one or more logical units to which the prioritized information belongs are identified to correspond to the location of the prioritized information within the log entry 300.

At step 404, the prioritized information associated with each such logical unit (i.e. each logical unit identified in step 402) is written to a data node designated as a fast recovery node. In other words, the prioritized information is stored (in the form of data subpackets) at the data node designated as the fast recovery node. Such one or more logical units (i.e. one or more prioritized logical units) are defined in the data node designated as the fast recovery node.

At step 406, information associated with each logical unit not identified as comprising prioritized information is written to a data node that belongs to the second set 110, 224. Each logical unit not identified as comprising prioritized information corresponds to an unprioritized logical unit that is defined on the data node (for example, any of the data nodes 206-216) that belongs to the second set 110, 224. In an embodiment, each logical unit not identified as comprising prioritized information is identified based on a location of unprioritized information within the log entry 300. Moreover, each logical unit not identified as comprising prioritized information can be understood to belong to unprioritized logical units.

The steps 402 to 406 are only illustrative and other alternatives can also be provided where one or more steps are added, one or more steps are removed, or one or more steps are provided in a different sequence without departing from the scope of the claims herein.

In an embodiment, the method 400 further comprises the step of writing parity information to one or more logical units defined on parity nodes (i.e. the parity nodes 106, 218-220) of the data storage system 100, 200. The one or more logical units defined on parity nodes are identified based on a location of parity information within the log entry 300. Moreover, one or more logical units defined on parity nodes can be understood to belong to unprioritized logical units.

Pursuant to embodiments of the method 400, the data storage system 100, 200 employs data striping. In other words, data (or information) to be written to the data storage system 100, 200 is segmented into a plurality of packets, wherein consecutive packets are written to different nodes of the data storage system 100, 200. Data striping beneficially supports fast reads from the data storage system 100, 200, as multiple packets spread across the different nodes of the data storage system 100, 200 can be read concurrently. Data striping increases data throughput of the data storage system 100, 200.

In an embodiment, a given data stripe comprises h packets, wherein h is a multiple of n. In such a case, data is written at once to all n nodes 102, 202-220 of the data storage system 100, 200 by way of the given data stripe. The given stripe includes the data (i.e. the prioritized information, the unprioritized information and the parity information) and the unbalanced regenerating code. This allows recovery in case of failure of one or more nodes, depending on said code. It will be appreciated that typically, there is an alignment between a length of the given data stripe and an amount of data written to the n nodes 102, 202-220 at once.

In an embodiment, the log entry 300 corresponds to a single data stripe. In another embodiment, the log entry 300 corresponds to a plurality of data stripes. In an example, a given data storage system (such as the data storage system 100) may comprise three nodes, wherein two of the three nodes are data nodes and one of the three nodes is a parity node. Each of the three nodes may be implemented as a block storage device having a single block. Each of the three nodes may have 64 kilobytes of storage space. In such a case, a data stripe employed to write data to the given data storage system may have a total size of 192 kilobytes, wherein 128 kilobytes corresponds to two packets (one packet each to be stored in the single blocks of the two data nodes) and 64 kilobytes corresponds to one packet (to be stored in the single block of the one parity node). A log entry corresponding to such a data stripe would also have the size of 192 kilobytes.

FIG. 5 illustrates a flowchart of a computer-implemented method of recovering data in a data storage system, in accordance with an embodiment of the present disclosure. With reference to ≤IG. 5, there is shown a flowchart of a computer-implemented method 500 of recovering data in a data storage system (such as the data storage system 100, 200). At step 502, it is determined whether or not a failure has occurred in a data node belonging to a first set (i.e. the first set 108, 222). of data nodes (i.e. the data nodes 202, 204). When it is determined that the failure has occurred in the data node belonging to the first set 108, 222 of data nodes, step 504 is performed. Alternatively, step 506 is performed. At step 504, a fraction of all data from all data nodes 104, 202-216 is read, for recovery of data of the failed data node. At step 506, all data from all data nodes 104, 202-216 is read, for recovery of data of the failed data node.

The steps 502 to 506 are only illustrative and other alternatives can also be provided where one or more steps are added, one or more steps are removed, or one or more steps are provided in a different sequence without departing from the scope of the claims herein.

In the method 500, wherein in case of a failure in one of the data nodes in the first set f (i.e. the first set 108, 222), data can be recovered by reading - + — I- 1 of the total amount of data. Notably, when a given fast recovery node fails, the parities of the r parity nodes are used together to recover the lost data of the given fast recovery node in a time-efficient manner by reading only a fraction of data from all remaining functional data nodes. The step of reading only the fraction of data from all remaining functional data nodes to recover the lost data of the given fast recovery node corresponds to the step 504 of the method 500. As an example, when n=10, k=8, r=2 and f=2, in case of the failure in one of the nodes designated as fast recovery nodes, the recovery requires 56.25 percent of the total amount of data to be read (as (1/2) + {(2- l)/(2*8)}* (2/2) equals 0.5625).

It will be appreciated that the data nodes 202, 204 in the first set 108, 222 have much faster rate of data recovery (or data rebuild) as compared to data nodes 206-216 in the second set 110, 224

In an embodiment, the data storage system 100, 200 is the data storage system 100, 200, and the steps of recovering include, for a failed node 1 ≤ j ≤ f,

- determining the unique value of 1 ≤ i ≤ r such that

- after the step of determining, reading the k symbols p _1,i , d _1,i , ... , d _j+1,i , ... , d _k,i to recover d _j,i : d _j,i = p _1,i + d _1,i + ••• + d _{j -1,i} + d _j+1,i + ••• + d _k,i after the step of reading the k symbols, reading, for every 2 ≤ m ≤ r, the [f /r] symbols p _m,i , d _{[(i-1)f/r]+1 ,i+m,-1, ...,} d _{[(if/r),i+m- 1)} to recover d _j,i+m-1 : d _{j,i +m-1 =} μ _m-1 (p _m,i +λ _m,1 d _1,i +λ _{m, 2} d _2,i + _... +λ _m,k d _k,i + d _{[(i-1)f/r]+1 ,i+m,-1} + ...+d _{j-1 ,i +m -1} + ...+ d _{[(if/r),i+m- 1)} -

5 In an embodiment, the step 504 of the method 500 comprises the aforesaid steps of recovering data for a failed node belonging to the first set 108, 222 of data nodes 202, 204. Optionally, when recovering data for a failed node belonging to the first set 108, 222 of data nodes 202, 204, a total of k+(r-l)[f/r] symbols are accessed to recover the data for the failed node 1 ≤ j < f • Here, [f/r] As an example, in the data storage system

10 100, n = 1100,, kk = 8, r = 2 and f = 2. Then, in case of failure in any one of the data nodes designated as fast recovery nodes, a total of 9 symbols are accessed to recover lost data.

In an embodiment, the data storage system 100, 200 is the data storage system 100, 200, and the steps of recovering include, for a failed node 1 ≤ j ≤ [f/2], reading p _1,1 , d _1,1 ,... , d _j _ _1,1 , d _j+1,1 , ... , d _k,1 to recover

15 d _j,1 and then additionally reading p _2,1 , d _1,2 , ...,d _j-1,2 ,d _j+1,2 ,...,d _[f/2],2 to recover d _j,2 for a failed node [f/2] + 1 ≤ j ≤ f, reading p _1,2 , d _1,2 , .... dj_ _1,2 , dj _+1,2 , .... d _{k 2} to recover d _j,2 and then additionally reading p _2,2 , d[f/2] _+1,1 , ... , d _j _ _1,1 , d _j+1,1 , ... , d _f,1 to recover d _j,1

In this regard, in recovering the data of the failed node 1 ≤ j ≤ [f /2], a total of k + [f/2]

20 symbols are accessed. Likewise, in recovering the data of the failed node [f/2] + 1 ≤ j ≤ f, a total of k + [f /2] symbols are accessed. These steps of recovering pertain to the case when the data storage system 100, 200 includes 2 parity nodes, and the sub-packetization is 2. It will be appreciated that the f data nodes 202, 204 of the first set 108, 222 have a better reconstruction scheme in terms of the amount of data accessed (and transferred) as compared to the remaining

25 k-f data nodes 206-216 of the second set 110, 224.

Pursuant to an embodiment, there is provided a computer program product for controlling the reading of and/or writing to a data storage system (i.e. the data storage system 100, 200),

22 comprising computer readable code means which when run in a control unit of the data storage system 100, 200 is arranged to cause the control unit to perform the methods 400 and 500. The control unit is implemented as a hardware, software, firmware or a combination of these. The control unit is capable of controlling the reading of and/or writing to the n nodes 102, 202-220 of the data storage system 100, 200. Herein, the term "computer readable code means" refers to the unbalanced regenerating code described earlier.

Modifications to embodiments of the present disclosure described in the foregoing are possible without departing from the scope of the present disclosure as defined by the accompanying claims. Expressions such as "including", "comprising", "incorporating", "have", "is" used to describe and claim the present disclosure are intended to be construed in a non-exclusive manner, namely allowing for items, components or elements not explicitly described also to be present. Reference to the singular is also to be construed to relate to the plural. The word "exemplary" is used herein to mean "serving as an example, instance or illustration". Any embodiment described as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments. The word "optionally" is used herein to mean "is provided in some embodiments and not provided in other embodiments". It is appreciated that certain features of the present disclosure, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable combination or as suitable in any other described embodiment of the disclosure.