hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bryanduxb...@apache.org
Subject svn commit: r638534 - in /hadoop/hbase/branches/0.1: ./ src/java/org/apache/hadoop/hbase/ src/test/org/apache/hadoop/hbase/
Date Tue, 18 Mar 2008 19:44:49 GMT
Author: bryanduxbury
Date: Tue Mar 18 12:44:41 2008
New Revision: 638534

URL: http://svn.apache.org/viewvc?rev=638534&view=rev
Log:
HBASE-514 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/branches/0.1/CHANGES.txt
    hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HConnectionManager.java
    hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegion.java
    hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionInterface.java
    hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionServer.java
    hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HStore.java
    hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestGet2.java
    hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestHMemcache.java

Modified: hadoop/hbase/branches/0.1/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/CHANGES.txt?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/CHANGES.txt (original)
+++ hadoop/hbase/branches/0.1/CHANGES.txt Tue Mar 18 12:44:41 2008
@@ -46,6 +46,7 @@
    HBASE-516   HStoreFile.finalKey does not update the final key if it is not
                the top region of a split region
    HBASE-524   Problems with getFull
+   HBASE-514   table 'does not exist' when it does
    
   IMPROVEMENTS
    HADOOP-2555 Refactor the HTable#get and HTable#getRow methods to avoid

Modified: hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HConnectionManager.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HConnectionManager.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HConnectionManager.java (original)
+++ hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HConnectionManager.java Tue
Mar 18 12:44:41 2008
@@ -412,8 +412,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/branches/0.1/src/java/org/apache/hadoop/hbase/HRegion.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegion.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegion.java (original)
+++ hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegion.java Tue Mar 18 12:44:41
2008
@@ -1104,7 +1104,7 @@
    * @return map of values
    * @throws IOException
    */
-  public Map<Text, byte[]> getClosestRowBefore(final Text row, final long ts)
+  public Map<Text, byte[]> 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
@@ -1118,25 +1118,25 @@
         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);
         }
       }
 
       if (key == null) {
         return null;
       }
-          
+      
       // now that we've found our key, get the values
       TreeMap<Text, byte []> result = new TreeMap<Text, byte[]>();
       for (Text colFamily: stores.keySet()) {

Modified: hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionInterface.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionInterface.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionInterface.java (original)
+++ hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionInterface.java Tue Mar
18 12:44:41 2008
@@ -123,20 +123,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;
-
-  /**
    * Applies a batch of updates via one RPC
    * 
    * @param regionName name of the region to update

Modified: hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionServer.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionServer.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionServer.java (original)
+++ hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HRegionServer.java Tue Mar
18 12:44:41 2008
@@ -1354,13 +1354,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();
@@ -1369,7 +1362,7 @@
       HRegion region = getRegion(regionName);
       HbaseMapWritable result = new HbaseMapWritable();
       // ask the region for all the data 
-      Map<Text, byte[]> map = region.getClosestRowBefore(row, ts);
+      Map<Text, byte[]> map = region.getClosestRowBefore(row);
       // convert to a MapWritable
       if (map == null) {
         return null;

Modified: hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HStore.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HStore.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HStore.java (original)
+++ hadoop/hbase/branches/0.1/src/java/org/apache/hadoop/hbase/HStore.java Tue Mar 18 12:44:41
2008
@@ -30,6 +30,8 @@
 import java.util.SortedMap;
 import java.util.TreeMap;
 import java.util.Map.Entry;
+import java.util.SortedSet;
+import java.util.TreeSet;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 import java.util.regex.Matcher;
@@ -140,7 +142,7 @@
         this.lock.readLock().unlock();
       }
     }
-
+  
     /**
      * Look back through all the backlog TreeMaps to find the target.
      * @param key
@@ -223,83 +225,130 @@
      * Find 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 either is a precise match, return the original row.
-          if ( (key_memcache != null && key_memcache.equals(row)) 
-            || (key_snapshot != null && key_snapshot.equals(row)) ) {
-            return row;
-          }
-          // 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);
         }
       } 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 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())
{
+      // 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();
+
+        // 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 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 (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 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();
     }
     
     /**
@@ -1823,49 +1872,37 @@
   
   /**
    * Find the key that matches <i>row</i> exactly, or the one that immediately
-   * preceeds it.
+   * 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();
     }
@@ -1875,11 +1912,10 @@
    * 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();
     
@@ -1887,54 +1923,148 @@
       // don't bother with the rest of this if the file is empty
       map.reset();
       if (!map.next(readkey, readval)) {
-        return null;
-      }
-      
-      HStoreKey finalKey = new HStoreKey(); 
-      map.finalKey(finalKey);
-      if (finalKey.getRow().compareTo(row) < 0) {
-        return finalKey.getRow();
-      }
-      
-      // 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;
+        return;
       }
       
-      do {
-        if (readkey.getRow().compareTo(row) == 0) {
-          // exact match on row
-          if (readkey.getTimestamp() <= timestamp) {
-            // timestamp fits, return this key
-            return readkey.getRow();
-          }
-          // 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 ) {
-          // 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;
-        } 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());
+      // 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());
+
+        HStoreKey strippedKey = null;
+        
+        // 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()));          
 
           }
-          // otherwise, ignore this key, because it doesn't fulfill our 
-          // requirements.
-        }        
-      } while(map.next(readkey, readval));
+          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)) {
+            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);
+                } 
+              }
+            }
+          } 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 {
+            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());
   }
   
   /**

Modified: hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestGet2.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestGet2.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestGet2.java (original)
+++ hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestGet2.java Tue Mar 18 12:44:41
2008
@@ -159,6 +159,7 @@
       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.startBatchUpdate(t10);
@@ -172,6 +173,15 @@
       lockid = region_incommon.startBatchUpdate(t30);
       region_incommon.put(lockid, COLUMNS[0], "t30 bytes".getBytes());
       region_incommon.commit(lockid);
+
+
+      lockid = region_incommon.startBatchUpdate(t35);
+      region_incommon.put(lockid, COLUMNS[0], "t35 bytes".getBytes());
+      region_incommon.commit(lockid);
+      
+      lockid = region_incommon.startBatchUpdate(t35);
+      region_incommon.delete(lockid, COLUMNS[0]);
+      region_incommon.commit(lockid);
       
       lockid = region_incommon.startBatchUpdate(t40);
       region_incommon.put(lockid, COLUMNS[0], "t40 bytes".getBytes());
@@ -180,31 +190,41 @@
       // try finding "015"
       Text t15 = new Text("015");
       Map<Text, byte[]> results = 
-        region.getClosestRowBefore(t15, HConstants.LATEST_TIMESTAMP);
+        region.getClosestRowBefore(t15);
       assertEquals(new String(results.get(COLUMNS[0])), "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])), "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])), "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])), "t40 bytes");
 
       // force a flush
       region.flushcache();
 
       // try finding "015"      
-      results = region.getClosestRowBefore(t15, HConstants.LATEST_TIMESTAMP);
+      results = region.getClosestRowBefore(t15);
       assertEquals(new String(results.get(COLUMNS[0])), "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])), "t20 bytes");
 
+      // try "038", should skip deleted "035" and get "030"
+      results = region.getClosestRowBefore(t38);
+      assertNotNull("get for 038 shouldn't be null", results.get(COLUMNS[0]));
+      assertEquals(new String(results.get(COLUMNS[0])), "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])), "t40 bytes");
     } finally {
       if (region != null) {

Modified: hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestHMemcache.java
URL: http://svn.apache.org/viewvc/hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestHMemcache.java?rev=638534&r1=638533&r2=638534&view=diff
==============================================================================
--- hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestHMemcache.java (original)
+++ hadoop/hbase/branches/0.1/src/test/org/apache/hadoop/hbase/TestHMemcache.java Tue Mar
18 12:44:41 2008
@@ -23,7 +23,7 @@
 import java.io.UnsupportedEncodingException;
 import java.util.Map;
 import java.util.TreeMap;
-
+import java.util.SortedMap;
 import junit.framework.TestCase;
 
 import org.apache.hadoop.io.Text;
@@ -159,5 +159,51 @@
       // Clear out set.  Otherwise row results accumulate.
       results.clear();
     }
+  }
+  
+  /** For HBASE-514 **/
+  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