Strongly consistent insert

[fsdvh]

Is it possible to have strong consistency guarantees for insert operation on future/sync cache?

[tatsuya6502]

Hi. I am not sure which part of the consistency of insert operation you are referring to. But here is a brief explanation of the consistencies of the internal components of the cache:

• A Cache consists of two major components: (1) the concurrent hash table, and (2) the cache policy data structures.
• The concurrent hash table (1) stores key-value pairs you have inserted into the cache.
  • It always provides strong consistency. More specifically, it guarantees read-after-write consistency.
  • This means that if you insert a key-value pair into the cache, you can read the value immediately after the insertion and you should never get a stale value.
• The cache policy data structures (2) includes the LRU queue, LFU filter, an u64 holding the number of entries, etc. It provides (best-effort) eventual consistency, that is, it guarantees that the data structures will eventually reach a consistent state, with a small number of exceptions.
  • Eventual consistency means that if you insert a key-value pair into the cache, the cache policy data structures will not be updated immediately after the insertion, but they will eventually be updated.
    • For example, the cache can hold more entries than its capacity for a short period of time, but it will eventually evict entries to reach the capacity.
  • The cache policy data structures are updated in a batch manner, not immediately after each operation. This is to avoid lock contentions and to improve the throughput of the cache.
  • The update of the cache policy data structures is triggered implicitly by various operations, such as insert, get, remove, etc. You can also trigger the update explicitly by calling run_pending_tasks.
  • The best-effort means that there are some cases where the cache policy data structures may not reach the expected consistent state.
    • For example, the cache policy data structures may drop some cache read recordings (from get etc. methods, not from insert) when the cache is under heavy load.
    • Another example is that read recordings may not be processed in the order they were recorded. See the followings for more details: Unexpected behavior with LRU #448 (comment)
    • These exceptions exist to avoid the cache policy data structures from becoming a performance bottleneck of the cache.
    • This may have some impact to the hit rate of the cache, but it should not have a significant impact in typical use cases.
  • As of [email protected], there is no way to make the cache policy data structures strongly consistent.

If you are referring to the consistency of the concurrent hash table (1), you already have it as the table is always strongly consistent.

If you are referring to the consistency of the cache policy data structures (2), it is eventually consistent with a small number of exceptions. [email protected] does not provide a way to make the cache policy data structures strongly consistent. You can mitigate it by calling run_pending_tasks.

[fsdvh]

Thank you very much!