Re: Serializable Isolation without blocking - Mailing list pgsql-hackers

From Simon Riggs
Subject Re: Serializable Isolation without blocking
Date
Msg-id 1241717479.6109.314.camel@ebony.2ndQuadrant
Whole thread Raw
In response to Re: Serializable Isolation without blocking  ("Kevin Grittner" <Kevin.Grittner@wicourts.gov>)
Responses Re: Serializable Isolation without blocking  ("Kevin Grittner" <Kevin.Grittner@wicourts.gov>)
Re: Serializable Isolation without blocking  (Greg Stark <stark@enterprisedb.com>)
List pgsql-hackers
On Thu, 2009-05-07 at 10:56 -0500, Kevin Grittner wrote:
> > It's clear that any new-theory solution will cost significantly more
> > as the number of users increases, at least O(N^2), whereas simply
> > waiting is only O(N), AFAICS.
>  
> I'm not following your reasoning on the O(N^2).  Could you explain why
> you think it would follow that curve?

Each user must compare against work performed by all other users. O(N).

There are N users, so O(N^2).

With reasonable tuning we can make that work with 10 users each checking
the other's data, but with a 100 we'll end up spending more time
checking for aborts (and aborting) than we would if we had just queued
up for it.

If you want this, the simplest implementation is to quite literally
allow only a single SERIALIZABLE txn onto the system at any time. All
other SERIALIZABLEs queue. Note that simple serialization requires no
special handling for aborted transactions. Implementing that will be
fast, proving it works is trivial and it seems will work better in the
general case.

Yeh, it sucks for medium arrival rate transactions, but its great for
low or high arrival rate transactions. The new model is good for medium
arrival rates only and will take a lot of work to implement, correctly
and sufficiently optimally to keep the applicability window wide enough
to justify the effort.

Optimising it would basically entail implementing the equivalent of
block-level locking.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support



pgsql-hackers by date:

Previous
From: Tom Lane
Date:
Subject: Re: Some 8.4 changes needed according to pg_migrator testing
Next
From: Simon Riggs
Date:
Subject: Re: Re: [BUGS] BUG #4796: Recovery followed by backup creates unrecoverable WAL-file