You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by te...@apache.org on 2016/09/25 13:42:39 UTC
hbase git commit: HBASE-16645 Wrong range of Cells is caused by
CellFlatMap#tailMap, headMap, and SubMap (ChiaPing Tsai)
Repository: hbase
Updated Branches:
refs/heads/master 3896d9ed0 -> b7e0e1578
HBASE-16645 Wrong range of Cells is caused by CellFlatMap#tailMap, headMap, and SubMap (ChiaPing Tsai)
Project: http://git-wip-us.apache.org/repos/asf/hbase/repo
Commit: http://git-wip-us.apache.org/repos/asf/hbase/commit/b7e0e157
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/b7e0e157
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/b7e0e157
Branch: refs/heads/master
Commit: b7e0e1578717709fc564832e95fac64a325da6aa
Parents: 3896d9e
Author: tedyu <yu...@gmail.com>
Authored: Sun Sep 25 06:42:32 2016 -0700
Committer: tedyu <yu...@gmail.com>
Committed: Sun Sep 25 06:42:32 2016 -0700
----------------------------------------------------------------------
.../hadoop/hbase/regionserver/CellFlatMap.java | 100 +++++++-------
.../hadoop/hbase/regionserver/CellSet.java | 6 +
.../hbase/regionserver/TestCellFlatSet.java | 130 ++++++++++++++-----
3 files changed, 154 insertions(+), 82 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/hbase/blob/b7e0e157/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellFlatMap.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellFlatMap.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellFlatMap.java
index 6d26785..c83a382 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellFlatMap.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellFlatMap.java
@@ -28,6 +28,8 @@ import java.util.Map;
import java.util.NavigableSet;
import java.util.NavigableMap;
import java.util.Set;
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
/**
@@ -42,7 +44,7 @@ import java.util.Set;
*/
@InterfaceAudience.Private
public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
-
+ private static final Log LOG = LogFactory.getLog(CellFlatMap.class);
private final Comparator<? super Cell> comparator;
protected int minCellIdx = 0; // the index of the minimal cell (for sub-sets)
protected int maxCellIdx = 0; // the index of the cell after the maximal cell (for sub-sets)
@@ -88,8 +90,9 @@ public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
if (compareRes == 0) {
return mid; // 0 means equals. We found the key
}
-
- if (compareRes < 0) {
+ // Key not found. Check the comparison results; reverse the meaning of
+ // the comparison in case the order is descending (using XOR)
+ if ((compareRes < 0) ^ descending) {
// midCell is less than needle so we need to look at farther up
begin = mid + 1;
} else {
@@ -101,37 +104,37 @@ public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
return (-1 * begin)-1;
}
- /* Get the index of the given anchor key for creating subsequent set.
- ** It doesn't matter whether the given key exists in the set or not.
- **
- ** taking into consideration whether
- ** the key should be inclusive or exclusive */
+ /**
+ * Get the index of the given anchor key for creating subsequent set.
+ * It doesn't matter whether the given key exists in the set or not.
+ * taking into consideration whether
+ * the key should be inclusive or exclusive.
+ */
private int getValidIndex(Cell key, boolean inclusive, boolean tail) {
- int index = find(key);
- int result = -1;
-
- // if the key is found and to be included, for all possibilities, the answer is the found index
- if (index >= 0 && inclusive) result = index;
-
- // The compliment Operator (~) converts the returned insertion point to the real one
- if (index<0) result = ~index;
-
- if (tail && result==-1) {
- if (index >= 0 && !inclusive)
- result = (descending) ? index - 1 : index + 1;
- } else if (result==-1) {
- if (index >= 0 && !inclusive)
- result = (descending) ? index + 1 : index - 1;
- }
-
- if (result < minCellIdx || result > maxCellIdx) {
- throw new IllegalArgumentException("Index " + result + " (initial index " + index + ") "
- + " out of boundary, when looking for key " + key + ". The minCellIdx is " + minCellIdx
- + " and the maxCellIdx is " + maxCellIdx + ". Finally, descending? " + descending
- + " and was the key requested inclusively? " + inclusive);
+ final int index = find(key);
+ // get the valid (positive) insertion point from the output of the find() method
+ int insertionPoint = index < 0 ? ~index : index;
+
+ // correct the insertion point in case the given anchor key DOES EXIST in the set
+ if (index >= 0) {
+ if ( descending && !(tail ^ inclusive)) {
+ // for the descending case
+ // if anchor for head set (tail=false) AND anchor is not inclusive -> move the insertion pt
+ // if anchor for tail set (tail=true) AND the keys is inclusive -> move the insertion point
+ // because the end index of a set is the index of the cell after the maximal cell
+ insertionPoint += 1;
+ } else if ( !descending && (tail ^ inclusive)) {
+ // for the ascending case
+ // if anchor for head set (tail=false) AND anchor is inclusive -> move the insertion point
+ // because the end index of a set is the index of the cell after the maximal cell
+ // if anchor for tail set (tail=true) AND the keys is not inclusive -> move the insertion pt
+ insertionPoint += 1;
+ }
}
- return result;
- }
+ // insert the insertion point into the valid range,
+ // as we may enlarge it too much in the above correction
+ return Math.min(Math.max(insertionPoint, minCellIdx), maxCellIdx);
+}
@Override
public Comparator<? super Cell> comparator() {
@@ -155,27 +158,31 @@ public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
boolean fromInclusive,
Cell toKey,
boolean toInclusive) {
- int toIndex = getValidIndex(toKey, toInclusive, false);
- int fromIndex = (getValidIndex(fromKey, fromInclusive, true));
-
- if (fromIndex > toIndex) {
- throw new IllegalArgumentException("Inconsistent range, when looking from "
- + fromKey + " to " + toKey);
+ final int lessCellIndex = getValidIndex(fromKey, fromInclusive, true);
+ final int greaterCellIndex = getValidIndex(toKey, toInclusive, false);
+ if (descending) {
+ return createSubCellFlatMap(greaterCellIndex, lessCellIndex, descending);
+ } else {
+ return createSubCellFlatMap(lessCellIndex, greaterCellIndex, descending);
}
- return createSubCellFlatMap(fromIndex, toIndex+1, descending);
}
@Override
public NavigableMap<Cell, Cell> headMap(Cell toKey, boolean inclusive) {
- int index = getValidIndex(toKey, inclusive, false);
- // "+1" because the max index is one after the true index
- return createSubCellFlatMap(minCellIdx, index+1, descending);
+ if (descending) {
+ return createSubCellFlatMap(getValidIndex(toKey, inclusive, false), maxCellIdx, descending);
+ } else {
+ return createSubCellFlatMap(minCellIdx, getValidIndex(toKey, inclusive, false), descending);
+ }
}
@Override
public NavigableMap<Cell, Cell> tailMap(Cell fromKey, boolean inclusive) {
- int index = (getValidIndex(fromKey, inclusive, true));
- return createSubCellFlatMap(index, maxCellIdx, descending);
+ if (descending) {
+ return createSubCellFlatMap(minCellIdx, getValidIndex(fromKey, inclusive, true), descending);
+ } else {
+ return createSubCellFlatMap(getValidIndex(fromKey, inclusive, true), maxCellIdx, descending);
+ }
}
@Override
@@ -403,7 +410,7 @@ public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
private final class CellFlatMapCollection implements Collection<Cell> {
@Override
- public int size() {
+ public int size() {
return CellFlatMap.this.size();
}
@@ -466,8 +473,5 @@ public abstract class CellFlatMap implements NavigableMap<Cell,Cell> {
public boolean retainAll(Collection<?> collection) {
throw new UnsupportedOperationException();
}
-
-
}
-
}
http://git-wip-us.apache.org/repos/asf/hbase/blob/b7e0e157/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellSet.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellSet.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellSet.java
index 6f70bac..531bf66 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellSet.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/CellSet.java
@@ -18,6 +18,7 @@
*/
package org.apache.hadoop.hbase.regionserver;
+import com.google.common.annotations.VisibleForTesting;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
@@ -54,6 +55,11 @@ public class CellSet implements NavigableSet<Cell> {
this.delegatee = m;
}
+ @VisibleForTesting
+ NavigableMap<Cell, Cell> getDelegatee() {
+ return delegatee;
+ }
+
public Cell ceiling(Cell e) {
throw new UnsupportedOperationException("Not implemented");
}
http://git-wip-us.apache.org/repos/asf/hbase/blob/b7e0e157/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCellFlatSet.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCellFlatSet.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCellFlatSet.java
index cd5788e..2905a5b 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCellFlatSet.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/regionserver/TestCellFlatSet.java
@@ -18,31 +18,37 @@
*/
package org.apache.hadoop.hbase.regionserver;
+import java.util.Iterator;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.SortedSet;
import junit.framework.TestCase;
import org.apache.hadoop.conf.Configuration;
-import org.apache.hadoop.hbase.*;
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellComparator;
+import org.apache.hadoop.hbase.CellUtil;
+import org.apache.hadoop.hbase.KeyValue;
import org.apache.hadoop.hbase.testclassification.RegionServerTests;
import org.apache.hadoop.hbase.testclassification.SmallTests;
import org.apache.hadoop.hbase.util.Bytes;
+import org.junit.Test;
import org.junit.experimental.categories.Category;
-import java.util.Iterator;
-import java.util.NavigableMap;
-import java.util.SortedSet;
-import static org.junit.Assert.assertTrue;
+
@Category({RegionServerTests.class, SmallTests.class})
public class TestCellFlatSet extends TestCase {
-
private static final int NUM_OF_CELLS = 4;
-
- private Cell cells[];
- private CellArrayMap cbOnHeap;
-
- private final static Configuration conf = new Configuration();
+ private Cell ascCells[];
+ private CellArrayMap ascCbOnHeap;
+ private Cell descCells[];
+ private CellArrayMap descCbOnHeap;
+ private final static Configuration CONF = new Configuration();
private HeapMemStoreLAB mslab;
+ private KeyValue lowerOuterCell;
+ private KeyValue upperOuterCell;
-
+ @Override
protected void setUp() throws Exception {
super.setUp();
@@ -60,22 +66,78 @@ public class TestCellFlatSet extends TestCase {
final KeyValue kv2 = new KeyValue(two, f, q, 20, v);
final KeyValue kv3 = new KeyValue(three, f, q, 30, v);
final KeyValue kv4 = new KeyValue(four, f, q, 40, v);
-
- cells = new Cell[] {kv1,kv2,kv3,kv4};
- cbOnHeap = new CellArrayMap(CellComparator.COMPARATOR,cells,0,NUM_OF_CELLS,false);
-
- conf.setBoolean(SegmentFactory.USEMSLAB_KEY, true);
- conf.setFloat(MemStoreChunkPool.CHUNK_POOL_MAXSIZE_KEY, 0.2f);
+ lowerOuterCell = new KeyValue(Bytes.toBytes(10), f, q, 10, v);
+ upperOuterCell = new KeyValue(Bytes.toBytes(50), f, q, 10, v);
+ ascCells = new Cell[] {kv1,kv2,kv3,kv4};
+ ascCbOnHeap = new CellArrayMap(CellComparator.COMPARATOR,ascCells,0,NUM_OF_CELLS,false);
+ descCells = new Cell[] {kv4,kv3,kv2,kv1};
+ descCbOnHeap = new CellArrayMap(CellComparator.COMPARATOR,descCells,0,NUM_OF_CELLS,true);
+ CONF.setBoolean(SegmentFactory.USEMSLAB_KEY, true);
+ CONF.setFloat(MemStoreChunkPool.CHUNK_POOL_MAXSIZE_KEY, 0.2f);
MemStoreChunkPool.chunkPoolDisabled = false;
- mslab = new HeapMemStoreLAB(conf);
+ mslab = new HeapMemStoreLAB(CONF);
}
/* Create and test CellSet based on CellArrayMap */
public void testCellBlocksOnHeap() throws Exception {
- CellSet cs = new CellSet(cbOnHeap);
+ CellSet cs = new CellSet(ascCbOnHeap);
testCellBlocks(cs);
testIterators(cs);
}
+ @Test
+ public void testAsc() throws Exception {
+ CellSet ascCs = new CellSet(ascCbOnHeap);
+ assertEquals(NUM_OF_CELLS, ascCs.size());
+ testSubSet(ascCs);
+ }
+ @Test
+ public void testDesc() throws Exception {
+ CellSet descCs = new CellSet(descCbOnHeap);
+ assertEquals(NUM_OF_CELLS, descCs.size());
+ testSubSet(descCs);
+ }
+
+ private void testSubSet(CellSet cs) throws Exception {
+ for (int i = 0; i != ascCells.length; ++i) {
+ NavigableSet<Cell> excludeTail = cs.tailSet(ascCells[i], false);
+ NavigableSet<Cell> includeTail = cs.tailSet(ascCells[i], true);
+ assertEquals(ascCells.length - 1 - i, excludeTail.size());
+ assertEquals(ascCells.length - i, includeTail.size());
+ Iterator<Cell> excludeIter = excludeTail.iterator();
+ Iterator<Cell> includeIter = includeTail.iterator();
+ for (int j = 1 + i; j != ascCells.length; ++j) {
+ assertEquals(true, CellUtil.equals(excludeIter.next(), ascCells[j]));
+ }
+ for (int j = i; j != ascCells.length; ++j) {
+ assertEquals(true, CellUtil.equals(includeIter.next(), ascCells[j]));
+ }
+ }
+ assertEquals(NUM_OF_CELLS, cs.tailSet(lowerOuterCell, false).size());
+ assertEquals(0, cs.tailSet(upperOuterCell, false).size());
+ for (int i = 0; i != ascCells.length; ++i) {
+ NavigableSet<Cell> excludeHead = cs.headSet(ascCells[i], false);
+ NavigableSet<Cell> includeHead = cs.headSet(ascCells[i], true);
+ assertEquals(i, excludeHead.size());
+ assertEquals(i + 1, includeHead.size());
+ Iterator<Cell> excludeIter = excludeHead.iterator();
+ Iterator<Cell> includeIter = includeHead.iterator();
+ for (int j = 0; j != i; ++j) {
+ assertEquals(true, CellUtil.equals(excludeIter.next(), ascCells[j]));
+ }
+ for (int j = 0; j != i + 1; ++j) {
+ assertEquals(true, CellUtil.equals(includeIter.next(), ascCells[j]));
+ }
+ }
+ assertEquals(0, cs.headSet(lowerOuterCell, false).size());
+ assertEquals(NUM_OF_CELLS, cs.headSet(upperOuterCell, false).size());
+
+ NavigableMap<Cell, Cell> sub = cs.getDelegatee().subMap(lowerOuterCell, true, upperOuterCell, true);
+ assertEquals(NUM_OF_CELLS, sub.size());
+ Iterator<Cell> iter = sub.values().iterator();
+ for (int i = 0; i != ascCells.length; ++i) {
+ assertEquals(true, CellUtil.equals(iter.next(), ascCells[i]));
+ }
+ }
/* Generic basic test for immutable CellSet */
private void testCellBlocks(CellSet cs) throws Exception {
@@ -88,31 +150,31 @@ public class TestCellFlatSet extends TestCase {
assertEquals(NUM_OF_CELLS, cs.size()); // check size
assertFalse(cs.contains(outerCell)); // check outer cell
- assertTrue(cs.contains(cells[0])); // check existence of the first
+ assertTrue(cs.contains(ascCells[0])); // check existence of the first
Cell first = cs.first();
- assertTrue(cells[0].equals(first));
+ assertTrue(ascCells[0].equals(first));
- assertTrue(cs.contains(cells[NUM_OF_CELLS - 1])); // check last
+ assertTrue(cs.contains(ascCells[NUM_OF_CELLS - 1])); // check last
Cell last = cs.last();
- assertTrue(cells[NUM_OF_CELLS - 1].equals(last));
+ assertTrue(ascCells[NUM_OF_CELLS - 1].equals(last));
- SortedSet<Cell> tail = cs.tailSet(cells[1]); // check tail abd head sizes
+ SortedSet<Cell> tail = cs.tailSet(ascCells[1]); // check tail abd head sizes
assertEquals(NUM_OF_CELLS - 1, tail.size());
- SortedSet<Cell> head = cs.headSet(cells[1]);
+ SortedSet<Cell> head = cs.headSet(ascCells[1]);
assertEquals(1, head.size());
SortedSet<Cell> tailOuter = cs.tailSet(outerCell); // check tail starting from outer cell
assertEquals(NUM_OF_CELLS - 1, tailOuter.size());
Cell tailFirst = tail.first();
- assertTrue(cells[1].equals(tailFirst));
+ assertTrue(ascCells[1].equals(tailFirst));
Cell tailLast = tail.last();
- assertTrue(cells[NUM_OF_CELLS - 1].equals(tailLast));
+ assertTrue(ascCells[NUM_OF_CELLS - 1].equals(tailLast));
Cell headFirst = head.first();
- assertTrue(cells[0].equals(headFirst));
+ assertTrue(ascCells[0].equals(headFirst));
Cell headLast = head.last();
- assertTrue(cells[0].equals(headLast));
+ assertTrue(ascCells[0].equals(headLast));
}
/* Generic iterators test for immutable CellSet */
@@ -123,10 +185,10 @@ public class TestCellFlatSet extends TestCase {
for (Cell kv: cs) {
assertEquals("\n\n-------------------------------------------------------------------\n"
+ "Comparing iteration number " + (count + 1) + " the returned cell: " + kv
- + ", the first Cell in the CellBlocksMap: " + cells[count]
- + ", and the same transformed to String: " + cells[count].toString()
+ + ", the first Cell in the CellBlocksMap: " + ascCells[count]
+ + ", and the same transformed to String: " + ascCells[count].toString()
+ "\n-------------------------------------------------------------------\n",
- cells[count], kv);
+ ascCells[count], kv);
count++;
}
assertEquals(NUM_OF_CELLS, count);
@@ -135,7 +197,7 @@ public class TestCellFlatSet extends TestCase {
count = 0;
for (Iterator<Cell> i = cs.descendingIterator(); i.hasNext();) {
Cell kv = i.next();
- assertEquals(cells[NUM_OF_CELLS - (count + 1)], kv);
+ assertEquals(ascCells[NUM_OF_CELLS - (count + 1)], kv);
count++;
}
assertEquals(NUM_OF_CELLS, count);