Distributed data storage grouping

• US 10,402,372 B2
• Filed: 12/27/2018
• Issued: 09/03/2019
• Est. Priority Date: 07/27/2015
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Bowman, Brian Payton, Cleveland, III, Jeff Ira
• Primary Examiner(s): Giardino, Jr., Mark A
• Application Number:
  US16/233,400
• Publication Number:
  US 20190129887A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1056 Simplification
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/262 configured as RAID
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5077 : Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/542 : Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H05K 999/99 : dummy group

Abstract

An apparatus includes a processor component to receive a node device identifier defining an ordering among multiple node devices and among multiple blocks of data distributed among the multiple node devices, and transmit a size of a first subset of the multiple blocks stored within the node device to a control device. In response to receiving instructions to receive a second subset from another node device, perform operations including: receive and store the second subset; group the blocks of data of the first and second subsets into multiple segments in an order that corresponds to the ordering among the multiple blocks, wherein each segment is sized to fit minimum and maximum sizes for transmission to storage device(s); transmit the multiple segments to the storage device(s); and relay multiple segment identifiers from the storage device(s) to the control device in an order corresponding to the ordering among the multiple segments.

Claims

1. An apparatus comprising a processor component and a storage to store instructions that, when executed by the processor component, cause the processor component to perform operations comprising:

receive, at a node device of multiple node devices, and from a control device via a network, a node device identifier of a set of node device identifiers assigned by the control device to multiple node devices, wherein;

the set of node device identifiers defines an ascending or descending series of numerical values that define an ordering among the multiple node devices; and

the ordering among the node devices defines a corresponding ordering among subsets of multiple blocks of data of a data set that are distributed among the multiple node devices;

transmit, to the control device via the network, an indication of a total size of a first subset of the multiple blocks of data that is stored within the storage of the node device;

receive, from the control device via the network, a block exchange instruction for the node device to participate in a performance of a set of block exchanges in which at least one node device of the multiple node devices serves as a source device to transmit one of the subsets of the multiple blocks of data to another node device of the multiple node devices that serves as a target node device; and

in response to the block exchange instruction comprising an indication that the node device is to serve as a target node to receive a second subset of the multiple blocks of data from another node device that serves as a source node device in the set of block exchanges, the processor component is caused to perform operations comprising;

receive, from the source node device via the network, the second subset;

store the second subset in the storage;

as part of a registration of the multiple blocks of data by the multiple node devices, transmit, to the control device via the network, an indication of a size of each block of data, or of each sub-block of each block of data, of the first subset and of the second subset, and in an order among the blocks of data of the first subset and the second subset that corresponds to an ordering among the multiple blocks of data that corresponds to the ordering among the multiple node devices;

group, by the processor component, the blocks of data of the first subset and the second subset into multiple segments of the data set in an order within each segment of the multiple segments and in an order among the multiple segments that corresponds to the ordering among the multiple blocks of data, wherein each segment of the multiple segments is formed to have a size that meets a minimum threshold size imposed on units of data that are transmitted to one or more storage devices;

transmit, to the one or more storage devices via the network, the multiple segments;

receive, from the one or more storage devices via the network, multiple segment identifiers, wherein each segment identifier of the multiple segment identifiers corresponds to a segment of the multiple segments; and

transmit, to the control device via the network, the multiple segment identifiers in an order that corresponds to the ordering among the multiple segments.

2. The apparatus of claim 1, wherein:

the set of node device identifiers defines a 0-based ascending set of positive integers incremented by a value of 1;

the data of the data set comprises partitioned data wherein;

the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;

each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and

all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;

each partition of the set of partitions is provided with a unique label of a set of labels; and

the control device transmits the set of node device identifiers to the multiple node devices prior to using the set of node device identifiers to distribute the data set among the multiple node devices based on matches between the set of node device identifiers and a set of hashed values derived from the set of labels through dividing a hash value from a hash taken of each label by a quantity of the multiple node devices.

3. The apparatus of claim 1, wherein:

prior to the performance of the set of block exchanges, the control device receives an indication of a total size of the subset of the multiple blocks of data distributed to each node device of the multiple node devices;

the control device derives the set of block exchanges based on the total sizes of the subsets received from the multiple node devices;

the control device generates a block exchange vector that identifies each source node device and each target node device based on the set of node device identifiers; and

the processor component is caused to perform operations comprising;

receive the block exchange vector from the control device as the block exchange instruction for the node device to participate in a performance of the set of block exchanges; and

analyze the block exchange vector in view of the node device identifier assigned to the node device to determine whether the node device is to serve as a source node device or a target node device.

4. The apparatus of claim 1, wherein, in response to the block exchange instruction comprising an indication that the node device is to serve as a target node, the processor component is caused to perform operations comprising:

transmit a request, via the network and to the source node device, to transmit the second subset to the node device; and

receive, from the source node device via the network, and along with the second subset, an indication of a size of each block of data of the second subset or of each sub-block of data within each block of data of the second subset.

5. The apparatus of claim 1, wherein, in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit the first subset of the multiple blocks of data to another device that serves as a target node device in the set of block exchanges, the processor component is caused to perform operations comprising:

receive, from the other device via the network, a request to transmit the first subset to the other device; and

transmit, to the other device via the network, the first subset and an indication of size of each block of data of the first subset or each sub-block of data within each block of data of the first subset.

6. The apparatus of claim 1, wherein:

the data of the data set comprises partitioned data wherein;

the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;

each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and

all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data; and

as part of the registration of the multiple blocks of data, the processor component is caused to transmit, to the control device via the network, an indication of a size and a hashed value indicative of a partition for each data sub-block of each block of data of the first subset and of the second subset.

7. The apparatus of claim 1, wherein:

the data of the data set comprises non-partitioned data; and

as part of the registration of the multiple blocks of data, the processor component is caused to transmit, to the control device via the network, an indication of a size of each block of data of the first subset and of the second subset.

8. The apparatus of claim 1, wherein:

the data of the data set is to be stored within the one or more storage devices in encrypted form, wherein each block of data is to be separately encrypted by one of the node devices of the multiple node devices; and

as part of the registration of multiple blocks of data, the processor component is caused to transmit, to the control device via the network, data block encryption data for each block of data of the first subset and of the second subset.

9. The apparatus of claim 1, wherein the processor component is caused to perform operations comprising:

receive, from the control device via the network, at least one of a map data and a metadata, wherein;

the map data is indicative of the order among the multiple blocks of data, wherein the order among the multiple blocks of data is to be maintained within the one or more storage devices while the data set is stored within the one or more storage devices; and

the metadata is indicative of at least one of whether the data of the data set comprises partitioned data and whether the data set is to be stored within the one or more storage devices in encrypted form; and

group, by the processor component, the at least one of the map data and the metadata together with the blocks of data of the first subset and the second subset into the multiple segments in an order within each segment of the multiple segments and in an order among the multiple segments that corresponds to the ordering among the multiple blocks of data, and in an order that places the at least one of the map data and the metadata ahead of the multiple blocks of data.

10. The apparatus of claim 1, wherein, in response to a block of data of the first subset or of the second subset exceeding a maximum threshold size imposed on units of data that are transmitted to the one or more storage devices, the processor component is caused to divide the block of data among two or more segments of the multiple segments to form each segment of the multiple segments to have a size that fits within the minimum threshold size and the maximum threshold size.

11. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a processor component to perform operations comprising:

receive, at a node device of multiple node devices, and from a control device via a network, a node device identifier of a set of node device identifiers assigned by the control device to multiple node devices, wherein;

the set of node device identifiers defines an ascending or descending series of numerical values that define an ordering among the multiple node devices; and

the ordering among the node devices defines a corresponding ordering among subsets of multiple blocks of data of a data set that are distributed among the multiple node devices;

transmit, to the control device via the network, an indication of a total size of a first subset of the multiple blocks of data that is stored within the storage of the node device;

receive, from the control device via the network, a block exchange instruction for the node device to participate in a performance of a set of block exchanges in which at least one node device of the multiple node devices serves as a source device to transmit one of the subsets of the multiple blocks of data to another node device of the multiple node devices that serves as a target node device; and

in response to the block exchange instruction comprising an indication that the node device is to serve as a target node to receive a second subset of the multiple blocks of data from another node device that serves as a source node device in the set of block exchanges, the processor component is caused to perform operations comprising;

receive, from the source node device via the network, the second subset;

store the second subset in the storage;

as part of a registration of the multiple blocks of data by the multiple node devices, transmit, to the control device via the network, an indication of a size of each block of data, or of each sub-block of each block of data, of the first subset and of the second subset, and in an order among the blocks of data of the first subset and the second subset that corresponds to an ordering among the multiple blocks of data that corresponds to the ordering among the multiple node devices;

group, by the processor component, the blocks of data of the first subset and the second subset into multiple segments of the data set in an order within each segment of the multiple segments and in an order among the multiple segments that corresponds to the ordering among the multiple blocks of data, wherein each segment of the multiple segments is formed to have a size that meets a minimum threshold size imposed on units of data that are transmitted to one or more storage devices;

transmit, to the one or more storage devices via the network, the multiple segments;

receive, from the one or more storage devices via the network, multiple segment identifiers, wherein each segment identifier of the multiple segment identifiers corresponds to a segment of the multiple segments; and

transmit, to the control device via the network, the multiple segment identifiers in an order that corresponds to the ordering among the multiple segments.

12. The computer-program product of claim 11, wherein:

the set of node device identifiers defines a 0-based ascending set of positive integers incremented by a value of 1;

the data of the data set comprises partitioned data wherein;

the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;

each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and

all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;

each partition of the set of partitions is provided with a unique label of a set of labels; and

the control device transmits the set of node device identifiers to the multiple node devices prior to using the set of node device identifiers to distribute the data set among the multiple node devices based on matches between the set of node device identifiers and a set of hashed values derived from the set of labels through dividing a hash value from a hash taken of each label by a quantity of the multiple node devices.

13. The computer-program product of claim 11, wherein:

prior to the performance of the set of block exchanges, the control device receives an indication of a total size of the subset of the multiple blocks of data distributed to each node device of the multiple node devices;

the control device derives the set of block exchanges based on the total sizes of the subsets received from the multiple node devices;

the control device generates a block exchange vector that identifies each source node device and each target node device based on the set of node device identifiers; and

the processor component is caused to perform operations comprising;

receive the block exchange vector from the control device as the block exchange instruction for the node device to participate in a performance of the set of block exchanges; and

analyze the block exchange vector in view of the node device identifier assigned to the node device to determine whether the node device is to serve as a source node device or a target node device.

14. The computer-program product of claim 11, wherein, in response to the block exchange instruction comprising an indication that the node device is to serve as a target node, the processor component is caused to perform operations comprising:

transmit a request, via the network and to the source node device, to transmit the second subset to the node device; and

receive, from the source node device via the network, and along with the second subset, an indication of a size of each block of data of the second subset or of each sub-block of data within each block of data of the second subset.

15. The computer-program product of claim 11, wherein, in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit the first subset of the multiple blocks of data to another device that serves as a target node device in the set of block exchanges, the processor component is caused to perform operations comprising:

receive, from the other device via the network, a request to transmit the first subset to the other device; and

transmit, to the other device via the network, the first subset and an indication of size of each block of data of the first subset or each sub-block of data within each block of data of the first subset.

16. The computer-program product of claim 11, wherein:

the data of the data set comprises partitioned data wherein;

the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;

each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and

all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data; and

as part of the registration of the multiple blocks of data, the processor component is caused to transmit, to the control device via the network, an indication of a size and a hashed value indicative of a partition for each data sub-block of each block of data of the first subset and of the second subset.

17. The computer-program product of claim 11, wherein:

the data of the data set comprises non-partitioned data; and

as part of the registration of the multiple blocks of data, the processor component is caused to transmit, to the control device via the network, an indication of a size of each block of data of the first subset and of the second subset.

18. The computer-program product of claim 11, wherein:

the data of the data set is to be stored within the one or more storage devices in encrypted form, wherein each block of data is to be separately encrypted by one of the node devices of the multiple node devices; and

as part of the registration of multiple blocks of data, the processor component is caused to transmit, to the control device via the network, data block encryption data for each block of data of the first subset and of the second subset.

19. The computer-program product of claim 11, wherein the processor component is caused to perform operations comprising:

receive, from the control device via the network, at least one of a map data and a metadata, wherein;

the map data is indicative of the order among the multiple blocks of data, wherein the order among the multiple blocks of data is to be maintained within the one or more storage devices while the data set is stored within the one or more storage devices; and

the metadata is indicative of at least one of whether the data of the data set comprises partitioned data and whether the data set is to be stored within the one or more storage devices in encrypted form; and

group, by the processor component, the at least one of the map data and the metadata together with the blocks of data of the first subset and the second subset into the multiple segments in an order within each segment of the multiple segments and in an order among the multiple segments that corresponds to the ordering among the multiple blocks of data, and in an order that places the at least one of the map data and the metadata ahead of the multiple blocks of data.

20. The computer-program product of claim 11, wherein, in response to a block of data of the first subset or of the second subset exceeding a maximum threshold size imposed on units of data that are transmitted to the one or more storage devices, the processor component is caused to divide the block of data among two or more segments of the multiple segments to form each segment of the multiple segments to have a size that fits within the minimum threshold size and the maximum threshold size.

21. A computer-implemented method comprising:

receiving, by a processor component at a node device of multiple node devices, and from a control device via a network, a node device identifier of a set of node device identifiers assigned by the control device to multiple node devices, wherein;

the set of node device identifiers defines an ascending or descending series of numerical values that define an ordering among the multiple node devices; and

the ordering among the node devices defines a corresponding ordering among subsets of multiple blocks of data of a data set that are distributed among the multiple node devices;

transmitting, by the processor component to the control device via the network, an indication of a total size of a first subset of the multiple blocks of data that is stored within the storage of the node device;

receiving, by the processor component from the control device via the network, a block exchange instruction for the node device to participate in a performance of a set of block exchanges in which at least one node device of the multiple node devices serves as a source device to transmit one of the subsets of the multiple blocks of data to another node device of the multiple node devices that serves as a target node device; and

in response to the block exchange instruction comprising an indication that the node device is to serve as a target node to receive a second subset of the multiple blocks of data from another node device that serves as a source node device in the set of block exchanges, performing operations comprising;

receiving, by the processor component from the source node device via the network, the second subset;

storing the second subset in the storage;

as part of a registration of the multiple blocks of data by the multiple node devices, transmitting, by the processor component to the control device via the network, an indication of a size of each block of data, or of each sub-block of each block of data, of the first subset and of the second subset, and in an order among the blocks of data of the first subset and the second subset that corresponds to an ordering among the multiple blocks of data that corresponds to the ordering among the multiple node devices;

grouping, by the processor component, the blocks of data of the first subset and the second subset into multiple segments of the data set in an order within each segment of the multiple segments and in an order among the multiple segments that corresponds to the ordering among the multiple blocks of data, wherein each segment of the multiple segments is formed to have a size that meets a minimum threshold size imposed on units of data that are transmitted to one or more storage devices;

transmitting, by the processor component to the one or more storage devices via the network, the multiple segments;

receiving, by the processor component from the one or more storage devices via the network, multiple segment identifiers, wherein each segment identifier of the multiple segment identifiers corresponds to a segment of the multiple segments; and

transmitting, by the processor component to the control device via the network, the multiple segment identifiers in an order that corresponds to the ordering among the multiple segments.

22. The computer-implemented method of claim 21, wherein:

the set of node device identifiers defines a 0-based ascending set of positive integers incremented by a value of 1;

the data of the data set comprises partitioned data wherein;

the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;

each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and

all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data;

each partition of the set of partitions is provided with a unique label of a set of labels; and

the control device transmits the set of node device identifiers to the multiple node devices prior to using the set of node device identifiers to distribute the data set among the multiple node devices based on matches between the set of node device identifiers and a set of hashed values derived from the set of labels through dividing a hash value from a hash taken of each label by a quantity of the multiple node devices.

23. The computer-implemented method of claim 21, wherein:

prior to the performance of the set of block exchanges, the control device receives an indication of a total size of the subset of the multiple blocks of data distributed to each node device of the multiple node devices;

the control device derives the set of block exchanges based on the total sizes of the subsets received from the multiple node devices;

the control device generates a block exchange vector that identifies each source node device and each target node device based on the set of node device identifiers; and

the method comprises;

receiving, by the processor component, the block exchange vector from the control device as the block exchange instruction for the node device to participate in a performance of the set of block exchanges; and

analyzing, by the processor component, the block exchange vector in view of the node device identifier assigned to the node device to determine whether the node device is to serve as a source node device or a target node device.

24. The computer-implemented method of claim 21, comprising, in response to the block exchange instruction comprising an indication that the node device is to serve as a target node, performing operations comprising:

transmitting, by the processor component, a request, via the network and to the source node device, to transmit the second subset to the node device; and

receiving, by the processor component, from the source node device via the network, and along with the second subset, an indication of a size of each block of data of the second subset or of each sub-block of data within each block of data of the second subset.

25. The computer-implemented method of claim 21, comprising, in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit the first subset of the multiple blocks of data to another device that serves as a target node device in the set of block exchanges, performing operations comprising:

receiving, by the processor component, from the other device via the network, a request to transmit the first subset to the other device; and

transmitting, by the processor component, to the other device via the network, the first subset and an indication of size of each block of data of the first subset or each sub-block of data within each block of data of the first subset.

26. The computer-implemented method of claim 21, wherein:

the data of the data set comprises partitioned data wherein;

the data of the data set is divided into a set of partitions that are each required to be provided to a single node device;

each block of data is divided into one or more data sub-blocks that are each individually associated with a partition of the set of partitions; and

all data sub-blocks associated with a single partition of the set of partitions must be included within a single block of data; and

as part of the registration of the multiple blocks of data, the method comprises transmitting, by the processor component to the control device via the network, an indication of a size and a hashed value indicative of a partition for each data sub-block of each block of data of the first subset and of the second subset.

27. The computer-implemented method of claim 21, wherein:

the data of the data set comprises non-partitioned data; and

as part of the registration of the multiple blocks of data, the method comprises transmitting, by the processor component to the control device via the network, an indication of a size of each block of data of the first subset and of the second subset.

28. The computer-implemented method of claim 21, wherein:

the data of the data set is to be stored within the one or more storage devices in encrypted form, wherein each block of data is to be separately encrypted by one of the node devices of the multiple node devices; and

as part of the registration of multiple blocks of data, the method comprises transmitting, by the processor component to the control device via the network, data block encryption data for each block of data of the first subset and of the second subset.

29. The computer-implemented method of claim 21, comprising:

receiving, by the processor component from the control device via the network, at least one of a map data and a metadata, wherein;

the map data is indicative of the order among the multiple blocks of data, wherein the order among the multiple blocks of data is to be maintained within the one or more storage devices while the data set is stored within the one or more storage devices; and

the metadata is indicative of at least one of whether the data of the data set comprises partitioned data and whether the data set is to be stored within the one or more storage devices in encrypted form; and

grouping, by the processor component, the at least one of the map data and the metadata together with the blocks of data of the first subset and the second subset into the multiple segments in an order within each segment of the multiple segments and in an order among the multiple segments that corresponds to the ordering among the multiple blocks of data, and in an order that places the at least one of the map data and the metadata ahead of the multiple blocks of data.

30. The computer-implemented method of claim 21, comprising, in response to a block of data of the first subset or of the second subset exceeding a maximum threshold size imposed on units of data that are transmitted to the one or more storage devices, dividing, by the processor component, the block of data among two or more segments of the multiple segments to form each segment of the multiple segments to have a size that fits within the minimum threshold size and the maximum threshold size.