Granted Patent B2

US 9,348,526 · App. 14/229,748 · Granted May 24, 2016

Inventors: Philip Andrew White (San Francisco, CA); Hank T. Hsieh (San Francisco, CA)

Assignee: Scale Computing, Inc.

G06F3/0619G06F3/065G06F3/0689

Abstract

Claims (54)

1. A method comprising:

tracking one or more parameters associated with a plurality of real storage devices (RSDs);

generating a plurality of RSD objects in a memory associated with a first node, each RSD object corresponding to a particular RSD in the plurality of RSDs;

generating a virtual storage device (VSD) object in the memory;

selecting one or more RSD objects in the plurality of RSD objects based on at least one parameter in the one or more parameters; and

for each RSD object in the one or more RSD objects, allocating a block of memory in the RSD associated with the RSD object to store data corresponding to a first block of memory associated with the VSD object,

wherein each RSD object is associated with a failure group identifier that comprises a 32-bit integer that encodes a drive identifier, a node identifier, a rack identifier, and a row identifier.

2. The method of claim 1 , wherein each RSD comprises a device selected from the group consisting of a hard disk drive, a solid state drive, a tape drive, and an optical disc drive.

3. The method of claim 1 , wherein each VSD object comprises a data structure that includes a mapping table that associates ranges of addresses associated with the VSD object with one or more blocks of memory included in the plurality of RSDs.

4. The method of claim 1 , wherein selecting the one or more RSD objects in the plurality of RSD objects comprises:

adding an RSD object to a solution set based on a value of a counter;

incrementing the value of the counter;

determining whether the solution set includes less than a threshold number of RSD objects; and

if the solution set includes less than the threshold number of RSD objects, then adding another RSD object to the solution set, or

if the solution set includes greater than or equal to the threshold number of RSD objects, then selecting the RSD objects in the solution set as the one or more RSD objects.

5. The method of claim 1 , wherein selecting the one or more RSD objects in the plurality of RSD objects comprises selecting one or more RSD objects from a set of allowed RSD objects, each RSD object of the one or more RSD objects having a unique failure group identifier with respect to each of the other RSD objects in the one or more RSD objects.

6. The method of claim 5 , wherein failure group identifiers for each RSD object are generated automatically during provisioning of a cluster of nodes.

7. The method of claim 1 , wherein selecting the one or more RSD objects in the plurality of RSD objects comprises:

calculating a heuristic value associated with each RSD object in the plurality of RSD objects, wherein the heuristic value is based on the one or more parameters associated with an RSD corresponding to the RSD object; and

selecting the one or more RSD objects based on the heuristic values.

8. The method of claim 7 , wherein the one or more parameters comprises a number of input/output operations per second (IOPS) for the RSD.

9. The method of claim 7 , wherein the one or more parameters comprises a utilization measurement for the RSD.

10. The method of claim 7 , wherein the one or more parameters comprises an error rate for the RSD.

11. The method of claim 7 , wherein the one or more parameters comprises at least two parameters selected from the group consisting of a utilization measurement for the RSD, a number of input/output operations per second (TOPS) for the RSD, a failure group identifier for the RSD, an error rate for the RSD, and an indication of whether the data is pre-placed on the RSD.

12. The method of claim 11 , wherein each parameter of the one or more parameters is weighted.

13. The method of claim 1 , further comprising periodically checking the one or more RSD objects allocated to the first block of memory based on a utilization rate of the first block of memory.

14. The method of claim 13 , further comprising, if the utilization rate is above a threshold value, then copying data associated with the first block of memory from a first RSD to a second RSD, wherein a response time parameter value associated with the second RSD is greater than a response time parameter value associated with the first RSD.

15. A system comprising:

one or more virtual machines implemented by a first node in a cluster of nodes; and

a process in communication with each of the one or more virtual machines, the process being executed by the first node and configured to:

track one or more parameters associated with a plurality of real storage devices (RSDs),

generate a plurality of RSD objects in a memory associated with the first node, each RSD object corresponding to a particular RSD in the plurality of RSDs,

generate a virtual storage device (VSD) object in the memory,

select one or more RSD objects in the plurality of RSD objects based on at least one parameter in the one or more parameters, and

for each RSD object in the one or more RSD objects, allocate a block of memory in the RSD associated with the RSD object to store data corresponding to a first block of memory associated with the VSD object,

wherein each RSD object is associated with a failure group identifier that comprises a 32-bit integer that encodes a drive identifier, a node identifier, a rack identifier, and a row identifier.

16. The system of claim 15 , further comprising:

one or more additional virtual machines implemented on a second node of the cluster; and

a second process in communication with the one or more additional virtual machines, the second process being executed by the second node and configured to:

track the one or more parameters associated with the plurality of RSDs, generate a second plurality of RSD objects in a memory associated with the second node, and

generate a second VSD object in the memory associated with the second node.

17. The system of claim 16 , wherein the process is further configured to:

generate input/output (I/O) requests associated with a first RSD coupled to the second node; and

transmit the I/O requests to the second node via a network.

18. The system of claim 15 , wherein, to select the one or more RSD objects in the plurality of RSD objects, the process is configured to:

calculate a heuristic value associated with each RSD object in the plurality of RSD objects, wherein the heuristic value is based on the one or more parameters associated with an RSD corresponding to the RSD object; and

select the one or more RSD objects based on the heuristic values.

19. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:

tracking one or more parameters associated with a plurality of real storage devices (RSDs);

generating a plurality of RSD objects in a memory associated with a first node, each RSD object corresponding to a particular RSD in the plurality of RSDs;

generating a virtual storage device (VSD) object in the memory;

selecting one or more RSD objects in the plurality of RSD objects based on at least one parameter in the one or more parameters; and

for each RSD object in the one or more RSD objects, allocating a block of memory in the RSD associated with the RSD object to store data corresponding to a first block of memory associated with the VSD object,

wherein each RSD object is associated with a failure group identifier that comprises a 32-bit integer that encodes a drive identifier, a node identifier, a rack identifier, and a row identifier.

Assignments (18)

Continuity (1)