JP2859960B2 - Data storage device and method - Google Patents

Description

Description: TECHNICAL BACKGROUND OF THE INVENTION The present invention relates to mass data storage elements. In particular, the present invention relates to a set of physical mass storage devices that collectively execute as one or more logical mass storage devices. Further, the invention relates to improving flexibility, transaction / bandwidth efficiency, speed, and reliability of these sets of physical mass storage elements.

It is known that multiple mass data storage elements are operated as a single logical mass data storage element. Such devices consist of disk drives or other mass data storage technologies, including tape and other technologies. When a set of such elements are operated collectively as logic elements, the data stored in the write operation is propagated tolerant with one or more members of the combination.

One of the advantages of such a combination is that data is stored or retrieved quickly, which means that data is written to or read from all physical elements or in parallel from physical elements. It is. Another advantage of such a combination is that it is more tolerant of physical failure. For example, if one physical element fails, it is still possible to read and write other members of the combination.
In addition, storing redundant information in combinations can increase the probability that data stored on a failed physical element can be recovered. The redundant information is in the form of mirror or shadow data,
Data stored in any element of the combination is copied to the other element of the combination. Also, the amount of redundant information stored in the combination can be reduced by storing what is commonly referred to as test data. Such test data typically consists of a codeword constructed by encoding the data stored in the combination. Reconstruction of the data stored on the failed device is achieved by mathematical extraction of the missing data from the codeword.

Another advantage of using multiple physical elements as logic elements is that the ratio of read / write heads per unit of mass storage is increased. As a result of having a greater density of such actuators, each of which can access data individually, it is possible for the logic element to simultaneously process a greater number of required data. This is advantageous in applications such as databases and on-line transaction processing that require a high rate of aggregate requests / second rate.

The use of multiple physical elements in parallel, depending on the configuration, can provide a likely bandwidth of such a combination, eg, a large number of data that can be written or read simultaneously. High bandwidth is advantageous for applications such as real-time analysis, numerical analysis and image processing. A known technique for providing high bandwidth in such a combination of elements is to store data by interleaving data blocks that intersect the elements of the combination, which block is implemented in a round-robin fashion through the combination. Is stored sequentially. This is also known as striping data.

However, while the combination of physical mass storage elements has the potential for the advantages described above, among other things, known techniques for organizing and backing up data in such combinations may require different applications. There is no flexibility in taking full advantage of these advantages. The full range of data organization possible in such a combination of elements is not utilized. In other words, a mass storage device created from a plurality of physical storage elements
Two currently running applications with different data storage needs, for example, one application requiring large data transfer (high bandwidth) and the other application requiring high frequency transfer (high Operation range) is required to operate as a logical storage element. A third application requires equipment to provide both high bandwidth and high operating range. Known operating techniques for combinations of physical elements provide the ability to dynamically compose a single combination of physical elements to provide optimal service in response to such variable needs. I can't.

Accordingly, it would be desirable to be able to provide a mass storage device made from a plurality of physical storage elements that can flexibly provide both high bandwidth and high operating range with the required high reliability.

SUMMARY OF THE INVENTION The purpose of this invention is to provide the required high reliability,
It is an object of the present invention to provide a mass storage device made of a plurality of physical storage elements that can flexibly provide both a high bandwidth and a high operation range.

According to the present invention, a large capacity comprising a number of physically large data storage elements operatively interconnected to function at a first logic level as one or more logically redundant groups. A data storage device is provided. The width, depth and type of redundancy (e.g., mirror image data or inspection data) of each logically redundant group, and the location of the redundant information therein, are independent of the desired capacity and reliability requirements. Can be built. At a second logical level, blocks of mass storage data are grouped into one or more logical data groups. Logically redundant groups are divided into one or more of such data groups. The width, depth, addressing sequence and arrangement of data blocks in each logical data group can be independently constructed to divide them into large data areas with potentially different bandwidth and operating range characteristics It is.

A third logical level is also provided for interacting with the application software of the host computer operating system. Application levels are logically grouped into data groups for output to application software as a single logical storage unit to allow for data groups, single or combination from one or more redundant groups. Add a business application unit. A method of operating such a device is further provided.

BRIEF DESCRIPTION OF THE DRAWINGS The above and other objects and advantages of the present invention will be apparent in light of the following detailed description, taken in conjunction with the accompanying drawings, wherein like reference numerals designate like parts.

FIG. 1 is a schematic connection diagram of a set of disk drives in detection data distributed during driving of a combination according to the prior art.

FIG. 2 is a schematic diagram of a mass storage system suitable for use in the present invention.

FIG. 3 is a schematic connection diagram for distributing data to the surface of the magnetic disk.

FIG. 4 is a schematic connection diagram for distributing data as a first preferred embodiment of a redundant group according to the present invention.

FIG. 5 is a schematic connection diagram for distributing data as a second particularly preferred embodiment of a redundant group according to the present invention.

FIG. 6 is a connection diagram illustrating a method of configuring a memory space of a combination of elements according to the principles of the present invention.

FIG. 7 is a schematic diagram of an exemplary embodiment of a data structure for mapping between logical levels of the present invention.

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a set of physical mass data storage elements that are dynamically constructed as one or more logical mass storage elements. According to the present invention,
Such a set of physical elements is constructed as one or more redundant groups, and each redundant group is constructed as one or more data groups.

A redundant group, conventionally used as a known combination of elements, is a group of physical elements that are all shared with similar redundant element combinations. Redundant elements are used if one or more physical elements of the group are accidental.
An element that stores copy data or inspection data for the purpose of recovering stored data.

With the test data, the designation of a special physical element as a redundant element for the entire redundant group allows the redundant element to be accessed for all write operations involving any of the other physical elements in the group. To be done. Thus, every write operation to a group interferes with the other one, which is the same for small data accesses involving less than all data storage elements.

By distributing the test data through the formation of a redundant group, i.e. a logically redundant element consisting of parts of some or all elements of the redundant group,
It is known to avoid such contention problems on write operations. For example, FIG. 1 shows a group of thirteen disk storage elements. The columns are denoted by variable disks D1-D13, and the rows are denoted by different sectors S1-S5 on the disk. Sectors containing inspection data are indicated by hatching. Sector S1 of disk D13 includes inspection data for sector S1 of disks D1-D12. Similarly, the remaining hatched sectors contain inspection data for their respective sector rows. Thus, if the data is written to sector S4 of disk 7, the update check data is written to sector S4 of disk D10. This is achieved by reading the old test data, re-encoding it using the new data, and writing the new test data to the disk. This operation is indicated as read-modify-write. Similarly, if the data is written to sector S1 of disk D11, the test data is written to sector S1 of disk D13. For writing, in such a selection of four disks, there is no overlap, so both read-modify-write operations can be performed in parallel.

The distribution of test data in redundant groups in the manner shown in FIG. 1 is known as the construction of striped test data. The term “redundant striped group” is generally used herein to refer to a redundant group of test data arranged in a striped configuration as shown in FIG. 1, and the term “redundant group” The "stripe depth of" is used to refer to the stripe depth of each test data in such a striped redundant group.

It is known to obtain all combinations as a single redundant group in previously known combinations of elements.
A redundant group may be defined as a depth portion of each redundant group, and may be divided into variable "extents", each of which may have a different construction of test data from that of other extents in a similar redundant group. Was found. Further, one or more redundant groups may be obtained under the control of a single "array controller" and in a single element combination connected to the main processing unit via one or more element controllers. Was found.

Similarly, in previously known combinations of elements, a single redundant group included only one data group for application data, for example, a combination of elements operated as a single logical element. However, it has been found that the redundant groups can be broken down into separate data groups, each as a separate logical storage element or as part of a larger logical storage element. The data group may include all available mass storage memory on a single physical element (eg, all memory on the element available for storing application data), or It can include all available mass storage memory on multiple physical elements in a redundant group. In addition, as described more fully below, a data group can include several physical elements, but instead of including all available mass storage memory of each element, use of each element It may include only parts of the possible mass storage memory. In addition, it has been found that it is possible to allow groups of data from different redundant groups to the form of a single logic element. This is achieved by being redundant and overlaying additional logical layers above the data groups, as described more fully.

Furthermore, in the known combination of elements in which application data is interleaved across the elements of the combination, the organization or geometry of the data is of a very simple form. Such a combination usually cannot allow for a different logical organization of the application data in the same logical unit, and may not allow for a dynamic mapping of the logical organization of the application data in the logical unit. It has been found that the organization of data in data groups can be dynamically constructed in various ways. In particular,
Importantly, the data stripe depth of the data group is created independently of the redundant group stripe depth, and for applications with different data storage requirements, to obtain optimal efficiency characteristics, It has been found that one data group in a logical unit can be variable from another data group.

An example of a mass storage system 200 including two parallel arrays 201 and 202 is shown in the block diagram of FIG. As shown in FIG. 2, each parallel array 201 and 202 comprises:
13 physical elements 203-215 and parallel array controller
Includes 216. Parallel array controller 216 includes a microprocessor 216a that controls how data is written to and verified on the drives of the parallel array. The microprocessor 216a also controls the updating or reproduction of data when one of the physical elements malfunctions or becomes out of sync with the other physical elements in the parallel array. For the present invention, the microprocessor 216a in each parallel array controller also controls the division of the parallel arrays 201 and 202 into redundant groups, data groups and application units. Redundant groups, data groups and application units are initially established by the system operator when the parallel array is equipped, and may be established at a time prior to use during the tea ceremony time of the parallel array. The build is defined by the following more detailed description, preferably in the program memory of the microprocessor 216a, on each physical drive of the parallel array, creating a variable address map to define the secure build parameters used. Is achieved by

Each parallel array 201 and 202 is connected to a pair of element controllers 218 and 220. Each element controller:
It is sequentially connected to the CPU main memory by a bus or channel 222. Generally, each parallel array is connected to at least two element controllers, and at least two CPUs from one or more CPU main memories to the parallel array.
There are two parallel paths. Thus, for example, each parallel array 201 and 202 is connected to element controllers 218 and 220 by buses 224 and 226. Thus, the CPU
The parallel data path from the to the parallel array can be used as routing data around a busy or failed device controller.

Disk drive unit 203 as each parallel array
There is a drive set consisting of −214 and a backup set consisting of the disk drive unit 215. The parallel array controllers are the same as the element controllers 218 and 2
Send data between 20 and a particular one of disk drive units 203-215 or the like. Element controllers 218 and 220 interface with parallel arrays 201 and 202 to the main memory of one or more CPUs and can respond to processing I / O requests from applications driven by these CPUs It is.

To understand how to deploy data within the variable physical drives of the drive set 230 of the parallel arrays 201 and 202, it is necessary to understand the geometry of a single drive. FIG. 3 shows one aspect of the simplest type of disk drive, a single platter drive. Some disk drives in personal computers are of this type, with a single disk-type "platter" capable of storing data on both sides. In many hybrid drives, there are several platters on one "spindle" with a central post around the platter spin.

As shown in FIG. 3, each surface 300 of the disk platter
It is divided into a plurality of geometrical angles 301, and eight divisions are shown in FIG. 3, but other numbers of divisions may be used. surface
The 300 is also divided into a plurality of ring-shaped "tracks" of substantially equal width, with seven tracks shown in FIG. The intersection of the track and the geometric angle is
Known as a sector, and is typically the most basic unit of storage in a disk drive system. FIG. 3 shows 56 sectors 303.

Several faces of disk platter on one spindle
A collection of equal radius tracks 302 on 300 forms a "cylinder". Thus, a single platter duplex drive has two cylinders with height = 2 and has as many cylinders as tracks 302 on one side 300. For a two platter drive, the cylinder height would be four. For a single platter drive on one side, the cylinder height is one.

The disk drive performs reading and writing by a “read / write head” that moves on the surface of the side surface 300. FIG. 4 shows the distribution of data sub-units, ie, sectors, tracks and cylinders, within a group of eight single platters, two-sided drivers 400-407 in a more preferred manner as shown in the present invention. It is. Drives 400-407 correspond, for example, to drive units 203-210 of parallel array 201 or 202. Each small horizontal split is displayed in sector 408. For each drive, four cylinders 409-412 consist of two tracks 41
Each cylinder containing 3 and 414, each track containing 5 sectors is shown.

In the preferred embodiment shown in FIG.
Consists of a single redundant group as two types of redundant data, referred to as "P" test data and "Q" test data used to make the data redundant. The P and Q test data determines the Reed-Solomon coding algorithm applied to the mass storage data stored as redundant groups. The particular redundancy method used is by convention and not part of the present invention. As shown, redundant data is distributed across all spindles, or physical drives, of group 416, which form two logical test drives for the redundant group of groups 416. For example, the P and Q test data for the data in sector 408 of cylinder 409 of drives 400-405 are stored in cylinder 40 of drives 406 and 407.
9 Separately included. Each time data is stored in drive 400-
Any sector in any one of 405 cylinders 409
Writes to 408 and read-modify-write operations are performed on the P and Q test data contained in opposite sectors of drives 406 and 407 to update the redundant data.

Similarly, cylinders 410 of drives 400-407 share the P and Q inspection data contained in cylinders 410 of drives 404 and 405, and cylinders 411 of drives 400-407.
Is the P included in the cylinder 411 of the drives 402 and 403
And Q test data, and drives 400-407
Cylinder 412 of drive 400 and 401
Share the P and Q test data contained in.

Three data groups D1-D3 are shown in FIG. Data group D1 includes cylinders 409 of spindles 400 and 401.
including. Data group D2 includes cylinders 409 of each spindle 402,403. Data group D3 contains P and Q
Spindle 40 excluding these cylinders including inspection data
Includes all remaining cylinders 0-407. Data group D1
Has two spindle bandwidths and data group D2
Has four spindle bandwidths, and data group D3 has six spindle bandwidths. Thus, in accordance with the principles of the present invention, it is shown in FIG. 4 that a redundant group consists of several data groups of different bandwidths. In addition, each data group D1-D3 alone or in combination with one or more other data groups constitutes a separate logical storage device. This can be achieved by defining combinations as each data group or individual application unit. Application units are described in more detail below.

In FIG. 4, sectors 408 are numbered for each data group as a sequence of logical data blocks. This sequence is defined when the data group is built and can be arranged in various ways. FIG. 4 shows an associated simple arrangement where the sectors in each data group are numbered from left to right in stripes that intersect the width of the individual data groups, where each data stripe is a single sector of data. Have a width. Such an arrangement allows a maximum parallel transfer rate of consecutively numbered sectors for a given bandwidth of each data group.

The term "data group stripe depth", as described herein, refers to a logically contiguous data sector stored on a drive at the boundary of a single stripe of data in a data group to provide a data group. Used as a number. In accordance with the principles of the present invention, the stripe depth of the data group is smaller, greater, or equal to the stripe depth of the redundant group. As one example of this, FIG. 4 shows data groups D1-D3 each having a data group stripe depth of one sector, and a redundant group having a stripe depth of one cylinder redundant group. It is included in everything.

Redundant group 416 processes six data read requests simultaneously, one from each spindle 400-405. This is because the read / write heads of the spindle move individually to the other. Redundant groups 416, such as those constructed in FIG. 4, can also simultaneously process certain combinations of write requests. For example, in many requests for data sectors of data group D1, spindle 40 that cannot be backed up by P and Q test data on spindles 400, 401, 406 or 407
Data can be written simultaneously with the data sector of data group D3 including 2-405.

Redundant group 416 as constructed in FIG.
Generally cannot simultaneously process write operations on sectors in data groups D1 and D2. However, the reason for performing a write operation on any of these data groups is that it is necessary to suitably write to drives 406 and 407. Only write operations may be performed on the test data of drives 406, 407 at any time. Similarly, independent of the distribution of data groups, backed up by inspection data on similar drives 2
Write operations to two data sectors cannot be simultaneous. A request to the read / write head for more test data than at a point in time can be referred to as a "mismatch."

The limitation on writing simultaneously to different data drives sharing the common test drive described above is that the drive system is specially tested and is not a limitation of the present invention. For example, limitations can be avoided by implementing the invention using redundant groups of mirror images, which redundant groups do not have the property that different data drives have in common with redundant data on similar drives.

FIG. 5 shows a redundant group 416 constructed according to the present invention.
2 shows a particularly preferred embodiment of the present invention. In FIG.
As in FIG. 4, the logic test "drive" is deployed in all of the spindles 400-407 on a cylinder basis, but could be on a track basis or on a sector basis.

Data groups D1 and D2 are constructed as in FIG. The sectors of data group D3 in FIG. 4 are, however, divided into four data groups D4-D7. As shown in FIG. 5, the sequence of the sectors in the data groups D4-D7 includes the data groups D1 and D2.
Not a single-sector-depth stripe of Data group D4 has a data group stripe depth of 20 sectors, equal to the depth of the data group itself. Thus, in data group D4, logically numbered sectors 0-19 comprise a single spindle 40
Accessing only 0 allows continuous reading, thereby allowing the read / write head of spindles 401-407 to process other transactions. Data groups D5, D6, and D7 show examples of different intermediate data group stripe depths for five sectors, two sectors, and four sectors, respectively.

The distribution of inspection data on the variable spindle is chosen in such a way to minimize discrepancies. further,
Give unique distribution and parallel array controller 216
For the scope of selecting the command of the gas operation, the command may be selected to minimize the mismatch.

The distribution of redundant groups and data groups on the drive sets 230 of the parallel arrays 201 and 202 can be parameterized. For example, redundant groups include redundant group width (at the spindle), an indication of the number of spindles spanned by a particular combination of inspection data, redundant group depth (submitted, sector, track or cylinder) and Redundant group stripe depth (also submitted, sector, track or cylinder)
It is characterized by A data group is characterized by a width (at the spindle), a depth (submitted, sector, track or cylinder) and a stripe depth of the data group (also submitted, sector, track or cylinder). Because the data group does not start only at the start of the drive set 230, it is characterized by a "basis" which, when the data group starts, makes two parameters, spindle and offset, from the start of the spindle. Redundant groups are
Like a data group, less than all of the entire spindle is included. In addition, as described above, the redundant group is divided into a plurality of ranges. Redundant group ranges have equal widths and different bases and depths. For each range, the distribution of test data therein is individually parameterized. In a preferred embodiment, the extent of each redundant group is determined by the stripe depth of each redundant group in the extent of the redundant group and the drive position of the P and Q test data for such a redundant group of stripes. As such, it has additional internal parameters.

The width of the redundant group reflects an exchange between reliability and capacity. If the width of the redundant group is large, a large capacity is available, so a drive consisting of only two but a large number is passed through the remaining drives for data and used as test data. Is done.
On the other hand, if the width of the redundant group is = 4, the situation ends mirrorically or shaded, and 50
Percentage of the test data as being present (but mirroring, if the collection of two drives other than the four failures, all of their data is lost, the two drivers Used to play in situations). Such low redundancy group widths exhibit great reliability, but low capacity per unit cost, while high redundancy group widths exhibit high capacity per low cost unit, However, the reliability is relatively high.

The width of the data group reflects the exchange between the bandwidth and the requested rate as described above. That is, the width of the high data group reflects on the high bandwidth, and the width of the low data group reflects on the high required rate.

The data group stripe depth also reflects the exchange between bandwidth and required rate. Such an exchange is variable depending on the relationship between the data group and the average size of the I / O request with respect to the data stripe depth in the data group. The relationship of the average I / O request size to the stripe depth of the data group determines how often the I / O request for the data group spans more than one read / write head in the data group,
It also determines bandwidth and requested rate. The large ratio is a result similar to the span of multiple data drives in I / O requests, where such requested data is accessed with high bandwidth if the data is located all over one drive. Is done. If, on the other hand, a high request rate is promoted, the data group stripe depth will be less than the I / O to data group stripe depth.
It is preferably selected such that the ratio of the required sizes is small. A small ratio results in the likelihood that the I / O requests will be spanned more than one data drive, and such an increase in prospects will result in multiple I / O requests for data groups being processed simultaneously. Selling.

The change in the average size of the I / O request can be counted in selecting the stripe depth of the data group. For example, given the average I / O request size, the stripe depth of the data group required to achieve the desired request rate increases with increasing changes in I / O request size.

In accordance with the present invention, a mass storage device comprising a plurality of physical mass storage elements is referred to herein as an application unit, and groups data groups from one or from different redundant groups into a common logical unit. Is further enhanced. Such an application unit appears to the application software of the operating system as a single logical mass storage unit combining the different operating characteristics of the variable data groups. Further, the use of such application units allows for data groups and redundant groups to be constructed as desired by individual system operators of the particular storage architecture expected by the application software. . These additional levels of logical grouping are:
Similar to the logical level of redundant groups and data groups, controlled by the parallel array controller 216.

FIG. 6 shows an example of how application units, data groups, and redundant groups are mapped to drive sets, such as parallel arrays 201 or 202, during parallel array initialization. .

First a linear graph of the logical unit address space
For 600, this graph displays the parallel array's mass data storage memory as it appears to the CPU operating system application software. In the particular embodiment of FIG. 6, the parallel array is constructed to provide a logical unit address space consisting of two application (logical) units (LUN0 and LUN1). Logical unit
LUN0 is constructed to include 20 addressable logical blocks with logical block numbers LBN0-LBN19. As shown in FIG. 6, logical unit LUN0 also includes an unmapped logical address space 602 reserved for dynamic construction. The dynamic construction means can request that the application software of the CPU change from its initial construction to a parallel array construction during the operating time of the parallel array. In the embodiment of FIG. 6, the unmapped spaces 602 and 604 are each logical unit LUN0 to allow a data group to be added to each logical unit without a request to remove any logical unit from the line. And LUN1 are individually reserved. Such dynamic construction features
It can be implemented by providing a message service to the CPU application to request a configuration change. For mass storage system 200, the message service is provided by, for example, element controllers 218 and 220.
Can be processed. Logical unit LUN1 includes a plurality of addressable logical blocks LBN0-LBN179 and LBN200-LBN239. Logical blocks LBN180-LBN199 are reserved for dynamic construction and are not available to application software during the initial construction of a parallel array, as shown in FIG.

The mass storage address space of logical unit LUN0 is:
As shown by the data group address space chart 606, it consists of a single data group D1. Data group D1 contains 20 logical continuous data blocks 0-19.
, And correspond one-to-one with the logical block numbers LBN0-LBN19. Logical unit LUN
1 includes two data groups D2 and D3 and consists of 40 data block numbers 0-39, corresponding to logical block LBN200-LBN239 of logical unit LUN1 and data block numbers 0-179 of 180, and logical unit LUN1 Logical blocks LBN0-LBN179. As shown in the embodiment of FIG. 6, the logical blocks of a logical unit may be mapped as desired to data blocks of one or more groups of data in various ways. The data group address space 606 also includes additional data groups (D4) and (D5) reserved for dynamic construction. These data groups are formatted on the disk drives of the parallel array, either during initialization of the parallel array or during operation time, but are available to application software during the initial configuration of the parallel array. is not.

The redundant group construction of the parallel array is a two-dimensional address space consisting of the entire memory space of the parallel array.
Indicated by 608. Address space 608 contains 12 drives in drive set 230 and 1 drive in backup set 232.
Thirteen physical drives in the parallel array are displayed, including one spare drive. In FIG. 6, the drives in the drive set are individually numbered 0-11 to reflect their logical position in the parallel array. As indicated by the redundant group address space 608, the parallel array is built as one redundant group RG0 with three deployments A, B and C. As shown, the width of each deployment is equal to the entire width of the drive set 230 from the 12 logical drive locations or other perspectives of the redundant group RG0.

Deployment A of redundant group RG0 includes sectors 1-5 of drives 0-11. Thus, deployment A of redundant group RG0 has a width of 12 spindles and a deployment depth of 5 sectors. In the embodiment of FIG.
Provided as a memory space for a diagnostic program coupled with the mass storage system 200. Such a diagnostic program constructs the memory space of the deployment A in a number of ways by executing a specific diagnostic operation.
The diagnostic program may generate other parts of the deployment to be reconstructed, for example, at the boundaries of deployment A containing application data and test data.

Deployment B of redundant group RG0 contains all application data stored on the parallel array. In particular, in the embodiment of FIG. 6, deployment B is a data group D1, D2 constructed as shown in FIG. 4, like the additional memory space reserved for data groups (D4) and (D5).
And D3, and an area 609 of memory space that is not mapped to either logical unit LUN0 or LUN1. This area 609 is mapped, for example, to another logical unit (eg, LUN2) used by another application.

Address space 608 also includes a third deployment C in which the second diagnostic area is located. However, a parallel array is shown to include only a single redundant group RG0, and a parallel array has more than one redundant group,
Split alternately. For example, as shown in FIGS. 4 and 5 and such that a second redundant group is provided for logical drive locations 8-11.
Limit the width of eight spindles, including seven.

The entire width of the parallel array need not be included in redundant group RG0. As an example, FIG. 6 shows that the upper and lower redundant groups RG0 are portions 610 and 611 of the memory space that do not include the redundant groups. In the embodiment of FIG. 6, portions 610 and 611 are:
Includes a data structure that reflects the construction of the parallel array. These data structures are described in more detail below in relation to FIG. In addition, portions of the memory space between array deployments A, B and C, such as those indicated by regions D and E in FIG.
Excluded from 0.

FIG. 6 further provides a graph 612 showing a linear representation of the physical address space of the drive at logical location 0. Graph 612 shows a cross-sectional view of the address space chart along line 0'-0 "and further illustrates the relationship of the variable logic levels of the present invention as an example in the exemplary parallel array construction of FIG.

As mentioned above, a parallel array may be initially constructed by an operator during installation time and / or operation of the parallel array. The operator formats and builds the application units to be used according to the initially determined capacity, efficiency and redundancy requirements for each unit. These considerations are as described above herein. capacity,
Once the efficiency and redundancy requirements are defined, the logical organization of the unit can be specified by the defining parameters for each logical layer (redundant group layer, data group layer and application unit layer). These parameters provide a construction utility program that is executed by the processor 216a of the parallel array controller 216. The configuration utility manages a memory-resident database of configuration information for the parallel arrays. Preferably, a copy of this database information is maintained in non-volatile memory to prevent information being lost in the event of a power supply failure affecting the parallel array. The format utility program executed by processor 216a makes use of the information in this database, such as input parameters of where to format the physical drives of the parallel array as directed by the operator.

The basic parameters are preferably defined by a construction database that includes:

1) For each redundancy group Type: mirror image; 2 inspection drives; 1 inspection drive;

Width: The number of logical drive positions as spindles in the redundancy group.

Deployment Size: For each deployment in the redundancy group, the size (depth) of the deployment in sectors.

Deployment Base: For each deployment in the redundancy group, the physical layer address of the first sector in the deployment.

Stripe depth: for interleaved test drive groups
The depth, in sectors, of the stripe of inspection data.

Drive: Identification of the physical drives included in the redundancy group.

Name: Each redundancy group with a name that uniquely intersects mass storage system 200.

2) For each data group Base: First in data group with redundancy group
Index (logical drive number) of the drive position in the redundancy group that is the drive position of.

Width: Number of drive locations (logical drives) in the data group. This is the number of sectors that cross the address space of the data group.

Start: An offset in a sector with the expansion of the redundancy group above the logical drive location where the data group rectangle is identified by the base parameter.

Depth: In a redundancy group expansion, the number of sectors in the vertical column of the data group. Both depth and width are shown in FIG.
-6 are the dimensions of the sides and square tops formed by each data group as shown in FIG.

Redundancy group: The name of the redundancy group that belongs to the data group.

Deployment number: Name and number that identifies the deployment where the data group is located.

Index: A construction utility that assigns a number to each data group, unique in the redundancy group. This number is used for the format utility and in the run time to identify the end of the data group.

Stripe Depth: The depth, in sectors, of logically contiguous blocks of data in each stripe of data in a data group.

3) For each application unit Size: Sector size List of data groups: List of data groups in unit address space and base unit logical address of each data group, and their sizes and instructions. Each group is
It is identified therein and in the index by the name of the redundancy group.

FIG. 7 shows an exemplary data structure including the above-described parameters that may be used in the implementation of a construction database for a combination of elements such as parallel arrays 201 or 202. These data structures may be as variable as desired to adapt the particular combination of elements applied. For example, the data structures described herein allow for many options that are not used in a particular element combination. In this case, the data structure is simple.

The build database includes a separate unit control block (UCB) for each application unit (a unit maps one or more parallel arrays) that references a parallel array. These UCBs are linked list 70
At 0 they are joined together. Each UCB includes an APPLICATION UNIT # that identifies the application unit number described by that UCB and labels the area. The UCB in the link list 700 is identified by a table of address pointers included in the link list 700 or another data structure in the program memory of the microprocessor 216a. Each UCB further includes a map 701 of the data groups contained in the particular application unit. The data group map 701 includes a counting area 702 that defines the number of the data group in the application unit, a size area 704 that defines the size of the application unit in the sector, and a linear address space of the application unit that is continuous (relative). Type area 706 that defines whether it is non-contiguous (absolute addressing) or discontinuous (absolute addressing). The non-contiguous address space is shown in FIG.
As described above in relation to the data groups (D4) and (D5) of this example, it is used to allow portions of the application unit to be reserved for dynamic construction.

The dynamic group map 701 further includes a data group mapping element 708 for each data group in the application unit. Each data group mapping element 708 includes a size area 710 that defines the size of the opposing data group in sectors, and a pointer 712 to the aforementioned block 714 in the data group list 716.
, A pointer 718 to the array control block 720, and an index area 721. A data group mapping element 708 is listed in the instruction in mapping the data blocks of each data group to the application unit's LBN. For example, the mapping element for data group D3 referenced in LUN1 of FIG. 6 may be listed before the data group mapping element for data group D2. If the address space of the application unit is non-contiguous, as in the case of LUN1 in FIG.
The data group map includes mapping elements that correspond to gaps in the available range of the LBN and identify the size.

The data group list 716 includes a description block 714 for each data group in the parallel array and provides parameters for mapping each data group to the redundant group and the expansion of the redundant group in which it is located. The data group list 716 includes a counting area 71 defining the number of the description block in the list.
Including 7. In the case of redundant groups with the construction of the striped test data, the description block 714 of each data group will have the first group of data groups from the start of the test data for the redundant group of stripes including the first data block. Includes a "pqdel" region 722 that defines the offset of the data block. Picdell area 72
A value of 2 is positive or negative depending on the relative position of the drive on which the first data block of the data group is built and the opposite test data drive for the redundant group of stripes containing the first data block. This value can be used to assist the parallel array controller in locating test data during I / O operations.

The description block 714 of each data block also includes an index area 723 (the same value as the index area 721), a width area 724, a base area 726, and a development number, which are individually defined as values for the above-described opposed parameters. An area 727, a start area 728, a depth area 730, a stripe depth area 731 of the data group, and a redundant group name area 732 are included.

Array control block 720 provides a map of the redundant groups of the parallel array to the physical address space of the drives of the parallel array. The array control block 720 also includes an array name area 734,
And one or more regions 735 that uniquely identify the current construction of the parallel array. The array control block 720 also includes a list of redundant group description group description blocks 736. Each redundant group description block 736 includes a redundant group name area 738 identifying the redundant group corresponding to the description block, a redundant group width area 740, and a redundant group expansion map 742. Array control block 720
Further, a physical drive identifier block 745 is included.

For each expansion in the redundant group, the redundant group expansion map 742 includes an expansion description block 746 that includes parameters that map the expansion to the corresponding physical addresses in the memory space of the parallel array, and The construction of sensitive information. For example, the expansion description blocks are shown for three expansions of the redundant group RG0 in FIG. 6, and each expansion description block has an expansion number area.
747, and a base and size area that defines the physical address of the relative deployment. Application database and size areas 748 and 750 are redundant group RG0
The diagnosis (low) base and size regions 752 and 754 correspond individually to the base and size of deployment A of the redundant group RG0 and the diagnosis (high). Base and size area
756 and 758 correspond individually to the base and size of deployment C of redundant group RG0.

Each expansion description block 746 also includes a type area 760 that defines the type of redundancy to be implemented in the expansion. For example, the deployment of a redundant group is performed by mirroring or shading the mass storage data stored in the data group in the deployment (where the deployment has the same number as the data drive and the redundant drive). Can be done. Also, the Reed-Solomon coding algorithm uses one for each redundant group of stripes in the deployment.
Used to generate test data on one drive, and more complex Reed-Solomon coding algorithms are used to generate two drives of test data for each redundant group of stripes. The type area 760 may identify whether the test data is striped through the deployment and how to stagger it (e.g., the type area indexes a series of standardized test data patterns, Such a pattern would position the test data for the first redundant group of stripes in the deployment at the next two numerically advanced logical drive locations of the redundancy group and for the second redundant group of stripes in the deployment. The test data is located in the next two numerically advanced logical drives, and so on). Furthermore, the type area 760
Indicates that the test drive is not included in the initial build of the redundant group deployment. This is, for example, the creation of a redundant group preferably created for use by a diagnostic program. The expansion of a redundant group of this type, described above in relation to the expansion A of the redundant group RG0,
As shown in FIG.

Each expansion description block 746 further includes a redundant group stripe depth area 762 to verify that the redundancy group stripe depth in the expansion is unique.

The list 744 of physical drive identifier blocks 745 includes an identifier block 745 for each physical drive in the parallel array. Each identifier block 745 provides information about the physical drive and its current operating state, and in particular, one or more areas 764 for defining logical locations in a parallel array of opposing physical drives. included.

To briefly summarize the functions expected for the variable data configuration of FIG. 7, the unit control block of the linked list 700 defines the mapping of application units to data groups in a parallel array. The mapping of the data groups to the redundant groups is defined by the data group list 716, and the mapping of the redundant groups to the physical address space of the memory of the parallel array is defined by the array control block 720.

Each physical disk in the parallel array is formatted with a formatting utility, a copy of the array control block 720, a linked list 700, and a data group list 716 stored on the drive. This information can be used for variable operations, such as rebuilding a failed drive. A copy of the build database can also be written to other parallel array controllers. This means that one of the parallel arrays fails,
This is the case when another is prepared to be placed.

During each I / O request for a parallel array, a mapping from unit addresses to physical addresses needs to be created. Mapping is about examining the build database for translation of the following: (1) From a unit logical address span specified in an I / O request to a sequence of data group address spans, (2) From a sequence of data group address spans, a set of addresses on a logical drive position in a redundant group From the set of address spans on the logical drive location to the physical drive address span to drive. This mapping process is performed for each I /
In response to an O request, this can be done by having a step of providing an I / O request via the constructed database data configuration. However, during the initialization of the parallel array, the build utility, in addition to generating the build database as described above, performs I / O to perform a unique quick mapping function for each data group.
O Generate a subroutine for the provision of a request. The specific manner in which providing an I / O request performs a mapping operation is specified by the implementation, and one of ordinary skill in the art will implement the provision of the I / O request according to the present invention as described herein. It is understood.

The following describes how the provision of an I / O request maps from the logical unit address span of the application I / O request to one or more spans in the physical address space of the parallel array. This is an example of whether to use the data configuration of FIG. The logical unit address span is specified in I / O requests by logical application unit number and in one or more
It is assumed to define LBN.

The provision of the I / O request is determined from the I / O request of the addressed application unit, and determines whether the application unit references a parallel array. Subsequent decisions are based on the UC with the APPLICATION UNIT # corresponding to the I / O request.
This is done by examining the linked list 700 for B. If a specific UCB is located, the provision of the I / O request then determines the data group in the data block for which these LBNs correspond to the location from the LBN specified in the I / O request. This is done by comparing the size area 710 of the mapping element in the data group map 701 with the LBN to determine the offset of the size area from the start of the application unit address space (including any gaps in the application unit address space). Achieved by counting. For example, if map 701
Is larger than the LBN of the I / O request, it is known that the LBN corresponds to the data block in that data group. If not, the size value of the first mapping element is added to the size value of the next mapping element in map 701, and the LBN is checked against the resulting sum. This process is repeated until a data group is identified for each LBN in the I / O request.

I / Os with unique data groups identified
Providing the request translates the span of the LBN in the I / O request to one or more spans of the corresponding data group number in the identified data group. The construction utility may locate the data group description block 714 in the data group list 716 for that data group by using the index area 7 in each mapping element 708 corresponding to the identified data group.
06 and the value of the pointer 712 can be used. The provision of the I / O request uses the parameters of the description block of the data group to translate each span of the data block number to the span of the logical drive address.

Initially, the provision of the I / O request determines the starting logical drive position of the data group from the base area 726 of the data group description block 714. Provision of the I / O request also determines the name and expansion number of the redundant group in which the data group is located from areas 732 and 727, and furthermore, during the start of the expansion of the redundant group and the start of the data group. In the base area 726, the number of sectors on the drive to be identified is determined from the start area 728. Thus, for example, if the provision of an I / O request reads a description block for a data group D3 constructed as shown in FIG. 6, the base area 726 begins on logical drive location 0. The data group is displayed, the redundant name area 732 displays the data group in the redundant group RG0, the expansion area 727 displays the data group in the expansion B, and the start area 728 displays the start of the expansion B and the data group D3. Display the offset of 10 sectors on logical drive 0 with the first data block.

The provision of the I / O request, known as the logical drive position and the first data block expansion offset of the data group, is performed by the logical drive position for each data block sequence in the data group corresponding to the LBN of the I / O request. And the deployment offset. In this way, provision of an I / O request may use the values of the width region 724, the depth region 730, and the stripe depth region 731 of the data group. If any test data includes a data group square boundary, the position of the test data, if necessary, can be counted in determining the logical drive position and the development offset address of the data block. This is the array control block 720
Achieved using information from. In addition, the provision of I / O requests can be performed by examining the type area 760 and the redundant group stripe depth area 762 of the unique redundant group expansion description block 746 to provide a logic for test data at data group boundaries. The drive position and the expansion offset can be determined (providing the I / O request is based on the expansion number area 7 matching the expansion number area 727 in the expansion description block 746 or the data group description block 714).
By locating the expansion description block 746 having 47, the identified expansion description block 746 can be determined. Provision of an I / O request is directed to the array control block 720 by the pointer 718 in the mapping element 708 of the data group.

To translate each logical drive location and deployment offset address span for a physical address span on a particular physical drive in a parallel array, the provision of the I / O request requires the physical drive corresponding to the identified logical drive location. To determine the physical drive identifier block
Read 745. Provision of an I / O request also reads the base area of the unique deployment description block 746 of the array control block 720 (eg, application base area 752) that provides the physical address on the drive at the start of the deployment. Using the expansion offset address span determined earlier,
Provision of the I / O request may determine the span of the physical address corresponding to the identified development offset address span for each physical drive. During operation of a parallel array, one or more physical drives can be removed or fail. Thus, the data of the erroneous or failed drive must be reconstructed into a spare drive. Under such conditions, the construction of the array
For the rebuild period during which data is reclaimed from the erroneous or failed drive and rebuilt on the spare drive, the new drive is counted as a temporary array change that must be performed. The count must be changed. The details of such regeneration and reconstruction are not within the scope of the present invention. However, the build utility can be used to remap the array build by redefining the build database parameters.

In this manner, it will be appreciated that mass storage devices are manufactured with a plurality of physical storage elements that provide both high bandwidth and high operation rates and provide the required high reliability. . Those skilled in the art will appreciate that the present invention may be practiced with embodiments other than those described above, and in particular may be incorporated into circuits other than the mass storage systems described above. The foregoing embodiments are submitted for illustrative purposes, and are not limiting, and the present invention is limited only by the following claims.

Continued on the front page (72) Inventor Gajah, Coomer United States, California 95131, San Jose, Fun Street 1700 (72) Inventor Glider, Joseph S. United States, California 94303, Palo Alto, Mari Way 3292 (72) Inventor Idolman, Thomas E United States, California 95051, Santa Clara, Brady Court 2660 (56) References JP-A-2-236714 (JP, A) WO 89/10594 (WO, A1) (58) Fields studied (Int. Cl. ⁶ , DB name) G06F 11/10 G06F 3/06 G06F 12/00

Claims (16)

(57) [Claims] 1. A mass storage system for storing data received on a channel from a CPU main memory, comprising: a plurality of storage elements; and at least two storage elements operatively interconnecting the plurality of storage elements. A controller for forming a storage element group, connecting the at least two storage element groups to the CPU via the channel, and controlling a flow of data to and from the CPU. Configuring at least one redundant group within at least one of said at least two storage element groups at a first logic level, and sharing said at least one redundant group for said at least two storage element groups Means for functioning as a redundant group of Arranging at least one data group within each one of the at least two storage element groups at two logical levels, each data group being independently configurable and operable as a separate logical storage device A storage system characterized in that: 2. The mass storage system according to claim 1, wherein each of said redundant groups includes a plurality of data groups. 3. The mass storage system according to claim 1, wherein there are a plurality of said redundant groups, and at least one data group from each of at least two of said plurality of redundant groups. Characterized by being combined to form one logical mass data storage element. 4. The mass storage system according to claim 1, wherein for at least one of said at least one redundancy group, redundancy is provided by an error detection and correction code. Are stored in at least one check drive included in the at least one redundancy group. 5. The mass storage system according to claim 4, wherein each of said at least one check drive is a specific storage element. 6. The mass storage system according to claim 4, wherein each of said at least one check drive is a logical mass storage element including a part of a plurality of said storage elements. Characterized by that. 7. The mass storage system according to claim 1, wherein redundancy is provided by mirroring for at least one of said at least one redundancy group. 8. The mass storage system according to claim 1, wherein at least one redundant mass storage element included in the redundancy group contains redundant data. What to do. 9. A data storage system comprising an external CPU and a controller for communicating with a plurality of storage elements, receiving data from an external CPU, and writing the data to the plurality of storage elements. Decomposing into a plurality of groups of data blocks such that the plurality of storage elements are operatively interconnected to form at least two storage element groups; and Arranging at least one redundancy group within at least one of the element groups, and causing the at least one redundancy group to function as a shared redundancy group for the at least two storage element groups; second logic Level of the at least two storage element groups. Arranging at least one data group within a group, each of the data groups being independently configurable and operable as a separate logical storage element. The method of storing received data from the external CPU. 10. The method for storing received data according to claim 9, wherein each redundancy group comprises a plurality of data groups. 11. The received data storage method according to claim 9, wherein there are a plurality of said redundant groups, and at least one data group from each of at least two of said plurality of redundant groups. Combining the plurality of storage elements so that they are combined to form a single logical mass data storage element. 12. The received data storage method according to claim 9, wherein for at least one of said at least one redundancy group, redundancy is provided by an error detection and correction code, and said error detection and correction is provided. A method wherein a codeword of a code is stored in at least one check storage element included in said at least one redundancy group. 13. The method for storing received data according to claim 12, wherein each of said at least one check storage element is a specific storage element. 14. The storage method according to claim 12, wherein each of said at least one check storage element includes a part of a plurality of said storage elements. It is characterized by being. 15. The method of claim 12, wherein redundancy is provided by mirroring for at least one of the at least one redundancy group. . 16. The received data storage method according to claim 12, wherein at least one redundant storage element included in the redundant group includes redundant data. Method.