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

[Paul T]

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
table. 

'Aspects' or 'tags' are superset of 'table', because
table has only two dimensions and N aspects have N
dinemsions.

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
memcached. 

Basically, if you need N aspects - just maintain N
key_salts ( you would have to do one extra 'multiple
get' to fetch the salts ;-)

Rgds.Paul.


--- 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
> also
> > illustrates why cache engine is not your standard
> > relational engine -- different design principles
> > apply.
> >
> > 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 ;-)
> >
> > A.
> >
> > 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)
> >
> > B.
> >
> > 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.
> >
> >
> > 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
> 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)
> >
> > Cool!
> >
> > 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!
> >
> > 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
> 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.
> 
=== message truncated ===


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com