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

[Karthik Nayak <karthik.188@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2431 bytes --]

"Justin Tobler via GitGitGadget" <gitgitgadget@gmail.com> writes:

> 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:
>

Nit: A numerical example would really help make this simpler to understand.

> +	/*
> +	 * 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.
> +	 *

Nit: we need the accumulated sum because the tables from the end of the
segment will be recursively merged backwards. This might be worthwhile
to add here.


>  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 */

Nit: since we're here, maybe worthwhile cleaning up this comment. Not
sure what it actually is for.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 690 bytes --]