[PATCH v2 2/2] reftable: fix quadratic behavior in the presence of tombstones

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

From: Kristofer Karlsson <krka@spotify.com>

When many tombstones are present in a reftable, operations that need
to look up or iterate over refs exhibit quadratic behavior.  With
8000 refs deleted and re-created, update-ref takes ~15s, quadrupling
for each doubling of input size.

The root cause is the merged iterator's suppress_deletions flag.
When set, merged_iter_next_void() silently consumes tombstone records
in a tight internal loop before returning to the caller.  This
prevents higher-level code from checking iteration bounds (such as
prefix or refname comparisons) until after all tombstones have been
scanned.

This affects any code path that seeks into a range containing
tombstones, including:

 - refs_verify_refnames_available() seeks to "refs/tags/foo-1/" to
   check for D/F conflicts and must scan through all subsequent
   tombstones before the caller can see that they are past the prefix
   of interest.

 - reftable_backend_read_ref() seeks to a specific refname and must
   scan through all subsequent tombstones before returning "not
   found", because the merged iterator skips the matching tombstone
   and searches for the next live record.

Fix this by no longer setting suppress_deletions on the stack's
merged table and instead handling deletion records at each call site
in the reftable backend, where prefix and refname bounds are
available.  Tombstones are now returned to callers, which skip them
after their existing bounds checks.  This allows iteration to
terminate as soon as a tombstone past the relevant bound is
encountered.

The suppress_deletions flag and its logic in the merged iterator are
retained for downstream users of the reftable library (e.g. libgit2).

This also requires adding deletion checks to the log iteration paths,
since suppress_deletions applied to both ref and log iterators.

Both tests in p1401 go from ~14s to ~0.2s with this change.

Reported-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 refs/reftable-backend.c | 54 ++++++++++++++++++++++++++++++++---------
 reftable/stack.c        |  1 -
 2 files changed, 43 insertions(+), 12 deletions(-)

diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c
index 212408c769..028f0211af 100644
--- a/refs/reftable-backend.c
+++ b/refs/reftable-backend.c
@@ -84,7 +84,8 @@ static int reftable_backend_read_ref(struct reftable_backend *be,
 	if (ret)
 		goto done;
 
-	if (strcmp(ref.refname, refname)) {
+	if (strcmp(ref.refname, refname) ||
+	    reftable_ref_record_is_deletion(&ref)) {
 		ret = 1;
 		goto done;
 	}
@@ -110,7 +111,6 @@ static int reftable_backend_read_ref(struct reftable_backend *be,
 		oidread(oid, reftable_ref_record_val1(&ref),
 			&hash_algos[hash_id]);
 	} else {
-		/* We got a tombstone, which should not happen. */
 		BUG("unhandled reference value type %d", ref.value_type);
 	}
 
@@ -652,6 +652,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
 			break;
 		}
 
+		if (iter->ref.value_type == REFTABLE_REF_DELETION)
+			continue;
+
 		if (iter->exclude_patterns && should_exclude_current_ref(iter))
 			continue;
 
@@ -1532,6 +1535,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data
 					ret = 0;
 					break;
 				}
+				if (reftable_log_record_is_deletion(&log))
+					continue;
 
 				ALLOC_GROW(logs, logs_nr + 1, logs_alloc);
 				tombstone = &logs[logs_nr++];
@@ -1929,6 +1934,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&old_log))
+			continue;
 
 		free(old_log.refname);
 
@@ -2061,6 +2068,9 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator)
 		if (iter->err)
 			break;
 
+		if (reftable_log_record_is_deletion(&iter->log))
+			continue;
+
 		/*
 		 * We want the refnames that we have reflogs for, so we skip if
 		 * we've already produced this name. This could be faster by
@@ -2220,6 +2230,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log))
+			continue;
 
 		ret = yield_log_record(refs, &log, fn, cb_data);
 		if (ret)
@@ -2272,6 +2284,10 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log)) {
+			reftable_log_record_release(&log);
+			continue;
+		}
 
 		ALLOC_GROW(logs, logs_nr + 1, logs_alloc);
 		logs[logs_nr++] = log;
@@ -2318,18 +2334,26 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,
 		goto done;
 
 	/*
-	 * Check whether we get at least one log record for the given ref name.
-	 * If so, the reflog exists, otherwise it doesn't.
+	 * Check whether we get at least one non-deleted log record for the
+	 * given ref name.  If so, the reflog exists, otherwise it doesn't.
 	 */
-	ret = reftable_iterator_next_log(&it, &log);
-	if (ret < 0)
-		goto done;
-	if (ret > 0) {
-		ret = 0;
-		goto done;
+	while (1) {
+		ret = reftable_iterator_next_log(&it, &log);
+		if (ret < 0)
+			goto done;
+		if (ret > 0) {
+			ret = 0;
+			goto done;
+		}
+		if (strcmp(log.refname, refname)) {
+			ret = 0;
+			goto done;
+		}
+		if (!reftable_log_record_is_deletion(&log))
+			break;
 	}
 
-	ret = strcmp(log.refname, refname) == 0;
+	ret = 1;
 
 done:
 	reftable_iterator_destroy(&it);
@@ -2442,6 +2466,8 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da
 			ret = 0;
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log))
+			continue;
 
 		tombstone.refname = (char *)arg->refname;
 		tombstone.value_type = REFTABLE_LOG_DELETION;
@@ -2625,6 +2651,10 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,
 			reftable_log_record_release(&log);
 			break;
 		}
+		if (reftable_log_record_is_deletion(&log)) {
+			reftable_log_record_release(&log);
+			continue;
+		}
 
 		oidread(&old_oid, log.value.update.old_hash,
 			ref_store->repo->hash_algo);
@@ -2791,6 +2821,8 @@ static int reftable_be_fsck(struct ref_store *ref_store, struct fsck_options *o,
 		report.path = refname.buf;
 
 		switch (ref.value_type) {
+		case REFTABLE_REF_DELETION:
+			continue;
 		case REFTABLE_REF_VAL1:
 		case REFTABLE_REF_VAL2: {
 			struct object_id oid;
diff --git a/reftable/stack.c b/reftable/stack.c
index ab12926708..fd7d8f3f1e 100644
--- a/reftable/stack.c
+++ b/reftable/stack.c
@@ -337,7 +337,6 @@ static int reftable_stack_reload_once(struct reftable_stack *st,
 	/* Update the stack to point to the new tables. */
 	if (st->merged)
 		reftable_merged_table_free(st->merged);
-	new_merged->suppress_deletions = 1;
 	st->merged = new_merged;
 
 	if (st->tables)
-- 
gitgitgadget