Patent Description:
<CIT> describes a method for storing data, consisting of distributing a first plurality of groups of logical addresses among one or more storage devices in a storage system, receiving a second plurality of data-sets containing the data to be stored, and assigning each data-set among the plurality of data-sets a random number chosen from a first plurality of different numbers. The method further consists of partitioning each data-set into multiple partitions, so that each partition among the multiple partitions receives a sequential partition number, assigning each partition within each data-set to be stored at a specific group of logical addresses in the storage system in accordance with the sequential partition number of the partition and the random number assigned to the data-set, and storing each partition in the storage system at the assigned specific group of logical addresses.

<CIT> describes a method, system, and article of manufacture, where a plurality of extents are stored in a first set of storage units coupled to a controller. A determination is made that a second set of storage units has been coupled to the controller. The plurality of extents are distributed among all storage units included in the first set of storage units and the second set of storage units.

<CIT> describes a disk control system and data rearrangement method in which each logical stripe is subjected to a judgment whether or not it should be selected as object of repack (rearrangement) by referring to an address conversion table. For the judgment, alpha representing the percentage of valid logical block numbers and beta representing the percentage of the consecutive logical address numbers of adjacently located logical blocks are computationally determined. Each logical stripe that satisfies the requirement that "alpha is not smaller than a predetermined value A and beta is not greater than a predetermined value B" is subjected to a repack processing operation. As a result, logical stripes whose valid blocks are physically distributed can be subjected to a repack processing operation with priority.

<CIT> describes parity declustered storage device arrays having partition groups. In an exemplary embodiment, the storage system includes a storage device array, such as disk array. Each storage device is divided into partitions. Each partition includes stripe units, such as hundreds or thousands of stripe units in exemplary embodiments. The storage system also includes a physical array controller coupled to the storage device array. In an exemplary embodiment, the array controller includes a partition group lookup table and stores and retrieves data and parity in the storage devices based on the partition group lookup table. In this exemplary embodiment, the array controller also includes a stripe lookup table and/or a log. In an exemplary embodiment, the partition group lookup table and the stripe lookup table take up less memory (e.g., by an order of magnitude) than a single-level stripe map conveying the same information.

The scope of the invention is defined by the independent claims.

As will be described in greater detail below, the instant disclosure describes various systems and methods for rebalancing striped information across multiple storage devices by, for example, performing optimized logical striping.

According to a first aspect there is provided a computer-implemented method for facilitating the rebalancing of striped information across multiple storage devices, to be performed by a computing device comprising at least one processor, the method comprising: allocating, by the computing device, "Y" contiguous storage spaces on "Y" physical storage devices of multiple storage devices, thereby to create "Y" physical stripes across the "Y" physical storage devices; characterized in that the method additionally comprises: dividing, by the computing device, the "Y" contiguous storage spaces into "N" chunks, wherein: "N" is a value equal to a least common multiple of {y, <NUM>, <NUM>, <NUM>,. , x}, "x" is equal to a maximum number of logical stripes of chunks, and "y" is equal to a minimum number of logical stripes of chunks; allocating, by the computing device, the "N" chunks to "X" logical stripes of chunks; allocating, by the computing device, each of a first "Y" logical stripes of chunks of the "X" logical stripes of chunks to a respective physical stripe in each of the "Y" physical stripes; dividing, by the computing device, remaining logical stripes of chunks by "Y" to form respective sub-groups of logical stripes of chunks; and allocating, by the computing device, the respective sub-groups of logical stripes of chunks across the "Y" physical stripes.

According to a second aspect there is provided a system comprising: a first allocating module, stored in memory, that allocates "Y" contiguous storage spaces on "Y" physical storage devices of multiple storage devices, thereby to create "Y" physical stripes across the "Y" physical storage devices; a dividing module, stored in the memory, that divides the "Y" contiguous storage spaces into "N" chunks wherein: "N" is a value equal to a least common multiple of {y, <NUM>, <NUM>, <NUM>,. , x}, "x" is equal to a maximum number of logical stripes of chunks, and "y" is equal to a minimum number of logical stripes of chunks; a second allocating module, stored in the memory, that allocates the "N" chunks to "X" logical stripes of chunks; a third allocating module, stored in the memory, that allocates each of the first "Y" logical stripes of chunks of the "X" logical stripes of chunks to a respective physical stripe in each of the "Y" physical stripes; wherein the dividing module divides remaining logical stripes of chunks by "Y" to form respective sub-groups of logical stripes of chunks; an "Nth" allocating module, stored in the memory, that allocates the respective sub-groups of logical stripes of chunks across the "Y" physical stripes; and at least one physical processor that executes the first allocating module, the dividing module, the second allocating module, the third allocating module, and the "Nth" allocating module.

According to a third aspect there is provided A computer-readable medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to: allocate "Y" contiguous storage spaces on "Y" physical storage devices of multiple storage devices, thereby to create "Y" physical stripes across the multiple storage devices; divide the "Y" contiguous physical storage spaces into "N" chunks, wherein: "N" is a value equal to a least common multiple of {y, <NUM>, <NUM>, <NUM>,. , x}, "x" is equal to a maximum number of logical stripes of chunks, and "y" is equal to a minimum number of logical stripes of chunks; allocate the "N" chunks to "X" logical stripes of chunks; allocate each of a first "Y" logical stripes of chunks of the "X" logical stripes of chunks to a respective physical stripe in each of the "Y" physical stripes; divide remaining logical stripes of chunks by "Y" to form respective sub-groups of logical stripes of chunks; and allocate the respective sub-groups of logical stripes of chunks across the "Y" physical stripes.

Throughout the drawings, identical reference characters and descriptions indicate similar, but not necessarily identical, elements. While the example embodiments described herein are susceptible to various modifications and alternative forms, specific embodiments have been shown by way of example in the drawings and will be described in detail herein. However, the example embodiments described herein are not intended to be limited to the particular forms disclosed.

The present disclosure is generally directed to systems and methods for rebalancing striped information across multiple storage devices. Provided systems and methods may rebalance striped information across multiple storage devices by performing optimized logical striping, where logical stripes may include subvolumes that may be transferred in balanced quantities across physical stripes prior to changing numbers of multiple storage devices. In embodiments, disclosed techniques may be utilized in connection with cloud-based storage devices.

By doing so, in some examples, the systems and methods described herein may improve the functioning of computing devices by automatically (re)balancing striped information across multiple storage devices, thus enabling cost-effective storage management. Also, in some examples, systems and methods described herein may save power by reducing quantities of data to be transferred. Provided methods may also not require using temporary storage space, may not require moving data to temporary space, may not require serially transferring substantially all data in multiple storage devices, and may not require moving as much data as conventional techniques, thus enabling cost-effective storage management. Provided methods may also move subvolumes of data in parallel (vs serially) and/or may transfer data faster. Also, in some examples, the systems and methods described herein may save power and/or better-manage network bandwidth utilization.

The following will provide, with reference to <FIG>, detailed descriptions of example systems for rebalancing striped information across multiple storage devices. Detailed descriptions of corresponding computer-implemented methods will also be provided in connection with <FIG>. In addition, detailed descriptions of performance of provided techniques relative to conventional techniques will also be provided in connection with <FIG>.

<FIG> is a block diagram of an example system <NUM> for rebalancing striped information across multiple storage devices. As illustrated in this figure, example system <NUM> may include one or more modules <NUM> for performing one or more tasks. As will be explained in greater detail below, modules <NUM> may include a first allocating module <NUM>, a dividing module <NUM>, a second allocating module <NUM>, a third allocating module <NUM>, a distributing module <NUM>, and an "Nth" allocating module <NUM>. Although illustrated as separate elements, one or more of modules <NUM> in <FIG> may represent portions of a single module or application.

In certain embodiments, one or more of modules <NUM> in <FIG> may represent one or more software applications or programs that, when executed by a computing device, may cause the computing device to perform one or more tasks. For example, and as will be described in greater detail below, one or more of modules <NUM> may represent modules stored and configured to run on one or more computing devices, such as the devices illustrated in <FIG> (e.g., computing device <NUM> and/or server <NUM>). One or more of modules <NUM> in <FIG> may also represent all or portions of one or more special-purpose computers configured to perform one or more tasks.

As illustrated in <FIG>, example system <NUM> may also include one or more tangible storage devices, such as storage device <NUM>. Storage device <NUM> generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or computer-readable instructions. In one example, storage device <NUM> may store, load, and/or maintain information indicating one or more of a physical stripe <NUM>, a logical stripe <NUM>, a sub-logical stripe <NUM>, and/or a subvolume <NUM>. In embodiments, subvolume <NUM> may be a part of logical stripe <NUM> in an absence of sub-logical stripe <NUM>. In some examples, storage device <NUM> may generally represent multiple storage devices. Examples of storage device <NUM> include, without limitation, Random Access Memory (RAM), Read Only Memory (ROM), flash memory, Hard Disk Drives (HDDs), Solid-State Drives (SSDs), optical disk drives, caches, a cloud-based storage device, variations or combinations of one or more of the same, and/or any other suitable storage memory.

As illustrated in <FIG>, example system <NUM> may also include one or more physical processors, such as physical processor <NUM>. Physical processor <NUM> generally represents any type or form of hardware-implemented processing unit capable of interpreting and/or executing computer-readable instructions. In one example, physical processor <NUM> may access and/or modify one or more of modules <NUM> stored in memory <NUM>. Additionally or alternatively, physical processor <NUM> may execute one or more of modules <NUM> to facilitate rebalancing striped information across multiple storage devices. Examples of physical processor <NUM> include, without limitation, microprocessors, microcontrollers, Central Processing Units (CPUs), Field-Programmable Gate Arrays (FPGAs) that implement softcore processors, Application-Specific Integrated Circuits (ASICs), portions of one or more of the same, variations or combinations of one or more of the same, or any other suitable physical processor.

As illustrated in <FIG>, example system <NUM> may also include one or more memory devices, such as memory <NUM>. Memory <NUM> generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or computer-readable instructions. In one example, memory <NUM> may store, load, and/or maintain one or more of modules <NUM>. Examples of memory <NUM> include, without limitation, Random Access Memory (RAM), Read Only Memory (ROM), flash memory, Hard Disk Drives (HDDs), Solid-State Drives (SSDs), optical disk drives, caches, variations or combinations of one or more of the same, or any other suitable storage memory.

Example system <NUM> in <FIG> may be implemented in a variety of ways. For example, all or a portion of example system <NUM> may represent portions of example system <NUM> in <FIG>. As shown in <FIG>, system <NUM> may include a computing device <NUM> in communication with a server <NUM> via a network <NUM>. Optional cloud storage device <NUM> may be coupled to computing device <NUM> and/or server <NUM>, such as via network <NUM>. In one example, all or a portion of functionality of modules <NUM> may be performed by computing device <NUM>, server <NUM>, and/or any other suitable computing system. As will be described in greater detail below, one or more of modules <NUM> from <FIG> may, when executed by at least one processor of computing device <NUM> and/or server <NUM>, enable computing device <NUM> and/or server <NUM> to rebalance striped information across multiple storage devices.

Computing device <NUM> generally represents any type or form of computing device capable of reading computer-executable instructions. In some examples, computing device <NUM> may represent a computer running storage management software. Additional examples of computing device <NUM> include, without limitation, laptops, tablets, desktops, servers, cellular phones, Personal Digital Assistants (PDAs), multimedia players, embedded systems, wearable devices (e.g., smart watches, smart glasses, etc.), smart vehicles, so-called Internet-of-Things devices (e.g., smart appliances, etc.), gaming consoles, variations or combinations of one or more of the same, or any other suitable computing device.

Network <NUM> generally represents any medium or architecture capable of facilitating communication or data transfer. In one example, network <NUM> may facilitate communication between computing device <NUM> and server <NUM>. In this example, network <NUM> may facilitate communication or data transfer using wireless and/or wired connections. Examples of network <NUM> include, without limitation, an intranet, a Wide Area Network (WAN), a Local Area Network (LAN), a Personal Area Network (PAN), the Internet, Power Line Communications (PLC), a cellular network (e.g., a Global System for Mobile Communications (GSM) network), portions of one or more of the same, variations or combinations of one or more of the same, or any other suitable network.

Server <NUM> generally represents any type or form of computing device that is capable of reading computer-executable instructions. In some examples, server <NUM> may represent a computer running storage management software. Additional examples of server <NUM> include, without limitation, storage servers, database servers, application servers, and/or web servers configured to run certain software applications and/or provide various storage, database, and/or web services. Although illustrated as a single entity in <FIG>, server <NUM> may include and/or represent a plurality of servers that work and/or operate in conjunction with one another.

Cloud storage device <NUM> generally represents any type or form of computing device that is capable of reading computer-executable instructions and/or storing information. In some examples, cloud storage device <NUM> may represent a computer running storage management software. Additional examples of cloud storage device <NUM> include, without limitation, one or more storage servers, database servers, application servers, and/or web servers configured to run certain software applications and/or provide various storage, database, and/or web services. Although illustrated as a single entity in <FIG>, cloud storage device <NUM> may include and/or represent a plurality of servers that work and/or operate in conjunction with one another.

In some examples, cloud storage device <NUM> may store one or more of physical stripe <NUM>, logical stripe <NUM>, sub-logical stripe <NUM>, and/or subvolume <NUM>.

Many other devices or subsystems may be connected to system <NUM> in <FIG> and/or system <NUM> in <FIG>. Conversely, all of the components and devices illustrated in <FIG> and <FIG> need not be present to practice the embodiments described and/or illustrated herein. The devices and subsystems referenced above may also be interconnected in different ways from that shown in <FIG>. Systems <NUM> and <NUM> may also employ any number of software, firmware, and/or hardware configurations. For example, one or more of the example embodiments disclosed herein may be encoded as a computer program (also referred to as computer software, software applications, computer-readable instructions, and/or computer control logic) on a computer-readable medium.

The term "computer-readable medium," as used herein, generally refers to any form of device, carrier, or medium capable of storing or carrying computer-readable instructions. Examples of computer-readable media include, without limitation, transmission-type media, such as carrier waves, and non-transitory-type media, such as magnetic-storage media (e.g., hard disk drives, tape drives, and floppy disks), optical-storage media (e.g., Compact Disks (CDs), Digital Video Disks (DVDs), and BLU-RAY disks), electronic-storage media (e.g., solid-state drives and flash media), and other distribution systems.

<FIG> is a flow diagram of an example computer-implemented method <NUM> for rebalancing striped information across multiple storage devices. The steps shown in <FIG> may be performed by any suitable computer-executable code and/or computing system, including system <NUM> in <FIG>, system <NUM> in <FIG>, and/or variations or combinations of one or more of the same. In one example, each of the steps shown in <FIG> may represent an algorithm whose structure includes and/or is represented by multiple sub-steps, examples of which will be provided in greater detail below. In embodiments, method <NUM> may start with allocating subvolumes <NUM> to multiple storage devices, such as storage device <NUM> and/or cloud storage device <NUM>.

As illustrated in <FIG>, at step <NUM> one or more of the systems described herein
"Y" contiguous storage spaces (e.g., create "Y" physical stripes) on "Y" physical devices (e.g., on multiple storage devices). The systems described herein may perform step <NUM> in a variety of ways. In an example, first allocating module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, allocate "Y" contiguous storage spaces on "Y" physical devices, such as storage devices <NUM> in computing device <NUM>, storage devices <NUM> in server <NUM>, and/or storage devices in cloud storage device <NUM>. For example, first allocating module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, create "Y" physical stripes <NUM> on multiple storage devices <NUM>, such as storage devices <NUM> in computing device <NUM>, storage devices <NUM> in server <NUM>, and/or storage devices in cloud storage device <NUM>. In some examples, "Y" is an integer.

In an example, physical stripes <NUM> may already be present on multiple storage devices <NUM> prior to initiating method <NUM>.

As illustrated in <FIG>, at step <NUM> one or more of the systems described herein
the "Y" continuous storage spaces into "N" subvolumes or chunks. The systems described herein may perform step <NUM> in a variety of ways. In an example, dividing module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, divide the "Y" continuous storage spaces into "N" subvolumes <NUM>. For example, dividing module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, divide storage space in multiple storage devices <NUM> into "N" subvolumes <NUM>. In some examples, "N" is an integer.

In an example, dividing may include calculating "N" as a least common multiple of {<NUM>, <NUM>,. X}, where "X" is a maximum number of logical stripes. In some examples, "X" is an integer number.

The term "subvolume," as used herein, may generally refer to like-sized units of information storage space. Examples of subvolumes are described herein with respect to <FIG>.

As illustrated in <FIG>, at step <NUM> one or more of the systems described herein
"N" subvolumes to "X" logical stripes. The systems described herein may perform step <NUM> in a variety of ways. For example, second allocating module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, allocate "N" subvolumes <NUM> to "X" logical stripes <NUM>.

In an example, method <NUM> may include tagging at least one logical stripe with a logical stripe identifier.

In some embodiments, method <NUM> may include allocating an equal number of subvolumes <NUM> to each of the "X" logical stripes.

The term "logical stripe," as used herein, generally refers to a logical group of subvolumes. Examples of logical stripes are described herein with respect to <FIG>.

As illustrated in <FIG>, at step <NUM> one or more of the systems described herein
each of first "Y" logical stripes to a respective physical stripe in each of "Y" physical stripes. In other words, lower-numbered logical stripes may be stored substantially in their entireties on a respective physical stripe, such as with one logical stripe being stored substantially entirely on each respective physical stripe. The systems described herein may perform step <NUM> in a variety of ways. For example, third allocating module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, allocate each of first "Y" logical stripes <NUM> to a respective physical stripe in each of "Y" physical stripes <NUM>.

As illustrated in <FIG>, at step <NUM> one or more of the systems described herein
remaining subvolumes to respective logical stripes, and in some cases, to respective sub-logical stripes. The systems described herein may perform step <NUM> in a variety of ways. In an example, distributing module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, distribute remaining subvolumes <NUM> to respective logical stripes <NUM>, and in some cases, to respective sub-logical stripes <NUM>. For example, distributing module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, divide remaining logical stripes <NUM> by "Y" to form respective sub-logical stripes <NUM>.

In an example, method <NUM> may include tagging at least one sub-logical stripe with a sub-logical stripe identifier.

The term "sub-logical stripe," as used herein, generally refers to a sub-group of subvolumes in a logical stripe. In an example, subvolumes in a sub-logical stripe may be stored across different physical stripes.

As illustrated in <FIG>, at step <NUM> one or more of the systems described herein
the respective subvolumes across the "Y" physical stripes. The systems described herein may perform step <NUM> in a variety of ways. In an example, "Nth" allocating module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, allocate the respective subvolumes <NUM> across the "Y" physical stripes <NUM>. For example, "Nth" allocating module <NUM> may, as part of computing device <NUM> and/or server <NUM> in <FIG>, allocate respective sub-logical stripes <NUM> across "Y" physical stripes <NUM> for each logical stripe <NUM>. In an embodiment, "N" is an integer such as four.

In an example, method <NUM> may include checking at least one subvolume for overuse and may include moving, when a subvolume is identified as overused, the overused subvolume to a different physical stripe. In an embodiment, when a logical stripe includes an overused subvolume, the logical stripe may be identified as an overused stripe.

<FIG> is a diagram of an example allocation of subvolumes across multiple storage devices <NUM>. In <FIG>, "Pi" refers to a respective physical stripe "i" (e.g., "P0" represents physical stripe zero). Further, "Lj" refers to a respective logical stripe "j" (e.g., "L0" represents logical stripe zero). In <FIG>, subvolumes are represented by blocks including a respective number (e.g., physical stripe P0 includes logical strip L0, which includes subvolume zero). Accordingly, as a result of performing method <NUM>, logical stripe L0 is stored on physical stripe P0 and includes subvolumes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. In this example, logical stripe L0 does not include any sub-logical stripes. Further, logical stripe L1 is stored on physical stripe P1 and includes subvolumes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. In this example, logical stripe L1 does not include any sub-logical stripes. Additionally, logical stripe L0 is stored in part on physical stripe P0 and in part on physical stripe P1. Logical stripe L0 includes two sub-logical stripes. A first sub-logical stripe of L2 is stored on physical stripe P0 and includes subvolumes <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. A second sub-logical stripe of L2 is stored on physical stripe P1 and includes subvolumes <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. <FIG> also depicts overused subvolumes <NUM> and <NUM>-<NUM>, which are depicted by respective triangles in upper right corners of respective subvolume blocks.

In some examples, methods for allocating subvolumes may include (<NUM>) dividing a complete volume space into "N" subvolumes, where N = LCM (y, <NUM>, <NUM>, <NUM>,. x), "x" = maximum number of stripes to support, and "y" = a minimum number of stripes to support, (<NUM>) applying a recursive logical striping algorithm to all sub volumes (<NUM> to N-<NUM>), (<NUM>) tagging a logical stripe property to each subvolume until a recursion level reaches a logical stripe number that is equal or smaller than a highest available physical stripe, (<NUM>) while allocating first subvolumes of a logical stripe, check where last subvolume of logical stripe(s) was allocated from and select a next physical stripe to which to allocate subvolumes, and (<NUM>) while tagging, determine if there are any overused subvolumes in a stripe and tag overused subvolumes as being overused.

<FIG> is an example flow diagram of an example computer-implemented method for allocating subvolumes across multiple storage devices <NUM>. The steps shown in <FIG> may be performed by any suitable computer-executable code and/or computing system, including system <NUM> in <FIG>, system <NUM> in <FIG>, and/or variations or combinations of one or more of the same. In one example, each of the steps shown in <FIG> may represent an algorithm whose structure includes and/or is represented by multiple sub-steps. In embodiments, method <NUM> may allocate subvolumes <NUM> to multiple storage devices, such as storage device <NUM> and/or cloud storage device <NUM>.

In some embodiments, new storage devices and/or physical stripes may be added to may be added to an initial group of multiple storage devices. When new storage devices and/or physical stripes are added, optimized relayout methods may be performed to optimize allocation of storage space. For example, returning to <FIG>, method <NUM> may include (<NUM>) adding an additional physical stripe (e.g., on an added storage device), (<NUM>) transferring the Y+<NUM> logical stripe and subvolumes therein to the additional physical stripe, and (<NUM>) redistributing subvolumes in Y+<NUM> and any higher logical stripes across the Y+<NUM> physical stripes. In an embodiment, method <NUM> may include (<NUM>) adding "P" physical stripes, where "P" is an integer, (<NUM>) transferring the Y+<NUM> to Y+P logical stripes and subvolumes therein to the additional "P" physical stripes, and (<NUM>) redistributing subvolumes in Y+P+<NUM> and any higher logical stripes across the Y+P physical stripes. In one example, method <NUM> may include checking at least one subvolume for overuse and transferring, when an overused subvolume is detected, the overused subvolume to the additional physical stripe.

<FIG> is a diagram of an example reallocation of subvolumes across multiple storage devices when adding a storage device <NUM>. The left side of <FIG> depicts initial conditions similar to those of <FIG>. The center portion of <FIG> depicts adding new physical stripe P2, moving logical stripe L2 to physical stripe P2, and redistributing subvolumes from logical stripes L3-L5 across physical stripes P0-P2. The right side of <FIG> depicts moving transferring overused subvolumes <NUM> and <NUM>-<NUM> to new physical stripe P2.

<FIG> is a diagram of an example reallocation of subvolumes across multiple storage devices when adding two storage devices <NUM>. The left side of <FIG> depicts initial conditions similar to those of <FIG>. The center portion of <FIG> depicts adding new physical stripes P2-P3, moving logical stripe L2 to physical stripe P2, moving logical stripe L3 to physical stripe P3, and redistributing subvolumes from logical stripes L4-L5 across physical stripes P0-P3. The right side of <FIG> depicts moving transferring overused subvolumes <NUM> and <NUM> to new physical stripes P2-P3.

Returning to <FIG>, in some examples, after new storage devices and/or physical stripes are added, storage devices and/or physical stripes may subsequently be removed. When storage devices and/or physical stripes are subsequently removed, optimized relayout methods may be performed to optimize allocation of storage space. For example, method <NUM> may include (e.g., subsequently) (<NUM>) redistributing subvolumes from the Y+<NUM> logical stripe across the first "Y" physical stripes, (<NUM>) redistributing subvolumes in Y+<NUM> and any higher logical stripes across the first "Y" physical stripes, and (<NUM>) removing the Y+<NUM> physical stripe from the multiple storage devices (e.g., from a storage device to be removed). In one embodiment, method <NUM> may include checking at least one subvolume for overuse and transferring, when an overused subvolume is detected, the overused subvolume to a physical stripe storing a fewest number of subvolumes.

In some embodiments, storage devices and/or physical stripes may be removed from initial groups of multiple storage devices. When storage devices and/or physical stripes are removed from initial groups of multiple storage devices, optimized relayout methods may be performed to optimize allocation of storage space. For example, method <NUM> may include (<NUM>) redistributing subvolumes from the "Y" logical stripe across the first "Y-<NUM>" physical stripes, (<NUM>) redistributing subvolumes in Y+<NUM> and any higher logical stripes across the first "Y-<NUM>" physical stripes, and (<NUM>) removing the "Y" physical stripe from the multiple storage devices (e.g., from a storage device to be removed). In one example, method <NUM> may include checking at least one subvolume for overuse and transferring, when an overused subvolume is detected, the overused subvolume to a physical stripe storing a fewest number of subvolumes.

<FIG> is a diagram of an example reallocation of subvolumes across multiple storage devices when removing a storage device <NUM>. The left side of <FIG> depicts initial conditions similar to those of the right side of <FIG>. The center portion of <FIG> depicts preparing to remove physical stripe P3 and redistributing subvolumes in logical stripe L3 across physical stripes P0-P2. Subvolumes in logical stripes L4-L5 are redistributed across physical stripes P0-P2. The right side of <FIG> depicts removal of physical stripe P3.

<FIG> is a diagram of an example reallocation of subvolumes across multiple storage devices when removing two storage devices <NUM>. The left side of <FIG> depicts initial conditions similar to those of the right side of <FIG>. The center portion of <FIG> depicts preparing to remove physical stripes P2-P3 and redistributing subvolumes in logical stripes L2-L3 across physical stripes P0-P1. Subvolumes in logical stripes L4-L5 are redistributed across physical stripes P0-P1. The right side of <FIG> depicts removal of physical stripes P2-P3.

Returning to <FIG>, in some examples, after new storage devices and/or physical stripes are removed, new storage devices and/or new physical stripes may subsequently be added. When storage devices and/or new storage devices and/or new physical stripes are subsequently added, optimized relayout methods may be performed to optimize allocation of storage space. For example, method <NUM> may include (e.g., subsequently) (<NUM>) adding an additional physical stripe (e.g., on an added storage device), (<NUM>) transferring the Y-<NUM> logical stripe and subvolumes therein to the additional physical stripe, and (<NUM>) redistributing subvolumes in "Y" and any higher logical stripes across the "Y" physical stripes. In an embodiment, method <NUM> may include (<NUM>) adding "P" physical stripes, where "P" is an integer, (<NUM>) transferring the Y+<NUM> to Y+P logical stripes and subvolumes therein to the additional "P" physical stripes, and (<NUM>) redistributing subvolumes in Y+P+<NUM> and any higher logical stripes across the Y+P physical stripes. In one embodiment, method <NUM> may include checking at least one subvolume for overuse and transferring, when an overused subvolume is detected, the overused subvolume to the additional physical stripe.

<FIG> is a chart comparing operational performance of conventional techniques ("existing") to an example of operational performance of provided optimized techniques <NUM>. In some examples, improvements in relayout time may be <NUM>%-<NUM>% for volume sizes of 600GB-1200GB and growing volume size from <NUM> physical stripes to either <NUM> or <NUM> physical stripes.

In some examples, provided optimized techniques with two physical stripes, eight logical stripes, and <NUM> subvolumes may beneficially provide only a slight decline in input/output performance of a <NUM>% drop in write relayout time and a <NUM>% drop in read relayout time. In additional embodiments, provided optimized techniques with three physical stripes, eight logical stripes, and <NUM> subvolumes may beneficially provide only a slight decline in input/output performance of a <NUM>% drop in write relayout time and a <NUM>% drop in read relayout time.

As detailed above, the steps outlined herein may provide methods for rebalancing striped information across multiple storage devices. In some examples, the provided systems and methods may be used with striped storage devices. By doing so, in some examples, the systems and methods described herein may improve the functioning of computing devices by automatically (re)balancing striped information across multiple storage devices, thus enabling cost-effective storage management. Also, in some examples, the systems and methods described herein may save power by reducing a quantity of data to be transferred. Provided methods may also not require using temporary storage space, may not require serially transferring substantially all data in the multiple storage devices, and may not require moving as much data as conventional techniques.

While the foregoing disclosure sets forth various embodiments using specific block diagrams, flowcharts, and examples, each block diagram component, flowchart step, operation, and/or component described and/or illustrated herein may be implemented, individually and/or collectively, using a wide range of hardware, software, or firmware (or any combination thereof) configurations. In addition, any disclosure of components contained within other components should be considered example in nature since many other architectures can be implemented to achieve the same functionality.

In some examples, all or a portion of example system <NUM> in <FIG> may represent portions of a cloud-computing or network-based environment. Cloud-computing environments may provide various services and applications via the Internet. These cloud-based services (e.g., software as a service, platform as a service, infrastructure as a service, etc.) may be accessible through a web browser or other remote interface. Various functions described herein may be provided through a remote desktop environment or any other cloud-based computing environment.

In various embodiments, all or a portion of example system <NUM> in <FIG> may facilitate multi-tenancy within a cloud-based computing environment. In other words, the modules described herein may configure a computing system (e.g., a server) to facilitate multi-tenancy for one or more of the functions described herein. For example, one or more of the modules described herein may program a server to enable two or more clients (e.g., customers) to share an application that is running on the server. A server programmed in this manner may share an application, operating system, processing system, and/or storage system among multiple customers (i.e., tenants). One or more of the modules described herein may also partition data and/or configuration information of a multi-tenant application for each customer such that one customer cannot access data and/or configuration information of another customer.

According to various embodiments, all or a portion of example system <NUM> in <FIG> may be implemented within a virtual environment. For example, the modules and/or data described herein may reside and/or execute within a virtual machine. As used herein, the term "virtual machine" generally refers to any operating system environment that is abstracted from computing hardware by a virtual machine manager (e.g., a hypervisor).

In some examples, all or a portion of example system <NUM> in <FIG> may represent portions of a mobile computing environment. Mobile computing environments may be implemented by a wide range of mobile computing devices, including mobile phones, tablet computers, e-book readers, personal digital assistants, wearable computing devices (e.g., computing devices with a head-mounted display, smartwatches, etc.), variations or combinations of one or more of the same, or any other suitable mobile computing devices. In some examples, mobile computing environments may have one or more distinct features, including, for example, reliance on battery power, presenting only one foreground application at any given time, remote management features, touchscreen features, location and movement data (e.g., provided by Global Positioning Systems, gyroscopes, accelerometers, etc.), restricted platforms that restrict modifications to system-level configurations and/or that limit the ability of third-party software to inspect the behavior of other applications, controls to restrict the installation of applications (e.g., to only originate from approved application stores), etc. Various functions described herein may be provided for a mobile computing environment and/or may interact with a mobile computing environment.

While various embodiments have been described and/or illustrated herein in the context of fully functional computing systems, one or more of these example embodiments may be distributed as a program product in a variety of forms, regardless of the particular type of computer-readable media used to actually carry out the distribution. The embodiments disclosed herein may also be implemented using modules that perform certain tasks. These modules may include script, batch, or other executable files that may be stored on a computer-readable storage medium or in a computing system. In some embodiments, these modules may configure a computing system to perform one or more of the example embodiments disclosed herein.

The preceding description has been provided to enable others skilled in the art to best utilize various aspects of the example embodiments disclosed herein. This example description is not intended to be exhaustive or to be limited to any precise form disclosed. Many modifications and variations are possible without departing from the scope of protection as defined by the appended claims. The embodiments disclosed herein should be considered in all respects illustrative and not restrictive.

Claim 1:
A computer-implemented method for facilitating the rebalancing of striped information across multiple storage devices, to be performed by a computing device (<NUM>) comprising at least one processor (<NUM>), the method comprising:
allocating (<NUM>), by the computing device, "Y" contiguous storage spaces on "Y" physical storage devices (<NUM>) of multiple storage devices, thereby to create "Y" physical stripes (<NUM>) across the "Y" physical storage devices;
characterized in that the method additionally comprises:
dividing (<NUM>), by the computing device, the "Y" contiguous storage spaces into "N" chunks (<NUM>), wherein:
"N" is a value equal to the least common multiple of {y, <NUM>, <NUM>, <NUM>, ... , x},
"x" is equal to a maximum number of logical stripes of chunks, and
"y" is equal to a minimum number of logical stripes of chunks;
allocating (<NUM>), by the computing device, the "N" chunks to "X" logical stripes of chunks (<NUM>);
allocating (<NUM>), by the computing device, each of the first "Y" logical stripes of chunks of the "X" logical stripes of chunks to a respective physical stripe in each of the "Y" physical stripes;
dividing (<NUM>), by the computing device, remaining logical stripes of chunks (<NUM>) by "Y" to form respective sub-groups of logical stripes of chunks (<NUM>); and
allocating (<NUM>), by the computing device, the respective sub-groups of logical stripes of chunks across the "Y" physical stripes.