Re: [google-appengine] Re: The Dining Philosophers

[Emlyn]

On 28 October 2011 12:19, Brandon Wirtz  wrote:
> I would think that it would make more sense to store the last read Memcache
> state to instance memory (basically free), if Memcache is flushed detect and
> upload last state to memcache.

There's no way to guarantee it'd be there, is there? The task that
runs and find out that there's no memcache might be in an entirely new
instance.


> -Original Message-
> From: google-appengine@googlegroups.com
> [mailto:google-appengine@googlegroups.com] On Behalf Of Emlyn
> Sent: Thursday, October 27, 2011 5:04 PM
> To: google-appengine@googlegroups.com
> Subject: Re: [google-appengine] Re: The Dining Philosophers
>
> 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 da

RE: [google-appengine] Re: The Dining Philosophers

[Brandon Wirtz]

I would think that it would make more sense to store the last read Memcache
state to instance memory (basically free), if Memcache is flushed detect and
upload last state to memcache.


-Original Message-
From: google-appengine@googlegroups.com
[mailto:google-appengine@googlegroups.com] On Behalf Of Emlyn
Sent: Thursday, October 27, 2011 5:04 PM
To: google-appengine@googlegroups.com
Subject: Re: [google-appengine] Re: The Dining Philosophers

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  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 tha

Re: [google-appengine] Re: The Dining Philosophers

[Emlyn]

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  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  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

Re: [google-appengine] Re: The Dining Philosophers

[Emlyn]

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  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

-- 
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.

Re: [google-appengine] Re: The Dining Philosophers

[Murph]

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.

RE: [google-appengine] Re: The Dining Philosophers

[Brandon Wirtz]

My first time interviewing at Microsoft I got the Philosophers question with
Rice and Chopsticks.  I proposed two solutions... 

One that worked on position and timing... 

The other was the "Python 2.7" fix. 

doonce(BreakChopSticks);

do{think;}
while(hungry!=true)

Cut the chopsticks in half and let everyone eat half as fast, but think on
their own schedule.   The philosophers will be happier, and the code is
easier to write.



-Original Message-
From: google-appengine@googlegroups.com
[mailto:google-appengine@googlegroups.com] On Behalf Of Emlyn
Sent: Wednesday, October 26, 2011 5:39 PM
To: google-appengine@googlegroups.com
Subject: Re: [google-appengine] Re: The Dining Philosophers

On 25 October 2011 02:18, Kyle  wrote:
> Is there a reason that you didn't use the memcached service to 
> implement semaphores?
>
> -Kyle

I'm assuming you mean Memcache?

Well, two things. Firstly, as far as I know there are no transactions or
locks or anything like that for memcache, so where you need a critical
section, how will you implement it? (This is not actually a rhetorical
question; is there a way?)

Secondly, you can't trust Memcache to stick around, as far as I know.
If one task constructs a semaphore in memcache, then will that still be
there when another tasks tries to wait() on it?

Anything that is implemented in terms of Semaphores really needs to be able
to rely on them to behave. It might be good to come up with an alternative
construct that can tolerate memcache's behaviour, I'm totally open to
suggestions.



>
> On Oct 23, 6:23 am, Emlyn  wrote:
>> Here's a new AppEngine article from me, "The Dining Philosophers". It 
>> includes a full working implementation of Semaphores using the 
>> Datastore, and implementation of flawed and successful solutions to 
>> the classic Dining Philosophers problem using Semaphores.
>>
>> http://appenginedevelopment.blogspot.com/2011/10/dining-philosophers
>>
>> Fun for hard core comp sci types ;-)
>>
>> --
>> 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.
>
>



--
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.


-- 
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.

Re: [google-appengine] Re: The Dining Philosophers

[Emlyn]

On 25 October 2011 02:18, Kyle  wrote:
> Is there a reason that you didn't use the memcached service to
> implement semaphores?
>
> -Kyle

I'm assuming you mean Memcache?

Well, two things. Firstly, as far as I know there are no transactions
or locks or anything like that for memcache, so where you need a
critical section, how will you implement it? (This is not actually a
rhetorical question; is there a way?)

Secondly, you can't trust Memcache to stick around, as far as I know.
If one task constructs a semaphore in memcache, then will that still
be there when another tasks tries to wait() on it?

Anything that is implemented in terms of Semaphores really needs to be
able to rely on them to behave. It might be good to come up with an
alternative construct that can tolerate memcache's behaviour, I'm
totally open to suggestions.



>
> On Oct 23, 6:23 am, Emlyn  wrote:
>> Here's a new AppEngine article from me, "The Dining Philosophers". It
>> includes a full working implementation of Semaphores using the
>> Datastore, and implementation of flawed and successful solutions to
>> the classic Dining Philosophers problem using Semaphores.
>>
>> http://appenginedevelopment.blogspot.com/2011/10/dining-philosophers
>>
>> Fun for hard core comp sci types ;-)
>>
>> --
>> 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.
>
>



-- 
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.

[google-appengine] Re: The Dining Philosophers

[Kyle]

Is there a reason that you didn't use the memcached service to
implement semaphores?

-Kyle

On Oct 23, 6:23 am, Emlyn  wrote:
> Here's a new AppEngine article from me, "The Dining Philosophers". It
> includes a full working implementation of Semaphores using the
> Datastore, and implementation of flawed and successful solutions to
> the classic Dining Philosophers problem using Semaphores.
>
> http://appenginedevelopment.blogspot.com/2011/10/dining-philosophers
>
> Fun for hard core comp sci types ;-)
>
> --
> 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.