HBase
  1. HBase
  2. HBASE-19

CountingBloomFilter can overflow its storage

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.2.0
    • Component/s: None
    • Labels:
      None

      Description

      The org.onelab.filter.CountingBloomFilter implementation does not check the value of a bucket before incrementing/decrementing it. The buckets in a Counting Bloom filter must not be allowed to overflow, and if they reach their maximum value, they must not be allowed to decrement. This is the only way to preserve the assumptions of the filter (without larger buckets). See: http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters

      Currently, if enough values hash to a bucket, the CountingBloomFilter may begin reporting false negatives when it wraps back around to 0.

      1. 19.patch
        7 kB
        Bryan Duxbury
      2. 19-v2.patch
        7 kB
        Bryan Duxbury
      3. counting-overflow.patch
        0.9 kB
        Stu Hood
      4. counting-overflow-fourbit.patch
        7 kB
        Stu Hood
      5. counting-overflow-fourbit.patch
        7 kB
        Stu Hood

        Activity

        Jim Kellerman made changes -
        Status Resolved [ 5 ] Closed [ 6 ]
        stack made changes -
        Resolution Fixed [ 1 ]
        Status Patch Available [ 10002 ] Resolved [ 5 ]
        Bryan Duxbury made changes -
        Attachment 19-v2.patch [ 12374946 ]
        Bryan Duxbury made changes -
        Fix Version/s 0.2.0 [ 12312955 ]
        Bryan Duxbury made changes -
        Attachment 19.patch [ 12374695 ]
        Owen O'Malley made changes -
        Key HADOOP-2654 HBASE-19
        Project Hadoop Core [ 12310240 ] Hadoop HBase [ 12310753 ]
        Component/s contrib/hbase [ 12311752 ]
        Stu Hood made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Stu Hood made changes -
        Attachment counting-overflow-fourbit.patch [ 12373593 ]
        Stu Hood made changes -
        Status Patch Available [ 10002 ] Open [ 1 ]
        Stu Hood made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Stu Hood made changes -
        Attachment counting-overflow-fourbit.patch [ 12373592 ]
        Stu Hood made changes -
        Status Patch Available [ 10002 ] Open [ 1 ]
        Stu Hood made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Stu Hood made changes -
        Field Original Value New Value
        Attachment counting-overflow.patch [ 12373483 ]
        Stu Hood created issue -

          People

          • Assignee:
            Unassigned
            Reporter:
            Stu Hood
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development