MANAGING CONCURRENT TRANSACTIONS USING BLOOM FILTERS

• US 20090183159A1
• Filed: 01/11/2008
• Published: 07/16/2009
• Est. Priority Date: 01/11/2008
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Michael, Maged M., von Praun, Christoph, Spear, Michael F.
• Application Number:
  US11/973,000
• Publication Number:
  US 20090183159A1
• Time in Patent Office: Days
• US Class Current: 718/101
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A computer-implemented method for managing concurrent transactions includes recording locations written by a first transaction in a first Bloom filter, recording locations to be read by a second transaction in a second Bloom filter, and performing one of a cancellation or a commission of the second transaction based on an intersection of the first Bloom filter and the second Bloom filter.

Claims

1. A computer-implemented method for managing concurrent transactions, the method comprising:

recording locations written by a first transaction in a first Bloom filter;

recording locations to be read by a second transaction in a second Bloom filter; and

performing one of a cancellation or a commission of the second transaction based on an intersection of the first Bloom filter and the second Bloom filter.

2. The computer-implemented method of claim 1, wherein the performing comprises:

canceling the second transaction when at least one bit of the intersection is set; and

committing the second transaction when no bits of the intersection are set.

3. The computer-implemented method of claim 1, wherein the determination of the intersection takes place after the first transaction has committed.

4. The computer-implemented method of claim 3, wherein the determination of the intersection takes place before the first transaction has written values to all of its locations in shared memory.

5. The computer-implemented method of claim 1, wherein each Bloom filter has an equal number of bits.

6. The computer-implemented method of claim 1, wherein each Bloom filter has the same K hash functions, K being a natural number.

7. A computer-implemented method for managing concurrent transactions, the method comprising:

maintaining a list for a plurality of committed transactions, each entry in the list comprising a first write Bloom filter for storing locations to be written by a corresponding committed transaction;

maintaining metadata for a plurality of pending transactions, the metadata comprising a first read Bloom filter for storing locations to read by a pending transaction and a second write Bloom filter for storing locations to be written by the pending transaction; and

canceling the pending transaction when at least one bit of an intersection of a first write Bloom filter and the first read Bloom filter is set.

8. The computer-implemented method of claim 7, further comprising committing the pending transaction when no bits of the intersection are set.

9. The computer-implemented method of claim 8, further comprising adding an entry to the list comprising the second write Bloom filter when the pending transaction is committed.

10. The computer-implemented method of claim 8, wherein each entry in the list further comprises a status field that indicates whether the committed pending transaction has finished writing its locations to shared memory.

11. The computer-implemented method of claim 10, wherein the committed pending transaction is blocked from updating its status field until all other transactions in the list have written their locations to memory.

12. The computer-implemented method of claim 7, wherein each Bloom filter has a same number of bits and a single hash function.

13. A computer-implemented method for managing concurrent transactions, the method comprising:

recording locations written by a first transaction in a first Bloom filter of N bits, N being a natural number;

recording locations to be read by a second transaction in a second Bloom filter of M bits, M being a natural number; and

determining whether N is different from M after the first transaction has logically committed and when N is different from M,

restarting the second transaction;

recording locations read by the restarted second transaction in a third Bloom filter of N bits; and

performing one of a cancellation or a commission of the second transaction based on an intersection of the first Bloom filter and the third Bloom filter.

14. The computer-implemented method of claim 13 wherein the performing comprises:

canceling the second transaction when at least one bit of the intersection is set; and

committing the second transaction when no bits of the intersection are set.

15. The computer-implemented method of claim 13, wherein M is not different from N, the method further comprises performing one of a cancellation or a commission of the second transaction based on an intersection of the first Bloom filter and the second Bloom filter.

16. The computer-implemented method of claim 13, wherein each Bloom filter has the same K hash functions, K being a natural number.

17. A computer-implemented method for managing concurrent transactions, the method comprising:

maintaining a plurality of lists of committed transactions, each list comprising at least one Bloom filter, each list representing a different priority level, each Bloom filter in a respective list representing locations written by at least one committed transaction;

generating a Bloom filter representing locations read by a pending transaction;

increasing a priority level of the pending transaction when the pending transaction has aborted based on an intersection of the Bloom filter of the pending transaction and a Bloom filter of the plurality of lists; and

restarting the pending transaction when transactions of the lists having a priority level higher than the increased priority level have completed.

18. The computer-implement method of claim 17, wherein the lists having a priority level lower than the pending transaction are locked so that new entries cannot be added.

19. The computer-implemented method of claim 17, wherein each Bloom filter has an equal number of bits.

20. The computer-implemented method of claim 17, wherein each Bloom filter has the same K hash functions, K being a natural number.