wild card search on memcache

[Brad Fitzpatrick]

Timo,

On Sat, 19 Feb 2005, Timo Ewalds wrote:

> heh, I meant to send that to the list.
>
> I don't actually use explicit hashvalues, though I certainly should
> start. I use a wrapper around the memcache library to detect when a key
> is going to run out, and get a new value from a callback function. It is
> really only useful for entries that I don't want to be grabbed several
> times due to the expensive queries needed to generate it. Detecting it
> before hand lets me continue to use the previous version while the new
> one is being generated. That wrapper doesn't currently doesn't support
> specifying the hashvalue explicitly. The other reason for that wrapper
> is just that before I found memcache, I used a class with the same
> interface to do caching to the db.
>
> Btw, how do you cache values that you grab from the database in a range
> type query for livejournal? For something like say the comments for a
> journal entry, do you store each comment individually? or all as one?

We have one object that contains the list of comment ids for a userid.
Its key is like:

   [$userid, "list_of_comments:$userid:entry_id=123"]

(but obviously with shorter keys)  So its explicit hash value is $userid.

>From that list, we can now do one big get_multi request, which we know
will all go to the same server because they all have the same explcit
hash value (the $userid)

Then each comment is its own memcached object:

   [$userid, "comment:$userid:$entryid:comment_id=1"]
   [$userid, "comment:$userid:$entryid:comment_id=2"]
   [$userid, "comment:$userid:$entryid:comment_id=3"]
   [$userid, "comment:$userid:$entryid:comment_id=5"]

Or whatever.  (Again, with less verbose keys)

- Brad


>
> Timo
>
>
> Brad Fitzpatrick wrote:
>
> >So I'm not the only one using the explicit hashvalue support in the client
> >library?  :-)
> >
> >
> >On Fri, 18 Feb 2005, Timo Ewalds wrote:
> >
> >
> >
> >>Depending on your application, it isn't hard to get around your problem
> >>of having to touch all memcache servers. If your keys are of the form
> >>"key-<primary>-<secondary>" (as alot of mine are), and you only need to
> >>do a range search on the secondary part, then you choose the server
> >>solely based on the primary part.
> >>
> >>Timo
> >>
> >>Brad Fitzpatrick wrote:
> >>
> >>
> >>
> >>>BTW, a tree-based memcached is totally possible, but it'd only really work
> >>>for a single machine.
> >>>
> >>>You have to remember that memcached is a hash of hashes, and that's how it
> >>>spreads load.  Even if you could ask a single machine for a range of keys,
> >>>that's not to say one of the other 40 memcached servers doesn't also have
> >>>keys in that range.  And then what --- clients iterating over all the
> >>>servers?
> >>>
> >>>If you do want in-memory range searches, though, MySQL Cluster is your
> >>>answer.  It does that, and more.
> >>>
> >>>- Brad
> >>>
> >>>
> >>>On Thu, 17 Feb 2005, Skylos wrote:
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>>it would be interesting, however, if you were to make a similar to
> >>>>memcached implimentation whre instead of using hashes, used a btree
> >>>>index, which is apparently great at finding data that can be found in
> >>>>sort-related ways, like ranges and stuff.  anything greater than or
> >>>>equal to 'abc' and less than 'abd' should be efficient to find.
> >>>>
> >>>>But thats a whole new project.  memcached.btree, anybody?  :P
> >>>>
> >>>>Skylos
> >>>>
> >>>>
> >>>>On Thu, 17 Feb 2005 15:03:27 -0800, John McCaskey <johnm at klir.com> wrote:
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>>On Wed, 2005-02-02 at 18:20 +1100, Sherman Chan wrote:
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>>>Hi,
> >>>>>>I just play around memcached with PHP, and it's great, but I wonder
> >>>>>>does it supports wild card search, for example I would like to bring
> >>>>>>back all result with the key start with ABC
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>Not presently supported.
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>>>is that possible to do that?
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>Of course it is theoretically possible to add this feature, but the
> >>>>>issue is that it would be very slow.  A hash table is used internally to
> >>>>>represent the keys.  Hash tables are great for lookup of an exact value,
> >>>>>but very slow for search for values that match a wildcard type search
> >>>>>(basically have to do a full table scan comparing each key).
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>>>Thanks in advance
> >>>>>>Sherman
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>>
> >>>>>--
> >>>>>John A. McCaskey
> >>>>>Software Development Engineer
> >>>>>Klir Technologies, Inc.
> >>>>>johnm at klir.com
> >>>>>206.902.2027
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>>
> >>>>
> >>>>
> >>>
> >>>
> >>>
> >>>
> >>
> >>
> >
> >
> >
> >
>
>