git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 2/3] reftable/stack: use geometric table compaction

From
Patrick Steinhardt <ps@pks.im>
Date
Mar 22, 2024, 01:25 UTC
Message-ID
<Zfzd_yxeXWWTJdyP@tanuki>
In-Reply-To
<def7008452303f71c1fa469609bc199c629a19ec.1711060820.git.gitgitgadget@gmail.com>
On Thu, Mar 21, 2024 at 10:40:18PM +0000, Justin Tobler via GitGitGadget wrote:
Show 32 quoted lines
> From: Justin Tobler <jltobler@gmail.com>
> 
> To reduce the number of on-disk reftables, compaction is performed.
> Contiguous tables with the same binary log value of size are grouped
> into segments. The segment that has both the lowest binary log value and
> contains more than one table is set as the starting point when
> identifying the compaction segment.
> 
> Since segments containing a single table are not initially considered
> for compaction, if the table appended to the list does not match the
> previous table log value, no compaction occurs for the new table. It is
> therefore possible for unbounded growth of the table list. This can be
> demonstrated by repeating the following sequence:
> 
> git branch -f foo
> git branch -d foo
> 
> Each operation results in a new table being written with no compaction
> occurring until a separate operation produces a table matching the
> previous table log value.
> 
> Instead, to avoid unbounded growth of the table list, the compaction
> strategy is updated to ensure tables follow a geometric sequence after
> each operation. This is done by walking the table list in reverse index
> order to identify the compaction segment start and end. The compaction
> segment end is found by identifying the first table which has a
> preceding table size less than twice the current table. Next, the
> compaction segment start is found iterating through the remaining tables
> in the list checking if the previous table size is less than twice the
> cumulative of tables from the segment end. This ensures the correct
> segment start is found and that the newly compacted table does not
> violate the geometric sequence.

I don't think we need to go into so much detail how exactly the algorithm is working -- these kind of comments should ideally exist in the code. What would be more interesting to explain here is _why_ we chose the new algorithm over the old one instead of just trying to fix the issue.

Other than that this patch LGTM.
Patrick
Show 395 quoted lines
> When creating 10 thousand references, the new strategy has no
> performance impact:
> 
> Benchmark 1: update-ref: create refs sequentially (revision = HEAD~)
>   Time (mean ± σ):     26.516 s ±  0.047 s    [User: 17.864 s, System: 8.491 s]
>   Range (min … max):   26.447 s … 26.569 s    10 runs
> 
> Benchmark 2: update-ref: create refs sequentially (revision = HEAD)
>   Time (mean ± σ):     26.417 s ±  0.028 s    [User: 17.738 s, System: 8.500 s]
>   Range (min … max):   26.366 s … 26.444 s    10 runs
> 
> Summary
>   update-ref: create refs sequentially (revision = HEAD) ran
>     1.00 ± 0.00 times faster than update-ref: create refs sequentially (revision = HEAD~)
> 
> Some tests in `t0610-reftable-basics.sh` assert the on-disk state of
> tables and are therefore updated to specify the correct new table count.
> Since compaction is more aggressive in ensuring tables maintain a
> geometric sequence, the expected table count is reduced in these tests.
> In `reftable/stack_test.c` tests related to `sizes_to_segments()` are
> removed because the function is no longer needed. Also, the
> `test_suggest_compaction_segment()` test is updated to better showcase
> and reflect the new geometric compaction behavior.
> 
> Signed-off-by: Justin Tobler <jltobler@gmail.com>
> ---
>  reftable/stack.c           | 109 ++++++++++++++++---------------------
>  reftable/stack.h           |   3 -
>  reftable/stack_test.c      |  66 +++++-----------------
>  t/t0610-reftable-basics.sh |  43 ++++++++++-----
>  4 files changed, 91 insertions(+), 130 deletions(-)
> 
> diff --git a/reftable/stack.c b/reftable/stack.c
> index 2370d93d13b..ef55dc75cde 100644
> --- a/reftable/stack.c
> +++ b/reftable/stack.c
> @@ -1214,75 +1214,62 @@ static int segment_size(struct segment *s)
>  	return s->end - s->start;
>  }
>  
> -int fastlog2(uint64_t sz)
> -{
> -	int l = 0;
> -	if (sz == 0)
> -		return 0;
> -	for (; sz; sz /= 2) {
> -		l++;
> -	}
> -	return l - 1;
> -}
> -
> -struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n)
> -{
> -	struct segment *segs = reftable_calloc(n, sizeof(*segs));
> -	struct segment cur = { 0 };
> -	size_t next = 0, i;
> -
> -	if (n == 0) {
> -		*seglen = 0;
> -		return segs;
> -	}
> -	for (i = 0; i < n; i++) {
> -		int log = fastlog2(sizes[i]);
> -		if (cur.log != log && cur.bytes > 0) {
> -			struct segment fresh = {
> -				.start = i,
> -			};
> -
> -			segs[next++] = cur;
> -			cur = fresh;
> -		}
> -
> -		cur.log = log;
> -		cur.end = i + 1;
> -		cur.bytes += sizes[i];
> -	}
> -	segs[next++] = cur;
> -	*seglen = next;
> -	return segs;
> -}
> -
>  struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
>  {
> -	struct segment min_seg = {
> -		.log = 64,
> -	};
> -	struct segment *segs;
> -	size_t seglen = 0, i;
> -
> -	segs = sizes_to_segments(&seglen, sizes, n);
> -	for (i = 0; i < seglen; i++) {
> -		if (segment_size(&segs[i]) == 1)
> -			continue;
> +	struct segment seg = { 0 };
> +	uint64_t bytes;
> +	size_t i;
>  
> -		if (segs[i].log < min_seg.log)
> -			min_seg = segs[i];
> -	}
> +	/*
> +	 * If there are no tables or only a single one then we don't have to
> +	 * compact anything. The sequence is geometric by definition already.
> +	 */
> +	if (n <= 1)
> +		return seg;
>  
> -	while (min_seg.start > 0) {
> -		size_t prev = min_seg.start - 1;
> -		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev]))
> +	/*
> +	 * Find the ending table of the compaction segment needed to restore the
> +	 * geometric sequence.
> +	 *
> +	 * To do so, we iterate backwards starting from the most recent table
> +	 * until a valid segment end is found. If the preceding table is smaller
> +	 * than the current table multiplied by the geometric factor (2), the
> +	 * current table is set as the compaction segment end.
> +	 *
> +	 * Tables after the ending point are not added to the byte count because
> +	 * they are already valid members of the geometric sequence. Due to the
> +	 * properties of a geometric sequence, it is not possible for the sum of
> +	 * these tables to exceed the value of the ending point table.
> +	 */
> +	for (i = n - 1; i > 0; i--) {
> +		if (sizes[i - 1] < sizes[i] * 2) {
> +			seg.end = i + 1;
> +			bytes = sizes[i];
>  			break;
> +		}
> +	}
> +
> +	/*
> +	 * Find the starting table of the compaction segment by iterating
> +	 * through the remaining tables and keeping track of the accumulated
> +	 * size of all tables seen from the segment end table.
> +	 *
> +	 * Note that we keep iterating even after we have found the first
> +	 * starting point. This is because there may be tables in the stack
> +	 * preceding that first starting point which violate the geometric
> +	 * sequence.
> +	 */
> +	for (; i > 0; i--) {
> +		uint64_t curr = bytes;
> +		bytes += sizes[i - 1];
>  
> -		min_seg.start = prev;
> -		min_seg.bytes += sizes[prev];
> +		if (sizes[i - 1] < curr * 2) {
> +			seg.start = i - 1;
> +			seg.bytes = bytes;
> +		}
>  	}
>  
> -	reftable_free(segs);
> -	return min_seg;
> +	return seg;
>  }
>  
>  static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)
> diff --git a/reftable/stack.h b/reftable/stack.h
> index d919455669e..656f896cc28 100644
> --- a/reftable/stack.h
> +++ b/reftable/stack.h
> @@ -33,12 +33,9 @@ int read_lines(const char *filename, char ***lines);
>  
>  struct segment {
>  	size_t start, end;
> -	int log;
>  	uint64_t bytes;
>  };
>  
> -int fastlog2(uint64_t sz);
> -struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n);
>  struct segment suggest_compaction_segment(uint64_t *sizes, size_t n);
>  
>  #endif
> diff --git a/reftable/stack_test.c b/reftable/stack_test.c
> index 509f4866236..e5f6ff5c9e4 100644
> --- a/reftable/stack_test.c
> +++ b/reftable/stack_test.c
> @@ -720,59 +720,14 @@ static void test_reftable_stack_hash_id(void)
>  	clear_dir(dir);
>  }
>  
> -static void test_log2(void)
> -{
> -	EXPECT(1 == fastlog2(3));
> -	EXPECT(2 == fastlog2(4));
> -	EXPECT(2 == fastlog2(5));
> -}
> -
> -static void test_sizes_to_segments(void)
> -{
> -	uint64_t sizes[] = { 2, 3, 4, 5, 7, 9 };
> -	/* .................0  1  2  3  4  5 */
> -
> -	size_t seglen = 0;
> -	struct segment *segs =
> -		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
> -	EXPECT(segs[2].log == 3);
> -	EXPECT(segs[2].start == 5);
> -	EXPECT(segs[2].end == 6);
> -
> -	EXPECT(segs[1].log == 2);
> -	EXPECT(segs[1].start == 2);
> -	EXPECT(segs[1].end == 5);
> -	reftable_free(segs);
> -}
> -
> -static void test_sizes_to_segments_empty(void)
> -{
> -	size_t seglen = 0;
> -	struct segment *segs = sizes_to_segments(&seglen, NULL, 0);
> -	EXPECT(seglen == 0);
> -	reftable_free(segs);
> -}
> -
> -static void test_sizes_to_segments_all_equal(void)
> -{
> -	uint64_t sizes[] = { 5, 5 };
> -	size_t seglen = 0;
> -	struct segment *segs =
> -		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
> -	EXPECT(seglen == 1);
> -	EXPECT(segs[0].start == 0);
> -	EXPECT(segs[0].end == 2);
> -	reftable_free(segs);
> -}
> -
>  static void test_suggest_compaction_segment(void)
>  {
> -	uint64_t sizes[] = { 128, 64, 17, 16, 9, 9, 9, 16, 16 };
> +	uint64_t sizes[] = { 512, 64, 17, 16, 9, 9, 9, 16, 2, 16 };
>  	/* .................0    1    2  3   4  5  6 */
>  	struct segment min =
>  		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
> -	EXPECT(min.start == 2);
> -	EXPECT(min.end == 7);
> +	EXPECT(min.start == 1);
> +	EXPECT(min.end == 10);
>  }
>  
>  static void test_suggest_compaction_segment_nothing(void)
> @@ -884,6 +839,17 @@ static void test_empty_add(void)
>  	reftable_stack_destroy(st2);
>  }
>  
> +static int fastlog2(uint64_t sz)
> +{
> +	int l = 0;
> +	if (sz == 0)
> +		return 0;
> +	for (; sz; sz /= 2) {
> +		l++;
> +	}
> +	return l - 1;
> +}
> +
>  static void test_reftable_stack_auto_compaction(void)
>  {
>  	struct reftable_write_options cfg = { 0 };
> @@ -1072,7 +1038,6 @@ static void test_reftable_stack_compaction_concurrent_clean(void)
>  int stack_test_main(int argc, const char *argv[])
>  {
>  	RUN_TEST(test_empty_add);
> -	RUN_TEST(test_log2);
>  	RUN_TEST(test_names_equal);
>  	RUN_TEST(test_parse_names);
>  	RUN_TEST(test_read_file);
> @@ -1092,9 +1057,6 @@ int stack_test_main(int argc, const char *argv[])
>  	RUN_TEST(test_reftable_stack_update_index_check);
>  	RUN_TEST(test_reftable_stack_uptodate);
>  	RUN_TEST(test_reftable_stack_validate_refname);
> -	RUN_TEST(test_sizes_to_segments);
> -	RUN_TEST(test_sizes_to_segments_all_equal);
> -	RUN_TEST(test_sizes_to_segments_empty);
>  	RUN_TEST(test_suggest_compaction_segment);
>  	RUN_TEST(test_suggest_compaction_segment_nothing);
>  	return 0;
> diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh
> index 686781192eb..e6c3f94d874 100755
> --- a/t/t0610-reftable-basics.sh
> +++ b/t/t0610-reftable-basics.sh
> @@ -293,12 +293,24 @@ test_expect_success 'ref transaction: writes cause auto-compaction' '
>  	test_line_count = 1 repo/.git/reftable/tables.list &&
>  
>  	test_commit -C repo --no-tag A &&
> -	test_line_count = 2 repo/.git/reftable/tables.list &&
> +	test_line_count = 1 repo/.git/reftable/tables.list &&
>  
>  	test_commit -C repo --no-tag B &&
>  	test_line_count = 1 repo/.git/reftable/tables.list
>  '
>  
> +test_expect_success 'ref transaction: alternating table sizes are compacted' '
> +	test_when_finished "rm -rf repo" &&
> +	git init repo &&
> +	test_commit -C repo A &&
> +	for i in $(test_seq 20)
> +	do
> +		git -C repo branch -f foo &&
> +		git -C repo branch -d foo || return 1
> +	done &&
> +	test_line_count = 2 repo/.git/reftable/tables.list
> +'
> +
>  check_fsync_events () {
>  	local trace="$1" &&
>  	shift &&
> @@ -324,7 +336,7 @@ test_expect_success 'ref transaction: writes are synced' '
>  		git -C repo -c core.fsync=reference \
>  		-c core.fsyncMethod=fsync update-ref refs/heads/branch HEAD &&
>  	check_fsync_events trace2.txt <<-EOF
> -	"name":"hardware-flush","count":2
> +	"name":"hardware-flush","count":4
>  	EOF
>  '
>  
> @@ -346,8 +358,8 @@ test_expect_success 'pack-refs: compacts tables' '
>  
>  	test_commit -C repo A &&
>  	ls -1 repo/.git/reftable >table-files &&
> -	test_line_count = 4 table-files &&
> -	test_line_count = 3 repo/.git/reftable/tables.list &&
> +	test_line_count = 3 table-files &&
> +	test_line_count = 2 repo/.git/reftable/tables.list &&
>  
>  	git -C repo pack-refs &&
>  	ls -1 repo/.git/reftable >table-files &&
> @@ -379,7 +391,7 @@ do
>  			umask $umask &&
>  			git init --shared=true repo &&
>  			test_commit -C repo A &&
> -			test_line_count = 3 repo/.git/reftable/tables.list
> +			test_line_count = 2 repo/.git/reftable/tables.list
>  		) &&
>  		git -C repo pack-refs &&
>  		test_expect_perms "-rw-rw-r--" repo/.git/reftable/tables.list &&
> @@ -747,12 +759,13 @@ test_expect_success 'worktree: pack-refs in main repo packs main refs' '
>  	test_when_finished "rm -rf repo worktree" &&
>  	git init repo &&
>  	test_commit -C repo A &&
> -	git -C repo worktree add ../worktree &&
> +	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C repo worktree add ../worktree &&
> +	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C worktree update-ref refs/worktree/per-worktree HEAD &&
>  
> -	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
> -	test_line_count = 4 repo/.git/reftable/tables.list &&
> +	test_line_count = 4 repo/.git/worktrees/worktree/reftable/tables.list &&
> +	test_line_count = 3 repo/.git/reftable/tables.list &&
>  	git -C repo pack-refs &&
> -	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
> +	test_line_count = 4 repo/.git/worktrees/worktree/reftable/tables.list &&
>  	test_line_count = 1 repo/.git/reftable/tables.list
>  '
>  
> @@ -760,19 +773,21 @@ test_expect_success 'worktree: pack-refs in worktree packs worktree refs' '
>  	test_when_finished "rm -rf repo worktree" &&
>  	git init repo &&
>  	test_commit -C repo A &&
> -	git -C repo worktree add ../worktree &&
> +	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C repo worktree add ../worktree &&
> +	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C worktree update-ref refs/worktree/per-worktree HEAD &&
>  
> -	test_line_count = 3 repo/.git/worktrees/worktree/reftable/tables.list &&
> -	test_line_count = 4 repo/.git/reftable/tables.list &&
> +	test_line_count = 4 repo/.git/worktrees/worktree/reftable/tables.list &&
> +	test_line_count = 3 repo/.git/reftable/tables.list &&
>  	git -C worktree pack-refs &&
>  	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
> -	test_line_count = 4 repo/.git/reftable/tables.list
> +	test_line_count = 3 repo/.git/reftable/tables.list
>  '
>  
>  test_expect_success 'worktree: creating shared ref updates main stack' '
>  	test_when_finished "rm -rf repo worktree" &&
>  	git init repo &&
>  	test_commit -C repo A &&
> +	test_commit -C repo B &&
>  
>  	git -C repo worktree add ../worktree &&
>  	git -C repo pack-refs &&
> @@ -780,7 +795,7 @@ test_expect_success 'worktree: creating shared ref updates main stack' '
>  	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
>  	test_line_count = 1 repo/.git/reftable/tables.list &&
>  
> -	git -C worktree update-ref refs/heads/shared HEAD &&
> +	GIT_TEST_REFTABLE_NO_AUTOCOMPACTION=true git -C worktree update-ref refs/heads/shared HEAD &&
>  	test_line_count = 1 repo/.git/worktrees/worktree/reftable/tables.list &&
>  	test_line_count = 2 repo/.git/reftable/tables.list
>  '
> -- 
> gitgitgadget
>
Previous: Justin Tobler via GitGitGadgetNext: Karthik Nayak
Message 9 of 52 in “reftable/stack: use geometric table compaction”
  1. reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Mar 5, 2024
  2. Patrick SteinhardtMar 6, 2024
  3. Patrick SteinhardtMar 6, 2024
  4. Justin ToblerMar 21, 2024
  5. 0/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Mar 21, 2024
  6. 1/3 reftable/stack: add env to disable autocompactionJustin Tobler via GitGitGadget, Mar 21, 2024
  7. Patrick SteinhardtMar 22, 2024
  8. 2/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Mar 21, 2024
  9. Patrick SteinhardtMar 22, 2024
  10. Karthik NayakMar 27, 2024
  11. 3/3 reftable/segment: make segment end inclusiveJustin Tobler via GitGitGadget, Mar 21, 2024
  12. Patrick SteinhardtMar 22, 2024
  13. Han-Wen NienhuysApr 3, 2024
  14. Patrick SteinhardtApr 3, 2024
  15. Justin ToblerApr 3, 2024
  16. Junio C HamanoApr 3, 2024
  17. 0/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Mar 29, 2024
  18. 1/3 reftable/stack: add env to disable autocompactionJustin Tobler via GitGitGadget, Mar 29, 2024
  19. Junio C HamanoMar 29, 2024
  20. Junio C HamanoMar 29, 2024
  21. Patrick SteinhardtApr 2, 2024
  22. Junio C HamanoApr 2, 2024
  23. 3/3 reftable/stack: make segment end inclusiveJustin Tobler via GitGitGadget, Mar 29, 2024
  24. Junio C HamanoMar 29, 2024
  25. Patrick SteinhardtApr 2, 2024
  26. 2/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Mar 29, 2024
  27. Patrick SteinhardtApr 2, 2024
  28. 0/2 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Apr 3, 2024
  29. 1/2 reftable/stack: add env to disable autocompactionJustin Tobler via GitGitGadget, Apr 3, 2024
  30. 2/2 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Apr 3, 2024
  31. Patrick SteinhardtApr 3, 2024
  32. Karthik NayakApr 3, 2024
  33. Junio C HamanoApr 3, 2024
  34. 0/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Apr 4, 2024
  35. 1/3 reftable/stack: allow disabling of auto-compactionJustin Tobler via GitGitGadget, Apr 4, 2024
  36. Patrick SteinhardtApr 8, 2024
  37. 2/3 reftable/stack: add env to disable autocompactionJustin Tobler via GitGitGadget, Apr 4, 2024
  38. Patrick SteinhardtApr 8, 2024
  39. Junio C HamanoApr 8, 2024
  40. 3/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Apr 4, 2024
  41. Patrick SteinhardtApr 8, 2024
  42. Justin ToblerApr 8, 2024
  43. 0/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Apr 8, 2024
  44. 1/3 reftable/stack: expose option to disable auto-compactionJustin Tobler via GitGitGadget, Apr 8, 2024
  45. 2/3 reftable/stack: add env to disable autocompactionJustin Tobler via GitGitGadget, Apr 8, 2024
  46. 3/3 reftable/stack: use geometric table compactionJustin Tobler via GitGitGadget, Apr 8, 2024
  47. Patrick SteinhardtApr 8, 2024
  48. Junio C HamanoApr 8, 2024
  49. Junio C HamanoApr 3, 2024
  50. Patrick SteinhardtApr 3, 2024
  51. Patrick SteinhardtApr 4, 2024
  52. Justin ToblerApr 4, 2024

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.