[jira] Updated: (HADOOP-3063) BloomMapFile - fail-fast version of MapFile for sparsely populated key space

["Andrzej Bialecki (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/HADOOP-3063?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Andrzej Bialecki  updated HADOOP-3063:
--------------------------------------

    Attachment: bloommap-v3.patch

This patch uses the latest versions of Bloom filters and Hash implementations from HBase. It successfully passes the 'ant test-patch' command:

     [exec] +1 overall.
     [exec]
     [exec]     +1 @author.  The patch does not contain any @author tags.
     [exec]
     [exec]     +1 tests included.  The patch appears to include 4 new or modified tests.
     [exec]
     [exec]     +1 javadoc.  The javadoc tool did not generate any warning messages.
     [exec]
     [exec]     +1 javac.  The applied patch does not increase the total number of javac compiler warnings.
     [exec]
     [exec]     +1 findbugs.  The patch does not introduce any new Findbugs warnings.
     [exec]
     [exec]     +1 Eclipse classpath. The patch retains Eclipse classpath integrity.


> BloomMapFile - fail-fast version of MapFile for sparsely populated key space
> ----------------------------------------------------------------------------
>
>                 Key: HADOOP-3063
>                 URL: https://issues.apache.org/jira/browse/HADOOP-3063
>             Project: Hadoop Core
>          Issue Type: Improvement
>          Components: io
>    Affects Versions: 0.17.0
>            Reporter: Andrzej Bialecki 
>         Attachments: bloommap-v2.patch, bloommap-v3.patch, bloommap.patch
>
>
> The need for this improvement arose when working with large ancillary MapFile-s (essentially used as external dictionaries). For each invokation of map() / reduce() it was necessary to perform several look-ups in these MapFile-s, and in case of sparsely populated key-space the cost of finding that a key is absent was too high.
> This patch implements a subclass of MapFile that creates a Bloom filter from all keys, so that accurate tests for absence of keys can be performed quickly and with 100% accuracy.
> Writer.append() operations update a DynamicBloomFilter, which is then serialized when the Writer is closed. This filter is loaded in memory when a Reader is created. Reader.get() operation first checks the filter for the key membership, and if the key is absent it immediately returns null without doing any further IO.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.