svn commit: r1505601 - /hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java

[li...@apache.org]

Author: liyin
Date: Mon Jul 22 04:59:37 2013
New Revision: 1505601

URL: http://svn.apache.org/r1505601
Log:
[HBASE-9000] Linear reseek fix update.

Author: shaneh

Summary: Small changes and more explaniation of the correctness.

Test Plan: Bake in Shadow

Reviewers: aaiyer, liyintang

Reviewed By: aaiyer

CC: hbase-eng@

Differential Revision: https://phabricator.fb.com/D891714

Task ID: 2491819

Modified:
    hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java

Modified: hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java
URL: http://svn.apache.org/viewvc/hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java?rev=1505601&r1=1505600&r2=1505601&view=diff
==============================================================================
--- hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java (original)
+++ hbase/branches/0.89-fb/src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java Mon Jul 22 04:59:37 2013
@@ -657,26 +657,41 @@ public class MemStore implements HeapSiz
       return lowest != null;
     }
 
+
     @Override
     public synchronized boolean reseek(KeyValue key) {
 
+      /*
+       * The high level idea is to seek linearly up until a configurable maximum
+       * and then if the kvs we are seeking to are not found yet we fall back to
+       * logarithmic seek.
+       *
+       * The reason we can reach our reseek limit in the kvset and skip searching the
+       * snapshot all together is as follows...
+       * Let x and y denote the # of steps to seek in each of the lists, to reach "key".
+       * If x + y < 20, the order does not matter: we will find the "key" in linear search regardless.
+       * if x + y >= 20, we will have to fall back on seek(key) eventually. It does not matter,
+       * if we spend the 20 steps on x, or we spend it on y. -- aaiyer
+       */
+
+
       //Limit the number of kvs to search linearly before triggering a seek.
       int seeked = 0;
 
       while (kvsetNextRow != null &&
           comparator.compare(kvsetNextRow, key) < 0 &&
-          seeked++ < this.maxLinearReseeks) {
+          ++seeked <= this.maxLinearReseeks) {
         kvsetNextRow = getNext(kvsetIt);
       }
 
       while (snapshotNextRow != null &&
           comparator.compare(snapshotNextRow, key) < 0 &&
-          seeked++ < this.maxLinearReseeks) {
+          ++seeked <= this.maxLinearReseeks) {
         snapshotNextRow = getNext(snapshotIt);
       }
 
       // The linear reseek took more than the maximum allowed by config.
-      if (seeked >= this.maxLinearReseeks) {
+      if (seeked > this.maxLinearReseeks) {
         return seek(key);
       }