Granted Patent B2

US 9,740,627 · App. 15/136,831 · Granted Aug 22, 2017

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

Assignee: Scale Computing, Inc.

G06F12/10G06F3/064G06F3/065G06F3/0605G06F3/067G06F3/0619G06F3/0689G06F2212/151G06F2212/50G06F2212/65

Abstract

Claims (53)

1. A method comprising:

tracking, by a block engine daemon in communication with one or more virtual machines, 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, wherein each RSD object comprises a data structure in the memory, and wherein each RSD object corresponds to a particular RSD in the plurality of RSDs;

generating a virtual storage device (VSD) object in the memory, wherein the VSD object corresponds to a logical storage device accessible by at least one virtual machine in the one or more virtual machines;

selecting, by a VSD engine in the block engine daemon, one or more RSD objects in the plurality of RSD objects as a set of selected RSD objects returned by a placement specification implemented as a function included in the VSD engine, wherein the function utilizes at least one parameter in the one or more parameters to return a set of selected RSD objects; and

for each RSD object in the one or more RSD objects, allocating, by the block engine daemon, 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.

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 the placement specification is configured to return the set of selected RSD objects by:

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 the placement specification is configured to return the set of selected RSD objects by 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 a failure group identifier comprises a 32-bit integer that encodes a drive identifier, a node identifier, a rack identifier, and a row identifier.

7. The method of claim 5 , wherein a failure group identifier for an RSD object is generated automatically during provisioning of a cluster of nodes.

8. The method of claim 1 , wherein the placement specification is configured to return the set of selected RSD objects by:

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.

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

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

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

12. The method of claim 8 , 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 (IOPS) 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.

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

14. 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.

15. The method of claim 14 , 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.

16. A system comprising:

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

a block engine daemon in communication with each of the one or more virtual machines, the block engine daemon 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, wherein each RSD object comprises a data structure in the memory, and wherein each RSD object corresponds to a particular RSD in the plurality of RSDs,

generate a virtual storage device (VSD) object in the memory, wherein the VSD object corresponds to a logical storage device accessible by at least one virtual machine in the one or more virtual machines,

select, by a VSD engine in the block engine daemon, one or more RSD objects in the plurality of RSD objects as a set of selected RSD objects returned by a placement specification implemented as a function included in the VSD engine, wherein the function utilizes at least one parameter in the one or more parameters to return a set of selected RSD objects, 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.

17. The system of claim 16 , further comprising:

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

a second block engine daemon in communication with the one or more additional virtual machines, the second block engine daemon 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,

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

18. The system of claim 17 , wherein the block engine daemon 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.

19. The system of claim 16 , wherein the placement specification is configured to return the set of selected RSD objects by:

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.

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

tracking, by a block engine daemon in communication with one or more virtual machines, 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, wherein each RSD object comprises a data structure in the memory, and wherein each RSD object corresponds to a particular RSD in the plurality of RSDs;

generating a virtual storage device (VSD) object in the memory, wherein the VSD object corresponds to a logical storage device accessible by at least one virtual machine in the one or more virtual machines;

selecting, by a VSD engine in the block engine daemon, one or more RSD objects in the plurality of RSD objects as a set of selected RSD objects returned by a placement specification implemented as a function included in the VSD engine, wherein the function utilizes at least one parameter in the one or more parameters to return a set of selected RSD objects; and

for each RSD object in the one or more RSD objects, allocating, by the block engine daemon, 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.

Assignments (18)

Continuity (2)