<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:times new roman, new york, times, serif;font-size:12pt"><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;">This makes the assumption that the lock wasn't lost by LRU or a failed cache server. If it was, then you could have two clients who believe they obtained the lock. The domain might consider this an edge case problem that doesn't need to be solved, since it would be non-critical data that would self-heal later on. However, that's a design decision and would need to be noted. If you need a reliable lock, you'll likely need it register it in the database and manage it that way.<br><br><div style="font-family: times new roman,new york,times,serif; font-size: 12pt;">----- Original Message ----<br>From: Timo Ewalds <timo@tzc.com><br>To: Chris Goffinet <goffinet@yahoo-inc.com><br>Cc:
memcached@lists.danga.com<br>Sent: Friday, September 7, 2007 10:10:18 AM<br>Subject: Re: Binary Search Tree<br><br>
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.<br>
<br>
Timo<br>
<br>
Chris Goffinet wrote:
<blockquote type="cite">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. <br>
<br>
<div>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:</div>
<div><br class="webkit-block-placeholder">
</div>
<div>1) We have hundreds of memcache objects being created (imagine
rows in a database of users visiting a site)</div>
<div>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:</div>
<div><br class="webkit-block-placeholder">
</div>
<div> if(!memcache->get("userid:$hourofday")</div>
<div> {</div>
<div> $counter = memcache->set("counter",1);</div>
<div> memcache->set("counter:$counter", payload);</div>
<div> memcache->set("userid:$hourofday",1);</div>
<div> }<br>
<div><br class="webkit-block-placeholder">
</div>
<div> <span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-indent: 0px; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;">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:</span></div>
<div><br class="webkit-block-placeholder">
</div>
<div><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-indent: 0px; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;"> Hour
1 - > User A - Counter 1</span></div>
<div><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-indent: 0px; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;"> Hour
2 - > User A - Counter 2</span></div>
<div> Hour 3 - > User A - Counter 3</div>
<div>
<div> Hour 4 - > User A - Counter 4</div>
<div> Hour 5 - > User A - Counter 5</div>
<div><br class="webkit-block-placeholder">
</div>
</div>
<div><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-indent: 0px; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;">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!</span></div>
<div><br>
</div>
<div><br class="webkit-block-placeholder">
</div>
<div><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-indent: 0px; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px;">
<div>-Chris</div>
<br class="Apple-interchange-newline">
</span> </div>
<br>
</div>
</blockquote>
</div><br></div></div><br>
<hr size=1>Got a little couch potato? <br>
Check out fun <a href="http://us.rd.yahoo.com/evt=48248/*http://search.yahoo.com/search?fr=oni_on_mail&p=summer+activities+for+kids&cs=bz">summer activities for kids.</a></body></html>