Distributed data storage grouping

• US 10,311,023 B1
• Filed: 12/27/2018
• Issued: 06/04/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,573
• Publication Number:
  US 20190197021A1
• Time in Patent Office: 159 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 of includes a processor component to: transmit node device identifiers to multiple node devices to define an ordering thereamong and among subsets of multiple blocks of data distributed thereamong; receive sizes of the subsets from the multiple node devices; derive block exchanges among the multiple node device based on the sizes and a minimum size imposed on data transmissions to storage device(s); and transmit a block exchange vector that describes the block exchanges to the multiple node devices, wherein: the subsets remain distributed among a reduced number of the multiple node devices following the block exchanges; at least all node devices of the reduced number but one stores an amount of the blocks of data exceeding the minimum size; and the block exchanges are all lower-order to higher-order node device transfers, or all higher-order to lower-order node device transfers.

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:

transmit, from a control device, and to multiple node devices via a network, a set of node device identifiers to assign each node device of the multiple node devices a different node device identifier of the set of node device identifiers, 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;

receive, from the multiple node devices via the network, 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;

derive, by the processor component, a set of block exchanges based on the total sizes of the subsets received from the multiple node devices and a minimum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices, wherein;

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;

following a performance of the set of block exchanges, the data set remains distributed to a reduced number of the multiple node devices;

either each node device of the reduced number of node devices, or each node device but one of the reduced number of node devices, stores an amount of the data of the data set that is greater than the minimum threshold size; and

the set of block exchanges follows a block exchange rule that each transfer of one of the subsets of the multiple blocks of data in the set of block exchanges is to be from a lower-order source node device and to a higher-order target node device in the ordering among the multiple node devices, or that each transfer of one of the subsets of the multiple blocks of data is to be from a higher-order source node device and to a lower-order target node device in the ordering among the multiple node devices;

generate a block exchange vector that identifies each source node device and each target node device in the set of block exchanges based on the set of node device identifiers; and

transmit the block exchange vector to the multiple node devices as a block exchange instruction to cause a performance of the set of block exchanges among the multiple node devices.

2. 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;

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

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

prior to using the set of node device identifiers to derive the set of block exchanges, the processor component is caused to use 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 modulo 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 2, wherein, in response to receiving the block exchange instruction, a node device of the multiple node devices performs operations comprising:

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;

in response to a determination that the node device is to serve as a source node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding target node device;

or

in response to a determination that the node device is to serve as a target node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding source node device.

4. The apparatus of claim 1, wherein, in response to receiving the block exchange instruction, 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 subset of the multiple blocks of data from another node device that is to serve as a source node in the set of block exchanges, a node device of the multiple node devices performs operations comprising:

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

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

5. The apparatus of claim 1, wherein, in response to receiving the block exchange instruction, and in response to the block exchange instruction comprising an indication that the node device is to serve as a source node to transmit a subset of the multiple blocks of data to another device that is to serve as a target node device in the set of block exchanges, a node device of the multiple node devices performs operations comprising:

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

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

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

as part of a registration of the multiple blocks of data by the reduced number of node devices following the performance of the set of block exchanges, receive from each node device of the reduced number of node devices, and for each block of data of the multiple blocks of data, an indication of a size of the block of data or indications of a size of each sub-block of the block of data; and

generate, based at least on the indications of size received during registration, map data indicative of an ordering among the multiple blocks of data by which the multiple blocks of data are to be stored within the one or more storage devices, and which stems from the ordering among the subsets of the multiple blocks of data.

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

determine a total size of a combination of at least the map data and of a metadata 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;

determine whether the total size of the combination meets the minimum threshold size; and

in response to a determination that the combination does not meet the minimum threshold size, perform operations comprising;

identify a lowest-order node device or a highest-order node device in the ordering among the multiple node devices that is among the reduced number of node devices; and

transmit, to the identified lowest-order node device or highest-order node device, and via the network, the combination of the map data and the metadata.

8. The apparatus of claim 7, wherein the processor component is caused, in response to a determination that the combination does meet the minimum threshold size, to perform operations comprising:

form one or more segments for transmission to the one or more storage devices from the combination of the map data and the metadata that each fit within the minimum threshold size and a maximum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices; and

transmit, to the one or more storage devices via the network, the one or more segments at least partially in parallel with multiple other segments formed from the multiple blocks of data by the reduced number of node devices.

9. 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;

as part of the registration of the multiple blocks of data, the processor component is caused to receive, for each sub-block of each block of data, a hashed value indicative of a partition with which the sub-block is associated; and

the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the size and hashed value of each sub-block within the block of data.

10. 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;

as part of the registration of multiple blocks of data, the processor component is caused to receive, for each block of data of the multiple blocks of data, data block encryption data by which the block of data is encrypted; and

the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the data block encryption data for the block of data.

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:

transmit, from a control device, and to multiple node devices via a network, a set of node device identifiers to assign each node device of the multiple node devices a different node device identifier of the set of node device identifiers, 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;

receive, from the multiple node devices via the network, 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;

derive, by the processor component, a set of block exchanges based on the total sizes of the subsets received from the multiple node devices and a minimum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices, wherein;

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;

following a performance of the set of block exchanges, the data set remains distributed to a reduced number of the multiple node devices;

either each node device of the reduced number of node devices, or each node device but one of the reduced number of node devices, stores an amount of the data of the data set that is greater than the minimum threshold size; and

the set of block exchanges follows a block exchange rule that each transfer of one of the subsets of the multiple blocks of data in the set of block exchanges is to be from a lower-order source node device and to a higher-order target node device in the ordering among the multiple node devices, or that each transfer of one of the subsets of the multiple blocks of data is to be from a higher-order source node device and to a lower-order target node device in the ordering among the multiple node devices;

generate a block exchange vector that identifies each source node device and each target node device in the set of block exchanges based on the set of node device identifiers; and

transmit the block exchange vector to the multiple node devices as a block exchange instruction to cause a performance of the set of block exchanges among the multiple node devices.

12. 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;

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

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

prior to using the set of node device identifiers to derive the set of block exchanges, the processor component is caused to use 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 modulo 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 12, wherein, in response to receiving the block exchange instruction, a node device of the multiple node devices performs operations comprising:

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;

in response to a determination that the node device is to serve as a source node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding target node device;

or

in response to a determination that the node device is to serve as a target node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding source node device.

14. The computer-program product of claim 11, wherein, in response to receiving the block exchange instruction, 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 subset of the multiple blocks of data from another node device that is to serve as a source node in the set of block exchanges, a node device of the multiple node devices performs operations comprising:

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

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

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

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

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

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

as part of a registration of the multiple blocks of data by the reduced number of node devices following the performance of the set of block exchanges, receive from each node device of the reduced number of node devices, and for each block of data of the multiple blocks of data, an indication of a size of the block of data or indications of a size of each sub-block of the block of data; and

generate, based at least on the indications of size received during registration, map data indicative of an ordering among the multiple blocks of data by which the multiple blocks of data are to be stored within the one or more storage devices, and which stems from the ordering among the subsets of the multiple blocks of data.

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

determine a total size of a combination of at least the map data and of a metadata 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;

determine whether the total size of the combination meets the minimum threshold size; and

in response to a determination that the combination does not meet the minimum threshold size, perform operations comprising;

identify a lowest-order node device or a highest-order node device in the ordering among the multiple node devices that is among the reduced number of node devices; and

transmit, to the identified lowest-order node device or highest-order node device, and via the network, the combination of the map data and the metadata.

18. The computer-program product of claim 17, wherein the processor component is caused, in response to a determination that the combination does meet the minimum threshold size, to perform operations comprising:

form one or more segments for transmission to the one or more storage devices from the combination of the map data and the metadata that each fit within the minimum threshold size and a maximum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices; and

transmit, to the one or more storage devices via the network, the one or more segments at least partially in parallel with multiple other segments formed from the multiple blocks of data by the reduced number of node devices.

19. 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;

as part of the registration of the multiple blocks of data, the processor component is caused to receive, for each sub-block of each block of data, a hashed value indicative of a partition with which the sub-block is associated; and

the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the size and hashed value of each sub-block within the block of data.

20. 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;

as part of the registration of multiple blocks of data, the processor component is caused to receive, for each block of data of the multiple blocks of data, data block encryption data by which the block of data is encrypted; and

the processor component is caused to generate, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the data block encryption data for the block of data.

21. A computer-implemented method comprising:

transmitting, by a processor component from a control device, and to multiple node devices via a network, a set of node device identifiers to assign each node device of the multiple node devices a different node device identifier of the set of node device identifiers, 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;

receiving, by the processor component from the multiple node devices via the network, 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;

deriving, by the processor component, a set of block exchanges based on the total sizes of the subsets received from the multiple node devices and a minimum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices, wherein;

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;

following a performance of the set of block exchanges, the data set remains distributed to a reduced number of the multiple node devices;

either each node device of the reduced number of node devices, or each node device but one of the reduced number of node devices, stores an amount of the data of the data set that is greater than the minimum threshold size; and

the set of block exchanges follows a block exchange rule that each transfer of one of the subsets of the multiple blocks of data in the set of block exchanges is to be from a lower-order source node device and to a higher-order target node device in the ordering among the multiple node devices, or that each transfer of one of the subsets of the multiple blocks of data is to be from a higher-order source node device and to a lower-order target node device in the ordering among the multiple node devices;

generating, by the processor component, a block exchange vector that identifies each source node device and each target node device in the set of block exchanges based on the set of node device identifiers; and

transmitting, by the processor component, the block exchange vector to the multiple node devices as a block exchange instruction to cause a performance of the set of block exchanges among the multiple node devices.

22. 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;

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

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

the method comprises, prior to using the set of node device identifiers to derive the set of block exchanges, 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 modulo 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 22, wherein, in response to receiving the block exchange instruction, a node device of the multiple node devices performs operations comprising:

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;

in response to a determination that the node device is to serve as a source node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding target node device;

or

in response to a determination that the node device is to serve as a target node device, employ the block exchange rule in parsing the block exchange vector to identify the corresponding source node device.

24. The computer-implemented method of claim 21, wherein, in response to receiving the block exchange instruction, 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 subset of the multiple blocks of data from another node device that is to serve as a source node in the set of block exchanges, a node device of the multiple node devices performs operations comprising:

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

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

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

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

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

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

as part of a registration of the multiple blocks of data by the reduced number of node devices following the performance of the set of block exchanges, receiving by the processor component from each node device of the reduced number of node devices, and for each block of data of the multiple blocks of data, an indication of a size of the block of data or indications of a size of each sub-block of the block of data; and

generating, by the processor component, based at least on the indications of size received during registration, map data indicative of an ordering among the multiple blocks of data by which the multiple blocks of data are to be stored within the one or more storage devices, and which stems from the ordering among the subsets of the multiple blocks of data.

27. The computer-implemented method of claim 26, comprising:

determining, by the processor component, a total size of a combination of at least the map data and of a metadata 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;

determining, by the processor component, whether the total size of the combination meets the minimum threshold size; and

in response to a determination that the combination does not meet the minimum threshold size, performing operations comprising;

identifying, by the processor component, a lowest-order node device or a highest-order node device in the ordering among the multiple node devices that is among the reduced number of node devices; and

transmitting, by the processor component, to the identified lowest-order node device or highest-order node device, and via the network, the combination of the map data and the metadata.

28. The computer-implemented method of claim 27, comprising, in response to a determination that the combination does meet the minimum threshold size, performing operations comprising:

forming, by the processor component, one or more segments for transmission to the one or more storage devices from the combination of the map data and the metadata that each fit within the minimum threshold size and a maximum threshold size imposed on units of data of the data set to be transmitted to one or more storage devices; and

transmitting, by the processor component, to the one or more storage devices via the network, the one or more segments at least partially in parallel with multiple other segments formed from the multiple blocks of data by the reduced number of node devices.

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

the method comprises;

as part of the registration of the multiple blocks of data, receiving, by the processor component, for each sub-block of each block of data, a hashed value indicative of a partition with which the sub-block is associated; and

generating, by the processor component, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the size and hashed value of each sub-block within the block of data.

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

the method comprises;

as part of the registration of multiple blocks of data, receiving, by the processor component, for each block of data of the multiple blocks of data, data block encryption data by which the block of data is encrypted; and

generating, by the processor component, within the map data and for each block of data of the multiple blocks of data, a separate map entry that comprises the data block encryption data for the block of data.