On Jul 14, 2007, at 7:12, Paul Lindner wrote:
* Wildcard (regex deletes)
There actually was some good discussion around wildcard deletes.
It'd be good to capture some of that.
As I understand it, the plan worked something like this:
There would be a ``rule list'' that was a sequential list of
deletion rules to be applied. For example:
rule 11: /^dvd:/
rule 12: /^something:/
...
Each item in the cache would have a latest rule applied indicator.
When an item was to be retrieved from the cache, we'd check to see if
any rules had been created since the last access, and if so, each
rule would be evaluated against the item's key, and then the rule
pointer would be updated.
The typical overhead on a key fetch would be a fetch and number
comparison. Deletions would be O(n) (n == items in the cache), but
be amortized over cache retrievals. The actual queueing of a rule is
O(1). In many cases, items may naturally expire, or be subject to
LRU before retrieval, so normal case *may* be better. Worst case, a
*lot* of rules get added in a short period of time, and then we go
around looking for all of the keys.
As for rule cleanup, each rule would also have a reference count. I
don't exactly know how this would work, but the basic idea is that
when a rule is added, the reference count is set to the number of
items in the cache. Each time an item is retrieved, it'd walk
through the rules that have not been applied, apply them, and
decrement the count. The count would also have to be decremented
when an item was deleted, replaced, or fell out due to LRU. When the
reference count hits 0, the rule is no longer needed.
I imagine the whole thing could be implemented with a linked list.
An item in the cache would have a pointer to the latest applied
item. if item->next, there's stuff to do.
I'm not sure how important the regex is for this vs. simple prefix
deletion. There'd need to be a regex engine. The PCRE code really
scares me.
--
Dustin Sallings
