hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mberto...@apache.org
Subject [27/50] [abbrv] hbase git commit: HBASE-13510 - Purge ByteBloomFilter (Ram)
Date Thu, 21 May 2015 16:43:10 GMT
HBASE-13510 - Purge ByteBloomFilter (Ram)


Project: http://git-wip-us.apache.org/repos/asf/hbase/repo
Commit: http://git-wip-us.apache.org/repos/asf/hbase/commit/5e7e626e
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/5e7e626e
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/5e7e626e

Branch: refs/heads/hbase-12439
Commit: 5e7e626ef54ada9e75b18b31bb49e23b22ae9fe9
Parents: 901714d
Author: ramkrishna <ramkrishna.s.vasudevan@gmail.com>
Authored: Tue May 19 10:22:56 2015 +0530
Committer: ramkrishna <ramkrishna.s.vasudevan@gmail.com>
Committed: Tue May 19 10:22:56 2015 +0530

----------------------------------------------------------------------
 .../hbase/io/hfile/HFilePrettyPrinter.java      |   6 +-
 .../hadoop/hbase/regionserver/StoreFile.java    |  56 +-
 .../apache/hadoop/hbase/util/BloomFilter.java   |  59 +-
 .../hadoop/hbase/util/BloomFilterBase.java      |   7 -
 .../hadoop/hbase/util/BloomFilterChunk.java     | 322 +++++++++
 .../hadoop/hbase/util/BloomFilterFactory.java   |   7 -
 .../hadoop/hbase/util/BloomFilterUtil.java      | 269 ++++++++
 .../hadoop/hbase/util/BloomFilterWriter.java    |   4 -
 .../hadoop/hbase/util/ByteBloomFilter.java      | 654 -------------------
 .../hadoop/hbase/util/CompoundBloomFilter.java  |  32 +-
 .../hbase/util/CompoundBloomFilterBase.java     |  22 -
 .../hbase/util/CompoundBloomFilterWriter.java   |  25 +-
 .../regionserver/TestCompoundBloomFilter.java   |  19 +-
 .../hadoop/hbase/util/TestBloomFilterChunk.java | 185 ++++++
 .../hadoop/hbase/util/TestByteBloomFilter.java  | 169 -----
 15 files changed, 903 insertions(+), 933 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFilePrettyPrinter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFilePrettyPrinter.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFilePrettyPrinter.java
index 7463e83..7cc31d0 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFilePrettyPrinter.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFilePrettyPrinter.java
@@ -59,8 +59,8 @@ import org.apache.hadoop.hbase.io.FSDataInputStreamWrapper;
 import org.apache.hadoop.hbase.io.hfile.HFile.FileInfo;
 import org.apache.hadoop.hbase.regionserver.TimeRangeTracker;
 import org.apache.hadoop.hbase.util.BloomFilter;
+import org.apache.hadoop.hbase.util.BloomFilterUtil;
 import org.apache.hadoop.hbase.util.BloomFilterFactory;
-import org.apache.hadoop.hbase.util.ByteBloomFilter;
 import org.apache.hadoop.hbase.util.Bytes;
 import org.apache.hadoop.hbase.util.FSUtils;
 import org.apache.hadoop.hbase.util.Writables;
@@ -424,7 +424,7 @@ public class HFilePrettyPrinter extends Configured implements Tool {
     System.out.println("Bloom filter:");
     if (bloomFilter != null) {
       System.out.println(FOUR_SPACES + bloomFilter.toString().replaceAll(
-          ByteBloomFilter.STATS_RECORD_SEP, "\n" + FOUR_SPACES));
+          BloomFilterUtil.STATS_RECORD_SEP, "\n" + FOUR_SPACES));
     } else {
       System.out.println(FOUR_SPACES + "Not present");
     }
@@ -438,7 +438,7 @@ public class HFilePrettyPrinter extends Configured implements Tool {
     System.out.println("Delete Family Bloom filter:");
     if (bloomFilter != null) {
       System.out.println(FOUR_SPACES
-          + bloomFilter.toString().replaceAll(ByteBloomFilter.STATS_RECORD_SEP,
+          + bloomFilter.toString().replaceAll(BloomFilterUtil.STATS_RECORD_SEP,
               "\n" + FOUR_SPACES));
     } else {
       System.out.println(FOUR_SPACES + "Not present");

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFile.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFile.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFile.java
index 1992479..eba3689 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFile.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFile.java
@@ -707,7 +707,6 @@ public class StoreFile {
     private final BloomType bloomType;
     private byte[] lastBloomKey;
     private int lastBloomKeyOffset, lastBloomKeyLen;
-    private CellComparator kvComparator;
     private Cell lastCell = null;
     private long earliestPutTs = HConstants.LATEST_TIMESTAMP;
     private Cell lastDeleteFamilyCell = null;
@@ -754,8 +753,6 @@ public class StoreFile {
           .withFileContext(fileContext)
           .create();
 
-      this.kvComparator = comparator;
-
       generalBloomFilterWriter = BloomFilterFactory.createGeneralBloomAtWrite(
           conf, cacheConf, bloomType,
           (int) Math.min(maxKeys, Integer.MAX_VALUE), writer);
@@ -864,7 +861,9 @@ public class StoreFile {
            *  1. Row = Row
            *  2. RowCol = Row + Qualifier
            */
-          byte[] bloomKey;
+          byte[] bloomKey = null;
+          // Used with ROW_COL bloom
+          KeyValue bloomKeyKV = null;
           int bloomKeyOffset, bloomKeyLen;
 
           switch (bloomType) {
@@ -877,11 +876,14 @@ public class StoreFile {
             // merge(row, qualifier)
             // TODO: could save one buffer copy in case of compound Bloom
             // filters when this involves creating a KeyValue
-            bloomKey = generalBloomFilterWriter.createBloomKey(cell.getRowArray(),
-                cell.getRowOffset(), cell.getRowLength(), cell.getQualifierArray(),
-                cell.getQualifierOffset(), cell.getQualifierLength());
-            bloomKeyOffset = 0;
-            bloomKeyLen = bloomKey.length;
+            bloomKeyKV = KeyValueUtil.createFirstOnRow(cell.getRowArray(), cell.getRowOffset(),
+                cell.getRowLength(), 
+                HConstants.EMPTY_BYTE_ARRAY, 0, 0, cell.getQualifierArray(),
+                cell.getQualifierOffset(),
+                cell.getQualifierLength());
+            bloomKey = bloomKeyKV.getBuffer();
+            bloomKeyOffset = bloomKeyKV.getKeyOffset();
+            bloomKeyLen = bloomKeyKV.getKeyLength();
             break;
           default:
             throw new IOException("Invalid Bloom filter type: " + bloomType +
@@ -889,17 +891,17 @@ public class StoreFile {
           }
           generalBloomFilterWriter.add(bloomKey, bloomKeyOffset, bloomKeyLen);
           if (lastBloomKey != null) {
-            boolean res = false;
+            int res = 0;
             // hbase:meta does not have blooms. So we need not have special interpretation
             // of the hbase:meta cells.  We can safely use Bytes.BYTES_RAWCOMPARATOR for ROW Bloom
             if (bloomType == BloomType.ROW) {
               res = Bytes.BYTES_RAWCOMPARATOR.compare(bloomKey, bloomKeyOffset, bloomKeyLen,
-                  lastBloomKey, lastBloomKeyOffset, lastBloomKeyLen) <= 0;
+                  lastBloomKey, lastBloomKeyOffset, lastBloomKeyLen);
             } else {
-              res = (CellComparator.COMPARATOR.compare(lastBloomKeyOnlyKV, bloomKey,
-                                     bloomKeyOffset, bloomKeyLen) >= 0);
+              // TODO : Caching of kv components becomes important in these cases
+              res = CellComparator.COMPARATOR.compare(bloomKeyKV, lastBloomKeyOnlyKV);
             }
-            if (res) {
+            if (res <= 0) {
               throw new IOException("Non-increasing Bloom keys: "
                   + Bytes.toStringBinary(bloomKey, bloomKeyOffset, bloomKeyLen) + " after "
                   + Bytes.toStringBinary(lastBloomKey, lastBloomKeyOffset, lastBloomKeyLen));
@@ -1252,7 +1254,10 @@ public class StoreFile {
         return true;
       }
 
-      byte[] key;
+      // Used in ROW bloom
+      byte[] key = null;
+      // Used in ROW_COL bloom
+      KeyValue kvKey = null;
       switch (bloomFilterType) {
         case ROW:
           if (col != null) {
@@ -1267,8 +1272,9 @@ public class StoreFile {
           break;
 
         case ROWCOL:
-          key = bloomFilter.createBloomKey(row, rowOffset, rowLen, col,
-              colOffset, colLen);
+          kvKey = KeyValueUtil.createFirstOnRow(row, rowOffset, rowLen, 
+              HConstants.EMPTY_BYTE_ARRAY, 0, 0, col, colOffset,
+              colLen);
           break;
 
         default:
@@ -1304,9 +1310,7 @@ public class StoreFile {
             if (bloomFilterType == BloomType.ROW) {
               keyIsAfterLast = (Bytes.BYTES_RAWCOMPARATOR.compare(key, lastBloomKey) > 0);
             } else {
-              // TODO : Convert key to Cell so that we could use compare(Cell, Cell)
-              keyIsAfterLast = (CellComparator.COMPARATOR.compare(lastBloomKeyOnlyKV, key, 0,
-                                   key.length)) < 0;
+              keyIsAfterLast = (CellComparator.COMPARATOR.compare(kvKey, lastBloomKeyOnlyKV)) > 0;
             }
           }
 
@@ -1315,19 +1319,17 @@ public class StoreFile {
             // columns, a file might be skipped if using row+col Bloom filter.
             // In order to ensure this file is included an additional check is
             // required looking only for a row bloom.
-            byte[] rowBloomKey = bloomFilter.createBloomKey(row, rowOffset, rowLen,
-                null, 0, 0);
+            KeyValue rowBloomKey = KeyValueUtil.createFirstOnRow(row, rowOffset, rowLen,
+                HConstants.EMPTY_BYTE_ARRAY, 0, 0, HConstants.EMPTY_BYTE_ARRAY, 0, 0);
             // hbase:meta does not have blooms. So we need not have special interpretation
             // of the hbase:meta cells.  We can safely use Bytes.BYTES_RAWCOMPARATOR for ROW Bloom
             if (keyIsAfterLast
-                && (CellComparator.COMPARATOR.compare(lastBloomKeyOnlyKV, rowBloomKey, 0,
-                    rowBloomKey.length)) < 0) {
+                && (CellComparator.COMPARATOR.compare(rowBloomKey, lastBloomKeyOnlyKV)) > 0) {
               exists = false;
             } else {
               exists =
-                  bloomFilter.contains(key, 0, key.length, bloom) ||
-                  bloomFilter.contains(rowBloomKey, 0, rowBloomKey.length,
-                      bloom);
+                  bloomFilter.contains(kvKey, bloom) ||
+                  bloomFilter.contains(rowBloomKey, bloom);
             }
           } else {
             exists = !keyIsAfterLast

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilter.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilter.java
index b314bf6..f119086 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilter.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilter.java
@@ -20,24 +20,57 @@ package org.apache.hadoop.hbase.util;
 
 import java.nio.ByteBuffer;
 
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.classification.InterfaceAudience;
 
 /**
- * Defines the general behavior of a bloom filter.
  *
+ * Implements a <i>Bloom filter</i>, as defined by Bloom in 1970.
  * <p>
- * The Bloom filter is a data structure that was introduced in 1970 and that
- * has been adopted by the networking research community in the past decade
- * thanks to the bandwidth efficiencies that it offers for the transmission of
- * set membership information between networked hosts. A sender encodes the
+ * The Bloom filter is a data structure that was introduced in 1970 and that has
+ * been adopted by the networking research community in the past decade thanks
+ * to the bandwidth efficiencies that it offers for the transmission of set
+ * membership information between networked hosts. A sender encodes the
  * information into a bit vector, the Bloom filter, that is more compact than a
- * conventional representation. Computation and space costs for construction
- * are linear in the number of elements. The receiver uses the filter to test
+ * conventional representation. Computation and space costs for construction are
+ * linear in the number of elements. The receiver uses the filter to test
  * whether various elements are members of the set. Though the filter will
  * occasionally return a false positive, it will never return a false negative.
  * When creating the filter, the sender can choose its desired point in a
  * trade-off between the false positive rate and the size.
  *
+ * <p>
+ * Originally inspired by <a href="http://www.one-lab.org">European Commission
+ * One-Lab Project 034819</a>.
+ *
+ * Bloom filters are very sensitive to the number of elements inserted into
+ * them. For HBase, the number of entries depends on the size of the data stored
+ * in the column. Currently the default region size is 256MB, so entry count ~=
+ * 256MB / (average value size for column). Despite this rule of thumb, there is
+ * no efficient way to calculate the entry count after compactions. Therefore,
+ * it is often easier to use a dynamic bloom filter that will add extra space
+ * instead of allowing the error rate to grow.
+ *
+ * ( http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/BloomFilterSurvey
+ * .pdf )
+ *
+ * m denotes the number of bits in the Bloom filter (bitSize) n denotes the
+ * number of elements inserted into the Bloom filter (maxKeys) k represents the
+ * number of hash functions used (nbHash) e represents the desired false
+ * positive rate for the bloom (err)
+ *
+ * If we fix the error rate (e) and know the number of entries, then the optimal
+ * bloom size m = -(n * ln(err) / (ln(2)^2) ~= n * ln(err) / ln(0.6185)
+ *
+ * The probability of false positives is minimized when k = m/n ln(2).
+ *
+ * @see BloomFilter The general behavior of a filter
+ *
+ * @see <a
+ *      href="http://portal.acm.org/citation.cfm?id=362692&dl=ACM&coll=portal">
+ *      Space/Time Trade-Offs in Hash Coding with Allowable Errors</a>
+ *
  * @see BloomFilterWriter for the ability to add elements to a Bloom filter
  */
 @InterfaceAudience.Private
@@ -45,7 +78,17 @@ public interface BloomFilter extends BloomFilterBase {
 
   /**
    * Check if the specified key is contained in the bloom filter.
-   *
+   * Used in ROW_COL blooms where the blooms are serialized as KeyValues
+   * @param keyCell the key to check for the existence of
+   * @param bloom bloom filter data to search. This can be null if auto-loading
+   *        is supported.
+   * @return true if matched by bloom, false if not
+   */
+  boolean contains(Cell keyCell, ByteBuffer bloom);
+
+  /**
+   * Check if the specified key is contained in the bloom filter.
+   * Used in ROW bloom where the blooms are just plain byte[]
    * @param buf data to check for existence of
    * @param offset offset into the data
    * @param length length of the data

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterBase.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterBase.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterBase.java
index 0396965..43cf75d 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterBase.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterBase.java
@@ -41,11 +41,4 @@ public interface BloomFilterBase {
    * @return Size of the bloom, in bytes
    */
   long getByteSize();
-
-  /**
-   * Create a key for a row-column Bloom filter.
-   */
-  byte[] createBloomKey(byte[] rowBuf, int rowOffset, int rowLen,
-      byte[] qualBuf, int qualOffset, int qualLen);
-
 }

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterChunk.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterChunk.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterChunk.java
new file mode 100644
index 0000000..a80a201
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterChunk.java
@@ -0,0 +1,322 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hbase.util;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+
+import com.google.common.annotations.VisibleForTesting;
+
+/**
+ * The basic building block for the {@link CompoundBloomFilter}
+ */
+@InterfaceAudience.Private
+public class BloomFilterChunk implements BloomFilterBase {
+
+  /** Bytes (B) in the array. This actually has to fit into an int. */
+  protected long byteSize;
+  /** Number of hash functions */
+  protected int hashCount;
+  /** Hash type */
+  protected final int hashType;
+  /** Hash Function */
+  protected final Hash hash;
+  /** Keys currently in the bloom */
+  protected int keyCount;
+  /** Max Keys expected for the bloom */
+  protected int maxKeys;
+  /** Bloom bits */
+  protected ByteBuffer bloom;
+
+  /**
+   * Loads bloom filter meta data from file input.
+   * @param meta stored bloom meta data
+   * @throws IllegalArgumentException meta data is invalid
+   */
+  public BloomFilterChunk(DataInput meta)
+      throws IOException, IllegalArgumentException {
+    this.byteSize = meta.readInt();
+    this.hashCount = meta.readInt();
+    this.hashType = meta.readInt();
+    this.keyCount = meta.readInt();
+    this.maxKeys = this.keyCount;
+
+    this.hash = Hash.getInstance(this.hashType);
+    if (hash == null) {
+      throw new IllegalArgumentException("Invalid hash type: " + hashType);
+    }
+    sanityCheck();
+  }
+
+  /**
+   * Computes the error rate for this Bloom filter, taking into account the
+   * actual number of hash functions and keys inserted. The return value of
+   * this function changes as a Bloom filter is being populated. Used for
+   * reporting the actual error rate of compound Bloom filters when writing
+   * them out.
+   *
+   * @return error rate for this particular Bloom filter
+   */
+  public double actualErrorRate() {
+    return BloomFilterUtil.actualErrorRate(keyCount, byteSize * 8, hashCount);
+  }
+
+  public BloomFilterChunk(int hashType) {
+    this.hashType = hashType;
+    this.hash = Hash.getInstance(hashType);
+  }
+
+  /**
+   * Determines & initializes bloom filter meta data from user config. Call
+   * {@link #allocBloom()} to allocate bloom filter data.
+   *
+   * @param maxKeys Maximum expected number of keys that will be stored in this
+   *          bloom
+   * @param errorRate Desired false positive error rate. Lower rate = more
+   *          storage required
+   * @param hashType Type of hash function to use
+   * @param foldFactor When finished adding entries, you may be able to 'fold'
+   *          this bloom to save space. Tradeoff potentially excess bytes in
+   *          bloom for ability to fold if keyCount is exponentially greater
+   *          than maxKeys.
+   * @throws IllegalArgumentException
+   */
+  public BloomFilterChunk(int maxKeys, double errorRate, int hashType,
+      int foldFactor) throws IllegalArgumentException {
+    this(hashType);
+
+    long bitSize = BloomFilterUtil.computeBitSize(maxKeys, errorRate);
+    hashCount = BloomFilterUtil.optimalFunctionCount(maxKeys, bitSize);
+    this.maxKeys = maxKeys;
+
+    // increase byteSize so folding is possible
+    byteSize = BloomFilterUtil.computeFoldableByteSize(bitSize, foldFactor);
+
+    sanityCheck();
+  }
+
+  /**
+   * Creates another similar Bloom filter. Does not copy the actual bits, and
+   * sets the new filter's key count to zero.
+   *
+   * @return a Bloom filter with the same configuration as this
+   */
+  public BloomFilterChunk createAnother() {
+    BloomFilterChunk bbf = new BloomFilterChunk(hashType);
+    bbf.byteSize = byteSize;
+    bbf.hashCount = hashCount;
+    bbf.maxKeys = maxKeys;
+    return bbf;
+  }
+
+  public void allocBloom() {
+    if (this.bloom != null) {
+      throw new IllegalArgumentException("can only create bloom once.");
+    }
+    this.bloom = ByteBuffer.allocate((int)this.byteSize);
+    assert this.bloom.hasArray();
+  }
+
+  void sanityCheck() throws IllegalArgumentException {
+    if(0 >= this.byteSize || this.byteSize > Integer.MAX_VALUE) {
+      throw new IllegalArgumentException("Invalid byteSize: " + this.byteSize);
+    }
+
+    if(this.hashCount <= 0) {
+      throw new IllegalArgumentException("Hash function count must be > 0");
+    }
+
+    if (this.hash == null) {
+      throw new IllegalArgumentException("hashType must be known");
+    }
+
+    if (this.keyCount < 0) {
+      throw new IllegalArgumentException("must have positive keyCount");
+    }
+  }
+
+  void bloomCheck(ByteBuffer bloom)  throws IllegalArgumentException {
+    if (this.byteSize != bloom.limit()) {
+      throw new IllegalArgumentException(
+          "Configured bloom length should match actual length");
+    }
+  }
+
+  public void add(byte [] buf) {
+    add(buf, 0, buf.length);
+  }
+
+  public void add(byte [] buf, int offset, int len) {
+    /*
+     * For faster hashing, use combinatorial generation
+     * http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
+     */
+    int hash1 = this.hash.hash(buf, offset, len, 0);
+    int hash2 = this.hash.hash(buf, offset, len, hash1);
+
+    for (int i = 0; i < this.hashCount; i++) {
+      long hashLoc = Math.abs((hash1 + i * hash2) % (this.byteSize * 8));
+      set(hashLoc);
+    }
+
+    ++this.keyCount;
+  }
+
+  @VisibleForTesting
+  boolean contains(byte [] buf) {
+    return contains(buf, 0, buf.length, this.bloom);
+  }
+
+  @VisibleForTesting
+  boolean contains(byte [] buf, int offset, int length) {
+    return contains(buf, offset, length, bloom);
+  }
+
+  @VisibleForTesting
+  boolean contains(byte[] buf, ByteBuffer bloom) {
+    return contains(buf, 0, buf.length, bloom);
+  }
+
+  public boolean contains(byte[] buf, int offset, int length, ByteBuffer theBloom) {
+    if (theBloom == null) {
+      theBloom = bloom;
+    }
+
+    if (theBloom.limit() != byteSize) {
+      throw new IllegalArgumentException("Bloom does not match expected size:"
+          + " theBloom.limit()=" + theBloom.limit() + ", byteSize=" + byteSize);
+    }
+
+    return BloomFilterUtil.contains(buf, offset, length, theBloom, 0, (int) byteSize, hash,
+        hashCount);
+  }
+
+  //---------------------------------------------------------------------------
+  /** Private helpers */
+
+  /**
+   * Set the bit at the specified index to 1.
+   *
+   * @param pos index of bit
+   */
+  void set(long pos) {
+    int bytePos = (int)(pos / 8);
+    int bitPos = (int)(pos % 8);
+    byte curByte = bloom.get(bytePos);
+    curByte |= BloomFilterUtil.bitvals[bitPos];
+    bloom.put(bytePos, curByte);
+  }
+
+  /**
+   * Check if bit at specified index is 1.
+   *
+   * @param pos index of bit
+   * @return true if bit at specified index is 1, false if 0.
+   */
+  static boolean get(int pos, ByteBuffer bloomBuf, int bloomOffset) {
+    int bytePos = pos >> 3; //pos / 8
+    int bitPos = pos & 0x7; //pos % 8
+    // TODO access this via Util API which can do Unsafe access if possible(?)
+    byte curByte = bloomBuf.get(bloomOffset + bytePos);
+    curByte &= BloomFilterUtil.bitvals[bitPos];
+    return (curByte != 0);
+  }
+
+  @Override
+  public long getKeyCount() {
+    return keyCount;
+  }
+
+  @Override
+  public long getMaxKeys() {
+    return maxKeys;
+  }
+
+  @Override
+  public long getByteSize() {
+    return byteSize;
+  }
+
+  public int getHashType() {
+    return hashType;
+  }
+
+  public void compactBloom() {
+    // see if the actual size is exponentially smaller than expected.
+    if (this.keyCount > 0 && this.bloom.hasArray()) {
+      int pieces = 1;
+      int newByteSize = (int)this.byteSize;
+      int newMaxKeys = this.maxKeys;
+
+      // while exponentially smaller & folding is lossless
+      while ((newByteSize & 1) == 0 && newMaxKeys > (this.keyCount<<1)) {
+        pieces <<= 1;
+        newByteSize >>= 1;
+        newMaxKeys >>= 1;
+      }
+
+      // if we should fold these into pieces
+      if (pieces > 1) {
+        byte[] array = this.bloom.array();
+        int start = this.bloom.arrayOffset();
+        int end = start + newByteSize;
+        int off = end;
+        for(int p = 1; p < pieces; ++p) {
+          for(int pos = start; pos < end; ++pos) {
+            array[pos] |= array[off++];
+          }
+        }
+        // folding done, only use a subset of this array
+        this.bloom.rewind();
+        this.bloom.limit(newByteSize);
+        this.bloom = this.bloom.slice();
+        this.byteSize = newByteSize;
+        this.maxKeys = newMaxKeys;
+      }
+    }
+  }
+
+  /**
+   * Writes just the bloom filter to the output array
+   * @param out OutputStream to place bloom
+   * @throws IOException Error writing bloom array
+   */
+  public void writeBloom(final DataOutput out)
+      throws IOException {
+    if (!this.bloom.hasArray()) {
+      throw new IOException("Only writes ByteBuffer with underlying array.");
+    }
+    out.write(this.bloom.array(), this.bloom.arrayOffset(), this.bloom.limit());
+  }
+
+  public int getHashCount() {
+    return hashCount;
+  }
+
+  @Override
+  public String toString() {
+    return BloomFilterUtil.toString(this);
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java
index 1a63f6b..aecbdf8 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java
@@ -99,13 +99,6 @@ public final class BloomFilterFactory {
       throws IllegalArgumentException, IOException {
     int version = meta.readInt();
     switch (version) {
-      case ByteBloomFilter.VERSION:
-        // This is only possible in a version 1 HFile. We are ignoring the
-        // passed comparator because raw byte comparators are always used
-        // in version 1 Bloom filters.
-        // TODO:Remove this code - use only CompoundBloomFilter
-        return new ByteBloomFilter(meta);
-
       case CompoundBloomFilterBase.VERSION:
         return new CompoundBloomFilter(meta, reader);
 

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterUtil.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterUtil.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterUtil.java
new file mode 100644
index 0000000..29b08d2
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterUtil.java
@@ -0,0 +1,269 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.util;
+
+import java.nio.ByteBuffer;
+import java.text.NumberFormat;
+import java.util.Random;
+
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+
+/**
+ * Utility methods related to BloomFilters 
+ */
+@InterfaceAudience.Private
+public class BloomFilterUtil {
+
+  /** Record separator for the Bloom filter statistics human-readable string */
+  public static final String STATS_RECORD_SEP = "; ";
+  /**
+   * Used in computing the optimal Bloom filter size. This approximately equals
+   * 0.480453.
+   */
+  public static final double LOG2_SQUARED = Math.log(2) * Math.log(2);
+  
+  /**
+   * A random number generator to use for "fake lookups" when testing to
+   * estimate the ideal false positive rate.
+   */
+  private static Random randomGeneratorForTest;
+  
+  /** Bit-value lookup array to prevent doing the same work over and over */
+  public static final byte [] bitvals = {
+    (byte) 0x01,
+    (byte) 0x02,
+    (byte) 0x04,
+    (byte) 0x08,
+    (byte) 0x10,
+    (byte) 0x20,
+    (byte) 0x40,
+    (byte) 0x80
+  };
+  /**
+   * @param maxKeys
+   * @param errorRate
+   * @return the number of bits for a Bloom filter than can hold the given
+   *         number of keys and provide the given error rate, assuming that the
+   *         optimal number of hash functions is used and it does not have to
+   *         be an integer.
+   */
+  public static long computeBitSize(long maxKeys, double errorRate) {
+    return (long) Math.ceil(maxKeys * (-Math.log(errorRate) / LOG2_SQUARED));
+  }
+
+  public static void setFakeLookupMode(boolean enabled) {
+    if (enabled) {
+      randomGeneratorForTest = new Random(283742987L);
+    } else {
+      randomGeneratorForTest = null;
+    }
+  }
+
+  /**
+   * The maximum number of keys we can put into a Bloom filter of a certain
+   * size to maintain the given error rate, assuming the number of hash
+   * functions is chosen optimally and does not even have to be an integer
+   * (hence the "ideal" in the function name).
+   *
+   * @param bitSize
+   * @param errorRate
+   * @return maximum number of keys that can be inserted into the Bloom filter
+   * @see #computeMaxKeys(long, double, int) for a more precise estimate
+   */
+  public static long idealMaxKeys(long bitSize, double errorRate) {
+    // The reason we need to use floor here is that otherwise we might put
+    // more keys in a Bloom filter than is allowed by the target error rate.
+    return (long) (bitSize * (LOG2_SQUARED / -Math.log(errorRate)));
+  }
+
+  /**
+   * The maximum number of keys we can put into a Bloom filter of a certain
+   * size to get the given error rate, with the given number of hash functions.
+   *
+   * @param bitSize
+   * @param errorRate
+   * @param hashCount
+   * @return the maximum number of keys that can be inserted in a Bloom filter
+   *         to maintain the target error rate, if the number of hash functions
+   *         is provided.
+   */
+  public static long computeMaxKeys(long bitSize, double errorRate,
+      int hashCount) {
+    return (long) (-bitSize * 1.0 / hashCount *
+        Math.log(1 - Math.exp(Math.log(errorRate) / hashCount)));
+  }
+
+  /**
+   * Computes the actual error rate for the given number of elements, number
+   * of bits, and number of hash functions. Taken directly from the
+   * <a href=
+   * "http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives"
+   * > Wikipedia Bloom filter article</a>.
+   *
+   * @param maxKeys
+   * @param bitSize
+   * @param functionCount
+   * @return the actual error rate
+   */
+  public static double actualErrorRate(long maxKeys, long bitSize,
+      int functionCount) {
+    return Math.exp(Math.log(1 - Math.exp(-functionCount * maxKeys * 1.0
+        / bitSize)) * functionCount);
+  }
+
+  /**
+   * Increases the given byte size of a Bloom filter until it can be folded by
+   * the given factor.
+   *
+   * @param bitSize
+   * @param foldFactor
+   * @return Foldable byte size
+   */
+  public static int computeFoldableByteSize(long bitSize, int foldFactor) {
+    long byteSizeLong = (bitSize + 7) / 8;
+    int mask = (1 << foldFactor) - 1;
+    if ((mask & byteSizeLong) != 0) {
+      byteSizeLong >>= foldFactor;
+      ++byteSizeLong;
+      byteSizeLong <<= foldFactor;
+    }
+    if (byteSizeLong > Integer.MAX_VALUE) {
+      throw new IllegalArgumentException("byteSize=" + byteSizeLong + " too "
+          + "large for bitSize=" + bitSize + ", foldFactor=" + foldFactor);
+    }
+    return (int) byteSizeLong;
+  }
+
+  public static int optimalFunctionCount(int maxKeys, long bitSize) {
+    long i = bitSize / maxKeys;
+    double result = Math.ceil(Math.log(2) * i);
+    if (result > Integer.MAX_VALUE){
+      throw new IllegalArgumentException("result too large for integer value.");
+    }
+    return (int)result;
+  }
+  
+  /**
+   * Creates a Bloom filter chunk of the given size.
+   *
+   * @param byteSizeHint the desired number of bytes for the Bloom filter bit
+   *          array. Will be increased so that folding is possible.
+   * @param errorRate target false positive rate of the Bloom filter
+   * @param hashType Bloom filter hash function type
+   * @param foldFactor
+   * @return the new Bloom filter of the desired size
+   */
+  public static BloomFilterChunk createBySize(int byteSizeHint,
+      double errorRate, int hashType, int foldFactor) {
+    BloomFilterChunk bbf = new BloomFilterChunk(hashType);
+
+    bbf.byteSize = computeFoldableByteSize(byteSizeHint * 8L, foldFactor);
+    long bitSize = bbf.byteSize * 8;
+    bbf.maxKeys = (int) idealMaxKeys(bitSize, errorRate);
+    bbf.hashCount = optimalFunctionCount(bbf.maxKeys, bitSize);
+
+    // Adjust max keys to bring error rate closer to what was requested,
+    // because byteSize was adjusted to allow for folding, and hashCount was
+    // rounded.
+    bbf.maxKeys = (int) computeMaxKeys(bitSize, errorRate, bbf.hashCount);
+
+    return bbf;
+  }
+
+  /** Should only be used in tests */
+  public static boolean contains(byte[] buf, int offset, int length, ByteBuffer bloom) {
+    return contains(buf, offset, length, bloom);
+  }
+
+  /** Should only be used in tests */
+  boolean contains(byte[] buf, ByteBuffer bloom) {
+    return contains(buf, 0, buf.length, bloom);
+  }
+
+  public static boolean contains(byte[] buf, int offset, int length,
+      ByteBuffer bloomBuf, int bloomOffset, int bloomSize, Hash hash,
+      int hashCount) {
+
+    int hash1 = hash.hash(buf, offset, length, 0);
+    int hash2 = hash.hash(buf, offset, length, hash1);
+    int bloomBitSize = bloomSize << 3;
+    
+    if (randomGeneratorForTest == null) {
+      // Production mode.
+      int compositeHash = hash1;
+      for (int i = 0; i < hashCount; i++) {
+        int hashLoc = Math.abs(compositeHash % bloomBitSize);
+        compositeHash += hash2;
+        if (!get(hashLoc, bloomBuf, bloomOffset)) {
+          return false;
+        }
+      }
+    } else {
+      // Test mode with "fake lookups" to estimate "ideal false positive rate".
+      for (int i = 0; i < hashCount; i++) {
+        int hashLoc = randomGeneratorForTest.nextInt(bloomBitSize);
+        if (!get(hashLoc, bloomBuf, bloomOffset)){
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+  
+  /**
+   * Check if bit at specified index is 1.
+   *
+   * @param pos index of bit
+   * @return true if bit at specified index is 1, false if 0.
+   */
+  public static boolean get(int pos, ByteBuffer bloomBuf, int bloomOffset) {
+    int bytePos = pos >> 3; //pos / 8
+    int bitPos = pos & 0x7; //pos % 8
+    // TODO access this via Util API which can do Unsafe access if possible(?)
+    byte curByte = bloomBuf.get(bloomOffset + bytePos);
+    curByte &= bitvals[bitPos];
+    return (curByte != 0);
+  }
+  
+  /**
+   * A human-readable string with statistics for the given Bloom filter.
+   *
+   * @param bloomFilter the Bloom filter to output statistics for;
+   * @return a string consisting of "&lt;key&gt;: &lt;value&gt;" parts
+   *         separated by {@link #STATS_RECORD_SEP}.
+   */
+  public static String formatStats(BloomFilterBase bloomFilter) {
+    StringBuilder sb = new StringBuilder();
+    long k = bloomFilter.getKeyCount();
+    long m = bloomFilter.getMaxKeys();
+
+    sb.append("BloomSize: " + bloomFilter.getByteSize() + STATS_RECORD_SEP);
+    sb.append("No of Keys in bloom: " + k + STATS_RECORD_SEP);
+    sb.append("Max Keys for bloom: " + m);
+    if (m > 0) {
+      sb.append(STATS_RECORD_SEP + "Percentage filled: "
+          + NumberFormat.getPercentInstance().format(k * 1.0 / m));
+    }
+    return sb.toString();
+  }
+
+  public static String toString(BloomFilterChunk bloomFilter) {
+    return formatStats(bloomFilter) + STATS_RECORD_SEP + "Actual error rate: "
+        + String.format("%.8f", bloomFilter.actualErrorRate());
+  }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterWriter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterWriter.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterWriter.java
index aa7f503..2aba737 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterWriter.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterWriter.java
@@ -29,12 +29,8 @@ import org.apache.hadoop.io.Writable;
 @InterfaceAudience.Private
 public interface BloomFilterWriter extends BloomFilterBase {
 
-  /** Allocate memory for the bloom filter data. */
-  void allocBloom();
-
   /** Compact the Bloom filter before writing metadata & data to disk. */
   void compactBloom();
-
   /**
    * Get a writable interface into bloom filter meta data.
    *

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/ByteBloomFilter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/ByteBloomFilter.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/ByteBloomFilter.java
deleted file mode 100644
index 1ea81dd..0000000
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/ByteBloomFilter.java
+++ /dev/null
@@ -1,654 +0,0 @@
-/*
- *
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.hadoop.hbase.util;
-
-import java.io.DataInput;
-import java.io.DataOutput;
-import java.io.IOException;
-import java.nio.ByteBuffer;
-import java.text.NumberFormat;
-import java.util.Random;
-
-import org.apache.hadoop.hbase.classification.InterfaceAudience;
-import org.apache.hadoop.io.Writable;
-
-/**
- * Implements a <i>Bloom filter</i>, as defined by Bloom in 1970.
- * <p>
- * The Bloom filter is a data structure that was introduced in 1970 and that has
- * been adopted by the networking research community in the past decade thanks
- * to the bandwidth efficiencies that it offers for the transmission of set
- * membership information between networked hosts. A sender encodes the
- * information into a bit vector, the Bloom filter, that is more compact than a
- * conventional representation. Computation and space costs for construction are
- * linear in the number of elements. The receiver uses the filter to test
- * whether various elements are members of the set. Though the filter will
- * occasionally return a false positive, it will never return a false negative.
- * When creating the filter, the sender can choose its desired point in a
- * trade-off between the false positive rate and the size.
- *
- * <p>
- * Originally inspired by <a href="http://www.one-lab.org">European Commission
- * One-Lab Project 034819</a>.
- *
- * Bloom filters are very sensitive to the number of elements inserted into
- * them. For HBase, the number of entries depends on the size of the data stored
- * in the column. Currently the default region size is 256MB, so entry count ~=
- * 256MB / (average value size for column). Despite this rule of thumb, there is
- * no efficient way to calculate the entry count after compactions. Therefore,
- * it is often easier to use a dynamic bloom filter that will add extra space
- * instead of allowing the error rate to grow.
- *
- * ( http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/BloomFilterSurvey
- * .pdf )
- *
- * m denotes the number of bits in the Bloom filter (bitSize) n denotes the
- * number of elements inserted into the Bloom filter (maxKeys) k represents the
- * number of hash functions used (nbHash) e represents the desired false
- * positive rate for the bloom (err)
- *
- * If we fix the error rate (e) and know the number of entries, then the optimal
- * bloom size m = -(n * ln(err) / (ln(2)^2) ~= n * ln(err) / ln(0.6185)
- *
- * The probability of false positives is minimized when k = m/n ln(2).
- *
- * @see BloomFilter The general behavior of a filter
- *
- * @see <a
- *      href="http://portal.acm.org/citation.cfm?id=362692&dl=ACM&coll=portal">
- *      Space/Time Trade-Offs in Hash Coding with Allowable Errors</a>
- */
-@InterfaceAudience.Private
-// TODO : Remove this ByteBloomFilter as an instance of BloomFilter
-public class ByteBloomFilter implements BloomFilter, BloomFilterWriter {
-
-  /** Current file format version */
-  public static final int VERSION = 1;
-
-  /** Bytes (B) in the array. This actually has to fit into an int. */
-  protected long byteSize;
-  /** Number of hash functions */
-  protected int hashCount;
-  /** Hash type */
-  protected final int hashType;
-  /** Hash Function */
-  protected final Hash hash;
-  /** Keys currently in the bloom */
-  protected int keyCount;
-  /** Max Keys expected for the bloom */
-  protected int maxKeys;
-  /** Bloom bits */
-  protected ByteBuffer bloom;
-
-  /** Record separator for the Bloom filter statistics human-readable string */
-  public static final String STATS_RECORD_SEP = "; ";
-
-  /**
-   * Used in computing the optimal Bloom filter size. This approximately equals
-   * 0.480453.
-   */
-  public static final double LOG2_SQUARED = Math.log(2) * Math.log(2);
-
-  /**
-   * A random number generator to use for "fake lookups" when testing to
-   * estimate the ideal false positive rate.
-   */
-  private static Random randomGeneratorForTest;
-
-  /** Bit-value lookup array to prevent doing the same work over and over */
-  private static final byte [] bitvals = {
-    (byte) 0x01,
-    (byte) 0x02,
-    (byte) 0x04,
-    (byte) 0x08,
-    (byte) 0x10,
-    (byte) 0x20,
-    (byte) 0x40,
-    (byte) 0x80
-  };
-
-  /**
-   * Loads bloom filter meta data from file input.
-   * @param meta stored bloom meta data
-   * @throws IllegalArgumentException meta data is invalid
-   */
-  public ByteBloomFilter(DataInput meta)
-      throws IOException, IllegalArgumentException {
-    this.byteSize = meta.readInt();
-    this.hashCount = meta.readInt();
-    this.hashType = meta.readInt();
-    this.keyCount = meta.readInt();
-    this.maxKeys = this.keyCount;
-
-    this.hash = Hash.getInstance(this.hashType);
-    if (hash == null) {
-      throw new IllegalArgumentException("Invalid hash type: " + hashType);
-    }
-    sanityCheck();
-  }
-
-  /**
-   * @param maxKeys
-   * @param errorRate
-   * @return the number of bits for a Bloom filter than can hold the given
-   *         number of keys and provide the given error rate, assuming that the
-   *         optimal number of hash functions is used and it does not have to
-   *         be an integer.
-   */
-  public static long computeBitSize(long maxKeys, double errorRate) {
-    return (long) Math.ceil(maxKeys * (-Math.log(errorRate) / LOG2_SQUARED));
-  }
-
-  /**
-   * The maximum number of keys we can put into a Bloom filter of a certain
-   * size to maintain the given error rate, assuming the number of hash
-   * functions is chosen optimally and does not even have to be an integer
-   * (hence the "ideal" in the function name).
-   *
-   * @param bitSize
-   * @param errorRate
-   * @return maximum number of keys that can be inserted into the Bloom filter
-   * @see #computeMaxKeys(long, double, int) for a more precise estimate
-   */
-  public static long idealMaxKeys(long bitSize, double errorRate) {
-    // The reason we need to use floor here is that otherwise we might put
-    // more keys in a Bloom filter than is allowed by the target error rate.
-    return (long) (bitSize * (LOG2_SQUARED / -Math.log(errorRate)));
-  }
-
-  /**
-   * The maximum number of keys we can put into a Bloom filter of a certain
-   * size to get the given error rate, with the given number of hash functions.
-   *
-   * @param bitSize
-   * @param errorRate
-   * @param hashCount
-   * @return the maximum number of keys that can be inserted in a Bloom filter
-   *         to maintain the target error rate, if the number of hash functions
-   *         is provided.
-   */
-  public static long computeMaxKeys(long bitSize, double errorRate,
-      int hashCount) {
-    return (long) (-bitSize * 1.0 / hashCount *
-        Math.log(1 - Math.exp(Math.log(errorRate) / hashCount)));
-  }
-
-  /**
-   * Computes the error rate for this Bloom filter, taking into account the
-   * actual number of hash functions and keys inserted. The return value of
-   * this function changes as a Bloom filter is being populated. Used for
-   * reporting the actual error rate of compound Bloom filters when writing
-   * them out.
-   *
-   * @return error rate for this particular Bloom filter
-   */
-  public double actualErrorRate() {
-    return actualErrorRate(keyCount, byteSize * 8, hashCount);
-  }
-
-  /**
-   * Computes the actual error rate for the given number of elements, number
-   * of bits, and number of hash functions. Taken directly from the
-   * <a href=
-   * "http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives"
-   * > Wikipedia Bloom filter article</a>.
-   *
-   * @param maxKeys
-   * @param bitSize
-   * @param functionCount
-   * @return the actual error rate
-   */
-  public static double actualErrorRate(long maxKeys, long bitSize,
-      int functionCount) {
-    return Math.exp(Math.log(1 - Math.exp(-functionCount * maxKeys * 1.0
-        / bitSize)) * functionCount);
-  }
-
-  /**
-   * Increases the given byte size of a Bloom filter until it can be folded by
-   * the given factor.
-   *
-   * @param bitSize
-   * @param foldFactor
-   * @return Foldable byte size
-   */
-  public static int computeFoldableByteSize(long bitSize, int foldFactor) {
-    long byteSizeLong = (bitSize + 7) / 8;
-    int mask = (1 << foldFactor) - 1;
-    if ((mask & byteSizeLong) != 0) {
-      byteSizeLong >>= foldFactor;
-      ++byteSizeLong;
-      byteSizeLong <<= foldFactor;
-    }
-    if (byteSizeLong > Integer.MAX_VALUE) {
-      throw new IllegalArgumentException("byteSize=" + byteSizeLong + " too "
-          + "large for bitSize=" + bitSize + ", foldFactor=" + foldFactor);
-    }
-    return (int) byteSizeLong;
-  }
-
-  private static int optimalFunctionCount(int maxKeys, long bitSize) {
-    long i = bitSize / maxKeys;
-    double result = Math.ceil(Math.log(2) * i);
-    if (result > Integer.MAX_VALUE){
-      throw new IllegalArgumentException("result too large for integer value.");
-    }
-    return (int)result;
-  }
-
-  /** Private constructor used by other constructors. */
-  private ByteBloomFilter(int hashType) {
-    this.hashType = hashType;
-    this.hash = Hash.getInstance(hashType);
-  }
-
-  /**
-   * Determines & initializes bloom filter meta data from user config. Call
-   * {@link #allocBloom()} to allocate bloom filter data.
-   *
-   * @param maxKeys Maximum expected number of keys that will be stored in this
-   *          bloom
-   * @param errorRate Desired false positive error rate. Lower rate = more
-   *          storage required
-   * @param hashType Type of hash function to use
-   * @param foldFactor When finished adding entries, you may be able to 'fold'
-   *          this bloom to save space. Tradeoff potentially excess bytes in
-   *          bloom for ability to fold if keyCount is exponentially greater
-   *          than maxKeys.
-   * @throws IllegalArgumentException
-   */
-  public ByteBloomFilter(int maxKeys, double errorRate, int hashType,
-      int foldFactor) throws IllegalArgumentException {
-    this(hashType);
-
-    long bitSize = computeBitSize(maxKeys, errorRate);
-    hashCount = optimalFunctionCount(maxKeys, bitSize);
-    this.maxKeys = maxKeys;
-
-    // increase byteSize so folding is possible
-    byteSize = computeFoldableByteSize(bitSize, foldFactor);
-
-    sanityCheck();
-  }
-
-  /**
-   * Creates a Bloom filter of the given size.
-   *
-   * @param byteSizeHint the desired number of bytes for the Bloom filter bit
-   *          array. Will be increased so that folding is possible.
-   * @param errorRate target false positive rate of the Bloom filter
-   * @param hashType Bloom filter hash function type
-   * @param foldFactor
-   * @return the new Bloom filter of the desired size
-   */
-  public static ByteBloomFilter createBySize(int byteSizeHint,
-      double errorRate, int hashType, int foldFactor) {
-    ByteBloomFilter bbf = new ByteBloomFilter(hashType);
-
-    bbf.byteSize = computeFoldableByteSize(byteSizeHint * 8L, foldFactor);
-    long bitSize = bbf.byteSize * 8;
-    bbf.maxKeys = (int) idealMaxKeys(bitSize, errorRate);
-    bbf.hashCount = optimalFunctionCount(bbf.maxKeys, bitSize);
-
-    // Adjust max keys to bring error rate closer to what was requested,
-    // because byteSize was adjusted to allow for folding, and hashCount was
-    // rounded.
-    bbf.maxKeys = (int) computeMaxKeys(bitSize, errorRate, bbf.hashCount);
-
-    return bbf;
-  }
-
-  /**
-   * Creates another similar Bloom filter. Does not copy the actual bits, and
-   * sets the new filter's key count to zero.
-   *
-   * @return a Bloom filter with the same configuration as this
-   */
-  public ByteBloomFilter createAnother() {
-    ByteBloomFilter bbf = new ByteBloomFilter(hashType);
-    bbf.byteSize = byteSize;
-    bbf.hashCount = hashCount;
-    bbf.maxKeys = maxKeys;
-    return bbf;
-  }
-
-  @Override
-  public void allocBloom() {
-    if (this.bloom != null) {
-      throw new IllegalArgumentException("can only create bloom once.");
-    }
-    this.bloom = ByteBuffer.allocate((int)this.byteSize);
-    assert this.bloom.hasArray();
-  }
-
-  void sanityCheck() throws IllegalArgumentException {
-    if(0 >= this.byteSize || this.byteSize > Integer.MAX_VALUE) {
-      throw new IllegalArgumentException("Invalid byteSize: " + this.byteSize);
-    }
-
-    if(this.hashCount <= 0) {
-      throw new IllegalArgumentException("Hash function count must be > 0");
-    }
-
-    if (this.hash == null) {
-      throw new IllegalArgumentException("hashType must be known");
-    }
-
-    if (this.keyCount < 0) {
-      throw new IllegalArgumentException("must have positive keyCount");
-    }
-  }
-
-  void bloomCheck(ByteBuffer bloom)  throws IllegalArgumentException {
-    if (this.byteSize != bloom.limit()) {
-      throw new IllegalArgumentException(
-          "Configured bloom length should match actual length");
-    }
-  }
-
-  public void add(byte [] buf) {
-    add(buf, 0, buf.length);
-  }
-
-  @Override
-  public void add(byte [] buf, int offset, int len) {
-    /*
-     * For faster hashing, use combinatorial generation
-     * http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
-     */
-    int hash1 = this.hash.hash(buf, offset, len, 0);
-    int hash2 = this.hash.hash(buf, offset, len, hash1);
-
-    for (int i = 0; i < this.hashCount; i++) {
-      long hashLoc = Math.abs((hash1 + i * hash2) % (this.byteSize * 8));
-      set(hashLoc);
-    }
-
-    ++this.keyCount;
-  }
-
-  /** Should only be used in tests */
-  boolean contains(byte [] buf) {
-    return contains(buf, 0, buf.length, this.bloom);
-  }
-
-  /** Should only be used in tests */
-  boolean contains(byte [] buf, int offset, int length) {
-    return contains(buf, offset, length, bloom);
-  }
-
-  /** Should only be used in tests */
-  boolean contains(byte[] buf, ByteBuffer bloom) {
-    return contains(buf, 0, buf.length, bloom);
-  }
-
-  @Override
-  public boolean contains(byte[] buf, int offset, int length, ByteBuffer theBloom) {
-    if (theBloom == null) {
-      // In a version 1 HFile Bloom filter data is stored in a separate meta
-      // block which is loaded on demand, but in version 2 it is pre-loaded.
-      // We want to use the same API in both cases.
-      theBloom = bloom;
-    }
-
-    if (theBloom.limit() != byteSize) {
-      throw new IllegalArgumentException("Bloom does not match expected size:"
-          + " theBloom.limit()=" + theBloom.limit() + ", byteSize=" + byteSize);
-    }
-
-    return contains(buf, offset, length, theBloom, 0, (int) byteSize, hash, hashCount);
-  }
-
-  public static boolean contains(byte[] buf, int offset, int length,
-      ByteBuffer bloomBuf, int bloomOffset, int bloomSize, Hash hash,
-      int hashCount) {
-
-    int hash1 = hash.hash(buf, offset, length, 0);
-    int hash2 = hash.hash(buf, offset, length, hash1);
-    int bloomBitSize = bloomSize << 3;
-    
-    if (randomGeneratorForTest == null) {
-      // Production mode.
-      int compositeHash = hash1;
-      for (int i = 0; i < hashCount; i++) {
-        int hashLoc = Math.abs(compositeHash % bloomBitSize);
-        compositeHash += hash2;
-        if (!get(hashLoc, bloomBuf, bloomOffset)) {
-          return false;
-        }
-      }
-    } else {
-      // Test mode with "fake lookups" to estimate "ideal false positive rate".
-      for (int i = 0; i < hashCount; i++) {
-        int hashLoc = randomGeneratorForTest.nextInt(bloomBitSize);
-        if (!get(hashLoc, bloomBuf, bloomOffset)){
-          return false;
-        }
-      }
-    }
-    return true;
-  }
-
-  //---------------------------------------------------------------------------
-  /** Private helpers */
-
-  /**
-   * Set the bit at the specified index to 1.
-   *
-   * @param pos index of bit
-   */
-  void set(long pos) {
-    int bytePos = (int)(pos / 8);
-    int bitPos = (int)(pos % 8);
-    byte curByte = bloom.get(bytePos);
-    curByte |= bitvals[bitPos];
-    bloom.put(bytePos, curByte);
-  }
-
-  /**
-   * Check if bit at specified index is 1.
-   *
-   * @param pos index of bit
-   * @return true if bit at specified index is 1, false if 0.
-   */
-  static boolean get(int pos, ByteBuffer bloomBuf, int bloomOffset) {
-    int bytePos = pos >> 3; //pos / 8
-    int bitPos = pos & 0x7; //pos % 8
-    // TODO access this via Util API which can do Unsafe access if possible(?)
-    byte curByte = bloomBuf.get(bloomOffset + bytePos);
-    curByte &= bitvals[bitPos];
-    return (curByte != 0);
-  }
-
-  @Override
-  public long getKeyCount() {
-    return keyCount;
-  }
-
-  @Override
-  public long getMaxKeys() {
-    return maxKeys;
-  }
-
-  @Override
-  public long getByteSize() {
-    return byteSize;
-  }
-
-  public int getHashType() {
-    return hashType;
-  }
-
-  @Override
-  public void compactBloom() {
-    // see if the actual size is exponentially smaller than expected.
-    if (this.keyCount > 0 && this.bloom.hasArray()) {
-      int pieces = 1;
-      int newByteSize = (int)this.byteSize;
-      int newMaxKeys = this.maxKeys;
-
-      // while exponentially smaller & folding is lossless
-      while ((newByteSize & 1) == 0 && newMaxKeys > (this.keyCount<<1) ) {
-        pieces <<= 1;
-        newByteSize >>= 1;
-        newMaxKeys >>= 1;
-      }
-
-      // if we should fold these into pieces
-      if (pieces > 1) {
-        byte[] array = this.bloom.array();
-        int start = this.bloom.arrayOffset();
-        int end = start + newByteSize;
-        int off = end;
-        for(int p = 1; p < pieces; ++p) {
-          for(int pos = start; pos < end; ++pos) {
-            array[pos] |= array[off++];
-          }
-        }
-        // folding done, only use a subset of this array
-        this.bloom.rewind();
-        this.bloom.limit(newByteSize);
-        this.bloom = this.bloom.slice();
-        this.byteSize = newByteSize;
-        this.maxKeys = newMaxKeys;
-      }
-    }
-  }
-
-
-  //---------------------------------------------------------------------------
-
-  /**
-   * Writes just the bloom filter to the output array
-   * @param out OutputStream to place bloom
-   * @throws IOException Error writing bloom array
-   */
-  public void writeBloom(final DataOutput out) throws IOException {
-    if (!this.bloom.hasArray()) {
-      throw new IOException("Only writes ByteBuffer with underlying array.");
-    }
-    out.write(bloom.array(), bloom.arrayOffset(), bloom.limit());
-  }
-
-  @Override
-  public Writable getMetaWriter() {
-    return new MetaWriter();
-  }
-
-  @Override
-  public Writable getDataWriter() {
-    return new DataWriter();
-  }
-
-  private class MetaWriter implements Writable {
-    protected MetaWriter() {}
-    @Override
-    public void readFields(DataInput arg0) throws IOException {
-      throw new IOException("Cant read with this class.");
-    }
-
-    @Override
-    public void write(DataOutput out) throws IOException {
-      out.writeInt(VERSION);
-      out.writeInt((int) byteSize);
-      out.writeInt(hashCount);
-      out.writeInt(hashType);
-      out.writeInt(keyCount);
-    }
-  }
-
-  private class DataWriter implements Writable {
-    protected DataWriter() {}
-    @Override
-    public void readFields(DataInput arg0) throws IOException {
-      throw new IOException("Cant read with this class.");
-    }
-
-    @Override
-    public void write(DataOutput out) throws IOException {
-      writeBloom(out);
-    }
-  }
-
-  public int getHashCount() {
-    return hashCount;
-  }
-
-  @Override
-  public boolean supportsAutoLoading() {
-    return bloom != null;
-  }
-
-  public static void setFakeLookupMode(boolean enabled) {
-    if (enabled) {
-      randomGeneratorForTest = new Random(283742987L);
-    } else {
-      randomGeneratorForTest = null;
-    }
-  }
-
-  /**
-   * {@inheritDoc}
-   * Just concatenate row and column by default. May return the original row
-   * buffer if the column qualifier is empty.
-   */
-  @Override
-  public byte[] createBloomKey(byte[] rowBuf, int rowOffset, int rowLen,
-      byte[] qualBuf, int qualOffset, int qualLen) {
-    // Optimize the frequent case when only the row is provided.
-    if (qualLen <= 0 && rowOffset == 0 && rowLen == rowBuf.length)
-      return rowBuf;
-
-    byte [] result = new byte[rowLen + qualLen];
-    System.arraycopy(rowBuf, rowOffset, result, 0,  rowLen);
-    if (qualLen > 0)
-      System.arraycopy(qualBuf, qualOffset, result, rowLen, qualLen);
-    return result;
-  }
-
-  /**
-   * A human-readable string with statistics for the given Bloom filter.
-   *
-   * @param bloomFilter the Bloom filter to output statistics for;
-   * @return a string consisting of "&lt;key&gt;: &lt;value&gt;" parts
-   *         separated by {@link #STATS_RECORD_SEP}.
-   */
-  public static String formatStats(BloomFilterBase bloomFilter) {
-    StringBuilder sb = new StringBuilder();
-    long k = bloomFilter.getKeyCount();
-    long m = bloomFilter.getMaxKeys();
-
-    sb.append("BloomSize: " + bloomFilter.getByteSize() + STATS_RECORD_SEP);
-    sb.append("No of Keys in bloom: " + k + STATS_RECORD_SEP);
-    sb.append("Max Keys for bloom: " + m);
-    if (m > 0) {
-      sb.append(STATS_RECORD_SEP + "Percentage filled: "
-          + NumberFormat.getPercentInstance().format(k * 1.0 / m));
-    }
-    return sb.toString();
-  }
-
-  @Override
-  public String toString() {
-    return formatStats(this) + STATS_RECORD_SEP + "Actual error rate: "
-        + String.format("%.8f", actualErrorRate());
-  }
-
-}

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java
index cae9d31..984742f 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java
@@ -23,6 +23,8 @@ import java.io.DataInput;
 import java.io.IOException;
 import java.nio.ByteBuffer;
 
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.classification.InterfaceAudience;
 import org.apache.hadoop.hbase.io.hfile.BlockType;
 import org.apache.hadoop.hbase.io.hfile.FixedFileTrailer;
@@ -31,7 +33,7 @@ import org.apache.hadoop.hbase.io.hfile.HFileBlock;
 import org.apache.hadoop.hbase.io.hfile.HFileBlockIndex;
 
 /**
- * A Bloom filter implementation built on top of {@link ByteBloomFilter},
+ * A Bloom filter implementation built on top of {@link BloomFilterChunk},
  * encapsulating a set of fixed-size Bloom filters written out at the time of
  * {@link org.apache.hadoop.hbase.io.hfile.HFile} generation into the data
  * block stream, and loaded on demand at query time. This class only provides
@@ -90,10 +92,14 @@ public class CompoundBloomFilter extends CompoundBloomFilterBase
   public boolean contains(byte[] key, int keyOffset, int keyLength, ByteBuffer bloom) {
     // We try to store the result in this variable so we can update stats for
     // testing, but when an error happens, we log a message and return.
-    boolean result;
 
     int block = index.rootBlockContainingKey(key, keyOffset,
-        keyLength, comparator);
+        keyLength);
+    return checkContains(key, keyOffset, keyLength, block);
+  }
+
+  private boolean checkContains(byte[] key, int keyOffset, int keyLength, int block) {
+    boolean result;
     if (block < 0) {
       result = false; // This key is not in the file.
     } else {
@@ -111,7 +117,7 @@ public class CompoundBloomFilter extends CompoundBloomFilterBase
       }
 
       ByteBuffer bloomBuf = bloomBlock.getBufferReadOnly();
-      result = ByteBloomFilter.contains(key, keyOffset, keyLength,
+      result = BloomFilterUtil.contains(key, keyOffset, keyLength,
           bloomBuf, bloomBlock.headerSize(),
           bloomBlock.getUncompressedSizeWithoutHeader(), hash, hashCount);
     }
@@ -126,6 +132,18 @@ public class CompoundBloomFilter extends CompoundBloomFilterBase
     return result;
   }
 
+  @Override
+  public boolean contains(Cell keyCell, ByteBuffer bloom) {
+    // We try to store the result in this variable so we can update stats for
+    // testing, but when an error happens, we log a message and return.
+    int block = index.rootBlockContainingKey(keyCell);
+    // TODO : Will be true KeyValue for now.
+    // When Offheap comes in we can add an else condition to work
+    // on the bytes in offheap
+    KeyValue kvKey = (KeyValue) keyCell;
+    return checkContains(kvKey.getBuffer(), kvKey.getKeyOffset(), kvKey.getKeyLength(), block);
+  }
+
   public boolean supportsAutoLoading() {
     return true;
   }
@@ -166,10 +184,10 @@ public class CompoundBloomFilter extends CompoundBloomFilterBase
   @Override
   public String toString() {
     StringBuilder sb = new StringBuilder();
-    sb.append(ByteBloomFilter.formatStats(this));
-    sb.append(ByteBloomFilter.STATS_RECORD_SEP + 
+    sb.append(BloomFilterUtil.formatStats(this));
+    sb.append(BloomFilterUtil.STATS_RECORD_SEP + 
         "Number of chunks: " + numChunks);
-    sb.append(ByteBloomFilter.STATS_RECORD_SEP + 
+    sb.append(BloomFilterUtil.STATS_RECORD_SEP + 
         ((comparator != null) ? "Comparator: "
         + comparator.getClass().getSimpleName() : "Comparator: "
         + Bytes.BYTES_RAWCOMPARATOR.getClass().getSimpleName()));

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterBase.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterBase.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterBase.java
index d68c78d..7c29ab2 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterBase.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterBase.java
@@ -22,8 +22,6 @@ package org.apache.hadoop.hbase.util;
 import org.apache.hadoop.hbase.classification.InterfaceAudience;
 
 import org.apache.hadoop.hbase.CellComparator;
-import org.apache.hadoop.hbase.KeyValue;
-import org.apache.hadoop.hbase.KeyValueUtil;
 
 @InterfaceAudience.Private
 public class CompoundBloomFilterBase implements BloomFilterBase {
@@ -69,24 +67,4 @@ public class CompoundBloomFilterBase implements BloomFilterBase {
     return totalByteSize;
   }
 
-  private static final byte[] DUMMY = new byte[0];
-
-  /**
-   * Prepare an ordered pair of row and qualifier to be compared using
-   * KeyValue.KeyComparator. This is only used for row-column Bloom
-   * filters.
-   */
-  @Override
-  public byte[] createBloomKey(byte[] row, int roffset, int rlength,
-      byte[] qualifier, int qoffset, int qlength) {
-    if (qualifier == null)
-      qualifier = DUMMY;
-
-    // Make sure this does not specify a timestamp so that the default maximum
-    // (most recent) timestamp is used.
-    KeyValue kv = KeyValueUtil.createFirstOnRow(row, roffset, rlength, DUMMY, 0, 0,
-        qualifier, qoffset, qlength);
-    return kv.getKey();
-  }
-
 }

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterWriter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterWriter.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterWriter.java
index 594fc94..93c6a7b 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterWriter.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilterWriter.java
@@ -47,10 +47,10 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
     LogFactory.getLog(CompoundBloomFilterWriter.class);
 
   /** The current chunk being written to */
-  private ByteBloomFilter chunk;
+  private BloomFilterChunk chunk;
 
   /** Previous chunk, so that we can create another similar chunk */
-  private ByteBloomFilter prevChunk;
+  private BloomFilterChunk prevChunk;
 
   /** Maximum fold factor */
   private int maxFold;
@@ -62,7 +62,7 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
   private static class ReadyChunk {
     int chunkId;
     byte[] firstKey;
-    ByteBloomFilter chunk;
+    BloomFilterChunk chunk;
   }
 
   private Queue<ReadyChunk> readyChunks = new LinkedList<ReadyChunk>();
@@ -90,7 +90,7 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
   public CompoundBloomFilterWriter(int chunkByteSizeHint, float errorRate,
       int hashType, int maxFold, boolean cacheOnWrite,
       CellComparator comparator) {
-    chunkByteSize = ByteBloomFilter.computeFoldableByteSize(
+    chunkByteSize = BloomFilterUtil.computeFoldableByteSize(
         chunkByteSizeHint * 8L, maxFold);
 
     this.errorRate = errorRate;
@@ -174,7 +174,7 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
 
       if (prevChunk == null) {
         // First chunk
-        chunk = ByteBloomFilter.createBySize(chunkByteSize, errorRate,
+        chunk = BloomFilterUtil.createBySize(chunkByteSize, errorRate,
             hashType, maxFold);
       } else {
         // Use the same parameters as the last chunk, but a new array and
@@ -201,8 +201,8 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
     // again for cache-on-write.
     ReadyChunk readyChunk = readyChunks.peek();
 
-    ByteBloomFilter readyChunkBloom = readyChunk.chunk;
-    readyChunkBloom.getDataWriter().write(out);
+    BloomFilterChunk readyChunkBloom = readyChunk.chunk;
+    readyChunkBloom.writeBloom(out);
   }
 
   @Override
@@ -225,7 +225,7 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
     }
 
     /**
-     * This is modeled after {@link ByteBloomFilter.MetaWriter} for simplicity,
+     * This is modeled after {@link BloomFilterChunk.MetaWriter} for simplicity,
      * although the two metadata formats do not have to be consistent. This
      * does have to be consistent with how {@link
      * CompoundBloomFilter#CompoundBloomFilter(DataInput,
@@ -256,17 +256,12 @@ public class CompoundBloomFilterWriter extends CompoundBloomFilterBase
   }
 
   @Override
-  public Writable getMetaWriter() {
-    return new MetaWriter();
-  }
-
-  @Override
   public void compactBloom() {
   }
 
   @Override
-  public void allocBloom() {
-    // Nothing happens here. All allocation happens on demand.
+  public Writable getMetaWriter() {
+    return new MetaWriter();
   }
 
   @Override

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCompoundBloomFilter.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCompoundBloomFilter.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCompoundBloomFilter.java
index 9bd9099..ce40515 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCompoundBloomFilter.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCompoundBloomFilter.java
@@ -51,11 +51,11 @@ import org.apache.hadoop.hbase.io.hfile.HFileContext;
 import org.apache.hadoop.hbase.io.hfile.HFileContextBuilder;
 import org.apache.hadoop.hbase.io.hfile.TestHFileWriterV2;
 import org.apache.hadoop.hbase.util.BloomFilterFactory;
-import org.apache.hadoop.hbase.util.ByteBloomFilter;
 import org.apache.hadoop.hbase.util.Bytes;
 import org.apache.hadoop.hbase.util.CompoundBloomFilter;
 import org.apache.hadoop.hbase.util.CompoundBloomFilterBase;
 import org.apache.hadoop.hbase.util.CompoundBloomFilterWriter;
+import org.apache.hadoop.hbase.util.BloomFilterUtil;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.experimental.categories.Category;
@@ -220,7 +220,7 @@ public class TestCompoundBloomFilter {
     // Test for false positives (some percentage allowed). We test in two modes:
     // "fake lookup" which ignores the key distribution, and production mode.
     for (boolean fakeLookupEnabled : new boolean[] { true, false }) {
-      ByteBloomFilter.setFakeLookupMode(fakeLookupEnabled);
+      BloomFilterUtil.setFakeLookupMode(fakeLookupEnabled);
       try {
         String fakeLookupModeStr = ", fake lookup is " + (fakeLookupEnabled ?
             "enabled" : "disabled");
@@ -270,7 +270,7 @@ public class TestCompoundBloomFilter {
         validateFalsePosRate(falsePosRate, nTrials, -2.58, cbf,
             fakeLookupModeStr);
       } finally {
-        ByteBloomFilter.setFakeLookupMode(false);
+        BloomFilterUtil.setFakeLookupMode(false);
       }
     }
 
@@ -337,11 +337,11 @@ public class TestCompoundBloomFilter {
     int bloomBlockByteSize = 4096;
     int bloomBlockBitSize = bloomBlockByteSize * 8;
     double targetErrorRate = 0.01;
-    long maxKeysPerChunk = ByteBloomFilter.idealMaxKeys(bloomBlockBitSize,
+    long maxKeysPerChunk = BloomFilterUtil.idealMaxKeys(bloomBlockBitSize,
         targetErrorRate);
 
     long bloomSize1 = bloomBlockByteSize * 8;
-    long bloomSize2 = ByteBloomFilter.computeBitSize(maxKeysPerChunk,
+    long bloomSize2 = BloomFilterUtil.computeBitSize(maxKeysPerChunk,
         targetErrorRate);
 
     double bloomSizeRatio = (bloomSize2 * 1.0 / bloomSize1);
@@ -350,13 +350,12 @@ public class TestCompoundBloomFilter {
 
   @Test
   public void testCreateKey() {
-    CompoundBloomFilterBase cbfb = new CompoundBloomFilterBase();
     byte[] row = "myRow".getBytes();
     byte[] qualifier = "myQualifier".getBytes();
-    byte[] rowKey = cbfb.createBloomKey(row, 0, row.length,
-        row, 0, 0);
-    byte[] rowColKey = cbfb.createBloomKey(row, 0, row.length,
-        qualifier, 0, qualifier.length);
+    // Mimic what Storefile.createBloomKeyValue() does
+    byte[] rowKey = KeyValueUtil.createFirstOnRow(row, 0, row.length, new byte[0], 0, 0, row, 0, 0).getKey();
+    byte[] rowColKey = KeyValueUtil.createFirstOnRow(row, 0, row.length,
+        new byte[0], 0, 0, qualifier, 0, qualifier.length).getKey();
     KeyValue rowKV = KeyValueUtil.createKeyValueFromKey(rowKey);
     KeyValue rowColKV = KeyValueUtil.createKeyValueFromKey(rowColKey);
     assertEquals(rowKV.getTimestamp(), rowColKV.getTimestamp());

http://git-wip-us.apache.org/repos/asf/hbase/blob/5e7e626e/hbase-server/src/test/java/org/apache/hadoop/hbase/util/TestBloomFilterChunk.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/util/TestBloomFilterChunk.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/util/TestBloomFilterChunk.java
new file mode 100644
index 0000000..4d8ad4b
--- /dev/null
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/util/TestBloomFilterChunk.java
@@ -0,0 +1,185 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.hadoop.hbase.util;
+
+import java.io.ByteArrayOutputStream;
+import java.io.DataOutputStream;
+import java.nio.ByteBuffer;
+
+import junit.framework.TestCase;
+import org.apache.hadoop.hbase.testclassification.MiscTests;
+import org.apache.hadoop.hbase.testclassification.SmallTests;
+import org.junit.experimental.categories.Category;
+
+@Category({MiscTests.class, SmallTests.class})
+public class TestBloomFilterChunk extends TestCase {
+
+  public void testBasicBloom() throws Exception {
+    BloomFilterChunk bf1 = new BloomFilterChunk(1000, (float)0.01, Hash.MURMUR_HASH, 0);
+    BloomFilterChunk bf2 = new BloomFilterChunk(1000, (float)0.01, Hash.MURMUR_HASH, 0);
+    bf1.allocBloom();
+    bf2.allocBloom();
+
+    // test 1: verify no fundamental false negatives or positives
+    byte[] key1 = {1,2,3,4,5,6,7,8,9};
+    byte[] key2 = {1,2,3,4,5,6,7,8,7};
+
+    bf1.add(key1);
+    bf2.add(key2);
+
+    assertTrue(BloomFilterUtil.contains(key1, 0, key1.length, bf1.bloom, 0, (int) bf1.byteSize,
+        bf1.hash, bf1.hashCount));
+    assertFalse(BloomFilterUtil.contains(key2, 0, key2.length, bf1.bloom, 0, (int) bf1.byteSize,
+        bf1.hash, bf1.hashCount));
+    assertFalse(BloomFilterUtil.contains(key1, 0, key1.length, bf2.bloom, 0, (int) bf2.byteSize,
+        bf2.hash, bf2.hashCount));
+    assertTrue(BloomFilterUtil.contains(key2, 0, key2.length, bf2.bloom, 0, (int) bf2.byteSize,
+        bf2.hash, bf2.hashCount));
+
+    byte [] bkey = {1,2,3,4};
+    byte [] bval = "this is a much larger byte array".getBytes();
+
+    bf1.add(bkey);
+    bf1.add(bval, 1, bval.length-1);
+
+    assertTrue(BloomFilterUtil.contains(bkey, 0, bkey.length, bf1.bloom, 0, (int) bf1.byteSize,
+        bf1.hash, bf1.hashCount));
+    assertTrue(BloomFilterUtil.contains(bval, 1, bval.length - 1, bf1.bloom, 0, (int) bf1.byteSize,
+        bf1.hash, bf1.hashCount));
+    assertFalse(BloomFilterUtil.contains(bval, 0, bval.length, bf1.bloom, 0, (int) bf1.byteSize,
+        bf1.hash, bf1.hashCount));
+
+    // test 2: serialization & deserialization.
+    // (convert bloom to byte array & read byte array back in as input)
+    ByteArrayOutputStream bOut = new ByteArrayOutputStream();
+    bf1.writeBloom(new DataOutputStream(bOut));
+    ByteBuffer bb = ByteBuffer.wrap(bOut.toByteArray());
+    BloomFilterChunk newBf1 = new BloomFilterChunk(1000, (float)0.01,
+        Hash.MURMUR_HASH, 0);
+    assertTrue(BloomFilterUtil.contains(key1, 0, key1.length, bb, 0, (int) newBf1.byteSize,
+        newBf1.hash, newBf1.hashCount));
+    assertFalse(BloomFilterUtil.contains(key2, 0, key2.length, bb, 0, (int) newBf1.byteSize,
+        newBf1.hash, newBf1.hashCount));
+    assertTrue(BloomFilterUtil.contains(bkey, 0, bkey.length, bb, 0, (int) newBf1.byteSize,
+        newBf1.hash, newBf1.hashCount));
+    assertTrue(BloomFilterUtil.contains(bval, 1, bval.length - 1, bb, 0, (int) newBf1.byteSize,
+        newBf1.hash, newBf1.hashCount));
+    assertFalse(BloomFilterUtil.contains(bval, 0, bval.length, bb, 0, (int) newBf1.byteSize,
+        newBf1.hash, newBf1.hashCount));
+    assertFalse(BloomFilterUtil.contains(bval, 0, bval.length, bb, 0, (int) newBf1.byteSize,
+        newBf1.hash, newBf1.hashCount));
+
+    System.out.println("Serialized as " + bOut.size() + " bytes");
+    assertTrue(bOut.size() - bf1.byteSize < 10); //... allow small padding
+  }
+
+  public void testBloomFold() throws Exception {
+    // test: foldFactor < log(max/actual)
+    BloomFilterChunk b = new BloomFilterChunk(1003, (float) 0.01,
+        Hash.MURMUR_HASH, 2);
+    b.allocBloom();
+    long origSize = b.getByteSize();
+    assertEquals(1204, origSize);
+    for (int i = 0; i < 12; ++i) {
+      b.add(Bytes.toBytes(i));
+    }
+    b.compactBloom();
+    assertEquals(origSize>>2, b.getByteSize());
+    int falsePositives = 0;
+    for (int i = 0; i < 25; ++i) {
+      byte[] bytes = Bytes.toBytes(i);
+      if (BloomFilterUtil.contains(bytes, 0, bytes.length, b.bloom, 0, (int) b.byteSize, b.hash,
+          b.hashCount)) {
+        if(i >= 12) falsePositives++;
+      } else {
+        assertFalse(i < 12);
+      }
+    }
+    assertTrue(falsePositives <= 1);
+
+    // test: foldFactor > log(max/actual)
+  }
+
+  public void testBloomPerf() throws Exception {
+    // add
+    float err = (float)0.01;
+    BloomFilterChunk b = new BloomFilterChunk(10*1000*1000, (float)err, Hash.MURMUR_HASH, 3);
+    b.allocBloom();
+    long startTime =  System.currentTimeMillis();
+    long origSize = b.getByteSize();
+    for (int i = 0; i < 1*1000*1000; ++i) {
+      b.add(Bytes.toBytes(i));
+    }
+    long endTime = System.currentTimeMillis();
+    System.out.println("Total Add time = " + (endTime - startTime) + "ms");
+
+    // fold
+    startTime = System.currentTimeMillis();
+    b.compactBloom();
+    endTime = System.currentTimeMillis();
+    System.out.println("Total Fold time = " + (endTime - startTime) + "ms");
+    assertTrue(origSize >= b.getByteSize()<<3);
+
+    // test
+    startTime = System.currentTimeMillis();
+    int falsePositives = 0;
+    for (int i = 0; i < 2*1000*1000; ++i) {
+
+      byte[] bytes = Bytes.toBytes(i);
+      if (BloomFilterUtil.contains(bytes, 0, bytes.length, b.bloom, 0, (int) b.byteSize, b.hash,
+          b.hashCount)) {
+        if(i >= 1*1000*1000) falsePositives++;
+      } else {
+        assertFalse(i < 1*1000*1000);
+      }
+    }
+    endTime = System.currentTimeMillis();
+    System.out.println("Total Contains time = " + (endTime - startTime) + "ms");
+    System.out.println("False Positive = " + falsePositives);
+    assertTrue(falsePositives <= (1*1000*1000)*err);
+
+    // test: foldFactor > log(max/actual)
+  }
+
+  public void testSizing() {
+    int bitSize = 8 * 128 * 1024; // 128 KB
+    double errorRate = 0.025; // target false positive rate
+
+    // How many keys can we store in a Bloom filter of this size maintaining
+    // the given false positive rate, not taking into account that the n
+    long maxKeys = BloomFilterUtil.idealMaxKeys(bitSize, errorRate);
+    assertEquals(136570, maxKeys);
+
+    // A reverse operation: how many bits would we need to store this many keys
+    // and keep the same low false positive rate?
+    long bitSize2 = BloomFilterUtil.computeBitSize(maxKeys, errorRate);
+
+    // The bit size comes out a little different due to rounding.
+    assertTrue(Math.abs(bitSize2 - bitSize) * 1.0 / bitSize < 1e-5);
+  }
+
+  public void testFoldableByteSize() {
+    assertEquals(128, BloomFilterUtil.computeFoldableByteSize(1000, 5));
+    assertEquals(640, BloomFilterUtil.computeFoldableByteSize(5001, 4));
+  }
+
+
+}
+


Mime
View raw message