DISTRIBUTED DATA SET STORAGE AND RETRIEVAL

• US 20170031599A1
• Filed: 07/26/2016
• Published: 02/02/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
• Granted Patent: US 9,619,148 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 includes a processor component caused to: retrieve metadata of organization of data within a data set, and map data of organization of data blocks within a data file; receive indications of which node devices are available to perform a processing task with a data set portion; and in response to the data set including partitioned data, compare the quantities of available node devices and of the node devices last involved in storing the data set. In response to a match, for each map data map entry: retrieve a hashed identifier for a data sub-block, and a size for each of the data sub-blocks within the corresponding data block; divide the hashed identifier by the quantity of available node devices; compare the modulo value to a designation assigned to each of the available node devices; and provide a pointer to the available node device assigned the matching designation.

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:

retrieve, from one or more storage devices through a network, metadata indicative of organization of data within a data set, and map data indicative of organization of multiple data blocks within a data file maintained by the one or more storage devices, wherein;

the map data 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;

receive, from multiple node devices, indications of which node devices among the multiple node devices are available node devices that are each able to perform a processing task with at least one data set portion of the one or more data set portions; and

in response to an indication within the metadata or the map data that the data set comprises partitioned data wherein the data within the data set is organized into multiple partitions that are each distributable to a single node device, and each map entry corresponds to a single data block;

determine a first quantity of the available node devices based on the indications of which node devices are available node devices;

retrieve a second quantity of node devices last involved in storage of the data set within the data file from the metadata or the map data;

compare the first and second quantities of node devices to detect a match between the first and second quantities;

assign each of the available node devices one of a series of positive integer values as a designation value, wherein the series extends from an integer value of 0 to a positive integer value equal to the first quantity minus the integer value of 1; and

in response to detection of a match between the first and second quantities, for each map entry of the map data;

retrieve, from the map entry, a hashed identifier for one data sub-block indicated in the map entry as within the corresponding data block, and a data sub-block size for each of the data sub-blocks indicated in the map entry as within the corresponding data block, wherein;

the hashed identifier is derived from a partition label of a partition of the multiple partitions; and

the data sub-block comprises a data set portion of the one or more data set portions;

determine a location of the corresponding data block within the data file;

divide the hashed identifier by the first quantity to obtain a modulo value;

compare the modulo value to the designation value assigned to each of the available node devices to identify an available node device assigned a designation value that matches the modulo value; and

provide a pointer to the available node device assigned the designation value that matches the modulo value, the pointer comprising;

an indication of the location of the corresponding data block; and

a sum of the data sub-block sizes of all of the data sub-blocks within the corresponding data block.

2. The apparatus of claim 1, wherein in response to the indication that the data set comprises partitioned data and in response to detection of a lack of a match between the first and second quantities, the processor component is caused to perform operations comprising:

for each indication within each map entry of a data sub-block within a corresponding data block;

retrieve, from the map entry, the data sub-block size and hashed identifier of the data sub-block;

determine a location of the data sub-block within the data file;

divide the hashed identifier by the first quantity to obtain a modulo value;

compare the modulo value to the designation value assigned to each of the available node devices to identify an available node device assigned a designation value that matches the modulo value; and

provide a pointer to the available node device assigned the designation value that matches the modulo value, the pointer comprising;

an indication of the location of the data sub-block; and

the data sub-block size.

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

in response to an indication within the metadata or the map data that the data set does not comprise partitioned data, for each map entry of the map data;

retrieve, from the map entry, a data block size and a data block quantity, wherein the data block quantity indicates a quantity of adjacent data blocks in the data file that correspond to the map entry; and

for each data block that corresponds to the map entry;

determine a location of the corresponding data block within the data file;

select one of the available node devices; and

provide a pointer to the selected one of the available node devices, the pointer comprising;

an indication of the location of the corresponding data block; and

the data block size.

4. The apparatus of claim 3, wherein the selection of one of the available node devices comprises a round robin selection of one of the available node devices.

5. The apparatus of claim 1, wherein the apparatus comprises one of the available node devices.

6. The apparatus of claim 5, wherein the processor component performs a processing task with at least one data set portion retrieved from the data file as the one of the available node devices at least partially in parallel with at least one other of the available node devices.

7. The apparatus of claim 1, wherein to retrieve the map data from the one or more storage devices, the processor component is caused to perform operations comprising:

retrieve a map base from the data file;

analyze the map base to determine whether at least a portion of the map data is stored within one or more map extensions within the data file; and

in response to a determination that at least a portion of the map data is stored within one or more map extensions;

retrieve the one or more map extensions from the data file; and

retrieve at least a subset of the map entries from the one or more map extensions.

8. The apparatus of claim 7, wherein in response to a determination that no portion of the map data is stored within one or more map extensions, the processor is caused to perform operations comprising retrieve all of the map entries from the map base.

9. The apparatus of claim 1, wherein to receive indications of which node devices among the multiple node devices are available, the processor component is caused to perform operations comprising:

recurringly receive indications of status from the multiple node devices; and

recurringly update a stored indication of the availability of each node device of the multiple node devices.

10. The apparatus of claim 1, wherein the processor component is caused to perform operations comprising provide an indication of a task to perform with the data set to the multiple node devices to enable at least a first node device of the multiple node devices to perform the task with a first data set portion of the data set and at least a second node device of the multiple node devices to perform the task with a second data set portion of the data set at least partially in parallel.

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:

retrieve, from one or more storage devices through a network, metadata indicative of organization of data within a data set, and map data indicative of organization of multiple data blocks within a data file maintained by the one or more storage devices, wherein;

the map data 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;

receive, from multiple node devices, indications of which node devices among the multiple node devices are available node devices that are each able to perform a processing task with at least one data set portion of the one or more data set portions; and

in response to an indication within the metadata or the map data that the data set comprises partitioned data wherein the data within the data set is organized into multiple partitions that are each distributable to a single node device, and each map entry corresponds to a single data block;

determine a first quantity of the available node devices based on the indications of which node devices are available node devices;

retrieve a second quantity of node devices last involved in storage of the data set within the data file from the metadata or the map data;

compare the first and second quantities of node devices to detect a match between the first and second quantities;

assign each of the available node devices one of a series of positive integer values as a designation value, wherein the series extends from an integer value of 0 to a positive integer value equal to the first quantity minus the integer value of 1; and

in response to detection of a match between the first and second quantities, for each map entry of the map data;

retrieve, from the map entry, a hashed identifier for one data sub-block indicated in the map entry as within the corresponding data block, and a data sub-block size for each of the data sub-blocks indicated in the map entry as within the corresponding data block, wherein;

the hashed identifier is derived from a partition label of a partition of the multiple partitions; and

the data sub-block comprises a data set portion of the one or more data set portions;

determine a location of the corresponding data block within the data file;

divide the hashed identifier by the first quantity to obtain a modulo value;

compare the modulo value to the designation value assigned to each of the available node devices to identify an available node device assigned a designation value that matches the modulo value; and

provide a pointer to the available node device assigned the designation value that matches the modulo value, the pointer comprising;

an indication of the location of the corresponding data block; and

a sum of the data sub-block sizes of all of the data sub-blocks within the corresponding data block.

12. The computer-program product of claim 11, wherein in response to the indication that the data set comprises partitioned data and in response to detection of a lack of a match between the first and second quantities, the processor component is caused to perform operations comprising:

for each indication within each map entry of a data sub-block within a corresponding data block;

retrieve, from the map entry, the data sub-block size and hashed identifier of the data sub-block;

determine a location of the data sub-block within the data file;

divide the hashed identifier by the first quantity to obtain a modulo value;

compare the modulo value to the designation value assigned to each of the available node devices to identify an available node device assigned a designation value that matches the modulo value; and

provide a pointer to the available node device assigned the designation value that matches the modulo value, the pointer comprising;

an indication of the location of the data sub-block; and

the data sub-block size.

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

in response to an indication within the metadata or the map data that the data set does not comprise partitioned data, for each map entry of the map data;

retrieve, from the map entry, a data block size and a data block quantity, wherein the data block quantity indicates a quantity of adjacent data blocks in the data file that correspond to the map entry; and

for each data block that corresponds to the map entry;

determine a location of the corresponding data block within the data file;

select one of the available node devices; and

provide a pointer to the selected one of the available node devices, the pointer comprising;

an indication of the location of the corresponding data block; and

the data block size.

14. The computer-program product of claim 13, wherein the selection of one of the available node devices comprises a round robin selection of one of the available node devices.

15. The computer-program product of claim 13, wherein the processor component is caused to perform operations comprising employ, in response to the data set not comprising partitioned data, the indication of the location and data block size of a data block corresponding to one of the map entries to retrieve the data block from the data file as one of the available node devices at least partially in parallel with at least one other of the available node devices.

16. The computer-program product of claim 15, wherein the processor component is caused to perform operations comprising perform a processing task with the data block as the one of the available node devices at least partially in parallel with at least one other of the available node devices.

17. The computer-program product of claim 11, wherein to retrieve the map data from the one or more storage devices, the processor component is caused to perform operations comprising:

retrieve a map base from the data file;

analyze the map base to determine whether at least a portion of the map data is stored within one or more map extensions within the data file; and

in response to a determination that at least a portion of the map data is stored within one or more map extensions;

retrieve the one or more map extensions from the data file; and

retrieve at least a subset of the map entries from the one or more map extensions.

18. The computer-program product of claim 17, wherein in response to a determination that no portion of the map data is stored within one or more map extensions, the processor component is caused to perform operations comprising retrieve all of the map entries from the map base.

19. The computer-program product of claim 11, wherein to receive indications of which node devices among the multiple node devices are available, the processor component is caused to perform operations comprising:

recurringly receive indications of status from the multiple node devices; and

recurringly update a stored indication of the availability of each node device of the multiple node devices.

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

provide an indication of a task to perform with the data set to the multiple node devices to enable at least a first node device of the multiple node devices to perform the task with a first data set portion of the data set; and

perform the task with a second data set portion of the data set, as a second node device, at least partially in parallel with the performance of the task by the first node device.

21. A computer-implemented method comprising:

retrieving, from one or more storage devices through a network, metadata indicative of organization of data within a data set, and map data indicative of organization of multiple data blocks within a data file maintained by the one or more storage devices, wherein;

the map data 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;

receiving, from multiple node devices, indications of which node devices among the multiple node devices are available node devices that are each able to perform a processing task with at least one data set portion of the one or more data set portions; and

in response to an indication within the metadata or the map data that the data set comprises partitioned data wherein the data within the data set is organized into multiple partitions that are each distributable to a single node device, and each map entry corresponds to a single data block;

determining a first quantity of the available node devices based on the indications of which node devices are available node devices;

retrieving a second quantity of node devices last involved in storage of the data set within the data file from the metadata or the map data;

comparing the first and second quantities of node devices to detect a match between the first and second quantities; and

assigning each of the available node devices one of a series of positive integer values as a designation value, wherein the series extends from an integer value of 0 to a positive integer value equal to the first quantity minus the integer value of 1; and

in response to detection of a match between the first and second quantities, for each map entry of the map data;

retrieving, from the map entry, a hashed identifier for one data sub-block indicated in the map entry as within the corresponding data block, and a data sub-block size for each of the data sub-blocks indicated in the map entry as within the corresponding data block, wherein;

the hashed identifier is derived from a partition label of a partition of the multiple partitions; and

the data sub-block comprises a data set portion of the one or more data set portions;

determining a location of the corresponding data block within the data file;

dividing the hashed identifier by the first quantity to obtain a modulo value;

comparing the modulo value to the designation value assigned to each of the available node devices to identify an available node device assigned a designation value that matches the modulo value; and

providing a pointer to the available node device assigned the designation value that matches the modulo value, the pointer comprising;

an indication of the location of the corresponding data block; and

a sum of the data sub-block sizes of all of the data sub-blocks within the corresponding data block.

22. The computer-implemented method of claim 21, comprising, in response to the indication that the data set comprises partitioned data and in response to detection of a lack of a match between the first and second quantities:

for each indication within each map entry of a data sub-block within a corresponding data block;

retrieving, from the map entry, the data sub-block size and hashed identifier of the data sub-block;

determining a location of the data sub-block within the data file;

dividing the hashed identifier by the first quantity to obtain a modulo value;

comparing the modulo value to the designation value assigned to each of the available node devices to identify an available node device assigned a designation value that matches the modulo value; and

providing a pointer to the available node device assigned the designation value that matches the modulo value, the pointer comprising;

an indication of the location of the data sub-block; and

the data sub-block size.

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

in response to an indication within the metadata or the map data that the data set does not comprise partitioned data, for each map entry of the map data;

retrieving, from the map entry, a data block size and a data block quantity, wherein the data block quantity indicates a quantity of adjacent data blocks in the data file that correspond to the map entry; and

for each data block that corresponds to the map entry;

determining a location of the corresponding data block within the data file;

selecting one of the available node devices; and

providing a pointer to the selected one of the available node devices, the pointer comprising;

an indication of the location of the corresponding data block; and

the data block size.

24. The computer-implemented method of claim 23, wherein selecting one of the available node devices comprises a round robin selection of one of the available node devices.

25. The computer-implemented method of claim 21, comprising, in response to the data set comprising partitioned data, acting as one of the available node devices by employing the indication of the location and data block size of a data block corresponding to one of the map entries to retrieve the data block from the data file at least partially in parallel with at least one other of the available node devices.

26. The computer-implemented method of claim 25, comprising performing a processing task with each data sub-block within the data block as the one of the available node devices at least partially in parallel with at least one other of the available node devices.

27. The computer-implemented method of claim 21, wherein retrieving the map data from the one or more storage devices comprises:

retrieving a map base from the data file;

analyzing the map base to determine whether at least a portion of the map data is stored within one or more map extensions within the data file; and

in response to a determination that at least a portion of the map data is stored within one or more map extensions;

retrieving the one or more map extensions from the data file; and

retrieving at least a subset of the map entries from the one or more map extensions.

28. The computer-implemented method of claim 27, wherein retrieving the map data from the one or more storage devices comprises, in response to a determination that no portion of the map data is stored within one or more map extensions, retrieving all of the map entries from the map base.

29. The computer-implemented method of claim 21, wherein receiving indications of which node devices among the multiple node devices are available comprises:

recurringly receiving indications of status from the multiple node devices; and

recurringly updating a stored indication of the availability of each node device of the multiple node devices.

30. The computer-implemented method of claim 21, comprising providing an indication of a task to perform with the data set to the multiple node devices to enable at least a first node device of the multiple node devices to perform the task with a first data set portion of the data set and at least a second node device of the multiple node devices to perform the task with a second data set portion of the data set at least partially in parallel.