Distributed data set storage and retrieval

• US 9,811,524 B2
• Filed: 07/26/2016
• Issued: 11/07/2017
• Est. Priority Date: 07/27/2015
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Bowman, Brian Payton, Krueger, Steven E., Knight, Richard Todd, Ho, Chih-Wei
• Primary Examiner(s): Rigol, Yaima
• Assistant Examiner(s): WOOLWINE, SHANE D
• Application Number:
  US15/220,182
• Publication Number:
  US 20170031936A1
• Time in Patent Office: 469 Days
• Field of Search: 711135, 711170-173, 707 47
• 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 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/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/061 Improving I/O performance
• 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

Abstract

An apparatus comprising a processor component to: provide, to a control device, an indication of availability to perform a processing task with one or more data set portions as a node device; perform a processing task specified by the control device with the one or more data set portions; and request a pointer to a location at which to store the one or more data set portions as a data block within a data file. In response to the data set including partitioned data, for each data set portion, include a data sub-block size of the data set portion and a hashed identifier derived from a partition label of a partition in the request; receive, from the control device, the requested pointer to the location; and store each data set portion as a data sub-block within the data block starting at the location within the data file.

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:

provide, to a control device, an indication of being currently available to participate in a performance of a processing task as a node device among multiple node devices;

receive, from the control device, an indication of the processing task to perform with one or more data set portions of multiple data set portions of a data set, wherein the data set comprises data organized in a manner indicated in metadata;

perform the processing task with the one or more data set portions;

provide a request to the control device for a pointer to a location at which to store the one or more data set portions as a data block of multiple data blocks within a data file maintained by one or more storage devices, wherein;

the multiple data blocks are organized within the data file in a manner indicated in map data that comprises multiple map entries; and

each map entry of the multiple map entries corresponds to one or more data blocks of the multiple data blocks;

analyze the metadata to determine whether the metadata indicates that the data set is partitioned;

in response to an indication in the metadata that the data set comprises partitioned data, wherein the data within the data set is organized into multiple partitions that are each distributable to just a single node device, each map entry corresponds to a single data block and the processing task is able to be performed with the data within each partition independently of the data within any other partition of the multiple partitions, the processor component is caused to perform operations comprising;

for each data set portion of the one or more data set portions;

include a data sub-block size indicative of a size of the data set portion in the request;

derive a hashed identifier of a partition label of the partition to which the data set portion belongs of the multiple partitions; and

include the hashed identifier in the request;

receive, from the control device, the requested pointer indicating the location within the data file at which to store the data block; and

after the performance of the processing task with the one or more data set portions, store each data set portion of the one or more data set portions as a data sub-block within the data block starting at the location within the data file; and

in response to a lack of indication in the metadata that the data set comprises partitioned data, the processor component is caused to perform operations comprising;

derive a sum of sizes each data set portion of the one or more data set portions;

include the sum of sizes as a data block size of the data block in the request;

receive, from the control device, the requested pointer indicating the location within the data file at which to store the data block; and

after the performance of the processing task with the one or more data set portions, store the one or more data set portions together as the data block at the location within the data file.

2. The apparatus of claim 1, wherein:

the processing task comprises generation of the data set as an output; and

the processor component is caused to generate at least a portion of the metadata and to provide the at least a portion of the metadata to the control device.

3. The apparatus of claim 1, wherein:

the processing task comprises use of the data set as an input; and

the processor component is caused to receive the metadata from the control device.

4. The apparatus of claim 1, wherein:

the processor component comprises multiple processor cores; and

the processor component is caused to perform the processing task with each data set portion of the one or more data set portions using a separate one of the multiple processor cores at least partially in parallel.

5. The apparatus of claim 4, wherein the processor component is caused to perform the processing task with at least one data set portion of the one or more data set portions at least partially in parallel with a performance, by at least one other node device of the multiple node devices, of the processing task with at least one other data set portion of the multiple data set portions.

6. The apparatus of claim 4, wherein:

each node device of the multiple node devices is required to generate a single request for a pointer for all data set portions with which the processing task is performed by each node device; and

the processor component is caused to generate the request to be associated with all of the data set portions of the one or more data set portions with which the processor component performs the processing task.

7. The apparatus of claim 1, wherein the processor component is caused to store the one or more data portions within the data block within the data file at least partially in parallel with storage of at least one other data set portion of the multiple data set portions by at least one other node device of the multiple node devices.

8. The apparatus of claim 7, wherein the processor component is caused to, in response to completion of storage of the one or more data set portions within the data block within the data file, provide an indication of the completion of the storage to the control device.

9. The apparatus of claim 1, wherein:

the node device comprises a separate and distinct device from any of the one or more storage devices;

the node device comprises the control device implemented as a controller within the node device; and

the controller comprises a controller processor component and a controller storage to store controller instructions that, when executed by the controller processor component, cause the controller processor component to perform operations comprising;

determine the location within the data file at which to store the data block indicated by the requested pointer; and

provide the requested pointer to the processor component.

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

in response to the indication in the metadata that the data set comprises partitioned data;

generate a map entry within the map data that corresponds to the data block;

generate within the map entry a data sub-block count indicative of a quantity of data sub-blocks to be stored by the node device within the data block, wherein each data sub-block comprises a data set portion of the one or more data set portions; and

generate within the map entry a separate map sub-entry for each of the data sub-blocks, wherein each map sub-entry comprises a sub-block size indicative of a size of a corresponding data set portion and a hash identifier derived from a partition label of the partition to which the corresponding data set portion belongs; and

in response to generation of all pointers for the storage of all data set portions of the data set in the data file by all of the multiple node devices, store the map data in the data file.

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

in response to a lack of indication in the metadata that the data set comprises partitioned data;

compare a data block size of the data block to a data block size of an adjacent data block to be stored by another node device of the multiple node devices at an adjacent location within the data file to detect a match between the two data block sizes;

in response to detection of a match between the two data block sizes, increment a data block count of a map entry within the map data that corresponds to the adjacent data block; and

in response to detection of a lack of a match between the two data block sizes, generate a new map entry within the map data that corresponds to the data block, wherein the new map entry comprises a data block count indicative of correspondence to a single data block and a data block size indicative of the size of the data block.

12. The apparatus of claim 1, wherein:

the multiple data blocks are organized within the data file in a manner indicated in map data to be generated by the control device from information provided in the request and in corresponding requests from other node devices of the multiple node devices;

the map data is to be stored by the control device with the data file; and

the map data comprises multiple map entries.

13. The apparatus of claim 1, wherein each partition of the multiple partitions is associated with just a single partition label.

14. The apparatus of claim 1, wherein the data within the data set is organized into multiple partitions that are each distributable to just a single node device to avoid performance of the processing task with the data within any partition of the multiple partitions necessitating an exchange of the data within the partition among two or more nodes of the multiple nodes.

15. 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:

provide, to a control device, an indication of being currently available to participate in a performance of a processing task as a node device among multiple node devices;

receive, from the control device, an indication of the processing task to perform with one or more data set portions of multiple data set portions of a data set, wherein the data set comprises data organized in a manner indicated in metadata;

perform the processing task with the one or more data set portions;

provide a request to the control device for a pointer to a location at which to store the one or more data set portions as a data block of multiple data blocks within a data file maintained by one or more storage devices, wherein;

the multiple data blocks are organized within the data file in a manner indicated in map data that comprises multiple map entries; and

each map entry of the multiple map entries corresponds to one or more data blocks of the multiple data blocks;

analyze the metadata to determine whether the metadata indicates that the data set is partitioned;

in response to an indication in the metadata that the data set comprises partitioned data, wherein the data within the data set is organized into multiple partitions that are each distributable to just a single node device, each map entry corresponds to a single data block and the processing task is able to be performed with the data within each partition independently of the data within any other partition of the multiple partitions, the processor component is caused to perform operations comprising;

for each data set portion of the one or more data set portions;

include a data sub-block size indicative of a size of the data set portion in the request;

derive a hashed identifier of a partition label of the partition to which the data set portion belongs of the multiple partitions; and

include the hashed identifier in the request;

receive, from the control device, the requested pointer indicating the location within the data file at which to store the data block; and

after the performance of the processing task with the one or more data set portions, store each data set portion of the one or more data set portions as a data sub-block within the data block starting at the location within the data file; and

in response to a lack of indication in the metadata that the data set comprises partitioned data, the processor component is caused to perform operations comprising;

derive a sum of sizes each data set portion of the one or more data set portions;

include the sum of sizes as a data block size of the data block in the request;

receive, from the control device, the requested pointer indicating the location within the data file at which to store the data block; and

after the performance of the processing task with the one or more data set portions, store the one or more data set portions together as the data block at the location within the data file.

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

the processing task comprises generation of the data set as an output; and

the processor component is caused to generate at least a portion of the metadata and to provide the at least a portion of the metadata to the control device.

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

the processing task comprises use of the data set as an input; and

the processor component is caused to receive the metadata from the control device.

18. The computer-program product of claim 15, wherein the processor component is caused to perform the processing task with each data set portion of the one or more data set portions using a separate one of multiple processor cores of the processor component at least partially in parallel.

19. The computer-program product of claim 18, wherein the processor component is caused to perform the processing task with at least one data set portion of the one or more data set portions at least partially in parallel with a performance, by at least one other node device of the multiple node devices, of the processing task with at least one other data set portion of the multiple data set portions.

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

each node device of the multiple node devices is required to generate a single request for a pointer for all data set portions with which the processing task is performed by each node device; and

the processor component is caused to generate the request to be associated with all of the data set portions of the one or more data set portions with which the processor component performs the processing task.

21. The computer-program product of claim 15, wherein the processor component is caused to store the one or more data portions within the data block within the data file at least partially in parallel with storage of at least one other data set portion of the multiple data set portions by at least one other node device of the multiple node devices.

22. The computer-program product of claim 21, wherein the processor component is caused to, in response to completion of storage of the one or more data set portions within the data block within the data file, provide an indication of the completion of the storage to the control device.

23. A computer-implemented method comprising:

providing, to a control device, an indication of being currently available to participate in a performance of a processing task as a node device among multiple node devices;

receiving, from the control device, an indication of the processing task to perform with one or more data set portions of multiple data set portions of a data set, wherein the data set comprises data organized in a manner indicated in metadata;

performing the processing task with the one or more data set portions;

providing a request to the control device for a pointer to a location at which to store the one or more data set portions as a data block of multiple data blocks within a data file maintained by one or more storage devices, wherein;

the multiple data blocks are organized within the data file in a manner indicated in map data that comprises multiple map entries; and

each map entry of the multiple map entries corresponds to one or more data blocks of the multiple data blocks;

analyzing the metadata to determine whether the metadata indicates that the data set is partitioned;

in response to an indication in the metadata that the data set comprises partitioned data, wherein the data within the data set is organized into multiple partitions that are each distributable to just a single node device, each map entry corresponds to a single data block and the processing task is able to be performed with the data within each partition independently of the data within any other partition of the multiple partitions, the method comprises;

for each data set portion of the one or more data set portions;

including, in the request, a data sub-block size indicative of a size of the data set portion;

derive a hashed identifier of a partition label of the partition to which the data set portion belongs of the multiple partitions; and

including, in the request, the hashed identifier;

receiving, from the control device, the requested pointer indicating the location within the data file at which to store the data block; and

after performing the processing task with the one or more data set portions, storing each data set portion of the one or more data set portions as a data sub-block within the data block starting at the location within the data file; and

in response to a lack of indication in the metadata that the data set comprises partitioned data;

deriving a sum of sizes each data set portion of the one or more data set portions;

including the sum of sizes as a data block size of the data block in the request

receiving, from the control device, the requested pointer indicating the location within the data file at which to store the data block; and

after performing the processing task with the one or more data set portions, storing the one or more data set portions together as the data block at the location within the data file.

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

the processing task comprises generation of the data set as an output; and

the method comprises generating at least a portion of the metadata and to provide the at least a portion of the metadata to the control device.

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

the processing task comprises use of the data set as an input; and

the method comprises receiving the metadata from the control device.

26. The computer-implemented method of claim 23, comprising performing the processing task with each data set portion of the one or more data set portions using a separate one of multiple processor cores of a processor component of the node device at least partially in parallel.

27. The computer-implemented method of claim 26, comprising performing the processing task with at least one data set portion of the one or more data set portions at least partially in parallel with a performance, by at least one other node device of the multiple node devices, of the processing task with at least one other data set portion of the multiple data set portions.

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

each node device of the multiple node devices is required to generate a single request for a pointer for all data set portions with which the processing task is performed by each node device; and

the method comprises generating the request to be associated with all of the data set portions of the one or more data set portions with which the processor component performs the processing task.

29. The computer-implemented method of claim 23, comprising storing the one or more data portions within the data block within the data file at least partially in parallel with storage of at least one other data set portion of the multiple data set portions by at least one other node device of the multiple node devices.

30. The computer-implemented method of claim 29, comprising, in response to completion of storage of the one or more data set portions within the data block within the data file, providing an indication of the completion of the storage to the control device.