hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bryanduxb...@apache.org
Subject svn commit: r638598 - in /hadoop/hbase/trunk: ./ src/java/org/apache/hadoop/hbase/client/ src/java/org/apache/hadoop/hbase/ipc/ src/java/org/apache/hadoop/hbase/regionserver/ src/test/org/apache/hadoop/hbase/regionserver/
Date Tue, 18 Mar 2008 21:48:37 GMT
Author: bryanduxbury
Date: Tue Mar 18 14:48:22 2008
New Revision: 638598

URL: http://svn.apache.org/viewvc?rev=638598&view=rev
Log:
HBASE-528 table 'does not exist' when it does
-Changed HStore and Memcache methods for computing closest row at or before
-Added more test cases for verifying this functionality
-Simplified the getClosestRowBefore interface so that it does not take timestamps
-Noted that getClosestRowBefore is assumed to work correctly ONLY on tables where updates
are always with ascending timestamps (method is still not a part of HTable interface, so not
available to clients)

Modified:
    hadoop/hbase/trunk/CHANGES.txt
    hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/client/HConnectionManager.java
    hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/ipc/HRegionInterface.java
    hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegion.java
    hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
    hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HStore.java
    hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/Memcache.java
    hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestGet2.java
    hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestHMemcache.java

Modified: hadoop/hbase/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/CHANGES.txt?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/CHANGES.txt (original)
+++ hadoop/hbase/trunk/CHANGES.txt Tue Mar 18 14:48:22 2008
@@ -46,6 +46,7 @@
                the top region of a split region
    HBASE-525   HTable.getRow(Text) does not work (Clint Morgan via Bryan Duxbury)
    HBASE-524   Problems with getFull
+   HBASE-528   table 'does not exist' when it does
    
   IMPROVEMENTS
    HBASE-415   Rewrite leases to use DelayedBlockingQueue instead of polling

Modified: hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/client/HConnectionManager.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/client/HConnectionManager.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/client/HConnectionManager.java (original)
+++ hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/client/HConnectionManager.java Tue
Mar 18 14:48:22 2008
@@ -413,8 +413,7 @@
 
           // query the root region for the location of the meta region
           HbaseMapWritable regionInfoRow = server.getClosestRowBefore(
-            metaLocation.getRegionInfo().getRegionName(), 
-            metaKey, HConstants.LATEST_TIMESTAMP);
+            metaLocation.getRegionInfo().getRegionName(), metaKey);
 
           if (regionInfoRow == null) {
             throw new TableNotFoundException("Table '" + tableName + 

Modified: hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/ipc/HRegionInterface.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/ipc/HRegionInterface.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/ipc/HRegionInterface.java (original)
+++ hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/ipc/HRegionInterface.java Tue Mar
18 14:48:22 2008
@@ -116,20 +116,6 @@
   throws IOException;
 
   /**
-   * Return all the data for the row that matches <i>row</i> exactly, 
-   * or the one that immediately preceeds it, at or immediately before 
-   * <i>ts</i>.
-   * 
-   * @param regionName region name
-   * @param row row key
-   * @return map of values
-   * @throws IOException
-   */
-  public HbaseMapWritable getClosestRowBefore(final Text regionName, 
-    final Text row, final long ts)
-  throws IOException;
-
-  /**
    * Get selected columns for the specified row at a given timestamp.
    * 
    * @param regionName region name

Modified: hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegion.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegion.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegion.java (original)
+++ hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegion.java Tue Mar
18 14:48:22 2008
@@ -1111,7 +1111,7 @@
    * @return map of values
    * @throws IOException
    */
-  public Map<Text, Cell> getClosestRowBefore(final Text row, final long ts)
+  public Map<Text, Cell> getClosestRowBefore(final Text row)
   throws IOException{
     // look across all the HStores for this region and determine what the
     // closest key is across all column families, since the data may be sparse
@@ -1125,18 +1125,18 @@
         HStore store = stores.get(colFamily);
 
         // get the closest key
-        Text closestKey = store.getRowKeyAtOrBefore(row, ts);
+        Text closestKey = store.getRowKeyAtOrBefore(row);
         
         // if it happens to be an exact match, we can stop looping
         if (row.equals(closestKey)) {
-          key = new HStoreKey(closestKey, ts);
+          key = new HStoreKey(closestKey);
           break;
         }
 
         // otherwise, we need to check if it's the max and move to the next
         if (closestKey != null 
           && (key == null || closestKey.compareTo(key.getRow()) > 0) ) {
-          key = new HStoreKey(closestKey, ts);
+          key = new HStoreKey(closestKey);
         }
       }
 

Modified: hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java (original)
+++ hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HRegionServer.java Tue
Mar 18 14:48:22 2008
@@ -988,13 +988,6 @@
   public HbaseMapWritable getClosestRowBefore(final Text regionName, 
     final Text row)
   throws IOException {
-    return getClosestRowBefore(regionName, row, HConstants.LATEST_TIMESTAMP);
-  }
-
-  /** {@inheritDoc} */
-  public HbaseMapWritable getClosestRowBefore(final Text regionName, 
-    final Text row, final long ts)
-  throws IOException {
     checkOpen();
     requestCount.incrementAndGet();
     try {
@@ -1002,7 +995,7 @@
       HRegion region = getRegion(regionName);
       HbaseMapWritable result = new HbaseMapWritable();
       // ask the region for all the data 
-      Map<Text, Cell> map = region.getClosestRowBefore(row, ts);
+      Map<Text, Cell> map = region.getClosestRowBefore(row);
       // convert to a MapWritable
       if (map == null) {
         return null;

Modified: hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HStore.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HStore.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HStore.java (original)
+++ hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/HStore.java Tue Mar 18
14:48:22 2008
@@ -30,6 +30,8 @@
 import java.util.Set;
 import java.util.SortedMap;
 import java.util.TreeMap;
+import java.util.SortedSet;
+import java.util.TreeSet;
 import java.util.Map.Entry;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.locks.ReentrantReadWriteLock;
@@ -1311,53 +1313,38 @@
   }
   
   /**
-   * @return the key that matches <i>row</i> exactly, or the one that immediately
-   * preceeds it.
-   * @param row
-   * @param timestamp
-   * @throws IOException
+   * Find the key that matches <i>row</i> exactly, or the one that immediately
+   * preceeds it. WARNING: Only use this method on a table where writes occur 
+   * with stricly increasing timestamps. This method assumes this pattern of 
+   * writes in order to make it reasonably performant. 
    */
-  public Text getRowKeyAtOrBefore(final Text row, final long timestamp)
+  Text getRowKeyAtOrBefore(final Text row)
   throws IOException{
-    // if the exact key is found, return that key
-    // if we find a key that is greater than our search key, then use the 
-    // last key we processed, and if that was null, return null.
-
-    Text foundKey = memcache.getRowKeyAtOrBefore(row, timestamp);
-    if (foundKey != null) {
-      return foundKey;
-    }
+    // map of HStoreKeys that are candidates for holding the row key that
+    // most closely matches what we're looking for. we'll have to update it 
+    // deletes found all over the place as we go along before finally reading
+    // the best key out of it at the end.
+    SortedMap<HStoreKey, Long> candidateKeys = new TreeMap<HStoreKey, Long>();
   
     
     // obtain read lock
     this.lock.readLock().lock();
     try {
       MapFile.Reader[] maparray = getReaders();
       
-      Text bestSoFar = null;
-
       // process each store file
       for(int i = maparray.length - 1; i >= 0; i--) {
-        Text row_from_mapfile = 
-          rowAtOrBeforeFromMapFile(maparray[i], row, timestamp);
-        
-        // if the result from the mapfile is null, then we know that
-        // the mapfile was empty and can move on to the next one.
-        if (row_from_mapfile == null) {
-          continue;
-        }
-      
-        // short circuit on an exact match
-        if (row.equals(row_from_mapfile)) {
-          return row;
-        }
-        
-        // check to see if we've found a new closest row key as a result
-        if (bestSoFar == null || bestSoFar.compareTo(row_from_mapfile) < 0) {
-          bestSoFar = row_from_mapfile;
-        }
+        // update the candidate keys from the current map file
+        rowAtOrBeforeFromMapFile(maparray[i], row, candidateKeys);
       }
       
-      return bestSoFar;
+      // finally, check the memcache
+      memcache.getRowKeyAtOrBefore(row, candidateKeys);
+      
+      // return the best key from candidateKeys
+      if (!candidateKeys.isEmpty()) {
+        return candidateKeys.lastKey().getRow();
+      } 
+      return null;
     } finally {
       this.lock.readLock().unlock();
     }
@@ -1367,68 +1354,159 @@
    * Check an individual MapFile for the row at or before a given key 
    * and timestamp
    */
-  private Text rowAtOrBeforeFromMapFile(MapFile.Reader map, Text row, 
-    long timestamp)
+  private void rowAtOrBeforeFromMapFile(MapFile.Reader map, Text row, 
+    SortedMap<HStoreKey, Long> candidateKeys)
   throws IOException {
-    HStoreKey searchKey = new HStoreKey(row, timestamp);
-    Text previousRow = null;
+    HStoreKey searchKey = null;
     ImmutableBytesWritable readval = new ImmutableBytesWritable();
     HStoreKey readkey = new HStoreKey();
+    HStoreKey strippedKey = null;
     
     synchronized(map) {
       // don't bother with the rest of this if the file is empty
       map.reset();
       if (!map.next(readkey, readval)) {
-        return null;
+        return;
       }
       
-      HStoreKey finalKey = new HStoreKey(); 
-      map.finalKey(finalKey);
-      if (finalKey.getRow().compareTo(row) < 0) {
-        return finalKey.getRow();
+      // if there aren't any candidate keys yet, we'll do some things slightly
+      // different 
+      if (candidateKeys.isEmpty()) {
+        searchKey = new HStoreKey(row);
+        
+        // if the row we're looking for is past the end of this mapfile, just
+        // save time and add the last key to the candidates.
+        HStoreKey finalKey = new HStoreKey(); 
+        map.finalKey(finalKey);
+        if (finalKey.getRow().compareTo(row) < 0) {
+          candidateKeys.put(stripTimestamp(finalKey), 
+            new Long(finalKey.getTimestamp()));
+          return;
+        }
+        
+        // seek to the exact row, or the one that would be immediately before it
+        readkey = (HStoreKey)map.getClosest(searchKey, readval, true);
+      
+        if (readkey == null) {
+          // didn't find anything that would match, so return
+          return;
+        }
+      
+        do {
+          // if we have an exact match on row, and it's not a delete, save this
+          // as a candidate key
+          if (readkey.getRow().equals(row)) {
+            if (!HLogEdit.isDeleted(readval.get())) {
+              candidateKeys.put(stripTimestamp(readkey), 
+                new Long(readkey.getTimestamp()));
+            }
+          } else if (readkey.getRow().compareTo(row) > 0 ) {
+            // if the row key we just read is beyond the key we're searching for,
+            // then we're done. return.
+            return;
+          } else {
+            // so, the row key doesn't match, but we haven't gone past the row
+            // we're seeking yet, so this row is a candidate for closest
+            // (assuming that it isn't a delete).
+            if (!HLogEdit.isDeleted(readval.get())) {
+              candidateKeys.put(stripTimestamp(readkey), 
+                new Long(readkey.getTimestamp()));
+            }
+          }        
+        } while(map.next(readkey, readval));
+      
+        // arriving here just means that we consumed the whole rest of the map
+        // without going "past" the key we're searching for. we can just fall
+        // through here.
+      } else {
+        // if there are already candidate keys, we need to start our search 
+        // at the earliest possible key so that we can discover any possible
+        // deletes for keys between the start and the search key.
+        searchKey = new HStoreKey(candidateKeys.firstKey().getRow());
+              
+        // if the row we're looking for is past the end of this mapfile, just
+        // save time and add the last key to the candidates.
+        HStoreKey finalKey = new HStoreKey(); 
+        map.finalKey(finalKey);
+        if (finalKey.getRow().compareTo(searchKey.getRow()) < 0) {
+          strippedKey = stripTimestamp(finalKey);
+          
+          // if the candidate keys has a cell like this one already,
+          // then we might want to update the timestamp we're using on it
+          if (candidateKeys.containsKey(strippedKey)) {
+            long bestCandidateTs = 
+              candidateKeys.get(strippedKey).longValue();
+            if (bestCandidateTs < finalKey.getTimestamp()) {
+              candidateKeys.put(strippedKey, new Long(finalKey.getTimestamp()));
+            } 
+          } else {
+            // otherwise, this is a new key, so put it up as a candidate
+            candidateKeys.put(strippedKey, new Long(finalKey.getTimestamp()));
+          }
+        }
+        return;
       }
       
       // seek to the exact row, or the one that would be immediately before it
       readkey = (HStoreKey)map.getClosest(searchKey, readval, true);
       
       if (readkey == null) {
-        // didn't find anything that would match, so returns
-        return null;
+        // didn't find anything that would match, so return
+        return;
       }
       
       do {
-        if (readkey.getRow().compareTo(row) == 0) {
-          // exact match on row
-          if (readkey.getTimestamp() <= timestamp) {
-            // timestamp fits, return this key
-            return readkey.getRow();
+        // if we have an exact match on row, and it's not a delete, save this
+        // as a candidate key
+        if (readkey.getRow().equals(row)) {
+          strippedKey = stripTimestamp(readkey);
+          if (!HLogEdit.isDeleted(readval.get())) {
+            candidateKeys.put(strippedKey, new Long(readkey.getTimestamp()));
+          } else {
+            // if the candidate keys contain any that might match by timestamp,
+            // then check for a match and remove it if it's too young to 
+            // survive the delete 
+            if (candidateKeys.containsKey(strippedKey)) {
+              long bestCandidateTs =
+                candidateKeys.get(strippedKey).longValue();
+              if (bestCandidateTs <= readkey.getTimestamp()) {
+                candidateKeys.remove(strippedKey);
+              } 
+            }
           }
-          // getting here means that we matched the row, but the timestamp
-          // is too recent - hopefully one of the next cells will match
-          // better, so keep rolling
-          continue;
-        } else if (readkey.getRow().toString().compareTo(row.toString()) > 0 ) {
+        } else if (readkey.getRow().compareTo(row) > 0 ) {
           // if the row key we just read is beyond the key we're searching for,
-          // then we're done; return the last key we saw before this one
-          return previousRow;
+          // then we're done. return.
+          return;
         } else {
-          // so, the row key doesn't match, and we haven't gone past the row
-          // we're seeking yet, so this row is a candidate for closest, as
-          // long as the timestamp is correct.
-          if (readkey.getTimestamp() <= timestamp) {
-            previousRow = new Text(readkey.getRow());
-          }
-          // otherwise, ignore this key, because it doesn't fulfill our 
-          // requirements.
-        }        
+          strippedKey = stripTimestamp(readkey);
+          
+          // so, the row key doesn't match, but we haven't gone past the row
+          // we're seeking yet, so this row is a candidate for closest 
+          // (assuming that it isn't a delete).
+          if (!HLogEdit.isDeleted(readval.get())) {
+            candidateKeys.put(strippedKey, readkey.getTimestamp());
+          } else {
+            // if the candidate keys contain any that might match by timestamp,
+            // then check for a match and remove it if it's too young to 
+            // survive the delete 
+            if (candidateKeys.containsKey(strippedKey)) {
+              long bestCandidateTs = 
+                candidateKeys.get(strippedKey).longValue();
+              if (bestCandidateTs <= readkey.getTimestamp()) {
+                candidateKeys.remove(strippedKey);
+              } 
+            }
+          }      
+        }
       } while(map.next(readkey, readval));
     }
-    // getting here means we exhausted all of the cells in the mapfile.
-    // whatever satisfying row we reached previously is the row we should 
-    // return
-    return previousRow;
   }
   
+  static HStoreKey stripTimestamp(HStoreKey key) {
+    return new HStoreKey(key.getRow(), key.getColumn());
+  }
+    
   /**
    * Test that the <i>target</i> matches the <i>origin</i>. If the

    * <i>origin</i> has an empty column, then it's assumed to mean any column


Modified: hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/Memcache.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/Memcache.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/Memcache.java (original)
+++ hadoop/hbase/trunk/src/java/org/apache/hadoop/hbase/regionserver/Memcache.java Tue Mar
18 14:48:22 2008
@@ -199,82 +199,134 @@
    * @return the key that matches <i>row</i> exactly, or the one that
    * immediately preceeds it.
    */
-  public Text getRowKeyAtOrBefore(final Text row, long timestamp) {
+  void getRowKeyAtOrBefore(final Text row, 
+    SortedMap<HStoreKey, Long> candidateKeys)
+  throws IOException {
     this.lock.readLock().lock();
     
-    Text key_memcache = null;
-    Text key_snapshot = null;
-    
     try {
       synchronized (memcache) {
-        key_memcache = internalGetRowKeyAtOrBefore(memcache, row, timestamp);
+        internalGetRowKeyAtOrBefore(memcache, row, candidateKeys);
       }
       synchronized (snapshot) {
-        key_snapshot = internalGetRowKeyAtOrBefore(snapshot, row, timestamp);
-      }
-
-      if (key_memcache == null && key_snapshot == null) {
-        // didn't find any candidates, return null
-        return null;
-      } else if (key_memcache == null && key_snapshot != null) {
-        return key_snapshot;
-      } else if (key_memcache != null && key_snapshot == null) {
-        return key_memcache;
-      } else if ( (key_memcache != null && key_memcache.equals(row)) 
-          || (key_snapshot != null && key_snapshot.equals(row)) ) {
-        // if either is a precise match, return the original row.
-        return row;
-      } else if (key_memcache != null) {
-        // no precise matches, so return the one that is closer to the search
-        // key (greatest)
-        return key_memcache.compareTo(key_snapshot) > 0 ? 
-            key_memcache : key_snapshot;
+        internalGetRowKeyAtOrBefore(snapshot, row, candidateKeys);
       }
-      return null;
     } finally {
       this.lock.readLock().unlock();
     }
   }
 
-  private Text internalGetRowKeyAtOrBefore(SortedMap<HStoreKey, byte []> map, 
-    Text key, long timestamp) {
-    // TODO: account for deleted cells
-
-    HStoreKey search_key = new HStoreKey(key, timestamp);
-
+  private void internalGetRowKeyAtOrBefore(SortedMap<HStoreKey, byte []> map,
+    Text key, SortedMap<HStoreKey, Long> candidateKeys) {
+    
+    HStoreKey strippedKey = null;
+    
+    // we want the earliest possible to start searching from
+    HStoreKey search_key = candidateKeys.isEmpty() ? 
+      new HStoreKey(key) : new HStoreKey(candidateKeys.firstKey().getRow());
+        
+    Iterator<HStoreKey> key_iterator = null;
+    HStoreKey found_key = null;
+    
     // get all the entries that come equal or after our search key
     SortedMap<HStoreKey, byte []> tailMap = map.tailMap(search_key);
+    
+    // if there are items in the tail map, there's either a direct match to
+    // the search key, or a range of values between the first candidate key
+    // and the ultimate search key (or the end of the cache)
+    if (!tailMap.isEmpty() && tailMap.firstKey().getRow().compareTo(key) <= 0)
{
+      key_iterator = tailMap.keySet().iterator();
 
-    // if the first item in the tail has a matching row, then we have an 
-    // exact match, and we should return that item
-    if (!tailMap.isEmpty() && tailMap.firstKey().getRow().equals(key)) {
-      // seek forward past any cells that don't fulfill the timestamp
-      // argument
-      Iterator<HStoreKey> key_iterator = tailMap.keySet().iterator();
-      HStoreKey found_key = key_iterator.next();
-      
-      // keep seeking so long as we're in the same row, and the timstamp
-      // isn't as small as we'd like, and there are more cells to check
-      while (found_key.getRow().equals(key)
-        && found_key.getTimestamp() > timestamp && key_iterator.hasNext())
{
+      // keep looking at cells as long as they are no greater than the 
+      // ultimate search key and there's still records left in the map.
+      do {
         found_key = key_iterator.next();
-      }
+        if (found_key.getRow().compareTo(key) <= 0) {
+          strippedKey = stripTimestamp(found_key);
+          if (HLogEdit.isDeleted(tailMap.get(found_key))) {
+            if (candidateKeys.containsKey(strippedKey)) {
+              long bestCandidateTs = 
+                candidateKeys.get(strippedKey).longValue();
+              if (bestCandidateTs <= found_key.getTimestamp()) {
+                candidateKeys.remove(strippedKey);
+              }
+            }
+          } else {
+            candidateKeys.put(strippedKey, 
+              new Long(found_key.getTimestamp()));
+          }
+        }
+      } while (found_key.getRow().compareTo(key) <= 0 
+        && key_iterator.hasNext());
+    } else {
+      // the tail didn't contain any keys that matched our criteria, or was 
+      // empty. examine all the keys that preceed our splitting point.
+      SortedMap<HStoreKey, byte []> headMap = map.headMap(search_key);
       
-      // if this check fails, then we've iterated through all the keys that 
-      // match by row, but none match by timestamp, so we fall through to
-      // the headMap case.
-      if (found_key.getTimestamp() <= timestamp) {
-        // we didn't find a key that matched by timestamp, so we have to 
-        // return null;
-/*          LOG.debug("Went searching for " + key + ", found " + found_key.getRow());*/
-        return found_key.getRow();
+      // if we tried to create a headMap and got an empty map, then there are
+      // no keys at or before the search key, so we're done.
+      if (headMap.isEmpty()) {
+        return;
+      }        
+      
+      // if there aren't any candidate keys at this point, we need to search
+      // backwards until we find at least one candidate or run out of headMap.
+      if (candidateKeys.isEmpty()) {
+        HStoreKey[] cells = 
+          headMap.keySet().toArray(new HStoreKey[headMap.keySet().size()]);
+           
+        Text lastRowFound = null;
+        for(int i = cells.length - 1; i >= 0; i--) {
+          HStoreKey thisKey = cells[i];
+          
+          // if the last row we found a candidate key for is different than
+          // the row of the current candidate, we can stop looking.
+          if (lastRowFound != null && !lastRowFound.equals(thisKey.getRow())) {
+            break;
+          }
+          
+          // if this isn't a delete, record it as a candidate key. also 
+          // take note of the row of this candidate so that we'll know when
+          // we cross the row boundary into the previous row.
+          if (!HLogEdit.isDeleted(headMap.get(thisKey))) {
+            lastRowFound = thisKey.getRow();
+            candidateKeys.put(stripTimestamp(thisKey), 
+              new Long(thisKey.getTimestamp()));
+          }
+        }
+      } else {
+        // if there are already some candidate keys, we only need to consider
+        // the very last row's worth of keys in the headMap, because any 
+        // smaller acceptable candidate keys would have caused us to start
+        // our search earlier in the list, and we wouldn't be searching here.
+        SortedMap<HStoreKey, byte[]> thisRowTailMap = 
+          headMap.tailMap(new HStoreKey(headMap.lastKey().getRow()));
+          
+        key_iterator = thisRowTailMap.keySet().iterator();
+  
+        do {
+          found_key = key_iterator.next();
+          
+          if (HLogEdit.isDeleted(thisRowTailMap.get(found_key))) {
+            strippedKey = stripTimestamp(found_key);              
+            if (candidateKeys.containsKey(strippedKey)) {
+              long bestCandidateTs = 
+                candidateKeys.get(strippedKey).longValue();
+              if (bestCandidateTs <= found_key.getTimestamp()) {
+                candidateKeys.remove(strippedKey);
+              }
+            }
+          } else {
+            candidateKeys.put(stripTimestamp(found_key), 
+              found_key.getTimestamp());
+          }
+        } while (key_iterator.hasNext());
       }
     }
-    
-    // the tail didn't contain the key we're searching for, so we should
-    // use the last key in the headmap as the closest before
-    SortedMap<HStoreKey, byte []> headMap = map.headMap(search_key);
-    return headMap.isEmpty()? null: headMap.lastKey().getRow();
+  }
+  
+  static HStoreKey stripTimestamp(HStoreKey key) {
+    return new HStoreKey(key.getRow(), key.getColumn());
   }
   
   /**

Modified: hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestGet2.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestGet2.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestGet2.java (original)
+++ hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestGet2.java Tue Mar
18 14:48:22 2008
@@ -159,7 +159,8 @@
 
     HRegion region = null;
     HRegionIncommon region_incommon = null;
-
+    BatchUpdate batchUpdate = null;
+    
     try {
       HTableDescriptor htd = createTableDescriptor(getName());
       region = createNewHRegion(htd, null, null);
@@ -169,52 +170,70 @@
       Text t10 = new Text("010");
       Text t20 = new Text("020");
       Text t30 = new Text("030");
+      Text t35 = new Text("035");
       Text t40 = new Text("040");
       
-      long lockid = region_incommon.startUpdate(t10);
-      region_incommon.put(lockid, COLUMNS[0], "t10 bytes".getBytes());
-      region_incommon.commit(lockid);
-      
-      lockid = region_incommon.startUpdate(t20);
-      region_incommon.put(lockid, COLUMNS[0], "t20 bytes".getBytes());
-      region_incommon.commit(lockid);
-      
-      lockid = region_incommon.startUpdate(t30);
-      region_incommon.put(lockid, COLUMNS[0], "t30 bytes".getBytes());
-      region_incommon.commit(lockid);
-      
-      lockid = region_incommon.startUpdate(t40);
-      region_incommon.put(lockid, COLUMNS[0], "t40 bytes".getBytes());
-      region_incommon.commit(lockid);
+      batchUpdate = new BatchUpdate(t10);
+      batchUpdate.put(COLUMNS[0], "t10 bytes".getBytes());
+      region.batchUpdate(batchUpdate);
+      
+      batchUpdate = new BatchUpdate(t20);
+      batchUpdate.put(COLUMNS[0], "t20 bytes".getBytes());
+      region.batchUpdate(batchUpdate);
+      
+      batchUpdate = new BatchUpdate(t30);
+      batchUpdate.put(COLUMNS[0], "t30 bytes".getBytes());
+      region.batchUpdate(batchUpdate);
+      
+      batchUpdate = new BatchUpdate(t35);
+      batchUpdate.put(COLUMNS[0], "t35 bytes".getBytes());
+      region.batchUpdate(batchUpdate);
+      
+      batchUpdate = new BatchUpdate(t35);
+      batchUpdate.delete(COLUMNS[0]);
+      region.batchUpdate(batchUpdate);
+      
+      batchUpdate = new BatchUpdate(t40);
+      batchUpdate.put(COLUMNS[0], "t40 bytes".getBytes());
+      region.batchUpdate(batchUpdate);
       
       // try finding "015"
       Text t15 = new Text("015");
       Map<Text, Cell> results = 
-        region.getClosestRowBefore(t15, HConstants.LATEST_TIMESTAMP);
+        region.getClosestRowBefore(t15);
       assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t10 bytes");
 
       // try "020", we should get that row exactly
-      results = region.getClosestRowBefore(t20, HConstants.LATEST_TIMESTAMP);
+      results = region.getClosestRowBefore(t20);
       assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t20 bytes");
-
+      
+      // try "038", should skip deleted "035" and get "030"
+      Text t38 = new Text("038");
+      results = region.getClosestRowBefore(t38);
+      assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t30 bytes");
+      
       // try "050", should get stuff from "040"
       Text t50 = new Text("050");
-      results = region.getClosestRowBefore(t50, HConstants.LATEST_TIMESTAMP);
+      results = region.getClosestRowBefore(t50);
       assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t40 bytes");
 
       // force a flush
       region.flushcache();
 
-      // try finding "015"      
-      results = region.getClosestRowBefore(t15, HConstants.LATEST_TIMESTAMP);
+      // try finding "015"
+      results = region.getClosestRowBefore(t15);
       assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t10 bytes");
 
       // try "020", we should get that row exactly
-      results = region.getClosestRowBefore(t20, HConstants.LATEST_TIMESTAMP);
+      results = region.getClosestRowBefore(t20);
       assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t20 bytes");
 
+      // try "038", should skip deleted "035" and get "030"
+      results = region.getClosestRowBefore(t38);
+      assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t30 bytes");
+
       // try "050", should get stuff from "040"
-      results = region.getClosestRowBefore(t50, HConstants.LATEST_TIMESTAMP);
+      results = region.getClosestRowBefore(t50);
       assertEquals(new String(results.get(COLUMNS[0]).getValue()), "t40 bytes");
     } finally {
       if (region != null) {

Modified: hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestHMemcache.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestHMemcache.java?rev=638598&r1=638597&r2=638598&view=diff
==============================================================================
--- hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestHMemcache.java (original)
+++ hadoop/hbase/trunk/src/test/org/apache/hadoop/hbase/regionserver/TestHMemcache.java Tue
Mar 18 14:48:22 2008
@@ -22,6 +22,7 @@
 import java.io.IOException;
 import java.io.UnsupportedEncodingException;
 import java.util.Map;
+import java.util.SortedMap;
 import java.util.TreeMap;
 
 import junit.framework.TestCase;
@@ -173,4 +174,53 @@
       results.clear();
     }
   }
+  
+  /** For HBASE-528 **/
+  public void testGetRowKeyAtOrBefore() throws IOException {
+    // set up some test data
+    Text t10 = new Text("010");
+    Text t20 = new Text("020");
+    Text t30 = new Text("030");
+    Text t35 = new Text("035");
+    Text t40 = new Text("040");
+    
+    hmemcache.add(getHSKForRow(t10), "t10 bytes".getBytes());
+    hmemcache.add(getHSKForRow(t20), "t20 bytes".getBytes());
+    hmemcache.add(getHSKForRow(t30), "t30 bytes".getBytes());
+    // write a delete in there to see if things still work ok
+    hmemcache.add(getHSKForRow(t35), HLogEdit.deleteBytes.get());
+    hmemcache.add(getHSKForRow(t40), "t40 bytes".getBytes());
+    
+    SortedMap<HStoreKey, Long> results = null;
+    
+    // try finding "015"
+    results = new TreeMap<HStoreKey, Long>();
+    Text t15 = new Text("015");
+    hmemcache.getRowKeyAtOrBefore(t15, results);
+    assertEquals(t10, results.lastKey().getRow());
+    
+    // try "020", we should get that row exactly
+    results = new TreeMap<HStoreKey, Long>();
+    hmemcache.getRowKeyAtOrBefore(t20, results);
+    assertEquals(t20, results.lastKey().getRow());
+  
+    // try "038", should skip the deleted "035" and give "030"
+    results = new TreeMap<HStoreKey, Long>();
+    Text t38 = new Text("038");
+    hmemcache.getRowKeyAtOrBefore(t38, results);
+    assertEquals(t30, results.lastKey().getRow());
+  
+    // try "050", should get stuff from "040"
+    results = new TreeMap<HStoreKey, Long>();
+    Text t50 = new Text("050");
+    hmemcache.getRowKeyAtOrBefore(t50, results);
+    assertEquals(t40, results.lastKey().getRow());
+  }
+  
+  private HStoreKey getHSKForRow(Text row) {
+    return new HStoreKey(row, new Text("test_col:"), HConstants.LATEST_TIMESTAMP);
+  }
+  
+  
+  
 }



Mime
View raw message