US 6,016,552 AGrant
Object Striping Focusing on Data Object
Issue Date:2000-01-18
•16 Claims
•15 Drawing Sheets
Abstract
A technique to stripe a data object that focuses on the data object, but not on the storage media storing the data object. The data object, which can be of any size, is striped into data units at the object level. The technique includes the steps of striping a part of the data object that has not been striped before into at least one data unit. Then, at least one redundant unit is generated from the immediately striped at least one data unit to produce a stripe. The above steps are repeated until the entire data object is striped. In one embodiment, the striping step further includes the steps of (1) identifying the size of the data object; (2) determining the striping size based on the size of the data object; (3) receiving at least a part of the data object, with the size of that part being at least equal to the striping size; (4) striping the received data object into one or more data unit based on the striping size; and (5) if the part of the data object that has not been striped before is to be striped into more than one data unit, then repeating from the step of receiving to generate the data units.
Metadata
Assignee
- The Chinese University of Hong Kong
Inventors
- Jack Y. B. Lee
- Po C. Wong
Application Information
Application Number:US 8708983
Filing Date:1997-06-06
Priority Date:1997-06-06
Art Unit:275
Classifications
IPC:
G06F 1100
Field of Search:
395326711707371714182.04;181;1801011420240.111;2;6
Patent Drawings (15 sheets)
Description
Background
The present invention relates generally to storing data to an array of storage media or servers, and more particularly to methods to stripe the data to store in the array of storage media or servers.
In our information age, it is common to use an array of storage media to hold information. The information can be represented as data objects, whose sizes can range from kilobytes to gigabytes. If a data object is stored in one storage medium, and if the demand on that data object is much higher than other objects, the loading on that storage medium becomes much higher than others. This creates load imbalance. One typical way to balance the load is to stripe the data object into data units, and to store the units into the storage media in a round-robin fashion. This is the storage approach behind typical disk arrays, and the approach has also been extended to server arrays. An extensive discussion of the extension can be found, for example, in an article, entitled, "A Server Array Approach for Video-on-demand Service on Local Area Networks," published in INFOCOM '96, on March 1996, by Lee and Wong. The article describes an array of servers accessed by a number of clients.
A typical disk array system has a few different configurations. When a user formats a disk array, one configuration is selected. From then onwards, the organization and the size of the data units are fixed, with the storage spaces at each disk drive divided into units of the fixed striping size. Fixing the organization implies fixing the storage location of the data units of the data objects. Not only are the locations for the storage of the data objects fixed, the locations for the storage of redundant units or symbols are also fixed.
Redundant symbols or units are stored for fault tolerance reasons. In case one or more of the storage media fail, with the right level of redundancy based on the redundant symbols, the lost data can be restored. In a disk array system, the locations or sectors holding the redundant units are also fixed.
This organization is applied to all types of data objects. After a data object is striped into the fixed striping size, typically the data units are stored in the media in a round-robin fashion, skipping locations for redundant units wherever they exist.
A commonly used term in the disk array system is a stripe, which is defined as a group of data units and one or more redundant units that are generated by the data units. A stripe unit can be a data unit or a redundant unit.
After the data units are stored in the media, values for the redundant units are calculated. This is done stripe by stripe across the storage media. The above described process to store data into storage media is known as storage striping.
FIG. 1 shows one way to stripe a data object using storage striping. Each box in FIG. 1 denotes a stripe unit, such as 150, which denotes a number of bytes of data, such as 64 Kilobytes. Each stripe unit may store one or more symbols. Each vertical column of stripe units denotes the units stored within one storage medium or one server; for example, the units 152 and 154 are in the medium 156. With five columns shown in FIG. 1, there are five storage media or servers. Each row of stripe units represent a stripe; for example, the units 158 and 160 are two units for the stripe 162. In this example, each stripe also includes a redundant unit, such as 161. The locations for the redundant units are fixed, such as the locations for the units 161 and 164. The data units are stored around the redundant units. The redundant unit within each stripe can be generated by performing the exclusive-or operation on all of the data units within the stripe. All data objects are striped the same way.
Typically, data objects are of different sizes. If the size of a data object is not an integral multiple of the size of a stripe unit, storage spaces will be wasted at the last storage unit. This is known as internal fragmentation, which increases overhead. One way to represent overheads is as follows:
FIG. 2 shows a graph of normalized storage overhead versus the size of a stripe unit in storage striping. One calculation to generate FIG. 2 is shown in Appendix A. As the size of a stripe unit increases, the normalized storage overhead increases correspondingly, and the relationship is approximately linear. Note that storage overhead becomes impractical if the size of a stripe unit is larger than a few tens of kilobytes. The graph also shows the effect of having redundancy in the system for fault tolerance. It directly increases storage overhead, as shown in FIG. 2, because redundant units need additional storage.
Another issue to consider in a disk array system is on retrieving a data object from the storage media. A retrieval request for a data object can generate multiple retrieval operations in the storage media. For example, if the data object occupies one megabyte and the size of a stripe unit is one kilobyte, then it takes one thousand operations to retrieve the data object.
To consider the retrieval issue, stripe units of a data object are assumed to pack using a minimum number of stripes. In other words, the stripe units of the data object are not spread among many stripes, but are concentrated in as few stripes as possible. From this assumption, an average number of retrieval per byte (ANR) is calculated against the size of a stripe unit. This average number of retrieval per byte is defined as the average number of retrieval required to get a byte if the striping unit size is known, and if the probabilities of retrieving object of any sizes are the same. Actually, the probability of retrieving objects of different sizes are different.
In one approximation, the probability of retrieving object of different sizes are assumed to follow the WebStone retrieval distribution. FIG. 3 shows the WebStone retrieval distribution for web servers. It plots the probability of retrieving an object having a certain size; for example, the probability of retrieving an object having the size of 500 bytes in a typical web server is 0.5. Based on the WebStone approximation, a weighted average number of retrieval per byte (WANR) is calculated against the size of striping units. FIG. 4 shows a graph of WANR against striping sizes for normal mode of operation, and for failure mode, where there is media or server failure. The plots are in the form of steps because the WebStone approximation only has five samples. One calculation to generate FIG. 4 is shown in Appendix B.
Referring back to FIG. 4, one can see that WANR increases rapidly for small stripe unit sizes (10 to 15 kilobytes). In order to have good retrieval performance, or to have low WANR, stripe unit sizes should be large, such as larger than 20 kilobytes. The figure also shows that for large stripe unit sizes (>20 kilobytes), failure mode requires significantly more retrieval. This is because using large striping sizes results in fewer stripes per data object, which in turn increases the significance of retrieving extra stripe units at the last stripe, when there is failure.
On overhead storage, one prefers low stripe unit size. However, on retrieval, one prefers high stripe unit size. FIG. 5 shows the tradeoff in storage striping between the two factors: weighted average number of retrieval per byte vs. normalized storage overhead. The figure shows the difficulty of achieving low overhead storage and high retrieval efficiency simultaneously based on storage striping.
The difficulty is not diminished when storage striping is applied to multimedia data objects, which can be of very different sizes--a HTML page of text may only occupy a few kilobytes, while a picture requires a few megabytes, and a compressed movie a gigabyte. If the size of the striping units is one kilobyte, accessing a movie will take tremendous number of retrieval. However, if the size of the striping units is one megabyte, a lot of space will be wasted to hold a page of text due to internal fragmentation.
It should be apparent that there is a need for a new method to stripe a data object to be stored in an array of storage media. The method should provide low overhead storage and high retrieval efficiency. Also, the method should be equally applicable to both an array of storage media and an array of servers.
Summary of the Invention
The present invention provides a method known as object striping. It stripes a data object at the object level, not at the storage level. In storage striping, the locations for the stripe units are fixed. In other words, the locations for the redundant units are pre-set, with the data units positioned around them. In object striping, the positions of the redundant units are not pre-set; they are formed with the data units as a logical unit before they are stored in the storage media. The invented results provide low overhead storage and high retrieval efficiency at the same time. In addition, the present invention is applicable to data objects with significantly different data object sizes. The method can be applied to an array of storage media or an array of servers.
Instead of focusing on the formatted configuration of the storage media, the present invention changes the paradigm and concentrates on the data objects. In the prior art storage striping technique, the storage media are at the focal point. Once the storage media have been formatted, all types of data objects will be striped the same way. The data object might be a gigabyte movie or a kilobyte page of text. Both will have the same striping size, and their data units will be positioned around the pre-set locations of the redundant units.
In the present invention, data objects are at the focal point, with the striping process substantially de-coupled from the storage media. The redundant units and the data units are treated as a logical unit. The striping process is performed at the data object, and then redundant units are calculated. Both the data units and the redundant units can be stored in the storage media in a round-robin fashion. In object striping, the locations of the redundant units are not pre-defined. Different objects with different sizes can be striped differently.
In one embodiment, the invented method stripes a part of the data object that has not been striped before into a number of data units. Then at least one redundant unit is generated based on the immediately striped data units to generate a stripe. The invented process is repeated until the entire data object is striped. Note that in the present invention, a stripe is defined as one or more data units combined with one or more redundant units such that the redundant units are generated by the one or more data units.
In striping, the invented method first identifies the size of the data object, and determines the striping size. Then at least a part of the data object whose size is at least equal to the striping size is received, and striped into a data unit. The data units and the generated redundant units can be transmitted to the storage media in a round-robin fashion.
In another embodiment, the stripe unit size also depends on a number of other factors, which include the number of storage media or servers, the level of redundancy, and a user-configurable minimum striping size and maximum striping size. Based on these additional factors, data objects are striped.
The present invention provides a number of advantages. For example, it provides better throughput than storage striping. In one example, object striping has 40% higher throughput than storage striping.
Other aspects and advantages of the present invention will become apparent from the following detailed description, which, when taken in conjunction with the accompanying drawings, illustrates by way of example the principles of the invention.
Brief Description of the Drawings
FIG. 1 shows one way to stripe a data object using storage striping techniques.
FIG. 2 shows a graph of normalized storage overhead versus the size of a stripe unit in storage striping.
FIG. 3 shows the WebStone retrieval distribution for web servers.
FIG. 4 shows a graph of weighted average number of retrieval per byte (WANR) against striping sizes in storage stripping.
FIG. 5 shows the tradeoff in storage striping between two factors: weighted average number of retrieval per byte vs. normalized storage overhead.
FIG. 6 shows an apparatus to implement the present invention.
FIG. 7 shows one set of steps to implement one embodiment of the present invention.
FIG. 8 depicts a number of factors determining the striping size of a data object.
FIG. 9 shows a set of steps to generate a redundant symbol.
FIGS. 10A-B show two examples of striping two data objects using the present invention.
FIG. 11 shows an example of re-constructing lost data when one server fails for object striping.
FIG. 12 is a graph on normalized storage overhead versus the user-defined minimum striping size Q.sub.min for object striping.
FIG. 13 plots the weighted average number of retrievals per byte versus the user-defined minimum striping size Q.sub.min for object striping.
FIG. 14 plots the weighted average number of retrievals per byte versus the normalized storage overhead for object striping and storage striping.
FIG. 15 shows embodiments of striping sizes in the present invention.
Same numerals in FIGS. 1-15 are assigned to similar elements in all the figures. Embodiments of the invention are discussed below with reference to FIGS. 1-15. However, those skilled in the art will readily appreciate that the detailed description given herein with respect to these figures is for explanatory purposes as the invention extends beyond these limited embodiments.
Detailed Description of the Invention
In the present description, the invented object striping techniques are applied to servers. Nevertheless, the techniques are equally applicable to storage media.
FIG. 6 shows an apparatus 200 to implement the present invention. The apparatus 200 includes a main storage medium 202, such as a compact disk read-only memory (CD ROM). The medium 202 stores data objects to be striped. A management processor 204, disposed between an array of servers and the main storage medium 202, performs the striping process. The processor can be a computer. Each server includes a storage medium, such as the server 206 has its storage medium 208. Based on object striping, the management processor 204 stripes data objects into striping units, which can then be stored in the storage media of the servers in a round-robin fashion.
FIG. 7 shows one set 250 of steps for the present invention to generate stripe units for a data object of any size. In the present invention, a stripe is defined as one or more data units and one or more redundant units such that the redundant units are generated by the data units. The stripe units, which can be data units or redundant units, are stored in the servers. First, a part of the data object that has not been striped before is striped (Step 262) into one or more data units. Then, at least one redundant unit is generated (Step 264) from the immediately striped data unit. The data units with the one or more redundant units generated together produce a stripe. The above steps are then repeated (Step 266) until the entire data object is striped.
In one embodiment, the striping process (Step 262) includes a number of steps. First, the processor 204 identifies (step 252) the size of the data object. This can be done in a number of ways. For example, the data object can have a header file storing its size. The processor 204 can retrieve the header file of the data object to identify the size of the data object. Using the size of the data object, the processor 204 determines (step 254) the striping size or the size of each striping unit for that data object. Then, the processor 204 receives (step 256) at least a part of the data object, with the size of that part being at least equal to the striping size. The received data object is striped (step 258) into a data unit based on the striping size. Steps 256 to 258 are repeated (Step 260) a number of times to generate a number of data units.
The data units and the redundant units are transmitted to the servers. This transmission step can be after the step of generating at least one redundant unit (Step 264). In another embodiment, the transmission and the receiving step can be performed simultaneously--while one unit is arriving, another is leaving. In yet another embodiment, a significant part of the data object is received before striping is done. In one other embodiment, transmission starts after the entire data object is striped (Step 266).
The striping size depends on a number of factors. As described, the striping size depends on the size of its corresponding data object. Unlike storage striping, in object striping, the striping size is not fixed just by the format of the storage media in the servers.
FIG. 8 shows other factors determining the striping size in one embodiment. They include the number of servers 300, the level of redundancy 302, a user-defined minimum striping size 304 and maximum striping size 306, and the minimum unit size that can be supported by the servers 308.
The level of redundancy denotes the number of redundant units per stripe. For example, a (15,11) RS-code or Reed-Solomon code includes 4 redundant symbols in every 15 symbols. The level of redundancy is 4. In other words, data lost due to the failing of 4 servers can be reconstructed by the 4 redundant symbols.
There are different ways to generate redundant symbols. For example, FIG. 9 shows a set 350 of steps to generate a redundant symbol. First, the processor 204 receives (step 352) and stripes (step 354) a data object. After generating a number of data units, the processor 204 generates (step 356) at least one redundant symbol, based on methods that should be obvious to those skilled in the art.
The user-defined minimum striping size sets the lower limit of the size of a striping unit. The striping size should not be smaller than the minimum striping size. One reason to set the lower limit is that if the striping size is too small, the number of retrieval from the servers to re-generate a data object from the stripe units may be too large.
The user-defined maximum striping size sets the upper limit of the size of a striping unit. The striping size should not be larger than the maximum striping size. One reason to set the upper limit is that if the striping size is too large, there might be load imbalance. A server might be accessed significantly more than others. Setting the upper limit balances the load in accessing the servers to re-generate data objects from stripe units.
The minimum unit size that can be supported by servers is typically set by the servers' storage media. A storage medium typically has a storage allocation unit, which is the minimum unit size that can be supported by the storage medium. All of the stripe unit sizes should be integral multiples of this storage allocation unit, where the multiple in this case can be one.
One set of programming steps that tie the different factors together to determine the striping size of a data object is shown in the following. In this application, this approach is known as Dynamic Object Striping (DOS), which implies that the striping size can be set dynamically.
Variable
Q.sub.max : maximum striping size
Q.sub.min : minimum striping size
k : level of redundancy
b : size of data object
U : storage allocation unit
N.sub.s : number of servers
q : the assigned stripe unit size.
Program
01. N.sub.D =N.sub.s -k
02. if (b.ltoreq.Q.sub.min)
03. then q=.left brkt-top.b/U.right brkt-top.U
04. else if (b.ltoreq.Q.sub.min N.sub.D)
05. then q=Q.sub.min
06. else if (b<Q.sub.max N.sub.D)
07. then q=.left brkt-top.b/(N.sub.D U).right brkt-top.U
08. else q=Q.sub.max
where .left brkt-top.x.right brkt-top. denotes the immediate integer larger than x, if x is not an integer; for example, .left brkt-top.12.5.right brkt-top.=13.
As one example, Q.sub.min can be set to be equal to the size of the storage allocation unit, and Q.sub.max can be set to be equal to the average object size of the different objects in the servers divided by the number of data units per stripe. Note that in the present invention, Q.sub.max is bigger than Q.sub.min, and Q.sub.max is also an integral multiple of the storage allocation unit size.
In the above programming steps, if Q.sub.min is set to be equal to Q.sub.max, all data objects will be striped using the same stripe size. In the present application, this approach is known as Fixed Object Striping (FOS), which is suitable for data objects of similar sizes.
Note that FOS is still different from storage striping. This is because striping is still focused on the data object, not the storage medium. A stripe contains stripe units from the same data object because a data stripe is mapped logically to storage units. For the same reason, a stripe can be shorter than the number of servers, depending on the size of the data object and stripe unit. Thus, when a server fails, only stripe units belonging to the data object need to be retrieved for lost data reconstruction.
FIGS. 10A-B show two examples of striping two data objects using different stripe size and redundancy. In the example 398 shown in FIG. 10A, the programming steps above determine that the striping size should be 4 storage allocation units. There are five servers, S1 to S5. Each server has four storage allocation units, such as the server 400 has the storage allocation units 402 and 404. With the striping size set to be 4, each server holds one striping unit, such as the striping unit 406. In the example 450 shown in FIG. 10B, the programming steps above determine that the striping size should be 2 storage allocation units. Each server carries four storage allocation units, which implies that each server carries two stripe units, such as the server 452 carries the stripe units 454 and 456.
As illustrated in FIGS. 10A-B, a stripe always contains stripe units from the same data object. This is because a stripe is mapped logically to servers. Accordingly, a stripe can be shorter than the number of servers depending on the size of the data object and stripe unit, as in FIG. 10B. Due to these properties, only stripe units belonging to the data object need to be retrieved for lost data reconstruction for both FOS and DOS.
FIG. 11 shows an example of re-constructing lost data when one server fails. In this example, each stripe unit size holds two storage allocation units. Some of the stripe units hold data objects, while other stripe units hold redundant symbols. In this example, a storage allocation unit represented by V.sub.i,j denotes holding data objects, and a unit represented by P.sub.i,j denotes holding redundant symbols.
Assume that the server 500 fails. Re-construction can be done at a number of places. In one embodiment, a client accesses the servers. After accessing the striping units 502, 504, 508, 510, 512, 514 and 518, the client reconstructs the striping units 506 and 516 in the failed server. The reconstruction can be done, for example, as follows:
where .sym. denotes the exclusive-or operation. As shown in equation (2), the allocation unit V.sub.2,2 is reconstructed by data from three servers only. In storage striping, to reconstruct loss data in a stripe, one retrieves all the stripe units from an entire stripe, which resides in each of the servers. However, in object striping, one only has to retrieve stripe units that belong to the data object.
Based on the same data set as in the storage striping example in the background, a number of results are calculated. First, consider internal fragmentation. FIG. 12 is a graph on normalized storage overhead NSO versus the user-defined minimum striping size Q.sub.min. Unlike storage striping, NSO does not increase linearly with respect to the minimum striping size. Instead, compared with storage striping, the NSO in object striping is relatively constant, and does not exceed 0.5. The slight increase is due to increase in redundancy overhead because internal fragmentation is independent of the stripe size. Also, object striping needs significantly less storage overhead for larger stripe sizes. One calculation to generate FIG. 12 is shown in Appendix C.
Another issue is retrieval efficiency. Based on the same WebStone retrieval distribution as in storage striping, FIG. 13 is generated. It plots the weighted average number of retrievals per byte (WANR) versus the user-defined minimum striping size Q.sub.min for object striping. As in storage striping, retrieval efficiency increases with larger Q.sub.min. One calculation to generate FIG. 13 is shown in Appendix D.
FIG. 14 plots the weighted average number of retrievals per byte versus the normalized storage overhead for object striping and storage striping. As shown in the figure, under the same storage overhead, object striping has significantly better retrieval efficiency than storage striping. Also, object striping has no performance degradation in retrieval efficiency when server fails. Another observation from the figure is that the improvement of DOS over FOS is significant only at small storage overhead constraints.
Finally, experimental results indicate that object striping has better throughput than storage striping. For example, with normalized storage overhead fixed at 0.3 and with eight servers, object striping at 730 kilobytes per second per server has more than 40% higher throughput than storage striping at 500 kilobytes per second per server.
In the present invention, symbols and units are used interchangeably. However, a unit can have more than one symbol.
From the foregoing it should be appreciated that object striping has significant better performance than storage striping. By focusing on the data object, object striping provides low overhead storage and high retrieval efficiency at the same time. The invented object striping technique can be applied to both an array of storage media and an array of servers.
Other embodiments of the invention will be apparent to those skilled in the art from a consideration of this specification or practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with the true scope and spirit of the invention being indicated by the following claims.
Appendix A
Given N.sub.s servers in the server array, k redundant units for redundancy, N.sub.D data units with N.sub.D being equal to N.sub.S -k, and data object of size b bytes, the amount of unused storage in the last stripe unit is given by
where mod(b,q) returns the remainder of b/q. Hence the total internal fragmentation for all N.sub.b data objects stored in the system is ##EQU1##
The total number of stripe units required to store all N.sub.b objects is ##EQU2##
Similarly, the minimum number of stripes required to hold all these stripe units is
Since k stripe units are reserved for redundancy in every stripe of N.sub.S stripe units, the total redundancy overhead is simply given by
To obtain the total storage overhead, the total internal fragmentation is summed with the total redundancy overhead. To ease comparison, a Normalized Storage Overhead (NSO) is defined as follows: ##EQU3##
Substituting into Equations 1-5, one gets ##EQU4##
For example, a NSO value of 0.5 means 50% more additional storage spaces (relative to total amount of data stored) are required due to internal fragmentation and redundancy overhead. Given a redundancy k, the lower bound for the NSO is derived. The minimum possible internal fragmentation should be zero, and for every N.sub.D bytes of data stored, k additional bytes are required for redundancy. Hence the lower bound for NSO is ##EQU5##
To obtain numerical evaluation, the data-set located at the following web server (http://adnetpc0.ie.cuhk.edu.hk/) was used as the b.sub.i 's. The following figure shows the data object size distribution of this data-set. This data-set has been compared with a number of other web site data-sets and it has been found that they have similar distributions. In subsequent numerical evaluations, the embodiment is assumed to be a 5-servers server array (N.sub.S =5) with redundancy of 1 (k=1). ##STR1## Data object size distribution of a web site data-set. Appendix B
For a data object of size b bytes and stripe unit size q bytes, the total number of retrievals required to retrieve the entire object during normal-mode operation (i.e. without server failure) is
Under failure mode, the number of transactions required depends on how the data object is stored and which server fails. To calculate the average number of retrievals required, each server is assumed to be equally likely to fail. For example, if stripe units of a data object are packed using a minimum number of stripes, then the least number of retrievals is needed. This should be the best-case scenario, and is assumed to be the situation for all stored data objects. Therefore for a data object of .left brkt-top.b/q.right brkt-top. stripe units, the stripe units will span .left brkt-top.b/(qN.sub.D).right brkt-top. stripes. The number of stripe units in the last stripe can be calculated from
To cater for the case where the last stripe has N.sub.D units, one is subtracted from the total number of stripe units before taking modulus and then one is added afterwards. Since all servers are equally likely to fail, the probability of having a failed unit in the last stripe, denoted as event E, is ##EQU6##
Hence conditioning on this event E, the expected number of retrievals required is:
Equations (1) and (5) give the expected number of retrievals for retrieving a data object of size b bytes under normal mode and single-server failure mode respectively. To characterize the practical performance of a system with various types of objects, the pattern that data are retrieved has to be considered. The probability of retrieving a data object of size B.sub.i bytes is assumed to be known and is denoted by P.sub.i, where ##EQU8##
Using this knowledge, a Weighted Average Number of Retrievals Per Byte (WANR) is defined to characterize the retrieval efficiency for normal and failure mode operations: ##EQU9##
Regardless of the striping scheme, at least one retrieval per data object is needed. Hence the lower bound for WANR is calculated as follows: ##EQU10##
Again, the retrieval distribution is needed to evaluate WANR numerically. In this respect, the WebStone retrieval distribution is used (shown in FIG. 3), which is generally considered typical in large and busy web sites. Note that there are only five samples in the WebStone distribution and as a result, steps exist in the resultant WANR evaluations.
Appendix C
In object striping, storage spaces are allocated in units of U bytes. Hence the internal fragmentation may be considered as the wasted storage at the last allocated storage unit for storing the data object:
Hence summing over all objects in the system gives the total internal fragmentation: ##EQU11##
To derive the redundancy overhead, two cases shown in the following figure are considered. If the last data stripe contains more than one complete stripe units (i.e. mod(b.sub.i, N.sub.D q.sub.i).gtoreq.q.sub.i, then kq.sub.i bytes of redundancy for the last data stripe are needed. However, if there are less than one complete stripe unit (i.e. mod(b.sub.i, N.sub.D q.sub.i)<q.sub.i), then partial redundancy units can be used. For all other data stripes, each requires k complete redundancy units. Hence the redundancy overhead is ##EQU12##
Summing over all data objects in the system gives the total redundancy overhead: ##EQU13##
Equations (2) and (4) are substituted into the Equation (6) in Appendix A to obtain the Normalized Storage Overhead of object striping. ##STR2## Two cases in calculating redundancy overhead for a data object. Appendix D
Given an object with size b bytes, the program in the detailed description will assign a stripe unit size. Since the assignment is a function of b, DSA(b) is used to denote the assigned stripe unit size. When there are no server failures, the total number of retrievals required to retrieve the object is
One distinct feature of object striping is that the number of retrievals required under failure mode is the same as that under normal mode. To see why, consider an arbitrary data stripe of x units and k redundancy units. At normal mode, only those x stripe units will be retrieved, ignoring the k redundancy units. Now when a server fails, either one of the x stripe units or one of the k redundancy units will become inaccessible. If the former is true one more redundancy unit has to be retrieved for data reconstruction, i.e. total (x-1)+1=x retrievals. If the latter is true then all data units are still accessible, hence requiring the same x retrievals. Therefore Equation (1) also gives the number of retrievals required under failure mode. Again the Equation (7) in Appendix B sets the definition of Weighted Average Number of Retrievals Per Byte. The retrieval efficiency of object striping (same under normal and failure mode) is characterized as: ##EQU14##
Using the same WebStone retrieval distribution as in storage striping, the WANR of object striping is plotted.
Claims
What is claimed is:
1. A method for generating stripe units in a stripe for a data object which can be of any size, wherein: a stripe is defined as having one or more data units and one or more redundant units with the redundant units being generated by the data units, a stripe unit can be a data unit or a redundant unit; and the stripe units are to be stored in a plurality of storage media; and the method comprising the steps of: striping a part of the data object that has not been striped before into at least one data unit; generating at least one redundant unit from the immediately striped at least one data unit to produce a stripe; and repeating from the step of striping until the entire data object is striped; wherein the step of striping further comprises the steps of: identifying the size of the data object: determining the striping size based on the size of the data object; receiving at least a part of the data object, with the size of that part being at least equal to the striping size; striping the received data object into a data unit based on the striping size; and if the part of the data object that has not been striped before is to be striped into more than one data unit, then repeating from the step of receiving to generate the data units.
2. A method as recited in claim 1 further comprising the step of storing the data units with the one or more redundant units after the step of generating, in a round-robin configuration into the storage media.
3. A method as recited in claim 1 wherein the striping size is equal to an integral multiple of a minimum unit size supported by the storage media.
4. A method as recited in claim 3 wherein: the multiple can be less than the number of units of storage media; and if a storage medium fails with its data lost, only stripe units belonging to the data object need to be retrieved to reconstruct the lost data.
5. A method as recited in claim 1 wherein the striping size depends on the number of units of storage media.
6. A method as recited in claim 1 wherein: for fault tolerance, the method includes a level of redundancy; and the striping size depends on the level of redundancy.
7. A method as recited in claim 1 wherein the striping size is no less than a minimum striping value so as to limit the number of retrievals from the storage media to re-generate the data object from the stripe units.
8. A method as recited in claim 1 wherein the striping size is no bigger than a maximum striping value so as to balance the load in accessing the storage media to re-generate the data object from the stripe units.
9. A method as recited in claim 1 wherein the storage media reside in a plurality of server computers.
10. A method as recited in claim 9 further comprising the step of storing the data units with the one or more redundant units after the step of generating, in a round-robin configuration into the storage media.
11. A method as recited in claim 10 wherein the striping size is equal to an integral multiple of a minimum unit size supported by the storage media.
12. A method as recited in claim 11 wherein: the multiple can be less than the number of units of storage media; and if a storage medium fails with its data lost, only stripe units belonging to the data object need to be retrieved to reconstruct the lost data.
13. A method as recited in claim 12 wherein the striping size depends on the number of units of storage media.
14. A method as recited in claim 13 wherein: for fault tolerance, the method includes a level of redundancy; and the striping size depends on the level of redundancy.
15. A method as recited in claim 14 wherein the striping size is no less than a minimum striping value so as to limit the number of retrieval from the storage media to re-generate the data object from the stripe units.
16. A method as recited in claim 15 wherein the striping size is no bigger than a maximum striping value so as to balance the load in accessing the storage media to re-generate the data object from the stripe units.
Patent Citations (11)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US4761785 | 1988-08-01 | Clark et al. | |
| US4993030 | 1991-02-01 | Krakauer et al. | |
| US5130992 | 1992-07-01 | Frey, Jr. et al. | |
| US5202799 | 1993-04-01 | Hetzler et al. | |
| US5522032 | 1996-05-01 | Franaszek et al. | |
| US5537567 | 1996-07-01 | Galbraith et al. | |
| US5574882 | 1996-11-01 | Menon et al. | |
| US5613059 | 1997-03-01 | Stallmo et al. | |
| US5623595 | 1997-04-01 | Bailey | |
| US5708769 | 1998-01-01 | Stallmo | |
| US5737549 | 1998-04-01 | Hersch et al. |
Non-Patent Literature (6)
- Tewari et al., "High Availability in Clustered Multimedia Servers", IEEE, Proceedings of the Twelfth Intl Confference on Data Engineering, pp. 645-654, Mar. 1996.
- Lee et al., "A Server Array Approach for Video-on-demand Service on Local Area Networks", IEEE, pp. 27-33, Mar. 1996.
- Vin et al., "Designing a Multiuser HDTV Storage Server", IEEE Journal on Selected Areas in Communications, vol. 11, No. 1, pp. 153-164, Jan. 1993.
- Birk, "Random RAIDs with Selective Exploitation of Redundancy for High Performance Video Servers", IEEE Proceedings of the IEEE 7th International Workshop on Netwrok and Operating System Support for Audio and Video, pp. 13-23, May 1997.
- Gemmell et al., "Multimedia Storage Servers: A Tutorial", Computer, vol. 28, Iss. 5, pp. 40-49, May 1995.
- Vin et al., "Efficient Failure Recovery in Multi-Disk Multimedia Servers", Twenty-Fifth International Symposium on Fault-Tolerant Computing, IEEE, pp. 12-21, Jun. 1995.