TECHNIQUES FOR DATA RETRIEVAL IN A DISTRIBUTED COMPUTING ENVIRONMENT

• US 20140280247A1
• Filed: 03/18/2014
• Published: 09/18/2014
• 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
• Granted Patent: US 10,049,159 B2
• Time in Patent Office: Days
• US Class Current: 707/752
• 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, the computing node including a subset of data;

search among the subset of data for a beginning of a data range that is responsive to the data request; and

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

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.

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

4. The at least one non-transitory machine-readable storage medium of claim 2, 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.

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

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

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

8. The at least one non-transitory machine-readable storage medium of claim 1, further comprising instructions that, when executed by the processor, cause a proposal of one or more values responsive to the data request to another computing node of the distributed computing system during an active phase.

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

10. A computer-implemented method, comprising:

receiving a data request at a computing node of a distributed computing system, the computing node including a subset of data;

searching among the subset of data for a beginning of a data range that is responsive to the data request; and

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

11. The computer-implemented method of claim 10, further comprising sorting the subset of data.

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

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

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

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

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

17. The computer-implemented method of claim 10, further comprising proposing one or more values responsive to the data request to another computing node of the distributed computing system during an active phase.

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

19. An apparatus, comprising:

a processor; and

a memory unit communicatively coupled to the processor, the memory unit to store;

a search module that when executed by the processor is operative to receive a data request at a computing node of a distributed computing system, the computing node including a subset of data, and search among the subset of data for a beginning of a data range that is responsive to the data request; and

a send module that when executed by the processor is operative 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 other data ranges.

20. The apparatus of claim 19, further comprising a sort module that when executed by the processor is operative to sort the subset of data.

21. The apparatus of claim 20, wherein the sort module is further operative to sort the subset of data using a merge sort algorithm.

22. The apparatus of claim 20, wherein the sort module is further operative to sort the subset of data using a T-threaded M-block merge algorithm.

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

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

25. The apparatus of claim 19, wherein the send module is further operative to forward using a heap component utilizing references to one or more blocks of data.

26. The apparatus of claim 19, wherein the search module is further operative to propose one or more values responsive to the data request to another computing node of the distributed computing system during an active phase.

27. The apparatus of claim 26, wherein the search module is further operative to use a tie-breaker is used to ensure that the one or more proposed values are between two values in a local list of values.

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

search among the plurality of computing nodes for a beginning of a data range that is responsive to the data request;

forward the subsets of data between computing nodes within the distributed computing system, the forwarding beginning from a computing node that has the beginning 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.

29. The at least one non-transitory machine readable storage medium of claim 28, further comprising instructions that, when executed by a computing device, cause the computing device to sort each subset of data at each of the plurality of computing nodes.

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

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

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

33. The at least one non-transitory machine-readable storage medium of claim 29, the identifying comprises employing a nested binary search algorithm.

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

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

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

37. The at least one non-transitory machine-readable storage medium of claim 28, further comprising instructions that, when executed by the processor, cause a search module to propose one or more values responsive to the data request to one or more computing nodes within the distributed computing system during an active phase.

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

39. The at least one non-transitory machine readable storage medium of claim 28, wherein searching further comprises:

performing a finding phase in which a binary search is used to determine how many locally stored values are less than a proposed value;

performing an active phase in which values are shared with other computing nodes within the distributed system based upon the finding phase; and

performing a bracketing phase in which a greatest local value known to be globally less than the proposed value is shared with the other computing nodes within the distributed system.

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

searching among the plurality of computing nodes for a beginning of a data range that is responsive to the data request;

forwarding the subsets of data between computing nodes within the distributed computing system, the forwarding beginning from a computing node that has the beginning 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.

41. The computer-implemented method of claim 40, further comprising sorting each subset of data at each of the plurality of computing nodes.

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

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

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

45. The computer-implemented method of claim 40, wherein the identifying comprises employing a nested binary search algorithm.

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

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

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

49. The computer-implemented method of claim 40, further comprising proposing one or more values responsive to the data request to one or more computing nodes within the distributed computing system during an active phase.

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

51. The computer-implemented method of claim 40, wherein searching further comprises:

performing a finding phase in which a binary search is used to determine how many locally stored values are less than a proposed value;

performing an active phase in which values are shared with other computing nodes within the distributed system based upon the finding phase; and

performing a bracketing phase in which a greatest local value known to be globally less than the proposed value is shared with the other computing nodes within the distributed system.

52. An apparatus, comprising:

a processor; and

a memory unit communicatively coupled to the processor, the memory unit to store;

a search module that when executed by the processor is operative to receive a data request at a distributed computing system including a plurality of computing nodes, each computing node including a subset of data, and search among the plurality of computing nodes for a beginning of a data range that is responsive to the data request;

a send module that when executed by the processor is operative to forward the subsets of data between computing nodes within the distributed computing system, the forwarding beginning from a computing node that has the beginning of the data range found from the search; and

a merge module that when executed by the processor is operative to merge the forwarded subsets of data into a final data range responsive to the data request.

53. The apparatus of claim 52, further comprising a sort module that when executed by the processor is operative to sort each subset of data at each of the plurality of computing nodes.

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

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

56. The apparatus of claim 52, wherein the search module is further operative to identify a computing node among the plurality of computing nodes that includes a subset of data that has the beginning of the data range that is responsive to the data request.

57. The apparatus of claim 52, wherein the identifying comprises employing a nested binary search algorithm.

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

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

60. The apparatus of claim 52, wherein the merge module is further operative to use a heap component utilizing references to one or more blocks of data.

61. The apparatus of claim 52, wherein the search module is further operative to propose one or more values responsive to the data request to one or more computing nodes within the distributed computing system during an active phase.

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

63. The apparatus of claim 52, wherein the search module is further operative to:

perform a finding phase in which a binary search is used to determine how many locally stored values are less than a proposed value;

perform an active phase in which values are shared with other computing nodes within the distributed system based upon the finding phase; and

perform a bracketing phase in which a greatest local value known to be globally less than the proposed value is shared with the other computing nodes within the distributed system.