invalidation by namespace Re: Listing all keys on a server: why?

Paul T pault12345 at
Fri Jul 28 07:06:08 UTC 2006

This hack looks like a brilliant techique and it also
illustrates why cache engine is not your standard
relational engine -- different design principles

After thinking about your approach for some time I now
 think that this could be the most efficient way ever
of implementing 'namespaces' in cache engine. 

Correct me if I'm wrong, but your solution (a bit
generalized) actually is:

1. key_salt is effectively a namespace. The point of
namespace is to allow the whole 'namespace' to expire
at once and quietly. 

2. Every time you need to access the key that belongs
to key_salt namespace (being that get or set) - you
have to fetch the key_salt from memcached (to
construct the 'full name') - that means that you have
one extra request to memcached. No big deal, but still

3. key_salt is stored in memcached forever. (there is
no official way in memcached to guarantee that,
because strictly speaking expiration==0 does not
guarantee that the key will got get pushed out in
'need more RAM' situation when the item had slided to
the end of LRU list). However, in the real life
(because it would be accessed frequently) it is
unlikely for key_salt to slide down all the way to the
end of LRU list, so it is kinda safe to assume that it
will be there 'forever', but still ;-)


 newNs(nsname) translates in set( "namespace_" .
nsname, 1, -1) 

 expiration == -1 (meaning never *ever* expire) will
fix the "how to store in the cache forever" problem
(and will be used for all those 'special' kinds of
records that people keep tryng to store in memcached
now and then)


 set_n( nsname, key, value ) and get_n( nsname, key) 

 translates into ( server side ) :

 ns = lookup the value of ( "namespace_ ". nsname )
 value = lookup the value of ( ns . ":" . key )

The performance price is *one* extra hash lookup
(serverside, C) : take the "key_salt", find in hash,
concatenate with "key" - do the "key_salt:key" lookup.


 dropNs ( name )

 translates into incr( "namespace_" . name );

 My congratulations on a *very* efficient design of
'namespaced' keys. 

 I gonna implement it that way. It is more efficient
than lazy invalidation and has no side effects (other
than 1 server-side hash lookup on a namespaced keys
access, normal keys are not affected == zero
performace impact)


 Thanks a lot and I am wondering if this kind of cache
invalidation ( "cache invalidation by namespace" ? )
has some official name maybe? 

 Instead of invalidation the entries you derive the
entries from the base and then invalidate the *base*.

 I love the levels of indirection!


--- Brian Moon <brianm at> wrote:

> > I think a lot of that comes from the lack of
> namespaces in memcached. 
> > You can't just say 'invalidate all cache entries
> for user jsmith.'  So, 
> > an obvious way to work around it is to get a list
> of active keys, run 
> > through them looking for anything that matches
> 'jsmith' and delete it.
> I know it seems hacky, but this works for us quite
> well:
> psuedo code:
> user = "jsmith"
> key_salt = get(user."_salt)
> // get user
> key = "user_data_".user."_".key_salt
> user = get(key)
> // delete all jsmith cache
> incr(key_salt)
> If you need several salts, just have a few that are
> loaded on an as 
> needed basis in a static or global var depending on
> your language.
> -- 
> Brian Moon
> -------------
> Its good to be cheap =)

Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 

More information about the memcached mailing list