{"thread":{"id":"60794","subject":"[PATCH 0/5] reftable: fix writing multi-level indices","startedAt":"2024-01-26T10:31:36Z","lastAt":"2024-02-06T07:04:04Z","messageCount":21,"participants":["Patrick Steinhardt","Junio C Hamano","Toon Claes","Kristoffer Haugsbakk","jltobler"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"487398","messageId":"cover.1706263918.git.ps@pks.im","threadId":"60794","inReplyTo":null,"subject":"[PATCH 0/5] reftable: fix writing multi-level indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-26T10:31:30Z","receivedAt":"2024-01-26T10:31:36Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nyesterday I noticed that writing reftables with more than 250,000 refs\nled to the last block of refs in the table not being seekable anymore.\nAs it turns out, 250k refs was the boundary at which we start to write\nmulti-level indices for refs.\n\nThe root cause is a bug with how we write multi-level indices: we did\nnot flush out the last block of the previous index level, and thus we\ndidn't index it in the higher-level index. This patch series fixes this\nissue and also polishes surrounding code a bit.\n\nThe topic depends on Junio's jc/reftable-core-fsync at 1df18a1c9a\n(reftable: honor core.fsync, 2024-01-23) due to a semantic merge\nconflict in the newly added test.\n\nPatrick\n\nPatrick Steinhardt (5):\n  reftable/reader: be more careful about errors in indexed seeks\n  reftable/writer: use correct type to iterate through index entries\n  reftable/writer: simplify writing index records\n  reftable/writer: fix writing multi-level indices\n  reftable: document reading and writing indices\n\n reftable/reader.c         | 30 ++++++++++++++++++\n reftable/readwrite_test.c | 56 ++++++++++++++++++++++++++++++++++\n reftable/writer.c         | 64 ++++++++++++++++++++++-----------------\n 3 files changed, 123 insertions(+), 27 deletions(-)\n\n-- \n2.43.GIT\n\n"},{"id":"487399","messageId":"ecf834a2996f554aa046839dedb835385ef84df5.1706263918.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"[PATCH 1/5] reftable/reader: be more careful about errors in indexed seeks","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-26T10:31:34Z","receivedAt":"2024-01-26T10:31:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing an indexed seek we first need to do a linear seek in order to\nfind the index block for our wanted key. We do not check the returned\nerror of the linear seek though. This is likely not an issue because the\nnext call to `table_iter_next()` would return error, too. But it very\nmuch is a code smell when an error variable is being assigned to without\nactually checking it.\n\nSafeguard the code by checking for errors.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/reader.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 64dc366fb1..278f727a3d 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -509,6 +509,9 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\tgoto done;\n \n \terr = reader_seek_linear(&index_iter, &want_index);\n+\tif (err < 0)\n+\t\tgoto done;\n+\n \twhile (1) {\n \t\terr = table_iter_next(&index_iter, &index_result);\n \t\ttable_iter_block_done(&index_iter);\n-- \n2.43.GIT\n\n"},{"id":"487400","messageId":"88541d03bef7c6ff425d330b153f3e3d94ca7567.1706263918.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"[PATCH 2/5] reftable/writer: use correct type to iterate through index entries","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-26T10:31:39Z","receivedAt":"2024-01-26T10:31:47Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable writer is tracking the number of blocks it has to index via\nthe `index_len` variable. But while this variable is of type `size_t`,\nsome sites use an `int` to loop through the index entries.\n\nConvert the code to consistently use `size_t`.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/writer.c | 16 +++++++---------\n 1 file changed, 7 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 92935baa70..5a0b87b406 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -379,20 +379,21 @@ int reftable_writer_add_logs(struct reftable_writer *w,\n \n static int writer_finish_section(struct reftable_writer *w)\n {\n+\tstruct reftable_block_stats *bstats = NULL;\n \tuint8_t typ = block_writer_type(w->block_writer);\n \tuint64_t index_start = 0;\n \tint max_level = 0;\n-\tint threshold = w->opts.unpadded ? 1 : 3;\n+\tsize_t threshold = w->opts.unpadded ? 1 : 3;\n \tint before_blocks = w->stats.idx_stats.blocks;\n-\tint err = writer_flush_block(w);\n-\tint i = 0;\n-\tstruct reftable_block_stats *bstats = NULL;\n+\tint err;\n+\n+\terr = writer_flush_block(w);\n \tif (err < 0)\n \t\treturn err;\n \n \twhile (w->index_len > threshold) {\n \t\tstruct reftable_index_record *idx = NULL;\n-\t\tint idx_len = 0;\n+\t\tsize_t i, idx_len;\n \n \t\tmax_level++;\n \t\tindex_start = w->next;\n@@ -630,11 +631,8 @@ int reftable_writer_close(struct reftable_writer *w)\n \n static void writer_clear_index(struct reftable_writer *w)\n {\n-\tint i = 0;\n-\tfor (i = 0; i < w->index_len; i++) {\n+\tfor (size_t i = 0; i < w->index_len; i++)\n \t\tstrbuf_release(&w->index[i].last_key);\n-\t}\n-\n \tFREE_AND_NULL(w->index);\n \tw->index_len = 0;\n \tw->index_cap = 0;\n-- \n2.43.GIT\n\n"},{"id":"487401","messageId":"b0982baacf74a4501ce5c543b294bc15d6937875.1706263918.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"[PATCH 3/5] reftable/writer: simplify writing index records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-26T10:31:43Z","receivedAt":"2024-01-26T10:31:47Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When finishing the current section we may end up writing index records\nfor the section to the table. The logic to do so essentially copies what\nwe already have in `writer_add_record()`, making this more complicated\nthan it really has to be.\n\nSimplify the code by using `writer_add_record()` instead.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/writer.c | 19 ++++---------------\n 1 file changed, 4 insertions(+), 15 deletions(-)\n\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 5a0b87b406..2525f236b9 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -405,6 +405,7 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\tw->index = NULL;\n \t\tw->index_len = 0;\n \t\tw->index_cap = 0;\n+\n \t\tfor (i = 0; i < idx_len; i++) {\n \t\t\tstruct reftable_record rec = {\n \t\t\t\t.type = BLOCK_TYPE_INDEX,\n@@ -412,26 +413,14 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\t\t\t\t.idx = idx[i],\n \t\t\t\t},\n \t\t\t};\n-\t\t\tif (block_writer_add(w->block_writer, &rec) == 0) {\n-\t\t\t\tcontinue;\n-\t\t\t}\n \n-\t\t\terr = writer_flush_block(w);\n+\t\t\terr = writer_add_record(w, &rec);\n \t\t\tif (err < 0)\n \t\t\t\treturn err;\n-\n-\t\t\twriter_reinit_block_writer(w, BLOCK_TYPE_INDEX);\n-\n-\t\t\terr = block_writer_add(w->block_writer, &rec);\n-\t\t\tif (err != 0) {\n-\t\t\t\t/* write into fresh block should always succeed\n-\t\t\t\t */\n-\t\t\t\tabort();\n-\t\t\t}\n \t\t}\n-\t\tfor (i = 0; i < idx_len; i++) {\n+\n+\t\tfor (i = 0; i < idx_len; i++)\n \t\t\tstrbuf_release(&idx[i].last_key);\n-\t\t}\n \t\treftable_free(idx);\n \t}\n \n-- \n2.43.GIT\n\n"},{"id":"487402","messageId":"9c6622c4095a00f91885a3f96863f81a7b342f84.1706263918.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"[PATCH 4/5] reftable/writer: fix writing multi-level indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-26T10:31:47Z","receivedAt":"2024-01-26T10:31:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When finishing a section we will potentially write an index that makes\nit more efficient to look up relevant blocks. The index records written\nwill encode, for each block of the indexed section, what the offset of\nthat block is as well as the last key of that block. Thus, the reader\nwould iterate through the index records to find the first key larger or\nequal to the wanted key and then use the encoded offset to look up the\ndesired block.\n\nWhen there are a lot of blocks to index though we may end up writing\nmultiple index blocks, too. To not require a linear search across all\nindex blocks we instead end up writing a multi-level index. Instead of\nreferring to the block we are after, an index record may point to\nanother index block. The reader will then access the highest-level index\nand follow down the chain of index blocks until it hits the sought-after\nblock.\n\nIt has been observed though that it is impossible to seek ref records of\nthe last ref block when using a multi-level index. While the multi-level\nindex exists and looks fine for most of the part, the highest-level\nindex was missing an index record pointing to the last block of the next\nindex. Thus, every additional level made more refs become unseekable at\nthe end of the ref section.\n\nThe root cause is that we are not flushing the last block of the current\nlevel once done writing the level. Consequently, it wasn't recorded in\nthe blocks that need to be indexed by the next-higher level and thus we\nforgot about it.\n\nFix this bug by flushing blocks after we have written all index records.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/readwrite_test.c | 56 +++++++++++++++++++++++++++++++++++++++\n reftable/writer.c         |  8 +++---\n 2 files changed, 60 insertions(+), 4 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 6b99daeaf2..853923397e 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -866,6 +866,61 @@ static void test_write_multiple_indices(void)\n \tstrbuf_release(&buf);\n }\n \n+static void test_write_multi_level_index(void)\n+{\n+\tstruct reftable_write_options opts = {\n+\t\t.block_size = 100,\n+\t};\n+\tstruct strbuf writer_buf = STRBUF_INIT, buf = STRBUF_INIT;\n+\tstruct reftable_block_source source = { 0 };\n+\tstruct reftable_iterator it = { 0 };\n+\tconst struct reftable_stats *stats;\n+\tstruct reftable_writer *writer;\n+\tstruct reftable_reader *reader;\n+\tint err;\n+\n+\twriter = reftable_new_writer(&strbuf_add_void, &noop_flush, &writer_buf, &opts);\n+\treftable_writer_set_limits(writer, 1, 1);\n+\tfor (size_t i = 0; i < 200; i++) {\n+\t\tstruct reftable_ref_record ref = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_REF_VAL1,\n+\t\t\t.value.val1 = {i},\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%03\" PRIuMAX, (uintmax_t)i);\n+\t\tref.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_ref(writer, &ref);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\treftable_writer_close(writer);\n+\n+\t/*\n+\t * The written refs should be sufficiently large to result in a\n+\t * multi-level index.\n+\t */\n+\tstats = reftable_writer_stats(writer);\n+\tEXPECT(stats->ref_stats.max_index_level == 2);\n+\n+\tblock_source_from_strbuf(&source, &writer_buf);\n+\terr = reftable_new_reader(&reader, &source, \"filename\");\n+\tEXPECT_ERR(err);\n+\n+\t/*\n+\t * Seeking the last ref should work as expected.\n+\t */\n+\terr = reftable_reader_seek_ref(reader, &it, \"refs/heads/199\");\n+\tEXPECT_ERR(err);\n+\n+\treftable_iterator_destroy(&it);\n+\treftable_writer_free(writer);\n+\treftable_reader_free(reader);\n+\tstrbuf_release(&writer_buf);\n+\tstrbuf_release(&buf);\n+}\n+\n static void test_corrupt_table_empty(void)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -916,5 +971,6 @@ int readwrite_test_main(int argc, const char *argv[])\n \tRUN_TEST(test_write_object_id_length);\n \tRUN_TEST(test_write_object_id_min_length);\n \tRUN_TEST(test_write_multiple_indices);\n+\tRUN_TEST(test_write_multi_level_index);\n \treturn 0;\n }\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 2525f236b9..24fce5630a 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -419,15 +419,15 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\t\t\treturn err;\n \t\t}\n \n+\t\terr = writer_flush_block(w);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\n \t\tfor (i = 0; i < idx_len; i++)\n \t\t\tstrbuf_release(&idx[i].last_key);\n \t\treftable_free(idx);\n \t}\n \n-\terr = writer_flush_block(w);\n-\tif (err < 0)\n-\t\treturn err;\n-\n \twriter_clear_index(w);\n \n \tbstats = writer_reftable_block_stats(w, typ);\n-- \n2.43.GIT\n\n"},{"id":"487403","messageId":"7850e65878e42c6ae5064554a3681a3ea1a7ae6e.1706263918.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"[PATCH 5/5] reftable: document reading and writing indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-26T10:31:51Z","receivedAt":"2024-01-26T10:31:54Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The way the index gets written and read is not trivial at all and\nrequires the reader to piece together a bunch of parts to figure out how\nit works. Add some documentation to hopefully make this easier to\nunderstand for the next reader.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/reader.c | 27 +++++++++++++++++++++++++++\n reftable/writer.c | 23 +++++++++++++++++++++++\n 2 files changed, 50 insertions(+)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 278f727a3d..6011d0aa04 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -508,11 +508,38 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \tif (err < 0)\n \t\tgoto done;\n \n+\t/*\n+\t * The index may consist of multiple levels, where each level may have\n+\t * multiple index blocks. We start by doing a linear search in the\n+\t * highest layer that identifies the relevant index block as well as\n+\t * the record inside that block that corresponds to our wanted key.\n+\t */\n \terr = reader_seek_linear(&index_iter, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n+\t/*\n+\t * Traverse down the levels until we find a non-index entry.\n+\t */\n \twhile (1) {\n+\t\t/*\n+\t\t * In case we seek a record that does not exist the index iter\n+\t\t * will tell us that the iterator is over. This works because\n+\t\t * the last index entry of the current level will contain the\n+\t\t * last key it knows about. So in case our seeked key is larger\n+\t\t * than the last indexed key we know that it won't exist.\n+\t\t *\n+\t\t * There is one subtlety in the layout of the index section\n+\t\t * that makes this work as expected: the highest-level index is\n+\t\t * at end of the section and will point backwards and thus we\n+\t\t * start reading from the end of the index section, not the\n+\t\t * beginning.\n+\t\t *\n+\t\t * If that wasn't the case and the order was reversed then the\n+\t\t * linear seek would seek into the lower levels and traverse\n+\t\t * all levels of the index only to find out that the key does\n+\t\t * not exist.\n+\t\t */\n \t\terr = table_iter_next(&index_iter, &index_result);\n \t\ttable_iter_block_done(&index_iter);\n \t\tif (err != 0)\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 24fce5630a..6028789dee 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -391,6 +391,24 @@ static int writer_finish_section(struct reftable_writer *w)\n \tif (err < 0)\n \t\treturn err;\n \n+\t/*\n+\t * When the section we are about to index has a lot of blocks then the\n+\t * index itself may span across multiple blocks, as well. This would\n+\t * require a linear scan over index blocks only to find the desired\n+\t * indexed block, which is inefficient. Instead, we write a multi-level\n+\t * index where index records of level N+1 will refer to index blocks of\n+\t * level N. This isn't constant time, either, but at least logarithmic.\n+\t *\n+\t * This loop handles writing this multi-level index. Note that we write\n+\t * the lowest-level index pointing to the indexed blocks first. We then\n+\t * continue writing additional index levels until the current level has\n+\t * less blocks than the threshold so that the highest level will be at\n+\t * the end of the index section.\n+\t *\n+\t * Readers are thus required to start reading the index section from\n+\t * its end, which is why we set `index_start` to the beginning of the\n+\t * last index section.\n+\t */\n \twhile (w->index_len > threshold) {\n \t\tstruct reftable_index_record *idx = NULL;\n \t\tsize_t i, idx_len;\n@@ -428,6 +446,11 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\treftable_free(idx);\n \t}\n \n+\t/*\n+\t * The index may still contain a number of index blocks lower than the\n+\t * threshold. Clear it so that these entries don't leak into the next\n+\t * index section.\n+\t */\n \twriter_clear_index(w);\n \n \tbstats = writer_reftable_block_stats(w, typ);\n-- \n2.43.GIT\n\n"},{"id":"487413","messageId":"xmqqy1ccnjs3.fsf@gitster.g","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"Re: [PATCH 0/5] reftable: fix writing multi-level indices","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-01-26T16:26:04Z","receivedAt":"2024-01-26T16:26:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> yesterday I noticed that writing reftables with more than 250,000 refs\n> led to the last block of refs in the table not being seekable anymore.\n> As it turns out, 250k refs was the boundary at which we start to write\n> multi-level indices for refs.\n\nObviously one of the less exercised corners of the code ;-)\n\n> The topic depends on Junio's jc/reftable-core-fsync at 1df18a1c9a\n> (reftable: honor core.fsync, 2024-01-23) due to a semantic merge\n> conflict in the newly added test.\n\nThanks for the note for the base.  John Cai's work is well done and\nhas been reviewed, so let's merge it down to 'next' soonish.\n\nThanks.\n"},{"id":"487642","messageId":"87sf2dppjt.fsf@iotcl.com","threadId":"60794","inReplyTo":"b0982baacf74a4501ce5c543b294bc15d6937875.1706263918.git.ps@pks.im","subject":"Re: [PATCH 3/5] reftable/writer: simplify writing index records","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2024-01-31T13:44:38Z","receivedAt":"2024-01-31T14:09:01Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"\nPatrick Steinhardt <ps@pks.im> writes:\n\n> When finishing the current section we may end up writing index records\n> for the section to the table. The logic to do so essentially copies what\n> we already have in `writer_add_record()`, making this more complicated\n> than it really has to be.\n\nI didn't feel like this commit message made it easier for me to\nunderstand, because I interpreted words differently than you intended.\nUsing \"may end up\" makes it sound like it's unexpected behavior. Also\nthe use of \"copies\" implies to me it's doing a copy operation. I would\nrephrase it to something like:\n\n  When finishing the current section some index records might be written\n  for the section to the table. The logic to do so is essentially\n  duplicated from what we already have in `writer_add_record()`, making\n  this more complicated than it really has to be.\n\nOther than that, I don't have any comments about this patch series.\n\n--\nToon\n"},{"id":"487644","messageId":"b96f8ce1-f597-447b-b410-e135626e03d0@app.fastmail.com","threadId":"60794","inReplyTo":"b0982baacf74a4501ce5c543b294bc15d6937875.1706263918.git.ps@pks.im","subject":"Re: [PATCH 3/5] reftable/writer: simplify writing index records","fromName":"Kristoffer Haugsbakk","fromEmail":"code@khaugsbakk.name","sentAt":"2024-01-31T15:55:33Z","receivedAt":"2024-01-31T15:58:11Z","isPatch":true,"sender":{"key":"code@khaugsbakk.name","avatar":"https://avatars.githubusercontent.com/u/2229597?v=4"},"body":"Hi\n\nIt looks like this isn’t in `next` yet so I’ll leave a comment.\n\n> @@ -405,6 +405,7 @@ static int writer_finish_section(struct reftable_writer *w)\n>  \t\tw->index = NULL;\n>  \t\tw->index_len = 0;\n>  \t\tw->index_cap = 0;\n> +\n\nThis part and the next quoted one seem to be an unrelated edit by\n`clang-format`. They could perhaps be grouped in their own patch.\n\n> -\t\t\t\tabort();\n> -\t\t\t}\n>  \t\t}\n> -\t\tfor (i = 0; i < idx_len; i++) {\n> +\n> +\t\tfor (i = 0; i < idx_len; i++)\n>  \t\t\tstrbuf_release(&idx[i].last_key);\n> -\t\t}\n>  \t\treftable_free(idx);\n>  \t}\n\n-- \nKristoffer Haugsbakk\n"},{"id":"487709","messageId":"cover.1706773842.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706263918.git.ps@pks.im","subject":"[PATCH v2 0/5] reftable: fix writing multi-level indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T07:51:52Z","receivedAt":"2024-02-01T07:51:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second version of my patch series that fixes writing of\nmulti-level indices. There are two minor changes compared to v1:\n\n  - Slightly rephrased a commit message.\n\n  - Dropped an added newline that resulted in a new hunk.\n\nThe patch series continues to build on top of jc/reftable-core-fsync.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (5):\n  reftable/reader: be more careful about errors in indexed seeks\n  reftable/writer: use correct type to iterate through index entries\n  reftable/writer: simplify writing index records\n  reftable/writer: fix writing multi-level indices\n  reftable: document reading and writing indices\n\n reftable/reader.c         | 30 +++++++++++++++++++\n reftable/readwrite_test.c | 56 ++++++++++++++++++++++++++++++++++\n reftable/writer.c         | 63 ++++++++++++++++++++++-----------------\n 3 files changed, 122 insertions(+), 27 deletions(-)\n\nRange-diff against v1:\n1:  ecf834a299 = 1:  ecf834a299 reftable/reader: be more careful about errors in indexed seeks\n2:  88541d03be = 2:  88541d03be reftable/writer: use correct type to iterate through index entries\n3:  b0982baacf ! 3:  b3de0b7f3b reftable/writer: simplify writing index records\n    @@ Metadata\n      ## Commit message ##\n         reftable/writer: simplify writing index records\n     \n    -    When finishing the current section we may end up writing index records\n    -    for the section to the table. The logic to do so essentially copies what\n    -    we already have in `writer_add_record()`, making this more complicated\n    -    than it really has to be.\n    +    When finishing the current section some index records might be written\n    +    for the section to the table. The logic that adds these records to the\n    +    writer duplicates what we already have in `writer_add_record()`, making\n    +    this more complicated than it really has to be.\n     \n    -    Simplify the code by using `writer_add_record()` instead.\n    +    Simplify the code by using `writer_add_record()` instead. While at it,\n    +    drop the unneeded braces around a loop to make the code conform to our\n    +    code style better.\n     \n         Signed-off-by: Patrick Steinhardt <ps@pks.im>\n     \n      ## reftable/writer.c ##\n    -@@ reftable/writer.c: static int writer_finish_section(struct reftable_writer *w)\n    - \t\tw->index = NULL;\n    - \t\tw->index_len = 0;\n    - \t\tw->index_cap = 0;\n    -+\n    - \t\tfor (i = 0; i < idx_len; i++) {\n    - \t\t\tstruct reftable_record rec = {\n    - \t\t\t\t.type = BLOCK_TYPE_INDEX,\n     @@ reftable/writer.c: static int writer_finish_section(struct reftable_writer *w)\n      \t\t\t\t\t.idx = idx[i],\n      \t\t\t\t},\n4:  9c6622c409 = 4:  89a88cf83e reftable/writer: fix writing multi-level indices\n5:  7850e65878 = 5:  c3492bbd42 reftable: document reading and writing indices\n-- \n2.43.GIT\n\n"},{"id":"487710","messageId":"ecf834a2996f554aa046839dedb835385ef84df5.1706773842.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706773842.git.ps@pks.im","subject":"[PATCH v2 1/5] reftable/reader: be more careful about errors in indexed seeks","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T07:51:56Z","receivedAt":"2024-02-01T07:52:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing an indexed seek we first need to do a linear seek in order to\nfind the index block for our wanted key. We do not check the returned\nerror of the linear seek though. This is likely not an issue because the\nnext call to `table_iter_next()` would return error, too. But it very\nmuch is a code smell when an error variable is being assigned to without\nactually checking it.\n\nSafeguard the code by checking for errors.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/reader.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 64dc366fb1..278f727a3d 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -509,6 +509,9 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\tgoto done;\n \n \terr = reader_seek_linear(&index_iter, &want_index);\n+\tif (err < 0)\n+\t\tgoto done;\n+\n \twhile (1) {\n \t\terr = table_iter_next(&index_iter, &index_result);\n \t\ttable_iter_block_done(&index_iter);\n-- \n2.43.GIT\n\n"},{"id":"487711","messageId":"88541d03bef7c6ff425d330b153f3e3d94ca7567.1706773842.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706773842.git.ps@pks.im","subject":"[PATCH v2 2/5] reftable/writer: use correct type to iterate through index entries","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T07:52:00Z","receivedAt":"2024-02-01T07:52:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable writer is tracking the number of blocks it has to index via\nthe `index_len` variable. But while this variable is of type `size_t`,\nsome sites use an `int` to loop through the index entries.\n\nConvert the code to consistently use `size_t`.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/writer.c | 16 +++++++---------\n 1 file changed, 7 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 92935baa70..5a0b87b406 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -379,20 +379,21 @@ int reftable_writer_add_logs(struct reftable_writer *w,\n \n static int writer_finish_section(struct reftable_writer *w)\n {\n+\tstruct reftable_block_stats *bstats = NULL;\n \tuint8_t typ = block_writer_type(w->block_writer);\n \tuint64_t index_start = 0;\n \tint max_level = 0;\n-\tint threshold = w->opts.unpadded ? 1 : 3;\n+\tsize_t threshold = w->opts.unpadded ? 1 : 3;\n \tint before_blocks = w->stats.idx_stats.blocks;\n-\tint err = writer_flush_block(w);\n-\tint i = 0;\n-\tstruct reftable_block_stats *bstats = NULL;\n+\tint err;\n+\n+\terr = writer_flush_block(w);\n \tif (err < 0)\n \t\treturn err;\n \n \twhile (w->index_len > threshold) {\n \t\tstruct reftable_index_record *idx = NULL;\n-\t\tint idx_len = 0;\n+\t\tsize_t i, idx_len;\n \n \t\tmax_level++;\n \t\tindex_start = w->next;\n@@ -630,11 +631,8 @@ int reftable_writer_close(struct reftable_writer *w)\n \n static void writer_clear_index(struct reftable_writer *w)\n {\n-\tint i = 0;\n-\tfor (i = 0; i < w->index_len; i++) {\n+\tfor (size_t i = 0; i < w->index_len; i++)\n \t\tstrbuf_release(&w->index[i].last_key);\n-\t}\n-\n \tFREE_AND_NULL(w->index);\n \tw->index_len = 0;\n \tw->index_cap = 0;\n-- \n2.43.GIT\n\n"},{"id":"487712","messageId":"b3de0b7f3b3dfbe9cfa6a20220e20cb884b3539c.1706773842.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706773842.git.ps@pks.im","subject":"[PATCH v2 3/5] reftable/writer: simplify writing index records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T07:52:04Z","receivedAt":"2024-02-01T07:52:09Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When finishing the current section some index records might be written\nfor the section to the table. The logic that adds these records to the\nwriter duplicates what we already have in `writer_add_record()`, making\nthis more complicated than it really has to be.\n\nSimplify the code by using `writer_add_record()` instead. While at it,\ndrop the unneeded braces around a loop to make the code conform to our\ncode style better.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/writer.c | 18 +++---------------\n 1 file changed, 3 insertions(+), 15 deletions(-)\n\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 5a0b87b406..b5bcce0292 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -412,26 +412,14 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\t\t\t\t.idx = idx[i],\n \t\t\t\t},\n \t\t\t};\n-\t\t\tif (block_writer_add(w->block_writer, &rec) == 0) {\n-\t\t\t\tcontinue;\n-\t\t\t}\n \n-\t\t\terr = writer_flush_block(w);\n+\t\t\terr = writer_add_record(w, &rec);\n \t\t\tif (err < 0)\n \t\t\t\treturn err;\n-\n-\t\t\twriter_reinit_block_writer(w, BLOCK_TYPE_INDEX);\n-\n-\t\t\terr = block_writer_add(w->block_writer, &rec);\n-\t\t\tif (err != 0) {\n-\t\t\t\t/* write into fresh block should always succeed\n-\t\t\t\t */\n-\t\t\t\tabort();\n-\t\t\t}\n \t\t}\n-\t\tfor (i = 0; i < idx_len; i++) {\n+\n+\t\tfor (i = 0; i < idx_len; i++)\n \t\t\tstrbuf_release(&idx[i].last_key);\n-\t\t}\n \t\treftable_free(idx);\n \t}\n \n-- \n2.43.GIT\n\n"},{"id":"487713","messageId":"89a88cf83eeb50542d3878c5c6e56e46f2bc3e73.1706773842.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706773842.git.ps@pks.im","subject":"[PATCH v2 4/5] reftable/writer: fix writing multi-level indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T07:52:08Z","receivedAt":"2024-02-01T07:52:13Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When finishing a section we will potentially write an index that makes\nit more efficient to look up relevant blocks. The index records written\nwill encode, for each block of the indexed section, what the offset of\nthat block is as well as the last key of that block. Thus, the reader\nwould iterate through the index records to find the first key larger or\nequal to the wanted key and then use the encoded offset to look up the\ndesired block.\n\nWhen there are a lot of blocks to index though we may end up writing\nmultiple index blocks, too. To not require a linear search across all\nindex blocks we instead end up writing a multi-level index. Instead of\nreferring to the block we are after, an index record may point to\nanother index block. The reader will then access the highest-level index\nand follow down the chain of index blocks until it hits the sought-after\nblock.\n\nIt has been observed though that it is impossible to seek ref records of\nthe last ref block when using a multi-level index. While the multi-level\nindex exists and looks fine for most of the part, the highest-level\nindex was missing an index record pointing to the last block of the next\nindex. Thus, every additional level made more refs become unseekable at\nthe end of the ref section.\n\nThe root cause is that we are not flushing the last block of the current\nlevel once done writing the level. Consequently, it wasn't recorded in\nthe blocks that need to be indexed by the next-higher level and thus we\nforgot about it.\n\nFix this bug by flushing blocks after we have written all index records.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/readwrite_test.c | 56 +++++++++++++++++++++++++++++++++++++++\n reftable/writer.c         |  8 +++---\n 2 files changed, 60 insertions(+), 4 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 6b99daeaf2..853923397e 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -866,6 +866,61 @@ static void test_write_multiple_indices(void)\n \tstrbuf_release(&buf);\n }\n \n+static void test_write_multi_level_index(void)\n+{\n+\tstruct reftable_write_options opts = {\n+\t\t.block_size = 100,\n+\t};\n+\tstruct strbuf writer_buf = STRBUF_INIT, buf = STRBUF_INIT;\n+\tstruct reftable_block_source source = { 0 };\n+\tstruct reftable_iterator it = { 0 };\n+\tconst struct reftable_stats *stats;\n+\tstruct reftable_writer *writer;\n+\tstruct reftable_reader *reader;\n+\tint err;\n+\n+\twriter = reftable_new_writer(&strbuf_add_void, &noop_flush, &writer_buf, &opts);\n+\treftable_writer_set_limits(writer, 1, 1);\n+\tfor (size_t i = 0; i < 200; i++) {\n+\t\tstruct reftable_ref_record ref = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_REF_VAL1,\n+\t\t\t.value.val1 = {i},\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%03\" PRIuMAX, (uintmax_t)i);\n+\t\tref.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_ref(writer, &ref);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\treftable_writer_close(writer);\n+\n+\t/*\n+\t * The written refs should be sufficiently large to result in a\n+\t * multi-level index.\n+\t */\n+\tstats = reftable_writer_stats(writer);\n+\tEXPECT(stats->ref_stats.max_index_level == 2);\n+\n+\tblock_source_from_strbuf(&source, &writer_buf);\n+\terr = reftable_new_reader(&reader, &source, \"filename\");\n+\tEXPECT_ERR(err);\n+\n+\t/*\n+\t * Seeking the last ref should work as expected.\n+\t */\n+\terr = reftable_reader_seek_ref(reader, &it, \"refs/heads/199\");\n+\tEXPECT_ERR(err);\n+\n+\treftable_iterator_destroy(&it);\n+\treftable_writer_free(writer);\n+\treftable_reader_free(reader);\n+\tstrbuf_release(&writer_buf);\n+\tstrbuf_release(&buf);\n+}\n+\n static void test_corrupt_table_empty(void)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -916,5 +971,6 @@ int readwrite_test_main(int argc, const char *argv[])\n \tRUN_TEST(test_write_object_id_length);\n \tRUN_TEST(test_write_object_id_min_length);\n \tRUN_TEST(test_write_multiple_indices);\n+\tRUN_TEST(test_write_multi_level_index);\n \treturn 0;\n }\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex b5bcce0292..0349094d29 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -418,15 +418,15 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\t\t\treturn err;\n \t\t}\n \n+\t\terr = writer_flush_block(w);\n+\t\tif (err < 0)\n+\t\t\treturn err;\n+\n \t\tfor (i = 0; i < idx_len; i++)\n \t\t\tstrbuf_release(&idx[i].last_key);\n \t\treftable_free(idx);\n \t}\n \n-\terr = writer_flush_block(w);\n-\tif (err < 0)\n-\t\treturn err;\n-\n \twriter_clear_index(w);\n \n \tbstats = writer_reftable_block_stats(w, typ);\n-- \n2.43.GIT\n\n"},{"id":"487714","messageId":"c3492bbd42b9d2c17764208e814faccf395cb282.1706773842.git.ps@pks.im","threadId":"60794","inReplyTo":"cover.1706773842.git.ps@pks.im","subject":"[PATCH v2 5/5] reftable: document reading and writing indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T07:52:12Z","receivedAt":"2024-02-01T07:52:16Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The way the index gets written and read is not trivial at all and\nrequires the reader to piece together a bunch of parts to figure out how\nit works. Add some documentation to hopefully make this easier to\nunderstand for the next reader.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/reader.c | 27 +++++++++++++++++++++++++++\n reftable/writer.c | 23 +++++++++++++++++++++++\n 2 files changed, 50 insertions(+)\n\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex 278f727a3d..6011d0aa04 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -508,11 +508,38 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \tif (err < 0)\n \t\tgoto done;\n \n+\t/*\n+\t * The index may consist of multiple levels, where each level may have\n+\t * multiple index blocks. We start by doing a linear search in the\n+\t * highest layer that identifies the relevant index block as well as\n+\t * the record inside that block that corresponds to our wanted key.\n+\t */\n \terr = reader_seek_linear(&index_iter, &want_index);\n \tif (err < 0)\n \t\tgoto done;\n \n+\t/*\n+\t * Traverse down the levels until we find a non-index entry.\n+\t */\n \twhile (1) {\n+\t\t/*\n+\t\t * In case we seek a record that does not exist the index iter\n+\t\t * will tell us that the iterator is over. This works because\n+\t\t * the last index entry of the current level will contain the\n+\t\t * last key it knows about. So in case our seeked key is larger\n+\t\t * than the last indexed key we know that it won't exist.\n+\t\t *\n+\t\t * There is one subtlety in the layout of the index section\n+\t\t * that makes this work as expected: the highest-level index is\n+\t\t * at end of the section and will point backwards and thus we\n+\t\t * start reading from the end of the index section, not the\n+\t\t * beginning.\n+\t\t *\n+\t\t * If that wasn't the case and the order was reversed then the\n+\t\t * linear seek would seek into the lower levels and traverse\n+\t\t * all levels of the index only to find out that the key does\n+\t\t * not exist.\n+\t\t */\n \t\terr = table_iter_next(&index_iter, &index_result);\n \t\ttable_iter_block_done(&index_iter);\n \t\tif (err != 0)\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 0349094d29..e23953e498 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -391,6 +391,24 @@ static int writer_finish_section(struct reftable_writer *w)\n \tif (err < 0)\n \t\treturn err;\n \n+\t/*\n+\t * When the section we are about to index has a lot of blocks then the\n+\t * index itself may span across multiple blocks, as well. This would\n+\t * require a linear scan over index blocks only to find the desired\n+\t * indexed block, which is inefficient. Instead, we write a multi-level\n+\t * index where index records of level N+1 will refer to index blocks of\n+\t * level N. This isn't constant time, either, but at least logarithmic.\n+\t *\n+\t * This loop handles writing this multi-level index. Note that we write\n+\t * the lowest-level index pointing to the indexed blocks first. We then\n+\t * continue writing additional index levels until the current level has\n+\t * less blocks than the threshold so that the highest level will be at\n+\t * the end of the index section.\n+\t *\n+\t * Readers are thus required to start reading the index section from\n+\t * its end, which is why we set `index_start` to the beginning of the\n+\t * last index section.\n+\t */\n \twhile (w->index_len > threshold) {\n \t\tstruct reftable_index_record *idx = NULL;\n \t\tsize_t i, idx_len;\n@@ -427,6 +445,11 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\treftable_free(idx);\n \t}\n \n+\t/*\n+\t * The index may still contain a number of index blocks lower than the\n+\t * threshold. Clear it so that these entries don't leak into the next\n+\t * index section.\n+\t */\n \twriter_clear_index(w);\n \n \tbstats = writer_reftable_block_stats(w, typ);\n-- \n2.43.GIT\n\n"},{"id":"487715","messageId":"ZbtYxgpK_FL3vYL1@tanuki","threadId":"60794","inReplyTo":"b96f8ce1-f597-447b-b410-e135626e03d0@app.fastmail.com","subject":"Re: [PATCH 3/5] reftable/writer: simplify writing index records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T08:39:34Z","receivedAt":"2024-02-01T08:39:41Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Jan 31, 2024 at 04:55:33PM +0100, Kristoffer Haugsbakk wrote:\n> Hi\n> \n> It looks like this isn’t in `next` yet so I’ll leave a comment.\n> \n> > @@ -405,6 +405,7 @@ static int writer_finish_section(struct reftable_writer *w)\n> >  \t\tw->index = NULL;\n> >  \t\tw->index_len = 0;\n> >  \t\tw->index_cap = 0;\n> > +\n> \n> This part and the next quoted one seem to be an unrelated edit by\n> `clang-format`. They could perhaps be grouped in their own patch.\n\nI'll just drop this newline change here, it indeed does make the reader\nwonder what's going on. I'll keep the other one though -- it does not\nquite feel sensible to move it into its own patch.\n\nThanks!\n\nPatrick\n\n> > -\t\t\t\tabort();\n> > -\t\t\t}\n> >  \t\t}\n> > -\t\tfor (i = 0; i < idx_len; i++) {\n> > +\n> > +\t\tfor (i = 0; i < idx_len; i++)\n> >  \t\t\tstrbuf_release(&idx[i].last_key);\n> > -\t\t}\n> >  \t\treftable_free(idx);\n> >  \t}\n> \n> -- \n> Kristoffer Haugsbakk\n"},{"id":"487716","messageId":"ZbtYy4ZdjATQ4yi_@tanuki","threadId":"60794","inReplyTo":"87sf2dppjt.fsf@iotcl.com","subject":"Re: [PATCH 3/5] reftable/writer: simplify writing index records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-01T08:39:39Z","receivedAt":"2024-02-01T08:39:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Jan 31, 2024 at 02:44:38PM +0100, Toon Claes wrote:\n> \n> Patrick Steinhardt <ps@pks.im> writes:\n> \n> > When finishing the current section we may end up writing index records\n> > for the section to the table. The logic to do so essentially copies what\n> > we already have in `writer_add_record()`, making this more complicated\n> > than it really has to be.\n> \n> I didn't feel like this commit message made it easier for me to\n> understand, because I interpreted words differently than you intended.\n> Using \"may end up\" makes it sound like it's unexpected behavior. Also\n> the use of \"copies\" implies to me it's doing a copy operation. I would\n> rephrase it to something like:\n> \n>   When finishing the current section some index records might be written\n>   for the section to the table. The logic to do so is essentially\n>   duplicated from what we already have in `writer_add_record()`, making\n>   this more complicated than it really has to be.\n> \n> Other than that, I don't have any comments about this patch series.\n\nThanks, I'll use a slightly adapted version of this.\n\nPatrick\n"},{"id":"487972","messageId":"g5wshgzfv7x6om5zglsiv4bzsmhwcihwrqkmq4ebppiljqbreu@ml5eyr6zhkgu","threadId":"60794","inReplyTo":"89a88cf83eeb50542d3878c5c6e56e46f2bc3e73.1706773842.git.ps@pks.im","subject":"Re: [PATCH v2 4/5] reftable/writer: fix writing multi-level indices","fromName":"jltobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-02-05T23:56:11Z","receivedAt":"2024-02-05T23:56:17Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/02/01 08:52AM, Patrick Steinhardt wrote:\n> When finishing a section we will potentially write an index that makes\n> it more efficient to look up relevant blocks. The index records written\n> will encode, for each block of the indexed section, what the offset of\n> that block is as well as the last key of that block. Thus, the reader\n> would iterate through the index records to find the first key larger or\n> equal to the wanted key and then use the encoded offset to look up the\n> desired block.\n> \n> When there are a lot of blocks to index though we may end up writing\n> multiple index blocks, too. To not require a linear search across all\n> index blocks we instead end up writing a multi-level index. Instead of\n> referring to the block we are after, an index record may point to\n> another index block. The reader will then access the highest-level index\n> and follow down the chain of index blocks until it hits the sought-after\n> block.\n> \n> It has been observed though that it is impossible to seek ref records of\n> the last ref block when using a multi-level index. While the multi-level\n> index exists and looks fine for most of the part, the highest-level\n> index was missing an index record pointing to the last block of the next\n> index. Thus, every additional level made more refs become unseekable at\n> the end of the ref section.\n\nJust to clarify, is only the highest-level index not recording the last\nblock when multi-level indexes are being used? Or are the indexes at all\nlevels leaving the last block unreachable?\n\n> \n> The root cause is that we are not flushing the last block of the current\n> level once done writing the level. Consequently, it wasn't recorded in\n> the blocks that need to be indexed by the next-higher level and thus we\n> forgot about it.\n> \n> Fix this bug by flushing blocks after we have written all index records.\n\n -Justin\n"},{"id":"487977","messageId":"oslbbspnu4spohamhenhxyqv23fct7ltuqkdl67liw774opxwj@jjprhh7zy34o","threadId":"60794","inReplyTo":"c3492bbd42b9d2c17764208e814faccf395cb282.1706773842.git.ps@pks.im","subject":"Re: [PATCH v2 5/5] reftable: document reading and writing indices","fromName":"jltobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-02-06T01:43:07Z","receivedAt":"2024-02-06T01:43:13Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/02/01 08:52AM, Patrick Steinhardt wrote:\n> The way the index gets written and read is not trivial at all and\n> requires the reader to piece together a bunch of parts to figure out how\n> it works. Add some documentation to hopefully make this easier to\n> understand for the next reader.\n> \n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/reader.c | 27 +++++++++++++++++++++++++++\n>  reftable/writer.c | 23 +++++++++++++++++++++++\n>  2 files changed, 50 insertions(+)\n> \n> diff --git a/reftable/reader.c b/reftable/reader.c\n> index 278f727a3d..6011d0aa04 100644\n> --- a/reftable/reader.c\n> +++ b/reftable/reader.c\n> @@ -508,11 +508,38 @@ static int reader_seek_indexed(struct reftable_reader *r,\n>  \tif (err < 0)\n>  \t\tgoto done;\n>  \n> +\t/*\n> +\t * The index may consist of multiple levels, where each level may have\n> +\t * multiple index blocks. We start by doing a linear search in the\n> +\t * highest layer that identifies the relevant index block as well as\n> +\t * the record inside that block that corresponds to our wanted key.\n> +\t */\n>  \terr = reader_seek_linear(&index_iter, &want_index);\n>  \tif (err < 0)\n>  \t\tgoto done;\n>  \n> +\t/*\n> +\t * Traverse down the levels until we find a non-index entry.\n> +\t */\n>  \twhile (1) {\n> +\t\t/*\n> +\t\t * In case we seek a record that does not exist the index iter\n> +\t\t * will tell us that the iterator is over. This works because\n> +\t\t * the last index entry of the current level will contain the\n> +\t\t * last key it knows about. So in case our seeked key is larger\n> +\t\t * than the last indexed key we know that it won't exist.\n\nThe last block in the highest-level index section should end with the\nrecord key of greatest value. Doesn't that mean the initial linear seek\nshould be sufficient to stop the iterator from continuing if the wanted\nrecord key is of a greater value?\n\n> +\t\t *\n> +\t\t * There is one subtlety in the layout of the index section\n> +\t\t * that makes this work as expected: the highest-level index is\n> +\t\t * at end of the section and will point backwards and thus we\n\ns/end/the end\n\n> +\t\t * start reading from the end of the index section, not the\n> +\t\t * beginning.\n> +\t\t *\n> +\t\t * If that wasn't the case and the order was reversed then the\n> +\t\t * linear seek would seek into the lower levels and traverse\n> +\t\t * all levels of the index only to find out that the key does\n> +\t\t * not exist.\n> +\t\t */\n>  \t\terr = table_iter_next(&index_iter, &index_result);\n>  \t\ttable_iter_block_done(&index_iter);\n>  \t\tif (err != 0)\n\n-Justin\n"},{"id":"488040","messageId":"ZcHZQoqa74aUpbQl@tanuki","threadId":"60794","inReplyTo":"g5wshgzfv7x6om5zglsiv4bzsmhwcihwrqkmq4ebppiljqbreu@ml5eyr6zhkgu","subject":"Re: [PATCH v2 4/5] reftable/writer: fix writing multi-level indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-06T07:01:22Z","receivedAt":"2024-02-06T07:01:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Feb 05, 2024 at 05:56:11PM -0600, jltobler wrote:\n> On 24/02/01 08:52AM, Patrick Steinhardt wrote:\n> > When finishing a section we will potentially write an index that makes\n> > it more efficient to look up relevant blocks. The index records written\n> > will encode, for each block of the indexed section, what the offset of\n> > that block is as well as the last key of that block. Thus, the reader\n> > would iterate through the index records to find the first key larger or\n> > equal to the wanted key and then use the encoded offset to look up the\n> > desired block.\n> > \n> > When there are a lot of blocks to index though we may end up writing\n> > multiple index blocks, too. To not require a linear search across all\n> > index blocks we instead end up writing a multi-level index. Instead of\n> > referring to the block we are after, an index record may point to\n> > another index block. The reader will then access the highest-level index\n> > and follow down the chain of index blocks until it hits the sought-after\n> > block.\n> > \n> > It has been observed though that it is impossible to seek ref records of\n> > the last ref block when using a multi-level index. While the multi-level\n> > index exists and looks fine for most of the part, the highest-level\n> > index was missing an index record pointing to the last block of the next\n> > index. Thus, every additional level made more refs become unseekable at\n> > the end of the ref section.\n> \n> Just to clarify, is only the highest-level index not recording the last\n> block when multi-level indexes are being used? Or are the indexes at all\n> levels leaving the last block unreachable?\n\nEvery level N+1 looses the last block of level N. So the latter.\n\nPatrick\n\n> > \n> > The root cause is that we are not flushing the last block of the current\n> > level once done writing the level. Consequently, it wasn't recorded in\n> > the blocks that need to be indexed by the next-higher level and thus we\n> > forgot about it.\n> > \n> > Fix this bug by flushing blocks after we have written all index records.\n> \n>  -Justin\n"},{"id":"488041","messageId":"ZcHZ4HM8f1eGr710@tanuki","threadId":"60794","inReplyTo":"oslbbspnu4spohamhenhxyqv23fct7ltuqkdl67liw774opxwj@jjprhh7zy34o","subject":"Re: [PATCH v2 5/5] reftable: document reading and writing indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-06T07:04:00Z","receivedAt":"2024-02-06T07:04:04Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Feb 05, 2024 at 07:43:07PM -0600, jltobler wrote:\n> On 24/02/01 08:52AM, Patrick Steinhardt wrote:\n> > The way the index gets written and read is not trivial at all and\n> > requires the reader to piece together a bunch of parts to figure out how\n> > it works. Add some documentation to hopefully make this easier to\n> > understand for the next reader.\n> > \n> > Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> > ---\n> >  reftable/reader.c | 27 +++++++++++++++++++++++++++\n> >  reftable/writer.c | 23 +++++++++++++++++++++++\n> >  2 files changed, 50 insertions(+)\n> > \n> > diff --git a/reftable/reader.c b/reftable/reader.c\n> > index 278f727a3d..6011d0aa04 100644\n> > --- a/reftable/reader.c\n> > +++ b/reftable/reader.c\n> > @@ -508,11 +508,38 @@ static int reader_seek_indexed(struct reftable_reader *r,\n> >  \tif (err < 0)\n> >  \t\tgoto done;\n> >  \n> > +\t/*\n> > +\t * The index may consist of multiple levels, where each level may have\n> > +\t * multiple index blocks. We start by doing a linear search in the\n> > +\t * highest layer that identifies the relevant index block as well as\n> > +\t * the record inside that block that corresponds to our wanted key.\n> > +\t */\n> >  \terr = reader_seek_linear(&index_iter, &want_index);\n> >  \tif (err < 0)\n> >  \t\tgoto done;\n> >  \n> > +\t/*\n> > +\t * Traverse down the levels until we find a non-index entry.\n> > +\t */\n> >  \twhile (1) {\n> > +\t\t/*\n> > +\t\t * In case we seek a record that does not exist the index iter\n> > +\t\t * will tell us that the iterator is over. This works because\n> > +\t\t * the last index entry of the current level will contain the\n> > +\t\t * last key it knows about. So in case our seeked key is larger\n> > +\t\t * than the last indexed key we know that it won't exist.\n> \n> The last block in the highest-level index section should end with the\n> record key of greatest value. Doesn't that mean the initial linear seek\n> should be sufficient to stop the iterator from continuing if the wanted\n> record key is of a greater value?\n\nYes. But we only notice it here when calling `table_iter_next()`. The\ncall to `reader_seek_linear()` will not return an end-of-iterator\nindication.\n\nIs there any way you think this comment can be improved to clarify this?\n\nPatrick\n"}]}