tag proposal

[Dustin Sallings]

	Tags seem to be getting hot and lots of people have talked about it  
fairly abstractly.  I wanted to try to bring some of those together  
with respect to a memcached implementation and sit back and watch it  
all happen.  :)

	Firstly, I think there are two new commands to implement tags:

	1)  add_tag (key, tag_name)
	2)  invalidate_tag (tag_name)

	I don't think there's a need for tag inspection for a given object.   
There is *definitely* no command to search by tag.


	All of the actual tags (text) would exist in a global hash table  
whose value is a generation number.

	[It's unclear whether it's worth the effort to ever release a tag  
once it's been added.  If we assume that tags live forever, we don't  
have to refcount them and a few things get easier.  Any opinions?]


	A single global generation number is used to track invalidation events.

	Each cache item contains a space for pointers to tags with their  
individual generation numbers and a local generation number.

	When a tag is added to an item, the global generation number is  
copied into the item's local generation number (if it's not set), and  
the tag space is extended to point to the tag key at its current  
individual generation.

	Adding an existing tag to an item must not cause any modification to  
the item (i.e. check first).


	Invalidation of a tag would basically be a ``global_generation = + 
+tags[tag]'' kind of operation.

	Each time an item is requested from a cache, the local generation  
number is compared against the global generation number.  If it  
differs, each tag is checked to ensure the tag generation number  
equals the number stored for that tag.

	If they're all the same, the local generation number is set to the  
global generation number.

	If they're different, this record doesn't exist.



	I've secretly left a lot of holes in this concept as a puzzle to the  
reader.  Three units of cool to each person who finds one.

-- 
Dustin Sallings


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.danga.com/pipermail/memcached/attachments/20071003/0a6443a4/attachment.htm