Method and system for logical-object-to-physical-location translation and physical separation of logical objects

[0002] The present invention relates to the physical locations of logical objects in mass storage devices and, in particular, to a method and system for providing logical-object-to-physical-location translations and for providing physical separation of logical objects, where the translations and physical separations are requested by high-level application programs executed on a host computer or human users interacting with a host computer that accesses and manipulates logical objects stored on a remote mass storage device, such as a disk array.

[0003] The present invention relates to the access and manipulation of logical objects stored on remote mass storage devices by high-level application programs executing on host computers connected to the mass storage devices. The present invention is described and illustrated with reference to an embodiment partially included in a disk array controller that services I/O requests from a number of remote computers. However, alternative embodiments of the present invention may be employed in controllers of many other types of storage devices as well as in general electronic data storage applications.

[0004] FIG. 1 illustrates data storage within a platter of a hard disk drive. The platter is a thin disk, coated with a magnetic medium, such as iron oxide. Data can be stored in tiny areas of the surface of the platter having induced, stable magnetic fields. The surface of the disk platter 102 is divided into concentric rings, or tracks, such as tracks 104-105 in FIG. 1. Current disk platters contain many thousands of tracks. Each track is divided into radial segments, or sectors, such as sector 106 of track 104 in FIG. 1. Sectors each normally comprise a fixed number of bytes, normally 256, 512, 1024, or 2048 bytes. Data is normally retrieved from, and stored to, a hard disk drive in units of sectors. Once a sector is read from a disk and stored into computer memory, a program may access individual bytes and bits within the sector by accessing the random memory in which the sector is stored. Thus, the physical location of data on a disk platter can be described by a starting location and an ending location, each location specified as a track/sector/byte triple. Normally, a hard disk drive contains a number of platters aligned in parallel along a spindle passing through the center of each platter. Typically, the track and sectors of the platter can be thought of as aligned to form cylinders spanning the platters. In such hard disk drives, the physical address of a byte of data may also be described by a track/sector/byte triplet, where the byte within an aligned group of sectors composing a section of a cylinder are consecutively ordered.

[0005] FIG. 2 is a block diagram of a standard disk drive. The disk drive 201 receives input/output (“I/O”) requests from remote computers via a communications medium 202 such as a computer bus, fibre channel, or other such electronic communications medium. For many types of storage devices, including the disk drive 201 illustrated in FIG. 2, the vast majority of I/O requests are either READ or WRITE requests. A READ request requests that the storage device return to the requesting remote computer some requested amount of electronic data stored within the storage device. A WRITE request requests that the storage device store electronic data furnished by the remote computer within the storage device. Thus, as a result of a READ operation carried out by the storage device, data is returned via communications medium 202 to a remote computer, and as a result of a WRITE operation, data is received from a remote computer by the storage device via communications medium 202 and stored within the storage device.

[0006] The disk drive storage device illustrated in FIG. 2 includes controller hardware and logic 203 including electronic memory, one or more processors or processing circuits, and controller firmware, and also includes a number of disk platters 204 coated with a magnetic medium for storing electronic data. The disk drive contains many other components not shown in FIG. 2, including read/write heads, a high-speed electronic motor, a drive shaft, and other electronic, mechanical, and electromechanical components. The memory within the disk drive includes a request/reply buffer 205 which stores I/O requests received from remote computers and an I/O queue 206 that stores internal I/O commands corresponding to the I/O requests stored within the request/reply buffer 205. Communication between remote computers and the disk drive, translation of I/O requests into internal I/O commands, and management of the I/O queue, among other things, are carried out by the disk drive I/O controller as specified by disk drive I/O controller firmware 207. Translation of internal I/O commands into electromechanical disk operations in which data is stored onto, or retrieved from, the disk platters 204 is carried out by the disk drive I/O controller as specified by disk media read/write management firmware 208. Thus, the disk drive I/O control firmware 207 and the disk media read/write management firmware 208, along with the processors and memory that enable execution of the firmware, compose the disk drive controller.

[0007] Individual disk drives, such as the disk drive illustrated in FIG. 2, are normally connected to, and used by, a single remote computer, although it has been common to provide dual-ported disk drives for use by two remote computers and multi-port disk drives that can be accessed by numerous remote computers via a communications medium such as a fibre channel. However, the amount of electronic data that can be stored in a single disk drive is limited. In order to provide much larger-capacity electronic data storage devices that can be efficiently accessed by numerous remote computers, disk manufacturers commonly combine many different individual disk drives, such as the disk drive illustrated in FIG. 2, into a disk array device, increasing both the storage capacity as well as increasing the capacity for parallel I/O request servicing by concurrent operation of the multiple disk drives contained within the disk array.

[0008] FIG. 3 is a simple block diagram of a disk array. The disk array 302 includes a number of disk drive devices 303, 304, and 305. In FIG. 3, for simplicity of illustration, only three individual disk drives are shown within the disk array, but disk arrays may contain many tens or hundreds of individual disk drives. A disk array contains a disk array controller 306 and cache memory 307. Generally, data retrieved from disk drives in response to READ requests may be stored within the cache memory 307 so that subsequent requests for the same data can be more quickly satisfied by reading the data from the quickly accessible cache memory rather than from the much slower electromechanical disk drives. Various elaborate mechanisms are employed to maintain, within the cache memory 307, data that has the greatest chance of being subsequently re-requested within a reasonable amount of time. The disk array controller 306 may also elect to store data received from remote computers via WRITE requests in cache memory 307 in the event that the data may be subsequently requested via READ requests or in order to defer slower writing of the data to physical storage medium.

[0009] Electronic data is stored within a disk array at specific addressable locations. Because a disk array may contain many different individual disk drives, the address space represented by a disk array is immense, generally many thousands of gigabytes. The overall address space is normally partitioned among a number of abstract data storage resources called logical units (“LUNs”). A LUN includes a defined amount of electronic data storage space, mapped to the data storage space of one or more disk drives within the disk array, and may be associated with various logical parameters including access privileges, backup frequencies, and mirror coordination with one or more LUNs. LUNs may also be based on random access memory (“RAM”), mass storage devices other than hard disks, or combinations of memory, hard disks, and/or other types of mass storage devices. Remote computers generally access data within a disk array through one of the many abstract LUNs 308-315 provided by the disk array via internal disk drives 303-305 and the disk array controller 306. Thus, a remote computer may specify a particular unit quantity of data, such as a byte, word, or block, using a bus communications media address corresponding to a disk array, a LUN specifier, normally a 64-bit integer, and a 32-bit, 64-bit, or 128-bit data address that specifies a LUN, and a data address within the logical data address partition allocated to the LUN. The disk array controller translates such a data specification into an indication of a particular disk drive within the disk array and a logical data address within the disk drive. A disk drive controller within the disk drive finally translates the logical address to a physical medium address. Normally, electronic data is read and written as one or more blocks of contiguous 32-bit or 64-bit computer words, the exact details of the granularity of access depending on the hardware and firmware capabilities within the disk array and individual disk drives as well as the operating system of the remote computers generating I/O requests and characteristics of the communication medium interconnecting the disk array with the remote computers.

[0010] While the disk array, as described above, provides data storage within, and addressed relative to, LUNs, high-level application programs (“APPs”) executing on host computers access data stored within LUNs via a number of higher-level abstractions. FIG. 4 illustrates the hierarchical data abstraction levels within a host computer/disk array system. Each block in FIG. 4 represents a separate program, program/hardware, or hardware component within the host computer/disk array system. As discussed above, the disk array 402 accesses data stored within internal disks via internal physical addresses that each contain indications of a disk, a track within a disk, a sector within the track, and a byte within the sector. However, as discussed above, the disk array provides data access and storage to virtual storage spaces, called LUNs, each LUN having some fixed number of addressable units, such as bytes. The two abstractions 404 and 406 in FIG. 4 are linked to operating system components that execute within the operating system of a host computer interconnected with a disk array. The first component is a volume manager 404. This component interacts with a disk array via a communications medium, accessing and storing data relative to the LUN abstraction provided by the disk array. The volume manager 404 presents a different interface to components above the volume manager in the abstraction hierarchy. The volume manager provides volumes which have volume names and which contain a linear address space of bytes, words, or some other convenient addressable entity. The volume manager may map a volume onto one or more LUNs, translating volume-relative addresses received from higher-level components into LUN-based data addresses that the volume manager then passes to the disk array. In addition, the volume manager can increase the size of a logical volume using an arbitrary LUN, which can quickly change the physical location of the entirety of a logical object.

[0011] The next highest component shown in FIG. 4 is the operating system's file manager 406. The file manager provides a logical object interface to the highest-level component, an executing APP 408. Most logical objects currently provided by file managers and used by APPs are called “files.” Files are arbitrarily sized, consecutive sequences of data bytes, described by file names, that are stored on a mass storage device and read from, and written to, operating-system-provided I/O commands. A file manager provides a hierarchical, multi-component file name space to allow an APP or user to organize files within hierarchical directories. The file manager translates a file name, including the directory and subdirectory prefixes within the file name, to a range of consecutive addressable entities, such as bytes, within a volume. An APP 408, or a human user interacting with the APP, stores data to, and accesses data from, a mass storage device, such as a disk array, in terms of named logical objects.

[0012] Normally, a human user or APP is not concerned with the actual physical location of logical objects. Logical objects may, for example, span a number of different LUNs, each of which span a number of different hard disk drives within a disk array. There are, however, cases where a human user or APP may be very concerned about the physical locations of data stored within logical objects. In many systems, logical objects are replicated in order to provide greater reliability. If the storage medium on which a first logical object is stored becomes corrupted, then the second logical object, a copy of the first logical object, can be accessed instead. However, if both logical objects, or portions of the logical objects, are stored on the same hard disk drive, a single hard disk drive failure may destroy both logical objects and may therefore constitute an unrecoverable error. No matter how many copies of a logical object are saved, because portions of the logical objects may end up residing on a common disk drive, a user or application program may not be guaranteed of being able to recover a single good copy of the logical object following a hard disk drive failure. Of course, a user or APP may direct copies of the logical objects to be stored on different disk arrays or other types of mass storage devices. However, there may be additional virtual address layers between disk drives and a host computer, so that an APP or user may not, in fact, be able to determine from a logical object name on which mass storage device the logical object resides.

[0013] Various utilities and support functionality within operating systems and disk array controllers have been developed in order to facilitate translation of logical object names to physical storage locations. FIG. 5 graphically represents two translation mechanisms that facilitate translation of logical object names to physical storage locations. Within a disk array controller 502, a LUN Manager, or LUN Manager functionality, may translate a LUN into one or more physical extents, each physical extent comprising a starting point and ending point on a hard disk drive, each extent expressed as indications of a disk, a track within the disk, and a sector within the track. The LUN Manager 504, in addition to providing LUN to physical location translations, can also forcibly relocate a first LUN to different hard disks within the disk array so that the first LUN does not overlap a second LUN, or, in other words, so that no data of the first LUN is stored on a hard disk that stores data of the second LUN. When data of a first LUN is stored on a disk which contains data of a second LUN, then the two LUNs are said to overlap. Thus, the forcible relocation functionality provided by the LUN Manager 504 ensures that two LUNs do not overlap.

[0014] Within operating systems or within an application directly above the operating system, of host computers, an executable routine or component “ResolveObject” 506 has been developed to translate a logical object name 508 into one or more LUNs 510 on which the object is stored in a mass storage device. ResolveObject interacts with the file manager and volume manager, or with shared data structures employed by the file manager and volume manager, to translate logical object names into a list of LUNs. Both ResolveObject 506 and LUN Manager 504 provide necessary pieces of a logical-object-name-to-physical-location translation mechanism required by certain human users and APPs running on host computers. However, these separate functionalities are not currently linked, and it is difficult or impossible for a human user or APP to first use ResolveObject to translate a logical object name to a list of LUNs and then to directly access functionality provided by the LUN Manager 504 on a remote disk array 502 to obtain a physical translation of a logical object name and to employ the forced-move functionality provided by the LUN Manager in order to separate the set of LUNs that together compose a first logical object from the set of LUNs that together compose a second logical object so that the first logical object does not overlap the second logical object.

[0015] Thus, computer users, application program developers, database managers, database designers, and computer and mass storage device designers and manufacturers have all recognized the need for direct, easy-to-use logical object translation and logical object separation mechanisms that can be employed by human users and APPs to determine the physical locations of logical objects and to force and monitor separation of logical objects.

[0016] One embodiment of the present invention provides logical object to physical location translation to human users and APPs for logical objects stored on mass storage devices. In addition, this embodiment of the present invention provides tools with which a human user or APPs may separate two logical objects so that the two logical objects do not overlap on physical storage media and tools that allow a human user or APP to monitor the resulting separation of logical objects to detect subsequent re-overlap of the logical objects. This embodiment of the present invention makes use of already existing object resolution and LUN Manager functionalities developed for host computers and mass storage devices, respectively. This embodiment provides new interfaces to the object resolution and LUN Manager components, and provides direct interaction between these new interfaces.

[0017] FIG. 1 illustrates data storage within a platter of a hard disk drive.

[0018] FIG. 2 is a block diagram of a standard disk drive.

[0019] FIG. 3 is a simple block diagram of a disk array.

[0020] FIG. 4 illustrates a number of components within a host computer/disk array system.

[0021] FIG. 5 graphically represents two translation mechanisms that facilitate translation of logical object names to physical storage locations.

[0022] FIG. 6 illustrates the relationship between one embodiment of the present invention and the ResolveObject and LUN Manager functionality illustrated in FIG. 5.

[0023] FIG. 7 illustrates the overall organization and particular features of a C++-like pseudocode implementation of a portion of one embodiment of the present invention.

[0024] FIG. 8 is a flow-control diagram for the routine “watch.”

[0025] FIG. 9 is a flow-control diagram for the routine “rearrange.”

[0026] FIG. 10 is a flow-control diagram for the routine “rearrange_async.”

[0027] FIG. 11 is a flow-control diagram for the routine “separateAndWatch.”

[0028] FIG. 12 is a flow-control diagram of the routine “translate.”

[0029] FIG. 13 is a flow-control diagram for the routine “compare.”

[0030] FIG. 14 is a flow-control diagram for the routine “monitor.”

[0031] FIG. 15 is a flow-control diagram for the routine “physicalLocation.”

[0032] FIG. 16 illustrates an example of a graphical display of the mapping of a logical object onto physical disks within a disk array.

[0033] The present invention is related to determination of the physical location and control of the physical location of logical objects within mass storage devices. As described above, a logical object represents many levels of abstraction above the physical storage of data comprising the logical object on a mass storage device. Generally, the physical location or locations of a logical object is of little or no concern to computer users and APPs. However, in certain cases, including cases in which a logical object needs to be replicated so that loss of one copy of the logical object does not result in unrecoverable loss of the data within the logical object, the physical location or locations of a logical object are of great and immediate concern to a human user or APP. As discussed above, with reference to FIG. 5, the ResolveObject functionality 506 developed for host computers 505 and the LUN Manager functionality 504 developed for a particular type of mass storage device, the disk array 502, both provide portions of the functionality required for logical object name translation and logical object separation. However, as discussed with reference to FIG. 5, the ResolveObject and LUN Manager components are not currently interfaced with one another, and it is difficult or impossible for human users and APPs to employ the LUN Manager functionality following logical objects name resolution in order to obtain logical-object-physical-location translations and in order to separate logical objects so that the logical objects do not overlap within a mass storage device. Even if the physical location of a logical object could be obtained by a human users or an APP, there is no guarantee that, because of subtle changes, such as logical volume expansion or striping, the obtained physical location is valid at a subsequent point in time when the human users or APP attempts to use the obtained physical location.

[0034] FIG. 6 illustrates the relationship between one embodiment of the present invention and the ResolveObject and LUN Manager functionality illustrated in FIG. 5. In order to interface ResolveObject functionality with functionality provided by the LUN Manager, represented in FIG. 6 by double-headed arrow 606, a host logical object watch interface (“HLOWI”) 602 is provided that, in turn, provides a high-level functional interface to an array logical object watch interface (“ALOWI”) 604 within a disk array controller. Because the HLOWI interfaces to the ALOWI, the HLOWI can provide a functional interface to human users and to APPs that may draw on both ResolveObject functionality and LUN Manager functionality to carry out tasks specified by calling functions of the functional interface. Details of the functional interface are discussed below.

[0035] Note that the ALOWI component of the present invention may be implemented within a software program or routine running on a processor implementing a disk array controller, or controller in some other type of mass storage device, within a firmware implementation of a controller, or directly within logic circuits. The HLOWI component of the present invention may be implemented as a software program or collection of software routines within or above the operating system of a host computer. The HLOWI functionality may be implemented, in the future, in devices, other than computers, that are interconnected with, and that provide access to, mass storage devices such as disk arrays. C++-like pseudocode and flow control diagrams are provided below to illustrate one possible implementation of the present invention, but the C++-like pseudocode and flow control diagrams are not intended, in any way, to limit the present invention to a particular type or style of implementation.

[0036] Several embodiments of the present invention are discussed, below, with reference to a C++-like pseudocode implementation of a portion of a disk array controller. FIG. 7 illustrates the overall organization and particular features of this C++-like pseudocode. The C++-like pseudocode includes several routines. The routine “IORequestHandler” 702 represents high-level processing by the disk array controller. This routine receives I/O requests from remote computers via an inbound queue “inQueue” 704 and distributes received I/O requests to intermediary queues, called “IOreqQs” (for example, IOreqQ 706 in FIG. 7) associated with each LUN. For each LUN, a separate asynchronously executing thread executes the routine “IOHandler” (for example, IOHandler thread 708 in FIG. 7) that receives I/O requests from the intermediary queue associated with the thread, processes the I/O requests, and returns status and, in the case of a READ request, data to an outgoing queue “outQueue” 710.

[0037] Note that the following C++-like pseudocode does not attempt to illustrate or describe all of the various functionality of a disk array controller, but only that functionality related to the present invention. The following C++-like pseudocode is provided for illustration of an embodiment of the present invention.

[0038] First, a number of enumerations and constants are provided, followed by a number of class declarations. Many of these classes contain no member functions, because no additional detail is necessary for the subsequent routine descriptions. In essence, they are stubs, or place holders, representing additional potential functionality that is unnecessary for description of the present invention. Other of the classes contain minimal member functions sufficient for description of the present invention. Note, however, that the C++-like pseudocode used to describe the present invention can be easily transformed into working C++ code by including member functions not provided in the C++-like pseudocode and by implementing the member functions. In the C++-like pseudocode, implementations of routines are only provided when necessary to describe the present invention.

[0039] The C++-like pseudocode illustrates a possible implementation of the ALOWI component of one embodiment of the present invention within a disk array controller. A logical object may, in certain cases, span multiple disk arrays or other mass storage devices. In cases where logical objects may span multiple mass storage devices, such as multiple disk arrays, the ALOWI interface may be provided in a distributed fashion by one or more of the mass storage devices or by some intermediate device or computer. A distributed ALOWI requires more complex functionality and interconnection, but can be interfaced to an HLOWI, according to the present invention, in similar fashion to interfacing of a LUN Manager within a single mass storage device to an HLOWI.

[0040] 1 enum IOCommand {READ, WRITE, WATCH, REARRANGE, MOVE, TRANSLATE};

[0041] 2 enum IOstatus {SUCCESS, QUEUED, FAILURE};

[0042] 3 enum IOReplyTp {WATCH_REPLY, REARRANGE_REPLY, MOVE_REPLY};

[0043] 4 const int NULL=0;

[0044] 5 const int LUNno=4096;

[0045] The values of the enumeration “IOCommand” on line 1, above, represent the basic I/O commands READ and WRITE, as well as commands directed to the ALOWI that provide logical-object-name translation and logical-object separation and rearrangement. These commands will be discussed, in detail, below. The values of the enumeration “lostatus,” on line 2, above, indicate an outcome following execution of an I/O command. The status “QUEUED” indicates that an I/O command has resulted in launching or scheduling for launch of an asynchronous process that will complete at a later time. The values of the enumeration “IOReplyTp,” on line 3, above, indicate the type of IOReply returned from the ALOWI to the HLOWI. Note that this list is not complete, but only includes values necessary for implementation of the portions of the ALOWI shown in the C++-like pseudocode implementation. The constant “NULL” is defined to indicate null pointers. The constant “LUNno” is defined to represent the maximum number of LUNs that can be provided by a disk array, and is arbitrarily set to the constant value 4096 in the pseudocode.

[0046] An instance of the class “time,” defined above, represents a particular time returned, for example, by a call to a system function that returns the current system time. The class “time” may include a number of operator members that allow for comparison of times, subtraction of times, addition of times, and addition of an integer representing some number of units of time, such as seconds, to an instance of the class “time.” Only one operator is shown, above.

[0047] An instance of the class “hostID” represents a unique identifier and address for a host computer. An instance of the class “arrayID” represents the address of a disk array, in the current embodiment. Other types of addresses are necessary when the ALOWI resides on another type of mass storage device or on an intermediate computer. An instance of the class “IOaddress” represents the address of electronic data specified in an I/O request for READ or WRITE access. The class “buffAddress” represents the address of a buffer that stores electronic data for transfer between remote computers and the disk array controller.

[0048] An instance of the class “IO_LUN” represents a particular LUN provided by a disk array. The class “I/O_LUN” includes a member function “getLUN” that returns an integer uniquely identifying the LUN described by an intance of I/O_LUN. An instance of the class “I/O_LUNs” represents the collection of LUNs provided by a disk array, and the member functions “getFirst” and “getNext” allow an instance of the class “I/O_LUN” to be retrieved from the collection for each LUN provided by a disk array.

[0049] An instance of the class “LUNlist” represents a list of integer specifiers of LUNs. The class “LUNlist” includes member functions “getFirstLUN” and “getNextLUN” to get the first integers specifying a LUN from the list and then traverse the remaining integers within the list, and includes analogous functions “setFirstLUN” and “setNextLUN” for inserting integers into the list. The class “LUNlist” includes an additional member function “clear” that clears all entries from the lists. Below, a number of other classes use the same list paradigm, and will not be described in great detail as they are entirely analogous with the member functions of the classes “I/O_LUNs” and “LUNlist.”

[0050] An instance of the class “physicalMediumAddress” represents the address of a data entity, such as a byte or word, within a disk array. As described adove, a physical address includes an indication of a disk, a track within the disk, and a sector. The class “physicalMediumAddress” correspondingly includes member funtions for extracting and setting the disk, track, and sector indicators of a physical address.

[0051] An instance of the class “physicalMediumChunk” describes an extent of data stored within a disk array. An extent of data is a continuous sequence of data entities, such as bytes or words. An extent is characterized by a starting physical location and an ending physical location, and the class “physicalMediumChunk” correspondingly includes member functions for obtaining the start and ending physical address of the chunk and for setting the start and ending physical addresses for the chunk.

[0052] An instance of the class “chunkList” describes a set of physical extents, or chunks, and employs the same list paradigm as employed by the earlier described classes “IO_LUNs” and “LUNlist.” An instance of the class “physicalLunTranslation” describes the translation of a LUN into a list of physical extents, and therefore includes member functions to get and set the LUN, where the LUN is indicated by an integer, and member functions to get and set the physical-location descriptions of the extents contained within an instance of the class “chunkList.” An instance of the class “physicalLunTransList” is a list of instances of the class “physicalLunTranslation.” An instance of the class “physicalLunTransList” contains member functions that follow the paradigm described earlier for classes “IO_LUNs” and “LUNlists.” A list of physical translations represented by an instance of the class “physicalLunTransList” may represent a proposed rearrangement of LUNs to alternative physical locations within a disk array.

[0053] An instance of the class “objectName” represents the name of a logical object. An instance of the class “objectLunTranslation” represents the translation of a logical object name to a physical location, and includes member functions to get and set the name of the logical object and member functions to get and set the physical translation corresponding to the logical object. An instance of the class “internalArrayMap” represents an internal map within the disk array that maps the LUNs provided by the disk array to physical locations within a disk array. The class “internalArrayMap” includes the following member functions: (1) “valid,” a member function that returns a Boolean value indicating whether or not an integer designating a LUN, provided as an argument, specifies a valid LUN; (2) “getTrans,” a member function that provides the physical translation for a LUN specified by an integer provided as an argument; and (3) “setTrans,” a member function that enters a physical mapping of a LUN into the internal array map.

[0054] The class “IOrequest” encapsulates the various data that together compose an I/O request received by a disk array controller from a remote computer and that is serviced by the disk array controller. The class “IOrequest” includes the following member functions: (1) “getHostID,” a function that returns a pointer to an object of the class “HostID” that represents the remote computer that generated the I/O request represented by the current instance of the class “IOrequest;” (2) “setHostID,” a member function that sets the host ID of the I/O request represented by the current instance of the class “IOrequest” to the host ID pointed to by the supplied pointer argument; (3) “getArrayID,” a member function that returns an address of a disk array to which the I/O request is directed; (4) “setArrayID,” a member functions that sets an instance of the class “IOrequest” to be directed to a particular disk array addressed by the address provided as an argument; (5) “getIOCommand,” a member function that returns one of the values enumerated in the enumeration “IOCommand” indicating the nature of the I/O request; (6) “setIOCommand,” a member function that sets the I/O request to have a type equal to one of the values enumerated in the enumeration “IOCommand” to indicate the nature of the I/O request; (7) “getID,” a member function that returns a unique ID identifying an instance of the class “IOrequest;” and (8) “setID,” a member function that sets the unique ID identifying the IOrequest.

[0055] The C++-like pseudocode implementation employs a number of request classes derived from the above-described class “IOrequest.” These derived request classes represent particular types of I/O requests. The first derived request class, “DataRequest,” represents a standard READ or WRITE I/O command, and includes the following member functions: (1) “getLUN,” a member function that returns the LUN to which the I/O request is addressed; (2) “setLUN,” a member function that sets the LUN to which the I/O request is addressed; (3) “getIOaddress,” a member function that returns the address of the first electronic data to which the I/O request is targeted; (4) “setIOaddress,” a member function that sets the address of the first electronic data to which the I/O request is targeted; (5) “getBuffAddress,” a member function that returns the address of the buffer that contains data for a WRITE operation or into which data is placed for a READ operation; (6) “setBuffAddress,” a member function that sets the address of a buffer that contains data for a WRITE operation or into which data is placed for a READ operation; (7) “getLength,” a member function that returns the length, or number of contiguous bytes, words, or blocks of data to be read or written during servicing of the I/O request; and (8) “setLength,” a member function that sets the length, or number of contiguous bytes, words, or blocks of data to be read or written during servicing of the I/O request.

[0056] The next four derived request classes constitute the interface of the ALOWI. These four derived classes stand for the commands, or functions, WATCH, REARRANGE, MOVELUN, AND TRANSLATE. A WATCH command, represented by an instance of the class “WatchRequest,” instructs the ALOWI to monitor READ and WRITE activity directed towards LUNs provided within the WATCH command in a list of LUNs for an interval of time provided in the WATCH command as an integer. After monitoring the disk activity directed to the LUNs within the list of LUNs, the ALOWI furnishes, in response to the WATCH command, a proposed physical relocation of some or all of the LUNs in order to optimize disk activity associated with the LUNs. For example, monitoring of the LUNs may determine that greater parallelism can be achieved by separating the LUNs on separate physical disks. In other cases, if access to LUNs appears to be more or less regularly interleaved, the LUNs may be correspondingly interleaved on a single physical disk in order to minimize seek operations within the hard disk drives. An instance of the class “WatchRequest” includes the following member functions: (1) “getLUNlist,” a member function that returns a pointer to the list of LUNs included in the WatchRequest; (2) “setLUNlist,” a member function that sets the list of LUNs to be watched during execution of the WatchRequest; (3) “getInterval,” a member function that extracts from a WatchRequest the time interval during which monitoring should occur; and (4) “setInterval,” a member function that sets the time interval for monitoring.

[0057] An instance of the class “RearrangeRequest” represents a rearrange command that rearranges LUNs within a disk array according to a supplied list of translations of LUNs to sets of physical extents. These sets of physical extents are returned b a disk array controller in response to a WATCH command. Thus, in order to achieve disk array optimization, a WATCH command is directed to the disk array to obtain a proposed list of physical translations represented proposed relocations of LUNs, and that proposed list of changes is supplied to the disk array in a REARRANGE command in order to cause the disk array to remap the LUNs according to the proposed physical translations. An instance of the class “RearrangeRequest” therefore contains the following member functions: (1) “getTransList,” a member function that returns a list of proposed locations of LUNs; (2) “setTransList,” a member function that sets the request rearrangement to a proposed list of physical translations pointed to by the supplied pointer argument; (3) “getWhen,” a member function that returns a time indicating when the rearrangement should begin; (4) “setWhen,” a member function that sets the time at which rearrangement should begin for a particular REARRANGE request; (5) “getBy,” a member function that returns a time interval during which the rearrangement should occur; and (6) “setBy,” a member function that sets the time interval during which the arrangement should occur.

[0058] An instance of the class “MoveLunRequest” represents a MOVELUN command that directs a disk array to move or relocate a LUN such that the LUN does not overlap any of the disks that include a physical extent specified in an accompanying physical translation. The class “MoveLunRequest” therefore includes member functions to extract and to set a physical LUN translation to indicate both a LUN to relocate and a physical translation away from which the LUN should be relocated. A MOVELUN command is essentially a forced move or forced relation request can be used to physically separate a first LUN from a second LUN. Note that the physical LUN translation included in the MOVELUN request does not represent the physical translation of a LUN, but instead represents the combination of a LUN to forcibly relocate and the physical translation of a second LUN away from which the LUN should be physically relocated.

[0059] An instance of the class “TranslateRequest” represents a translate command that directs the ALOWI to provide a physical translation of the LUN included in the TranslateRequest. An instance of the class “TranslateRequest” includes member functions to get and set an indication of LUN to which the physical translation is requested.

[0060] An instance of the class “IORequestQueue” serves as the inQueue (702 in FIG. 7). The class “IORequestQueue” contains the following member functions: (1) “getNext,” a member function that dequeues and returns a pointer to the next I/O request on the queue; (2) “queue,” a member function that queues an I/O request, pointed to by the single argument, to the queue; (3) “getHeadHost,” a member function that returns the hostID from the next I/O request within the queue to be dequeued from the I/O request queue; (4) “empty,” a member function that returns a Boolean value indicating whether or not the I/O request queue is empty; (5) “terminated,” a member function that returns a Boolean value indicating whether or not the I/O request queue has been terminated, or shut down; and (6) “terminate,” a member function that shuts down, or terminates, the I/O request queue.

[0061] An instance of the class “IORequestQueueArray” maintains a buffer of instances of the class “IORequestQueue” described above. These instances of the class “IORequestQueue” correspond to the IOreqQs (for example, IOreqQ 703 in FIG. 7) associated with threads executing the routine “IOHandler.”

[0062] An instance of the class “IOreply” represents a reply to an IO command from the disk array back to a host computer. The class “IOreply” includes many of the same member functions included in the class “IOrequest.” However, a reply message represented by an instance of the class “IOreply” includes member functions to retrieve and set a reply type rather than the corresponding member functions in the class “IOrequest” that retrieve and set an IO command. The class “IOreply” includes two additional member functions that retrieve and set an IO status that represents the outcome of an IO command executed by the disk array controller.

[0063] The class “DataReply” represents a reply to a READ or WRITE I/O command, and contains member functions equivalent to those contained in the class “DataRequest.” An instance of the class “WatchReply” represents a reply from the disk array controller to a host computer WATCH command, and includes member functions to retrieve and set the physical LUN translation list included in the reply that represents a proposed relocation of one or more LUNs. An instance of the class “RearrangeOrMoveReply” represents the reply from the disk controller to a host computer to deliver a REARRANGE command or a MOVELUN command. In both cases, the status indication in the base class “IOreply” is sufficient to convey needed information from the disk controller back to the host computer. The class “TranslateReply” represents the reply to a TRANSLATE command from the disk controller to the host computer, and includes member functions to retrieve and set a physical translation list that represents the physical translation determined for the LUN specified the TRANSLATE command. Finally, the class “IOReplyQueue” is analogous to the class “IORequestQueue” and is used, for example, for the outQueue (710 in FIG. 7) in the disk array controller.

[0064] The routine “IORequestHandler” (702 in FIG. 7) represents high-level processing carried out by the disk array controller in order to implement one embodiment of the present invention:

[0065] The routine “IORequestHandler” receives pointers to the inQueue (704 in FIG. 7), the outQueue (710 in FIG. 7), a map of the physical locations of all LUNs within the disk array, and a container “iluns” that contains instances of the class “IO_LUN” for each LUN provided by the disk array controller. On line 10, IORequestHandler calls a routine “initialize” to carry out any initialization operations on the I/O queues. These initialization operations are, for the most part, dependent on implementations of other portions of the disk array controller that are beyond the scope of the present invention, and are therefore not described in an implementation of the routine “initialize.”

[0066] On lines 11-17, IORequestHandler starts execution of a separate instance of the routine “IOHandler” for each LUN. The bulk of the processing carried out by IORequestHandler occurs in the loop comprising lines 18-97. This loop is terminated only when one or both of the inQueue and outQueue (704 and 710 in FIG. 7, respectively) are terminated. On line 23, IORequestHandler checks to see if the inQueue is empty and, if so, calls a system function “systemWaitOnQueueEvent” to wait until an I/O request is queued to the inQueue. Once a next I/O request is available for processing, IORequestHandler dequeues that I/O request from the inQueue, on line 21. In the series of if and else-if statements starting in line 22, IORequestHandler processes each type of incoming command. If the incoming command is a READ or WRITE command, as detected by IORequestHandler on lines 22 and 23, then on lines 25-27, IORequestHandler forwards the request to he appropriate IORequestQueue associated with the LUN to which the READ or WRITE command is directed. If, on the other hand, the received I/O command relates to the ALOWI interface, the command is processed in the else-if statements on lines 29-96.

[0067] If the incoming command is a WATCH command, as detected by IORequestHandler on line 29, then IORequestHandler creates a WatchReply object on line 32 and fills in various fields of the WatchReply object on lines 33-36. On line 37, IORequestHandler starts up a separate thread to execute the routine “Watch,” provided below, to carry out monitoring of set of LUNs according to the parameters contained in the WATCH command dequeued from the IORequestQueue. A separate thread is started monitoring may continue for a lengthy period of time. In the meantime, on lines 38-44, IORequestHandler prepares a second WatchReply with an I/O status of “QUEUED” and queues the second WatchReply object to the outQueue to return to the host computer from which the WATCH command was received.

[0068] If the dequeued I/O command is a REARRANGE command, as detected on line 46 by IORequestHandler, then IORequestHandler carrier out processing similar to that which occurs for a WATCH command, the difference being that a thread is started to execute the routine “rearrange,” on line 55, to rearrange a set of LUNs according to a proposed rearrangement provided in the REARRANGE command.

[0069] If the dequeued I/O request represents a MOVELUN command, as detected by IORequestHandler on line 64, then IORequestHandler prepares a RearrangeOrMoveReply object on line 68, sets various fields of the RearrangeOrMoveReply object on lines 69-72, and then calls the LUN Manager routine “LunManagerMove” on line 73 to forcibly separate a LUN indicated in the physical LUN translation supplied in the MoveRequest from disks that include the physical mapping also supplied in the physical LUN translation in the MOVELUN command, as discussed above. Depending on the outcome of the routine “LunManagerMove,” IORequestHandler sets the I/O status of the RearrangeOrMoveReply object to SUCCESS, on line 74, or FAILURE, on line 75, and then queues the RearrangeOrMoveReply to the outQueue for return to the requesting host computer.

[0070] If the dequeued I/O request represents a TRANSLATE command, as detected by IORequestHandler on line 79, then IORequestHandler extracts a physical translation for a LUN from the internalArrayMap “map” and returns the physical translation to the requesting host computer via the outQueue on line 94. Finally, on lines 98-108, once one or both of the inQueue and outQueue are terminated, IORequestHandler terminates all of the IOreqQ queues and thus terminates all of the I/OHandler threads launched in the while-loop comprising lines 11-17.

[0071] The routine “watch,” provided above, runs asynchronously, using supplied parameters to call the LUN Manager routine “LunManagerWatch,” on line 6, in order to carry out the WATCH command. Depending on the outcome of the routine “LunManagerWatch,” the routine “watch” sets the I/O status to either SUCCESS, on line 10, or to FAILURE, on line 12, and then queues a WatchReply object to the outQueue before returning to the host computer. The routine “rearrange,” also provided above, similarly processes a REARRANGE command by calling the LUN Manager routine “LunManagerRearrange,” on line 5.

[0072] The functional interface provided by the ALOWI to a human user or an application program will next be described in a series of flow-control diagrams. This functional interface comprises the routines “watch,” “rearrange,” “separateAndWatch,” and “physicalLocation.”

[0073] FIG. 8 is a flow-control diagram for the routine “watch.” This routine allows a human user or APP on a host computer to request a disk array to monitor activity within the disk array related to a specified logical object and to return a proposed rearrangement of the LUNs to which the logical object is mapped in order to optimize I/O activity directed to the logical object. In step 801, the routine “watch” receives a logical object name, a time interval, and a buffer address as inputs, the time interval argument specifying the time interval during which the disk array should monitor I/O activity directed to the logical object name, and the buffer address argument specifying the place in which the proposed rearrangement information returned by the disk array will be stored. In step 802, the routine “watch” calls ResolveObject functionality currently provided for host computers, to resolve the logical object into a list of one or more LUNs. In step 803, the routine “watch” prepares a WATCH I/O command, using a WatchRequest object provided in the above C++-like pseudocode implementation, and sends the WATCH command to the disk array via an operating-system-supplied communication interface. In step 804, the routine “watch” receives the response to the WATCH command from the disk array. Note that, in this implementation, the routine “watch” blocks during monitoring by the disk array. In the next implementation, to be described below, an asynchronous thread or process is launched in order to carry out an I/O command. An asynchronous paradigm may also be employed in an alternative implementation of the routine “watch.” If the WATCH is successfully executed by the disk array, as detected by the routine “watch” in step 805, then the routine “watch” copies the returned physicalLunTransList into the buffer described by the buffer address argument in step 801, sets a return value to TRUE, in step 806, and then returns. Otherwise, in step 807, the routine “watch” sets the return value to FALSE and then returns.

[0074] FIG. 9 is a flow-control diagram for the routine “rearrange.” This routine directs the disk array to rearrange the LUNs to which a logical object is mapped according to a proposed rearrangement returned by the disk array in a preceding call to the function “watch” described above. In step 901, the routine “rearrange” receives a buffer pointer, a first time, a second time, and a callback function pointer as arguments. The buffer pointer points to a proposed rearrangement, residing in a physicalLunTransList, the first time argument indicates the time when the rearrange command is to be processed by the disk array, the second time argument indicates a maximum amount of time the disk array should spend processing the rearrange command, and the callback function pointer points to a function to be called when the rearrangement has been executed. Then, in step 902, the routine “rearrange” launches an asynchronous thread or process, depending on the implementation style, to execute the routine “rearrangement_async,” and then returns.

[0075] FIG. 10 is a flow-control diagram for the routine “rearrange_async.” This routine is launched from the previously described routine “rearrange” in step 902. In step 1001, the routine “rearrange_async” receives the arguments passed initially to the routine “rearrange” in step 901 of FIG. 9. In step 1002, the routine “rearrange_async” prepares a RearrangeRequest object using the supplied arguments. In step 1003, the routine “rearrange_async” transmits the REARRANGE command represented by the RearrangeRequest object to the disk array via an operating-system-supplied communications interface. Then, in step 1004, the routine “rearrange_async” waits for, and finally receives, a response from the disk array to the REARRANGE command. If the response contains an I/O status indicating success, as detected by rearrange_async in step 1005, then, in step 1006, rearrange_async calls the callback function, passing to that function a SUCCESS status, and returns. Otherwise, in step 1007, rearrange_async calls the callback function and passes the callback function a FAILURE status and returns. Note that the callback function may, in turn, initiate a number of different events on the host computer to notify either a human user or an APP that the rearrange command has been executed. For example, an email may be sent to a human user, the appearance of an icon on a human user's screen may be altered, a pager number may be dialed and a message transmitted to the pager, or a second callback routine within an APP may be invoked.

[0076] FIG. 11 is a flow-control diagram for the routine “Separate And Watch.” The routine “separateAndWatch” allows a human user or high-level application program to specify the names of two logical objects that the routine then physically separates from one another and subsequently monitors the placement of the logical objects to ensure that the two logical objects remain physically separated. A disk array may constantly remap physical objects, in order to optimize access to the objects, relocate objects around failed disk drives, or for other reasons. Therefore, when two logical objects are separated, their physical locations must be continuously monitored in order to ensure that they are not subsequently remapped partially or fully onto a common disk drive. In step 1101, the routine “separateAndWatch” receives, as arguments, the names of two logical objects to separate as well as a pointer to a callback function. In step 1102, the routine “separateAndWatch” calls the existing ResolveObject functionality on the host computer to translate each logical object name into a list of LUNs onto which the logical object is mapped. In step 1103, the routine “separateAndWatch” calls the routine “TRANSLATE,” described below, to translate the list of LUNs to which each logical object has been resolved in step 1102 to lists of physical extents or, in other words, physical translation lists. In step 1104, the two physical translation lists are compared, via a call to the routine “Compare,” described below, in order to determine whether the two logical objects overlap. If the two logical objects overlap as detected in step 1105, then the routine “separateAndWatch” prepares and transmits a MOVELUN Request to the disk array on which the logical objects are stored in order to physically separate the logical objects in step 1106. Note that, in a complete implementation, the returned I/O status in the response to the MOVELUN command returned to the routine “separateAndWatch” from the disk array to be checked in step 1106 and, if the returned I/O status is not SUCCESS, then the routine “separateAndWatch” should return an error indication and terminate. This error handling is not explicitly shown in the flow-control diagram of FIG. 11 for the sake of brevity, and because similar error handling has been explicitly shown in previous flow-control diagrams and in the C++-like pseudocode implementation. Finally, in step 1107, the routine “separateAndWatch” calls the routine “monitor,” described below, to continuously check that the two logical objects remain physically separated. The routine “monitor” continues to execute asynchronously, while the routine “separateAndWatch” returns following invocation of the routine “monitor.”

[0077] FIG. 12 is a flow-control diagram of the routine “translate.” This routine is called from step 1103 of the routine “separateAndWatch.” The routine “translate,” in step 1201, receives two lists of LUNs that represent the mapping of two logical objects to LUNs within a disk array. In step 1202, the routine “translate” prepares and sends a translate request for the first received list of LUNs to the disk array, and, in step 1203, prepares and sends a translate request to the disk array for the second list of LUNs. In steps 1204 and 1205, the routine “translate” receives the returned physical LUN translations from the disk array in response to the translate request messages sent to the disk array, and stores the returned physical LUN translations for subsequent access by the calling routine.

[0078] FIG. 13 is a flow-control diagram for the routine “compare.” The routine “compare” compares two physical translation lists representing the physical mapping of two logical objects within a disk array in order to determine whether there is any overlap between the physical storage locations of the two logical objects. In step 1301, the routine “compare” receives two physical translation lists as arguments. Steps 1302-1306 together compose two nested while-loops that operate to compare each extent in the first physical translation list with each extent in the second physical translation list. If any of the comparisons indicate an overlap between a physical extent of the first translation list with a physical extent of the second physical translation list, as detected in step 1304, then the routine “compare” returns a value of TRUE. Otherwise, the routine “compare” returns the value FALSE.

[0079] FIG. 14 is a flow-control diagram for the routine “monitor.” This routine is called in step 1107 of the routine “separateAndWatch.” The routine “monitor” runs asynchronously, continuously monitoring the physical separation of two logical objects. If, at any point, the routine “monitor” detects that the two logical objects partially or completely physically overlap, then the routine “monitor” notifies either a human user or an APP, via a callback function, to allow the human-user or APP to take appropriate action to either re-separate the logical objects or to otherwise provide for the possibility that both logical objects may be irretrievably corrupted by a single disk failure. In step 1401, the routine “monitor” receives the names of two logical objects and a pointer to a callback function. In step 1402, the routine “monitor” waits for some specific time interval, as it is not essential for the monitoring to run continuously, but only that physical separation of the two logical objects is tracked at regular time intervals. In step 1403, the routine “monitor” calls existing ResolveObject functionality on the host computer to resolve each logical object into a LUN list. In step 1404, the routine “monitor” calls the routine “translate,” described above, and in step 1405, the routine “monitor” calls the routine “compare,” also described above. The result of calling these two routines is a Boolean value indicating whether or not the two logical objects physically overlap. If the two logical objects physically overlap, as detected in step 1406, then the routine “monitor,” in step 1407, calls the callback function in order to alert either a human user or an APP to the detected physical overlap. Otherwise, the routine “monitor” loops back to step 1402.

[0080] FIG. 15 is a flow-control diagram for the routine “physicalLocation.” This routine resolves a logical object name, provided as an argument in step 1501, into a LUN list in step 1502 and then, in step 1503, obtains a physical mapping for the logical object from a disk array via a TRANSLATE command. In step 1504, the routine “physicalLocation” determines whether or not to graphically display the physical translation. If a graphical display is not indicated, then the physical location is returned. Otherwise, a graphical display is prepared in step 1505 and displayed to a human user. FIG. 16 illustrates an example of a graphical display of the mapping of a logical object onto physical disks within a disk array.

[0081] Although the present invention has been described in terms of a particular embodiment, it is not intended that the invention be limited to this embodiment. Modifications within the spirit of the invention will be apparent to those skilled in the art. For example, an almost limitless number of different types of hardware and software implementations may be used to implement the logical object name translation and logic separation and monitoring functionality provided by the combination of the HLOWI and ALOWI. An almost limitless number of functional interfaces may be provided by the HLOWI and ALOWI that result in the same conceptual functional interfaces provided by the implementations discussed above. Functionality may be moved from the ALOWI to the HLOWI, and vice versa. While the above implementations are related to logical name translation and separation within disk arrays, the same principles can be applied to many different types of mass storage devices. The current invention is not restricted to any particular type of mass storage device. Many different types of design and programming methodologies may be used to accomplish the relatively long-executing monitoring and rearrangement tasks, and many different types of methodologies may be used to return results to a human user or a high-level application program. Processes may launch threads or other processes, which carry out the tasks synchronously, as described above, or processes may simply block, waiting for I/O requests to be executed on a disk array, as also described above. Other paradigms are possible. While the functional interface described above included functions for physically separating and monitoring two logical objects, functions for physically separating and monitoring more than two logical objects are easily implemented in similar fashion, are within the scope of the invention. In the above implementation, callback functions are employed for notification of logical object overlap and other conditions, but shared memory data structures and other techniques may be alternatively employed.

[0082] The foregoing description, for purposes of explanation, used specific nomenclature to provide a thorough understanding of the invention. However, it will be apparent to one skilled in the art that the specific details are not required in order to practice the invention. The foregoing descriptions of specific embodiments of the present invention are presented for purpose of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed. Obviously many modifications and variations are possible in view of the above teachings. The embodiments are shown and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents.