Re: [PATCH v2 4/5] reftable/writer: fix writing multi-level indices

[Patrick Steinhardt <ps@pks.im>]

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

On Mon, Feb 05, 2024 at 05:56:11PM -0600, jltobler wrote:
> On 24/02/01 08:52AM, Patrick Steinhardt wrote:
> > When finishing a section we will potentially write an index that makes
> > it more efficient to look up relevant blocks. The index records written
> > will encode, for each block of the indexed section, what the offset of
> > that block is as well as the last key of that block. Thus, the reader
> > would iterate through the index records to find the first key larger or
> > equal to the wanted key and then use the encoded offset to look up the
> > desired block.
> > 
> > When there are a lot of blocks to index though we may end up writing
> > multiple index blocks, too. To not require a linear search across all
> > index blocks we instead end up writing a multi-level index. Instead of
> > referring to the block we are after, an index record may point to
> > another index block. The reader will then access the highest-level index
> > and follow down the chain of index blocks until it hits the sought-after
> > block.
> > 
> > It has been observed though that it is impossible to seek ref records of
> > the last ref block when using a multi-level index. While the multi-level
> > index exists and looks fine for most of the part, the highest-level
> > index was missing an index record pointing to the last block of the next
> > index. Thus, every additional level made more refs become unseekable at
> > the end of the ref section.
> 
> Just to clarify, is only the highest-level index not recording the last
> block when multi-level indexes are being used? Or are the indexes at all
> levels leaving the last block unreachable?

Every level N+1 looses the last block of level N. So the latter.

Patrick

> > 
> > The root cause is that we are not flushing the last block of the current
> > level once done writing the level. Consequently, it wasn't recorded in
> > the blocks that need to be indexed by the next-higher level and thus we
> > forgot about it.
> > 
> > Fix this bug by flushing blocks after we have written all index records.
> 
>  -Justin

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