Protcol Additions

Marcel Holan mh at
Thu Nov 17 09:28:43 PST 2005


On Thu, Nov 17, 2005 at 10:04:45AM -0700, Graham Batty wrote:
> Since memcache uses a hash table internally to store the data (as 
> opposed to, say, a binary tree of some sort where at least trailing 
> wildcards would be possible), it would essentially require a sequential 
> scan of the entire table to find matching entries. This would obviously 
> be very slow on any large data set.

That's true. OTOH it would not be slower than doing so "by hand" from the
application. Also, because memcached is distributed - if you'd like to keep
just a set of keys that are to be manipulated in some way (e.g. deleted),
you'd have to do so at every node of your cluster (or using memcached for

Although slow, I can clearly see the value of such a functional addition
because not always you had the chance to memoize what keys you have in
memcache that'd need deletion but if you have a clean naming scheme you know
what their name ought to be.

> The only way this could happen is either by reimplementing it using some 
> kind of tree (a splay tree would probably work pretty well for memcache) 
> so you could at least match only the beginning of the key, or by adding 
> secondary indexes that are maintained alongside the main index.

I see no problem in having this feature present with a O(n) runtime
complexity, as all alternative and viable ways @ clientside have O(n) also,
but add much more cruft to the code.

 best regards
  Marcel Holan

 project manager R&D
 PetaMem s.r.o., Ocelarska 1, 190 00 Praha, Czech Republic -

More information about the memcached mailing list