Clarification needed about new 'shard_index' method in 0.6.22

[joanbalaguero]

Hi Arthur,

I've seen the new version, with the public method to get the shard index for a certain key.

You say this new method can improve batch operations. I have a lot of insert/delete batches, but even with this new method I can't see how this can help, because the api does not have 'insert_many/remove_any' methods where I could send a vector of keys belonging to the same shard.

Could you please clarify?

Thanks,

Joan.

[joanbalaguero]

Hi Arthur,

Regarding the previous question, I wanted to ask for your advice about a severe latency issue we are seeing during a specific workload.

Our application uses a very large quick_cache::sync::Cache as an in-memory index for data already written to disk. The cache contains metadata pointing to disk files and offsets.

The workload is roughly:

Many concurrent GET requests doing cache.get(&key).
Periodic PUT/flush operations.
Each flush writes a disk file successfully first.
After the disk file is written, we publish around 70k–80k keys into quick_cache using cache.insert(key, value).
The cache can grow to hundreds of millions of entries during warm-up.
We originally used 64 shards, and also tested 128 shards.

During warm-up, we sometimes see severe GET p999 (even avg) latency spikes. Some stalls are multi-hundred milliseconds, and some can reach second-level latency. The system is not swapping, has no major page faults, and does not appear to be CPU-bound or disk-bound during the stall. Instead, useful CPU activity drops, and several Tokio worker threads appear to be waiting.

We captured one of the severe stalls with GDB using a release build with debug symbols. The relevant part is that several GET worker threads are blocked trying to acquire the same shard read lock:

[Thread "vc-tokio-w-00":
#7  parking_lot::raw_rwlock::RawRwLock::lock_shared_slow
    (self=0xf6165075428, recursive=false, timeout=...)
    at src/raw_rwlock.rs:721
#10 quick_cache::rw_lock::RwLock<quick_cache::shard::CacheShard<...>>::read
#11 quick_cache::sync::Cache<...>::get
#12 ventusproxycache::cache::CacheMap::get_document_or_cache_value
    at src/cache.rs:601
#13 ventusproxycache::cache::CacheMap::get_all
    at src/cache.rs:673
#14 ventusproxycache::post_handler
    at src/main.rs:732

Thread "vc-tokio-w-01":
#7  parking_lot::raw_rwlock::RawRwLock::lock_shared_slow
    (self=0xf6165075428, recursive=false, timeout=...)
    at src/raw_rwlock.rs:721
#10 quick_cache::rw_lock::RwLock<quick_cache::shard::CacheShard<...>>::read
#11 quick_cache::sync::Cache<...>::get
#12 ventusproxycache::cache::CacheMap::get_document_or_cache_value
    at src/cache.rs:601

Thread "vc-tokio-w-02":
#7  parking_lot::raw_rwlock::RawRwLock::lock_shared_slow
    (self=0xf6165075428, recursive=false, timeout=...)
    at src/raw_rwlock.rs:721
#10 quick_cache::rw_lock::RwLock<quick_cache::shard::CacheShard<...>>::read
#11 quick_cache::sync::Cache<...>::get
#12 ventusproxycache::cache::CacheMap::get_document_or_cache_value
    at src/cache.rs:601](url)

At the same time, one of our blocking PUT/flush workers is inside quick_cache::insert(). More specifically, it appears to be growing/reallocating the internal LinkedSlab storage:

Thread "vc-tokio-b-02":
#0  __memcpy_avx512_unaligned_erms
#2  _rjem_je_large_ralloc
    oldsize=167772160
    new_size=335544320
#13 alloc::raw_vec::RawVecInner::grow_amortized
#16 alloc::vec::Vec<quick_cache::linked_slab::Entry<...>>::push_mut
#17 alloc::vec::Vec<quick_cache::linked_slab::Entry<...>>::push
#18 quick_cache::linked_slab::LinkedSlab<...>::insert
    at quick_cache-0.6.22/src/linked_slab.rs:76
#19 quick_cache::shard::CacheShard<...>::insert
    at quick_cache-0.6.22/src/shard.rs:1109
#20 quick_cache::sync::Cache<...>::insert_with_lifecycle
    at quick_cache-0.6.22/src/sync.rs:468
#21 quick_cache::sync::Cache<...>::insert
    at quick_cache-0.6.22/src/sync.rs:448
#22 ventusproxycache::cache::CacheMap::push_method_data_to_cache
    at src/cache.rs:854
#23 ventusproxycache::cache::CacheMap::perform_cache_write::{closure#0}
    at src/cache.rs:811
#28 ventusproxycache::cache::CacheMap::perform_cache_write
    at src/cache.rs:810
#29 ventusproxycache::cache::CacheMap::flush
    at src/cache.rs:771
#30 ventusproxycache::perform_put::{closure#0}
    at src/main.rs:895

One detail that caught our attention is that the reader threads are all waiting on:

RawRwLock self=0xf6165075428

and the writer appears to be growing the LinkedSlab at a nearby address:

LinkedSlab / Vec self=0xf6165075430

So our interpretation is that the writer is operating on the same CacheShard whose lock the readers are blocked on. In other words, a large LinkedSlab growth/reallocation may be happening while the shard write lock is held, and concurrent readers on that shard are stalled until the reallocation finishes.

We also observed that these severe stalls tend to appear at certain cache sizes, which would be consistent with internal storage growth thresholds. Moving from 64 shards to 128 shards did not eliminate the issue, although it may slightly change the frequency/severity.

Our current publication loop is essentially:

while let Some((cache_key, mut cache_value)) = queue.pop() {
    cache_value.second_dir = second_dir;
    cache_value.filename = filename;

    cache.insert(cache_key, cache_value);
    inserted += 1;
    if inserted % 5000 == 0 {
        std::thread::yield_now();
    }
}

We previously used Rayon to parallelize this publication phase, but that made the problem worse. A single sequential loop improved things, but large stalls still happen.

We are now considering using Cache::shard_index() to group entries by shard and publish them in small round-robin bursts, for example:

64 inserts into shard 0
64 inserts into shard 1
64 inserts into shard 2
...
64 inserts into shard 127
repeat

The idea would be to avoid hammering one shard for too long and reduce reader stalls.

I have a few questions:

1. Is LinkedSlab growth/reallocation performed while holding the shard write lock?
2. If so, could this explain multi-hundred-ms or second-level reader stalls during very large insert bursts?
3. Is there any way to pre-reserve shard storage, avoid large reallocations under the shard lock, or otherwise reduce this effect? In fact, we are reserving all the expected cache size right in the cache creation. When the app starts, we already see around 24GB occuppied, that we understand belong to quick cache. But it's not reserving de whole space we set up, 100GB, just arounf 24GB.
4. Is grouping by shard_index() and publishing in small round-robin bursts a reasonable mitigation?
5. Would you recommend a different pattern for large bulk insert workloads where concurrent read latency is very important?

We are not expecting wait-free reads, but we are trying to avoid severe GET p999/avg spikes while publishing large batches into the cache.

I can provide more complete GDB logs or workload details if useful.

Best regards,
Joan.

[joanbalaguero]

Sorry Arthur, a last observation, not sure if it matters ...

We have noticed a consistent pattern in the cache size at which the stalls occur.

The severe stalls seem to happen when the total cache entry count crosses power-of-two-like thresholds:

~67 million entries ≈ 2^26
~134 million entries ≈ 2^27
~268 million entries ≈ 2^28

With 64 shards, this corresponds approximately to:

~1,048,576 entries per shard = 2^20
~2,097,152 entries per shard = 2^21
~4,194,304 entries per shard = 2^22

[joanbalaguero]

Last comment, I promise.

We have reproduced the same pattern at the next expected threshold.

After the previous stalls around ~67M, ~134M and ~268M total entries, we expected the next one around:

536,870,912 entries = 2^29

With 64 shards, this corresponds to:

8,388,608 entries per shard = 2^23

The new stall happened exactly around that point. The worst batch was:

cache_size = 536,855,567
insert_only_us = 6,274,194

This is only 15,345 entries below 2^29, and the following batch crossed the threshold.

The GDB trace from this stall also shows the expected LinkedSlab growth:

oldsize = 335,544,320
new_size = 671,088,640

The stack again goes through:

tikv_jemallocator::realloc
alloc::raw_vec::RawVecInner::grow_amortized
Vec<quick_cache::linked_slab::Entry<...>>::push
quick_cache::linked_slab::LinkedSlab::insert
quick_cache::shard::CacheShard::insert
quick_cache::sync::Cache::insert

This strongly reinforces the hypothesis that the stalls are caused by per-shard LinkedSlab capacity doubling under the shard write lock.

Well, at the end of all this stuff, and with the pattern of put/get we have (mainly these heavies put batches), is there any way to mitigate these stalls?

Thanks a lot and sorry for flooding you with comments ...

[fsdvh]

@joanbalaguero In our case, we use shard_index to group items per shard and handle insertion at that level, so we can apply back-pressure on a per-shard basis. Combined with the newly added wait-free set of methods, you can build a read bias directly into your workflow.

Example of insertion call:

async fn insert_into_cache(
    cache: Cache,
    key: K,
    entry: V,
    eviction_buffer: &mut Vec<(K, V)>,
) -> bool {
    let started = Instant::now();

    let mut key = key;
    let mut value = value;
    let mut was_inserted = false;

    for attempt in 0..=PUT_MAX_RETRIES {
        match cache.try_insert_with_state(key, value, eviction_buffer) {
            Ok(()) => {
                was_inserted = true;
                break;
            }
            Err((k, v)) if attempt < PUT_MAX_RETRIES => {
                entry_id = k;
                entry = v;
                match PUT_BACKPRESSURE_INTERVAL_MS[attempt] {
                    Some(p) => tokio::time::sleep(Duration::from_millis(p.get())).await,
                    None => tokio::task::yield_now().await,
                }
            }
            Err(_) => {
                break;
            }
        }
    }

    was_inserted
}

[fsdvh]

@joanbalaguero insert_into_cache takes the shard's exclusive lock for the whole try_insert_with_state call, including the eviction cycle. Since get contends for that same lock, reads on the affected shard queue behind the insert — so eviction work shows up as get tail-latency, not just insert latency.

[fsdvh]

@joanbalaguero sorry I was referring to the API not yet available in upsteam: #122

[arthurprs]

@joanbalaguero sorry for the late reply. Your interpretation is correct.

Yes. insert holds the shard's exclusive write lock, and when the internal slab Vec fills, push reallocates by doubling. Pre-reserving is the main fix (#123), but there was a bug in reserve() as it only reserved the hash table, not the slab.

[joanbalaguero]

Hi Arthur,

Tried it again with 0.6.24 and it works like a charm, the stalls have gone.

Thanks!
Joan.