[TEPHRA-83] Use bloom filters to represent transaction change sets

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: manager
• Assignee: Gary Helmling
• Reporter: Gary Helmling
• Created: 25/Mar/15 01:50
• Updated: 25/Mar/15 19:23

Description

In order to perform conflict detection, we need to retain, in-memory, the change sets for all committed transactions which could conflict with any in-progress transaction. This amounts to an overhead of: change set size per tx X number of in-progress tx.

It would be far better if we could constrain this to a constant memory overhead per transaction, so that we are only bound by the number of in-progress transactions.

One possibility is to use a bloom filter to represent the change set for each retained committed transaction. Clients could send their committing change set as a bloom filter as well. Not only would the memory overhead per transaction be constant, the computation to identify conflicts (intersection between the bloom filters) would be much cheaper as well.