Germ of an idea: Assume we can implement semaphore entirely in memcache, ignoring the fact that it can be flushed.
Then, to cope with being flushed, we could have an idea of a Semaphore as being in one of three states; Ok, Gone and Restarting. Ok is just normal operation Gone is when you know it's been flushed You detect Gone by noticing the problem when you try to touch the Semaphore (in Wait() and Signal() calls). You restart the Semaphore. Restarting is a period where you are trying to get back to Ok state. Basically, the idea will be that if the Semaphore disappears, we go into a state (Restarting) where we are going to wait for a while until we can know that the semaphore should be unused, then reset it to it's initial state (ie: unused) and we're good to go again. The way we'll do this is to wait a bit for anyone who might be using the semaphore to finish, and then once we've waiting long enough, we just assume everyone is done and proceed. It's a timeout, and it means imposing a maximum time length on holding the Semaphore that callers need to obey. Semaphores have two bits of internal state which needs to be maintained: - Counter - Wait List The Wait list really needs to be in the datastore, because if it gets flushed there's just no way to reconstitute it, Waiters will be lost forever. But the counter has more promise. Try an algorithm like this: Semaphores only have two methods which need to accomodate these states: Wait() Touch the semaphore. What state are we in? OK: Proceed as normal (if the counter is above zero then decrement it and proceed, else suspend on the wait list) GONE: Reconstruct the semaphore in Restarting state. Suspend on the wait list. RESTARTING: Suspend on the wait list. Signal() Touch the semaphore. What state are we in? OK: Proceed as normal (if there is anyone on the wait list, awaken one. Otherwise, just increment the counter) GONE: Reconstruct the semaphore in RESTARTING state. Increment the counter. If it's equal to TokenMax, then Start the semaphore. RESTARTING: Increment the counter. If it's equal to TokenMax, then Start the semaphore. Semaphores are extended as follows: A reconstructed Semaphore in RESTARTING state is initialised with Counter = 0. We are going to restart the semaphore by - defining a maximum length of time that a Semaphore token can be held (if you're using Front End tasks, just set it longer than the maximum task length). - when we restart, we schedule a Start task for a time in the future equal to the maximum task length. - When the Start task runs, it checks the Semaphore. If it's still in RESTARTING state, it Starts the Semaphore. - There is an ABA problem here. A Start task is scheduled, the Semaphore restarts before the task runs, then goes back into GONE and RESTARTING again (and another Start task is kicked off), then the original Start task runs and prematurely wakes the Semaphore. Fix this by adding a StartTaskID (uuid) to the Semaphore, generate a new one each time the Start Task runs, and pass it to the Start Task. An old StartTask will have the wrong uuid and can terminate itself based on that. Start the Semaphore: Either in the Start Task, or as the result of a Signal, we've determined that it's ok to Start the semaphore. So set the Counter to MaxCounter and change the state to OK. If there is anyone on the Wait List, wake as many of them as the counter allows, decrementing the counter for each one. =========== I think this approach can work, and the cool thing is that the counter and the state should be implementable in Memcache. If the resource you're using isn't normally under contention (very commonly this is true, contention is unusual), then your most common operations will be in Memcache and wont touch the datastore. This also assumes that cache flushing is uncommon (if it flushed often, then it should still be correct, but the performance will be poor, because the restarting process is pretty slow). If the cache flushes really, really often (sub second?) then you'll starve, but I don't think memcache does that! Any thoughts? On 27 October 2011 23:24, Emlyn <emlynore...@gmail.com> wrote: > Thanks, I had no idea that Memcache was so capable (I haven't looked > closely enough recently). You could absolutely build a semaphore using > those methods (cas would do the job nicely). Except of course that it > could disappear at any moment. I can't help thinking that there must > be some way to cope with that, however. Worth a ponder! > > On 27 October 2011 18:53, Murph <paul.j.mu...@googlemail.com> wrote: >> I think it's basically possible to do locking, mutexes, semaphores, etc in >> memcache, by taking advantage of some of the semantics, plus the new-ish >> compare & store stuff. There's the obvious caveat that it could be flushed >> without warning, or disabled for a while, so it's not a high reliability >> thing. >> >> def add(self, key, value, time=0, min_compress_len=0, namespace=None): >> """Sets a key's value, iff item is not already in memcache. >> >> def replace(self, key, value, time=0, min_compress_len=0, namespace=None): >> """Replaces a key's value, failing if item isn't already in memcache. >> >> def cas(self, key, value, time=0, min_compress_len=0, namespace=None): >> """Compare-And-Set update. >> >> def incr(self, key, delta=1, namespace=None, initial_value=None): >> """Atomically increments a key's value. >> >> def decr(self, key, delta=1, namespace=None, initial_value=None): >> """Atomically decrements a key's value. >> >> It seems to me the you could carefully use the above in various creative >> ways to implement this, if you require frequent use and the datastore costs >> would be prohibitive for it. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google App Engine" group. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/google-appengine/-/cAlYR6jxlogJ. >> To post to this group, send email to google-appengine@googlegroups.com. >> To unsubscribe from this group, send email to >> google-appengine+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/google-appengine?hl=en. >> > > > > -- > Emlyn > > http://my.syyn.cc - Synchonise Google+, Facebook, WordPress and Google > Buzz posts, > comments and all. > http://point7.wordpress.com - My blog > Find me on Facebook and Buzz > -- Emlyn http://my.syyn.cc - Synchonise Google+, Facebook, WordPress and Google Buzz posts, comments and all. http://point7.wordpress.com - My blog Find me on Facebook and Buzz -- You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com. To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.
