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

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.

Regards,
Kuan-Wei

> Thanks.
> 
> Coly Li
> 
> 
> > 
> > Regards,
> > Kuan-Wei
> > 
> >> Best regards,
> >> Robert
> >> 
> >> ---
> >> include/linux/min_heap.h | 46 +++++++++++++++++++---------------------
> >> 1 file changed, 22 insertions(+), 24 deletions(-)
> >> 
> >> diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
> >> index 1160bed6579e..2d16e6747e36 100644
> >> --- a/include/linux/min_heap.h
> >> +++ b/include/linux/min_heap.h
> >> @@ -257,34 +257,32 @@ static __always_inline
> >> void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t
> >> elem_size,
> >>  const struct min_heap_callbacks *func, void *args)
> >> {
> >> - const unsigned long lsbit = elem_size & -elem_size;
> >> + void *left, *right, *parent, *smallest;
> >>  void *data = heap->data;
> >>  void (*swp)(void *lhs, void *rhs, void *args) = func->swp;
> >> - /* pre-scale counters for performance */
> >> - size_t a = pos * elem_size;
> >> - size_t b, c, d;
> >> - size_t n = heap->nr * elem_size;
> >> -
> >> - if (!swp)
> >> - swp = select_swap_func(data, elem_size);
> >> 
> >> - /* Find the sift-down path all the way to the leaves. */
> >> - for (b = a; c = 2 * b + elem_size, (d = c + elem_size) < n;)
> >> - b = func->less(data + c, data + d, args) ? c : d;
> >> -
> >> - /* Special case for the last leaf with no sibling. */
> >> - if (d == n)
> >> - b = c;
> >> -
> >> - /* Backtrack to the correct location. */
> >> - while (b != a && func->less(data + a, data + b, args))
> >> - b = parent(b, lsbit, elem_size);
> >> + for (;;) {
> >> + if (pos * 2 + 1 >= heap->nr)
> >> + break;
> >> 
> >> - /* Shift the element into its correct place. */
> >> - c = b;
> >> - while (b != a) {
> >> - b = parent(b, lsbit, elem_size);
> >> - do_swap(data + b, data + c, elem_size, swp, args);
> >> + left = data + ((pos * 2 + 1) * elem_size);
> >> + parent = data + (pos * elem_size);
> >> + smallest = parent;
> >> + if (func->less(left, smallest, args))
> >> + smallest = left;
> >> +
> >> + if (pos * 2 + 2 < heap->nr) {
> >> + right = data + ((pos * 2 + 2) * elem_size);
> >> + if (func->less(right, smallest, args))
> >> + smallest = right;
> >> + }
> >> + if (smallest == parent)
> >> + break;
> >> + do_swap(smallest, parent, elem_size, swp, args);
> >> + if (smallest == left)
> >> + pos = (pos * 2) + 1;
> >> + else
> >> + pos = (pos * 2) + 2;
> >>  }
> >> }
> >> 
> >> -- 
> >> 
> >> On Thu, May 15, 2025 at 12:12 AM Kuan-Wei Chiu <[email protected]> wrote:
> >>> 
> >>> Hi Robert,
> >>> 
> >>> On Wed, May 14, 2025 at 05:58:01PM -0700, Robert Pang wrote:
> >>>> Hi Coly,
> >>>> 
> >>>> My apologies for the delay in providing this update; comprehensive testing
> >>>> takes some time to complete.
> >>>> 
> >>>> As you suggested, I conducted extensive tests for 24 hours against the
> >>>> latest 6.14.5 Linux kernel, exploring more configurations to get a complete
> >>>> picture:
> >>>> 
> >>>> 1. 4KB block size with writethrough mode
> >>>> 2. 4KB block size with writeback mode (70% dirty)
> >>>> 3. 1MB block size with writethrough mode
> >>>> 
> >>>> The detailed results, available at [1], consistently demonstrate that our patch
> >>>> is effective in significantly reducing latency during garbage collection. This
> >>>> holds true for both the default writethrough mode and the 70% writeback mode.
> >>>> As anticipated, with 1MB block sizes, we observed no difference in latency
> >>>> because the number of btree nodes is much smaller.
> >>>> 
> >>>> [1] https://gist.github.com/robert-pang/817fa7c11ece99d25aabc0467a9427d8
> >>>> 
> >>>> However, during these tests, we've uncovered a new and distinct latency problem
> >>>> that appears to be introduced in the recent Linux kernel. This issue manifests
> >>>> as frequent and periodic latency spikes that occur outside of garbage
> >>>> collection.
> >>>> Below is a snippet of the latency data illustrating this:
> >>>> 
> >>>> time (s)  median (ms)  max (ms)
> >>>> 60810   2.28     679.37
> >>>> 60840   2.32   2,434.24 *
> >>>> 60870   2.46   2,434.24 *
> >>>> 60900   2.52   2,434.24 *
> >>>> 60930   2.63     566.15
> >>>> 60960   2.82     566.15
> >>>> 60990   2.82     566.15
> >>>> 61020   2.78     471.79
> >>>> 61050   2.93   2,028.54 *
> >>>> 61080   3.11   2,028.54 *
> >>>> 61110   3.29   2,028.54 *
> >>>> 61140   3.42     679.37
> >>>> 61170   3.42     679.37
> >>>> 61200   3.41     679.37
> >>>> 61230   3.30     566.15
> >>>> 61260   2.93   1,690.45 *
> >>>> 61290   2.75   1,690.45 *
> >>>> 61320   2.72   1,690.45 *
> >>>> 61350   2.88   1,408.71 *
> >>>> 61380   5.07   1,408.71 *
> >>>> 61410 107.94   1,408.71 **
> >>>> 61440  65.28   1,408.71 **
> >>>> 61470  45.41   2,028.54 **
> >>>> 61500  72.45   2,028.54 **
> >>>> 61530  55.37   2,028.54 **
> >>>> 61560  40.73   1,408.71 **
> >>>> 61590  11.48   1,690.45 **
> >>>> 61620   2.92   1,690.45 *
> >>>> 61650   2.54   1,690.45 *
> >>>> 61680   2.58     679.37
> >>>> 61710   2.78     679.37
> >>>> 
> >>>> ** garbage collection
> >>>> * cache replacement
> >>>> 
> >>>> Based on the consistent periodicity of these spikes, we deduce that they are
> >>>> linked to the invalidate_buckets_lru() function during cache replacement. This
> >>>> function was recently modified to use min heap operations [2]. To confirm our
> >>>> hypothesis, we reverted the relevant commits and re-ran the tests. Results show
> >>>> that the latency spikes completely disappeared, positively confirming that the
> >>>> min heap changes introduce this regression. Furthermore, these changes also
> >>>> reduce the effectiveness of our GC patch. It appears that the min heap changes
> >>>> reduce heap sort speed somehow in invalidate_buckets_lr() and in GC.
> >>> 
> >>> Thank you for reporting this regression and for taking the time to
> >>> perform such thorough testing.
> >>> 
> >>> My current hypothesis is that the root cause may be related to the
> >>> earlier change where the min heap API was converted from inline to
> >>> non-inline [1]. As a result, the comparison function used by the min
> >>> heap is now invoked via an indirect function call instead of a direct
> >>> one, which introduces significant overhead - especially when
> >>> CONFIG_MITIGATION_RETPOLINE is enabled, as the cost of indirect calls
> >>> can be quite substantial in that case.
> >>> 
> >>> I understand that running these tests takes considerable time, but
> >>> could you try the attached diff to see if it addresses the regression?
> >>> 
> >>> Regards,
> >>> Kuan-Wei
> >>> 
> >>> [1]: https://lore.kernel.org/lkml/[email protected]/
> >>> 
> >>> diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c
> >>> index 8998e61efa40..862e7118f81d 100644
> >>> --- a/drivers/md/bcache/alloc.c
> >>> +++ b/drivers/md/bcache/alloc.c
> >>> @@ -207,15 +207,15 @@ static void invalidate_buckets_lru(struct cache *ca)
> >>>                if (!bch_can_invalidate_bucket(ca, b))
> >>>                        continue;
> >>> 
> >>> -               if (!min_heap_full(&ca->heap))
> >>> -                       min_heap_push(&ca->heap, &b, &bucket_max_cmp_callback, ca);
> >>> +               if (!min_heap_full_inline(&ca->heap))
> >>> +                       min_heap_push_inline(&ca->heap, &b, &bucket_max_cmp_callback, ca);
> >>>                else if (!new_bucket_max_cmp(&b, min_heap_peek(&ca->heap), ca)) {
> >>>                        ca->heap.data[0] = b;
> >>> -                       min_heap_sift_down(&ca->heap, 0, &bucket_max_cmp_callback, ca);
> >>> +                       min_heap_sift_down_inline(&ca->heap, 0, &bucket_max_cmp_callback, ca);
> >>>                }
> >>>        }
> >>> 
> >>> -       min_heapify_all(&ca->heap, &bucket_min_cmp_callback, ca);
> >>> +       min_heapify_all_inline(&ca->heap, &bucket_min_cmp_callback, ca);
> >>> 
> >>>        while (!fifo_full(&ca->free_inc)) {
> >>>                if (!ca->heap.nr) {
> >>> @@ -227,8 +227,8 @@ static void invalidate_buckets_lru(struct cache *ca)
> >>>                        wake_up_gc(ca->set);
> >>>                        return;
> >>>                }
> >>> -               b = min_heap_peek(&ca->heap)[0];
> >>> -               min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca);
> >>> +               b = min_heap_peek_inline(&ca->heap)[0];
> >>> +               min_heap_pop_inline(&ca->heap, &bucket_min_cmp_callback, ca);
> >>> 
> >>>                bch_invalidate_one_bucket(ca, b);
> >>>        }
> >>> 
> >>>> 
> >>>> [2] https://lore.kernel.org/linux-bcache/ZxzkLJmhn3a%2F1ALQ@visitorckw-System-Product-Name/T/#m0dd24ba0c63615de465d3fec72dc73febb0f7a94
> >>>> 
> >>>> You may download the full test result data from these links.
> >>>> 
> >>>> https://gist.github.com/robert-pang/5df1d595ee77756c0a01d6479bdf8e34#file-bcache-latency-4kb-no-patch-csv
> >>>> https://gist.github.com/robert-pang/5df1d595ee77756c0a01d6479bdf8e34#file-bcache-latency-4kb-with-patch-csv
> >>>> https://gist.github.com/robert-pang/bcc26a3aa90dc95a083799cf4fd48116#file-bcache-latency-4kb-wb-no-patch-csv
> >>>> https://gist.github.com/robert-pang/bcc26a3aa90dc95a083799cf4fd48116#file-bcache-latency-4kb-wb-with-patch-csv
> >>>> https://gist.github.com/robert-pang/7036b06b66c8de7e958cdbddcd92a3f5#file-bcache-latency-1mb-no-patch-csv
> >>>> https://gist.github.com/robert-pang/7036b06b66c8de7e958cdbddcd92a3f5#file-bcache-latency-1mb-with-patch-csv
> >>>> https://gist.github.com/robert-pang/40f90afdea2d2a8c3f6e22ff959eff03#file-bcache-latency-4kb-no-patch-min-heap-reverted-csv
> >>>> https://gist.github.com/robert-pang/40f90afdea2d2a8c3f6e22ff959eff03#file-bcache-latency-4kb-with-patch-min-heap-reverted-csv
> >>>> 
> >>>> Best regards
> >>>> Robert Pang
> >>>> 
> >>>> On Sat, May 3, 2025 at 10:33 AM Coly Li <[email protected]> wrote:
> >>>>> 
> >>>>> On Thu, May 01, 2025 at 06:01:09PM +0800, Robert Pang wrote:
> >>>>>> Hi Coly,
> >>>>>> 
> >>>>>> Please disregard the test results I shared over a week ago. After digging
> >>>>>> deeper into the recent latency spikes with various workloads and by
> >>>>>> instrumenting the garbage collector, I realized that the earlier GC latency
> >>>>>> patch, "bcache: allow allocator to invalidate bucket in gc" [1], wasn't
> >>>>>> backported to the Linux 6.6 branch I tested my patch against. This omission
> >>>>>> explains the much higher latency observed during the extended test because the
> >>>>>> allocator was blocked for the entire GC. My sincere apologies for the
> >>>>>> inconsistent results and any confusion this has caused.
> >>>>>> 
> >>>>> 
> >>>>> Did you also backport commit 05356938a4be ("bcache: call force_wake_up_gc()
> >>>>> if necessary in check_should_bypass()") ? Last time when you pushed me to
> >>>>> add commit a14a68b76954 into mainline kernel, I tested a regression from this
> >>>>> patch and fixed it. Please add this fix if you didn't, otherwise the testing
> >>>>> might not be completed.
> >>>>> 
> >>>>> 
> >>>>>> With patch [1] back-patched and after a 24-hour re-test, the fio results clearly
> >>>>>> demonstrate that this patch effectively reduces front IO latency during GC due
> >>>>>> to the smaller incremental GC cycles, while the GC duration increase is still
> >>>>>> well within bounds.
> >>>>>> 
> >>>>> 
> >>>>> From the performance result in [2], it seems the max latency are reduced,
> >>>>> but higher latency period are longer. I am not sure whether this is a happy
> >>>>> result.
> >>>>> 
> >>>>> Can I have a download link for the whole log? Then I can look at the
> >>>>> performance numbers more close.
> >>>>> 
> >>>>>> Here's a summary of the improved latency:
> >>>>>> 
> >>>>>> Before:
> >>>>>> 
> >>>>>> Median latency (P50): 210 ms
> >>>>>> Max latency (P100): 3.5 sec
> >>>>>> 
> >>>>>> btree_gc_average_duration_ms:381138
> >>>>>> btree_gc_average_frequency_sec:3834
> >>>>>> btree_gc_last_sec:60668
> >>>>>> btree_gc_max_duration_ms:825228
> >>>>>> bset_tree_stats:
> >>>>>> btree nodes: 144330
> >>>>>> written sets: 283733
> >>>>>> unwritten sets: 144329
> >>>>>> written key bytes: 24993783392
> >>>>>> unwritten key bytes: 11777400
> >>>>>> floats: 30936844345385
> >>>>>> failed: 5776
> >>>>>> 
> >>>>>> After:
> >>>>>> 
> >>>>>> Median latency (P50): 25 ms
> >>>>>> Max latency (P100): 0.8 sec
> >>>>>> 
> >>>>>> btree_gc_average_duration_ms:622274
> >>>>>> btree_gc_average_frequency_sec:3518
> >>>>>> btree_gc_last_sec:8931
> >>>>>> btree_gc_max_duration_ms:953146
> >>>>>> bset_tree_stats:
> >>>>>> btree nodes: 175491
> >>>>>> written sets: 339078
> >>>>>> unwritten sets: 175488
> >>>>>> written key bytes: 29821314856
> >>>>>> unwritten key bytes: 14076504
> >>>>>> floats: 90520963280544
> >>>>>> failed: 6462
> >>>>>> 
> >>>>>> The complete latency data is available at [2].
> >>>>>> 
> >>>>>> I will be glad to run further tests to solidify these findings for the inclusion
> >>>>>> of this patch in the coming merge window. Let me know if you'd like me to
> >>>>>> conduct any specific tests.
> >>>>> 
> >>>>> Yes, more testing are necessary, from 512 Bytes block size to 1 MiB or
> >>>>> 8MiB block size. We need to make sure it won't introduce performance
> >>>>> regression in other workload or circumstances.
> >>>>> 
> >>>>> I don't have plan to submit this patch in this merge window, and please don't
> >>>>> push me. For performance improvement change, I prefer the defalt
> >>>>> configuration will cover most of work loads, so more testing and perforamce
> >>>>> data are desired. E.g. the patch you mentioned (commit a14a68b76954 "bcache:
> >>>>> allow allocator to invalidate bucket in gc"), it had been deployed in Easy
> >>>>> Stack product environment for 20+ months before it got merged.
> >>>>> 
> >>>>> Thanks.
> >>>>> 
> >>>>>> 
> >>>>>> [1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=a14a68b76954e73031ca6399abace17dcb77c17a
> >>>>>> [2[ https://gist.github.com/robert-pang/cc7c88f356293ea6d43103e6e5f9180f
> >>>>> 
> >>>>> [snipped]
> >>>>> 
> >>>>> --
> >>>>> Coly Li
> 
>