WT-3412 Add backoff logic in bt_delete and bt_walk (#3534)

When waiting for a ref to change state

8 files changed, 71 insertions, 33 deletions

diff --git a/dist/stat_data.py b/dist/stat_data.py
index 3c263a39c1f..783fb452599 100644
--- a/dist/stat_data.py
+++ b/dist/stat_data.py
@@ -464,9 +464,9 @@ connection_stats = [
     YieldStat('dhandle_lock_blocked', 'data handle lock yielded'),
     YieldStat('log_server_sync_blocked', 'log server sync yielded for log write'),
     YieldStat('page_busy_blocked', 'page acquire busy blocked'),
-    YieldStat('page_del_rollback_blocked', 'page delete rollback yielded for instantiation'),
+    YieldStat('page_del_rollback_blocked', 'page delete rollback time sleeping for state change (usecs)'),
     YieldStat('page_forcible_evict_blocked', 'page acquire eviction blocked'),
-    YieldStat('page_index_slot_blocked', 'reference for page index and slot yielded'),
+    YieldStat('page_index_slot_ref_blocked', 'get reference for page index and slot time sleeping (usecs)'),
     YieldStat('page_locked_blocked', 'page acquire locked blocked'),
     YieldStat('page_read_blocked', 'page acquire read blocked'),
     YieldStat('page_sleep', 'page acquire time sleeping (usecs)'),
diff --git a/src/btree/bt_delete.c b/src/btree/bt_delete.c
index 7bf471e7cf5..093192dbaa0 100644
--- a/src/btree/bt_delete.c
+++ b/src/btree/bt_delete.c
@@ -153,7 +153,7 @@ void
 __wt_delete_page_rollback(WT_SESSION_IMPL *session, WT_REF *ref)
 {
 	WT_UPDATE **upd;
-	uint64_t yield_count;
+	uint64_t sleep_count, yield_count;
 
 	/*
 	 * If the page is still "deleted", it's as we left it, reset the state
@@ -161,7 +161,7 @@ __wt_delete_page_rollback(WT_SESSION_IMPL *session, WT_REF *ref)
 	 * instantiated or being instantiated.  Loop because it's possible for
 	 * the page to return to the deleted state if instantiation fails.
 	 */
-	for (yield_count = 0;; yield_count++, __wt_yield())
+	for (sleep_count = yield_count = 0;;) {
 		switch (ref->state) {
 		case WT_REF_DISK:
 		case WT_REF_READING:
@@ -174,7 +174,7 @@ __wt_delete_page_rollback(WT_SESSION_IMPL *session, WT_REF *ref)
 			 */
 			if (__wt_atomic_casv32(
 			    &ref->state, WT_REF_DELETED, WT_REF_DISK))
-				goto done;
+				return;
 			break;
 		case WT_REF_LOCKED:
 			/*
@@ -204,10 +204,17 @@ __wt_delete_page_rollback(WT_SESSION_IMPL *session, WT_REF *ref)
 			 */
 			__wt_free(session, ref->page_del->update_list);
 			__wt_free(session, ref->page_del);
-			goto done;
+			return;
 		}
-
-done:	WT_STAT_CONN_INCRV(session, page_del_rollback_blocked, yield_count);
+		/*
+		 * We wait for the change in page state, yield before retrying,
+		 * and if we've yielded enough times, start sleeping so we don't
+		 * burn CPU to no purpose.
+		 */
+		__wt_ref_state_yield_sleep(&yield_count, &sleep_count);
+		WT_STAT_CONN_INCRV(session, page_del_rollback_blocked,
+		    sleep_count);
+	}
 }
 
 /*
diff --git a/src/btree/bt_read.c b/src/btree/bt_read.c
index 5302c8b0de8..91c1499840e 100644
--- a/src/btree/bt_read.c
+++ b/src/btree/bt_read.c
@@ -487,7 +487,7 @@ __wt_page_in_func(WT_SESSION_IMPL *session, WT_REF *ref, uint32_t flags
 	WT_BTREE *btree;
 	WT_DECL_RET;
 	WT_PAGE *page;
-	u_int sleep_cnt, wait_cnt;
+	uint64_t sleep_cnt, wait_cnt;
 	bool busy, cache_work, evict_soon, stalled;
 	int force_attempts;
 
@@ -672,9 +672,8 @@ skip_evict:
 			if (cache_work)
 				continue;
 		}
-		sleep_cnt = WT_MIN(sleep_cnt + WT_THOUSAND, 10000);
+		__wt_ref_state_yield_sleep(&wait_cnt, &sleep_cnt);
 		WT_STAT_CONN_INCRV(session, page_sleep, sleep_cnt);
-		__wt_sleep(0, sleep_cnt);
 	}
 }
 
diff --git a/src/btree/bt_walk.c b/src/btree/bt_walk.c
index 4b0b4484c6f..d783f8f6e71 100644
--- a/src/btree/bt_walk.c
+++ b/src/btree/bt_walk.c
@@ -18,7 +18,7 @@ __ref_index_slot(WT_SESSION_IMPL *session,
 {
 	WT_PAGE_INDEX *pindex;
 	WT_REF **start, **stop, **p, **t;
-	uint64_t yield_count;
+	uint64_t sleep_count, yield_count;
 	uint32_t entries, slot;
 
 	/*
@@ -27,7 +27,7 @@ __ref_index_slot(WT_SESSION_IMPL *session,
 	 * split, their WT_REF structure home values are updated; yield
 	 * and wait for that to happen.
 	 */
-	for (yield_count = 0;; yield_count++, __wt_yield()) {
+	for (sleep_count = yield_count = 0;;) {
 		/*
 		 * Copy the parent page's index value: the page can split at
 		 * any time, but the index's value is always valid, even if
@@ -65,14 +65,19 @@ __ref_index_slot(WT_SESSION_IMPL *session,
 				goto found;
 			}
 		}
-
+		/*
+		 * We failed to get the page index and slot reference, yield
+		 * before retrying, and if we've yielded enough times, start
+		 * sleeping so we don't burn CPU to no purpose.
+		 */
+		__wt_ref_state_yield_sleep(&yield_count, &sleep_count);
+		WT_STAT_CONN_INCRV(session, page_index_slot_ref_blocked,
+		    sleep_count);
 	}
 
 found:	WT_ASSERT(session, pindex->index[slot] == ref);
 	*pindexp = pindex;
 	*slotp = slot;
-
-	WT_STAT_CONN_INCRV(session, page_index_slot_blocked, yield_count);
 }
 
 /*
diff --git a/src/include/btree.i b/src/include/btree.i
index 8c9ac576fe3..216c99b1d9e 100644
--- a/src/include/btree.i
+++ b/src/include/btree.i
@@ -1602,3 +1602,24 @@ __wt_split_descent_race(
 	WT_INTL_INDEX_GET(session, ref->home, pindex);
 	return (pindex != saved_pindex);
 }
+
+/*
+ * __wt_ref_state_yield_sleep --
+ *	sleep while waiting for the wt_ref state after THOUSAND yields.
+ */
+static inline void
+__wt_ref_state_yield_sleep(uint64_t *yield_count, uint64_t *sleep_count)
+{
+	/*
+	 * We yield before retrying, and if we've yielded enough times, start
+	 * sleeping so we don't burn CPU to no purpose.
+	 */
+	if ((*yield_count) < WT_THOUSAND) {
+		(*yield_count)++;
+		__wt_yield();
+		return;
+	}
+
+	(*sleep_count) = WT_MIN((*sleep_count) + WT_THOUSAND, 10 * WT_THOUSAND);
+	__wt_sleep(0, (*sleep_count));
+}
diff --git a/src/include/stat.h b/src/include/stat.h
index e0d996fd81a..7ffc1b69c12 100644
--- a/src/include/stat.h
+++ b/src/include/stat.h
@@ -505,6 +505,7 @@ struct __wt_connection_stats {
 	int64_t txn_release_blocked;
 	int64_t conn_close_blocked_lsm;
 	int64_t dhandle_lock_blocked;
+	int64_t page_index_slot_ref_blocked;
 	int64_t log_server_sync_blocked;
 	int64_t page_busy_blocked;
 	int64_t page_forcible_evict_blocked;
@@ -513,7 +514,6 @@ struct __wt_connection_stats {
 	int64_t page_sleep;
 	int64_t page_del_rollback_blocked;
 	int64_t child_modify_blocked_page;
-	int64_t page_index_slot_blocked;
 	int64_t tree_descend_blocked;
 	int64_t txn_snapshots_created;
 	int64_t txn_snapshots_dropped;
diff --git a/src/include/wiredtiger.in b/src/include/wiredtiger.in
index 93d9a3dc7d1..07c3e756670 100644
--- a/src/include/wiredtiger.in
+++ b/src/include/wiredtiger.in
@@ -5058,24 +5058,30 @@ extern int wiredtiger_extension_terminate(WT_CONNECTION *connection);
 #define	WT_STAT_CONN_CONN_CLOSE_BLOCKED_LSM		1246
 /*! thread-yield: data handle lock yielded */
 #define	WT_STAT_CONN_DHANDLE_LOCK_BLOCKED		1247
+/*!
+ * thread-yield: get reference for page index and slot time sleeping
+ * (usecs)
+ */
+#define	WT_STAT_CONN_PAGE_INDEX_SLOT_REF_BLOCKED	1248
 /*! thread-yield: log server sync yielded for log write */
-#define	WT_STAT_CONN_LOG_SERVER_SYNC_BLOCKED		1248
+#define	WT_STAT_CONN_LOG_SERVER_SYNC_BLOCKED		1249
 /*! thread-yield: page acquire busy blocked */
-#define	WT_STAT_CONN_PAGE_BUSY_BLOCKED			1249
+#define	WT_STAT_CONN_PAGE_BUSY_BLOCKED			1250
 /*! thread-yield: page acquire eviction blocked */
-#define	WT_STAT_CONN_PAGE_FORCIBLE_EVICT_BLOCKED	1250
+#define	WT_STAT_CONN_PAGE_FORCIBLE_EVICT_BLOCKED	1251
 /*! thread-yield: page acquire locked blocked */
-#define	WT_STAT_CONN_PAGE_LOCKED_BLOCKED		1251
+#define	WT_STAT_CONN_PAGE_LOCKED_BLOCKED		1252
 /*! thread-yield: page acquire read blocked */
-#define	WT_STAT_CONN_PAGE_READ_BLOCKED			1252
+#define	WT_STAT_CONN_PAGE_READ_BLOCKED			1253
 /*! thread-yield: page acquire time sleeping (usecs) */
-#define	WT_STAT_CONN_PAGE_SLEEP				1253
-/*! thread-yield: page delete rollback yielded for instantiation */
-#define	WT_STAT_CONN_PAGE_DEL_ROLLBACK_BLOCKED		1254
+#define	WT_STAT_CONN_PAGE_SLEEP				1254
+/*!
+ * thread-yield: page delete rollback time sleeping for state change
+ * (usecs)
+ */
+#define	WT_STAT_CONN_PAGE_DEL_ROLLBACK_BLOCKED		1255
 /*! thread-yield: page reconciliation yielded due to child modification */
-#define	WT_STAT_CONN_CHILD_MODIFY_BLOCKED_PAGE		1255
-/*! thread-yield: reference for page index and slot yielded */
-#define	WT_STAT_CONN_PAGE_INDEX_SLOT_BLOCKED		1256
+#define	WT_STAT_CONN_CHILD_MODIFY_BLOCKED_PAGE		1256
 /*!
  * thread-yield: tree descend one level yielded for split page index
  * update
diff --git a/src/support/stat.c b/src/support/stat.c
index 0502c08d10f..ae029ad0a98 100644
--- a/src/support/stat.c
+++ b/src/support/stat.c
@@ -973,15 +973,15 @@ static const char * const __stats_connection_desc[] = {
 	"thread-yield: connection close blocked waiting for transaction state stabilization",
 	"thread-yield: connection close yielded for lsm manager shutdown",
 	"thread-yield: data handle lock yielded",
+	"thread-yield: get reference for page index and slot time sleeping (usecs)",
 	"thread-yield: log server sync yielded for log write",
 	"thread-yield: page acquire busy blocked",
 	"thread-yield: page acquire eviction blocked",
 	"thread-yield: page acquire locked blocked",
 	"thread-yield: page acquire read blocked",
 	"thread-yield: page acquire time sleeping (usecs)",
-	"thread-yield: page delete rollback yielded for instantiation",
+	"thread-yield: page delete rollback time sleeping for state change (usecs)",
 	"thread-yield: page reconciliation yielded due to child modification",
-	"thread-yield: reference for page index and slot yielded",
 	"thread-yield: tree descend one level yielded for split page index update",
 	"transaction: number of named snapshots created",
 	"transaction: number of named snapshots dropped",
@@ -1296,6 +1296,7 @@ __wt_stat_connection_clear_single(WT_CONNECTION_STATS *stats)
 	stats->txn_release_blocked = 0;
 	stats->conn_close_blocked_lsm = 0;
 	stats->dhandle_lock_blocked = 0;
+	stats->page_index_slot_ref_blocked = 0;
 	stats->log_server_sync_blocked = 0;
 	stats->page_busy_blocked = 0;
 	stats->page_forcible_evict_blocked = 0;
@@ -1304,7 +1305,6 @@ __wt_stat_connection_clear_single(WT_CONNECTION_STATS *stats)
 	stats->page_sleep = 0;
 	stats->page_del_rollback_blocked = 0;
 	stats->child_modify_blocked_page = 0;
-	stats->page_index_slot_blocked = 0;
 	stats->tree_descend_blocked = 0;
 	stats->txn_snapshots_created = 0;
 	stats->txn_snapshots_dropped = 0;
@@ -1700,6 +1700,8 @@ __wt_stat_connection_aggregate(
 	to->conn_close_blocked_lsm +=
 	    WT_STAT_READ(from, conn_close_blocked_lsm);
 	to->dhandle_lock_blocked += WT_STAT_READ(from, dhandle_lock_blocked);
+	to->page_index_slot_ref_blocked +=
+	    WT_STAT_READ(from, page_index_slot_ref_blocked);
 	to->log_server_sync_blocked +=
 	    WT_STAT_READ(from, log_server_sync_blocked);
 	to->page_busy_blocked += WT_STAT_READ(from, page_busy_blocked);
@@ -1712,8 +1714,6 @@ __wt_stat_connection_aggregate(
 	    WT_STAT_READ(from, page_del_rollback_blocked);
 	to->child_modify_blocked_page +=
 	    WT_STAT_READ(from, child_modify_blocked_page);
-	to->page_index_slot_blocked +=
-	    WT_STAT_READ(from, page_index_slot_blocked);
 	to->tree_descend_blocked += WT_STAT_READ(from, tree_descend_blocked);
 	to->txn_snapshots_created +=
 	    WT_STAT_READ(from, txn_snapshots_created);