Re: [PATCH 0/1] bcache: reduce front IO latency during GC

On Fri, Jun 06, 2025 at 12:39:52AM -0700, Robert Pang wrote:
> Hi Kuan-Wei,
> 
> I'm circling back on our plan to address this regression. Based on our
> discussions to-date, it seems a separate min_heap API that uses the
> conventional top-down sift-down strategy is the preferred approach.
> 
> I've prototyped this idea and sent out a patch series [1] to kick off
> the discussion on this approach. The patch has been running for over
> 12 hours and is looking promising. The API name is only my initial
> thoughts and suggestions are welcome.
> 
> Given that this regression was introduced in Linux 6.11 and affects
> versions up to 6.15 (including 6.12 LTS), a timely solution will be
> important.
> 

I'm terribly sorry for not submitting the patch to fix this regression
earlier. I had something drafted, but I got sick, and the issue
unfortunately slipped off my radar and I ended up forgetting about it.

Regards,
Kuan-Wei

> Best regress
> Robert Pang
> 
> [1] https://lore.kernel.org/linux-bcache/[email protected]/T/#t
> 
> 
> On Wed, May 21, 2025 at 7:40 AM Kuan-Wei Chiu <[email protected]> wrote:
> >
> > On Tue, May 20, 2025 at 09:13:09PM +0800, Coly Li wrote:
> > >
> > >
> > > > 2025年5月20日 20:26，Kuan-Wei Chiu <[email protected]> 写道：
> > > >
> > > > On Tue, May 20, 2025 at 08:13:47PM +0800, Coly Li wrote:
> > > >>
> > > >>
> > > >>> 2025年5月20日 19:51，Kuan-Wei Chiu <[email protected]> 写道：
> > > >>>
> > > >>> On Sat, May 17, 2025 at 07:02:06PM +0800, Coly Li wrote:
> > > >>>>
> > > >>>>
> > > >>>>> 2025年5月17日 00:14，Kuan-Wei Chiu <[email protected]> 写道：
> > > >>>>>
> > > >>>>> On Thu, May 15, 2025 at 08:58:44PM -0700, Robert Pang wrote:
> > > >>>>>> Hi Kuan-Wei,
> > > >>>>>>
> > > >>>>>> Thank you for your prompt response. I tested your suggested patch to
> > > >>>>>> inline the min heap operations for 8 hours and it is still ongoing.
> > > >>>>>> Unfortunately, basing on the results so far, it didn't resolve the
> > > >>>>>> regression, suggesting inlining isn't the issue.
> > > >>>>>>
> > > >>>>>> After reviewing the commits in lib/min_heap.h, I noticed commit
> > > >>>>>> c641722 ("lib min_heap: optimize number of comparisons in
> > > >>>>>> min_heapify()") and it looked like a potential candidate. I reverted
> > > >>>>>> this commit (below) and ran the tests. While the test is still
> > > >>>>>> ongoing, the results for the past 3 hours show that the latency spikes
> > > >>>>>> during invalidate_buckets_lru() disappeared after this change,
> > > >>>>>> indicating that this commit is likely the root cause of the
> > > >>>>>> regression.
> > > >>>>>>
> > > >>>>>> My hypothesis is that while commit c641722 was designed to reduce
> > > >>>>>> comparisons with randomized input [1], it might inadvertently increase
> > > >>>>>> comparisons when the input isn't as random. A scenario where this
> > > >>>>>> could happen is within invalidate_buckets_lru() before the cache is
> > > >>>>>> fully populated. In such cases, many buckets are unfilled, causing
> > > >>>>>> new_bucket_prio() to return zero, leading to more frequent
> > > >>>>>> compare-equal operations with other unfilled buckets. In the case when
> > > >>>>>> the cache is populated, the bucket priorities fall in a range with
> > > >>>>>> many duplicates. How will heap_sift() behave in such cases?
> > > >>>>>>
> > > >>>>>> [1] https://lore.kernel.org/linux-bcache/[email protected]/
> > > >>>>>>
> > > >>>>>
> > > >>>>> You're very likely correct.
> > > >>>>>
> > > >>>>> In scenarios where the majority of elements in the heap are identical,
> > > >>>>> the traditional top-down version of heapify finishes after just 2
> > > >>>>> comparisons. However, with the bottom-up version introduced by that
> > > >>>>> commit, it ends up performing roughly 2 * log₂(n) comparisons in the
> > > >>>>> same case.
> > > >>>>
> > > >>>> For bcache scenario for ideal circumstances and best performance, the cached data
> > > >>>> and following requests should have spatial or temporal locality.
> > > >>>>
> > > >>>> I guess it means for the heap usage, the input might not be typical random.
> > > >>>>
> > > >>>>
> > > >>>>>
> > > >>>>> That said, reverting the commit would increase the number of
> > > >>>>> comparisons by about 2x in cases where all elements in the heap are
> > > >>>>> distinct, which was the original motivation for the change. I'm not
> > > >>>>> entirely sure what the best way would be to fix this regression without
> > > >>>>> negatively impacting the performance of the other use cases.
> > > >>>>
> > > >>>> If the data read model are fully sequential or random, bcache cannot help too much.
> > > >>>>
> > > >>>> So I guess maybe we still need to old heapify code? The new version is for full random input,
> > > >>>> and previous version for not that much random input.
> > > >>>>
> > > >>>
> > > >>> I think we have two options here. One is to add a classic heapify
> > > >>> function to min_heap.h, allowing users to choose based on whether they
> > > >>> expect many duplicate elements in the heap. While having two heapify
> > > >>> variants might be confusing from a library design perspective, we could
> > > >>> mitigate that with clear kernel-doc comments. The other option is to
> > > >>> revert to the old bcache heap code. I'm not sure which approach is
> > > >>> better.
> > > >>>
> > > >>
> > > >> I prefer to have two min_heap APIs, but how to name them, this is a question from me.
> > > >>
> > > >> Also if the full-random min_heap version has no user in kernel, whether to keep it in kernel also is a question.
> > > >
> > > > From the perspective of the number of comparisons in heapify, what
> > > > matters more is whether the data contains many equal elements, rather
> > > > than whether it's truly random. I assume that for most other kernel
> > > > users, their use cases don't typically involve a large number of equal
> > > > elements?
> > > >
> > >
> > > Yes, you are right.  Maybe dm-vdo also has similar I/O pattern?
> > >
> > > Deduplication may also have duplicated items in heap I guess.
> > >
> >
> > Thanks for pointing out this potential issue.
> > I'll check with Matthew to confirm.
> >
> > Regards,
> > Kuan-Wei
> >
> > > Thanks.
> > >
> > >
> > > >>
> > > >> Kent,
> > > >> Could you please offer your opinion?
> > > >>
> > > >> Thanks.
> > > >>
> > > >> Coly Li
> > >
> > >