Re: [PATCH v2 2/3] reftable/stack: use geometric table compaction
From: Karthik Nayak <hidden>
Date: 2024-03-27 13:24:27
"Justin Tobler via GitGitGadget" [off-list ref] writes:
From: Justin Tobler <redacted> 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.
Attachments
- signature.asc [application/pgp-signature] 690 bytes