You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by to...@apache.org on 2018/03/30 18:33:06 UTC

[3/5] kudu git commit: KUDU-1977. Avoid extra reference counting for fast-path MetaCache lookups

KUDU-1977. Avoid extra reference counting for fast-path MetaCache lookups

This does a bit of refactoring of MetaCache so that fast-path lookups
can occur without allocating a LookupRpc object. This avoids an
allocation/deallocation pair as well as reference counting overhead on
various objects. The reference counting was seen as a bottleneck in a
workload like:

$ kudu perf loadgen -num-threads 16 \
  -num-rows-per-thread $[10*1000*1000] -table-num-replicas 3 \
  -table-num-buckets=100 <master>

I ran before/after on the above command writing into a large (100+-node
cluster) that I had handy. A few key stats:

Before:

  time total  : 90676.3 ms
    1458961.567442      task-clock (msec)         #   15.954 CPUs utilized

  Top lines of profile:

    27.21%  kudu             kudu                 [.] kudu::client::internal::MetaCache::LookupTabletByKeyFastPath
    14.95%  kudu             kudu                 [.] kudu::subtle::RefCountedThreadSafeBase::AddRef
    12.52%  kudu             kudu                 [.] kudu::subtle::RefCountedThreadSafeBase::Release
     4.75%  kudu             kudu                 [.] kudu::client::internal::MetaCache::LookupTabletByKey
     3.04%  kudu             kudu                 [.] operator new[]
     1.78%  rpc reactor-387  kudu                 [.] std::unordered_set<InFlightOp*>::erase

After:

  time total  : 60796.6 ms
     693975.355549      task-clock (msec)         #   11.154 CPUs utilized
  Top lines of profile:
    14.05%  kudu             kudu                   [.] kudu::client::internal::MetaCache::LookupTabletByKeyFastPath
     7.89%  kudu             kudu                   [.] operator new[]
     4.96%  rpc reactor-397  kudu                   [.] std::unordered_set<InFlightOp*>::erase
     4.47%  kudu             libc-2.17.so           [.] __memcpy_ssse3_back
     3.42%  rpc reactor-397  kudu                   [.] kudu::client::KuduInsert::~KuduInsert

In other words, this reduced CPU by more than 2x and throughput by about 50%.
Results on the above were relatively stable across multiple runs, with
wall-clock showing more variance than CPU-time.

The new bottleneck seems to be the rw_spinlock in MetaCache.

Change-Id: I5f17ffa88289c766b5b168b22da9781bf78f5592
Reviewed-on: http://gerrit.cloudera.org:8080/9753
Reviewed-by: Adar Dembo <ad...@cloudera.com>
Tested-by: Kudu Jenkins


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/b2b8fb74
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/b2b8fb74
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/b2b8fb74

Branch: refs/heads/master
Commit: b2b8fb74dc564b5e55af6406982e80f2efa19f3c
Parents: 5508ae7
Author: Todd Lipcon <to...@apache.org>
Authored: Wed Mar 21 20:34:34 2018 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Fri Mar 30 03:16:08 2018 +0000

----------------------------------------------------------------------
 src/kudu/client/batcher.cc              |   1 +
 src/kudu/client/client-test.cc          |  15 +--
 src/kudu/client/meta_cache.cc           | 144 +++++++++++++++------------
 src/kudu/client/meta_cache.h            |  45 ++++++---
 src/kudu/client/partitioner-internal.cc |   5 +-
 src/kudu/client/scan_token-internal.cc  |  14 +--
 src/kudu/client/scanner-internal.cc     |  12 ++-
 src/kudu/client/schema.h                |   2 +
 8 files changed, 140 insertions(+), 98 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/batcher.cc
----------------------------------------------------------------------
diff --git a/src/kudu/client/batcher.cc b/src/kudu/client/batcher.cc
index 1b7e2b8..6e30970 100644
--- a/src/kudu/client/batcher.cc
+++ b/src/kudu/client/batcher.cc
@@ -601,6 +601,7 @@ Status Batcher::Add(KuduWriteOperation* write_op) {
       op->write_op->table(),
       std::move(partition_key),
       deadline,
+      MetaCache::LookupType::kPoint,
       &op->tablet,
       Bind(&Batcher::TabletLookupFinished, this, op.get()));
   IgnoreResult(op.release());

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/client-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/client/client-test.cc b/src/kudu/client/client-test.cc
index 5b37ca1..a227b15 100644
--- a/src/kudu/client/client-test.cc
+++ b/src/kudu/client/client-test.cc
@@ -204,8 +204,11 @@ class ClientTest : public KuduTest {
                                                         const string& partition_key) {
     scoped_refptr<internal::RemoteTablet> rt;
     Synchronizer sync;
-    client_->data_->meta_cache_->LookupTabletByKey(table, partition_key, MonoTime::Max(), &rt,
-                                                   sync.AsStatusCallback());
+    client_->data_->meta_cache_->LookupTabletByKey(
+        table, partition_key, MonoTime::Max(),
+        internal::MetaCache::LookupType::kPoint,
+        &rt,
+        sync.AsStatusCallback());
     CHECK_OK(sync.Wait());
     return rt;
   }
@@ -1790,21 +1793,21 @@ TEST_F(ClientTest, TestMetaCacheExpiry) {
   // Clear the cache.
   meta_cache->ClearCache();
   internal::MetaCacheEntry entry;
-  ASSERT_FALSE(meta_cache->LookupTabletByKeyFastPath(client_table_.get(), "", &entry));
+  ASSERT_FALSE(meta_cache->LookupEntryByKeyFastPath(client_table_.get(), "", &entry));
 
   // Prime the cache.
   CHECK_NOTNULL(MetaCacheLookup(client_table_.get(), "").get());
-  ASSERT_TRUE(meta_cache->LookupTabletByKeyFastPath(client_table_.get(), "", &entry));
+  ASSERT_TRUE(meta_cache->LookupEntryByKeyFastPath(client_table_.get(), "", &entry));
   ASSERT_FALSE(entry.stale());
 
   // Sleep in order to expire the cache.
   SleepFor(MonoDelta::FromMilliseconds(FLAGS_table_locations_ttl_ms));
   ASSERT_TRUE(entry.stale());
-  ASSERT_FALSE(meta_cache->LookupTabletByKeyFastPath(client_table_.get(), "", &entry));
+  ASSERT_FALSE(meta_cache->LookupEntryByKeyFastPath(client_table_.get(), "", &entry));
 
   // Force a lookup and ensure the entry is refreshed.
   CHECK_NOTNULL(MetaCacheLookup(client_table_.get(), "").get());
-  ASSERT_TRUE(meta_cache->LookupTabletByKeyFastPath(client_table_.get(), "", &entry));
+  ASSERT_TRUE(meta_cache->LookupEntryByKeyFastPath(client_table_.get(), "", &entry));
   ASSERT_FALSE(entry.stale());
 }
 

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/meta_cache.cc
----------------------------------------------------------------------
diff --git a/src/kudu/client/meta_cache.cc b/src/kudu/client/meta_cache.cc
index a204773..aa77741 100644
--- a/src/kudu/client/meta_cache.cc
+++ b/src/kudu/client/meta_cache.cc
@@ -18,7 +18,6 @@
 #include "kudu/client/meta_cache.h"
 
 #include <algorithm>
-#include <cstddef>
 #include <mutex>
 #include <ostream>
 #include <set>
@@ -329,8 +328,7 @@ string MetaCacheEntry::DebugString(const KuduTable* table) const {
   const string& lower_bound = lower_bound_partition_key();
   const string& upper_bound = upper_bound_partition_key();
 
-  string lower_bound_string = lower_bound.empty() ? "<start>" :
-    table->partition_schema().PartitionKeyDebugString(lower_bound, *table->schema().schema_);
+  string lower_bound_string = MetaCache::DebugLowerBoundPartitionKey(table, lower_bound);
 
   string upper_bound_string = upper_bound.empty() ? "<end>" :
     table->partition_schema().PartitionKeyDebugString(upper_bound, *table->schema().schema_);
@@ -443,7 +441,8 @@ void MetaCacheServerPicker::PickLeader(const ServerPickedCallback& callback,
         table_,
         tablet_->partition().partition_key_start(),
         deadline,
-        NULL,
+        MetaCache::LookupType::kPoint,
+        nullptr,
         Bind(&MetaCacheServerPicker::LookUpTabletCb, Unretained(this), callback, deadline));
     return;
   }
@@ -540,11 +539,12 @@ class LookupRpc : public Rpc {
             scoped_refptr<RemoteTablet>* remote_tablet,
             const MonoTime& deadline,
             shared_ptr<Messenger> messenger,
-            int max_returned_locations,
-            bool is_exact_lookup,
+            MetaCache::LookupType lookup_type,
             ReplicaController::Visibility replica_visibility);
   virtual ~LookupRpc();
   virtual void SendRpc() OVERRIDE;
+  // Send the next RPC without consulting the metacache.
+  void SendRpcSlowPath();
   virtual string ToString() const OVERRIDE;
 
   const GetTableLocationsRequestPB& req() const { return req_; }
@@ -552,7 +552,18 @@ class LookupRpc : public Rpc {
   const string& table_name() const { return table_->name(); }
   const string& table_id() const { return table_->id(); }
   const string& partition_key() const { return partition_key_; }
-  bool is_exact_lookup() const { return is_exact_lookup_; }
+  bool is_exact_lookup() const {
+    return lookup_type_ == MetaCache::LookupType::kPoint;
+  }
+  int locations_to_fetch() const {
+    switch (lookup_type_) {
+      case MetaCache::LookupType::kLowerBound:
+        return kFetchTabletsPerRangeLookup;
+      case MetaCache::LookupType::kPoint:
+        return kFetchTabletsPerPointLookup;
+    }
+    __builtin_unreachable();
+  }
   const KuduTable* table() const { return table_; }
 
  private:
@@ -597,13 +608,8 @@ class LookupRpc : public Rpc {
   // Whether this lookup has acquired a master lookup permit.
   bool has_permit_;
 
-  // The max number of tablets to fetch per round trip from the master
-  const int max_returned_locations_;
-
-  // If true, this lookup is for an exact tablet match with the requested
-  // partition key. If false, the next tablet after the partition key should be
-  // returned if the partition key falls in a non-covered partition range.
-  const bool is_exact_lookup_;
+  // Whether this lookup is for a range or a point.
+  const MetaCache::LookupType lookup_type_;
 
   // Controlling which replicas to look up. If set to Visibility::ALL,
   // non-voter tablet replicas, if any, appear in the lookup result in addition
@@ -617,8 +623,7 @@ LookupRpc::LookupRpc(scoped_refptr<MetaCache> meta_cache,
                      scoped_refptr<RemoteTablet>* remote_tablet,
                      const MonoTime& deadline,
                      shared_ptr<Messenger> messenger,
-                     int max_returned_locations,
-                     bool is_exact_lookup,
+                     MetaCache::LookupType lookup_type,
                      ReplicaController::Visibility replica_visibility)
     : Rpc(deadline, std::move(messenger)),
       meta_cache_(std::move(meta_cache)),
@@ -627,8 +632,7 @@ LookupRpc::LookupRpc(scoped_refptr<MetaCache> meta_cache,
       partition_key_(std::move(partition_key)),
       remote_tablet_(remote_tablet),
       has_permit_(false),
-      max_returned_locations_(max_returned_locations),
-      is_exact_lookup_(is_exact_lookup),
+      lookup_type_(lookup_type),
       replica_visibility_(replica_visibility) {
   DCHECK(deadline.Initialized());
 }
@@ -640,28 +644,17 @@ LookupRpc::~LookupRpc() {
 }
 
 void LookupRpc::SendRpc() {
-  // Fast path: lookup in the cache.
-  MetaCacheEntry entry;
-  while (PREDICT_TRUE(meta_cache_->LookupTabletByKeyFastPath(table_, partition_key_, &entry))
-         && (entry.is_non_covered_range() || entry.tablet()->HasLeader())) {
-    VLOG(4) << "Fast lookup: found " << entry.DebugString(table_) << " for " << ToString();
-    if (!entry.is_non_covered_range()) {
-      if (remote_tablet_) {
-        *remote_tablet_ = entry.tablet();
-      }
-      user_cb_.Run(Status::OK());
-      delete this;
-      return;
-    }
-    if (is_exact_lookup_ || entry.upper_bound_partition_key().empty()) {
-      user_cb_.Run(Status::NotFound("No tablet covering the requested range partition",
-                                    entry.DebugString(table_)));
-      delete this;
-      return;
-    }
-    partition_key_ = entry.upper_bound_partition_key();
+  Status fastpath_status = meta_cache_->DoFastPathLookup(
+      table_, &partition_key_, lookup_type_, remote_tablet_);
+  if (!fastpath_status.IsIncomplete()) {
+    user_cb_.Run(fastpath_status);
+    delete this;
+    return;
   }
+  SendRpcSlowPath();
+}
 
+void LookupRpc::SendRpcSlowPath() {
   // Slow path: must lookup the tablet in the master.
   VLOG(4) << "Fast lookup: no cache entry for " << ToString()
           << ": refreshing our metadata from the Master";
@@ -679,7 +672,7 @@ void LookupRpc::SendRpc() {
   // Fill out the request.
   req_.mutable_table()->set_table_id(table_->id());
   req_.set_partition_key_start(partition_key_);
-  req_.set_max_returned_locations(max_returned_locations_);
+  req_.set_max_returned_locations(locations_to_fetch());
   if (replica_visibility_ == ReplicaController::Visibility::ALL) {
     req_.set_replica_type_filter(master::ANY_REPLICA);
   }
@@ -705,9 +698,7 @@ void LookupRpc::SendRpc() {
 string LookupRpc::ToString() const {
   return Substitute("GetTableLocations { table: '$0', partition-key: ($1), attempt: $2 }",
                     table_->name(),
-                    (partition_key_.empty() ? "<start>" :
-                     table_->partition_schema()
-                            .PartitionKeyDebugString(partition_key_, *table_->schema().schema_)),
+                    MetaCache::DebugLowerBoundPartitionKey(table_, partition_key_),
                     num_attempts());
 }
 
@@ -806,7 +797,7 @@ void LookupRpc::SendRpcCb(const Status& status) {
 
   if (new_status.ok()) {
     MetaCacheEntry entry;
-    new_status = meta_cache_->ProcessLookupResponse(*this, &entry, max_returned_locations_);
+    new_status = meta_cache_->ProcessLookupResponse(*this, &entry, locations_to_fetch());
     if (entry.is_non_covered_range()) {
       new_status = Status::NotFound("No tablet covering the requested range partition",
                                     entry.DebugString(table_));
@@ -967,9 +958,9 @@ Status MetaCache::ProcessLookupResponse(const LookupRpc& rpc,
   return Status::OK();
 }
 
-bool MetaCache::LookupTabletByKeyFastPath(const KuduTable* table,
-                                          const string& partition_key,
-                                          MetaCacheEntry* entry) {
+bool MetaCache::LookupEntryByKeyFastPath(const KuduTable* table,
+                                         const string& partition_key,
+                                         MetaCacheEntry* entry) {
   shared_lock<rw_spinlock> l(lock_);
   const TabletMap* tablets = FindOrNull(tablets_by_table_and_key_, table->id());
   if (PREDICT_FALSE(!tablets)) {
@@ -996,6 +987,30 @@ bool MetaCache::LookupTabletByKeyFastPath(const KuduTable* table,
   return false;
 }
 
+Status MetaCache::DoFastPathLookup(const KuduTable* table,
+                                   string* partition_key,
+                                   MetaCache::LookupType lookup_type,
+                                   scoped_refptr<RemoteTablet>* remote_tablet) {
+  MetaCacheEntry entry;
+  while (PREDICT_TRUE(LookupEntryByKeyFastPath(table, *partition_key, &entry))
+         && (entry.is_non_covered_range() || entry.tablet()->HasLeader())) {
+    VLOG(4) << "Fast lookup: found " << entry.DebugString(table) << " for "
+            << DebugLowerBoundPartitionKey(table, *partition_key);
+    if (!entry.is_non_covered_range()) {
+      if (remote_tablet) {
+        *remote_tablet = entry.tablet();
+      }
+      return Status::OK();
+    }
+    if (lookup_type == LookupType::kPoint || entry.upper_bound_partition_key().empty()) {
+      return Status::NotFound("No tablet covering the requested range partition",
+                              entry.DebugString(table));
+    }
+    *partition_key = entry.upper_bound_partition_key();
+  }
+  return Status::Incomplete("");
+}
+
 void MetaCache::ClearNonCoveredRangeEntries(const std::string& table_id) {
   VLOG(3) << "Clearing non-covered range entries of table " << table_id;
   std::lock_guard<rw_spinlock> l(lock_);
@@ -1026,26 +1041,18 @@ void MetaCache::ClearCache() {
 void MetaCache::LookupTabletByKey(const KuduTable* table,
                                   string partition_key,
                                   const MonoTime& deadline,
+                                  MetaCache::LookupType lookup_type,
                                   scoped_refptr<RemoteTablet>* remote_tablet,
                                   const StatusCallback& callback) {
-  LookupRpc* rpc = new LookupRpc(this,
-                                 callback,
-                                 table,
-                                 std::move(partition_key),
-                                 remote_tablet,
-                                 deadline,
-                                 client_->data_->messenger_,
-                                 kFetchTabletsPerPointLookup,
-                                 true, replica_visibility_);
-  rpc->SendRpc();
-}
+  // Try a fast path without allocating a LookupRpc.
+  // This avoids the allocation and also reference count increment/decrements.
+  Status fastpath_status = DoFastPathLookup(
+      table, &partition_key, lookup_type, remote_tablet);
+  if (!fastpath_status.IsIncomplete()) {
+    callback.Run(fastpath_status);
+    return;
+  }
 
-void MetaCache::LookupTabletByKeyOrNext(const KuduTable* table,
-                                        string partition_key,
-                                        const MonoTime& deadline,
-                                        scoped_refptr<RemoteTablet>* remote_tablet,
-                                        const StatusCallback& callback,
-                                        int max_returned_locations) {
   LookupRpc* rpc = new LookupRpc(this,
                                  callback,
                                  table,
@@ -1053,9 +1060,9 @@ void MetaCache::LookupTabletByKeyOrNext(const KuduTable* table,
                                  remote_tablet,
                                  deadline,
                                  client_->data_->messenger_,
-                                 max_returned_locations,
-                                 false, replica_visibility_);
-  rpc->SendRpc();
+                                 lookup_type,
+                                 replica_visibility_);
+  rpc->SendRpcSlowPath();
 }
 
 void MetaCache::MarkTSFailed(RemoteTabletServer* ts,
@@ -1081,6 +1088,11 @@ void MetaCache::ReleaseMasterLookupPermit() {
   master_lookup_sem_.Release();
 }
 
+string MetaCache::DebugLowerBoundPartitionKey(const KuduTable* table, const string& partition_key) {
+  return partition_key.empty() ? "<start>" :
+      table->partition_schema().PartitionKeyDebugString(partition_key, *table->schema().schema_);
+}
+
 } // namespace internal
 } // namespace client
 } // namespace kudu

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/meta_cache.h
----------------------------------------------------------------------
diff --git a/src/kudu/client/meta_cache.h b/src/kudu/client/meta_cache.h
index ec003b7..34232bc 100644
--- a/src/kudu/client/meta_cache.h
+++ b/src/kudu/client/meta_cache.h
@@ -373,6 +373,17 @@ class MetaCache : public RefCountedThreadSafe<MetaCache> {
   MetaCache(KuduClient* client, ReplicaController::Visibility replica_visibility);
   ~MetaCache();
 
+  // Determines what type of operation a MetaCache lookup is being done for.
+  enum class LookupType {
+    // The lookup should only return a tablet which actually covers the
+    // requested partition key.
+    kPoint,
+    // The lookup should return the next tablet after the requested
+    // partition key if the requested key does not fall within a covered
+    // range.
+    kLowerBound
+  };
+
   // Look up which tablet hosts the given partition key for a table. When it is
   // available, the tablet is stored in 'remote_tablet' (if not NULL) and the
   // callback is fired. Only tablets with non-failed LEADERs are considered.
@@ -385,18 +396,10 @@ class MetaCache : public RefCountedThreadSafe<MetaCache> {
   void LookupTabletByKey(const KuduTable* table,
                          std::string partition_key,
                          const MonoTime& deadline,
+                         LookupType lookup_type,
                          scoped_refptr<RemoteTablet>* remote_tablet,
                          const StatusCallback& callback);
 
-  // Look up which tablet hosts the given partition key, or the next tablet if
-  // the key falls in a non-covered range partition.
-  void LookupTabletByKeyOrNext(const KuduTable* table,
-                               std::string partition_key,
-                               const MonoTime& deadline,
-                               scoped_refptr<RemoteTablet>* remote_tablet,
-                               const StatusCallback& callback,
-                               int max_returned_locations = kFetchTabletsPerPointLookup);
-
   // Clears the non-covered range entries from a table's meta cache.
   void ClearNonCoveredRangeEntries(const std::string& table_id);
 
@@ -414,6 +417,10 @@ class MetaCache : public RefCountedThreadSafe<MetaCache> {
   bool AcquireMasterLookupPermit();
   void ReleaseMasterLookupPermit();
 
+  // Return stringified representation of the given partition key, using "<start>" if empty.
+  static std::string DebugLowerBoundPartitionKey(const KuduTable* table,
+                                                 const std::string& partition_key);
+
  private:
   friend class LookupRpc;
 
@@ -427,10 +434,22 @@ class MetaCache : public RefCountedThreadSafe<MetaCache> {
                                int max_returned_locations);
 
   // Lookup the given tablet by key, only consulting local information.
-  // Returns true and sets *remote_tablet if successful.
-  bool LookupTabletByKeyFastPath(const KuduTable* table,
-                                 const std::string& partition_key,
-                                 MetaCacheEntry* entry);
+  // Returns true and sets *entry if successful.
+  bool LookupEntryByKeyFastPath(const KuduTable* table,
+                                const std::string& partition_key,
+                                MetaCacheEntry* entry);
+
+  // Perform the complete fast-path lookup. Returns:
+  //  - NotFound if the lookup hits a non-covering range.
+  //  - Incomplete if the fast path was not possible
+  //  - OK if the lookup was successful.
+  //
+  // If 'lookup_type' is kLowerBound, then 'partition_key' will be updated to indicate the
+  // start of the range for the matched tablet.
+  Status DoFastPathLookup(const KuduTable* table,
+                          std::string* partition_key, // in-out parameter
+                          LookupType lookup_type,
+                          scoped_refptr<RemoteTablet>* remote_tablet);
 
   // Update our information about the given tablet server.
   //

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/partitioner-internal.cc
----------------------------------------------------------------------
diff --git a/src/kudu/client/partitioner-internal.cc b/src/kudu/client/partitioner-internal.cc
index 0f4458f..826d402 100644
--- a/src/kudu/client/partitioner-internal.cc
+++ b/src/kudu/client/partitioner-internal.cc
@@ -53,8 +53,9 @@ Status KuduPartitionerBuilder::Data::Build(KuduPartitioner** partitioner) {
   while (true) {
     scoped_refptr<internal::RemoteTablet> tablet;
     Synchronizer sync;
-    mc->LookupTabletByKeyOrNext(table_.get(), next_part_key, deadline,
-                                &tablet, sync.AsStatusCallback());
+    mc->LookupTabletByKey(table_.get(), next_part_key, deadline,
+                          internal::MetaCache::LookupType::kLowerBound,
+                          &tablet, sync.AsStatusCallback());
     Status s = sync.Wait();
     if (s.IsNotFound()) {
       // No more tablets

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/scan_token-internal.cc
----------------------------------------------------------------------
diff --git a/src/kudu/client/scan_token-internal.cc b/src/kudu/client/scan_token-internal.cc
index beb43ad..21fc786 100644
--- a/src/kudu/client/scan_token-internal.cc
+++ b/src/kudu/client/scan_token-internal.cc
@@ -62,6 +62,8 @@ using strings::Substitute;
 namespace kudu {
 namespace client {
 
+using internal::MetaCache;
+
 KuduScanToken::Data::Data(KuduTable* table,
                           ScanTokenPB message,
                           unique_ptr<KuduTablet> tablet)
@@ -283,12 +285,12 @@ Status KuduScanTokenBuilder::Data::Build(vector<KuduScanToken*>* tokens) {
     scoped_refptr<internal::RemoteTablet> tablet;
     Synchronizer sync;
     const string& partition_key = pruner.NextPartitionKey();
-    client->data_->meta_cache_->LookupTabletByKeyOrNext(table,
-                                                        partition_key,
-                                                        deadline,
-                                                        &tablet,
-                                                        sync.AsStatusCallback(),
-                                                        internal::kFetchTabletsPerRangeLookup);
+    client->data_->meta_cache_->LookupTabletByKey(table,
+                                                  partition_key,
+                                                  deadline,
+                                                  MetaCache::LookupType::kLowerBound,
+                                                  &tablet,
+                                                  sync.AsStatusCallback());
     Status s = sync.Wait();
     if (s.IsNotFound()) {
       // No more tablets in the table.

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/scanner-internal.cc
----------------------------------------------------------------------
diff --git a/src/kudu/client/scanner-internal.cc b/src/kudu/client/scanner-internal.cc
index ea67ec2..f2bb4e8 100644
--- a/src/kudu/client/scanner-internal.cc
+++ b/src/kudu/client/scanner-internal.cc
@@ -390,11 +390,13 @@ Status KuduScanner::Data::OpenTablet(const string& partition_key,
 
   for (int attempt = 1;; attempt++) {
     Synchronizer sync;
-    table_->client()->data_->meta_cache_->LookupTabletByKeyOrNext(table_.get(),
-                                                                  partition_key,
-                                                                  deadline,
-                                                                  &remote_,
-                                                                  sync.AsStatusCallback());
+    table_->client()->data_->meta_cache_->LookupTabletByKey(
+        table_.get(),
+        partition_key,
+        deadline,
+        internal::MetaCache::LookupType::kLowerBound,
+        &remote_,
+        sync.AsStatusCallback());
     Status s = sync.Wait();
     if (s.IsNotFound()) {
       // No more tablets in the table.

http://git-wip-us.apache.org/repos/asf/kudu/blob/b2b8fb74/src/kudu/client/schema.h
----------------------------------------------------------------------
diff --git a/src/kudu/client/schema.h b/src/kudu/client/schema.h
index 279a79d..79abbfc 100644
--- a/src/kudu/client/schema.h
+++ b/src/kudu/client/schema.h
@@ -53,6 +53,7 @@ namespace client {
 namespace internal {
 class GetTableSchemaRpc;
 class LookupRpc;
+class MetaCache;
 class MetaCacheEntry;
 class WriteRpc;
 } // namespace internal
@@ -581,6 +582,7 @@ class KUDU_EXPORT KuduSchema {
   friend class ScanConfiguration;
   friend class internal::GetTableSchemaRpc;
   friend class internal::LookupRpc;
+  friend class internal::MetaCache;
   friend class internal::MetaCacheEntry;
   friend class internal::WriteRpc;
   friend class tools::RemoteKsckMaster;