Method and System for Accelerated Stream Processing

• US 20090287628A1
• Filed: 05/15/2008
• Published: 11/19/2009
• Est. Priority Date: 05/15/2008
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Exegy Incorporated
• Inventors: Singla, Naveen, White, Jason R., Indeck, Ronald S., Indeck, David Mark
• Granted Patent: US 8,374,986 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C

Abstract

Disclosed herein is a method and system for hardware-accelerating various data processing operations in a rule-based decision-making system such as a business rules engine, an event stream processor, and a complex event stream processor. Preferably, incoming data streams are checked against a plurality of rule conditions. Among the data processing operations that are hardware-accelerated include rule condition check operations, filtering operations, and path merging operations. The rule condition check operations generate rule condition check results for the processed data streams, wherein the rule condition check results are indicative of any rule conditions which have been satisfied by the data streams. The generation of such results with a low degree of latency provides enterprises with the ability to perform timely decision-making based on the data present in received data streams.

Claims

1. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor; and

processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied, wherein the processing is performed by the coprocessor.

2. The method of claim 1 further comprising:

enhancing the bit stream with at least one bit corresponding to the rule condition checking result.

3. The method of claim 2 wherein the coprocessor comprises a reconfigurable logic device.

4. The method of claim 3 wherein the reconfigurable logic device has firmware deployed thereon, wherein the firmware is configured to perform the processing step.

5. The method of claim 4 wherein the firmware is further configured to perform the enhancing step.

6. The method of claim 2 wherein the processing step comprises:

performing a hardware-accelerated rule condition check operation on the bit stream portion that compares the bit stream portion with a plurality of rule conditions; and

in response to the performing step resulting in a finding that the bit stream portion satisfies at least one of the rule conditions, generating a rule condition check result that is indicative of a satisfaction of the at least one rule condition.

7. The method of claim 6 wherein the hardware-accelerated rule condition check operation comprises a hardware-accelerated matching operation.

8. The method of claim 7 wherein the hardware-accelerated matching operation comprises a hardware-accelerated exact word matching operation.

9. The method of claim 7 wherein the hardware-accelerated matching operation comprises a hardware-accelerated approximate word matching operation.

10. The method of claim 7 wherein the hardware-accelerated matching operation comprises a hardware-accelerated regular expression pattern matching operation.

11. The method of claim 7 further comprising wherein the processing step further comprises:

filtering the received bit stream using the coprocessor to thereby provide a reduced bit stream for use by the performing step.

12. The method of claim 11 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein the filtering step comprises passing only data corresponding to at least one pre-selected data field to the performing step.

13. The method of claim 7 wherein the hardware-accelerated rule condition check operation comprises a hardware-accelerated range check operation.

14. The method of claim 7 wherein the hardware-accelerated rule condition check operation comprises a hardware-accelerated threshold check operation.

15. The method of claim 1 wherein the bit stream comprises a plurality of records, and wherein the enhancing step comprises generating a new record for insertion in the bit stream, the new record being indicative of the generated rule condition check result.

16. The method of claim 1 wherein the bit stream comprises a plurality of records, and wherein the enhancing step comprises appending a bit string indicative of the generated rule condition check result to the record for which the rule condition check result was generated.

17. The method of claim 1 further comprising:

passing the enhanced bit stream out of the coprocessor for post-processing that is based at least in part on the generated rule condition check result.

18. The method of claim 17 further comprising:

performing the post-processing, wherein the post-processing comprises routing at least a portion of the enhanced bit stream to a particular destination within a network based at least in part on the generated rule condition check result.

19. The method of claim 17 further comprising:

performing the post-processing, wherein the post-processing comprises (1) selecting a location within a network for storing at least a portion of the enhanced bit stream based at least in part on the generated rule condition check result and (2) storing that enhanced bit stream portion in the selected location.

20. The method of claim 1 wherein the processing step comprises delivering the received bit stream to a plurality parallel paths, and wherein the processing step comprises independently performing the processing step within a plurality of the paths.

21. The method of claim 20 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein the processing step further comprises:

within a first of the parallel paths, (1) filtering the bit stream to pass only data corresponding to at least one pre-selected data field, and (2) processing that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition; and

within a second of the parallel paths, (1) filtering the bit stream to pass only data corresponding to at least one pre-selected data field that is different than the at least one pre-selected data field of the first path, and (2) processing that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition.

22. The method of claim 21 further comprising merging data outputs for the plurality of parallel paths using the coprocessor.

23. The method of claim 22 further comprising delivering the received bit stream to the merging step via a bypass path, and wherein the merging step further comprises inserting the rule condition check result generated within the plurality of paths into the received bit stream at a plurality of locations.

26. The method of claim 1 wherein the processing step comprises:

computing a derived value based at least in part upon the bit stream portion;

determining whether a rule condition is satisfied based at least in part upon the computed derived value; and

in response to a determination that that rule condition is satisfied, generating a rule condition check result indicative of that rule condition'"'"'s satisfaction.

27. The method of claim 1 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein the processing step comprises:

filtering the bit stream to pass only data corresponding to at least one pre-selected data field;

performing a range check on the each field of the passed data to determine whether the passed data has a data value within a range of acceptable values corresponding to at least one range-based rule condition; and

in response to a determination that that at least one range-based rule condition is satisfied, generating a rule condition check result indicative of that range-based rule condition'"'"'s satisfaction.

28. The method of claim 1 wherein each rule condition has a corresponding action, the method further comprising:

performing the action corresponding to a rule condition that is identified by the generated rule condition check result.

29. The method of claim 1 wherein the processing step comprises performing an approximate join operation with the coprocessor on data within the received bit stream.

30. The method of claim 1 wherein the processing step comprises performing a join operation with the coprocessor between data within the received bit stream and data stored in a database.

24. The method of 1 wherein the processing step comprises:

computing an aggregate value based at least in part upon the bit stream portion;

determining whether a rule condition is satisfied based at least in part upon the computed aggregate value; and

in response to a determination that that rule condition is satisfied, generating a rule condition check result indicative of that rule condition'"'"'s satisfaction.

25. The method of claim 24 further comprising:

storing the aggregate value in a memory; and

retrieving the aggregate value from the memory as additional bit stream portions are processed by the processing step.

31. A method for operating a rule-based system, the method comprising:

receiving a data stream within the rule-based system, the rule-based system being configured with a plurality of business rules, each business rule having at least one pre-defined rule condition; and

hardware-accelerating a determination as to whether any data within the received data stream satisfies any of a plurality of pre-defined rule conditions for the business rules.

32. The method of claim 31 further comprising:

generating a rule condition check result if a determination is made that one of the pre-defined rule conditions is satisfied; and

enhancing the data stream with the generated rule condition check result.

33. The method of claim 32 wherein the hardware-accelerating step comprises hardware-accelerating a matching operation to determine if any data within the data stream matches any of a plurality of keys, the keys corresponding to at least a plurality of the rule conditions.

34. The method of claim 33 wherein the matching operation comprises at least one selected from the group consisting of an exact word matching operation, an approximate word matching operation, and a regular expression pattern matching operation.

35. The method of claim 32 wherein the hardware-accelerating step comprises hardware-accelerating a range check operation to determine if any data within the data stream falls within a data range, wherein the data range corresponds to at least one of the rule conditions.

36. The method of claim 32 wherein the hardware-accelerating step comprises (1) hardware-accelerating a computation of an aggregate value based on data within the data stream, and (2) hardware-accelerating an operation to determine if the aggregate value satisfies at least one of the rule conditions.

37. The method of claim 32 wherein the hardware-accelerating step comprises (1) hardware-accelerating a computation of a derived value based on data within the data stream, and (2) hardware-accelerating an operation to determine if the derived value satisfies at least one of the rule conditions.

38. The method of claim 31 further comprising:

processing the data stream within a plurality of parallelized processing paths within the business rules engine; and

performing the hardware-accelerating step within at least a plurality of the parallelized processing paths.

39. The method of claim 38 further comprising:

within a plurality of the processing paths, performing a hardware-accelerated filtering operation specific to a particular processing path to limit which portions of data within the data stream are processed with the hardware-accelerating step for that particular processing path.

40. The method of claim 31 wherein the rule-based system comprises a Rete network.

41. The method of claim 40 wherein the Rete network comprises a plurality of alpha nodes, the method further comprising performing the hardware-accelerating step with at least one of the alpha nodes.

42. The method of claim 41 wherein the hardware-accelerating step comprises hardware-accelerating a matching operation to determine if any data within the data stream matches any of a plurality of keys, the keys corresponding to at least a plurality of the rule conditions.

43. The method of claim 40 wherein the Rete network comprises a plurality of beta nodes, the method further comprising performing the hardware-accelerating step with at least one of the beta nodes.

44. The method of claim 31 wherein the rule-based system comprises a business rules engine.

45. The method of claim 31 wherein the rule-based system comprises an event stream processor.

46. The method of claim 45 wherein the event stream processor comprises a complex event stream processor.

47. A method for processing a bit stream, the method comprising:

receiving a bit stream at a reconfigurable logic device; and

processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied, wherein the processing is performed by the reconfigurable logic device.

48. The method of claim 47 further comprising:

enhancing the bit stream with at least one bit corresponding to the rule condition check result.

49. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied.

50. The system of claim 49 wherein the coprocessor is further configured to enhance the bit stream with at least one bit corresponding to the rule condition checking result.

51. The system of claim 50 wherein the coprocessor comprises a reconfigurable logic device.

52. The system of claim 51 wherein the reconfigurable logic device has firmware deployed thereon, and wherein the firmware is configured to process at least a portion of the bit stream against the at least one rule condition to thereby generate the rule condition check result.

53. The system of claim 52 wherein the firmware is further configured to enhance the bit stream with at least one bit corresponding to the rule condition check result.

54. The system of claim 50 wherein the coprocessor is further configured to (1) perform a rule condition check operation on the bit stream portion that compares the bit stream portion with a plurality of rule conditions, and (2) in response to finding a match between the bit stream portion and at least one of the rule conditions, generate a rule condition check result that is indicative of a satisfaction of the at least one rule condition.

55. The system of claim 54 wherein the rule condition check operation comprises a matching operation.

56. The system of claim 55 wherein the matching operation comprises an exact word matching operation.

57. The system of claim 55 wherein the matching operation comprises an approximate word matching operation.

58. The system of claim 55 wherein the matching operation comprises a regular expression pattern matching operation.

59. The system of claim 55 wherein the coprocessor is further configured to filter the accepted bit stream to thereby provide a reduced bit stream for use by the matching operation.

60. The system of claim 59 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein coprocessor is further configured to filter the accepted bit stream by passing only data corresponding to at least one pre-selected data field for use by the matching operation.

61. The system of claim 55 wherein the rule condition check operation comprises a range check operation.

62. The system of claim 55 wherein the rule condition check operation comprises a threshold check operation.

63. The system of claim 49 wherein the bit stream comprises a plurality of records, and wherein the coprocessor is further configured to enhance the bit stream by generating a new record for insertion in the bit stream, the new record being indicative of the generated rule condition check result.

64. The system of claim 49 wherein the bit stream comprises a plurality of records, and wherein the coprocessor is further configured to enhance the bit stream by appending a bit string indicative of the generated rule condition check result to the record for which the rule condition check result was generated.

65. The system of claim 49 wherein the coprocessor is further configured to pass the enhanced bit stream to the processor for post-processing that is based at least in part on the generated rule condition check result.

66. The system of claim 65 wherein the processor is configured to perform the post-processing, wherein the post-processing comprises a routing operation to route at least a portion of the enhanced bit stream to a particular destination within a network based at least in part on the generated rule condition check result.

67. The system of claim 65 wherein the processor is configured to perform the post-processing, wherein the post-processing comprises (1) an operation to select a location within a network for storing at least a portion of the enhanced bit stream based at least in part on the generated rule condition check result and (2) an operation to store that enhanced bit stream portion in the selected location.

68. The system of claim 49 wherein the coprocessor is further configured to process bits within the accepted bit stream within a plurality parallel paths, at least a plurality of the paths being configured to independently process at least a portion of the bit stream against a plurality of rule conditions.

69. The system of claim 68 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein the coprocessor is further configured to:

within a first of the parallel paths, (1) filter the bit stream to pass only data corresponding to at least one pre-selected data field, and (2) process that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition; and

within a second of the parallel paths, (1) filter the bit stream to pass only data corresponding to at least one pre-selected data field that is different than the at least one pre-selected data field of the first path, and (2) process that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition.

70. The system of claim 69 wherein the coprocessor is further configured to perform a merge operation to merge data outputs for the plurality of parallel paths.

71. The system of claim 70 wherein one of the parallel paths comprises a bypass path over which the accepted bit stream is delivered to the merge operation, and wherein the merge operation is configured to insert data corresponding to the rule condition check results generated within the plurality of paths into the received bit stream at a plurality of locations.

74. The system of claim 49 wherein the coprocessor is further configured to:

compute a derived value based at least in part upon the bit stream portion;

determine whether a rule condition is satisfied based at least in part upon the computed derived value; and

in response to a determination that that rule condition is satisfied, generate a rule condition check result indicative of that rule condition'"'"'s satisfaction.

75. The system of claim 49 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein the coprocessor is further configured to:

filter the bit stream to pass only data corresponding to at least one pre-selected data field;

perform a range check on the each field of the passed data to determine whether the passed data has a data value within a range of acceptable values corresponding to at least one range-based rule condition; and

in response to a determination that that at least one range-based rule condition is satisfied, generate a rule condition check result indicative of that range-based rule condition'"'"'s satisfaction.

76. The system of claim 49 wherein each rule condition has a corresponding action, and wherein at least one of the group consisting of the processor and the coprocessor is configured to perform the action corresponding to a rule condition that is identified by the generated rule condition check result.

77. The system of claim 49 wherein the coprocessor is further configured to perform an approximate join operation on data within the accepted bit stream.

78. The system of claim 49 wherein the coprocessor is in communication with a database, wherein the coprocessor is further configured to perform a join operation between data within the accepted bit stream and data stored in the database.

72. The system of 49 wherein the coprocessor is further configured to:

compute an aggregate value based at least in part upon the bit stream portion;

determine whether a rule condition is satisfied based at least in part upon the computed aggregate value; and

in response to a determination that that rule condition is satisfied, generate a rule condition check result indicative of that rule condition'"'"'s satisfaction.

73. The system of claim 72 wherein the coprocessor is further configured to:

store the aggregate value in memory; and

retrieve the aggregate value from memory as additional bit stream portions are processed by the coprocessor.

79. A system comprising:

a rule-based processing system, the rule-based processing system being configured to accept an incoming data stream, the rule-based processing system also being configured with a plurality of business rules, each business rule having at least one pre-defined rule condition; and

wherein the rule-based processing system comprises a coprocessor that is configured to determine whether any data within the accepted data stream satisfies any of a plurality of pre-defined rule conditions for the business rules.

80. The system of claim 79 wherein the coprocessor is further configured to:

generate a rule condition check result if a determination is made that one of the pre-defined rule conditions is satisfied; and

enhance the data stream with the generated rule condition check result.

81. The system of claim 80 wherein the coprocessor is further configured to perform a matching operation to determine if any data within the data stream matches any of a plurality of keys, the keys corresponding to at least a plurality of the rule conditions.

82. The system of claim 81 wherein the matching operation comprises at least one selected from the group consisting of an exact word matching operation, an approximate word matching operation, and a regular expression pattern matching operation.

83. The system of claim 80 wherein the coprocessor is further configured to perform a range check operation to determine if any data within the data stream falls within a data range, wherein the data range corresponds to at least one of the rule conditions.

84. The system of claim 80 wherein the coprocessor is further configured to:

compute an aggregate value based on data within the data stream; and

determine if the aggregate value satisfies at least one of the rule conditions.

85. The system of claim 80 wherein the coprocessor is further configured to:

compute a derived value based on data within the data stream;

determine if the derived value satisfies at least one of the rule conditions.

86. The system of claim 79 wherein the coprocessor is further configured to

process the accepted data stream within a plurality of parallelized processing paths;

and

within each of a plurality of the processing paths, determine whether any data within the accepted data stream satisfies any of a plurality of pre-defined rule conditions for the business rules.

87. The system of claim 86 wherein the coprocessor is further configured to, within a plurality of the processing paths, perform a filtering operation specific to a particular processing path to limit which portions of data within the data stream are processed downstream within that path.

88. The system of claim 79 wherein the rule-based processing system comprises a Rete network.

89. The system of claim 88 wherein the Rete network comprises a plurality of alpha nodes, and wherein at least one of the alpha nodes is implemented at least in part with the coprocessor.

90. The system of claim 89 wherein the coprocessor is further configured to perform a matching operation for the at least one alpha node to thereby determine if any data within the data stream matches any of a plurality of keys, the keys corresponding to at least a plurality of the rule conditions.

91. The system of claim 88 wherein the Rete network comprises a plurality of beta nodes, and wherein at least one of the beta nodes is implemented at least in part with the coprocessor.

92. The system of claim 79 wherein the rule-based processing system comprises a business rules engine.

93. The system of claim 79 wherein the rule-based processing system comprises an event stream processor.

94. The system of claim 93 wherein the event stream processor comprises a complex event stream processor.

95. A system for processing a bit stream against a plurality of rule conditions, the method comprising:

a reconfigurable logic device configured to (1) accept a bit stream, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied.

96. The system of claim 95 wherein the reconfigurable logic device is further configured to enhance the bit stream with a plurality of bits corresponding to the rule condition check result.

97. A method of processing a data stream corresponding to a plurality of transactions, the method comprising:

processing the data stream with a plurality of hardware-accelerated rule condition check operations, the rule condition check operations corresponding to a plurality of rule conditions and being configured to determine whether data within the data stream satisfies any of the rule conditions; and

generating a plurality of rule condition check results for the transactions based on the processing step.

98. The method of claim 97 wherein the transactions comprise a plurality of credit card transactions.

99. The method of claim 98 wherein at least one of the hardware-accelerated rule condition check operations comprises a hardware-accelerated range check operation.

100. The method of claim 98 wherein at least one of the hardware-accelerated rule condition check operations comprises a hardware-accelerated matching operation.

101. The method of claim 98 wherein the processing step further comprises performing a hardware-accelerated derived value computation operation to compute a derived value for at least one credit card transaction, and wherein the hardware-accelerated rule condition check operation is based on the computed derived value.

102. The method of claim 98 wherein the processing step further comprises performing a hardware-accelerated aggregate value computation operation to compute an aggregate value for at least one credit card transaction, and wherein the hardware-accelerated rule condition check operation is based on the computed aggregate value.

103. The method of claim 98 further comprising performing a hardware-accelerated filtering operation on the data stream upstream from the hardware-accelerated rule condition check operation.

104. A method of integrating a data stream within an enterprise computing system, the data stream comprising a plurality of records, each record having at least one data field, each data field having a data value, the method comprising:

processing the data stream with a plurality of hardware-accelerated data quality check operations, the data quality check operations corresponding to a plurality of rule conditions for the data fields and being configured to determine whether the data values within the data fields of the data stream satisfy any of the rule conditions; and

generating a plurality of rule condition check results for the records based on the processing step.

105. The method of claim 104 further comprising:

receiving the data stream within the enterprise computing system, and

performing the processing step and the generating step before storing the records in a database within the enterprise computing system.

106. The method of claim 105 wherein at least one of the hardware-accelerated rule condition check operations comprises a hardware-accelerated range check operation.

107. The method of claim 105 wherein at least one of the hardware-accelerated rule condition check operations comprises a hardware-accelerated matching operation.

108. The method of claim 105 wherein the processing step further comprises performing a hardware-accelerated derived value computation operation to compute a derived value for at least one record, and wherein the hardware-accelerated rule condition check operation is based on the computed derived value.

109. The method of claim 105 wherein the processing step further comprises performing a hardware-accelerated aggregate value computation operation to compute an aggregate value for at least one record, and wherein the hardware-accelerated rule condition check operation is based on the computed aggregate value.

110. The method of claim 105 further comprising performing a hardware-accelerated filtering operation on the data stream upstream from the hardware-accelerated rule condition check operation.

111. The method of claim 104 wherein the data stream comprises a plurality of XML data records.

112. The method of claim 104 wherein the data stream comprises a plurality of StreamSQL data records.