Source: https://patents.google.com/patent/US8271727B2/en
Timestamp: 2019-12-09 18:07:08
Document Index: 24112846

Matched Legal Cases: ['§119', 'arts 930', 'arts 930', 'art 0', 'art 2000', 'art 3000', 'art 4000']

US8271727B2 - Method and system for distributing commands to targets - Google Patents
US8271727B2
US8271727B2 US13/291,311 US201113291311A US8271727B2 US 8271727 B2 US8271727 B2 US 8271727B2 US 201113291311 A US201113291311 A US 201113291311A US 8271727 B2 US8271727 B2 US 8271727B2
US13/291,311
US20120054432A1 (en
2009-06-05 Priority to US12/479,403 priority patent/US8086797B2/en
2011-11-08 Priority to US13/291,311 priority patent/US8271727B2/en
2011-12-08 Assigned to PIVOT3 reassignment PIVOT3 ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: CALLISON, RYAN A., GALLOWAY, WILLIAM C., MCGOWEN, MICHAEL. E.
2012-03-01 Publication of US20120054432A1 publication Critical patent/US20120054432A1/en
2012-08-28 Assigned to PIVOT3, INC. reassignment PIVOT3, INC. CORRECTIVE DOCUMENT FOR ASSIGNEE'S NAME FOR ASSIGNMENT ORIGINALLY RECORDED AT REEL 027377 FRAME 0514. Assignors: CALLISON, RYAN A., GALLOWAY, WILLIAM C., MCGOWEN, MICHAEL E.
2012-09-18 Publication of US8271727B2 publication Critical patent/US8271727B2/en
This application is a continuation of and claims a benefit of priority under 35 U.S.C. 120 of the filing date of U.S. patent application Ser. No. 12/479,403, by inventors Galloway et al., entitled “Method and System for Distributing Commands to Targets” filed on Jun. 5, 2009, which in turn claims a benefit of priority under 35 U.S.C. §119 to provisional patent application Nos. 61/131,270 by inventors Galloway et al., entitled “Method and System for Distributed RAID Implementation” filed on Jun. 6, 2008; and 61/131,314 by inventors Galloway et al., entitled “Method and System for Data Migration in a Distributed Multi-Processor RAID Subsystem” filed Jun. 6, 2008; and 61/131,291 by inventors Galloway et al., entitled “System and Method for Distributing Read/Write Requests to Optimal SCSI Targets” filed Jun. 6, 2008; and 61/131,290 by inventors Galloway et al., entitled “Method and System for Utilizing Storage in a Storage System” filed Jun. 6, 2008; and 61/131,379 by inventors Galloway et al., entitled “Method and System for Rebuilding Data” filed Jun. 6, 2008; and 61/131,312 by inventors Galloway et al., entitled “Method and System for Placement of Data on Storage” filed Jun. 6, 2008; the entire contents of each are hereby fully incorporated by reference herein for all purposes.
This invention relates generally to the use of storage devices. More particularly, embodiments of this invention relate to implementing Redundant Array of Independent Disks (RAID) on storage devices. Even more specifically, certain embodiments of this invention relate to a distributed implementation of RAID.
At least portions of the functionalities or processes described herein can be implemented in suitable computer-executable instructions. The computer-executable instructions may be stored as software code components or modules on one or more computer readable media (such as non-volatile memories, volatile memories, DASD arrays, magnetic tapes, floppy diskettes, hard drives, optical storage devices, etc. or any other appropriate computer-readable readable medium or storage device). In one embodiment, the computer-executable instructions may include lines of complied C++, Java, HTML, or any other programming or scripting code.
Additionally, any examples or illustrations given herein are not to be regarded in any way as restrictions on, limits to, or express definitions of, any term or terms with which they are utilized. Instead, these examples or illustrations are to be regarded as being described with respect to one particular embodiment and as illustrative only. Those of ordinary skill in the art will appreciate that any term or terms with which these examples or illustrations are utilized will encompass other embodiments which may or may not be given therewith or elsewhere in the specification and all such embodiments are intended to be included within the scope of that term or terms. Language designating such nonlimiting examples and illustrations includes, but is not limited to: “for example”,“for instance”, “e.g.”, “in one embodiment”.
This application is related to U.S. patent application Ser. No. 12/479,319 entitled “Method and System for Distributed RAID Implementation” by Galloway et al., filed on Jun. 5, 2009; Ser. No. 12/479,360, entitled “Method and System for Data Migration in a Distributed RAID Implementation” by Galloway et al., filed on Jun. 5, 2009; Ser. No. 12/479,377, entitled “Method and System for Initializing Storage in a Storage System” by Galloway et al., filed Jun. 5, 2009; Ser. No. 12/479,434, entitled “Method and System for Rebuilding Data in a Distributed RAID System” by Galloway et al., filed Jun. 5, 2009; and Ser. No. 12/479,394, entitled “Method and System for Placement of Data on a Storage Device” by Galloway et al., filed Jun. 5, 2009 all of which are incorporated fully herein by reference.
These locations may be better explained with reference to the concept of a segment which may be utilized by embodiments of a distributed RAID application 210, where a segment may be the size of 2048 logical block addresses (LEAs) (or some other size) and the size of the logical block address corresponds to the sector size of a disk 252. Disks 252 in the data store 250 on each of data banks 110 may therefore be separated into equal size segments (for example, 1 MB) at step 310. These segments may correspond to one or more contiguous data blocks of a disk drive 252. Therefore, when a user or host 102 requests the creation of a volume from distributed RAID application 210 at step 320 and specifies a level of RAID which will be used in conjunction with that volume at step 330, a number of these segments corresponding to the requested size of the volume plus the number of segments desired to implement the desired level of RAID in conjunction with the volume may be assigned to the volume at step 340.
The use of such a DSM 115 may be illustrated better with respect to FIG. 8 which depicts one embodiment of a method for initializing, updating and utilizing a DSM at a host 102. At step 810, when a DSM 115 on a host 102 is initialized, whether because a host 102 is booted or powered on, the DSM 115 is installed for the first time, etc., the DSM 115 may register with the MPIO. As is known in the art, registering with an MIPO 113 may entail providing the MPIO with information to identify which commands received by the MPIO 113 should be processed in conjunction with the DSM 115.
Referring back now to step 70 of FIG. 8, DSM 115 can utilize a logical address of a volume reference by a command and the table corresponding to the volume to mathematically determine a data bank 110 where the command should be routed. More specifically, the logical address may be used in conjunction with starts 930 and ends 934 and service such commands as described herein. To service, for example, WRITE and READ commands from hosts 102, DSM 115 can map logical addresses to data banks 110 according to table 917. DSM 115 can examine starts 930 and ends 934 in table 917 to determine within which range 924 particular logical addresses lie. More particularly, DSM 115 can determine
a modulo b=c Eq. 1
Field Value Map version 1 LV number 1 Segment size 512 Segment Count 2048 Range count 4 Range 924a Start 0 End 999 Data bank count 5 Data bank order 1, 3, 2, 4, 5 Range 924b Start 2000 End 2999 Data bank count 5 Data bank order 1, 3, 2, 4, 5 Range 924c Start 3000 End 3999 Data bank count 5 Data bank order 1, 3, 2, 4, 5 Range 924d Start 4000 End 5000 Data bank count 5 Data bank order 1, 3, 2, 4, 5
3503 modulo 5=3 Eq. 2
a first computer readable medium, comprising instructions executable for:
obtaining a first command corresponding to a first segment of a first volume;
determining a first storage appliance of a plurality of storage appliances, wherein the first storage appliance corresponds to the first segment of the first volume; and
routing the first command to the first storage appliance, wherein each of the set of hosts is coupled to a distributed RAID system comprising the plurality of storage appliances, each storage appliance coupled to each of the other storage appliance of the plurality of storage appliances, each storage appliance including:
a second computer readable medium comprising instructions executable for:
implementing commands in conjunction with the first volume, wherein the first volume comprises a set of segments including the first segment and the set of segments of the first volume are stored on the plurality of storage appliances according to a first storage appliance order where the first storage appliance order is a first ordering of the plurality of storage appliances including each of the plurality of storage appliances exactly once, and wherein
redundancy data corresponding to a first RAID level implemented in conjunction with the first volume is stored on each of the plurality of storage appliances, such that for each segment of the first volume a corresponding redundancy segment comprising the redundancy data associated with that segment of the first volume does not reside on the same storage appliance as the corresponding segment of the volume.
2. The system of claim 1, wherein determining the first storage appliance is done by a device specific module (DSM).
3. The system of claim 2, wherein the DSM comprises a first table associated with the first volume comprising the first storage appliance order.
4. The system of claim 3, wherein a second volume is stored on the plurality of storage appliances according to a second storage appliance order, where the second storage appliance order is a second ordering of the plurality of storage appliances including each of the plurality of storage appliances exactly once.
5. The system of claim 4, wherein the DSM comprises a second table associated with the second volume comprising the second storage appliance order.
6. The system of claim 3, wherein the first table is updated based on a notification received from one of the plurality of storage appliances that the first table has changed.
7. The system of claim 6, wherein the notification is sent from the one of the plurality of storage appliances when a threshold amount of data associated with the first volume has been moved.
8. The system of claim 6, wherein the first computer readable medium further comprises instructions for updating the first table by obtaining the first table from one of the plurality of storage appliances.
9. A method for routing commands from a host computer to a distributed RAID system, comprising:
obtaining a first command corresponding to the first segment of the first volume;
routing the first command to the first storage appliance in the distributed RAID system comprising the plurality of storage appliances, each storage appliance coupled to each of the other storage appliances of the plurality of storage appliances, and each storage appliance configured for:
redundancy data corresponding to a first RAID level implemented in conjunction with the first volume is stored on each of the plurality of storage appliances, such that for each segment of the first volume a corresponding redundancy segment comprising the redundancy data associated with that segment of the first volume does not reside on the same storage appliance as the corresponding segment of the first volume.
10. The method of claim 9, wherein determining the first storage appliance is done by a device specific module (DSM).
11. The method of claim 10, wherein the DSM comprises a first table associated with the first volume comprising the first storage appliance order.
12. The method of claim 11, wherein a second volume is stored on the plurality of storage appliances according to a second storage appliance order, where the second storage appliance order is a second ordering of the plurality of storage appliances including each of the plurality of storage appliances exactly once.
13. The method of claim 12, wherein the DSM comprises a second table associated with the second volume comprising the second storage appliance order.
14. The method of claim 11, wherein the first table is updated based on a notification received from one of the plurality of storage appliances that the first table has changed.
15. The method of claim 14, wherein the notification is sent from the one of the plurality of storage appliances when a threshold amount of data associated with the first volume has been moved.
16. The method of claim 15, wherein the first computer readable medium further comprises instructions for updating the first table by obtaining the first table from one of the plurality of storage appliances.
17. A non-transitory computer readable medium, comprising instructions executable for:
determining a first storage appliance of a plurality of storage appliances, wherein a first storage appliance corresponds to the first segment of the first volume; and
routing the first command to the first storage appliance in a distributed RAID system comprising the plurality of storage appliances, each storage appliance coupled to each of the other storage appliances of the plurality of storage appliances, and each storage appliance configured for:
18. The computer readable medium of claim 17, wherein determining the first storage appliance is done by a device specific module (DSM).
19. The computer readable medium of claim 18, wherein the DSM comprises a first table associated with the first volume comprising the first storage appliance order.
20. The computer readable medium of claim 19, wherein a second volume is stored on the plurality of storage appliances according to a second storage appliance order, where the second storage appliance order is a second ordering of the plurality of storage appliances including each of the plurality of storage appliances exactly once.
21. The computer readable medium of claim 20, wherein the DSM comprises a second table associated with the second volume comprising the second storage appliance order.
22. The computer readable medium of claim 19, wherein the first table is updated based on a notification received from one of the plurality of storage appliances that the first table has changed.
23. The computer readable medium of claim 22, wherein the notification is sent from the one of the plurality of storage appliances when a threshold amount of data associated with the first volume has been moved.
24. The computer readable medium of claim 23, wherein the first computer readable medium further comprises instructions for updating the first table by obtaining the first table from one of the plurality of storage appliances.
US13/291,311 2008-06-06 2011-11-08 Method and system for distributing commands to targets Active US8271727B2 (en)
US12/479,403 US8086797B2 (en) 2008-06-06 2009-06-05 Method and system for distributing commands to targets
US13/291,311 US8271727B2 (en) 2008-06-06 2011-11-08 Method and system for distributing commands to targets
US12/479,403 Continuation US8086797B2 (en) 2008-06-06 2009-06-05 Method and system for distributing commands to targets
US20120054432A1 US20120054432A1 (en) 2012-03-01
US8271727B2 true US8271727B2 (en) 2012-09-18
JP2011003111A (en) 2011-01-06 Method for managing storage system using flash memory, and computer
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GALLOWAY, WILLIAM C.;CALLISON, RYAN A.;MCGOWEN, MICHAEL. E.;REEL/FRAME:027377/0514
Free format text: CORRECTIVE DOCUMENT FOR ASSIGNEE'S NAME FOR ASSIGNMENT ORIGINALLY RECORDED AT REEL 027377 FRAME 0514;ASSIGNORS:GALLOWAY, WILLIAM C.;CALLISON, RYAN A.;MCGOWEN, MICHAEL E.;REEL/FRAME:028856/0704