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

[Kuan-Wei Chiu <visitorckw@gmail.com>]

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/20241020040200.939973-2-visitorckw@gmail.com/

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 <colyli@kernel.org> 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