Subject: Re: Concurrency and locking

From: [email-masked] (Jean Anderson)
Date: Thu, 14 Oct 93 14:34:07 PDT

Paul Aoki ([email-masked]) writes:
>                                    but without something like
> SELECT ... FOR UPDATE, this kind of application is likely to 
> exhibit similar behavior ....

The SELECT...FOR UPDATE oracle implemented behaves the same as the
sybase/postgres strategy of doing the write, then the read. The main 
difference is the oracle process blocks forever and ever amen unless 
you also slap a "nowait" flag on, which will make it time out with a 
lock wait error.

In other words, the strategy for managing concurrency is pretty much
the same for all these guys:

  o Detect deadlock or lock timeout
    This has admittedly been a problem because PQerrormsg hasn't always
    gotten set. But Paul Aoki has been doing a lot of work to clean up 
    errors (coming soon....). With PQerrormsg set, you can parse errors 
    correctly to discriminate between lock errors, heap_openr, etc.

  o Sleep a while
    How long depends on what you are doing.  You should sleep longer for 
    a 5 minute write than for a 2 second timestamp update.

  o Retry

Robert Withrow ([email-masked]) writes:
> What would help is if someone could post a test program stressing this
> area of postgres that we could all run, and post the results here...

I was cleaning up an old version of a test program that passed an 8 
concurrent user test last Spring on my SUN 4/110.  It gets shared memory
errors on my Sparc today :-( But if anybody wants to take a crack at it,
I put it down below. In the meantime, I'll try to figure out what the 
problem is on my Sparc.
 
-jean
 [email-masked]

-------------------------< snip, snip, snip >------------------------------
/*    
 * NAME
 *     pg_get_key -- exercise concurrency management.
 *
 * DESCRIPTION
 *     This exercises management of concurrent hits on the database with a
 *     sequencer ("unique key dispenser").
 *
 *     A blocked process should retry up to RETRIES times.
 *
 * CONFIGURATION
 *     This assumes existence of a 'keyid' class with keyname 'arid':
 *
 *     create keyid (keyname=char16, keyvalue=int4, lddate=abstime)
 *     append keyid (keyname="arid", keyvalue=1, lddate="now")
 *     define index keyid_keyname on keyid using btree (keyname char16_ops)
 *
 *     To keep sample code small, the following parameters are hardcoded 
 *     in main() and should be changed to your configuration:
 *
 *          database name  = "geodemo"
 *          tablename      = "keyid"
 *          keyname        = "arid"
 *
 * COMPILE
 *     cc -g -I$POSTGRESHOME/include -o pg_get_key pg_get_key.c \
 *         $POSTGRESHOME/lib/libpq.a -lm
 */

#include <stdio.h>
#include <sys/types.h>
#include <sys/file.h>

#include "tmp/libpq-fe.h"

extern char    PQerrormsg[];

extern int     getpid();
extern void    srand48();
extern long    lrand48();

int            pg_get_key();
int            pg_key_replace(); 
int            pg_key_retrieve();
void           pg_cleanup();
void           pg_sleep ();

#define SUCCESS          0
#define FAILURE          1
#define PG_LOCK_TIMEOUT  2
#define PG_DUP_VERSION   3

#define INVALID_KEY      0

#define BAD_VALUE       -1
#define DONE             1
#define NOT_DONE         0
#define RETRIES         10     /* Number of times to retry if timeout occurs */

int
main()
{
     char     c;
     int     key_value;          /* highest key id returned */
     int     errflag=0;     
     char    command_buf[256];

     /* ======== Open database ======== */

     PQsetdb("geodemo");     /* HARD CODED! */

     /* ======== Call pg_get_key ======== */

     if(pg_get_key("keyid", "arid", 1, &key_value) == FAILURE) 
     {    fprintf(stderr, "db_getkey failed\n");
          exit(-1);
     }
     else 
     {    fprintf(stderr, "Back from pg_get_key, ");
          fprintf(stderr, "key for %s is %d.\n", "arid", key_value);
     }

     /* ======== Close Connection ======== */
     PQfinish();
     exit(0);
}

int
pg_get_key (tname, cname, nkeys, kvalue)
char     *tname;
char     *cname;
int      nkeys;
int      *kvalue;
{
     char    *routine="pg_get_key";
     int     done, i, status;
     /* int     max_sleep_time=28;*/    /* works for 8 concurrent procs */
     int     max_sleep_time=60;    /* works for 8 concurrent procs */

     *kvalue = BAD_VALUE;          /* initialize to invalid value */

     for (i=1, done = NOT_DONE ; (i <= RETRIES) && (done == NOT_DONE) ; i++)
     {
          fprintf(stderr, "%16s: Attempt %d.\n", routine, i);

          /* ======== Begin Transaction ======== */
          (void) PQexec("begin");

          /* ======== Update keyvalue ======== */

          status = pg_key_replace (tname, cname, nkeys);
          if( status == PG_LOCK_TIMEOUT ) 
          {    fprintf(stderr, "%16s: deadlock encountered.  ", routine);
               fprintf(stderr, "Sleeping before retry.\n");

               (void) PQexec("abort");  /* probably don't need this */
               pg_sleep(max_sleep_time);
               continue;
          }
          else if ( status == FAILURE )
          {    (void) PQexec("abort");
               return(FAILURE);
          }

          /* ======== Retrieve keyvalue ======== */

          status = pg_key_retrieve (tname, cname, kvalue, i);
          if( status == PG_DUP_VERSION ) 
          {    fprintf(stderr, "%16s: Sleeping before retry.\n", routine);
               (void) PQexec("abort");
               pg_sleep(max_sleep_time);
               continue;
          }
          else if ( status == FAILURE ) 
          {    (void) PQexec("abort");
               return(FAILURE);
          }

          /* ======== Commit Change ======== */

          PQexec("end");
          done=DONE;
     }

     if( (done == NOT_DONE) || (*kvalue == BAD_VALUE) ) 
     {
          fprintf(stderr,
          "%s: tried to get '%s' key %d times, but ran out of retries.\n",
               routine, cname, i-1);
          return(FAILURE);
     }

     fprintf(stderr, "%16s: succeeded in %d tries.\n", routine, i-1);

     return (SUCCESS);
}

static
int
pg_key_replace (tname, cname, nkeys)
char    *tname;
char    *cname;
int     nkeys;
{
     char     *routine="pg_key_replace";
     char     DbQuery[200];
     char     *res;

     /* ---------------
      * Update keyvalue
      * ---------------
      */
     sprintf(DbQuery, 
          "replace %s (keyvalue=%s.keyvalue+%d) where %s.keyname=\"%s\"",
          tname, tname, nkeys, tname, cname);

     res = (char *) PQexec(DbQuery);     
     if ( pg_error(res, routine) != SUCCESS )
     {
          fprintf(stderr, "%16s: Replace failed.\n", routine);
          if (*res == 'R')     /* 'R'eally dubious assumption */
               return(PG_LOCK_TIMEOUT);
          else
               return(FAILURE);
     }

     return(SUCCESS);
}

static
int
pg_key_retrieve (tname, cname, kvalue, count)
char    *tname;
char    *cname;
int     *kvalue;
int     count;
{
     char         *routine="pg_key_retrieve";
     char         msg_buf [80];
     char         DbQuery[200];
     char         *res, *kname;
     int          ngroups, ntups, tupno, grpno;
     int          koid=0, dup_row=FALSE; /* multiple version check */
     PortalBuffer *portalbuf;
     int          status, len;

     sprintf(DbQuery,
     "retrieve portal key_port (%s.oid, %s.keyvalue, %s.keyname) where %s.keyname=\"%s\"",
          tname, tname, tname, tname, cname);

     res = (char *) PQexec(DbQuery);     
     if( pg_error(res, routine) != SUCCESS)
          return(FAILURE);

     res = (char *) PQexec("fetch all in key_port");
     if( pg_error(res, routine) != SUCCESS)
     {    pg_cleanup("key_port");
          return(FAILURE);
     }

     if (*res != 'P')
     {    fprintf(stderr, "pg_key_retrieve: no portal!");
          pg_cleanup("key_port");
          return(FAILURE);
     }

     portalbuf = PQparray(++res);
     ntups = PQntuples (portalbuf);

     if (ntups == 0 )
     {    fprintf(stderr, "%s key '%s' does not exist in class '%s'.",
               routine, cname, tname);
          pg_cleanup("key_port");
          return(FAILURE);
     }
     else if ( (ntups > 1) && (count == 1) )
     {    fprintf(stderr, 
               "%s key '%s' in class '%s' has more than 1 entry (%d).",
               routine, cname, tname, ntups);
          pg_cleanup("key_port");
          return(FAILURE);
     }

     ngroups = PQngroups(portalbuf);

     dup_row=FALSE;
     for (grpno = 0; grpno < ngroups; grpno++)
     {
          ntups = PQntuplesGroup(portalbuf, grpno);
          for (tupno = 0; tupno < ntups; tupno++)
          {
               koid = atoi(PQgetvalue(portalbuf, tupno, 0));
               *kvalue = atoi(PQgetvalue(portalbuf, tupno, 1));
          }

               /* Retry if process sees multiple versions (fixed
                * in tqual.c,v 1.18).
                */
          if(ntups > 1)
          {
               dup_row=TRUE;
               fprintf(stderr,"%16s: found multiple %s versions.\n",
                    routine, cname);
          }
     }

     pg_cleanup("key_port");

     if(dup_row==TRUE)
          return(PG_DUP_VERSION);

     return(SUCCESS);
}

static
void
pg_cleanup(port)
char     *port;
{
     char DbQuery[30];

     sprintf(DbQuery, "close %s", port);

     PQclear(port);       /* Free memory */
     PQexec(DbQuery);     /* close portal */
     return;
}

int
pg_error (pg_buffer, errtext)
char    *pg_buffer;    /* (i) Postgres results buffer */
char    *errtext;      /* (i) custom error text       */
{
     char    *routine = "pg_error";
     int     status;
     char    type_code;

          /* Get the status type */
     type_code = pg_buffer[0];

     switch (type_code)
     {
          case 'A':     /* asynchronous handling? I'm not sure */
          case 'B':     /* ready for 'copy' output */
          case 'C':     /* query 'C'ompleted   (tcop/dest.c)*/
          case 'D':     /* ready for 'copy' input */
          case 'I':     /* the last query finished (tcop/dest.c)*/
          case 'P':     /* Results are in the Portal buffer */
             status = SUCCESS;
             break;
          case 'E':     /* An error occurred */
          case 'R':     /* Something 'R'eally bad happened */
          default:
             status = FAILURE;
             break;
     }

     if(status == FAILURE)
          fprintf(stderr, "%s: %c: %s", errtext, type_code, PQerrormsg);

     return (status);
}

void
pg_sleep(max_sleep)
int max_sleep;
{
     int          pid, sleep_time;
     static int   first = TRUE;

     if (max_sleep <= 0)
          return;

                /* Seed with the UNIX pid the first time this is called. */
     if (first == TRUE) 
     {    pid = getpid ();
          srand48 (pid);
          first = FALSE;
     }

     sleep_time = (lrand48 () % max_sleep);

     fprintf(stderr, "gdi_sleep: sleeping %d seconds\n", sleep_time);

     sleep (sleep_time);
     return;
}

---

From: [email-masked] (Jean Anderson)
Date: Thu, 14 Oct 93 15:18:56 PDT

Regarding what I wrote:
> I put it down below.

I should have mentioned that it should be cracked at cautiously.  When it 
gets shared memory errors, it hoses all backends on my system.

 -jean

---

From: [email-masked] (Jean Anderson)
Date: Thu, 14 Oct 93 19:13:00 PDT

> errors on my Sparc today :-( But if anybody wants to take a crack at it,

Well, an 8 user test ran fine on another SUN 4.  Since my Sparc has been 
eating mice lately (I'm on mouse #5), I guess I'm not terribly surprised.

I modified a few things, and put a new copy down below.

A couple notes:

  o I stripped the code down so it would be small--don't take it as an
    example of something to put into production (#include disclaimer).
  o The SUN I ran it on has 24 meg of memory and was configured with
    the EMOREIPCS parameters listed in the installation instructions.
  o You don't need the tqual fix Paul mentioned so long as you load
    unique id's.  Postgres version was the straight 4.1 (no mods).
  o Your mileage (# concurrent users) may vary.  On a small DEC 5000, 
    6 worked reliably, but 8 did not.

When I run it, I usually set up a bunch of windows and let them all run.
They should all end up with unique id's. In each window that retries,
you'll see something like this:

    [jean]greip% pg_get_key
          pg_get_key: Attempt 1.
    NOTICE:Oct 14 18:03:53:Timeout -- possible deadlock
    WARN:Oct 14 18:03:53:WaitOnLock: error on wakeup - Aborting this transaction
    pg_key_replace: R: 
      pg_key_replace: Replace failed.
          pg_get_key: deadlock encountered.  Sleeping before retry.
+-> NOTICE:Oct 14 18:03:53:UserAbortTransactionBlock and not inprogress state
|   NOTICE:Oct 14 18:03:53:AbortTransaction and not in in-progress state 
|   pg_sleep: sleeping 18 seconds
|         pg_get_key: Attempt 2.
|         pg_get_key: succeeded in 2 tries.
|   Back from pg_get_key, key for arid is 57.
|
+--> That "UserAbortTransactionBlock" error is because the code does an 'abort'
     after the deadlock is detected. I can't get it to work without the abort,
     so that's one quirk to live with.

Send any improvements my way and I'll be happy to incorporate and repost.

 -jean
  [email-masked]
-------------------------< snip, snip, snip >--------------------------------
/*
 * NAME
 *     If processes run out of retries, increase max_sleep_time in 
 *     pg_get_key().
 * @(#)pg_get_key.c	1.2 10/14/93
 */

#include <stdio.h>
#include <sys/types.h>
#include <sys/file.h>

extern int     getpid();
extern void    srand48();
extern long    lrand48();

int            pg_get_key();
int            pg_key_replace(); 
int            pg_key_retrieve();
void           pg_cleanup();
void           pg_sleep ();

#define SUCCESS          0
#define FAILURE          1

#define INVALID_KEY      0

#define BAD_VALUE       -1
#define DONE             1
#define NOT_DONE         0

int
main()
{
     char     c;

int
pg_get_key (tname, cname, nkeys, kvalue)
char     *tname;
char     *cname;
int      nkeys;
int      *kvalue;
{
     char    *routine="pg_get_key";
     int     done, i, status;
     int     max_sleep_time=33;    /* Increase if processes exceed RETRIES */

               /* Doing an abort generates the error
                * "UserAbortTransactionBlock and not inprogress state".
                * But if you don't abort, you get a fatal error.
                */
               (void) PQexec("abort"); 
               pg_sleep(max_sleep_time);
               continue;
          }
          else if ( status == FAILURE )
          {    (void) PQexec("abort");
               return(FAILURE);
          }

          PQexec("end");
          done=DONE;
     }

     return (SUCCESS);
}

static
int

     /* ---------------
      * Update keyvalue
      * ---------------
      */
     sprintf(DbQuery, 

     return(SUCCESS);
}

static
int

     sprintf(DbQuery,

     if (*res != 'P')

     if (ntups == 0 )

     dup_row=FALSE;

     pg_cleanup("key_port");

     if(dup_row==TRUE)
          return(PG_DUP_VERSION);

     return(SUCCESS);
}

static
void
pg_cleanup(port)
char     *port;
{
     char DbQuery[30];

int

     switch (type_code)
     {

     if(status == FAILURE)
          fprintf(stderr, "%s: %c: %s\n", errtext, type_code, PQerrormsg);

     return (status);
}

void
pg_sleep(max_sleep)
int max_sleep;
{
     int          pid, sleep_time;
     static int   first = TRUE;

     if (max_sleep <= 0)
          return;

     fprintf(stderr, "pg_sleep: sleeping %d seconds\n", sleep_time);

     sleep (sleep_time);
     return;
}

---

From: [email-masked]
Date: Mon, 18 Oct 93 13:54:08 -0400

> actually, this application is a classic example of an application
> that *does* deadlock.  it reads TEST, thereby read locking what it's
> scanning, then tries to write TEST.  when two processes run, sometimes
> they both get read locks, then one tries to get a write lock and can't
> (because of the other process's read lock).

Yes I agree that this is a ``classic'' example.  What I was trying to
point out is that trivially simple, but real, applicatins seem to
result in deadlock using Postgres.  As an example of this consider a
order entry system that a) requires a serialized order ID, and b) must
support a policy where the discount offered varies on the customer's
yearly volume, and must modify the discount (per customer, due to
contracts and what not) on the fly when processing an order.  The
straight-forward way of dealing with these things will result in
deadlocks. 

Of course, an easy (?) way out is to use some external locking
strategy (either using a dummy relation, or fcntl, or semaphores, or
what have you) and this works fine, but it seems that it's a shame to
go outside of postgres instead of having postgres do it for you
somehow.

When I drink enough coffee in the morning I can envision something
like a postgres statement, similar to the retrieve statement:

  ``lock [instance_variable(expression,...)] [for {read|write}] [from
         clause] [where clause] [,...]''

Which would have the following semantic properties.

  1) It would do a backoff and retry (with smarts) to lock things in
some predictable order,
  2) Would allow varying granularity, from ``lock for write'' which
would lock all of postgres, to ``lock t(value) for write from t in
TEST where t.name = "foo"'', to lock the single attribute of a single
tuple.  This would include ``lock TEST for write'' to lock then entire
TEST class, and ``lock t(all) from t in TEST where t.value > 5'' which
would readlock a set of tuples.
  3) Would have a lifetime of a single transaction (begin...end) and
only 1 would be allowed for each transaction.

But even this is likely to be either 1) impossible, 2) insufficient,
or 3) both... ;-)

---
 Robert Withrow, Tel: +1 617 598 4480, Fax: +1 617 598 4430, Net: [email-masked]
 R.W. Withrow Associates, 21 Railroad Ave, Swampscott MA 01907-1821 USA

---

From: Gerry Stringer <[email-masked]>
Date: Tue, 19 Oct 93 15:20:40 BST

>>result in deadlock using Postgres.  As an example of this consider a
...
...
>> R.W. Withrow Associates, 21 Railroad Ave, Swampscott MA 01907-1821 USA

Someone else who feels the same as me - I have posted on just this
subject quite a bit in the past. It is too easy to to write a query
which can deadlock Postgres and probably lots of other DBs as well. DBs
are supposed to make it look like you're the only user of the data and
do all the necessary work to make it appear so. When writing a query
guaranteed not to deadlock, you have to have a lot of knowledge about
the underlying locking mechanisms. I fully understand the reasons for
this (I worked on DB internals for 4 years) it's just that most DBs
don't help much in this regard.

As far as suggestions for Postgres go, my vote is for the equivalent of a
"retrieve for update" type of clause which just uses write locks
internally instead of read locks. I think it gives just enough hooks to
be able to write a deadlock free transaction while hiding most of the
details.

	Regards,

		gerry

+--------------------------------+---------------------------------+
|Gerry Stringer                  |Phone: +44 954 780926            |
|Cambridge Scanning Company Ltd  |Fax:   +44 954 789829            |
|Saxon Way                       |UUCP : [email-masked]       |
|Bar Hill                        |       [email-masked]        |
|Cambridge CB3 8SL               |       			   |
|United Kingdom                  |                                 |
+--------------------------------+---------------------------------+