De-duplication in billing system

• US 8,380,736 B2
• Filed: 05/21/2010
• Issued: 02/19/2013
• Est. Priority Date: 05/21/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pearson, Malcolm Erik, Setzer, Matthew Charles
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Mamillapalli, Pavan
• Application Number:
  US12/785,313
• Publication Number:
  US 20110289102A1
• Time in Patent Office: 1,005 Days
• Field of Search: 707/769, 705/34
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06Q 20/14 specially adapted for billing systems
• CPC Class Codes: G06Q 20/401 Transaction verification
• CPC Class Codes: G06Q 20/4016 involving fraud or risk level assessment in transaction processing
• CPC Class Codes: G06Q 30/04 Billing or invoicing

Abstract

Scalable handling of billing events that affect one or more accounts. A computing system partitions received events into a number of channels, perhaps by account identifier. The channels receive the events, and perform de-duplication of the events. This de-duplication may be performed using a Bloom filter that is updated to reflect the receipt of any original event. The Bloom filter may be used to either determine that the event is not a duplicate of another, or to determine that the event cannot be ruled out as being a duplicate of another. In the latter case, further processing may be performed to for definitively determine whether the event is truly a duplication, or in the alternative, the event may be immediately treated as a duplicate.

Claims

1. A computer-implemented method for performing de-duplication of incoming events, the method comprising:

an act of a computing system receiving a plurality of events in the form of event messages, each of at least some of the events affecting one or more of a plurality of accounts;

an act of the computing system partitioning each of the plurality of events into a plurality of channels, each of the plurality of channels receiving a subset of the plurality of events; and

for at least one of the plurality of channels, performing de-duplication for at least some of the events received by the corresponding channel, wherein de-duplication comprises;

an act of comparing an event identifier for a first event against a Bloom filter to determine that the first event cannot be ruled out as being a duplicate of another event previously received by the channel;

identifying a value of the first event; and

an act of taking subsequent action, which is directed at determining whether the first event is a duplicate, based upon both of (1) the determination that the first event cannot be ruled out as being a duplicate, as well as (2) the value of the first event,

wherein the subsequent action comprises a first combination of processes when the value of the first event is less than a predetermined threshold, and

wherein the subsequent action comprises a second combination of processes that is different than the first combination of processes when the value of the first event is greater than a predetermined threshold.

2. The method in accordance with claim 1, wherein the act of taking subsequent action comprises:

an act of treating the first event as a duplicate.

3. The method in accordance with claim 2, wherein the act of treating the first event as a duplicate comprises:

an act of deleting the first event.

4. The method in accordance with claim 2, wherein the act of treating the first event as a duplicate comprises:

an act of logging detection of a duplicate; and

using the logged detection of the duplicate to evaluate a failure associated with the de-duplication.

5. The method in accordance with claim 1, wherein the act of taking subsequent action comprises:

an act of searching identifiers for events previously received by the channel until a duplicate identifier is found corresponding to the identifier of the first event.

6. The method in accordance with claim 5, wherein the act of searching identifiers for events previously received by the channel comprises:

an act of searching a time-ordered identifier index that contains an index of identifiers of previously received events ordered by time.

7. The method in accordance with claim 1, wherein the Bloom filter is deleted after a predetermined time period.

8. The method in accordance with claim 1, wherein de-duplication further comprises:

an act of comparing an event identifier for a second event against the Bloom filter to determine that the second event is not a duplicate of another event received by the corresponding channel;

in response to determining that the second event is not a duplicate of another event, an act of updating the Bloom filter to reflect receipt of the second event, wherein the second event may be received by the channel before or after the first event.

9. The method in accordance with claim 8, wherein the act of updating the Bloom filter to reflect receipt of the second event is performed in a batch as part of an act of updating the Bloom filter to reflect receipt of a plurality of events.

10. The method in accordance with claim 1, wherein the act of performing de-duplication in the corresponding channel comprises:

an act of further partitioning the received events into a plurality of partitions within the corresponding channel, prior to performing the act of de-duplicating the received events.

11. A computer storage device having stored thereon computer-executable instructions that, when executed by one or more processors of a computing system, cause the computing system to perform a method that includes:

an act of a computing system receiving a plurality of events in the form of event messages, each of at least some of the events affecting one or more of a plurality of accounts;

an act of the computing system partitioning each of the plurality of events into a plurality of channels, each of the plurality of channels receiving a subset of the plurality of events; and

for at least one of the plurality of channels, performing de-duplication for at least some of the events received by the corresponding channel, wherein de-duplication comprises;

an act of comparing an event identifier for a first event against a Bloom filter to determine that the first event cannot be ruled out as being a duplicate of another event previously received by the channel;

identifying a value of the first event; and

an act of taking subsequent action, which is directed at determining whether the first event is a duplicate, based upon both of (1) the determination that the first event cannot be ruled out as being a duplicate, as well as (2) the value of the first event,

wherein the subsequent action comprises a first combination of processes when the value of the first event is a first value, and

wherein the subsequent action comprises a second combination of processes that is different than the first combination of processes when the value of the first event is a second value that is different than the first value.

12. The computer storage device in accordance with claim 11, wherein the computer-executable instructions are further structured such that, when executed by the one or more processors, the computing system treats the first event as a duplicate.

13. The computer storage device in accordance with claim 12, wherein the computing system treats the first event as a duplicate by deleting the first event.

14. The computer storage device in accordance with claim 12, wherein the computing system treats the first event as a duplicate by logging detection of a duplicate.

15. The computer storage device in accordance with claim 11, wherein the computing system further searches identifiers for events previously received by the channel until a duplicate identifier is found corresponding to the identifier of the first event.

16. The computer storage device in accordance with claim 15, wherein the computing system searches for identifiers for events previously received by the channel by searching a time-ordered identifier index that contains an index of identifiers of previously received events ordered by time.

17. The computer storage device in accordance with claim 11, wherein the computer-executable instructions are further structured such that, when executed by the one or more processors, the computing system deletes the Bloom filter after a predetermined time period.

18. The computer storage device in accordance with claim 11, wherein de-duplication further comprises:

comparing an event identifier for a second event against the Bloom filter to determine that the second event is not a duplicate of another event received by the corresponding channel;

in response to determining that the second event is not a duplicate of another event, an act of updating the Bloom filter to reflect receipt of the second event, wherein the second event may be received by the channel before or after the first event.

19. The computer storage device in accordance with claim 18, wherein the act of updating the Bloom filter to reflect receipt of the second event is performed in a batch as part of an act of updating the Bloom filter to reflect receipt of a plurality of events.

20. A computer-implemented method for determining when to delete one or more events during de-duplication of incoming events, the method comprising:

an act of a computing system receiving a plurality of events in the form of event messages, each of at least some of the events affecting one or more of a plurality of accounts;

an act of the computing system partitioning each of the plurality of events into a plurality of channels, each of the plurality of channels receiving a subset of the plurality of events; and

for at least one of the plurality of channels, performing de-duplication for at least some of the events received by the corresponding channel, wherein de-duplication comprises;

an act of comparing an event identifier for a first event against the Bloom filter to determine that the first event cannot be ruled out as being a duplicate of another event previously received by the channel;

an act of deleting the first event even though the first event is not determined to be a duplicate, but is only identified as potentially being a duplicate;

an act of comparing an event identifier for a second event against the Bloom filter to determine that the second event is not a duplicate of another event received by the corresponding channel; and

in response to determining that the second event is not a duplicate of another event, an act of updating the Bloom filter to reflect receipt of the second event, wherein the second event may be received by the channel before or after the first event.

21. The method of claim 20, wherein the first event is a unique event that is received by the corresponding channel performing de-duplication, such that the first event is deleted during de-duplication, even though the first event is not a duplicate event.

22. A computing system comprising:

one or more processor; and

one or more storage device having stored computer-executable instructions that, when executed by the one or more processor, cause the computing system to implement a method that includes;

receiving a plurality of events in the form of event messages, each of at least some of the events affecting one or more of a plurality of accounts;

partitioning each of the plurality of events into a plurality of channels, each of the plurality of channels receiving a subset of the plurality of events; and

for at least one of the plurality of channels, performing de-duplication for at least some of the events received by the corresponding channel, wherein de-duplication comprises;

an act of comparing an event identifier for a first event against a Bloom filter to determine that the first event cannot be ruled out as being a duplicate of another event previously received by the channel;

identifying a value of the first event; and

an act of taking subsequent action, which is directed at determining whether the first event is a duplicate, based upon both of (1) the determination that the first event cannot be ruled out as being a duplicate, as well as (2) the value of the first event,

wherein the subsequent action comprises a first combination of processes when the value of the first event is a first value, and

wherein the subsequent action comprises a second combination of processes that is different than the first combination of processes when the value of the first event is a second value.

23. The system of claim 22, wherein the value comprises a financial value.

24. The system of claim 22, wherein the value comprises an impact value on a financial billing that is associated with the incoming events.