hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ecl...@apache.org
Subject [05/19] hbase git commit: HBASE-12476 HydraBase consensus protocol
Date Tue, 25 Nov 2014 20:28:58 GMT
http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocator.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocator.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocator.java
new file mode 100644
index 0000000..62ca6cd
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocator.java
@@ -0,0 +1,455 @@
+/**
+ * Copyright The Apache Software Foundation
+ *
+ * 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.util.ArrayList;
+import java.util.List;
+
+import com.google.common.base.Preconditions;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.hbase.io.hfile.bucket.CacheFullException;
+
+/**
+ * This class is used to allocate a block with specified size and free the block
+ * when evicting. It manages an array of buckets, each bucket is associated with
+ * a size and caches elements up to this size. For completely empty bucket, this
+ * size could be re-specified dynamically.
+ *
+ * This class is not thread safe.
+ */
+public final class BucketAllocator {
+  static final Log LOG = LogFactory.getLog(BucketAllocator.class);
+
+  public static final int[] DEFAULT_BUCKETS = { 4 * 1024 + 1024,
+    8 * 1024 + 1024 };
+
+  final private static class Bucket {
+    private final int[] bucketSizes;
+    private final long bucketCapacity;
+    private long baseOffset;
+    private int itemAllocationSize, sizeIndex;
+    private int itemCount;
+    private int freeList[];
+    private int freeCount, usedCount;
+
+    public Bucket(int[] bucketSizes, long bucketCapacity, long offset) {
+      this.bucketSizes = bucketSizes;
+      this.bucketCapacity = bucketCapacity;
+      baseOffset = offset;
+      sizeIndex = -1;
+    }
+
+    void reconfigure(int sizeIndex) {
+      this.sizeIndex = Preconditions.checkPositionIndex(sizeIndex,
+          bucketSizes.length);
+      itemAllocationSize = bucketSizes[sizeIndex];
+      itemCount = (int) ((bucketCapacity) / (long) itemAllocationSize);
+      freeCount = itemCount;
+      usedCount = 0;
+      freeList = new int[itemCount];
+      for (int i = 0; i < freeCount; ++i)
+        freeList[i] = i;
+    }
+
+    public boolean isUninstantiated() {
+      return sizeIndex == -1;
+    }
+
+    public int sizeIndex() {
+      return sizeIndex;
+    }
+
+    public int itemAllocationSize() {
+      return itemAllocationSize;
+    }
+
+    public boolean hasFreeSpace() {
+      return freeCount > 0;
+    }
+
+    public boolean isCompletelyFree() {
+      return usedCount == 0;
+    }
+
+    public int freeCount() {
+      return freeCount;
+    }
+
+    public int usedCount() {
+      return usedCount;
+    }
+
+    public int freeBytes() {
+      return freeCount * itemAllocationSize;
+    }
+
+    public int usedBytes() {
+      return usedCount * itemAllocationSize;
+    }
+
+    public long baseOffset() {
+      return baseOffset;
+    }
+
+    /**
+     * Allocate a block in this bucket, return the offset representing the
+     * position in physical space
+     * @return the offset in the IOEngine
+     */
+    public long allocate() {
+      Preconditions.checkState(freeCount > 0, "No space to allocate!");
+      Preconditions.checkState(sizeIndex != -1);
+      ++usedCount;
+      return ConditionUtil
+          .checkPositiveOffset(baseOffset + (freeList[--freeCount] * itemAllocationSize));
+    }
+
+    private void free(long offset) {
+      Preconditions.checkState(usedCount > 0);
+      Preconditions.checkState(freeCount < itemCount,
+          "duplicate free, offset: " + offset);
+      offset = ConditionUtil.checkOffset(offset - baseOffset,
+          itemCount * itemAllocationSize);
+      Preconditions.checkState(offset % itemAllocationSize == 0);
+      int item = (int) (offset / (long) itemAllocationSize);
+      Preconditions.checkState(!freeListContains(item), "Item at " + offset +
+          " already on freelist!");
+
+      --usedCount;
+      freeList[freeCount++] = item;
+    }
+
+    private boolean freeListContains(int blockNo) {
+      for (int i = 0; i < freeCount; ++i) {
+        if (freeList[i] == blockNo) return true;
+      }
+      return false;
+    }
+  }
+
+  public final class BucketSizeInfo {
+    // Free bucket means it has space to allocate a block;
+    // Completely free bucket means it has no block.
+    private List<Bucket> bucketList, freeBuckets, completelyFreeBuckets;
+    private int sizeIndex;
+
+    BucketSizeInfo(int sizeIndex) {
+      bucketList = new ArrayList<Bucket>();
+      freeBuckets = new ArrayList<Bucket>();
+      completelyFreeBuckets = new ArrayList<Bucket>();
+      this.sizeIndex = sizeIndex;
+    }
+
+    public void instantiateBucket(Bucket b) {
+      Preconditions.checkArgument(b.isUninstantiated() || b.isCompletelyFree());
+      b.reconfigure(sizeIndex);
+      bucketList.add(b);
+      freeBuckets.add(b);
+      completelyFreeBuckets.add(b);
+    }
+
+    public int sizeIndex() {
+      return sizeIndex;
+    }
+
+    /**
+     * Find a bucket to allocate a block
+     * @return the offset in the IOEngine
+     */
+    public long allocateBlock() {
+      Bucket b = null;
+      if (freeBuckets.size() > 0) // Use up an existing one first...
+        b = freeBuckets.get(freeBuckets.size() - 1);
+      if (b == null) {
+        b = grabGlobalCompletelyFreeBucket();
+        if (b != null) instantiateBucket(b);
+      }
+      if (b == null) return -1;
+      long result = b.allocate();
+      blockAllocated(b);
+      return result;
+    }
+
+    void blockAllocated(Bucket b) {
+      if (!b.isCompletelyFree()) completelyFreeBuckets.remove(b);
+      if (!b.hasFreeSpace()) freeBuckets.remove(b);
+    }
+
+    public Bucket findAndRemoveCompletelyFreeBucket() {
+      Bucket b = null;
+      Preconditions.checkState(bucketList.size() > 0);
+      if (bucketList.size() == 1) {
+        // So we never get complete starvation of a bucket for a size
+        return null;
+      }
+
+      if (completelyFreeBuckets.size() > 0) {
+        b = completelyFreeBuckets.get(0);
+        removeBucket(b);
+      }
+      return b;
+    }
+
+    private void removeBucket(Bucket b) {
+      Preconditions.checkArgument(b.isCompletelyFree());
+      bucketList.remove(b);
+      freeBuckets.remove(b);
+      completelyFreeBuckets.remove(b);
+    }
+
+    public void freeBlock(Bucket b, long offset) {
+      Preconditions.checkArgument(bucketList.contains(b));
+      // else we shouldn't have anything to free...
+      Preconditions.checkArgument(!completelyFreeBuckets.contains(b),
+          "nothing to free!");
+      b.free(offset);
+      if (!freeBuckets.contains(b)) freeBuckets.add(b);
+      if (b.isCompletelyFree()) completelyFreeBuckets.add(b);
+    }
+
+    public IndexStatistics statistics() {
+      long free = 0, used = 0;
+      for (Bucket b : bucketList) {
+        free += b.freeCount();
+        used += b.usedCount();
+      }
+      return new IndexStatistics(free, used, bucketSizes[sizeIndex]);
+    }
+  }
+
+  private final int bucketSizes[];
+
+  /**
+   * Round up the given block size to bucket size, and get the corresponding
+   * BucketSizeInfo
+   * @param blockSize
+   * @return BucketSizeInfo
+   */
+  public BucketSizeInfo roundUpToBucketSizeInfo(int blockSize) {
+    for (int i = 0; i < bucketSizes.length; ++i)
+      if (blockSize <= bucketSizes[i])
+        return bucketSizeInfos[i];
+    return null;
+  }
+
+
+  static public final int FEWEST_ITEMS_IN_BUCKET = 4;
+  // The capacity size for each bucket
+
+  private final long bucketCapacity;
+
+  private final Bucket[] buckets;
+  private final BucketSizeInfo[] bucketSizeInfos;
+  private final long totalSize;
+
+  private long usedSize = 0;
+
+  public BucketAllocator(int[] bucketSizes, long availableSpace) throws
+    BucketAllocatorException {
+    this.bucketSizes = bucketSizes;
+    int bigItemSize = bucketSizes[bucketSizes.length - 1];
+    bucketCapacity = FEWEST_ITEMS_IN_BUCKET * bigItemSize;
+    buckets = new Bucket[(int) (availableSpace / bucketCapacity)];
+    if (buckets.length < bucketSizes.length)
+      throw new BucketAllocatorException(
+          "Bucket allocator size too small - must have room for at least "
+              + bucketSizes.length + " buckets");
+    bucketSizeInfos = new BucketSizeInfo[bucketSizes.length];
+    for (int i = 0; i < bucketSizes.length; ++i) {
+      bucketSizeInfos[i] = new BucketSizeInfo(i);
+    }
+    for (int i = 0; i < buckets.length; ++i) {
+      buckets[i] = new Bucket(bucketSizes, bucketCapacity, bucketCapacity * i);
+      bucketSizeInfos[i < bucketSizes.length ? i : bucketSizes.length - 1]
+          .instantiateBucket(buckets[i]);
+    }
+    this.totalSize = ((long) buckets.length) * bucketCapacity;
+  }
+
+  public String getInfo() {
+    StringBuilder sb = new StringBuilder(1024);
+    for (int i = 0; i < buckets.length; ++i) {
+      Bucket b = buckets[i];
+      sb.append("    Bucket ").append(i).append(": ").append(b.itemAllocationSize());
+      sb.append(" freeCount=").append(b.freeCount()).append(" used=")
+          .append(b.usedCount());
+      sb.append('\n');
+    }
+    return sb.toString();
+  }
+
+  public long getUsedSize() {
+    return this.usedSize;
+  }
+
+  public long getFreeSize() {
+    return this.totalSize - getUsedSize();
+  }
+
+  public long getTotalSize() {
+    return this.totalSize;
+  }
+
+  /**
+   * Allocate a block with specified size. Return the offset
+   * @param blockSize size of block
+   * @throws BucketAllocatorException,org.apache.hadoop.hbase.io.hfile.bucket.CacheFullException
+   * @return the offset in the IOEngine
+   */
+  public synchronized long allocateBlock(int blockSize) throws
+    CacheFullException,
+      BucketAllocatorException {
+    Preconditions.checkArgument(blockSize > 0);
+    BucketSizeInfo bsi = roundUpToBucketSizeInfo(blockSize);
+    if (bsi == null) {
+      throw new BucketAllocatorException("Allocation too big size=" + blockSize);
+    }
+    long offset = bsi.allocateBlock();
+
+    // Ask caller to free up space and try again!
+    if (offset < 0)
+      throw new CacheFullException(blockSize, bsi.sizeIndex());
+    usedSize += bucketSizes[bsi.sizeIndex()];
+    return offset;
+  }
+
+  private Bucket grabGlobalCompletelyFreeBucket() {
+    for (BucketSizeInfo bsi : bucketSizeInfos) {
+      Bucket b = bsi.findAndRemoveCompletelyFreeBucket();
+      if (b != null) return b;
+    }
+    return null;
+  }
+
+  /**
+   * Free a block with the offset
+   * @param offset block's offset
+   * @return size freed
+   */
+  public synchronized int freeBlock(long offset) {
+    int bucketNo = (int) (offset / bucketCapacity);
+    Preconditions.checkPositionIndex(bucketNo, buckets.length);
+    Bucket targetBucket = buckets[bucketNo];
+    bucketSizeInfos[targetBucket.sizeIndex()].freeBlock(targetBucket, offset);
+    usedSize -= targetBucket.itemAllocationSize();
+    return targetBucket.itemAllocationSize();
+  }
+
+  public int sizeOfAllocation(long offset) {
+    int bucketNo = (int) (offset / bucketCapacity);
+    Preconditions.checkPositionIndex(bucketNo, buckets.length);
+    Bucket targetBucket = buckets[bucketNo];
+    return targetBucket.itemAllocationSize();
+  }
+
+  public static class IndexStatistics {
+    private long freeCount, usedCount, itemSize, totalCount;
+
+    public long freeCount() {
+      return freeCount;
+    }
+
+    public long usedCount() {
+      return usedCount;
+    }
+
+    public long totalCount() {
+      return totalCount;
+    }
+
+    public long freeBytes() {
+      return freeCount * itemSize;
+    }
+
+    public long usedBytes() {
+      return usedCount * itemSize;
+    }
+
+    public long totalBytes() {
+      return totalCount * itemSize;
+    }
+
+    public long itemSize() {
+      return itemSize;
+    }
+
+    public IndexStatistics(long free, long used, long itemSize) {
+      setTo(free, used, itemSize);
+    }
+
+    public IndexStatistics() {
+      setTo(-1, -1, 0);
+    }
+
+    public void setTo(long free, long used, long itemSize) {
+      this.itemSize = itemSize;
+      this.freeCount = free;
+      this.usedCount = used;
+      this.totalCount = free + used;
+    }
+  }
+
+  public void dumpToLog() {
+    logStatistics();
+    StringBuilder sb = new StringBuilder();
+    for (Bucket b : buckets) {
+      sb.append("Bucket:").append(b.baseOffset).append('\n');
+      sb.append("  Size index: " + b.sizeIndex() + "; Free:" + b.freeCount
+          + "; used:" + b.usedCount + "; freelist\n");
+      for (int i = 0; i < b.freeCount(); ++i)
+        sb.append(b.freeList[i]).append(',');
+      sb.append('\n');
+    }
+    LOG.info(sb);
+  }
+
+  public void logStatistics() {
+    IndexStatistics total = new IndexStatistics();
+    IndexStatistics[] stats = getIndexStatistics(total);
+    LOG.info("Bucket allocator statistics follow:\n");
+    LOG.info("  Free bytes=" + total.freeBytes() + "+; used bytes="
+        + total.usedBytes() + "; total bytes=" + total.totalBytes());
+    for (IndexStatistics s : stats) {
+      LOG.info("  Object size " + s.itemSize() + " used=" + s.usedCount()
+          + "; free=" + s.freeCount() + "; total=" + s.totalCount());
+    }
+  }
+
+  public IndexStatistics[] getIndexStatistics(IndexStatistics grandTotal) {
+    IndexStatistics[] stats = getIndexStatistics();
+    long totalfree = 0, totalused = 0;
+    for (IndexStatistics stat : stats) {
+      totalfree += stat.freeBytes();
+      totalused += stat.usedBytes();
+    }
+    grandTotal.setTo(totalfree, totalused, 1);
+    return stats;
+  }
+
+  public IndexStatistics[] getIndexStatistics() {
+    IndexStatistics[] stats = new IndexStatistics[bucketSizes.length];
+    for (int i = 0; i < stats.length; ++i)
+      stats[i] = bucketSizeInfos[i].statistics();
+    return stats;
+  }
+}
+

http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocatorException.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocatorException.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocatorException.java
new file mode 100644
index 0000000..932a64f
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/BucketAllocatorException.java
@@ -0,0 +1,34 @@
+/**
+ * Copyright The Apache Software Foundation
+ *
+ * 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.IOException;
+
+
+/**
+ * Thrown by {@link org.apache.hadoop.hbase.util.BucketAllocator}
+ */
+public class BucketAllocatorException extends IOException {
+  private static final long serialVersionUID = 2479119906660788096L;
+
+  BucketAllocatorException(String reason) {
+    super(reason);
+  }
+}
+

http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Bytes.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
new file mode 100644
index 0000000..2fdbb47
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Bytes.java
@@ -0,0 +1,1612 @@
+/**
+ * Copyright 2010 The Apache Software Foundation
+ *
+ * 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 com.facebook.swift.codec.ThriftCodec;
+import com.facebook.swift.codec.ThriftCodecManager;
+import org.apache.hadoop.hbase.HConstants;
+import org.apache.hadoop.hbase.io.ImmutableBytesWritable;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.io.RawComparator;
+import org.apache.hadoop.io.WritableComparator;
+import org.apache.hadoop.io.WritableUtils;
+import org.apache.thrift.protocol.TProtocol;
+import org.apache.thrift.transport.TMemoryBuffer;
+import org.apache.thrift.transport.TMemoryInputTransport;
+import org.apache.thrift.transport.TTransport;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.io.UnsupportedEncodingException;
+import java.math.BigInteger;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.Iterator;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.hbase.HConstants;
+import org.apache.hadoop.hbase.io.ImmutableBytesWritable;
+import org.apache.hadoop.io.RawComparator;
+import org.apache.hadoop.io.WritableComparator;
+import org.apache.hadoop.io.WritableUtils;
+
+/**
+ * Utility class that handles byte arrays, conversions to/from other types,
+ * comparisons, hash code generation, manufacturing keys for HashMaps or
+ * HashSets, etc.
+ */
+public class Bytes {
+
+  private static final Log LOG = LogFactory.getLog(Bytes.class);
+
+  /**
+   * Size of boolean in bytes
+   */
+  public static final int SIZEOF_BOOLEAN = Byte.SIZE / Byte.SIZE;
+
+  /**
+   * Size of byte in bytes
+   */
+  public static final int SIZEOF_BYTE = SIZEOF_BOOLEAN;
+
+  /**
+   * Size of char in bytes
+   */
+  public static final int SIZEOF_CHAR = Character.SIZE / Byte.SIZE;
+
+  /**
+   * Size of double in bytes
+   */
+  public static final int SIZEOF_DOUBLE = Double.SIZE / Byte.SIZE;
+
+  /**
+   * Size of float in bytes
+   */
+  public static final int SIZEOF_FLOAT = Float.SIZE / Byte.SIZE;
+
+  /**
+   * Size of int in bytes
+   */
+  public static final int SIZEOF_INT = Integer.SIZE / Byte.SIZE;
+
+  /**
+   * Size of long in bytes
+   */
+  public static final int SIZEOF_LONG = Long.SIZE / Byte.SIZE;
+
+  /**
+   * Size of short in bytes
+   */
+  public static final int SIZEOF_SHORT = Short.SIZE / Byte.SIZE;
+
+
+  /**
+   * Estimate of size cost to pay beyond payload in jvm for instance of byte [].
+   * Estimate based on study of jhat and jprofiler numbers.
+   */
+  // JHat says BU is 56 bytes.
+  // SizeOf which uses java.lang.instrument says 24 bytes. (3 longs?)
+  public static final int ESTIMATED_HEAP_TAX = 16;
+
+  /**
+   * Byte array comparator class.
+   */
+  public static class ByteArrayComparator implements RawComparator<byte []> {
+    /**
+     * Constructor
+     */
+    public ByteArrayComparator() {
+      super();
+    }
+    @Override
+    public int compare(byte [] left, byte [] right) {
+      return compareTo(left, right);
+    }
+    @Override
+    public int compare(byte [] b1, int s1, int l1, byte [] b2, int s2, int l2) {
+      return compareTo(b1, s1, l1, b2, s2, l2);
+    }
+  }
+
+  /**
+   * Pass this to TreeMaps where byte [] are keys.
+   */
+  public static final Comparator<byte []> BYTES_COMPARATOR =
+    new ByteArrayComparator();
+
+  /**
+   * Use comparing byte arrays, byte-by-byte
+   */
+  public static final RawComparator<byte []> BYTES_RAWCOMPARATOR =
+    new ByteArrayComparator();
+
+  public static final Comparator<ByteBuffer> BYTE_BUFFER_COMPARATOR =
+      new Comparator<ByteBuffer>() {
+        @Override
+        public int compare(ByteBuffer left, ByteBuffer right) {
+          int lpos = left.position();
+          int rpos = right.position();
+          return compareTo(left.array(), left.arrayOffset() + lpos, left.limit() - lpos,
+              right.array(), right.arrayOffset() + rpos, right.limit() - rpos);
+        }
+      };
+
+  public static final ThriftCodecManager THRIFT_CODEC_MANAGER =
+    new ThriftCodecManager();
+
+  /**
+   * Read byte-array written with a WritableableUtils.vint prefix.
+   * @param in Input to read from.
+   * @return byte array read off <code>in</code>
+   * @throws IOException e
+   */
+  public static byte [] readByteArray(final DataInput in)
+  throws IOException {
+    int len = WritableUtils.readVInt(in);
+    if (len < 0) {
+      throw new NegativeArraySizeException(Integer.toString(len));
+    }
+    byte [] result = new byte[len];
+    in.readFully(result, 0, len);
+    return result;
+  }
+
+  /**
+   * Read byte-array written with a WritableableUtils.vint prefix.
+   * IOException is converted to a RuntimeException.
+   * @param in Input to read from.
+   * @return byte array read off <code>in</code>
+   */
+  public static byte [] readByteArrayThrowsRuntime(final DataInput in) {
+    try {
+      return readByteArray(in);
+    } catch (Exception e) {
+      throw new RuntimeException(e);
+    }
+  }
+
+  /**
+   * Write byte-array with a WritableableUtils.vint prefix.
+   * @param out output stream to be written to
+   * @param b array to write
+   * @throws IOException e
+   */
+  public static void writeByteArray(final DataOutput out, final byte [] b)
+  throws IOException {
+    if(b == null) {
+      WritableUtils.writeVInt(out, 0);
+    } else {
+      writeByteArray(out, b, 0, b.length);
+    }
+  }
+
+  /**
+   * Write byte-array to out with a vint length prefix.
+   * @param out output stream
+   * @param b array
+   * @param offset offset into array
+   * @param length length past offset
+   * @throws IOException e
+   */
+  public static void writeByteArray(final DataOutput out, final byte [] b,
+      final int offset, final int length)
+  throws IOException {
+    WritableUtils.writeVInt(out, length);
+    out.write(b, offset, length);
+  }
+
+  /**
+   * Write byte-array from src to tgt with a vint length prefix.
+   * @param tgt target array
+   * @param tgtOffset offset into target array
+   * @param src source array
+   * @param srcOffset source offset
+   * @param srcLength source length
+   * @return New offset in src array.
+   */
+  public static int writeByteArray(final byte [] tgt, final int tgtOffset,
+      final byte [] src, final int srcOffset, final int srcLength) {
+    byte [] vint = vintToBytes(srcLength);
+    System.arraycopy(vint, 0, tgt, tgtOffset, vint.length);
+    int offset = tgtOffset + vint.length;
+    System.arraycopy(src, srcOffset, tgt, offset, srcLength);
+    return offset + srcLength;
+  }
+
+  /**
+   * Put bytes at the specified byte array position.
+   * @param tgtBytes the byte array
+   * @param tgtOffset position in the array
+   * @param srcBytes array to write out
+   * @param srcOffset source offset
+   * @param srcLength source length
+   * @return incremented offset
+   */
+  public static int putBytes(byte[] tgtBytes, int tgtOffset, byte[] srcBytes,
+      int srcOffset, int srcLength) {
+    System.arraycopy(srcBytes, srcOffset, tgtBytes, tgtOffset, srcLength);
+    return tgtOffset + srcLength;
+  }
+
+  /**
+   * Write a single byte out to the specified byte array position.
+   * @param bytes the byte array
+   * @param offset position in the array
+   * @param b byte to write out
+   * @return incremented offset
+   */
+  public static int putByte(byte[] bytes, int offset, byte b) {
+    bytes[offset] = b;
+    return offset + 1;
+  }
+
+  /**
+   * Returns a new byte array, copied from the passed ByteBuffer. Starts from the array offset
+   * of the buffer and copies bytes to the limit of the buffer.
+   * @param bb A ByteBuffer
+   * @return the byte array
+   */
+  public static byte[] toBytes(ByteBuffer bb) {
+    int length = bb.limit();
+    byte [] result = new byte[length];
+    System.arraycopy(bb.array(), bb.arrayOffset(), result, 0, length);
+    return result;
+  }
+
+  /**
+   * Returns a new byte array, copied from the passed ByteBuffer. Starts from the current position
+   * in the buffer and copies all the remaining bytes to the limit of the buffer.
+   * @param bb A ByteBuffer
+   * @return the byte array
+   */
+  public static byte[] toBytesRemaining(ByteBuffer bb) {
+    int length = bb.remaining();
+    byte [] result = new byte[length];
+    System.arraycopy(bb.array(), bb.arrayOffset() + bb.position(), result, 0, length);
+    return result;
+  }
+
+  /**
+   * @param b Presumed UTF-8 encoded byte array.
+   * @return String made from <code>b</code>
+   */
+  public static String toString(final byte [] b) {
+    if (b == null) {
+      return null;
+    }
+    return toString(b, 0, b.length);
+  }
+
+  /**
+   * Joins two byte arrays together using a separator.
+   * @param b1 The first byte array.
+   * @param sep The separator to use.
+   * @param b2 The second byte array.
+   */
+  public static String toString(final byte [] b1,
+                                String sep,
+                                final byte [] b2) {
+    return toString(b1, 0, b1.length) + sep + toString(b2, 0, b2.length);
+  }
+
+  /**
+   * This method will convert utf8 encoded bytes into a string. If
+   * an UnsupportedEncodingException occurs, this method will eat it
+   * and return null instead.
+   *
+   * @param b Presumed UTF-8 encoded byte array.
+   * @param off offset into array
+   * @param len length of utf-8 sequence
+   * @return String made from <code>b</code> or null
+   */
+  public static String toString(final byte [] b, int off, int len) {
+    if (b == null) {
+      return null;
+    }
+    if (len == 0) {
+      return "";
+    }
+    try {
+      return new String(b, off, len, HConstants.UTF8_ENCODING);
+    } catch (UnsupportedEncodingException e) {
+      LOG.error("UTF-8 not supported?", e);
+      return null;
+    }
+  }
+
+  /**
+   * Write a printable representation of a byte array.
+   *
+   * @param b byte array
+   * @return string
+   * @see #toStringBinary(byte[], int, int)
+   */
+  public static String toStringBinary(final byte [] b) {
+    if (b == null)
+      return "null";
+    return toStringBinary(b, 0, b.length);
+  }
+
+  /**
+   * Converts the given byte buffer, from its array offset to its limit, to
+   * a string. The position and the mark are ignored.
+   *
+   * @param buf a byte buffer
+   * @return a string representation of the buffer's binary contents
+   */
+  public static String toStringBinary(ByteBuffer buf) {
+    if (buf == null)
+      return "null";
+    return toStringBinary(buf.array(), buf.arrayOffset(), buf.limit());
+  }
+
+  /**
+   * Similar to {@link #toStringBinary(byte[])}, but converts the portion of the buffer from the
+   * current position to the limit to string.
+   *
+   * @param buf a byte buffer
+   * @return a string representation of the buffer's remaining contents
+   */
+  public static String toStringBinaryRemaining(ByteBuffer buf) {
+    if (buf == null) {
+      return "null";
+    }
+    int offset = buf.arrayOffset();
+    int pos = buf.position();
+    return toStringBinary(buf.array(), offset + pos, buf.limit() - pos);
+  }
+
+  /**
+   * Write a printable representation of a byte array. Non-printable
+   * characters are hex escaped in the format \\x%02X, eg:
+   * \x00 \x05 etc
+   *
+   * @param b array to write out
+   * @param off offset to start at
+   * @param len length to write
+   * @return string output
+   */
+  public static String toStringBinary(final byte [] b, int off, int len) {
+    StringBuilder result = new StringBuilder();
+    try {
+      String first = new String(b, off, len, "ISO-8859-1");
+      for (int i = 0; i < first.length() ; ++i ) {
+        int ch = first.charAt(i) & 0xFF;
+        if ( (ch >= '0' && ch <= '9')
+            || (ch >= 'A' && ch <= 'Z')
+            || (ch >= 'a' && ch <= 'z')
+            || " `~!@#$%^&*()-_=+[]{}\\|;:'\",.<>/?".indexOf(ch) >= 0 ) {
+          result.append(first.charAt(i));
+        } else {
+          result.append(String.format("\\x%02X", ch));
+        }
+      }
+    } catch (UnsupportedEncodingException e) {
+      LOG.error("ISO-8859-1 not supported?", e);
+    }
+    return result.toString();
+  }
+
+  private static boolean isHexDigit(char c) {
+    return
+        (c >= 'A' && c <= 'F') ||
+        (c >= '0' && c <= '9');
+  }
+
+  /**
+   * Takes a ASCII digit in the range A-F0-9 and returns
+   * the corresponding integer/ordinal value.
+   * @param ch  The hex digit.
+   * @return The converted hex value as a byte.
+   */
+  public static byte toBinaryFromHex(byte ch) {
+    if ( ch >= 'A' && ch <= 'F' )
+      return (byte) ((byte)10 + (byte) (ch - 'A'));
+    // else
+    return (byte) (ch - '0');
+  }
+
+  public static byte [] toBytesBinary(String in) {
+    // this may be bigger than we need, but lets be safe.
+    byte [] b = new byte[in.length()];
+    int size = 0;
+    for (int i = 0; i < in.length(); ++i) {
+      char ch = in.charAt(i);
+      if (ch == '\\') {
+        // begin hex escape:
+        char next = in.charAt(i+1);
+        if (next != 'x') {
+          // invalid escape sequence, ignore this one.
+          b[size++] = (byte)ch;
+          continue;
+        }
+        // ok, take next 2 hex digits.
+        char hd1 = in.charAt(i+2);
+        char hd2 = in.charAt(i+3);
+
+        // they need to be A-F0-9:
+        if (!isHexDigit(hd1) ||
+            !isHexDigit(hd2)) {
+          // bogus escape code, ignore:
+          continue;
+        }
+        // turn hex ASCII digit -> number
+        byte d = (byte) ((toBinaryFromHex((byte)hd1) << 4) + toBinaryFromHex((byte)hd2));
+
+        b[size++] = d;
+        i += 3; // skip 3
+      } else {
+        b[size++] = (byte) ch;
+      }
+    }
+    // resize:
+    byte [] b2 = new byte[size];
+    System.arraycopy(b, 0, b2, 0, size);
+    return b2;
+  }
+
+  /**
+   * Converts a string to a UTF-8 byte array.
+   * @param s string
+   * @return the byte array
+   */
+  public static byte[] toBytes(String s) {
+    try {
+      return s.getBytes(HConstants.UTF8_ENCODING);
+    } catch (UnsupportedEncodingException e) {
+      LOG.error("UTF-8 not supported?", e);
+      return null;
+    }
+  }
+
+  /**
+   * Convert a boolean to a byte array. True becomes -1
+   * and false becomes 0.
+   *
+   * @param b value
+   * @return <code>b</code> encoded in a byte array.
+   */
+  public static byte [] toBytes(final boolean b) {
+    return new byte[] { b ? (byte) -1 : (byte) 0 };
+  }
+
+  /**
+   * Reverses {@link #toBytes(boolean)}
+   * @param b array
+   * @return True or false.
+   */
+  public static boolean toBoolean(final byte [] b) {
+    if (b.length != 1) {
+      throw new IllegalArgumentException("Array has wrong size: " + b.length);
+    }
+    return b[0] != (byte) 0;
+  }
+
+  /**
+   * Convert a long value to a byte array using big-endian.
+   *
+   * @param val value to convert
+   * @return the byte array
+   */
+  public static byte[] toBytes(long val) {
+    byte [] b = new byte[8];
+    for (int i = 7; i > 0; i--) {
+      b[i] = (byte) val;
+      val >>>= 8;
+    }
+    b[0] = (byte) val;
+    return b;
+  }
+
+  /**
+   * Converts a byte array to a long value. Reverses
+   * {@link #toBytes(long)}
+   * @param bytes array
+   * @return the long value
+   */
+  public static long toLong(byte[] bytes) {
+    return toLong(bytes, 0, SIZEOF_LONG);
+  }
+
+  /**
+   * Converts a byte array to a long value. Assumes there will be
+   * {@link #SIZEOF_LONG} bytes available.
+   *
+   * @param bytes bytes
+   * @param offset offset
+   * @return the long value
+   */
+  public static long toLong(byte[] bytes, int offset) {
+    return toLong(bytes, offset, SIZEOF_LONG);
+  }
+
+  /**
+   * Converts a byte array to a long value.
+   *
+   * @param bytes array of bytes
+   * @param offset offset into array
+   * @param length length of data (must be {@link #SIZEOF_LONG})
+   * @return the long value
+   * @throws IllegalArgumentException if length is not {@link #SIZEOF_LONG} or
+   * if there's not enough room in the array at the offset indicated.
+   */
+  public static long toLong(byte[] bytes, int offset, final int length) {
+    if (length != SIZEOF_LONG || offset + length > bytes.length) {
+      throw explainWrongLengthOrOffset(bytes, offset, length, SIZEOF_LONG);
+    }
+    long l = 0;
+    for(int i = offset; i < offset + length; i++) {
+      l <<= 8;
+      l ^= bytes[i] & 0xFF;
+    }
+    return l;
+  }
+
+  private static IllegalArgumentException
+    explainWrongLengthOrOffset(final byte[] bytes,
+                               final int offset,
+                               final int length,
+                               final int expectedLength) {
+    String reason;
+    if (length != expectedLength) {
+      reason = "Wrong length: " + length + ", expected " + expectedLength;
+    } else {
+     reason = "offset (" + offset + ") + length (" + length + ") exceed the"
+        + " capacity of the array: " + bytes.length;
+    }
+    return new IllegalArgumentException(reason);
+  }
+
+  /**
+   * Put a long value out to the specified byte array position.
+   * @param bytes the byte array
+   * @param offset position in the array
+   * @param val long to write out
+   * @return incremented offset
+   * @throws IllegalArgumentException if the byte array given doesn't have
+   * enough room at the offset specified.
+   */
+  public static int putLong(byte[] bytes, int offset, long val) {
+    if (bytes.length - offset < SIZEOF_LONG) {
+      throw new IllegalArgumentException("Not enough room to put a long at"
+          + " offset " + offset + " in a " + bytes.length + " byte array");
+    }
+    for(int i = offset + 7; i > offset; i--) {
+      bytes[i] = (byte) val;
+      val >>>= 8;
+    }
+    bytes[offset] = (byte) val;
+    return offset + SIZEOF_LONG;
+  }
+
+  /**
+   * Presumes float encoded as IEEE 754 floating-point "single format"
+   * @param bytes byte array
+   * @return Float made from passed byte array.
+   */
+  public static float toFloat(byte [] bytes) {
+    return toFloat(bytes, 0);
+  }
+
+  /**
+   * Presumes float encoded as IEEE 754 floating-point "single format"
+   * @param bytes array to convert
+   * @param offset offset into array
+   * @return Float made from passed byte array.
+   */
+  public static float toFloat(byte [] bytes, int offset) {
+    return Float.intBitsToFloat(toInt(bytes, offset, SIZEOF_INT));
+  }
+
+  /**
+   * @param bytes byte array
+   * @param offset offset to write to
+   * @param f float value
+   * @return New offset in <code>bytes</code>
+   */
+  public static int putFloat(byte [] bytes, int offset, float f) {
+    return putInt(bytes, offset, Float.floatToRawIntBits(f));
+  }
+
+  /**
+   * @param f float value
+   * @return the float represented as byte []
+   */
+  public static byte [] toBytes(final float f) {
+    // Encode it as int
+    return Bytes.toBytes(Float.floatToRawIntBits(f));
+  }
+
+  /**
+   * @param bytes byte array
+   * @return Return double made from passed bytes.
+   */
+  public static double toDouble(final byte [] bytes) {
+    return toDouble(bytes, 0);
+  }
+
+  /**
+   * @param bytes byte array
+   * @param offset offset where double is
+   * @return Return double made from passed bytes.
+   */
+  public static double toDouble(final byte [] bytes, final int offset) {
+    return Double.longBitsToDouble(toLong(bytes, offset, SIZEOF_LONG));
+  }
+
+  /**
+   * @param bytes byte array
+   * @param offset offset to write to
+   * @param d value
+   * @return New offset into array <code>bytes</code>
+   */
+  public static int putDouble(byte [] bytes, int offset, double d) {
+    return putLong(bytes, offset, Double.doubleToLongBits(d));
+  }
+
+  /**
+   * Serialize a double as the IEEE 754 double format output. The resultant
+   * array will be 8 bytes long.
+   *
+   * @param d value
+   * @return the double represented as byte []
+   */
+  public static byte [] toBytes(final double d) {
+    // Encode it as a long
+    return Bytes.toBytes(Double.doubleToRawLongBits(d));
+  }
+
+  /**
+   * Convert an int value to a byte array
+   * @param val value
+   * @return the byte array
+   */
+  public static byte[] toBytes(int val) {
+    byte [] b = new byte[4];
+    for(int i = 3; i > 0; i--) {
+      b[i] = (byte) val;
+      val >>>= 8;
+    }
+    b[0] = (byte) val;
+    return b;
+  }
+
+  /**
+   * Converts a byte array to an int value
+   * @param bytes byte array
+   * @return the int value
+   */
+  public static int toInt(byte[] bytes) {
+    return toInt(bytes, 0, SIZEOF_INT);
+  }
+
+  /**
+   * Converts a byte array to an int value
+   * @param bytes byte array
+   * @param offset offset into array
+   * @return the int value
+   */
+  public static int toInt(byte[] bytes, int offset) {
+    return toInt(bytes, offset, SIZEOF_INT);
+  }
+
+  /**
+   * Converts a byte array to an int value
+   * @param bytes byte array
+   * @param offset offset into array
+   * @param length length of int (has to be {@link #SIZEOF_INT})
+   * @return the int value
+   * @throws IllegalArgumentException if length is not {@link #SIZEOF_INT} or
+   * if there's not enough room in the array at the offset indicated.
+   */
+  public static int toInt(byte[] bytes, int offset, final int length) {
+    if (length != SIZEOF_INT || offset + length > bytes.length) {
+      throw explainWrongLengthOrOffset(bytes, offset, length, SIZEOF_INT);
+    }
+    int n = 0;
+    for(int i = offset; i < (offset + length); i++) {
+      n <<= 8;
+      n ^= bytes[i] & 0xFF;
+    }
+    return n;
+  }
+
+  /**
+   * Put an int value out to the specified byte array position.
+   * @param bytes the byte array
+   * @param offset position in the array
+   * @param val int to write out
+   * @return incremented offset
+   * @throws IllegalArgumentException if the byte array given doesn't have
+   * enough room at the offset specified.
+   */
+  public static int putInt(byte[] bytes, int offset, int val) {
+    if (bytes.length - offset < SIZEOF_INT) {
+      throw new IllegalArgumentException("Not enough room to put an int at"
+          + " offset " + offset + " in a " + bytes.length + " byte array");
+    }
+    for(int i= offset + 3; i > offset; i--) {
+      bytes[i] = (byte) val;
+      val >>>= 8;
+    }
+    bytes[offset] = (byte) val;
+    return offset + SIZEOF_INT;
+  }
+
+  /**
+   * Convert a short value to a byte array of {@link #SIZEOF_SHORT} bytes long.
+   * @param val value
+   * @return the byte array
+   */
+  public static byte[] toBytes(short val) {
+    byte[] b = new byte[SIZEOF_SHORT];
+    b[1] = (byte) val;
+    val >>= 8;
+    b[0] = (byte) val;
+    return b;
+  }
+
+  /**
+   * Converts a byte array to a short value
+   * @param bytes byte array
+   * @return the short value
+   */
+  public static short toShort(byte[] bytes) {
+    return toShort(bytes, 0, SIZEOF_SHORT);
+  }
+
+  /**
+   * Converts a byte array to a short value
+   * @param bytes byte array
+   * @param offset offset into array
+   * @return the short value
+   */
+  public static short toShort(byte[] bytes, int offset) {
+    return toShort(bytes, offset, SIZEOF_SHORT);
+  }
+
+  /**
+   * Converts a byte array to a short value
+   * @param bytes byte array
+   * @param offset offset into array
+   * @param length length, has to be {@link #SIZEOF_SHORT}
+   * @return the short value
+   * @throws IllegalArgumentException if length is not {@link #SIZEOF_SHORT}
+   * or if there's not enough room in the array at the offset indicated.
+   */
+  public static short toShort(byte[] bytes, int offset, final int length) {
+    if (length != SIZEOF_SHORT || offset + length > bytes.length) {
+      throw explainWrongLengthOrOffset(bytes, offset, length, SIZEOF_SHORT);
+    }
+    short n = 0;
+    n ^= bytes[offset] & 0xFF;
+    n <<= 8;
+    n ^= bytes[offset+1] & 0xFF;
+    return n;
+  }
+
+  public static byte[] getBytes(ByteBuffer buf) {
+    if (buf == null) {
+      return HConstants.EMPTY_BYTE_ARRAY;
+    }
+
+    if (buf.arrayOffset() == 0 && buf.position() == 0) {
+      byte[] arr = buf.array();
+      if (buf.limit() == arr.length) {
+        // We already have the exact array we need, just return it.
+        return arr;
+      }
+    }
+
+    int savedPos = buf.position();
+    byte [] newBytes = new byte[buf.remaining()];
+    buf.get(newBytes);
+    buf.position(savedPos);
+    return newBytes;
+  }
+
+  /**
+   * Put a short value out to the specified byte array position.
+   * @param bytes the byte array
+   * @param offset position in the array
+   * @param val short to write out
+   * @return incremented offset
+   * @throws IllegalArgumentException if the byte array given doesn't have
+   * enough room at the offset specified.
+   */
+  public static int putShort(byte[] bytes, int offset, short val) {
+    if (bytes.length - offset < SIZEOF_SHORT) {
+      throw new IllegalArgumentException("Not enough room to put a short at"
+          + " offset " + offset + " in a " + bytes.length + " byte array");
+    }
+    bytes[offset+1] = (byte) val;
+    val >>= 8;
+    bytes[offset] = (byte) val;
+    return offset + SIZEOF_SHORT;
+  }
+
+  /**
+   * @param vint Integer to make a vint of.
+   * @return Vint as bytes array.
+   */
+  public static byte [] vintToBytes(final long vint) {
+    long i = vint;
+    int size = WritableUtils.getVIntSize(i);
+    byte [] result = new byte[size];
+    int offset = 0;
+    if (i >= -112 && i <= 127) {
+      result[offset] = (byte) i;
+      return result;
+    }
+
+    int len = -112;
+    if (i < 0) {
+      i ^= -1L; // take one's complement'
+      len = -120;
+    }
+
+    long tmp = i;
+    while (tmp != 0) {
+      tmp = tmp >> 8;
+      len--;
+    }
+
+    result[offset++] = (byte) len;
+
+    len = (len < -120) ? -(len + 120) : -(len + 112);
+
+    for (int idx = len; idx != 0; idx--) {
+      int shiftbits = (idx - 1) * 8;
+      long mask = 0xFFL << shiftbits;
+      result[offset++] = (byte)((i & mask) >> shiftbits);
+    }
+    return result;
+  }
+
+  /**
+   * @param buffer buffer to convert
+   * @return vint bytes as an integer.
+   */
+  public static long bytesToVint(final byte [] buffer) {
+    int offset = 0;
+    byte firstByte = buffer[offset++];
+    int len = WritableUtils.decodeVIntSize(firstByte);
+    if (len == 1) {
+      return firstByte;
+    }
+    long i = 0;
+    for (int idx = 0; idx < len-1; idx++) {
+      byte b = buffer[offset++];
+      i = i << 8;
+      i = i | (b & 0xFF);
+    }
+    return (WritableUtils.isNegativeVInt(firstByte) ? ~i : i);
+  }
+
+  /**
+   * Reads a zero-compressed encoded long from input stream and returns it.
+   * @param buffer Binary array
+   * @param offset Offset into array at which vint begins.
+   * @throws java.io.IOException e
+   * @return deserialized long from stream.
+   */
+  public static long readVLong(final byte [] buffer, final int offset)
+  throws IOException {
+    byte firstByte = buffer[offset];
+    int len = WritableUtils.decodeVIntSize(firstByte);
+    if (len == 1) {
+      return firstByte;
+    }
+    long i = 0;
+    for (int idx = 0; idx < len-1; idx++) {
+      byte b = buffer[offset + 1 + idx];
+      i = i << 8;
+      i = i | (b & 0xFF);
+    }
+    return (WritableUtils.isNegativeVInt(firstByte) ? ~i : i);
+  }
+
+  /**
+   * @param left left operand
+   * @param right right operand
+   * @return 0 if equal, < 0 if left is less than right, etc.
+   */
+  public static int compareTo(final byte [] left, final byte [] right) {
+    return compareTo(left, 0, left.length, right, 0, right.length);
+  }
+
+  /**
+   * Lexographically compare two arrays.
+   *
+   * @param buffer1 left operand
+   * @param buffer2 right operand
+   * @param offset1 Where to start comparing in the left buffer
+   * @param offset2 Where to start comparing in the right buffer
+   * @param length1 How much to compare from the left buffer
+   * @param length2 How much to compare from the right buffer
+   * @return 0 if equal, < 0 if left is less than right, etc.
+   */
+  public static int compareTo(byte[] buffer1, int offset1, int length1,
+      byte[] buffer2, int offset2, int length2) {
+    // Bring WritableComparator code local
+    int end1 = offset1 + length1;
+    int end2 = offset2 + length2;
+    for (int i = offset1, j = offset2; i < end1 && j < end2; i++, j++) {
+      int a = (buffer1[i] & 0xff);
+      int b = (buffer2[j] & 0xff);
+      if (a != b) {
+        return a - b;
+      }
+    }
+    return length1 - length2;
+  }
+
+  /**
+   * @param left left operand
+   * @param right right operand
+   * @return True if equal
+   */
+  public static boolean equals(final byte [] left, final byte [] right) {
+    // Could use Arrays.equals?
+    //noinspection SimplifiableConditionalExpression
+    if (left == null && right == null) {
+      return true;
+    }
+    return (left == null || right == null || (left.length != right.length)
+            ? false : compareTo(left, right) == 0);
+  }
+
+  public static boolean equals(final byte[] left, int leftOffset, int leftLength,
+      final byte[] right, int rightOffset, int rightLength) {
+    if (left == null && right == null) {
+      return true;
+    }
+    return (left == null || right == null || (leftLength != rightLength) ? false : compareTo(left,
+        leftOffset, leftLength, right, rightOffset, rightLength) == 0);
+  }
+
+  /**
+   * Return true if the byte array on the right is a prefix of the byte
+   * array on the left.
+   */
+  public static boolean startsWith(byte[] bytes, byte[] prefix) {
+    return bytes != null && prefix != null &&
+      bytes.length >= prefix.length &&
+      compareTo(bytes, 0, prefix.length, prefix, 0, prefix.length) == 0;
+  }
+
+  /**
+   * @param b bytes to hash
+   * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the
+   * passed in array.  This method is what {@link org.apache.hadoop.io.Text} and
+   * {@link ImmutableBytesWritable} use calculating hash code.
+   */
+  public static int hashCode(final byte [] b) {
+    return hashCode(b, b.length);
+  }
+
+  /**
+   * @param b value
+   * @param length length of the value
+   * @return Runs {@link WritableComparator#hashBytes(byte[], int)} on the
+   * passed in array.  This method is what {@link org.apache.hadoop.io.Text} and
+   * {@link ImmutableBytesWritable} use calculating hash code.
+   */
+  public static int hashCode(final byte [] b, final int length) {
+    return WritableComparator.hashBytes(b, length);
+  }
+
+  /**
+   * @param b bytes to hash
+   * @return A hash of <code>b</code> as an Integer that can be used as key in
+   * Maps.
+   */
+  public static Integer mapKey(final byte [] b) {
+    return hashCode(b);
+  }
+
+  /**
+   * @param b bytes to hash
+   * @param length length to hash
+   * @return A hash of <code>b</code> as an Integer that can be used as key in
+   * Maps.
+   */
+  public static Integer mapKey(final byte [] b, final int length) {
+    return hashCode(b, length);
+  }
+
+  /**
+   * @param a lower half
+   * @param b upper half
+   * @return New array that has a in lower half and b in upper half.
+   */
+  public static byte [] add(final byte [] a, final byte [] b) {
+    return add(a, b, HConstants.EMPTY_BYTE_ARRAY);
+  }
+
+  /**
+   * @param a first third
+   * @param b second third
+   * @param c third third
+   * @return New array made from a, b and c
+   */
+  public static byte [] add(final byte [] a, final byte [] b, final byte [] c) {
+    byte [] result = new byte[a.length + b.length + c.length];
+    System.arraycopy(a, 0, result, 0, a.length);
+    System.arraycopy(b, 0, result, a.length, b.length);
+    System.arraycopy(c, 0, result, a.length + b.length, c.length);
+    return result;
+  }
+
+  /**
+   * @param a first third
+   * @param b second third
+   * @param c third third
+   * @return New array made from a, b and c
+   */
+  public static byte [] add(final byte [] a, int aOffset, int aLength,
+      final byte [] b, int bOffset, int bLength,
+      final byte [] c, int cOffset, int cLength) {
+    byte [] result = new byte[aLength + bLength + cLength];
+    System.arraycopy(a, aOffset, result, 0, aLength);
+    System.arraycopy(b, bOffset, result, aLength, bLength);
+    System.arraycopy(c, cOffset, result, aLength + bLength, cLength);
+    return result;
+  }
+
+  /**
+   * @param a array
+   * @param length amount of bytes to grab
+   * @return First <code>length</code> bytes from <code>a</code>
+   */
+  public static byte [] head(final byte [] a, final int length) {
+    if (a.length < length) {
+      return null;
+    }
+    byte [] result = new byte[length];
+    System.arraycopy(a, 0, result, 0, length);
+    return result;
+  }
+
+  /**
+   * @param a array
+   * @param length amount of bytes to snarf
+   * @return Last <code>length</code> bytes from <code>a</code>
+   */
+  public static byte [] tail(final byte [] a, final int length) {
+    if (a.length < length) {
+      return null;
+    }
+    byte [] result = new byte[length];
+    System.arraycopy(a, a.length - length, result, 0, length);
+    return result;
+  }
+
+  /**
+   * @param a array
+   * @param length new array size
+   * @return Value in <code>a</code> plus <code>length</code> prepended 0 bytes
+   */
+  public static byte [] padHead(final byte [] a, final int length) {
+    byte [] padding = new byte[length];
+    for (int i = 0; i < length; i++) {
+      padding[i] = 0;
+    }
+    return add(padding,a);
+  }
+
+  /**
+   * @param a array
+   * @param length new array size
+   * @return Value in <code>a</code> plus <code>length</code> appended 0 bytes
+   */
+  public static byte [] padTail(final byte [] a, final int length) {
+    return appendToTail(a, length, (byte)0);
+  }
+
+  /**
+   * Appends length bytes to the end of the array and returns the new array
+   * Fills byte b in the newly allocated space in the byte[].
+   * @param a array
+   * @param length new array size
+   * @param b byte to write to the tail.
+   * @return Value in <code>a</code> plus <code>length</code> appended 0 bytes
+   */
+  public static byte [] appendToTail(final byte [] a, final int length, byte b)
+  {
+    byte [] padding = new byte[length];
+    for (int i = 0; i < length; i++) {
+      padding[i] = b;
+    }
+    return add(a,padding);
+  }
+
+  /**
+   * Split passed range.  Expensive operation relatively.  Uses BigInteger math.
+   * Useful splitting ranges for MapReduce jobs.
+   * @param a Beginning of range
+   * @param b End of range
+   * @param num Number of times to split range.  Pass 1 if you want to split
+   * the range in two; i.e. one split.
+   * @return Array of dividing values
+   */
+  public static byte [][] split(final byte [] a, final byte [] b, final int num) {
+    return split(a, b, false, num);
+  }
+
+  /**
+   * Split passed range.  Expensive operation relatively.  Uses BigInteger math.
+   * Useful splitting ranges for MapReduce jobs.
+   * @param a Beginning of range
+   * @param b End of range
+   * @param inclusive Whether the end of range is prefix-inclusive or is
+   * considered an exclusive boundary.  Automatic splits are generally exclusive
+   * and manual splits with an explicit range utilize an inclusive end of range.
+   * @param num Number of times to split range.  Pass 1 if you want to split
+   * the range in two; i.e. one split.
+   * @return Array of dividing values
+   */
+  public static byte[][] split(final byte[] a, final byte[] b,
+      boolean inclusive, final int num) {
+    byte[][] ret = new byte[num + 2][];
+    int i = 0;
+    Iterable<byte[]> iter = iterateOnSplits(a, b, inclusive, num);
+    if (iter == null)
+      return null;
+    for (byte[] elem : iter) {
+      ret[i++] = elem;
+    }
+    return ret;
+  }
+
+  /**
+   * Iterate over keys within the passed range, splitting at an [a,b) boundary.
+   */
+  public static Iterable<byte[]> iterateOnSplits(final byte[] a,
+      final byte[] b, final int num)
+  {
+    return iterateOnSplits(a, b, false, num);
+  }
+
+  /**
+   * Iterate over keys within the passed range.
+   */
+  public static Iterable<byte[]> iterateOnSplits(
+      final byte[] a, final byte[]b, boolean inclusive, final int num)
+  {
+    byte [] aPadded;
+    byte [] bPadded;
+    if (a.length < b.length) {
+      aPadded = padTail(a, b.length - a.length);
+      bPadded = b;
+    } else if (b.length < a.length) {
+      aPadded = a;
+      bPadded = padTail(b, a.length - b.length);
+    } else {
+      aPadded = a;
+      bPadded = b;
+    }
+    if (compareTo(aPadded,bPadded) >= 0) {
+      throw new IllegalArgumentException("b <= a");
+    }
+    if (num < 0) {
+      throw new IllegalArgumentException("num cannot be < 0");
+    }
+    byte [] prependHeader = {1, 0};
+    final BigInteger startBI = new BigInteger(add(prependHeader, aPadded));
+    final BigInteger stopBI = new BigInteger(add(prependHeader, bPadded));
+    BigInteger diffBI = stopBI.subtract(startBI);
+    if (inclusive) {
+      diffBI = diffBI.add(BigInteger.ONE);
+    }
+    final BigInteger splitsBI = BigInteger.valueOf(num + 1);
+    if(diffBI.compareTo(splitsBI) < 0) {
+      return null;
+    }
+    final BigInteger intervalBI;
+    try {
+      intervalBI = diffBI.divide(splitsBI);
+    } catch(Exception e) {
+      LOG.error("Exception caught during division", e);
+      return null;
+    }
+
+    final Iterator<byte[]> iterator = new Iterator<byte[]>() {
+      private int i = -1;
+      private BigInteger curBI = startBI;
+
+      @Override
+      public boolean hasNext() {
+        return i < num+1;
+      }
+
+      @Override
+      public byte[] next() {
+        i++;
+        if (i == 0) return a;
+        if (i == num + 1) return b;
+
+        curBI = curBI.add(intervalBI);
+        byte [] padded = curBI.toByteArray();
+        if (padded[1] == 0)
+          padded = tail(padded, padded.length - 2);
+        else
+          padded = tail(padded, padded.length - 1);
+        return padded;
+      }
+
+      @Override
+      public void remove() {
+        throw new UnsupportedOperationException();
+      }
+
+    };
+
+    return new Iterable<byte[]>() {
+      @Override
+      public Iterator<byte[]> iterator() {
+        return iterator;
+      }
+    };
+  }
+
+  /**
+   * Calculate the next <code>num</code> elements in arithemetic
+   * progression sequence.
+   *
+   * @param a First element.
+   * @param b Second element.
+   * @param num Number of next elements to find.
+   * @return <code>num</code> byte arrays each having the same interval
+   *         from <code>a</code> to <code>b</code>, starting from b. In
+   *         other words, it returns an array consists of b+(b-a)*(i+1),
+   *         where i is the index of the resulting array of size <code>
+   *         num</code>. Uses BigInteger math.
+   */
+  public static byte[][] arithmeticProgSeq(byte[] a, byte[] b, int num) {
+    byte [][] result = new byte[num][];
+    byte [] aPadded;
+    byte [] bPadded;
+    if (a.length < b.length) {
+      aPadded = padTail(a, b.length - a.length);
+      bPadded = b;
+    } else if (b.length < a.length) {
+      aPadded = a;
+      bPadded = padTail(b, a.length - b.length);
+    } else {
+      aPadded = a;
+      bPadded = b;
+    }
+    if (num < 0) {
+      throw new IllegalArgumentException("num cannot be < 0");
+    }
+    byte [] prependHeader = {1, 0};
+    BigInteger startBI = new BigInteger(add(prependHeader, aPadded));
+    BigInteger stopBI = new BigInteger(add(prependHeader, bPadded));
+    BigInteger diffBI = stopBI.subtract(startBI);
+    BigInteger curBI = stopBI;
+    for (int i = 0; i < num; i++) {
+      curBI = curBI.add(diffBI);
+      byte [] padded = curBI.toByteArray();
+      if (padded[1] == 0)
+        padded = tail(padded, padded.length - 2);
+      else
+        padded = tail(padded, padded.length - 1);
+      result[i] = padded;
+    }
+    return result;
+  }
+
+  /**
+   * @param t operands
+   * @return Array of byte arrays made from passed array of Text
+   */
+  public static byte [][] toByteArrays(final String [] t) {
+    byte [][] result = new byte[t.length][];
+    for (int i = 0; i < t.length; i++) {
+      result[i] = Bytes.toBytes(t[i]);
+    }
+    return result;
+  }
+
+  /**
+   * @param column operand
+   * @return A byte array of a byte array where first and only entry is
+   * <code>column</code>
+   */
+  public static byte [][] toByteArrays(final String column) {
+    return toByteArrays(toBytes(column));
+  }
+
+  /**
+   * @param column operand
+   * @return A byte array of a byte array where first and only entry is
+   * <code>column</code>
+   */
+  public static byte [][] toByteArrays(final byte [] column) {
+    byte [][] result = new byte[1][];
+    result[0] = column;
+    return result;
+  }
+
+  /**
+   * Binary search for keys in indexes.
+   *
+   * @param arr array of byte arrays to search for
+   * @param key the key you want to find
+   * @param offset the offset in the key you want to find
+   * @param length the length of the key
+   * @param comparator a comparator to compare.
+   * @return zero-based index of the key, if the key is present in the array.
+   *         Otherwise, a value -(i + 1) such that the key is between arr[i -
+   *         1] and arr[i] non-inclusively, where i is in [0, i], if we define
+   *         arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above
+   *         means that this function can return 2N + 1 different values
+   *         ranging from -(N + 1) to N - 1.
+   */
+  public static int binarySearch(byte [][]arr, byte []key, int offset,
+      int length, RawComparator<byte []> comparator) {
+    int low = 0;
+    int high = arr.length - 1;
+
+    while (low <= high) {
+      int mid = (low+high) >>> 1;
+      // we have to compare in this order, because the comparator order
+      // has special logic when the 'left side' is a special key.
+      int cmp = comparator.compare(key, offset, length,
+          arr[mid], 0, arr[mid].length);
+      // key lives above the midpoint
+      if (cmp > 0)
+        low = mid + 1;
+      // key lives below the midpoint
+      else if (cmp < 0)
+        high = mid - 1;
+      // BAM. how often does this really happen?
+      else
+        return mid;
+    }
+    return - (low+1);
+  }
+
+  /**
+   * Bytewise binary increment/deincrement of long contained in byte array
+   * on given amount.
+   *
+   * @param value - array of bytes containing long (length <= SIZEOF_LONG)
+   * @param amount value will be incremented on (deincremented if negative)
+   * @return array of bytes containing incremented long (length == SIZEOF_LONG)
+   * @throws IOException - if value.length > SIZEOF_LONG
+   */
+  public static byte [] incrementBytes(byte[] value, long amount)
+  throws IOException {
+    byte[] val = value;
+    if (val.length < SIZEOF_LONG) {
+      // Hopefully this doesn't happen too often.
+      byte [] newvalue;
+      if (val[0] < 0) {
+        newvalue = new byte[]{-1, -1, -1, -1, -1, -1, -1, -1};
+      } else {
+        newvalue = new byte[SIZEOF_LONG];
+      }
+      System.arraycopy(val, 0, newvalue, newvalue.length - val.length,
+        val.length);
+      val = newvalue;
+    } else if (val.length > SIZEOF_LONG) {
+      throw new IllegalArgumentException("Increment Bytes - value too big: " +
+        val.length);
+    }
+    if(amount == 0) return val;
+    if(val[0] < 0){
+      return binaryIncrementNeg(val, amount);
+    }
+    return binaryIncrementPos(val, amount);
+  }
+
+  /* increment/deincrement for positive value */
+  private static byte [] binaryIncrementPos(byte [] value, long amount) {
+    long amo = amount;
+    int sign = 1;
+    if (amount < 0) {
+      amo = -amount;
+      sign = -1;
+    }
+    for(int i=0;i<value.length;i++) {
+      int cur = ((int)amo % 256) * sign;
+      amo = (amo >> 8);
+      int val = value[value.length-i-1] & 0x0ff;
+      int total = val + cur;
+      if(total > 255) {
+        amo += sign;
+        total %= 256;
+      } else if (total < 0) {
+        amo -= sign;
+      }
+      value[value.length-i-1] = (byte)total;
+      if (amo == 0) return value;
+    }
+    return value;
+  }
+
+  /* increment/deincrement for negative value */
+  private static byte [] binaryIncrementNeg(byte [] value, long amount) {
+    long amo = amount;
+    int sign = 1;
+    if (amount < 0) {
+      amo = -amount;
+      sign = -1;
+    }
+    for(int i=0;i<value.length;i++) {
+      int cur = ((int)amo % 256) * sign;
+      amo = (amo >> 8);
+      int val = ((~value[value.length-i-1]) & 0x0ff) + 1;
+      int total = cur - val;
+      if(total >= 0) {
+        amo += sign;
+      } else if (total < -256) {
+        amo -= sign;
+        total %= 256;
+      }
+      value[value.length-i-1] = (byte)total;
+      if (amo == 0) return value;
+    }
+    return value;
+  }
+
+  /**
+   * Writes a string as a fixed-size field, padded with zeros.
+   */
+  public static void writeStringFixedSize(final DataOutput out, String s,
+      int size) throws IOException {
+    byte[] b = toBytes(s);
+    if (b.length > size) {
+      throw new IOException("Trying to write " + b.length + " bytes (" +
+          toStringBinary(b) + ") into a field of length " + size);
+    }
+
+    out.writeBytes(s);
+    for (int i = 0; i < size - s.length(); ++i)
+      out.writeByte(0);
+  }
+
+  /**
+   * Reads a fixed-size field and interprets it as a string padded with zeros.
+   */
+  public static String readStringFixedSize(final DataInput in, int size)
+      throws IOException {
+    byte[] b = new byte[size];
+    in.readFully(b);
+    int n = b.length;
+    while (n > 0 && b[n - 1] == 0)
+      --n;
+
+    return toString(b, 0, n);
+  }
+
+  /**
+   * @param b a byte buffer
+   * @return true if the given byte buffer is non-null and non-empty (has remaining bytes)
+   */
+  public static boolean isNonEmpty(ByteBuffer b) {
+    return b != null && b.remaining() > 0;
+  }
+
+  /**
+   * This is a utility method, that serializes a Swift annotated class' object
+   * into a byte array. This is equivalent to Writable.getBytes().
+   *
+   * @param t The object to be serialized.
+   * @param clazz The class of the object to be serialized
+   * @param <T>
+   * @return The byte array corresponding to the serialized object.
+   * @throws Exception
+   */
+  public static <T> ByteBuffer writeThriftBytes(T t, Class<T> clazz,
+    Class<? extends TProtocol> protocolClass)
+    throws Exception {
+    TMemoryBuffer buffer =
+      writeThriftBytesAndGetBuffer(t, clazz, protocolClass);
+    return ByteBuffer.wrap(buffer.getArray(), 0, buffer.length());
+  }
+
+  /**
+   * @param t
+   * @param clazz
+   * @return
+   * @throws Exception
+   */
+  public static <T> TMemoryBuffer writeThriftBytesAndGetBuffer(T t,
+    Class<T> clazz, Class<? extends TProtocol> protocolClass) throws Exception {
+    ThriftCodec<T> codec = THRIFT_CODEC_MANAGER.getCodec(clazz);
+    TMemoryBuffer buffer = new TMemoryBuffer(0);
+    TProtocol protocol =
+      protocolClass.getConstructor(TTransport.class).newInstance(buffer);
+    codec.write(t, protocol);
+    return buffer;
+  }
+
+  /**
+   * This is a utility method, that deserializes a Swift annotated class' object
+   * from a byte array. This is equivalent to Writable.getWritable().
+   *
+   * @param buff
+   * @param clazz
+   * @param <T>
+   * @return
+   * @throws Exception
+   */
+  public static <T> T readThriftBytes(byte[] buff,
+    Class<T> clazz, Class<? extends TProtocol> protocolClass)
+    throws Exception {
+    ThriftCodec<T> codec = THRIFT_CODEC_MANAGER.getCodec(clazz);
+    TMemoryInputTransport buffer = new TMemoryInputTransport(buff);
+    TProtocol protocol =
+      protocolClass.getConstructor(TTransport.class).newInstance(buffer);
+    return codec.read(protocol);
+  }
+
+  public static byte[] copyOfByteArray(byte[] arr) {
+    byte[] tmp = new byte[arr.length];
+    System.arraycopy(arr, 0, tmp, 0, arr.length);
+    return tmp;
+  }
+
+  /**
+   * Returns a byte array next to a given one, i.e. it is the smallest byte
+   * array among all byte arrays that is strictly greater than the give array.
+   * Greater and smaller are defined by Bytes.compareTo.
+   *
+   * @param b
+   *          the give array
+   */
+  public static byte[] nextOf(byte[] b) {
+    byte[] res = new byte[b.length + 1];
+    System.arraycopy(b, 0, res, 0, b.length);
+    return res;
+  }
+
+  /**
+   * Return whether b equals nextOf(a)
+   */
+  public static boolean isNext(byte[] a, byte[] b) {
+    return isNext(a, 0, a.length, b, 0, b.length);
+  }
+
+  /**
+   * Return whether b[...] equals nextOf(a[...])
+   */
+  public static boolean isNext(byte[] a, int aOffs, int aLen, byte[] b,
+      int bOffs, int bLen) {
+    if (a == null || b == null) {
+      return false;
+    }
+
+    if (bLen != aLen + 1) {
+      return false;
+    }
+    if (b[bOffs + aLen] != 0) {
+      return false;
+    }
+    return Bytes.compareTo(a, aOffs, aLen, b, bOffs, aLen) == 0;
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/ConditionUtil.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/ConditionUtil.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/ConditionUtil.java
new file mode 100644
index 0000000..a86264d
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/ConditionUtil.java
@@ -0,0 +1,62 @@
+/**
+ * Copyright The Apache Software Foundation
+ *
+ * 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 com.google.common.base.Preconditions;
+
+/**
+ * Extends the patterns in {@link Preconditions}
+ */
+public class ConditionUtil {
+
+  /**
+   * Checks if a specified offset is >= 0
+   * @param offset The offset to check
+   * @return The specified offset if it is >= 0
+   * @throws IndexOutOfBoundsException If specified offset is negative
+   */
+  public static long checkPositiveOffset(long offset) {
+    return checkOffset(offset, -1);
+  }
+
+  /**
+   * Check if an offset is >= 0 but less than a maximum limit (if one is
+   * specified).
+   * @see {@link Preconditions#checkPositionIndex(int, int)}
+   * @param offset The offset to check
+   * @param limit The maximum limit or -1 if none
+   * @return The specified offset if it is positive and if the a limit is
+   *         specified lower than that limit.
+   * @throws IllegalStateException If the offset is negative, or if a limit
+   *         is specified and the offset is greater than the limit.
+   */
+  public static long checkOffset(long offset, long limit) {
+    if (offset < 0) {
+      throw new IndexOutOfBoundsException("Negative offset: " + offset);
+    }
+    if (limit != -1 && offset >= limit) {
+      throw new IndexOutOfBoundsException("Offset (" + offset +
+          ") is greater than limit (" + limit + ")");
+    }
+    return offset;
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/DaemonThreadFactory.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/DaemonThreadFactory.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/DaemonThreadFactory.java
new file mode 100644
index 0000000..9733fdb
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/DaemonThreadFactory.java
@@ -0,0 +1,46 @@
+/**
+ * Copyright The Apache Software Foundation
+ *
+ * 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.util.concurrent.ThreadFactory;
+
+public class DaemonThreadFactory implements ThreadFactory {
+  final ThreadGroup group;
+  int threadNumber = 1;
+  final String namePrefix;
+
+  public DaemonThreadFactory(String namePrefix) {
+      SecurityManager s = System.getSecurityManager();
+      group = (s != null)? s.getThreadGroup() :
+                           Thread.currentThread().getThreadGroup();
+      this.namePrefix = namePrefix;
+  }
+
+  public Thread newThread(Runnable r) {
+      Thread t = new Thread(group, r,
+                            namePrefix + (threadNumber++),
+                            0);
+      if (!t.isDaemon())
+          t.setDaemon(true);
+      if (t.getPriority() != Thread.NORM_PRIORITY)
+          t.setPriority(Thread.NORM_PRIORITY);
+      return t;
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/HasThread.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/HasThread.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/HasThread.java
new file mode 100644
index 0000000..058d64c
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/HasThread.java
@@ -0,0 +1,101 @@
+/**
+ * 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.lang.Thread.UncaughtExceptionHandler;
+
+/**
+ * Abstract class which contains a Thread and delegates the common Thread
+ * methods to that instance.
+ *
+ * The purpose of this class is to workaround Sun JVM bug #6915621, in which
+ * something internal to the JDK uses Thread.currentThread() as a monitor
+ * lock. This can produce deadlocks like HBASE-4367, HBASE-4101, etc.
+ */
+public abstract class HasThread implements Runnable {
+  private final Thread thread;
+
+  public HasThread() {
+    this.thread = new Thread(this);
+  }
+
+  public HasThread(String name) {
+    this.thread = new Thread(this, name);
+  }
+
+  public Thread getThread() {
+    return thread;
+  }
+
+  public abstract void run();
+
+  //// Begin delegation to Thread
+
+  public final String getName() {
+    return thread.getName();
+  }
+
+  public void interrupt() {
+    thread.interrupt();
+  }
+
+  public final boolean isAlive() {
+    return thread.isAlive();
+  }
+
+  public boolean isInterrupted() {
+    return thread.isInterrupted();
+  }
+
+  public final void setDaemon(boolean on) {
+    thread.setDaemon(on);
+  }
+
+  public final void setName(String name) {
+    thread.setName(name);
+  }
+
+  public final void setPriority(int newPriority) {
+    thread.setPriority(newPriority);
+  }
+
+  public void setUncaughtExceptionHandler(UncaughtExceptionHandler eh) {
+    thread.setUncaughtExceptionHandler(eh);
+  }
+
+  public void start() {
+    thread.start();
+  }
+
+  public final void join() throws InterruptedException {
+    thread.join();
+  }
+
+  public final void join(long millis, int nanos) throws InterruptedException {
+    thread.join(millis, nanos);
+  }
+
+  public final void join(long millis) throws InterruptedException {
+    thread.join(millis);
+  }
+
+  public static void sleep(long millis) throws InterruptedException {
+    Thread.sleep(millis);
+  }
+  //// End delegation to Thread
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/eca32aa4/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Histogram.java
----------------------------------------------------------------------
diff --git a/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Histogram.java b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Histogram.java
new file mode 100644
index 0000000..adab560
--- /dev/null
+++ b/hbase-consensus/src/main/java/org/apache/hadoop/hbase/util/Histogram.java
@@ -0,0 +1,390 @@
+/**
+ * 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 org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.hbase.regionserver.metrics.PercentileMetric;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
+/**
+ * The Histogram class provides a mechanism to sample data points and perform
+ * estimates about percentile metrics.
+ * Percentile metric is defined as the follows :
+ *  A P99 value is the 99th percentile value among the given data points.
+ *
+ * Usage :
+ * Refer to RegionServerMetrics to see how this Histogram can be used to find
+ * percentile estimates.
+ *
+ * The general expected workflow of a Histogram class is as follows:
+ * [<Initialize Histogram> [[<addValue>]* [<getPercentileEstimate>]+ <refresh>]*]
+ *
+ * In the above sequence addValue can be called from different threads, but
+ * getPercentileEstimate and refresh should be called from the same thread since
+ * they are not mutually thread safe.
+ */
+
+public class Histogram {
+  private List<Bucket> buckets;
+  private int numBuckets;
+  private double minValue;
+  private double maxValue;
+
+  public static class Stats {
+    public double min = 0;
+    public double max = 0;
+    public double avg = 0;
+    public double count = 0;
+  }
+
+  private List<Double> underloadSampleList; // We serve the under loaded cases
+  // from this list.
+  final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
+  private boolean underload = true;
+  public static final Log LOG = LogFactory.getLog(Histogram.class.getName());
+
+  // We will consider the case when we have more than 100 samples as
+  // overloaded case and use the Histogram only in such scenarios. In other
+  // cases, we can serve the percentile queries using the underloadSampleList
+  private static final int DEFAULT_MINIMUM_LOAD = 100;
+
+  /**
+   * Create a histogram with the default values of number of buckets,
+   * and min/max for the values.
+   */
+  public Histogram() {
+    this(PercentileMetric.HISTOGRAM_NUM_BUCKETS_DEFAULT,
+          PercentileMetric.HISTOGRAM_MINVALUE_DEFAULT,
+          PercentileMetric.HISTOGRAM_MAXVALUE_DEFAULT);
+  }
+
+  // Bucket indexing is from 1 to N
+  public Histogram(int numBuckets, double lowBound, double maxValue) {
+    if (numBuckets < 1 || lowBound >= maxValue) {
+      throw new UnsupportedOperationException();
+    }
+    buckets = new ArrayList<Bucket>(numBuckets);
+    underloadSampleList = Collections.synchronizedList(new ArrayList<Double>());
+    refresh(numBuckets, lowBound, maxValue);
+  }
+
+  public Stats getBasicStats() {
+    Stats stats = new Stats();
+
+    this.lock.writeLock().lock();
+    try {
+      if (underloadSampleList.size() == 0) {
+        if (LOG.isTraceEnabled()) {
+          LOG.trace("Too few data points. Consider increasing the sampling time.");
+        }
+        return stats;
+      } else if (underload) {
+        Collections.sort(underloadSampleList);
+        stats.min = underloadSampleList.get(0);
+        stats.max = underloadSampleList.get(underloadSampleList.size() - 1);
+        stats.count = underloadSampleList.size();
+        double sum = 0;
+        for (double d : underloadSampleList) {
+          sum += d;
+        }
+        stats.avg = sum / stats.count;
+
+        return stats;
+      } else {
+        int totalCount = 0;
+        double totalSum = 0;
+        boolean minFound = false;
+        stats.max = Double.MIN_VALUE;
+
+        for (int i = 0; i < this.buckets.size(); i++) {
+          Bucket b = this.buckets.get(i);
+          if (b.count > 0) {
+            if (!minFound) {
+              stats.min = b.getMinValue();
+              minFound = true;
+            }
+            stats.max = Math.max(stats.max, b.getMaxValue());
+            totalCount += b.getCount();
+            totalSum += b.getSum();
+          }
+        }
+        stats.count = totalCount;
+        stats.avg = (totalCount == 0) ? 0 : (totalSum / (double) totalCount);
+      }
+    } catch(Exception e) {
+      LOG.error("Unknown Exception : " + e.getMessage());
+    } finally {
+      this.lock.writeLock().unlock();
+    }
+
+    return stats;
+  }
+
+  // This is included in the bucket
+  private double getBucketStartValue(int bucketIndex) {
+    if (bucketIndex < 1 || bucketIndex > this.numBuckets) {
+      throw new IndexOutOfBoundsException();
+    }
+    double gap = this.maxValue - this.minValue;
+    double slice = gap/this.numBuckets;
+    return this.minValue + (bucketIndex - 1.0)*slice;
+  }
+
+  //This is not included in the bucket
+  private double getBucketEndValue(int bucketIndex) {
+    if (bucketIndex < 1 || bucketIndex > this.numBuckets) {
+      throw new IndexOutOfBoundsException();
+    }
+    double gap = this.maxValue - this.minValue;
+    double slice = gap/this.numBuckets;
+    return this.minValue + (bucketIndex)*slice;
+  }
+
+  private int getBucketIndex(double value) {
+    if (value < this.minValue) {
+      return 0;
+    } else if (value >= this.maxValue) {
+      return this.numBuckets + 1;
+    } else {
+      double gap = value - this.minValue;
+      double idx = this.numBuckets * gap / (this.maxValue - this.minValue);
+      int i = (int)idx + 1;
+      // Check if the index falls in the margin somehow.
+      if (value < this.getBucketStartValue(i)) i--;
+      else if (value >= this.getBucketEndValue(i)) i++;
+      return i; // Due to 1 indexing
+    }
+  }
+
+  public void refresh() {
+    this.refresh(this.numBuckets);
+  }
+
+  public void refresh(int numBuckets) {
+    this.lock.writeLock().lock();
+    try {
+      double lowBound = this.minValue;
+      double upBound = this.maxValue;
+      for (Bucket bucket : this.buckets) {
+        if (bucket.count > 0) {
+          lowBound = bucket.getMinValue();
+          break;
+        }
+      }
+      for (int i = this.buckets.size() - 1; i>=0; i--) {
+        Bucket bucket = this.buckets.get(i);
+        if (bucket.count > 0) {
+          upBound = bucket.getMaxValue();
+          break;
+        }
+      }
+      this.refresh(numBuckets, lowBound, upBound);
+    } catch (Exception e) {
+      LOG.error("Unknown Exception : " + e.getMessage());
+    } finally {
+      this.lock.writeLock().unlock();
+    }
+  }
+
+  private void refresh(int numBuckets, double minValue, double maxValue) {
+    this.numBuckets = numBuckets;
+    this.minValue = minValue;
+    this.maxValue = maxValue;
+
+    this.buckets.clear();
+    underloadSampleList.clear();
+    underload = true;
+    buckets.add(new Bucket(Double.MIN_VALUE, this.getBucketStartValue(1)));
+    for (int i = 1; i<=this.numBuckets; i++) {
+      this.buckets.add(new Bucket(this.getBucketStartValue(i),
+          this.getBucketEndValue(i)));
+    }
+    buckets.add(new Bucket(this.getBucketEndValue(this.numBuckets),
+        Double.MAX_VALUE));
+  }
+
+  public double getPercentileEstimate(double prcntyl) {
+    // We scan from the end of the table since our use case is to find the
+    // p99, p95 latencies.
+    double originalPrcntyl = prcntyl;
+    if (prcntyl > 100.0 || prcntyl < 0.0) {
+      throw new IllegalArgumentException("Percentile input value not in range.");
+    } else {
+      prcntyl = 100.0 - prcntyl;
+    }
+    double ret = 0.0;
+    this.lock.writeLock().lock();
+    try {
+      if (underloadSampleList.size() == 0) {
+        if (LOG.isTraceEnabled()) {
+          LOG.trace("Too few data points. Consider increasing the sampling time.");
+        }
+        return ret;
+      } else if (underload) {
+        Collections.sort(underloadSampleList);
+        // Since the use case is to clear the list after a call to this
+        // function, we can afford to sort this list here and enjoy O(1) the
+        // rest of the time.
+        return underloadSampleList.get(
+            (int)(originalPrcntyl * underloadSampleList.size()/100.0));
+      }
+      int totalCount = 0;
+      for (Bucket bucket : this.buckets) {
+        totalCount += bucket.count;
+      }
+      double countToCoverdouble = (totalCount * prcntyl / 100.0);
+      int countToCover = (int)countToCoverdouble;
+      for (int i=this.buckets.size() - 1; i >= 0; i--) {
+        Bucket bucket = this.buckets.get(i);
+        if (bucket.getCount() >= countToCover) {
+          return bucket.getGreaterValue(bucket.getCount() - countToCover);
+        } else {
+          countToCover -= bucket.getCount();
+        }
+      }
+      ret = this.maxValue;
+    } catch(Exception e) {
+      LOG.error("Unknown Exception : " + e.getMessage());
+    } finally {
+      this.lock.writeLock().unlock();
+    }
+    return ret;
+  }
+
+  public void addValue(double value) {
+    this.lock.readLock().lock();
+    try {
+      if (underloadSampleList.size() >= Histogram.DEFAULT_MINIMUM_LOAD) {
+        if (underload) {
+          synchronized (underloadSampleList) {
+            if (underload) {
+              for (double val : underloadSampleList) {
+                Bucket bucket = buckets.get(this.getBucketIndex(val));
+                bucket.addValue(val);
+              }
+            }
+            underload = false;
+          }
+        }
+        Bucket bucket = buckets.get(this.getBucketIndex(value));
+        bucket.addValue(value);
+      } else {
+        underloadSampleList.add(value);
+      }
+    } catch (Exception e) {
+      LOG.error("Unknown Exception : " + e.getMessage());
+    } finally {
+      this.lock.readLock().unlock();
+    }
+  }
+
+  public void addValue(Long value) {
+    addValue(value.doubleValue());
+  }
+
+  public class Bucket {
+    private double sum;
+    private int count;
+    private double minValue;
+    private double maxValue;
+    private double startValue;
+    private double endValue;
+    public Bucket(double startValue, double endValue) {
+      this.sum = 0.0;
+      this.count = 0;
+      this.minValue = endValue;
+      this.maxValue = startValue;
+      this.startValue = startValue;
+      this.endValue = endValue;
+    }
+
+    public void addValue(double value) {
+      this.sum = this.sum + value;
+      count++;
+      this.minValue = Math.min(this.minValue, value);
+      this.maxValue = Math.max(this.maxValue, value);
+    }
+
+    /**
+     * This function gives the count of the number of items in the bucket
+     * which are smaller than the given value;
+     * For the purpose of this calculation, the distribution over the bucket
+     * is assumed to be uniformly distributed between minValue and maxValue
+     */
+    public int getGreaterCount(double value) {
+      if (!(this.minValue < value && this.maxValue >= value)) {
+        throw new IllegalArgumentException();
+      }
+      if (this.count == 0) return 0;
+      else if (this.count == 1) {
+        if (this.minValue > value) return 0;
+        else return 1;
+      }
+      double gap = value - this.minValue;
+      double ret = this.count * gap / (this.maxValue - this.minValue);
+      return (int)ret;
+    }
+
+    /**
+     * This function gives the value which is more than a certain count in this
+     * bucket.
+     * */
+    public double getGreaterValue(int count) {
+      if (count > this.count) {
+        throw new IllegalArgumentException();
+      }
+      double gap = this.maxValue - this.minValue;
+      double ret = this.minValue + gap * count / this.count;
+      return ret;
+    }
+
+    public double getSum() {
+      return this.sum;
+    }
+
+    public int getCount() {
+      return this.count;
+    }
+
+    public double getMinValue() {
+      return this.minValue;
+    }
+
+    public double getMaxValue() {
+      return this.maxValue;
+    }
+
+    @Override
+    public String toString() {
+      StringBuilder s = new StringBuilder();
+      s.append("Bucket Details :");
+      s.append(" count : " + this.count);
+      s.append(" sum : " + this.sum);
+      s.append(" minValue : " + this.minValue);
+      s.append(" maxValue : " + this.maxValue);
+      s.append(" startValue : " + this.startValue);
+      s.append(" endValue : " + this.endValue);
+      return s.toString();
+    }
+  }
+}


Mime
View raw message