We use HDDs, but this problem started occurring recently. We've been using them this way for a few years.
Not directly fitting to your setup, let's call it "just for entertainment":
This is a personal anecdote,
possibly with the same background as your problem but with
local ZFS storage: when I had setup my first PBS I did that on rotating rust (only). This worked. At first. With the amount of backups stored the number of chunks increased.
After several weeks(!) of adding more backups I had the effect that I could not list the backups in the Web Gui anymore. The first click just got a timeout. When I clicked a second time the most of the backups listing was already read into cache and now this second click worked.
The solution for my problem would be easy: kick out rotating rust. Yeah, that would've been expensive...
So
my solution (better: workaround) was to introduce fast meta data storage. This approach is possible for ZFS (with a fast "Special Device" added
before filling in much data) and also (for example) for brtfs on a Synology.
For me the "lesson learned" was no surprise as it is documented everywhere:
PBS needs IOPS!
----
Note that this metadata-optimization does
not solve
your problem as the actual data has still to be read from the spindles...