Request: upsert with asynchronous guard

[pierrebelzile]

I’m looking at switching from moka to this. My benchmarks are amazing! Thanks so much.

One use case I have is to replace an invalid value in the cache.

I can do a get to retrieve the value. Then notice that invalid. (That’s occurs because we received a cache invalidation message with a generation/timestamp and stored that in the cache.) The cache invalid value is the minimum generation to accept from the reading the value from a network cache.

At this point there is no function that I can see that will let me atomically replace the value with a guard that ensures a single compute. I simulate it with a remove + get_value_or_guard_async. However that leaves a small window where another reader finds nothing in the cache and hence has no idea about the minimum generation to accept from the network cache.

Does that make sense or am I missing something?

It seems to me that after the retrieval of the invalid value or failing to retrieve a value, I would like to call something like cache.upsert_guard_async to compute and overwrite the invalid value or insert when nothing present.

If you agree, I can take a look at creating a PR.

[arthurprs]

Hi, glad you like it!

I think I understand the use case, but how would the API for such a function look?

[pierrebelzile]

Here is my current code:

fn obsolete(&self, key: CacheKey, new_gen: i64) {
  let _r = self.cache.insert(key, CacheValue::invalid(new_gen));
}

async fn cache_read(&self, key: &CacheKey) -> Result<CacheValue> {
        let mut min_gen = 0;
        loop {
            if let Some(v) = self.cache.get(key) {
                if v.is_valid() {
                    return Ok(v);
                } else {
                    self.cache.remove(key);
                    min_gen = v.generation
                }
            };

            // we can get here with a race condition with thread A having read min_gen > 0 and thread B seeing the
            // no value in the cache (cleared by thread A) and using min_gen == 0.
            // If B wins the race, it can proceed to get the guard and potentially retrieve an obsolete value from the network cache.
            // When it concludes thread A will then get the guard and overwrite the
            // content with a value with the min generation. But B ended up using an obsolete value.

            match self.cache.get_value_or_guard_async(key).await {
                Ok(v) => {
                    if v.is_valid() && v.generation >= min_gen {
                        return Ok(v);
                    }
                }
                Err(g) => match calc_value(key, min_gen).await {
                    Ok(v) => {
                        if let Ok(()) = g.insert(v.clone()) {
                            return Ok(v);
                        }
                        // insert failed because another write in "obsolete".
                    }
                    Err(e) => return Err(e),
                },
            }
        }
}

As you can see, because obsolete and read are not synchronized, it gets hairy quickly and its even difficult to ensure that correct. I would like to rewrite like this:

async fn obsolete(&self, key: CacheKey, new_gen: i64) {
   let (opt_val, g) = self.cache.upsert_guard_async(key);
   if opt_val.map(|v| v.generation).unwrap_or_default() < new_gen {
     g.insert(CacheValue::invalid(new_gen));
}

async fn cache_read(&self, key: &CacheKey) -> Result<CacheValue> {
   let (opt_val, guard) = self.cache.upsert_guard_async(key).await;
   let min_gen = if let Some(val) = opt_val
      if val.is_valid() {
        return Ok(val);
      }
      val.generation
   } else {
     0
   };
     
  let val = calc_value(key, min_gen).await?;
  guard.insert(val.clone());
  Ok(val)
}

The alternative would be for upsert_guard_async to take a function but I like how you do the current guard which matches what std::sync::mutex does. It provides flexibility to not do an update at all and that's great.

Cheers, Pierre

[arthurprs]

The trick is that you cannot (currently) get a "guard" for an existing value, and adding that without adding overhead for those not using the feature might be tricky.

Maybe we'll have to settle for an API like

get_validate_or_guard(&self, key: Q, validation: FnMut(&Val) -> bool) -> GuardResult<K, V>

The implementation is probably more finicky than it looks, but doable.

[xldenis]

hi @arthurprs are you open to PRs contributing a get_validate_or_guard function? We could use the same kind of api for similar purposes (timestamp invalidation of cache entries).

[arthurprs]

@xldenis I am 👍

I've since seen another feature request with slightly different semantics. I sketched an API for that in #77 (comment). But here you'd not need a mutable ref necessarily, so they actually may end up being different APIS.

[xldenis]

But here you'd not need a mutable ref necessarily, so they actually may end up being different APIS.

I'm not familiar with the codebase yet but we could achieve what we want using an entry api, do you have any preferences / hesitations about either option? Just want to make sure I'm doing to best thing here.

[arthurprs]

I really think we'll end up with both. So pick whichever one you think is best/easier for you 👍