groups of keys and dependent keys

[Paul T]

> The original message described adding dependency
> relationships between 
> arbitrary keys, though, which is not quite the same
> thing as namespaces.

I think that most of the time it is the same.
Especially if you allow one key to be part of N
namespaces. 

I would like to see an example of dependency that can
not be solved by 'namespaces' ( which is logical
grouping actually - 'namespaces' is a bit confusing,
'grouping' looks more accurate ).
 
> We're already doing something pretty similar to that
> namespace proposal; 
> it works just fine. I happen to think that the
> namespace-based technique 
> is the best we're going to get without killing
> memcached's performance, 
> but I'd love to be proven wrong.

The only reasonable alternative that I can think of is
 'lasy invalidation', when request to eliminate the
group of keys ( by regexpr for example ) is *not*
processed by the client, but moves all the way to the
server - but does not result in instant execution (to
avoid blocking) but is applied as a mask for
*some*time*.

I think that good cache engine should have both
'groups' and 'lazy invalidation', commercial engines
already have it and I think that opensource engines
would get some eventually.
 
Rgds.Paul.

PS. BTW - regaring the benchmark on hash that you did.
If you've been running Judy for less that couple
hours, you might not be getting the best of it. 

In my betchmarks, the STLs Map (which is Tree) came
close to STLs Hash after couple of hours of running (I
kid you not). Could be hardware / OS specific though.

Also you might try Google hashes, they beat STL
HashMap.

PPS. Not to mention the fact that there is one line in
memcached code which is responsible for 5-10 fold
performance impact and has nothing to do with hashing
;-)

> -Steve
> 
> 
> Paul T wrote:
> > The efficient implementation of 'namespaces' is
> > described here :
> >
> >
>
http://lists.danga.com/pipermail/memcached/2006-July/002551.html
> >
> > No need to broadcast nothing, the expiration is
> > effectievly client side. 
> >
> > No substantial impact on performance either.
> >
> > Rgds.Paul.
> >
> >   
> >> A key and its dependencies may be spread across
> >> multiple servers, 
> >> memcached being a distributed system. How will a
> >> server know when it's 
> >> safe to delete something? Bear in mind that at
> some
> >> installations (ours 
> >> included, but others as well) "multiple servers"
> >> means well in excess of 
> >> 100, so "broadcast to all the other servers when
> >> something happens" is 
> >> not an option unless you're VERY frugal in the
> use
> >> of broadcasts.
> >>
> >> What happens when a server with one of the
> dependent
> >> keys crashes or its 
> >> memcached instance is restarted?
> >>
> >> Can you set different expiration times on
> different
> >> keys in a dependency 
> >> graph? What happens if the parent key's
> expiration
> >> time passes and you 
> >> try to fetch a child key? (Expiration is lazy in
> >> memcached.)
> >>
> >> What will the performance impact be on operations
> >> not involving key 
> >> dependencies? Busy memcached installations handle
> a
> >> couple tens of 
> >> thousands of requests a second, so whatever the
> >> implementation for this 
> >> looks like, it needs to be able to keep up with
> that
> >> kind of load.
> >>
> >> Don't get me wrong -- if what you describe can be
> >> made to work well, it 
> >> will definitely be useful! But I suspect it'll be
> >> trickier than it 
> >> appears to make it bulletproof.
> >>
> >> -Steve
> >>
> >>
> >> Martin Kihlgren wrote:
> >>     
> >>> Hello list.
> >>>
> >>> My name is Martin Kihlgren, and I am currently
> >>>       
> >> employed by a company
> >>     
> >>> that heavily relies on memcached.
> >>>
> >>> We are doing lots of caching, simply.
> >>>
> >>> And, unfortunately, a whole lot of
> invalidations.
> >>>
> >>> Today we got to know of
> >>>
> >>>       
> >
>
http://search.cpan.org/dist/Cache-Memcached-Managed/lib/Cache/Memcached/Managed.pm#SYNOPSIS
> >   
> >>> and I thought about the implications.
> >>>
> >>> It would be so very much nicer to have this
> >>>       
> >> functionality built into
> >>     
> >>> memcached :O
> >>>
> >>> The scheme I would imagine is:
> >>>
> >>>  * The addition of key dependency, in at least
> one
> >>>       
> >> level.
> >>     
> >>>    * A key can be declared depending on another
> >>>       
> >> key.
> >>     
> >>>  * A key can not be dropped unless all keys
> >>>       
> >> depending on it are
> >>     
> >>>    dropped.
> >>>    * If a key having dependent keys MUST be
> >>>       
> >> dropped, the whole
> >>     
> >>>      set of dependent keys are dropped as well.
> >>>
> >>> This would make it very easy for us to create
> >>>       
> >> group keys having
> >>     
> >>> dependent keys, and then just delete the group
> key
> >>>       
> >> thus forcing all
> >>     
> >>> dependent keys to be dropped.
> >>>
> >>> Much simpler and more efficient than storing the
> >>>       
> >> set of keys in the
> >>     
> >>> group in memcache (thus having to worry about
> >>>       
> >> memcache dropping the
> >>     
> >>> group key before the individual keys in the
> group
> >>>       
> >> are dropped) and
> >>     
> >>> also much better than storing the group keys on
> >>>       
> >> disk or in db.
> >>     
> >>> Is this something you have discussed? Or is it
> >>>       
> >> already in some edge
> >>     
> >>> version of memcached? Or is it something that is
> >>>       
> >> possible to do with
> >>     
> >>> the current codebase?
> >>>
> >>> regards,
> >>> //Martin Kihlgren
> >>>
> >>>   
> >>>       
> >>     
> >
> >
> > __________________________________________________
> > Do You Yahoo!?
> > Tired of spam?  Yahoo! Mail has the best spam
> protection around 
> > http://mail.yahoo.com 
> >   
> 
> 


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