bcache: add "clock" cache replacement policy
@ 2025-10-09 7:15 Robert Pang
2025-10-09 22:06 ` Robert Pang
0 siblings, 1 reply; 2+ messages in thread
From: Robert Pang @ 2025-10-09 7:15 UTC (permalink / raw)
To: Coly Li, Kent Overstreet; +Cc: linux-bcache, linux-kernel, Robert Pang
This new policy extends the FIFO policy to approximate the classic clock policy
(O(n) time complexity) by considering bucket priority, similar to the LRU
policy.
This clock policy addresses the high IO latency (1-2 seconds) experienced on
multi-terabyte cache devices when the free list is empty due to the default LRU
policy. The LRU policy's O(n log n) complexity for sorting priorities for the
entire bucket list causes this delay.
Here are the average execution times (in microseconds) of the LRU and the clock
replacement policies:
SSD Size Bucket Count LRU (us) Clock (us)
375 GB 1536000 58292 1163
750 GB 3072000 121769 1729
1.5 TB 6144000 244012 3862
3 TB 12288000 496569 6428
6 TB 24576000 1067628 14298
9 TB 36864000 1564348 25763
BUG=b/452726527
TEST=presubmit
RELEASE_NOTE=Fixed bcache latency spikes.
cos-patch: bug
Change-Id: I29cc6ebd98f163fca95053e611a2b2656d654653
Signed-off-by: Robert Pang <robertpang@google.com>
Reviewed-on: https://cos-review.googlesource.com/c/third_party/kernel/+/114884
Reviewed-by: Robert Kolchmeyer <rkolchmeyer@google.com>
Main-Branch-Verified: Cusky Presubmit Bot <presubmit@cos-infra-prod.iam.gserviceaccount.com>
Tested-by: Cusky Presubmit Bot <presubmit@cos-infra-prod.iam.gserviceaccount.com>
Reviewed-on: https://cos-review.googlesource.com/c/third_party/kernel/+/116804
4 files changed
