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

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


>> 
>> Kent,
>> Could you please offer your opinion?
>> 
>> Thanks.
>> 
>> Coly Li