Hackathon notes (non-binary protocol thread)

[Dustin Sallings]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.danga.com/pipermail/memcached/attachments/20070714/88d507a0/attachment.html