The Dining Philosophers in REST

Jeff Bone jbone@jump.net
Wed, 15 Aug 2001 01:53:53 -0500


--------------E9A5B2031F19E828710543D9
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit


Challenge:

     "I think you in fact can't do [GET+DELETE, or more
     generally atomic sequences of HTTP methods] within a REST
     framework, because if you do it with two calls, you get a
     race condition (what if the DELETE gets executed before the
     GET?), which means you either have to violate the
     asynchrony [?] of REST and make the interaction stateful,
     or you have to hide the DELETE call someplace in the path
     or query string of a GET request, which seems like a big
     no-no, REST-wise."

        -- Clay Shirky in [decentralization]

Clay posed race conditions as a challenge that perhaps cannot be
overcome with the REST design practice of using HTTP's generic
interfaces and resource modeling, due to a perceived need to
atomically perform a series of HTTP methods.  The claim is that an
RPC interface, by allowing the encapsulation of the desired
operations into one specialized interface that can be tunneled
through and atomically performed in the context of a single POST.

The latter strategy --- take care of all the necessaries in a single
POST --- is correct, but it doesn't require the introduction of
specialized method interfaces, just the appropriate decomposition
into resources.  I'd already been working on a short but hopefully
enlightening example --- the venerable Dining Philosophers,
serendipity! --- to demonstrate how resource modeling can handle a
similar problem.  Now deadlock and race conditions are closely
related, so I hope that by sketching this out I can convince the
reader that REST does not inherently suffer from the problem
mentioned above.

Assume that the problem space --- tables, forks, what have you --- is
implemented as a Web Service using the REST style.  The philosophers
themselves are the client applications which consume the Web
Service.  (There's a pun lurking there, but I was too lazy to go for
it. ;-)  The problem is to design a reasonable resource abstraction
of the problem domain that can be interacted with via the generic
HTTP methods without introducing new methods tunneled through HTTP.
So here goes, this is a rough cut at what the resource space looks
like --- forgive the terse and sloppy notation:

   /table
   /philosophers
   /philosophers/Hume
   /philosophers/Berkeley
   /philosophers/Hobbes
   /philosophers/Bacon
   /philosophers/Russell
   /waiter/dispenser
   /waiter/returner

Now, we assume that these resources are each implemented by, say,
servlets which share some state, either access to a persistent
database, shared application state, or whatever.  This doesn't
violate the REST model;  REST embraces the idea of data-producing
processes as resources with generic interfaces, and says nothing
about whether and how those resources communicate locally.  (I'm not
advocating lots of statefulness on servers, but any straightforward
solution to this problem will require some.  Note that Clay did not
specify that the solution be fully distributed / decentralized / p2p.
;-)

Each client application models a philosopher.  Each philosopher has a
ticket indicating their identity;  we'll ignore the specifics of how
these are obtained, authenticated, etc.  The goal of the client is to
obtain the required two forks in order to eat.  It will do this by
issuing some HTTP request(s) to the service identifying itself and
requesting the forks.  We don't have to model the forks directly in
the resource space, nor do we have to model obtaining each fork as a
separate HTTP interaction.

The resources /table, /philosophers, /philosophers/Kant, etc. are
just eye candy.  They might respond to GET requests and return some
instantaneous snapshot of the state of the overall problem and / or
indicated resources.  POSTs, PUTs, to them etc. are handled
appropriately, which is to say they probably don't have any real
behavior.  Responses from these guys are explicitly set to be
non-cacheable, and the client does *not* make decisions based on
these state snapshots.

The basic code for the philosopher client looks something like this:

philosopher(ticket) {
   while(TRUE) {
      think()  // a local call
      forks = POST /waiter/dispenser ticket
      if forks {
         eat()  // a local call
         ticket = POST /waiter/returner forks
      }
   }
}

Imagine that we have introduced to the problem space two waiters;
they act on behalf of the philosophers, who have been instructed not
to pick up or put down the forks directly themselves.  (In fact they
cannot because we don't model the forks directly.)  The desired
atomic behavior is encapsulated in and between the waiters.  One
waiter is tasked with observing the table and, at a philosopher's
request and if possible, taking from the philosopher their ticket,
removing the two adjacent forks from the table and handing them to
the philosopher.  The other waiter performs the reverse function,
exchanging forks for the corresponding ticket and placing them on the
table.

The general state of the problem is modeled as usual as an array
representing the state of the philosophers and an array of
semaphores.  The dispenser waiter will only allow a philosopher to
move into the eating state if neither neighbor is eating;  the
returner waiter manipulates the state arrays in the usual way.  The
critical sections which are usually protected by mutexes are
implemented in the waiters, and each is engaged through a single HTTP
transaction.  Very incompletely and sloppily, the implementations
look something like

/waiters/dispenser's POST handler
-----------------------------------------
onPost {
   transform the request document into a ticket & validate
   down(mutex) // a local, shared piece of state
   state[ticket] = HUNGRY
   if test(ticket) {
      give the forks to the philosopher (i.e., generate response)
   }
   up(mutex)
   down(semaphores[ticket])
}

shared server-side test operation
----------------------------------------
test(ticket) {
   if (state[ticket] == HUNGRY &&
        state[LEFT] != EATING &&
        state[RIGHT] != EATING) {
      state[ticket] = EATING
      up(semaphores[ticket])
}

/waiters/returner's POST handler
----------------------------------------
onPost {
   transform the request document into returned forks & validate
   find ticket for philosopher who got these forks
   down(mutex)
   state[ticket] = THINKING
   give the ticket back to the philosopher (i.e., generate response)
   test(LEFT)
   test(RIGHT)
   up(mutex)
}


So:  REST can do Dining Philosophers;  the trick is just to
encapsulate the critical sections into local objects and reify them
as resources.  The notion that you need some kind of transactional
control at the protocol level is, in fact, a boondoggle;
transactions are always a higher-level abstraction, and any
lower-level but complete abstraction --- INVOKE, GET / PUT / POST,
READ / WRITE / TAKE, etc. are all sufficient;  transactions can be
provided either locally or as higher-level semantics layered atop but
conforming to the semantics of the substrate.

More generally, this should at least suggest that the primary
difference between REST and procedure calling is in modeling the
problem domain as a set of resources --- nouns --- each of which can
be potentially active but which responds to a generic interface.
This as opposed to the RPC approach of specialized interfaces.  In
general, any n-ary function can be reformulated as a series of 1-ary
functions.  (Cf. currying.)  Whenever you need ACID semantics over a
series of 1-ary functions, you can usually roll those up into a
single 1-ary function operating on a large value.  And it's easy to
reformulate most (all of them I've encountered, at least) 1-ary
functions in a problem domain into resource abstractions that make
sense within the problem domain given HTTP semantics.  The problem is
one of modeling, not one of the richness and expressivity of either
approach.

---------------------------------------------------------------------

Sidenote:  Historical War Story of Tangential Significance
---------------------------------------------------------------------

The trick above is actually an example of a common pattern in
distributed application development, one that I have some personal
historical involvement with.  One of my first jobs was being an IT
whiz-kid at Sun back in the late 80s / early 90s.  One of the first
things that got thrown at me was an accelerating meltdown of Sun's
customer service support system, the internal system they used to log
and track service calls.  It was (then) a poorly designed system
built in 2 tiers, with clients accessing Sybase databases directly
inside transactions.  As the number of users N increased, performance
degraded exponentially to the point of severely impacting Sun's
ability to provide customer service at all.

The basic problem is obvious in hindsight:  the two-phase commit
protocol was managed in the client-side library, resulting in several
round-trips per transaction.  Since Sybase at the time did page-level
locking, the performance of any transactions involving a given page
was constrained to by the bandwidth and latency of the
slowest-performing client operating on that page.  (The problem was
compounded somewhat by the fact that these operations were performed
on multiple databases and dataservers, though thankfully those were
not geographically distributed.)

We introduced a middle tier whose purpose was to manage those
transactions locally to the resources being locked and manipulated,
exposing a higher-level interface to the clients which encapsulated
the transactions.  This is the common transaction manager pattern
we're all familiar with today.  To my knowledge, this was one of the
very first n-tier (n>2) architectures deployed on UNIX;  transaction
monitors / managers were a mainframe thing at that point in time, and
we had to build our own rather than buy one because they just didn't
exist for distributed environments.

The lesson is pretty clear:  it's always a bad idea to manage
transactions (i.e., attempt to guarantee atomicity of a sequence of
actions, *even if this is made possible by the underlying
communication model*) non-locally.  Whenever possible --- and it's
always possible --- atomic sequences of interactions should be
managed by intermediate objects local to the resources being locked
and manipulated;  it's trivial to encapsulate transactions into a
single atomic exchange, and exposing those encapsulations as first
class entities is generally a pretty good idea.  And it certainly
fits with the REST model of the world.  MUCH more so, in fact, than
RPC, as it forces one to aggregate those operations in the server
design rather than leaving it open to the client to abuse.  In fact,
I'd even say that doing so is critical to the ability to build
workable distributed systems.

$0.02,

jb






--------------E9A5B2031F19E828710543D9
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit

<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
 

Challenge:
"I think you in fact can't do [GET+DELETE, or more generally atomic sequences of HTTP methods] within a REST framework, because if you do it with two calls, you get a race condition (what if the DELETE gets executed before the GET?), which means you either have to violate the asynchrony [?] of REST and make the interaction stateful, or you have to hide the DELETE call someplace in the path or query string of a GET request, which seems like a big no-no, REST-wise."

   -- Clay Shirky in [decentralization]

Clay posed race conditions as a challenge that perhaps cannot be overcome with the REST design practice of using HTTP's generic interfaces and resource modeling, due to a perceived need to atomically perform a series of HTTP methods.  The claim is that an RPC interface, by allowing the encapsulation of the desired operations into one specialized interface that can be tunneled through and atomically performed in the context of a single POST.

The latter strategy --- take care of all the necessaries in a single POST --- is correct, but it doesn't require the introduction of specialized method interfaces, just the appropriate decomposition into resources.  I'd already been working on a short but hopefully enlightening example --- the venerable Dining Philosophers, serendipity! --- to demonstrate how resource modeling can handle a similar problem.  Now deadlock and race conditions are closely related, so I hope that by sketching this out I can convince the reader that REST does not inherently suffer from the problem mentioned above.

Assume that the problem space --- tables, forks, what have you --- is implemented as a Web Service using the REST style.  The philosophers themselves are the client applications which consume the Web Service.  (There's a pun lurking there, but I was too lazy to go for it. ;-)  The problem is to design a reasonable resource abstraction of the problem domain that can be interacted with via the generic HTTP methods without introducing new methods tunneled through HTTP.  So here goes, this is a rough cut at what the resource space looks like --- forgive the terse and sloppy notation:

   /table
   /philosophers
   /philosophers/Hume
   /philosophers/Berkeley
   /philosophers/Hobbes
   /philosophers/Bacon
   /philosophers/Russell
   /waiter/dispenser
   /waiter/returner

Now, we assume that these resources are each implemented by, say, servlets which share some state, either access to a persistent database, shared application state, or whatever.  This doesn't violate the REST model;  REST embraces the idea of data-producing processes as resources with generic interfaces, and says nothing about whether and how those resources communicate locally.  (I'm not advocating lots of statefulness on servers, but any straightforward solution to this problem will require some.  Note that Clay did not specify that the solution be fully distributed / decentralized / p2p. ;-)

Each client application models a philosopher.  Each philosopher has a ticket indicating their identity;  we'll ignore the specifics of how these are obtained, authenticated, etc.  The goal of the client is to obtain the required two forks in order to eat.  It will do this by issuing some HTTP request(s) to the service identifying itself and requesting the forks.  We don't have to model the forks directly in the resource space, nor do we have to model obtaining each fork as a separate HTTP interaction.

The resources /table, /philosophers, /philosophers/Kant, etc. are just eye candy.  They might respond to GET requests and return some instantaneous snapshot of the state of the overall problem and / or indicated resources.  POSTs, PUTs, to them etc. are handled appropriately, which is to say they probably don't have any real behavior.  Responses from these guys are explicitly set to be non-cacheable, and the client does *not* make decisions based on these state snapshots.

The basic code for the philosopher client looks something like this:

philosopher(ticket) {
   while(TRUE) {
      think()  // a local call
      forks = POST /waiter/dispenser ticket
      if forks {
         eat()  // a local call
         ticket = POST /waiter/returner forks
      }
   }
}

Imagine that we have introduced to the problem space two waiters;  they act on behalf of the philosophers, who have been instructed not to pick up or put down the forks directly themselves.  (In fact they cannot because we don't model the forks directly.)  The desired atomic behavior is encapsulated in and between the waiters.  One waiter is tasked with observing the table and, at a philosopher's request and if possible, taking from the philosopher their ticket, removing the two adjacent forks from the table and handing them to the philosopher.  The other waiter performs the reverse function, exchanging forks for the corresponding ticket and placing them on the table.

The general state of the problem is modeled as usual as an array representing the state of the philosophers and an array of semaphores.  The dispenser waiter will only allow a philosopher to move into the eating state if neither neighbor is eating;  the returner waiter manipulates the state arrays in the usual way.  The critical sections which are usually protected by mutexes are implemented in the waiters, and each is engaged through a single HTTP transaction.  Very incompletely and sloppily, the implementations look something like

/waiters/dispenser's POST handler
-----------------------------------------
onPost {
   transform the request document into a ticket & validate
   down(mutex) // a local, shared piece of state
   state[ticket] = HUNGRY
   if test(ticket) {
      give the forks to the philosopher (i.e., generate response)
   }
   up(mutex)
   down(semaphores[ticket])
}

shared server-side test operation
----------------------------------------
test(ticket) {
   if (state[ticket] == HUNGRY &&
        state[LEFT] != EATING &&
        state[RIGHT] != EATING) {
      state[ticket] = EATING
      up(semaphores[ticket])
}

/waiters/returner's POST handler
----------------------------------------
onPost {
   transform the request document into returned forks & validate
   find ticket for philosopher who got these forks
   down(mutex)
   state[ticket] = THINKING
   give the ticket back to the philosopher (i.e., generate response)
   test(LEFT)
   test(RIGHT)
   up(mutex)
}
 

So:  REST can do Dining Philosophers;  the trick is just to encapsulate the critical sections into local objects and reify them as resources.  The notion that you need some kind of transactional control at the protocol level is, in fact, a boondoggle;  transactions are always a higher-level abstraction, and any lower-level but complete abstraction --- INVOKE, GET / PUT / POST, READ / WRITE / TAKE, etc. are all sufficient;  transactions can be provided either locally or as higher-level semantics layered atop but conforming to the semantics of the substrate.

More generally, this should at least suggest that the primary difference between REST and procedure calling is in modeling the problem domain as a set of resources --- nouns --- each of which can be potentially active but which responds to a generic interface.  This as opposed to the RPC approach of specialized interfaces.  In general, any n-ary function can be reformulated as a series of 1-ary functions.  (Cf. currying.)  Whenever you need ACID semantics over a series of 1-ary functions, you can usually roll those up into a single 1-ary function operating on a large value.  And it's easy to reformulate most (all of them I've encountered, at least) 1-ary functions in a problem domain into resource abstractions that make sense within the problem domain given HTTP semantics.  The problem is one of modeling, not one of the richness and expressivity of either approach.

---------------------------------------------------------------------
Sidenote:  Historical War Story of Tangential Significance
---------------------------------------------------------------------

The trick above is actually an example of a common pattern in distributed application development, one that I have some personal historical involvement with.  One of my first jobs was being an IT whiz-kid at Sun back in the late 80s / early 90s.  One of the first things that got thrown at me was an accelerating meltdown of Sun's customer service support system, the internal system they used to log and track service calls.  It was (then) a poorly designed system built in 2 tiers, with clients accessing Sybase databases directly inside transactions.  As the number of users N increased, performance degraded exponentially to the point of severely impacting Sun's ability to provide customer service at all.

The basic problem is obvious in hindsight:  the two-phase commit protocol was managed in the client-side library, resulting in several round-trips per transaction.  Since Sybase at the time did page-level locking, the performance of any transactions involving a given page was constrained to by the bandwidth and latency of the slowest-performing client operating on that page.  (The problem was compounded somewhat by the fact that these operations were performed on multiple databases and dataservers, though thankfully those were not geographically distributed.)

We introduced a middle tier whose purpose was to manage those transactions locally to the resources being locked and manipulated, exposing a higher-level interface to the clients which encapsulated the transactions.  This is the common transaction manager pattern we're all familiar with today.  To my knowledge, this was one of the very first n-tier (n>2) architectures deployed on UNIX;  transaction monitors / managers were a mainframe thing at that point in time, and we had to build our own rather than buy one because they just didn't exist for distributed environments.

The lesson is pretty clear:  it's always a bad idea to manage transactions (i.e., attempt to guarantee atomicity of a sequence of actions, *even if this is made possible by the underlying communication model*) non-locally.  Whenever possible --- and it's always possible --- atomic sequences of interactions should be managed by intermediate objects local to the resources being locked and manipulated;  it's trivial to encapsulate transactions into a single atomic exchange, and exposing those encapsulations as first class entities is generally a pretty good idea.  And it certainly fits with the REST model of the world.  MUCH more so, in fact, than RPC, as it forces one to aggregate those operations in the server design rather than leaving it open to the client to abuse.  In fact, I'd even say that doing so is critical to the ability to build workable distributed systems.

$0.02,

jb
 
 
 
 
  --------------E9A5B2031F19E828710543D9--