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

[NTPT]

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.
>>
>> -- 
>>
>> Brian Moon
>> -------------
>> http://dealnews.com/
>> Its good to be cheap =)
>>
>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.1.394 / Virus Database: 268.10.4/402 - Release Date: 27.7.2006
>