Binary Search Tree

[Chris Goffinet]

Yes, sorry meant for the code below to use incr for the counter part I  
was aware of that :)

Anyway to get around waiting for locks?


On Sep 7, 2007, at 10:10 AM, Timo Ewalds wrote:

> I don't quite follow what you're doing there, but you can always use  
> a different key as a lock to get rid of the race conditions. Just  
> use an add operation on the lock key instead of set. If the add  
> worked, you have the lock, if not, someone else does, and you can  
> act appropriately (skip, wait, whatever). The other thing you may  
> care to know, is there are incr and decr commands which are good for  
> counters.
>
> Timo
>
> Chris Goffinet wrote:
>> 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/ae238eab/attachment.htm