invalidation by namespace Re: Listing all keys on a server: why?
pault12345 at yahoo.com
Fri Jul 28 09:18:02 UTC 2006
I think it is "other way around".
If we allow a key to have more than one namespace (or
'aspect', or 'tag' as Brian calls them), then what you
see as a 2 dimensional array can be seen as a set of
elements belonging to 2 namespaces.
object_ns : prefs_ns : user1 -> rendering result1
object_ns : prefs_ns : user2 -> rendering result2
When object_ns is invalidated (by incr(object_ns)),
then all the related entries would be invalidated.
If you look at object_ns and prefs_ns as 2
'coordinates' - you have two dimensional table. In
fact the snippet above describes a *three* dimensional
'Aspects' or 'tags' are superset of 'table', because
table has only two dimensions and N aspects have N
In fact, a classic "namespace" is effectively 1 hidden
aspect, attached to the 'key'.
The natural next step *is* to say, "if we allow 1
'aspect' then let's allow N aspects".
As Brian says - if you don't mind extra marshalling on
every request (and are not afraid of key_salt to
expire == have not many of them), this kind of tagging
can be already implemented on top of existing
Basically, if you need N aspects - just maintain N
key_salts ( you would have to do one extra 'multiple
get' to fetch the salts ;-)
--- NTPT <ntpt at seznam.cz> wrote:
> I think that cache acting as a 2-dimensional array
> (table or matrix - i do
> not know what term is appropriate, english is not my
> native language) where
> you can expire (or flush or wipe out or make
> invalid) one single row or
> one single column in one command , will be more
> flexibile and in fact
> implement this "namespace" behavior too.
> I think that situation where you need 2 dimensional
> cache with ability to
> expire or flush or make invalid whole row or whole
> column at once are not
> so rare. In my project for example I have "users"
> and "objects" and need
> to cache a rendered object acording user prefs and
> rendering process is time
> consuming. If object change all instance of rendered
> object must be wiped
> out of cache or make invalid (ie whole row).If user
> prefs change, all
> rendered data for this user must be wiped out of
> cache or made invalid (ie
> whole column).
> Because I can not get this behavior in memcached, I
> still use SQL database
> for this type of caching. :( (but it still give me a
> 3 - 10 times better
> performance )
> ----- Original Message -----
> From: "Paul T" <pault12345 at yahoo.com>
> To: "Brian Moon" <brianm at dealnews.com>; "Jacob Coby"
> <jcoby at listingbook.com>; <memcached at lists.danga.com>
> Sent: Friday, July 28, 2006 9:06 AM
> Subject: invalidation by namespace Re: Listing all
> keys on a server: why?
> > This hack looks like a brilliant techique and it
> > illustrates why cache engine is not your standard
> > relational engine -- different design principles
> > apply.
> > After thinking about your approach for some time I
> > think that this could be the most efficient way
> > 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
> > namespace is to allow the whole 'namespace' to
> > at once and quietly.
> > 2. Every time you need to access the key that
> > to key_salt namespace (being that get or set) -
> > have to fetch the key_salt from memcached (to
> > construct the 'full name') - that means that you
> > one extra request to memcached. No big deal, but
> > ;-)
> > 3. key_salt is stored in memcached forever. (there
> > 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
> > 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
> > end of LRU list, so it is kinda safe to assume
> that it
> > will be there 'forever', but still ;-)
> > A.
> > newNs(nsname) translates in set( "namespace_" .
> > nsname, 1, -1)
> > expiration == -1 (meaning never *ever* expire)
> > fix the "how to store in the cache forever"
> > (and will be used for all those 'special' kinds of
> > records that people keep tryng to store in
> > now and then)
> > B.
> > set_n( nsname, key, value ) and get_n( nsname,
> > 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
> > concatenate with "key" - do the "key_salt:key"
> > C.
> > 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
> > than lazy invalidation and has no side effects
> > than 1 server-side hash lookup on a namespaced
> > access, normal keys are not affected == zero
> > performace impact)
> > Cool!
> > Thanks a lot and I am wondering if this kind of
> > 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
> > I love the levels of indirection!
> > Rgds.Paul.
> > --- Brian Moon <brianm at dealnews.com> wrote:
> >> > I think a lot of that comes from the lack of
> >> namespaces in memcached.
> >> > You can't just say 'invalidate all cache
> >> for user jsmith.' So,
> >> > an obvious way to work around it is to get a
> >> 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
> >> 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
> >> loaded on an as
> >> needed basis in a static or global var depending
> >> your language.
=== message truncated ===
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
More information about the memcached