<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><br class="webkit-block-placeholder"></div><span class="Apple-tab-span" style="white-space:pre"> </span>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. :)<div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Firstly, I think there are two new commands to implement tags:</div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>1) add_tag (key, tag_name)<br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>2) invalidate_tag (tag_name)<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>I don't think there's a need for tag inspection for a given object. There is *definitely* no command to search by tag.</div><div><br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>All of the actual tags (text) would exist in a global hash table whose value is a generation number.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[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?]<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>A single global generation number is used to track invalidation events.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Each cache item contains a space for pointers to tags with their individual generation numbers and a local generation number.</div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>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.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Adding an existing tag to an item must not cause any modification to the item (i.e. check first).<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Invalidation of a tag would basically be a ``global_generation = ++tags[tag]'' kind of operation.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>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.</div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>If they're all the same, the local generation number is set to the global generation number.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>If they're different, this record doesn't exist.<br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>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.<br class="webkit-block-placeholder"></div><div><br><div> <span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div>-- </div><div>Dustin Sallings</div><br class="Apple-interchange-newline"></span> </div><br></div></body></html>