tag proposal

Dustin Sallings dustin at spy.net
Thu Oct 4 08:11:10 UTC 2007


On Oct 4, 2007, at 0:54, Brenton Alker wrote:

> > Firstly, I think there are two new commands to implement tags:
> >
> > 1)  add_tag (key, tag_name)
> > 2)  invalidate_tag (tag_name)
>
> Using these commands, would that mean that adding a key with tags,  
> would require 2 commands from the client, or are there "internal"  
> commands, and the tags would be passed as part of the set request  
> (as discussed in previous threads on the topic)?

	No, tagging is orthogonal to defining items within the cache.   
Otherwise, you'd at the very least need a tagging version of set,  
add, update, or to extend the protocol for these and any other  
mutation commands that might cause things to exist (such as binary  
incr).

	The only reasonable optimizations would be a multi-tag for the text  
protocol and a corresponding silent tag for the binary protocol.

> Multiple tags per key would make them _much_ more useful for me  
> also, but I can also see that this may be a sticking point for the  
> implementation when adhering to the goal that memcache operations  
> should be O(1), it was in my client-side (script, not memcache- 
> client) implementation.

	I'm not quite sure what you mean here.

> Using the algorithm you described, I think that would make a get  
> operation O(n), because it would need to check each tag for each  
> key to ensure it hasn't been invalidated. This could, of course, be  
> quite significant for multi-gets with many keys. Unless there is  
> some trick I'm unaware of (quite possible, I'm a scripter, not a C  
> coder).

	The purpose of the global generation was to make the *typical* get  
add only a single integer comparison.  After any tag invalidation (or  
multiple tag invalidations), any fetch will additionally have to  
validate each of its tags once.

	Your point is true when the multi-get with many keys with many tags  
occurs after a tag invalidation.  This is expected to be less common  
than a get where there hasn't been a tag invalidation.

	Even then, the process of validating the tags *should* be cheap.

-- 
Dustin Sallings




More information about the memcached mailing list