You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by zh...@apache.org on 2018/05/15 00:40:23 UTC
[04/32] hbase git commit: HBASE-20564 Tighter ByteBufferKeyValue Cell
Comparator
HBASE-20564 Tighter ByteBufferKeyValue Cell Comparator
Make a purposed comparator for the new ByteBufferKeyValue
base type. Cache deserialized sizes rather than recalc each time.
Project: http://git-wip-us.apache.org/repos/asf/hbase/repo
Commit: http://git-wip-us.apache.org/repos/asf/hbase/commit/db04a9f9
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/db04a9f9
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/db04a9f9
Branch: refs/heads/HBASE-19064
Commit: db04a9f9d910caf3976f8a86cdd8bacbafcd78e4
Parents: eabe672
Author: Michael Stack <st...@apache.org>
Authored: Fri May 11 07:09:52 2018 +0100
Committer: Michael Stack <st...@apache.org>
Committed: Mon May 14 15:18:26 2018 +0100
----------------------------------------------------------------------
.../apache/hadoop/hbase/ByteBufferKeyValue.java | 58 +++++----
.../apache/hadoop/hbase/CellComparatorImpl.java | 126 +++++++++++++++----
.../hadoop/hbase/TestByteBufferKeyValue.java | 19 +++
3 files changed, 159 insertions(+), 44 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hbase/blob/db04a9f9/hbase-common/src/main/java/org/apache/hadoop/hbase/ByteBufferKeyValue.java
----------------------------------------------------------------------
diff --git a/hbase-common/src/main/java/org/apache/hadoop/hbase/ByteBufferKeyValue.java b/hbase-common/src/main/java/org/apache/hadoop/hbase/ByteBufferKeyValue.java
index 760d02c..963b411 100644
--- a/hbase-common/src/main/java/org/apache/hadoop/hbase/ByteBufferKeyValue.java
+++ b/hbase-common/src/main/java/org/apache/hadoop/hbase/ByteBufferKeyValue.java
@@ -77,10 +77,6 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public short getRowLength() {
- return getRowLen();
- }
-
- private short getRowLen() {
return ByteBufferUtils.toShort(this.buf, this.offset + KeyValue.ROW_OFFSET);
}
@@ -99,12 +95,15 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
return getFamilyLength(getFamilyLengthPosition());
}
- private int getFamilyLengthPosition() {
- return this.offset + KeyValue.ROW_KEY_OFFSET
- + getRowLen();
+ int getFamilyLengthPosition() {
+ return getFamilyLengthPosition(getRowLength());
+ }
+
+ int getFamilyLengthPosition(int rowLength) {
+ return this.offset + KeyValue.ROW_KEY_OFFSET + rowLength;
}
- private byte getFamilyLength(int famLenPos) {
+ byte getFamilyLength(int famLenPos) {
return ByteBufferUtils.toByte(this.buf, famLenPos);
}
@@ -120,21 +119,24 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public int getQualifierLength() {
- return getQualifierLength(getRowLength(), getFamilyLength());
+ return getQualifierLength(getKeyLength(), getRowLength(), getFamilyLength());
}
- private int getQualifierLength(int rlength, int flength) {
- return getKeyLen()
- - (int) KeyValue.getKeyDataStructureSize(rlength, flength, 0);
+ int getQualifierLength(int keyLength, int rlength, int flength) {
+ return keyLength - (int) KeyValue.getKeyDataStructureSize(rlength, flength, 0);
}
@Override
public long getTimestamp() {
- int offset = getTimestampOffset(getKeyLen());
+ return getTimestamp(getKeyLength());
+ }
+
+ long getTimestamp(int keyLength) {
+ int offset = getTimestampOffset(keyLength);
return ByteBufferUtils.toLong(this.buf, offset);
}
- private int getKeyLen() {
+ int getKeyLength() {
return ByteBufferUtils.toInt(this.buf, this.offset);
}
@@ -144,8 +146,11 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public byte getTypeByte() {
- return ByteBufferUtils.toByte(this.buf,
- this.offset + getKeyLen() - 1 + KeyValue.ROW_OFFSET);
+ return getTypeByte(getKeyLength());
+ }
+
+ byte getTypeByte(int keyLen) {
+ return ByteBufferUtils.toByte(this.buf, this.offset + keyLen - 1 + KeyValue.ROW_OFFSET);
}
@Override
@@ -185,7 +190,7 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public int getTagsLength() {
- int tagsLen = this.length - (getKeyLen() + getValueLength()
+ int tagsLen = this.length - (getKeyLength() + getValueLength()
+ KeyValue.KEYVALUE_INFRASTRUCTURE_SIZE);
if (tagsLen > 0) {
// There are some Tag bytes in the byte[]. So reduce 2 bytes which is
@@ -213,7 +218,11 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public int getFamilyPosition() {
- return getFamilyLengthPosition() + Bytes.SIZEOF_BYTE;
+ return getFamilyPosition(getFamilyLengthPosition());
+ }
+
+ public int getFamilyPosition(int familyLengthPosition) {
+ return familyLengthPosition + Bytes.SIZEOF_BYTE;
}
@Override
@@ -223,7 +232,11 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public int getQualifierPosition() {
- return getFamilyPosition() + getFamilyLength();
+ return getQualifierPosition(getFamilyPosition(), getFamilyLength());
+ }
+
+ int getQualifierPosition(int familyPosition, int familyLength) {
+ return familyPosition + familyLength;
}
@Override
@@ -233,7 +246,7 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
@Override
public int getValuePosition() {
- return this.offset + KeyValue.ROW_OFFSET + getKeyLen();
+ return this.offset + KeyValue.ROW_OFFSET + getKeyLength();
}
@Override
@@ -270,8 +283,7 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
if (withTags) {
return this.length;
}
- return getKeyLen() + this.getValueLength()
- + KeyValue.KEYVALUE_INFRASTRUCTURE_SIZE;
+ return getKeyLength() + this.getValueLength() + KeyValue.KEYVALUE_INFRASTRUCTURE_SIZE;
}
@Override
@@ -292,7 +304,7 @@ public class ByteBufferKeyValue extends ByteBufferExtendedCell {
private int getTimestampOffset() {
return this.offset + KeyValue.KEYVALUE_INFRASTRUCTURE_SIZE
- + getKeyLen() - KeyValue.TIMESTAMP_TYPE_SIZE;
+ + getKeyLength() - KeyValue.TIMESTAMP_TYPE_SIZE;
}
@Override
http://git-wip-us.apache.org/repos/asf/hbase/blob/db04a9f9/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparatorImpl.java
----------------------------------------------------------------------
diff --git a/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparatorImpl.java b/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparatorImpl.java
index b1af716..fa336fd 100644
--- a/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparatorImpl.java
+++ b/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparatorImpl.java
@@ -70,20 +70,98 @@ public class CellComparatorImpl implements CellComparator {
* @return 0 if equal, -1 if a < b, and +1 if a > b.
*/
public final int compare(final Cell a, final Cell b, boolean ignoreSequenceid) {
- // row
- int c = compareRows(a, b);
- if (c != 0) return c;
+ int diff = 0;
+ if (a instanceof ByteBufferKeyValue && b instanceof ByteBufferKeyValue) {
+ diff = compareByteBufferKeyValue((ByteBufferKeyValue)a, (ByteBufferKeyValue)b);
+ if (diff != 0) {
+ return diff;
+ }
+ } else {
+ diff = compareRows(a, b);
+ if (diff != 0) {
+ return diff;
+ }
- c = compareWithoutRow(a, b);
- if(c != 0) return c;
+ diff = compareWithoutRow(a, b);
+ if (diff != 0) {
+ return diff;
+ }
+ }
- if (!ignoreSequenceid) {
- // Negate following comparisons so later edits show up first
- // mvccVersion: later sorts first
- return Longs.compare(b.getSequenceId(), a.getSequenceId());
- } else {
- return c;
+ // Negate following comparisons so later edits show up first mvccVersion: later sorts first
+ return ignoreSequenceid? diff: Longs.compare(b.getSequenceId(), a.getSequenceId());
+ }
+
+ /**
+ * Specialized comparator for the ByteBufferKeyValue type exclusivesly.
+ * Caches deserialized lengths of rows and families, etc., and reuses them where it can
+ * (ByteBufferKeyValue has been changed to be amenable to our providing pre-made lengths, etc.)
+ */
+ private final int compareByteBufferKeyValue(ByteBufferKeyValue left, ByteBufferKeyValue right) {
+ // Compare Rows. Cache row length.
+ int leftRowLength = left.getRowLength();
+ int rightRowLength = right.getRowLength();
+ int diff = ByteBufferUtils.compareTo(
+ left.getRowByteBuffer(), left.getRowPosition(), leftRowLength,
+ right.getRowByteBuffer(), right.getRowPosition(), rightRowLength);
+ if (diff != 0) {
+ return diff;
+ }
+
+ // If the column is not specified, the "minimum" key type appears the
+ // latest in the sorted order, regardless of the timestamp. This is used
+ // for specifying the last key/value in a given row, because there is no
+ // "lexicographically last column" (it would be infinitely long). The
+ // "maximum" key type does not need this behavior.
+ // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this.
+ // I tried to get rid of the above but scanners depend on it. TODO.
+ int leftFamilyLengthPosition = left.getFamilyLengthPosition(leftRowLength);
+ int leftFamilyLength = left.getFamilyLength(leftFamilyLengthPosition);
+ int rightFamilyLengthPosition = right.getFamilyLengthPosition(rightRowLength);
+ int rightFamilyLength = right.getFamilyLength(rightFamilyLengthPosition);
+ int leftKeyLength = left.getKeyLength();
+ int leftQualifierLength = left.getQualifierLength(leftKeyLength, leftRowLength,
+ leftFamilyLength);
+ byte leftType = left.getTypeByte(leftKeyLength);
+ if (leftFamilyLength + leftQualifierLength == 0 && leftType == Type.Minimum.getCode()) {
+ // left is "bigger", i.e. it appears later in the sorted order
+ return 1;
+ }
+ int rightKeyLength = right.getKeyLength();
+ int rightQualifierLength = right.getQualifierLength(rightKeyLength, rightRowLength,
+ rightFamilyLength);
+ byte rightType = right.getTypeByte(rightKeyLength);
+ if (rightFamilyLength + rightQualifierLength == 0 && rightType == Type.Minimum.getCode()) {
+ return -1;
}
+ // Compare families.
+ int leftFamilyPosition = left.getFamilyPosition(leftFamilyLengthPosition);
+ int rightFamilyPosition = right.getFamilyPosition(rightFamilyLengthPosition);
+ diff = ByteBufferUtils.compareTo(
+ left.getFamilyByteBuffer(), leftFamilyPosition, leftFamilyLength,
+ right.getFamilyByteBuffer(), rightFamilyPosition, rightFamilyLength);
+ if (diff != 0) {
+ return diff;
+ }
+ // Compare qualifiers
+ diff = ByteBufferUtils.compareTo(left.getQualifierByteBuffer(),
+ left.getQualifierPosition(leftFamilyPosition, leftFamilyLength), leftQualifierLength,
+ right.getQualifierByteBuffer(),
+ right.getQualifierPosition(rightFamilyPosition, rightFamilyLength),
+ rightQualifierLength);
+ if (diff != 0) {
+ return diff;
+ }
+ // Timestamps.
+ diff = compareTimestamps(left.getTimestamp(leftKeyLength), right.getTimestamp(rightKeyLength));
+ if (diff != 0) {
+ return diff;
+ }
+ // Compare types. Let the delete types sort ahead of puts; i.e. types
+ // of higher numbers sort before those of lesser numbers. Maximum (255)
+ // appears ahead of everything, and minimum (0) appears after
+ // everything.
+ return (0xff & rightType) - (0xff & leftType);
}
/**
@@ -173,35 +251,37 @@ public class CellComparatorImpl implements CellComparator {
* Compares the rows of the left and right cell.
* For the hbase:meta case this method is overridden such that it can handle hbase:meta cells.
* The caller should ensure using the appropriate comparator for hbase:meta.
- * @param left
- * @param right
* @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
*/
@Override
public int compareRows(final Cell left, final Cell right) {
+ return compareRows(left, left.getRowLength(), right, right.getRowLength());
+ }
+
+ int compareRows(final Cell left, int leftRowLength, final Cell right, int rightRowLength) {
// left and right can be exactly the same at the beginning of a row
if (left == right) {
return 0;
}
if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
+ ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength,
((ByteBufferExtendedCell) right).getRowByteBuffer(),
- ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
+ ((ByteBufferExtendedCell) right).getRowPosition(), rightRowLength);
}
if (left instanceof ByteBufferExtendedCell) {
return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
- right.getRowArray(), right.getRowOffset(), right.getRowLength());
+ ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength,
+ right.getRowArray(), right.getRowOffset(), rightRowLength);
}
if (right instanceof ByteBufferExtendedCell) {
// Notice how we flip the order of the compare here. We used to negate the return value but
// see what FindBugs says
// http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
// It suggest flipping the order to get same effect and 'safer'.
- return ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+ return ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength,
((ByteBufferExtendedCell)right).getRowByteBuffer(),
- ((ByteBufferExtendedCell)right).getRowPosition(), right.getRowLength());
+ ((ByteBufferExtendedCell)right).getRowPosition(), rightRowLength);
}
return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
right.getRowArray(), right.getRowOffset(), right.getRowLength());
@@ -261,10 +341,14 @@ public class CellComparatorImpl implements CellComparator {
}
// Compare cf:qualifier
int diff = compareColumns(left, right);
- if (diff != 0) return diff;
+ if (diff != 0) {
+ return diff;
+ }
diff = compareTimestamps(left, right);
- if (diff != 0) return diff;
+ if (diff != 0) {
+ return diff;
+ }
// Compare types. Let the delete types sort ahead of puts; i.e. types
// of higher numbers sort before those of lesser numbers. Maximum (255)
http://git-wip-us.apache.org/repos/asf/hbase/blob/db04a9f9/hbase-common/src/test/java/org/apache/hadoop/hbase/TestByteBufferKeyValue.java
----------------------------------------------------------------------
diff --git a/hbase-common/src/test/java/org/apache/hadoop/hbase/TestByteBufferKeyValue.java b/hbase-common/src/test/java/org/apache/hadoop/hbase/TestByteBufferKeyValue.java
index 172e36d..7069411 100644
--- a/hbase-common/src/test/java/org/apache/hadoop/hbase/TestByteBufferKeyValue.java
+++ b/hbase-common/src/test/java/org/apache/hadoop/hbase/TestByteBufferKeyValue.java
@@ -17,6 +17,7 @@
*/
package org.apache.hadoop.hbase;
+import static junit.framework.TestCase.assertTrue;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
@@ -58,6 +59,24 @@ public class TestByteBufferKeyValue {
}
@Test
+ public void testCompare() {
+ Cell cell1 = getOffheapCell(row1, fam1, qual1);
+ Cell cell2 = getOffheapCell(row1, fam1, qual2);
+ assertTrue(CellComparatorImpl.COMPARATOR.compare(cell1, cell2) < 0);
+ Cell cell3 = getOffheapCell(row1, Bytes.toBytes("wide_family"), qual2);
+ assertTrue(CellComparatorImpl.COMPARATOR.compare(cell1, cell3) < 0);
+ Cell cell4 = getOffheapCell(row1, Bytes.toBytes("f"), qual2);
+ assertTrue(CellComparatorImpl.COMPARATOR.compare(cell1, cell4) > 0);
+ }
+
+ private Cell getOffheapCell(byte [] row, byte [] family, byte [] qualifier) {
+ KeyValue kvCell = new KeyValue(row, family, qualifier, 0L, Type.Put, row);
+ ByteBuffer buf = ByteBuffer.allocateDirect(kvCell.getBuffer().length);
+ ByteBufferUtils.copyFromArrayToBuffer(buf, kvCell.getBuffer(), 0, kvCell.getBuffer().length);
+ return new ByteBufferKeyValue(buf, 0, buf.capacity(), 0L);
+ }
+
+ @Test
public void testByteBufferBackedKeyValue() throws Exception {
KeyValue kvCell = new KeyValue(row1, fam1, qual1, 0L, Type.Put, row1);
ByteBuffer buf = ByteBuffer.allocateDirect(kvCell.getBuffer().length);