Methods and systems for rule-based flexible cache invalidation

A method comprising:

• storing, by a cache validation system, a set of rules in a computer readable memory;
• receiving, by the cache validation system, a cache request, identifying a requested cache entry corresponding to the cache request, and determining that the requested cache entry is stale in response to at least one of the rules existing in the stored set of rules being satisfied by the requested cache entry;
• accepting, by the cache validation system, a rule insertion request specifying a new rule not present in the an existing set of rules stored as the set of rules in the computer readable memory;
• generating, by the cache validation system, responsive to a determination that adding the new rule to the existing set of rules would exceed a rule-set capacity limitation, a revised rule that subsumes that the union of one or more subsumable rules, where each of the one or more subsumable rules is either the new rule or a rule in the existing set of rules and the revised rule is broader than each of the subsumed rules;
• and
• updating, by the cache validation system, the set of rules to be a modified set of rules that does not exceed the capacity limitation, wherein the modified set of rules includes the revised rule and excludes the one or more subsumable rules subsumed by the revised rule.

A non-transitory computer-readable medium storing instructions that, when executed by one or more computing processors, cause the one or more computing processors to:

• store a set of rules in a rewritable computer-readable memory;
• receive a cache request, identify a requested cache entry corresponding to the cache request, and determine that the requested cache entry is stale in response to at least one of the rules existing in the stored set of rules being satisfied by the requested cache entry;
• accept a rule insertion request specifying a new rule not present in the existing stored set of rules;
• generate, responsive to a determination that adding the new rule to the existing set of rules would exceed a rule-set capacity limitation, a revised rule that subsumes the union of one or more subsumable rules, where each of the one or more subsumable rules is either the new rule or a rule in the existing set of rules, and the revised rule is broader than each of the subsumed rules;
• and
• update the stored set of rules to be a modified set of rules that does not exceed the capacity limitation, wherein the modified set of rules includes the revised rule and excludes the one or more subsumable rules subsumed by the revised rule.