[
https://issues.apache.org/jira/browse/CASSANDRA-8413?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14362378#comment-14362378
]
Benedict commented on CASSANDRA-8413:
-------------------------------------
This was filed prior to 2.1 being released. I agree that it's probably better
to target 3.0 now. I've pushed a minor update
[here|https://github.com/belliottsmith/cassandra/tree/8413-bffp] so that the
modelling of false positives can account both for random distribution over the
fixed bits and model flipping the inputs to the bloom filter. This latter
should logically be sufficient, and pans out to be so in limited testing. We
could also multiply by a fixed constant (say a large prime) as further
protection, but this isn't essential.
> Bloom filter false positive ratio is not honoured
> -------------------------------------------------
>
> Key: CASSANDRA-8413
> URL: https://issues.apache.org/jira/browse/CASSANDRA-8413
> Project: Cassandra
> Issue Type: Bug
> Components: Core
> Reporter: Benedict
> Assignee: Robert Stupp
> Fix For: 2.1.4
>
> Attachments: 8413.hack-3.0.txt, 8413.hack.txt
>
>
> Whilst thinking about CASSANDRA-7438 and hash bits, I realised we have a
> problem with sabotaging our bloom filters when using the murmur3 partitioner.
> I have performed a very quick test to confirm this risk is real.
> Since a typical cluster uses the same murmur3 hash for partitioning as we do
> for bloom filter lookups, and we own a contiguous range, we can guarantee
> that the top X bits collide for all keys on the node. This translates into
> poor bloom filter distribution. I quickly hacked LongBloomFilterTest to
> simulate the problem, and the result in these tests is _up to_ a doubling of
> the actual false positive ratio. The actual change will depend on the key
> distribution, the number of keys, the false positive ratio, the number of
> nodes, the token distribution, etc. But seems to be a real problem for
> non-vnode clusters of at least ~128 nodes in size.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
