Techniques for data retrieval in a distributed computing environment

• US 10,049,159 B2
• Filed: 03/18/2014
• Issued: 08/14/2018
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Pingenot, Joseph Albert F. S., Bailey, Christopher Daniel
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US14/218,057
• Publication Number:
  US 20140280247A1
• Time in Patent Office: 1,610 Days
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Enhanced techniques for data retrieval in a distributed computing environment are described. A computing node of a distributed computing environment may receive a data request. The computing node may include one or more subsets of data. The computing node may be configured to search among the one or more subset of data for a beginning of a data range that is responsive to the data request. The computing node may be further configured to forward a data range responsive to the search to another computing node of the distributed computing system to be merged with one or more additional data ranges. Other embodiments are described and claimed.

Claims

1. At least one non-transitory machine-readable storage medium comprising instructions that, when executed by a processor, cause the processor to:

receive a data request at a computing node of a distributed computing system to store a set of data, the computing node including a subset of data of the set of data;

sort the subset of data into a defined order via one or more data sorting sessions;

iteratively search among the sorted subset of data for a targeted beginning location of a data range that is responsive to the data request, each iteration to;

receive a proposed value of one or more proposed values from one of a plurality of computing nodes of the distributed computing system, the proposed value used to search for the beginning location of the data range,

utilize a binary search to locate a local insert location for the proposed value, the local insert location local to the subset of data of the computing node, the binary search to;

determine a first sum value of locally stored values indicating a number of locally stored values that are less than the proposed value stored on the computing node,

determine a second sum value of globally stored values less than the proposed value, wherein the globally stored values are values stored on the distributed computing system and the second sum value to include a summation of a number of values stored on other computing nodes of the distributed computing system and the first sum value,

determine whether the second sum value is less than, equal to, or greater than the targeted beginning location,

based on determining the second sum value is less than the targeted beginning location, the local insert location is set as a current lower bound of a bracketed range, and

based on determining the second sum value is greater than the targeted beginning location, the local insert location is set as an upper bound of the bracketed range, and

based on determining that the second sum value equals the targeted beginning location, set the local insert location to be the targeted beginning location, and cease searching among the sorted subset of data,

share, by the computing node, a location of a greatest local value known to be less than the proposed value with the other computing nodes within the distributed system,

cease searching among the sorted subset of data when the bracketed range equals zero, and

determine, during at least one of the iterations, one of the one or more proposed values and share the one of the one or more proposed values with other computing nodes within the distributed computing system; and

forward, from the computing node, data responsive to the search to another computing node of the distributed computing system to be merged with one or more other data from one or more other computing nodes.

2. The at least one non-transitory machine-readable storage medium of claim 1, further comprising instructions that, when executed by the processor, cause the processor to sort the subset of data using a merge sort algorithm.

3. The at least one non-transitory machine-readable storage medium of claim 1, further comprising instructions that, when executed by the processor, cause the processor to sort the subset of data using a T-threaded M-block merge algorithm.

4. The at least one non-transitory machine-readable storage medium of claim 1, wherein the computing node is labeled as a sender node or a merger node.

5. The at least one non-transitory machine-readable storage medium of claim 1, wherein the computing node is configured to forward data using a buffer ring.

6. The at least one non-transitory machine-readable storage medium of claim 1, wherein the forwarding is performed using a heap component utilizing references to one or more blocks of data.

7. The at least one non-transitory machine-readable storage medium of claim 1, wherein a tie-breaker is used to ensure that the one of the one or more proposed values is between two values in a local list of values.

8. A computer-implemented method, comprising:

receive a data request at a computing node of a distributed computing system to store a set of data, the computing node including a subset of data of the set of data;

sorting the subset of data into a defined order via one or more data sorting sessions;

iteratively searching among the sorted subset of data for a targeted beginning location of a data range that is responsive to the data request, each iteration to include;

receiving a proposed value of one or more proposed values from one of a plurality of computing nodes of the distributed computing system, the proposed value used to search for the beginning location of the data range,

utilizing a binary search to locate a local insert location for the proposed value, the local insert location local to the subset of data of the computing node, the binary search including;

determining a first sum value of locally stored values indicating a number of locally stored values that are less than the proposed value stored on the computing node,

determining a second sum value of globally stored values less than the proposed value, wherein the globally stored values are values stored on the distributed computing system and the second sum value to include a summation of a number of values stored on other computing nodes of the distributed computing system and the first sum value,

determining whether the second sum value is less than, equal to, or greater than the targeted beginning location,

based on determining the second sum value is less than the targeted beginning location, the local insert location is set as a current lower bound of a bracketed range, and

based on determining the second sum value is greater than the targeted beginning location, the local insert location is set as an upper bound of the bracketed range, and

based on determining that the second sum value equals the targeted beginning location, set the local insert location to be the targeted beginning location, and cease searching among the sorted subset of data,

sharing, by the computing node, a location of a greatest local value known to be less than the proposed value with the other computing nodes within the distributed system and cease searching among the sorted subset of data when the bracketed range equals zero,

determining, during at least one of the iterations, one of the one or more proposed values and share the one of the one or more proposed values with other computing nodes within the distributed computing system; and

forwarding, from the computing node, data responsive to the search to another computing node of the distributed computing system to be merged with one or more other data from one or more other computing nodes.

9. The computer-implemented method of claim 8, wherein the subset of data is sorted using a merge sort algorithm.

10. The computer-implemented method of claim 8, wherein the subset of data is sorted using a T-threaded M-block merge algorithm.

11. The computer-implemented method of claim 8, wherein the computing node is labeled as a sender node or a merger node.

12. The computer-implemented method of claim 8, wherein the forwarding is performed using a buffer ring.

13. The computer-implemented method of claim 8, wherein the forwarding is performed using a heap component utilizing references to one or more blocks of data.

14. The computer-implemented method of claim 8, wherein a tie-breaker is used to ensure that the one of the one or more proposed values is between two values in a local list of values.

15. An apparatus, comprising:

a processor;

a memory unit communicatively coupled to the processor; and

logic, at least partially implemented by the processor, the logic to;

receive a data request at a computing node of a distributed computing system to store a set of data, the computing node including a subset of data of the set of data,

sort the subset of data into a defined order via one or more data sorting sessions,

iteratively search among the sorted subset of data for a targeted beginning location of a data range that is responsive to the data request, each iteration to;

receive a proposed value of one or more proposed values from one of a plurality of computing nodes of the distributed computing system, the proposed value used to search for the beginning location of the data range,

utilize a binary search to locate a local insert location for the proposed value, the local insert location local to the subset of data of the computing node, the binary search to;

determine a first sum value of locally stored values indicating a number of locally stored values that are less than the proposed value stored on the computing node,

determine a second sum value of globally stored values less than the proposed value, wherein the globally stored values are values stored on the distributed computing system and the second sum value to include a summation of a number of values stored on other computing nodes of the distributed computing system and the first sum value,

determine whether the second sum value is less than, equal to, or greater than the targeted beginning location,

based on determining the second sum value is less than the targeted beginning location, the local insert location is set as a current lower bound of a bracketed range, and

based on determining the second sum value is greater than the targeted beginning location, the local insert location is set as an upper bound of the bracketed range, and

based on determining that the second sum value equals the targeted beginning location, set the local insert location to be the targeted beginning location, and cease searching among the sorted subset of data,

share, by the computing node, a location of a greatest local value known to be less than the proposed value with the other computing nodes within the distributed system and cease searching among the sorted subset of data when the bracketed range equals zero, and

determine, during at least one of the iterations, one of the one or more proposed values and share the one of the one or more proposed values with other computing nodes within the distributed computing system; and

forward, from the computing node, data responsive to the search to another computing node of the distributed computing system to be merged with one or more other data from one or more other computing nodes.

16. The apparatus of claim 15, the logic to sort the subset of data using a merge sort algorithm.

17. The apparatus of claim 15, the logic to sort the subset of data using a T-threaded M-block merge algorithm.

18. The apparatus of claim 15, wherein the computing node is labeled as a sender node or a merger node.

19. The apparatus of claim 15, wherein the computing node is configured to forward data using a buffer ring.

20. The apparatus of claim 15, the logic to forward using a heap component utilizing references to one or more blocks of data.

21. The apparatus of claim 15, the logic to use a tie-breaker is used to ensure that the one of the one or more proposed values is between two values in a local list of values.

22. At least one non-transitory machine-readable storage medium comprising instructions that, when executed by a computing device, cause the computing device to:

receive a data request at a distributed computing system including a plurality of computing nodes, each computing node including a subset of data of a set of data stored by the distributed computing system;

cause each computing node to sort each subset of data into a defined order via one or more data sorting sessions;

cause each of the plurality of computing nodes to iteratively search among the sorted subset of data for a targeted beginning location of a data range that is responsive to the data request, each iteration to;

receive a proposed value of one or more proposed values from one of the plurality of computing nodes of the distributed computing system, the proposed value used to search for the beginning location of the data range,

utilize a binary search to locate a local insert location for the proposed value, the local insert location local to the subset of data of a computing node, the binary search to;

determine a first sum value of locally stored values indicating a number of locally stored values that are less than the proposed value stored on the computing node,

determine a second sum value of globally stored values less than the proposed value, wherein the globally stored values are values stored on the distributed computing system and the second sum value to include a summation of a number of values stored on other computing nodes of the distributed computing system and the first sum value,

determine whether the second sum value is less than, equal to, or greater than the targeted beginning location,

based on determining the second sum value is less than the targeted beginning location, the local insert location is set as a current lower bound of a bracketed range, and

based on determining the second sum value is greater than the targeted beginning location, the local insert location is set as an upper bound of the bracketed range, and

based on determining that the second sum value equals the targeted beginning location, set the local insert location to be the targeted beginning location, and cease searching among the sorted subset of data,

share a location of a greatest local value known to be less than the proposed value with the plurality of computing nodes within the distributed system and cease searching among the sorted subset of data when the bracketed range equals zero,

determine, during at least one of the iterations, one of the one or more proposed values and share the one of the one or more proposed values with the plurality of computing nodes within the distributed computing system; and

cause one or more computing nodes to forward the subsets of data between computing nodes within the distributed computing system, the forwarding beginning from a computing node that has the targeted beginning location of the data range found from the search;

merge the forwarded subsets of data into a final data range responsive to the data request; and

send the final data range to a requesting device.

23. The at least one non-transitory machine-readable storage medium of claim 22, the sorting is performed using a merge sort algorithm.

24. The at least one non-transitory machine-readable storage medium of claim 22, the sorting is performed using a T-threaded M-block merge algorithm.

25. The at least one non-transitory machine readable storage medium of claim 22, further comprising instructions that, when executed by a computing device, cause the computing device to identify the computing node among the plurality of computing nodes that includes a subset of data that has the targeted beginning location of the data range that is responsive to the data request.

26. The at least one non-transitory machine-readable storage medium of claim 22, each of the plurality of computing nodes is labeled as a sender node or a merger node.

27. The at least one non-transitory machine-readable storage medium of claim 26, wherein sender nodes and merger nodes are configured to send subsets of data using a buffer ring.

28. The at least one non-transitory machine-readable storage medium of claim 22, wherein the merging is performed using a heap component utilizing references to one or more blocks of data.

29. The at least one non-transitory machine readable storage medium of claim 22, wherein a tie-breaker is used to ensure that the one of the one or more proposed values is between two values in a local list of values.

30. A computer-implemented method, comprising:

receiving a data request at a distributed computing system including a plurality of computing nodes, each computing node including a subset of data of a set of data stored by the distributed computing system;

causing each computing node to sort each subset of data into a defined order via one or more data sorting sessions;

cause each of the plurality of computing nodes to iteratively search among the sorted subset of data for a targeted beginning location of a data range that is responsive to the data request, each iteration to include;

receiving a proposed value of one or more proposed values from one of the plurality of computing nodes of the distributed computing system, the proposed value used to search for the beginning location of the data range,

utilizing a binary search to locate a local insert location for the proposed value, the local insert location local to the subset of data of a computing node, the binary search including;

determining a first sum value of locally stored values indicating a number of locally stored values that are less than the proposed value stored on the computing node,

determining a second sum value of globally stored values less than the proposed value, wherein the globally stored values are values stored on the distributed computing system and the second sum value to include a summation of a number of values stored on other computing nodes of the distributed computing system and the first sum value,

determining whether the second sum value is less than, equal to, or greater than the targeted beginning location,

based on determining the second sum value is less than the targeted beginning location, the local insert location is set as a current lower bound of a bracketed range, and

based on determining the second sum value is greater than the targeted beginning location, the local insert location is set as an upper bound of the bracketed range, and

based on determining that the second sum value equals the targeted beginning location, set the local insert location to be the targeted beginning location, and cease searching among the sorted subset of data,

sharing a location of a greatest local value known to be less than the proposed value with the plurality of computing nodes within the distributed system and cease searching among the sorted subset of data when the bracketed range equals zero,

determining, during at least one of the iterations, one of the one or more proposed values and share the one of the one or more proposed values with the plurality of computing nodes within the distributed computing system; and

cause one or more computing nodes to forward the subsets of data between computing nodes within the distributed computing system, the forwarding beginning from a computing node that has the targeted beginning location of the data range found from the search;

merging the forwarded subsets of data into a final data range responsive to the data request; and

sending the final data range to a requesting device.

31. The computer-implemented method of claim 30, the sorting is performed using a merge sort algorithm.

32. The computer-implemented method of claim 30, the sorting is performed using a T-threaded M-block merge algorithm.

33. The computer-implemented method of claim 30, further comprising identifying a computing node among the plurality of computing nodes that includes a subset of data that has the targeted beginning location of the data range that is responsive to the data request.

34. The computer-implemented method of claim 30, wherein each of the plurality of computing nodes is labeled as a sender node or a merger node.

35. The computer-implemented method of claim 34, wherein sender nodes and merger nodes are configured to send subsets of data using a buffer ring.

36. The computer-implemented method of claim 30, wherein the merging is performed using a heap component utilizing references to one or more blocks of data.

37. The computer-implemented method of claim 30, wherein a tie-breaker is used to ensure that the one of the one or more proposed values is between two values in a local list of values.

38. An apparatus, comprising:

a processor;

a memory unit communicatively coupled to the processor; and

logic, at least partially implemented by the processor, the logic to;

receive a data request at a distributed computing system including a plurality of computing nodes, each computing node including a subset of data of a set of data stored by the distributed computing system,

cause each computing node to sort each subset of data into a defined order via one or more data sorting sessions,

cause each of the plurality of computing nodes to iteratively search among the sorted subset of data for a targeted beginning location of a data range that is responsive to the data request, each iteration to;

receive a proposed value of one or more proposed values from one of the plurality of computing nodes of the distributed computing system, the proposed value used to search for the beginning location of the data range,

utilize a binary search to locate a local insert location for the proposed value, the local insert location local to the subset of data of a computing node, the binary search to;

determine a first sum value of locally stored values indicating a number of locally stored values that are less than the proposed value stored on the computing node,

determine a second sum value of globally stored values less than the proposed value, wherein the globally stored values are values stored on the distributed computing system and the second sum value to include a summation of a number of values stored on other computing nodes of the distributed computing system and the first sum value,

determine whether the second sum value is less than, equal to, or greater than the targeted beginning location,

based on determining the second sum value is less than the targeted beginning location, the local insert location is set as a current lower bound of a bracketed range, and

based on determining the second sum value is greater than the targeted beginning location, the local insert location is set as an upper bound of the bracketed range, and

based on determining that the second sum value equals the targeted beginning location, set the local insert location to be the targeted beginning location and cease searching among the sorted subset of data,

share a location of a greatest local value known to be less than the proposed value with the plurality of computing nodes within the distributed system and cease searching among the sorted subset of data when the bracketed range equals zero,

determine, during at least one of the iterations, one of the one or more proposed values and share the one of the one or more proposed values with the plurality of computing nodes within the distributed computing system, and

cause one or more computing nodes to forward the subsets of data between computing nodes within the distributed computing system, the forwarding beginning from a computing node that has the targeted beginning location of the data range found from the search, and

merge the forwarded subsets of data into a final data range responsive to the data request.

39. The apparatus of claim 38, wherein the sorting is performed using a merge sort algorithm.

40. The apparatus of claim 38, wherein the sorting is performed using a T-threaded M-block merge algorithm.

41. The apparatus of claim 38, the logic to identify the computing node among the plurality of computing nodes that includes a subset of data that has the targeted beginning location of the data range that is responsive to the data request.

42. The apparatus of claim 38, wherein each of the plurality of computing nodes is labeled as a sender node or a merger node.

43. The apparatus of claim 38, wherein sender nodes and merger nodes are configured to send subsets of data using a buffer ring.

44. The apparatus of claim 38, the logic to use a heap component utilizing references to one or more blocks of data.

45. The apparatus of claim 38, wherein a tie-breaker is used to ensure that the one of the one or more proposed values is between two values in a local list of values.