Semantic Cache: Support More Cache Cleanup Operations

[rootfs]

The Semantic Cache doesn't have a well defined garbage collection process. In line with other cache management policies, some can be implemented here such as LRU/LFU, or size based.

[aeft]

Can I work on this?

Currently, it always evicts the oldest entry. I can support LRU/LFU policy. I will make this policy configurable so that different policies can be specified in NewSemanticCache. For now, I will support:

1. evicting the least recently used entry
2. evicting the least frequently used entry

Do we keep TTLseconds in the config? Or do we still support TTL expiration? I’d prefer not to, since it may break the LRU/LFU policy. For example, a hot entry could be evicted due to TTL expiration.

Do you have some suggestions? Thanks!

[rootfs]

@aeft thanks for volunteering! For now, keep the timestamp in the cache but not use it. We may have another classifier for query freshness intent in the future. LRU and LFU are good to go. Please make sure the cache entry size can be set in total GB or raw count so we can support both in-memory and persistent storage sizing conventions.

[aeft]

1. You mean keep Timestamp in CacheEntry, right? I think I won't use this field for LRU/LFU. Currently, entry.Timestamp is updated in (1) handleRequestBody and (2) handleResponseBody. Maybe the name Timestamp is a little vague? How about remove it for now and use a more specific name later?
2. How about ttlSeconds in SemanticCache and config.yaml? I also won't use this field for LRU/LFU. How about I remove it and clean related logic (like remove cleanupExpiredEntries())
3. Sure. I will add a new field maxEntriesStorageSize in SemanticCache (just like maxEntries), if maxEntriesStorageSize > 0, it will be used to evict entries. I will also add this field to config.yaml and config.go, and set to 0 currently.

[rootfs]

@aeft if you want to have clean startup, feel free to remove all the TTL in config and in the code after I finish (#105), maybe in a day or two. WDYT?

[aeft]

Sure.

[rootfs]

@aeft There are research around adaptive semantic cache eviction. Now we have many of the building block to implement this strategy. If you feel this is something doable, please share your investigation. Thanks

[aeft]

@aeft There are research around adaptive semantic cache eviction. Now we have many of the building block to implement this strategy. If you feel this is something doable, please share your investigation. Thanks

This is interesting! I will have a look and share my thoughts later.

[arunkiyengar]

Regarding cache replacement, LRU is relatively straightforward to implement and is one of the most (if not the most) widely used cache replacement algorithms. Another option which is more complex but offers improvement over LRU is to assign a utility to cache entries and store the cache entries with the highest utility. Utility can be normalized by size; larger objects are less desirable to store as they take up more cache space. The seminal paper on this overall approach is:
Cao, P. and Irani, S., 1997. {Cost-Aware}{WWW} Proxy Caching Algorithms. In USENIX Symposium on Internet Technologies and Systems (USITS 97).
https://www.usenix.org/conference/usits-97/cost-aware-www-proxy-caching-algorithms

The SCALM approach looks complex to implement. It also seems to require a considerable analysis of the LLM workload. It isn’t clear how to use the approach if the workload is dynamic and different from the training data set.

Thus, LRU and the utility based approach are relatively straightforward to implement now, especially LRU. A clustering approach along the lines of SCALM could be an eventual objective. While the final algorithm may be inspired by SCALM, a lot of the details would need to be worked out that are not provided in the paper.