Binary Search Tree
dustin at spy.net
Fri Sep 7 22:49:29 UTC 2007
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
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the memcached