Q:

Whats the best way to manage keys (in memcache ) to prevent stale cached values?

Ive recently implemented memcache on my site which has been under heavy mysql load (mysql was as optimized as I could make it). It solved all my load issues, and site is running beautifully.
The problem that Im facing now is stale cached values. I have 1hr auto expiration times on most  pages, and Im also deleting the key when the value in the DB chnages, but Im having difficulty keeping track and efficiently clearing out all the keys. 
On some pages, its trivial. I can make the key be item_id (item_4653 for example), and when the data for it is updated, or the item is deleted, the key is cleaned out.
But on most pages, I take the script filename + querystring, md5 it, and use that as the key in memcache. This is especially useful for complex urls (which are very common). 
For example I have the following page loaded.
index.php?search_keywords=good&search_section=1&sort=release&page=2
It will contain a list of items, which will be fetched from memcache. Another user then submits an item, which has "good" in its title, and it happens to be in the range of values, where it would appear on page 2, except it will not appear there, until the cache is refreshed. What makes this even more complicated, is that the newly added item will also appear on index.php?sort=newest, as well as index.php?category=some_category?page=1 and etc. Each 1 of those will have a unique key (md5 of the script name + query string).
So the newly added item might appear on dozens of pages, if they were fetched from a live DB, but it wont be visible on any of them until the stale cache is updated. The only option is to wait for the item to expire automatically.
This problem becomes even more pronounced  on my forum (custom coded), where the values HAVE to be updated on demand, for all possible cached page combinations. Lets say I have 4 page thread, and I notice 3 spam posts on page 2. After deleting them, page 2 is rebuilt, but then it also has to rebuild pages 3 and 4, otherwise there will be duplicate posts on newly rebuild page 2, and old page 3. Thats just 1 example to..... there are dozens of these scenarios. 
Any ideas?

A:

Since you are caching entire pages in memcached, your pages can't share cached data from the database with each other. Say I have page1.php and page2.php, with page1 and page2 as keys in memcached. Both pages display items. I add a new item. Now I have to expire page1 and page2.
Instead, I could have an items key in memcached, that page1.php and page2.php both use to display items. When I add a new item, I expire the items key (or better, update it's value), and both page1.php and page2.php are up-to-date.
If you still want to cache the entire page, you could add information to your keys that will change when data being cached changes (this wouldn't make sense if the data changes too often). For instance:
"page1:[timestamp of newest item]"

This way you can look up the timestamp of the newest item, an inexpensive query, and build your cache key with it. Once a newer item is added, the cache key will change, automatically expiring. This method means you still have to hit the database to see what the newest item's timestamp is, every time. 

