Binary Search Tree

[Dustin Sallings]

On Sep 7, 2007, at 15:11 , Chris Goffinet wrote:

> There is a possibility that a site could have no traffic for hours,  
> and a user visits it each hour, so the list could have a user  
> multiple times (spread by hour) since were only limiting it by the  
> hour and we do want it to be unique. So what I am wondering is, how  
> could we potentially get around this issue by avoiding locks? We  
> thought about just storing an array for a site of last 10 users,  
> then using array push/pop methods on it and use a lock method. But  
> wouldn't a lock potentially delay the script executing until the  
> lock is available (slowing down the execution time) ?

	It's worse in the case where there's no blocking lock.

	There've been talks about having ADTs on the server-side to help  
deal with some of these issues.  What you really want here is a fixed- 
size set of sorts.  That'd be neat.

	Here's a way you might be able to emulate it, but I'm not sure how  
memcached would feel about this kind of thrashing:

	Create some arbitrary prefix:   last_visitor_

	Create a counter:  last_visitor_counter

	On a given request you'd define as a ``visit,'' you can increment  
the counter and set ``last_visitor_[n]'' to the user's id.  Your last  
visitors would be the unique IDs from the the last few found here.

	That's a sloppy,  lock-free way.  If you don't mind an occasional  
lock, you can first do a get, grab the latest n values, see if you're  
in them.  If you're in them, you're done.  If you're not, you can  
then acquire a lock, grab the values again, rewrite them however you  
want to make sure you're in the set, and then release the lock.

	A failure to grab the lock is expensive (because it's non-blocking  
and you have to poll), but you can make it less frequent by storing  
more data.

	A nice alternative would be a way to CAS a value.  The ``replace''  
semantics could *almost* provide such a thing, but there'd need to be  
more information returned from a ``get'' and more that could be  
supplied to a ``cas'' to make this work.  You wouldn't want to  
transfer two different values, but it'd be awfully handy to provide  
something to summarize the value reliably.

-- 
Dustin Sallings


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