Dynamic distributed generation of data representations from highly condensed data

• US 9,817,882 B2
• Filed: 03/30/2017
• Issued: 11/14/2017
• Est. Priority Date: 03/30/2016
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Christian, Stacey Michelle, Whitcher, Michael Stephen, McAlister, Donald Kent, Hanna, Phillip Elliot
• Primary Examiner(s): Yen, Syling
• Application Number:
  US15/474,636
• Publication Number:
  US 20170286520A1
• Time in Patent Office: 229 Days
• Field of Search: 707791, 707802, 707803, 707809, 707812, 7079991
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

An apparatus includes a processor and a storage storing instructions causing the processor to receive representation metadata indicating features of representation data to be generated from a plurality of representation portions, receive a command to generate at least one row of the representation data, determine a subset of data blocks of a data blob required to generate the at least one row, and a subset of node devices that store the subset of data blocks, for each node device of the subset of node devices, derive a node block map identifying at least one data item of a data block for generating a representation portion, transmit the node block maps to the subset of node devices; and transmit a command to the subset of node devices to each generate at least one row of one of the plurality of representation portions.

Claims

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

transmit, from a coordinating device to a plurality of node devices of a grid of node devices, a command to store a plurality of data blocks of a data blob, wherein;

the plurality of data blocks of the data blob are distributed among the plurality of node devices to be stored by the plurality of node devices;

the data blob comprises multiple data items; and

each data block of the plurality of data blocks comprises a subset of the multiple data items;

receive, at the coordinating device, representation metadata comprising an indication of features of representation data, wherein;

the representation data provides a two-dimensional (2D) representation of data items of the data blob; and

the representation data is to be assembled from a plurality of representation portions to be derived by the plurality of node devices from the plurality of data blocks;

receive, at the coordinating device, a command from a requesting device to generate at least one row of the representation data;

use the representation metadata, a data blob metadata and a master block map to determine a subset of data blocks of the plurality of data blocks that are required to generate the at least one row of the 2D representation, and a subset of node devices of the plurality of node devices that store the subset of the plurality of data blocks, wherein;

the data blob metadata comprises an indication of organization of the multiple data items within the data blob and an indication of at least one rule that limits distribution of the multiple data items of the data blob among the plurality of data blocks; and

the master block map comprises an indication of the distribution of the multiple data items within the data blob among the plurality of data blocks, and an indication of the distribution of the plurality of data blocks among the plurality of node devices;

use the representation metadata and the master block map to derive a node block map of a plurality of node block maps for each node device of the subset of node devices, wherein;

each node block map identifies at least one data item of the subset of data items of a data block from which to generate at least one row of a representation portion of the plurality of representation portions; and

each node block map indicates a selection of a reader routine to use to derive a transform to use with the data block to generate the at least one row of the representation portion;

transmit, from the coordinating device, each node block map of the plurality of node block maps to one of the node devices of the subset of node devices;

transmit, from the coordinating device, a command to each node device of the subset of node devices to generate at least one row of one of the representation portions of the plurality of representation portions;

receive, at the coordinating device, indications from the plurality of node devices of successful generation of at least one row of at least one representation portion of the plurality of representation portions;

receive, at the coordinating device, another command from the requesting device to generate at least one more row of the representation data; and

in response to the receipt of the indications of successful generation of the at least one row of the at least one representation portion, and in response to the receipt of the other command, transmit, from the coordinating device, a command to generate at least one more row of the plurality of representation portions to the subset of node devices.

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

receive, at the coordinating device, the data blob metadata from at least one source device;

determine a size of the data blob from the data blob metadata;

receive, at the coordinating device, instances of node data from each node device of the plurality of node devices; and

determine a quantity of the node devices of the plurality of node devices that are currently available to store the plurality of data blocks.

3. The apparatus of claim 2, wherein the processor is caused to perform operations comprising use the at least one rule of the data blob metadata and indications in the instances of the node data of available storage resources of each node of the plurality of nodes to derive the distribution of the multiple data items of the data blob among the plurality of data blocks.

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

receive, at the coordinating device and from a node device of the subset of node devices, an indication of failure in generating at least one row of a representation portion from a data block of the plurality of data blocks;

select another node device of the plurality of node devices that also stores the data block of the plurality of data blocks to generate the at least one row of the representation portion from the data block; and

transmit, from the coordinating device, a node block map of the plurality of node block maps that corresponds to the at least one row of the representation portion to the another node device.

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

use the representation metadata and an identifier of the requesting device or a entity associated with the requesting device to determine whether the requesting device or the entity is authorized to access data items of the data blob that are required to generate the at least one row of the representation data; and

in response to a determination that either the requesting device or the entity is not authorized to access any of the data items of the data blob that are required to generate the at least one row of the representation data, transmit an indication of failure from the coordinating device to the requesting device.

6. The apparatus of claim 1, wherein the processor is caused to perform operations comprising use at least the representation metadata and the data blob metadata to derive at least one operation to perform with at least one row of at least one representation portion of the plurality of representation portions to generate the at least one row of the representation data.

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

receive, at the coordinating device, the at least one representation portion;

perform the at least one operation with the at least one row of the at least one representation portion to generate the at least one row of the representation data; and

transmit, from the coordinating device, the at least one row of the representation data to the requesting device.

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

receive, at the coordinating device, another command from the requesting device to generate at least one more row of the representation data;

retrieve first state data indicative of a state of the coordinating device after the performance of at least one operations to generate the at least one row of the representation data;

use the first state data to prepare the coordinating device for another performance of the one or more operations with at least one more row of the at least one representation portion to generate the at least one more row of the representation data;

store second state data indicative of a state of the coordinating device after the another performance of the one or more operations to generate the at least one more row of the representation data; and

transmit, from the coordinating device, the at least one more row of the representation data to the requesting device.

9. The apparatus of claim 6, wherein the at least one operation is selected from a group consisting of aggregation of values of the at least one representation portion, averaging of data items of the at least one representation portion, sorting data items of the at least one representation portion, calculating a value of at least one column of the at least one row from a value of at least one other column of the at least one row, and transmitting the at least one row of the representation data to the plurality of node devices for storage.

10. The apparatus of claim 1, wherein:

the data blob comprises a hypercube that employs an indexing scheme of at least 3 dimensions; and

the data blob does not comprise the 2D representation of data provided by the representation data as a slice of the hypercube.

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 to perform operations comprising:

transmit, from a coordinating device to a plurality of node devices of a grid of node devices, a command to store a plurality of data blocks of a data blob, wherein;

the plurality of data blocks of the data blob are distributed among the plurality of node devices to be stored by the plurality of node devices;

the data blob comprises multiple data items; and

each data block of the plurality of data blocks comprises a subset of the multiple data items;

receive, at the coordinating device, representation metadata comprising an indication of features of representation data, wherein;

the representation data provides a two-dimensional (2D) representation of data items of the data blob; and

the representation data is to be assembled from a plurality of representation portions to be derived by the plurality of node devices from the plurality of data blocks;

receive, at the coordinating device, a command from a requesting device to generate at least one row of the representation data;

use the representation metadata, a data blob metadata and a master block map to determine a subset of data blocks of the plurality of data blocks that are required to generate the at least one row of the 2D representation, and a subset of node devices of the plurality of node devices that store the subset of the plurality of data blocks, wherein;

the data blob metadata comprises an indication of organization of the multiple data items within the data blob and an indication of at least one rule that limits distribution of the multiple data items of the data blob among the plurality of data blocks; and

the master block map comprises an indication of the distribution of the multiple data items within the data blob among the plurality of data blocks, and an indication of the distribution of the plurality of data blocks among the plurality of node devices;

use the representation metadata and the master block map to derive a node block map of a plurality of node block maps for each node device of the subset of node devices, wherein;

each node block map identifies at least one data item of the subset of data items of a data block from which to generate at least one row of a representation portion of the plurality of representation portions; and

each node block map indicates a selection of a reader routine to use to derive a transform to use with the data block to generate the at least one row of the representation portion;

transmit, from the coordinating device, each node block map of the plurality of node block maps to one of the node devices of the subset of node devices;

transmit, from the coordinating device, a command to each node device of the subset of node devices to generate at least one row of one of the representation portions of the plurality of representation portions;

receive, at the coordinating device, indications from the plurality of node devices of successful generation of at least one row of at least one representation portion of the plurality of representation portions;

receive, at the coordinating device, another command from the requesting device to generate at least one more row of the representation data; and

in response to the receipt of the indications of successful generation of the at least one row of the at least one representation portion, and in response to the receipt of the other command, transmit, from the coordinating device, a command to generate at least one more row of the plurality of representation portions to the subset of node devices.

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

receive, at the coordinating device, the data blob metadata from at least one source device;

determine a size of the data blob from the data blob metadata;

receive, at the coordinating device, instances of node data from each node device of the plurality of node devices; and

determine a quantity of the node devices of the plurality of node devices that are currently available to store the plurality of data blocks.

13. The computer-program product of claim 12, wherein the processor is caused to perform operations comprising use the at least one rule of the data blob metadata and indications in the instances of the node data of available storage resources of each node of the plurality of nodes to derive the distribution of the multiple data items of the data blob among the plurality of data blocks.

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

receive, at the coordinating device and from a node device of the subset of node devices, an indication of failure in generating at least one row of a representation portion from a data block of the plurality of data blocks;

select another node device of the plurality of node devices that also stores the data block of the plurality of data blocks to generate the at least one row of the representation portion from the data block; and

transmit, from the coordinating device, a node block map of the plurality of node block maps that corresponds to the at least one row of the representation portion to the another node device.

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

use the representation metadata and an identifier of the requesting device or a entity associated with the requesting device to determine whether the requesting device or the entity is authorized to access data items of the data blob that are required to generate the at least one row of the representation data; and

in response to a determination that either the requesting device or the entity is not authorized to access any of the data items of the data blob that are required to generate the at least one row of the representation data, transmit an indication of failure from the coordinating device to the requesting device.

16. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising use at least the representation metadata and the data blob metadata to derive at least one operation to perform with at least one row of at least one representation portion of the plurality of representation portions to generate the at least one row of the representation data.

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

receive, at the coordinating device, the at least one representation portion;

perform the at least one operation with the at least one row of the at least one representation portion to generate the at least one row of the representation data; and

transmit, from the coordinating device, the at least one row of the representation data to the requesting device.

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

receive, at the coordinating device, another command from the requesting device to generate at least one more row of the representation data;

retrieve first state data indicative of a state of the coordinating device after the performance of at least one operations to generate the at least one row of the representation data;

use the first state data to prepare the coordinating device for another performance of the one or more operations with at least one more row of the at least one representation portion to generate the at least one more row of the representation data;

store second state data indicative of a state of the coordinating device after the another performance of the one or more operations to generate the at least one more row of the representation data; and

transmit, from the coordinating device, the at least one more row of the representation data to the requesting device.

19. The computer-program product of claim 11, wherein the at least one rule is selected from a group consisting of a rule specifying at least one atomic unit of data that is not to be divided between two data blocks.

20. The computer-program product of claim 16, wherein the at least one operation is selected from a group consisting of aggregation of values of the at least one representation portion, averaging of data items of the at least one representation portion, sorting data items of the at least one representation portion, calculating a value of at least one column of the at least one row from a value of at least one other column of the at least one row, and transmitting the at least one row of the representation data to the plurality of node devices for storage.

21. A computer-implemented method comprising:

transmitting, from a coordinating device to a plurality of node devices of a grid of node devices, a command to store a plurality of data blocks of a data blob, wherein;

the plurality of data blocks of the data blob are distributed among the plurality of node devices to be stored by the plurality of node devices;

the data blob comprises multiple data items; and

each data block of the plurality of data blocks comprises a subset of the multiple data items;

receiving, at the coordinating device, representation metadata comprising an indication of features of representation data, wherein;

the representation data provides a two-dimensional (2D) representation of data items of the data blob; and

the representation data is to be assembled from a plurality of representation portions to be derived by the plurality of node devices from the plurality of data blocks;

receiving, at the coordinating device, a command from a requesting device to generate at least one row of the representation data;

using the representation metadata, a data blob metadata and a master block map to determine a subset of data blocks of the plurality of data blocks that are required to generate the at least one row of the 2D representation, and a subset of node devices of the plurality of node devices that store the subset of the plurality of data blocks, wherein;

the data blob metadata comprises an indication of organization of the multiple data items within the data blob and an indication of at least one rule that limits distribution of the multiple data items of the data blob among the plurality of data blocks; and

the master block map comprises an indication of the distribution of the multiple data items within the data blob among the plurality of data blocks, and an indication of the distribution of the plurality of data blocks among the plurality of node devices;

using the representation metadata and the master block map to derive a node block map of a plurality of node block maps for each node device of the subset of node devices, wherein;

each node block map identifies at least one data item of the subset of data items of a data block from which to generate at least one row of a representation portion of the plurality of representation portions; and

each node block map indicates a selection of a reader routine to use to derive a transform to use with the data block to generate the at least one row of the representation portion;

transmitting, from the coordinating device, each node block map of the plurality of node block maps to one of the node devices of the subset of node devices;

transmitting, from the coordinating device, a command to each node device of the subset of node devices to generate at least one row of one of the representation portions of the plurality of representation portions;

receiving, at the coordinating device, indications from the plurality of node devices of successful generation of at least one row of at least one representation portion of the plurality of representation portions;

receiving, at the coordinating device, another command from the requesting device to generate at least one more row of the representation data; and

in response to the receipt of the indications of successful generation of the at least one row of the at least one representation portion, and in response to the receipt of the other command, transmitting, from the coordinating device, a command to generate at least one more row of the plurality of representation portions to the subset of node devices.

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

receiving, at the coordinating device, the data blob metadata from at least one source device;

determining, at the coordinating device, a size of the data blob from the data blob metadata;

receiving, at the coordinating device, instances of node data from each node device of the plurality of node devices; and

determining, at the coordinating device, a quantity of the node devices of the plurality of node devices that are currently available to store the plurality of data blocks.

23. The computer-implemented method of claim 22, comprising using the at least one rule of the data blob metadata and indications in the instances of the node data of available storage resources of each node of the plurality of nodes to derive the distribution of the multiple data items of the data blob among the plurality of data blocks.

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

receiving, at the coordinating device and from a node device of the subset of node devices, an indication of failure in generating at least one row of a representation portion from a data block of the plurality of data blocks;

selecting, at the coordinating device, another node device of the plurality of node devices that also stores the data block of the plurality of data blocks to generate the at least one row of the representation portion from the data block; and

transmitting, from the coordinating device, a node block map of the plurality of node block maps that corresponds to the at least one row of the representation portion to the another node device.

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

using the representation metadata and an identifier of the requesting device or a entity associated with the requesting device to determine whether the requesting device or the entity is authorized to access data items of the data blob that are required to generate the at least one row of the representation data; and

in response to a determination that either the requesting device or the entity is not authorized to access any of the data items of the data blob that are required to generate the at least one row of the representation data, transmitting an indication of failure from the coordinating device to the requesting device.

26. The computer-implemented method of claim 21, comprising using at least the representation metadata and the data blob metadata to derive at least one operation to perform with at least one row of at least one representation portion of the plurality of representation portions to generate the at least one row of the representation data.

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

receiving, at the coordinating device, the at least one representation portion;

performing the at least one operation with the at least one row of the at least one representation portion to generate the at least one row of the representation data; and

transmitting, from the coordinating device, the at least one row of the representation data to the requesting device.

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

receiving, at the coordinating device, another command from the requesting device to generate at least one more row of the representation data;

retrieving first state data indicative of a state of the coordinating device after the performance of at least one operations to generate the at least one row of the representation data;

using the first state data to prepare the coordinating device for another performance of the one or more operations with at least one more row of the at least one representation portion to generate the at least one more row of the representation data;

storing second state data indicative of a state of the coordinating device after the another performance of the one or more operations to generate the at least one more row of the representation data; and

transmitting, from the coordinating device, the at least one more row of the representation data to the requesting device.

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

the data blob comprises a hypercube that employs an indexing scheme of at least 3 dimensions; and

the data blob does not comprise the 2D representation of data provided by the representation data as a slice of the hypercube.

30. The computer-implemented method of claim 21, wherein the at least one rule is selected from a group consisting of a rule specifying at least one atomic unit of data that is not to be divided between two data blocks.