hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From te...@apache.org
Subject hbase git commit: HBASE-16645 Wrong range of Cells is caused by CellFlatMap#tailMap, headMap, and SubMap (ChiaPing Tsai)
Date Sun, 25 Sep 2016 13:42:39 GMT
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 <yuzhihong@gmail.com>
Authored: Sun Sep 25 06:42:32 2016 -0700
Committer: tedyu <yuzhihong@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);


Mime
View raw message