[CASSANDRA-8921] Experiment with a probabilistic tree of membership for maxPurgeableTimestamp

• Type: Improvement
• Status: Open
• Priority: Normal
• Resolution: Unresolved
• Component/s: Legacy/Core
• Assignee: Unassigned
• Reporter: Benedict Elliott Smith
• Created: 05/Mar/15 13:54
• Updated: 16/Apr/19 09:31

Description

maxPurgeableTimestamp appears to be a significant cost for some workloads, the majority of which stemming from the cost of membership tests across the overlapping tables. It would be possible to construct a tree of bloom filters from the existing filters, that could yield queries of the set of possible membership of a given key with logarithmic performance, and it appears there is a research paper (that I haven't dived into yet) that outlines something like this http://www.usna.edu/Users/cs/adina/research/Bloofi%20_CloudI2013.pdf