Pooled partition layout and representation

A set of storage devices may interoperate to share a pool of storage space, such as in a Redundant Array of Inexpensive Disks (RAID) scheme. However, the details of the representation of the pool and the allocation of capacity to the pool may enable advantages and/or impose limitations on the storage set. Presented herein are techniques for generating a representing a pooled partition on one or more storage devices featuring a pool configuration representing the pool as a set of spaces manifested by the pool; a set of storage devices sharing the pool; and a set of extents that map physical areas of the storage devices to logical areas of the spaces. The flexibility of these pooling techniques may enable such features as flexible capacity allocation, delayed binding, thin provisioning, and the participation of a storage device in two or more distinct pools shared with different sets of storage devices.

BACKGROUND

Within the field of computing, many scenarios involve a set of one or more storage devices (e.g., platter-based magnetic and/or optical hard disk drives, solid-state storage devices, and nonvolatile memory circuits) that may be allocated in various ways. As a first example, the storage space provided by a storage device may be grouped into one or more partitions, each of which may store data associated with one or more logical drives reflected in an operating environment. As a second example, the capacity of two or more storage devices may be combined in many ways to provide additional storage features, e.g., various Redundant Array of Inexpensive Disks (RAID) schemes that provide features such as improved throughput, automatic mirroring, and automatic parity computations. As a third example, the storage space may be accessible to one or more computers (e.g., a network-attached storage device that is concurrently accessible to several computers on a network). More complex techniques may also be provided by such devices, such as journaled spaces and thin provisioning.

The design choices involved in such scenarios result in metadata indicating the number, types, capacities, allocations, and features provided by the storage devices of the storage set, as well as the pooling arrangements of one or more storage devices. This metadata may be stored in many ways, such as in the memory of a storage controller (e.g., a RAID controller configured to store information about a RAID scheme applied to the storage devices), or in standardized locations on one or more storage disks of the storage set. For example, a storage device may comprise, at the beginning of the storage space, a master boot record (MBR) listing the numbers, locations, sizes, and types of partitions stored on the storage device, and, at the end of the storage space, a logical disk model (LDM) database indicating the logical drives exposed by the partitions.

SUMMARY

The manner of persisting metadata describing a storage set may present various advantages and/or disadvantages. As a first example, metadata stored in the memory of a storage controller may be rapidly accessible, but may complicate the migration of a storage device to a different storage controller or computer (e.g., if a storage device is relocated to a different machine or array, the data on the storage device may be inaccessible if the partition information is not stored on the same storage device). As a second example, storing metadata for an array on only one storage device that subsequently fails may result in loss of data on several or all of the storage devices of the storage set. As a third example, sharing a storage device concurrently with two or more computers, where each may update the metadata, may result in race conditions and/or versioning conflicts among mirrored versions of the metadata. As a fourth example, storing the metadata on a storage device in a new manner may reduce the compatibility and/or accessibility of the storage device with other storage devices and/or computers (e.g., the metadata may not be readable and/or usable by devices that are not accordingly configured), and may result in an overwriting of the metadata and a loss of data and/or functionality. As a fifth example, some representations may not permit a storage device to participate in multiple storage pools that are distributed across different sets of storage devices (e.g., a first pooled partition shared with a first set of storage devices and a second pooled partition shared with a second, different set of storage devices), or to participate in the same storage pool in different roles (e.g., a single storage device featuring a pooled partition including first partition for user data, and a second partition allocated on the same storage device for parity data for the user data).

Presented herein are techniques for storing the metadata identifying the storage devices and storage spaces, as well as the provisions and pooling arrangements, of the storage devices in a storage set. In accordance with these techniques, one or more storage devices may share a pooled partition comprising a pool configuration and a set of extents. The pool configuration may represent the pooled partition as a pool record (identifying the pool); a set of space records representing various spaces manifested by the pooled partition (e.g., volumes for user data, maintenance spaces, and journal spaces storing a journal for the user data); a set of storage device records representing the storage devices participating in the pool; and a set of extent records that map allocations of a physical location within the pooled partition on a storage device to a logical location within a space of the pooled partition. The pool configuration may be stored at the top of the pooled partition of each storage device in a mirrored fashion to provide access to a consistent metadata representation of the pooled partition on any storage device. A request to manifest a space within a pooled partition may be fulfilled by generating a space record representing the space, possibly including a provisioned capacity of the space. Extents may also be allocated and bound to the space in order to allocate physical capacity to the space. This binding may be performed promptly upon creating the space, or may be delayed until the capacity of the space is utilized. Additionally, among the computers accessing the pooled partition, a pool configuration owner may be identified that is exclusively permitted to update the pool configuration, and any requests to alter the pool configuration (e.g., adding a space or allocating an extent to a space) may be forwarded to the pool configuration owner.

This representation of a pooled partition may enable several advantages over other representations of a pooled partition. As a first example, the data within the pooled partition of a storage device may remain accessible if the storage device is relocated (e.g., to a different machine or a different storage array), or if another storage device sharing the pooled partition crashes or becomes unavailable, because the pool configuration is mirrored on each storage device sharing the pooled partition. As a second example, this representation differentiates the provisioning of a space from the allocation of extents, which may be performed in a delayed manner, such as on a just-in-time basis. This differentiation may enable various types of flexibility of the storage set, such as an easy manner of reallocating extents to resize the spaces, a rapid provisioning technique that does not involve the allocation of capacity on the storage devices, and the capability of thin provisioning (e.g., provisioning a space with capacity exceeding the available physical capacity of the storage devices, with the option of fulfilling the provisioned capacity by adding physical storage capacity in the form of additional storage devices as the capacity of the space is exhausted). As a third example, a pooled partition represented in this manner may span two or more partitions on the same storage device. As a fourth example, a first pooled partition may coexist with non-pooled partitions (which may be accessible on storage systems that do not recognize the pooled partition). As a fifth example, a storage device may store two or more pooled partitions that are respectively shared with different sets of other storage devices. As a sixth example, the selection of a pool configuration owner among the computers or devices that may access the storage devices may reduce race conditions that may result in asynchrony of the pool configuration that may otherwise occur in the event that two or more devices concurrently update the pool configuration. These and other advantages may be achievable through the representation of a pooled partition according to the techniques presented herein.

DETAILED DESCRIPTION

Within the field of computing, many scenarios involve a storage device (e.g., a hard disk drive, a solid state storage device, or a volatile or nonvolatile memory circuit) configured to store data on behalf of one or more computers or other devices. The data stored may comprise many types of objects (e.g., files, media objects, media objects, data sets, or database records) and may be organized in various ways (e.g., as a collection of named objects, as a hierarchy, or in a relational manner). However, at a lower level, the storage device is often configured according to a layout that is usable by the device; e.g., regardless of the type and organization of data to be stored, the storage device is often organized (e.g., organized) in a particular manner that computers and other devices are capable of reading. As one such example, the available capacity of the storage device is often organized as a set of partitions, and a partition table generated at the beginning of the storage device indicates the locations, sizes, and types of the partitions. The segregation of the capacity of the storage device into volumes may provide various advantages (e.g., different partitions may isolate different groups of data; may be used to manifest different volumes; or may be differently organized to store different types of data, and/or to store data for access on different computers or devices that utilize different types of partitions).

FIG. 1presents an illustration of an exemplary scenario100featuring a storage device102having data storage capacity organized as a series of partitions104. In this exemplary scenario100, respective partitions104are configured to store various types of user data114, including one or more logical volumes106that may be manifested on a computer or device, further formatted with a file system, and used to store a set of files. For example, the storage device102may comprise a first partition104organized in a basic manner, and capable of storing one logical volume106comprising a master file table108representing a catalog of files comprising the user data112of the logical volume106. The storage device102may also comprise a second partition106organized in an extended manner, and therefore capable of storing more than one logical volume106. For example, the second partition106may include two logical volumes106, each contained in a third partition106(within the extended second partition106) that in turn contains data comprising a logical volume106. Information about the top-level partitions104may be contained in a partition table110stored at the beginning of the available capacity of the storage device102and containing metadata for each partition104, including the physical location where the partition104begins, whether or not the partition104comprises information to enable a computer to boot into an operating environment, and/or a partition type indicator identifying the type of the partition104(e.g., a basic partition type for the first partition104and an extended partition type for the second partition104), and the extended second partition104may precede each contained partition108with a master file table (MFT) comprising metadata about the contained partition108. In this manner, the capacity of the storage device102may be organized as a set of partitions104, each comprising one or more logical volumes106, and may therefore expose compartmentalize the storage capacity of the storage device102into several logical volumes106.

While the exemplary format of partitions104in the exemplary scenario100ofFIG. 1may satisfy some scenarios, it may be desirable to design the format in a manner that enables some additional features. As a first example, it may be desirable to establish a relationship between two or more partitions104, such as a mirrored relationship (where an identical data set is stored in each partition104, and where changes to the data within one partition104are automatically propagated to other partitions104). Such mirroring may promote the durability of the data set in the event of data corruption; e.g., in the event of a corruption of a partition104, or a failure of a storage device102comprising a partition104, the data set may remain intact and accessible if mirrored in a second partition104(possibly on a different storage device102). Mirroring may also improve performance; e.g., a first storage device102may be limited to a set of performance characteristics (e.g., a minimum latency involved in initiating an access request, or a maximum sustainable throughput while accessing the data), and mirroring a data set across two or more storage devices102may enable performance characteristics representing the sum of all of the storage devices102. A second feature that may be enabled by some formats of storage devices102is the spanning of a data set across the partitions104of two or more storage devices102. For example, in the exemplary scenario100ofFIG. 1, the size of a logical volume106is limited to the size of the partition104comprising the logical partition106, which in turn is limited to the available capacity of the storage device102. However, other formats may be enable a pooling of two or more partitions of one or more storage devices102, thereby exceeding the size limitations of any one partition104or storage devices102. The formatting of storage devices102may also be devised to promote error detection and error correction (e.g., for respective data sets, a storage device102may automatically generate and store a set of verifiers, such as checksums, that may be compared with the contents of the data sets to detect and possibly incorrectly written data) and shared access to the data set (e.g., a storage set102may enable multiple computers or other devices without exposing the data set to write-based race conditions, which may result in inconsistent or non-deterministic updates to the data set).

Accordingly, the basic format exhibited in the exemplary scenario100ofFIG. 1may be extended to enable features such as mirroring, concurrent access, fault tolerance, and error detection and correction. For example, a set of storage devices102may be organized according to a Redundant Array of Inexpensive Disks (RAID) scheme, which may be implemented in hardware and/or software to implement such features. As a first example, in a RAID 0 scheme, data stored in several partitions104of several storage devices102is presented as a single logical volume104. As a second example, in a RAID 1 scheme, data stored is automatically mirrored across several partitions104on one or more storage devices102, thereby enabling faster access to the data set and/or fault tolerance in the event that a storage device102or partition104becomes unreliable or inaccessible. As a third example, in a RAID 4 scheme, checksums are computed for respective portions of a data set that may be used to verify the integrity of the data set (e.g., that data written to the data set is consistently read from the data set, and is not inadvertently changed during storage), and/or to recover from a failure of a partition104and/or storage device102(e.g., if a partition104of a storage device102becomes corrupted, or if the storage device102is removed, the data contained in the partition104may be recoverable using the checksums of the missing data and other portions of the data set represented by the checksum). RAID schemes, as well as other format specifications, thereby enable these and other features through the particular organization and accessing of data on the storage devices102.

FIG. 2presents an illustration of an exemplary scenario200featuring a formatting of a set of four storage devices102according to a RAID 4 scheme in order to establish a pool202of capacity having particular storage features. In this exemplary scenario200, respective storage device102are configured to store user data114in a logical volume106extending across several partitions104, and to automatically generate and store parity data204in order to verify the integrity of the user data114and to recover the data set in the event of a failure of a storage device102. Accordingly, each storage device102may store a partition table110at the beginning of the storage device102comprising metadata describing the partitions104of the storage device102. Each storage device102also stores a partition104. The partitions104of the first three storage devices102are configured as a pool202presenting a single logical volume106(e.g., a master file table112and user data114). Additionally, the capacity of a fourth storage device102is included in the pool202but is reserved for parity data204, which is automatically calculated for corresponding data sets stored in the first three storage devices102. For example, for a word of data stored at a particular physical address in the partitions104of the first three storage devices102, a word-length checksum may be computed and stored in the same physical address in the partition104of the fourth storage device102. This formatting of the storage devices RAID 4 layout therefore enables the aggregation of the capacity of the storage devices102to generate a pool202presenting a logical volume106and verifier data that may improve the fault tolerance of the storage set102.

However, the layout in the exemplary scenario200ofFIG. 2may present some limitations. As a first example, a RAID 4 schema may only be capable of pooling storage devices102having matching characteristics; e.g., it may not be possible to apply this schema with storage devices102of varying capacities (e.g., a one-terabyte storage device102and a two-terabyte storage device). This limitation may arise from the computation of checksums on the fourth storage device102for corresponding physical addresses of the data sets on the first three storage devices102; e.g., the algorithm may be unable to adapt these computations (without diminished performance) to storage devices102of different sizes. As a second example, a RAID 4 schema may exhibit diminished consistency, reliability, and/or performance for storage sets comprising storage devices102with different performance characteristics (e.g., even if the storage devices102are identically sized, differences in the latency and throughput characteristics of storage devices102of different makes and/or models may result in problems or diminished performance of the storage set). As a third example, the interdependence of the storage devices102may diminish the portability of any one storage device102. For example, it may not be possible to access the contents of a storage device102if transferred to a different array, because the metadata describing the contents of the storage device102may be interrelated with the other storage devices102and/or the controller thereof (e.g., the metadata describing the pool202may be stored on a separate memory component of a RAID controller, and transferring one or more storage devices102to a different RAID controller may fail to transfer the metadata, resulting in an inaccessibility of the data set). As a fourth example, the formatting of these storage devices102may only be usable by systems (e.g., storage controllers and software) that are configured to support a RAID 4 scheme. As a fifth example, this scheme may utilize all of the capacity of all of the storage devices102. Therefore, it may not be possible to allocate some capacity on these storage devices102for use outside of the pool202, e.g., as a second partition104outside of the pool202, or as a partition104participating in another pool202with the same or other storage devices102. Moreover, it is difficult to implement different RAID schemes on a set of storage devices102; e.g., a RAID controller may be configured to apply one RAID scheme to the entire capacity of all of the storage devices102at its disposal.

FIG. 3presents an illustration of an exemplary scenario300featuring an exemplary formatting of storage devices102in accordance with a Logical Disk Manager (LDM) scheme that may overcome some of the limitations of the exemplary scenario200ofFIG. 2. In this exemplary scenario300, two storage devices102are organized to begin with a partition table110followed by a dynamic partition302comprising a set of subdisks304, representing large, allocated blocks of contiguous physical addresses that may be aggregated to manifest logical volumes106, including a logical volume106spanning both storage devices102and representing a pool202of the capacity of the dynamic partition302of the first storage device102and the dynamic partition302of the second storage device102. The dynamic partition may be logically represented, e.g., as a sequence of logical addresses aggregated from a first subdisk304stored in the dynamic partition302of the first storage device102and a second subdisk304stored in the dynamic partition302of the second storage device102. Though comprising separate blocks of physical addresses on different storage devices102, the subdisks304are aggregated and manifested as a contiguous block of logical addresses. Additionally, the metadata for the pool202is stored in a logical disk manager (LDM) database306located at the end of each storage device102that represents the allocation of the subdisks304of the storage devices102as logical volumes106. For example, in this exemplary scenario300, the logical disk manager database306indicates that the first storage device102comprises two subdisks304, and that the second storage device102comprises one subdisk304, but that the first subdisk304of the first storage devices102is manifested as a first logical volume106, while the second subdisk304of the first storage device102and the sole subdisk304of the second storage device102are manifested together as a second logical volume106. Moreover, the logical disk manager database306is mirrored on both storage devices102, and is therefore portable with each storage device102to indicate the logical manifestations of the dynamic partitions302contained therein.

The formatting of the storage devices102with a logical disk manager database306may present some advantages. As a first example, as compared with the exemplary scenario100illustrated inFIG. 1, the logical disk manager database306enables the representation of a pool202of subdisks304on multiple storage devices102. Also, as compared with the exemplary scenario200ofFIG. 2, the formatting illustrated in the exemplary scenario300ofFIG. 3may be implemented on storage devices102of different sizes and/or different performance characteristics (e.g., the first and second storage devices102inFIG. 3may have different total capacities generated by different manufacturers with different storage controllers). Additionally, as further compared with the exemplary scenario200illustrated inFIG. 2, the logical disk manager database306may enable the coexistence of a pool202with other partitions104that are not included in the pool202(e.g., the first partition104on the first storage device102), and that may be accessible to and usable by systems (e.g., storage controllers and software) that are not capable of using the logical disk manager database306.

However, the use of a logical disk manager database306to represent a pool202of subdisks304may also present some limitations. As a first example, many logical disk manager databases306are only capable of representing one pool202, and it may be difficult to extend the logical disk manager database306to represent multiple pools202of subdisks304. As a second example, the location of the logical disk manager database306at the end of the storage device104may limit the size of the logical disk manager database306, and expanding the logical disk manager database306may involve rewriting the entire logical disk manager database306at a different location on each storage device102. As a third example, it may be difficult to represent the manifestation of a logical volume106comprising only a portion of a partition104. For example, and as similarly illustrated in the exemplary scenario100ofFIG. 1, each partition104is entirely allocated to one logical volume106. Because of this correspondence, it may be difficult to allocate partitions104in a flexible manner (e.g., distributing the capacity of a partition104across two or more logical volumes106), and resizing a logical volume106(including a subdisk304contained therein) may involve significantly altering the partitions104of the storage device102(e.g., resizing a logical volume106may involve reallocating the partitions104, possibly involving a complete rewriting of the data stored in the partition104).

B. Presented Techniques

Presented herein are techniques for formatting storage devices102that may address some of the limitations of other formatting techniques, including those exhibited by the logical disk manager (LDM) database306in the exemplary scenario inFIG. 3. In accordance with these techniques, a format may be devised that organizes the available capacity of a storage device102in a manner that facilitates the implementation of various storage features (e.g., the generation of one or more pools202of storage capacity shared by multiple storage devices102; the specification and automated application of various coordinated storage features, such as mirroring in a RAID 1 array or checksumming in a RAID 4 array; and concurrent access by multiple computers or devices). Such techniques may also promote the robustness of the storage set stored on the storage devices102(e.g., the preservation of the metadata for a storage device102if relocated to a different storage controller); the flexibility of the organization (e.g., facilitating the resizing of partitions104, the allocation and reallocation of the available capacity of the storage device102, and the compatibility of the organization with other organizational techniques (e.g., enabling a storage device to include both more complex organizational structures, such as a pool202of storage synchronized with other storage devices102, and standardized structures, such as basic partitions104).

Therefore, in accordance with these and other considerations, the techniques presented herein involve organizing a storage device102to include one or more pooled partitions that, respectively, may be shared with other storage devices102and may implement various storage features (e.g., different RAID schemes or other features). In a coarse-granularity view of the storage device102, a pooled partition is allocated in a similar manner as other partitions104, e.g., as a block of available capacity set aside and indexed in the partition table110. Thus, a pooled partition may coexist with other partitions104of different types. However, the capacity of the pooled partition is utilized in a different manner. As a first example, the metadata describing the pooled partition is stored not in a separate structure (e.g., a logical disk manager database306), but within the pooled partition, thereby enabling multiple pooled partitions to be stored on the same storage device102of arbitrarily different types (e.g., shared with different sets of other storage devices102, and/or implementing different RAID schemes or other storage features). As a second example, the pooled partition may define a set of spaces, which may represent different constructs (e.g., logical volumes106storing user data; maintenance metadata for the spaces, such as staleness suggesting a resynchronization or failure suggesting the replacement of a storage device102; or a journal configured a as a temporary store of writes to the storage set). Moreover, rather than allocating the capacity of a partition102entirely to one logical volume106, or in a small number of large, contiguous blocks to a small number of logical volumes106, the capacity of the pooled partition may be allocated in small blocks (referred to herein as “extents”) that may be mapped to respective spaces. These associations may be stored in the pooled partition configuration. Moreover, the associations may facilitate the resizing of spaces (e.g., by allocating or deallocating extents), as well as other features, such as delaying the provisioning and/or binding of extents for the spaces, thereby enabling features such as thin provisioning. These and other features may be achievable through the formatting and organization of storage devices102according to the techniques presented herein.

FIG. 4presents an illustration of an exemplary scenario400featuring an exemplary representation of a storage device102that may enable these and other features. For contrast, in the exemplary scenario300ofFIG. 3, the logical disk manager database306represents the provisioning of the storage devices102as a set of logical volumes106and a set of storage devices102, associated by a set of subdisks304stored in respective dynamic partitions302. In this exemplary scenario400, the provisioning is represented as a pool404(e.g., represented by a pool record storing metadata for the pool404, such as a name of the pool404and identifying an owner of the pool404), and as a set of spaces406manifested from the pool404(e.g., represented by space records storing metadata for respective spaces406, such as a name of the space406, a type of the space406, a provisioned capacity of the space406, and storage features implemented by the space406, such as a RAID scheme). Many types of spaces406may be manifested by the pool404, including a logical volume106providing capacity for user data; a maintenance space410storing metadata about the other spaces406of the pool404, such as health indicators412representing the health (e.g., staleness, failure, or unavailability) of the respective spaces406; a checksum space storing checksums for other spaces406, such as in a RAID 4 scheme; and a journal space configured to a journal where data sets to be written to another space406may be temporarily stored (e.g., in order to promote batch writes and/or reduce the RAID write hole). Physically, the provisioning is represented as a set of storage devices102(e.g., represented by storage device records storing metadata for the storage devices102, including a name and a total capacity), and a set of extents408representing allocated portions of the storage devices102associated with respective spaces406(e.g., represented by an extent record mapping a range of physical addresses of a storage device102to a range of logical addresses of a space406). The pool configuration402thus represents the provisioning of the physical capacity of the storage devices102to the pool404through the association of extents408allocated to the spaces406manifested within the pool404.

FIG. 5presents an illustration of an exemplary scenario500illustrating an organization of storage devices102using the representation illustrated in the exemplary scenario400ofFIG. 4. In this exemplary scenario500, a first storage device102may be configured to store two pools404, the first pool404shared with a second storage device102and the second pool404shared with a third storage device102. The first storage device102begins with a partition table110, followed by a first pooled partition404comprising spaces that are manifested in collaboration with a second pooled partition404stored on the second storage device102. Both pooled partitions404begin with a pool configuration402comprising records describing the provisioning of the storage devices102according to the organization of the representation illustrated inFIG. 4. The pool configuration402identifies a set of spaces406manifested from the pool104, and indicates the extents408(e.g., physical allocations) allocated within the pooled partitions404of the first and second storage devices102respectively mapped to a set of logical addresses of a space406. For example, the first pooled partition404of the first storage device102stores four extents408that are respectively utilized as a maintenance space (e.g., the exemplary maintenance space410illustrated inFIG. 4); two extents408storing user data; and an extent408representing a journal for one or more other extents408and/or spaces406of the pooled partition404. The allocation may provide some flexibility in the provisioning of physical storage space (e.g., extents408) for the logical capacity of a space (e.g., the second space406begins with the second extent408of the first storage device102, continues through a third extent406of the first storage device102, and is logically followed by a second extent408on the second storage device102). The pool configuration402may also represent various types of relationships among the spaces408, such as a mirroring504of the maintenance space of the first storage device102and a corresponding maintenance space within the first pooled partition404of the second storage device102. Moreover, the first pooled partition404on the first storage device102shared with the second storage device102may coexist with a second pooled partition404stored on the first storage device102and share with the third storage device102, as well as a basic partition104.

The organization of the storage devices102in the exemplary scenarios400,500ofFIGS. 4-5, in accordance with the techniques presented herein, may enable some advantages with respect to other organizations (including those presented inFIGS. 1-3). As a first example, the pool configuration402enables the specification of different types of spaces406(e.g., a maintenance space, a user data space, and a journal space), as well as the specification of storage features to be applied to each space406(which enables the use of different storage features, such as different RAID schemes, for different spaces406). As a second example, the pool configuration402may define a set of spaces406manifested by the pool404, but may present some flexibility in the allocation of extents408comprising the physical capacity of the storage devices102to the spaces406of the pool404. For example, by allocating a series of small extents408instead of a large block such as a subdisk304, this organization enables a fine-grain resizing of spaces406through the reassignment of extents408. Additionally, the spaces406may be provisioned with a particular size, but an embodiment may allocate extents408and bind the physical addresses of the extents408to the logical addresses of the spaces406at a later moment, e.g., when a write is received to a location within a space406that is not yet bound to an extent404. These concepts of delayed allocation and delayed binding may enable a rapid completion of the formatting of the storage devices102(e.g., not having to allocate and initialize all of the extents408upon receiving a request to create a space406) and overprovisioning (e.g., creating a space406with a defined capacity exceeding the available capacity508of the storage devices102, and when the used capacity of the space406exhausts the available capacity508, prompting a user to add capacity to the storage set). These and other features may be achievable through the organization of the storage devices102as illustrated in the exemplary scenarios400,500ofFIGS. 4-5and in accordance with the techniques presented herein.

FIG. 6presents an illustration of an exemplary embodiment of these techniques, illustrated as an exemplary method600of organizing a storage set comprising at least two storage devices102. The exemplary method600may be implemented, e.g., as a set of instructions stored in a memory component of a device (e.g., a memory circuit, a platter of a hard disk drive, a solid-state memory component, or a magnetic or optical disc) that, when executed by a processor of a device, cause the device to perform the techniques presented herein. The exemplary method600begins at602and involves executing604the instructions on the processor. Specifically, the instructions are configured to, within a storage region of at least two pooled storage devices102, generate606a pooled partition502comprising a pool configuration402. The pool configuration402specifies608,610the pooled storage devices102storing the pooled partition402, and at least one space406represented within the pooled partition402. The instructions are also configured to, upon receiving612a request to allocate an extent408for a space406, allocate614an extent408for the space406within the pooled partition402, and associate616the extent408with the space406in the pool configuration402. In this manner, the instructions achieve the organization of the storage device102according to the techniques presented herein, and the exemplary method600so ends at618.

Another embodiment involves a computer-readable medium comprising processor-executable instructions configured to apply the techniques presented herein. Such computer-readable media may include, e.g., computer-readable storage media involving a tangible device, such as a memory semiconductor (e.g., a semiconductor utilizing static random access memory (SRAM), dynamic random access memory (DRAM), and/or synchronous dynamic random access memory (SDRAM) technologies), a platter of a hard disk drive, a flash memory device, or a magnetic or optical disc (such as a CD-R, DVD-R, or floppy disc), encoding a set of computer-readable instructions that, when executed by a processor of a device, cause the device to implement the techniques presented herein. Such computer-readable media may also include (as a class of technologies that are distinct from computer-readable storage media) various types of communications media, such as a signal that may be propagated through various physical phenomena (e.g., an electromagnetic signal, a sound wave signal, or an optical signal) and in various wired scenarios (e.g., via an Ethernet or fiber optic cable) and/or wireless scenarios (e.g., a wireless local area network (WLAN) such as WiFi, a personal area network (PAN) such as Bluetooth, or a cellular or radio network), and which encodes a set of computer-readable instructions that, when executed by a processor of a device, cause the device to implement the techniques presented herein.

An exemplary computer-readable medium that may be devised in these ways is illustrated inFIG. 7, wherein the implementation700comprises a computer-readable medium702(e.g., a CD-R, DVD-R, or a platter of a hard disk drive), on which is encoded computer-readable data704. This computer-readable data704in turn comprises a set of computer instructions706configured to operate according to the principles set forth herein. In one such embodiment, the processor-executable instructions706may, when executed by a processor712of a device710, cause the device710to perform a method of organizing the capacities of storage devices102, such as the exemplary method600ofFIG. 6. Some embodiments of this computer-readable medium may comprise a nontransitory computer-readable storage medium (e.g., a hard disk drive, an optical disc, or a flash memory device) that is configured to store processor-executable instructions configured in this manner. Many such computer-readable media may be devised by those of ordinary skill in the art that are configured to operate in accordance with the techniques presented herein.

The techniques discussed herein may be devised with variations in many aspects, and some variations may present additional advantages and/or reduce disadvantages with respect to other variations of these and other techniques. Moreover, some variations may be implemented in combination, and some combinations may feature additional advantages and/or reduced disadvantages through synergistic cooperation. The variations may be incorporated in various embodiments to confer individual and/or synergistic advantages upon such embodiments.

A first aspect that may vary among embodiments of these techniques relates to the scenarios wherein such techniques may be utilized. As a first variation of this first aspect, these techniques may be used with many types of storage devices102, including hard disk drives, solid-state storage devices, nonvolatile memory circuits, tape-based storage devices, and magnetic and optical discs. Such storage devices102may also be directly connected to a device710(such as a computer) implementing these techniques; may be accessible through a wired or wireless local area network (e.g., an 802.11 WiFi network or ad-hoc connection, or an infrared connection); and/or may be accessible through a wired or wireless wide-area network (e.g., a cellular network or the internet). Moreover, these techniques may be used with two or more storage devices102operating independently (e.g., storage devices106that are accessed independently through a software process); operating with loose interoperation (e.g., storage devices102that operate independently but that are informed of and may communicate with the other storage devices102sharing the storage set); or operating with tight interoperation (e.g., a Redundant Array of Inexpensive Disks (RAID) controller managing several storage devices106as components of a storage system). As a second variation of this first aspect, these techniques may be used in conjunction with many types of storage sets comprising various types of data sets, including binary storage systems storing various types of binary objects; file systems storing files; media libraries storing media objects; object systems storing many types of objects; databases storing records; and email systems storing email messages. As a third variation of this first aspect, portions or all of these techniques may be implemented within one or more components within the computing environment, such as a set of software instructions stored in a volatile or nonvolatile of a computer or device having access to the storage devices102(e.g., an operating system process or a hardware driver); by a storage system configured to interface with the storage devices102(e.g., a RAID controller); or in respective storage devices102of the storage set.

As a fourth variation of this first aspect, these techniques for organizing the capacities of storage devices104may achieve some results that may be difficult to achieve with other techniques (such as those illustrated inFIGS. 1-3). As a first example, these techniques may enable the generation of a pooled partition502spanning and aggregating at least two partitions104on the first storage device102. As a second example, these techniques may enable the generation of a space406comprising at least two extents408stored in the pooled partition502on a first storage device102, as well as at least one extent408stored in the pooled partition502on a second storage device102. As a third example, among a set of three storage devices102, these techniques may enable a first storage device102to share a first pool404with the second storage device102and not the third storage device102, and to share a second storage pool404with the third storage device102and not the second storage device102. This type of sharing may not be achievable through the use of other techniques, such as a logical disk manager database306, and in particular may not have enabled the storage devices102sharing a first pool404to update the pool configuration402in a manner that is isolated from updating the pool configuration402of a second pool404shared with a different set of storage devices102. Many such storage scenarios may be achieved through the organization of the storage devices102in accordance with the techniques presented herein.

D2. Pool Configuration

A second aspect that may vary among embodiments of these techniques relates to the nature and use of the pool configuration402to represent the pool404shared by the storage devices102. As a first variation of this second aspect, the pool configuration402may be stored on one storage device102, or may be mirrored on the storage devices102storing the pool404. As a second variation of this second aspect, a pooled partition502may be identified on a storage device102in many ways. For example, the storage device102may comprise a partition table110specifying the locations, sizes, and partition type identifiers of respective partitions104, and the pooled partition502may be identified in the partition table with a pooled partition type identifier, which may be understandable and usable by devices710configured to utilize pooled partitions502, and may be ignored (and therefore not misused) by other types of devices710.

As a third variation of this second aspect, the pool configuration402may be stored in many areas of the pooled partition502, including at the beginning of the pooled partition502, at the end of the pooled partition502, or at a defined or identifiable location in the pooled partition502. It may be advantageous to position the pool configuration402at the beginning of the pooled partition502for easy access and/or to enable the growth of the pool configuration402(in contrast with positioning the pool configuration402at the end of the pooled partition502, where growth may be difficult to achieve without rewriting the pool configuration402at a different location in the pool pooled partition502). As a fourth variation of this second aspect, the pool configuration502may be structured in many ways, such as a relational database, a hierarchically structured document (e.g., an Extensible Markup Language (XML) document), or a table. As a fifth variation of this second aspect, the pool configuration502may contain various types of metadata describing the respective entities (e.g., the pool402, the spaces406, the extents408, and the storage devices102), including names, manufacturers, models, capacities, performance characteristics, and uses. In particular, the pool configuration502may specify a space type identifier to identify the types of respective spaces406, such as a user space type identifier for a space406storing user data; a checksum space identifier for a space406storing the checksums (or other types of verifiers) of other spaces406; and a journal space type identifier for a space406used as a journal for storing writes to be applied to other spaces406. Additionally, spaces406may identify a parent space406to identify a sequential or nesting relationship (e.g., a second user data space406that is contiguous with a first user data space406, or a journal space identifying a parent space for which the journal space stores journal updates to be applied to the parent space).

As a sixth variation of this second aspect, the extents408may be specified as a block of physical addresses within the pooled partition502, either using a fixed physical location on the storage device102(e.g., track and sector), a physical address within the sequence of physical addresses on the storage device102(e.g., a physical address range), or an offset within the pooled partition502(e.g., the offset from the starting physical address of the pooled partition502); and may also associate the address range with a logical address range within a space406(e.g., specifying a starting logical address and a length or an ending logical address).

As a seventh variation of this second aspect, the allocation and binding of extents408to spaces406may be achieved in various ways.FIGS. 8-10present some alternative scenarios for achieving this binding. (Each of these figures presents the state of a storage device102at two time points, illustrated respectively as the left and right portions of the figure.) In the exemplary scenario800ofFIG. 8, at a first time point802, the storage device102comprises a pooled partition502storing a pool configuration402for a pool404, as well as a record of the storage device102storing the pool404, in addition to a large amount of available capacity508. At a second time point804, when a space allocation request806to generate a space406to store user data is received, the pool configuration402may be updated to add a record for the space406, including its type and provisioned capacity. Additionally, at this second time point804, two extents408may be created from the available capacity508of the pooled partition502, and the pool configuration402may be updated to add records for the extents408that bind the extents408to logical locations of the space406. In this manner, the extents408for a space406may be promptly allocated and available for use.

Alternatively, the binding of extents408for a space406may be delayed, and may be performed on a just-in-time basis. For example, as illustrated in the exemplary scenario900ofFIG. 9, at a first time point902, a space allocation request may be received to create a space406, and a record for the space406may be created within the pool configuration402. However, the capacity of the space406may not be fully allocated at the first time point902; for example, at the first time point902, only one extent408may be allocated, but other portions of the space406(e.g., other address blocks). However, at a second time point904, when a request is received to write to a particular address of the space406for which an extent408has not yet been allocated, a second extent408may be allocated from the available capacity508of the pooled partition502and bound to the space406in the extent record408within the pool configuration404. This delayed allocation may enable a faster fulfillment of the request to create the space406(since fewer than all extents408have to be allocated at the first time point902), and/or may enable thin provisioning, wherein space406may be provisioned with a provisioned size that is greater than a sum of the extent sizes of the extents408bound to the space406and an available capacity508of the storage devices102sharing the pool404.

FIG. 10presents an illustration of an exemplary scenario1000comprising a further variation in the allocation of spaces406, wherein the allocation of extents408for a space406may be separated from the binding of the extents408to particular logical locations of the space406. In this exemplary scenario1000, at a first time point1002, the storage device102comprises a pooled partition502having a space406for which two extents408have been allocated. However, the extents408have not been mapped to particular logical locations within the space406, but are simply reserved as available capacity for the space406. This reservation may be performed, e.g., upon receiving the request to create the space406, so that some capacity is reserved and available for use, even if less than all of the provisioned capacity of the space406is reserved and the addresses within which data is to be written to the space406are not yet known. Accordingly, at a second time point1004, when a write request is received to write to a logical address in the space406for which an extent408has not yet been bound, one of the unbound extents408may be selected and bound to the location of the space406comprising the logical address specified in the write request. In this manner, the binding of spaces406to extents408may be deferred without compromising the availability of capacity for the space406. In these and other ways, extents408may be allocated to spaces406to enable various features such as improved performance and thin provisioning. Those of ordinary skill in the art may devise many variations in the use of the pool configuration408while implementing the techniques presented herein.

D3. Pool Configuration Owner

A third aspect that may vary among embodiments of these techniques relates to the identification of a pool owner of the pool404. For example, among the computers or other devices710having access to the storage devices102comprising a pool, a pool configuration owner may be elected that has exclusively write access among the computers to the pool configuration402. Upon receiving a request to update the pool configuration402(e.g., a request to create a space406or bind an extent408to a space406), a computer may determine whether it is the pool configuration owner, and if not, may forward the request to the pool configuration owner. Moreover, if the pool configuration owner becomes unresponsive or unavailable, then the other computers may, upon detecting the failure of the pool configuration owner, identify a substitute pool configuration owner among the computers (e.g., electing a new pool configuration owner). This election may enable updates to the pool configuration402to be performed in a manner that avoids conflicting updates arising from race conditions, which may leave the pool configuration402in an inconsistent state. Those of ordinary skill in the art may envision and utilize many variations may be identified in the manner of updating the pool configuration402to protect the integrity of the pool configuration402and the pool404from such conditions.

E. Computing Environment

FIG. 11presents an illustration of an exemplary computing environment within a computing device1102wherein the techniques presented herein may be implemented. Example computing devices include, but are not limited to, personal computers, server computers, hand-held or laptop devices, mobile devices (such as mobile phones, Personal Digital Assistants (PDAs), media players, and the like), multiprocessor systems, consumer electronics, mini computers, mainframe computers, and distributed computing environments that include any of the above systems or devices.

FIG. 11illustrates an example of a system1100comprising a computing device1102configured to implement one or more embodiments provided herein. In one configuration, the computing device1102includes at least one processor1106and at least one memory component1108. Depending on the exact configuration and type of computing device, the memory component1108may be volatile (such as RAM, for example), non-volatile (such as ROM, flash memory, etc., for example) or an intermediate or hybrid type of memory component. This configuration is illustrated inFIG. 11by dashed line1104.

In some embodiments, device1102may include additional features and/or functionality. For example, device1102may include one or more additional storage components1110, including, but not limited to, a hard disk drive, a solid-state storage device, and/or other removable or non-removable magnetic or optical media. In one embodiment, computer-readable and processor-executable instructions implementing one or more embodiments provided herein are stored in the storage component1110. The storage component1110may also store other data objects, such as components of an operating system, executable binaries comprising one or more applications, programming libraries (e.g., application programming interfaces (APIs), media objects, and documentation. The computer-readable instructions may be loaded in the memory component1108for execution by the processor1106.

The computing device1102may also include one or more communication components1116that allows the computing device1102to communicate with other devices. The one or more communication components1116may comprise (e.g.) a modem, a Network Interface Card (NIC), a radiofrequency transmitter/receiver, an infrared port, and a universal serial bus (USB) USB connection. Such communication components1116may comprise a wired connection (connecting to a network through a physical cord, cable, or wire) or a wireless connection (communicating wirelessly with a networking device, such as through visible light, infrared, or one or more radiofrequencies.

The computing device1102may include one or more input components1114, such as keyboard, mouse, pen, voice input device, touch input device, infrared cameras, or video input devices, and/or one or more output components1112, such as one or more displays, speakers, and printers. The input components1114and/or output components1112may be connected to the computing device1102via a wired connection, a wireless connection, or any combination thereof. In one embodiment, an input component1114or an output component1112from another computing device may be used as input components1114and/or output components1112for the computing device1102.

The components of the computing device1102may be connected by various interconnects, such as a bus. Such interconnects may include a Peripheral Component Interconnect (PCI), such as PCI Express, a Universal Serial Bus (USB), firewire (IEEE 1394), an optical bus structure, and the like. In another embodiment, components of the computing device1102may be interconnected by a network. For example, the memory component1108may be comprised of multiple physical memory units located in different physical locations interconnected by a network.

Those skilled in the art will realize that storage devices utilized to store computer readable instructions may be distributed across a network. For example, a computing device1120accessible via a network1118may store computer readable instructions to implement one or more embodiments provided herein. The computing device1102may access the computing device1120and download a part or all of the computer readable instructions for execution. Alternatively, the computing device1102may download pieces of the computer readable instructions, as needed, or some instructions may be executed at the computing device1102and some at computing device1120.

F. Usage of Terms