ShardedLock for better read scaling

[gz]

I'm curious if you considered using https://docs.rs/crossbeam/latest/crossbeam/sync/struct.ShardedLock.html for the RwLock (or offering as an option) given that your get() paths lock the shard readable having many readers should scale better with more threads since ShardedLock uses many cache lines to spread out the reader locks and so has less contention.

[arthurprs]

The cache is already sharded internally and each shard gets a rwlock. While I haven't tested I presume further gains from sharding the rwlock itself will only be visible in the most extreme of circumstances while hurting the other cases.

[gz]

The cache is already sharded internally and each shard gets a rwlock

I understand, but the rwlock themselves are not sharded, if you have a very read heavy workload and many threads it can be a problem because read-locks in general aren't very scalable in rust (https://docs.rs/crossbeam/latest/crossbeam/sync/struct.ShardedLock.html is a bit better)

[arthurprs]

I would take such contribution if we can have a representative benchmark showing the benefits.

[gz]

here is the branch with the changes https://github.com/gz/quick-cache/tree/sharded-rwlock

using a benchmark in our codebase https://github.com/feldera/feldera/blob/d6a59bb6e17e080c5cea6be0d9a89361143b50d3/crates/dbsp/benches/buffer_cache.rs#L1

cargo bench -p dbsp --bench buffer_cache -- --write-ratios 0,1,10,20,100 --capacity-mib 8192 --max-duration 30 --strategy s3-fifo --threads 1,2,4,8,16,32

Here are the results (machine has 64 cores, 128 threads):

 write_ratio  threads throughput_baseline throughput_variant speedup
           0        1             12.1M/s            12.0M/s   0.99x
           0        2             11.1M/s            13.8M/s   1.24x
           0        4             16.5M/s            23.4M/s   1.42x
           0        8             28.0M/s            43.2M/s   1.54x
           0       16             43.4M/s            77.5M/s   1.79x
           0       32             64.8M/s           108.1M/s   1.67x
           1        1              9.0M/s             8.7M/s   0.97x
           1        2              9.3M/s            11.1M/s   1.18x
           1        4             14.6M/s            18.7M/s   1.28x
           1        8             24.2M/s            32.5M/s   1.34x
           1       16             41.5M/s            59.5M/s   1.43x
           1       32             56.2M/s            77.8M/s   1.39x
          10        1              4.1M/s             3.8M/s   0.92x
          10        2              5.2M/s             4.8M/s   0.91x
          10        4              8.5M/s             8.0M/s   0.95x
          10        8             15.2M/s            14.8M/s   0.97x
          10       16             25.6M/s            26.9M/s   1.05x
          10       32             19.7M/s            37.3M/s   1.89x
          20        1              2.6M/s             2.4M/s   0.95x
          20        2              3.3M/s             3.1M/s   0.93x
          20        4              5.7M/s             5.4M/s   0.95x
          20        8             10.7M/s            10.0M/s   0.93x
          20       16             16.6M/s            17.7M/s   1.07x
          20       32             13.2M/s            23.6M/s   1.78x
         100        1            768.4K/s           639.0K/s   0.83x
         100        2              1.0M/s           909.1K/s   0.87x
         100        4              1.8M/s             1.6M/s   0.88x
         100        8              3.4M/s             3.0M/s   0.88x
         100       16              5.1M/s             4.7M/s   0.92x
         100       32              5.7M/s             5.4M/s   0.94x

Summary:

• The tradeoff is obvious, having faster reads hurts writes (sharding a reader lock into many cache lines means acquiring a write lock becomes more expensive)
• However in our case (and probably many other scenarios) caches have low write, high read ratios
• The sweet spot where this helps most is in the range between 0 and below 10% writes
• Afterwards still helps when there are many threads contending

let me know if you'd like me to submit a PR.

[arthurprs]

Seems like the bench threads are accessing the cache in a busy loop ish and a relatively high skew (zipf 1.1)? I don't have access to a 64/128 box but I wonder

• if increasing quick cache shard counts help at all
• how this translates to feldera usage with threads doing significant work in between cache calls

Either way it looks like there is some opportunity here? I'd take that PR with a compile time feature flag. Seems like crossbeam uses a fixed 8 shard config so in the future quick cache may have its own sharded lock.

[gz]

bench threads are accessing the cache in a busy loop ish

in the profile I looked at about 30% of time is spent in alloc+zeroing buffer, but otherwise yes a lot of contention on the cache. This isn't always what happens I agree; was trying to show the general problem

a relatively high skew (zipf 1.1)

Yes, zipf is pretty independent of the read-scaling effect from what I can tell

if increasing quick cache shard counts help at all

we fix the shard count to 256

feldera usage with threads doing significant work in between cache calls

it depends, we have different of customers with different settings/pipelines cache access patterns; some run with many threads

Either way it looks like there is some opportunity here?

I think so, I submitted a PR