Binary Search Tree

[Chris Goffinet]

I was wondering if anyone had any suggestions of trying to implement a  
binary search tree using memcache? I know it wouldn't be a good  
candidate if we had multiple memcache servers, but I was thinking it  
might be doable if we partition the tree on 1 memcache node.

Our biggest concern at the moment is race conditions of the tree  
updating. I thought a binary tree might solve the problem were having  
and that is the following scenario:

1) We have hundreds of memcache objects being created (imagine rows in  
a database of users visiting a site)
2) We need to have a running list of last 10 users for the hour,  
without duplication of a users record. So we implemented the idea of a  
counter:

   if(!memcache->get("userid:$hourofday")
   {
     $counter = memcache->set("counter",1);
     memcache->set("counter:$counter", payload);
     memcache->set("userid:$hourofday",1);
   }

This would create only 1 record per hour of day, increment the  
counter, so we could build the key list in our application to pull  
last 10 items for the hour. The issue we run into is what happens when  
the following scenario happens:

   Hour 1 - > User A - Counter 1
   Hour 2 - > User A - Counter 2
   Hour 3 - > User A - Counter 3
   Hour 4 - > User A - Counter 4
   Hour 5 - > User A - Counter 5

In this case we would only just want to show User A one time  
especially since its a list of user activity. We can't store a hash  
and just push/pop because of race conditions (our first thought). If  
anyone has any ideas, I'd really appreciate it!


-Chris


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.danga.com/pipermail/memcached/attachments/20070907/36a0dd69/attachment-0001.htm