PostgreSQL Concurrency Issues

PostgreSQL Concurrency Issues 1

Tom Lane

Red Hat Database Group

Red Hat, Inc.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 2

Introduction

What I want to tell you about today:

How PostgreSQL handles concurrent operations

– Snapshots

– Conﬂict resolution rules

How to write application queries to get the right results without

sacriﬁcing performance

– Read-only transactions are pretty simple

– For read-write transactions, there are several approaches

depending on complexity of the transaction

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 3

What problem are we talking about?

We want to run transactions concurrently with:

correct behavior

good performance

“Correct behavior” basically means serializability. The transactions should

appear to execute one at a time, in isolation. When two transactions

physically overlap in time, we don’t care which one appears to go ﬁrst; but

we don’t want to see any behavior that reveals that they were concurrent.

Any such behavior would look like a bug to one or both users.

The easy way to do this would be to force transactions to actually go one

at a time . .. but for high-volume sites that kills performance. Ideally, no

transaction should block another from proceeding.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 4

Snapshots isolate transactions

Here’s the key idea in PostgreSQL’s implementation of concurrency:

Snapshots isolate transactions from the effects of concurrently

running transactions.

Each transaction runs against a notional “snapshot” of the committed state

of the database at a particular instant. It cannot see the effects of

uncommitted transactions (except itself), nor of transactions that commit

after the snapshot time.

Every update of a database row generates a new version of the row.

Snapshot information determines which version of a given row is visible to

a given transaction. Old versions of rows can be reclaimed (by

VACUUM

)

once they are no longer visible to any running transaction.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 5

PostgreSQL has two “isolation levels”

You can run PostgreSQL transactions in either of two modes:

SERIALIZABLE: a snapshot is taken at start of a transaction (actually, at

start of ﬁrst query within transaction). A reader’s view of the database is

thus ﬁxed throughout a transaction.

READ COMMITTED: a new snapshot is taken at start of each interactive

query. So, view of the database is stable within an interactive query, but

can change across queries within a transaction.

(The two modes also differ in update behavior, as we’ll discuss later.)

These modes are a subset of the four isolation levels deﬁned by SQL 92.

The other two SQL 92 modes correspond to behaviors that are useful in a

locking-based implementation, but are not interesting in a snapshot-based

implementation.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 6

Easy cases

We can cover these “easy” cases pretty quickly:

All read-only transactions

Many read-only transactions, only one writer (at a time)

The all-read-only case is obviously trivial. The one-writer case is nearly

trivial: snapshotting isolates the readers from the effects of the writer until

the writer commits.

“Interesting” cases have multiple writers to the same or related tables.

Then we have to worry about conﬂicting updates.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 7

But let’s look more closely at the one-writer case

The writer’s updates will all become visible when it commits, and will not

be visible before that.

Readers running in SERIALIZABLE mode will not see the changes from

writers that commit after they (the readers) start. So, they have a stable

view of the database throughout each transaction.

Readers running in READ COMMITTED mode will be able to see changes

beginning at ﬁrst SQL statement issued after writer commits. So, the view

is stable within a statement but not across statements. This is messier, but

necessary if (for example) you have procedures that want to observe

concurrent changes.

Either way, readers do not block the writer, and the writer does not block

readers, so concurrent performance is excellent.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 8

Reader correctness: a simple example

Suppose we want to cross check deposit totals against bank branch totals:

BEGIN;

SELECT SUM(balance) FROM accounts;

SELECT SUM(branch

balance) FROM branches;

-- check to see that we got the same result

COMMIT;

This is correct in serializable mode, but wrong in read committed mode.

To select serializable mode, either add

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

to each transaction block (just after

BEGIN

), or do

SET DEFAULT TRANSACTION ISOLATION TO SERIALIZABLE;

(this can be set in the

postgresql.conf

ﬁle, or per-connection).

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 9

An important coding rule

Be sure that reader activity is broken into transactions of appropriate

length.

Pure reader transactions should typically be run in SERIALIZABLE mode,

so that they see a consistent database view throughout the transaction;

then you set the transaction boundaries to deﬁne the times when you want

to recognize updates committed by other clients.

If you start one serializable transaction and hold it for the entire run of an

application, you’ll never observe any changes in database state, other

than those you make yourself. This is what you want in a few cases (for

instance, the backup utility

pg dump

does it to make a self-consistent

dump) but usually it’s not what you want.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 10

Beware of really long transactions

Holding a transaction open means that rows potentially visible to that

transaction can’t be reclaimed during

VACUUM

, even if they’re long dead to

everyone else.

Unlike Oracle, we won’t bomb out when a limited “rollback” area is ﬁlled;

but once your whole disk ﬁlls up, you’ve got a problem anyway.

So, avoid coding an application in a way that allows it to issue

BEGIN

and

then go to sleep for hours or days. Even though it’s not doing anything, it

may be blocking

VACUUM

from recovering space.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 11

The rules for concurrent writing

Two concurrent transactions cannot write (

UPDATE

DELETE

, or

SELECT

FOR UPDATE

) the same row. They can proceed as long as they write

nonoverlapping sets of rows.

If a transaction tries to write a row already written by a concurrent

transaction:

1. If other transaction is still in progress, wait for it to commit or abort.

2. If it aborted, proceed (using the non-updated version of the row).

3. If it committed:

(a) In SERIALIZABLE mode: abort with “can’t serialize” error.

(b) In READ COMMITTED mode: proceed, using the newly-committed

(latest) version of the row as the starting point for my operation.

(But ﬁrst, recheck the new row to see if it still satisﬁes the

WHERE

clause of my query; if not, ignore it.)

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 12

Our ﬁrst concurrent-writers example

We want to keep count of hits on different pages of a website. We have a

table with one row per webpage, and we are going to have a lot of clients

(webserver threads) concurrently executing something like

UPDATE webpages SET hits = hits + 1 WHERE url = ’...’;

Question: is this safe? In particular, can we ever “lose” a hit count

because two clients do this statement in parallel on the same row?

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 13

Concurrent writers can fail without some interlock

It’s easy to see that there could be a problem:

UPDATE webpages SET hits = hits + 1 WHERE url = ’...’;

CLIENT 1 CLIENT 2

reads row, sees hits = 531

computes hits+1 = 532

writes hits = 532

commit

Oops ... ﬁnal state of the row is 532, not 533 as we’d wish.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 14

READ COMMITTED works perfectly for this

But this bug will not occur in PostgreSQL. In READ COMMITTED mode,

the second client is forced to redo his computation:

CLIENT 1 CLIENT 2

reads row, sees hits = 531

computes hits+1 = 532

writes hits = 532

tries to write row, must wait

commit

re-reads row, sees hits = 532

re-computes hits+1 = 533

writes hits = 533

commit

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 15

READ COMMITTED vs. SERIALIZABLE mode

In SERIALIZABLE mode, the second client would instead get a “Can’t

serialize access due to concurrent update” error, and would have to retry

the transaction until he succeeded.

You always need to code a retry loop in the client when you are using

SERIALIZABLE mode for a writing transaction.

Why would you want to use SERIALIZABLE mode, given that it requires

extra client-side programming? Because READ COMMITTED doesn’t

scale very well to more complex situations.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 16

Example with separate read and write commands

Suppose we wanted to do our updates as a

SELECT

then

UPDATE

BEGIN;

SELECT hits FROM webpages WHERE url = ’...’;

-- client internally computes $newval = $hits + 1

UPDATE webpages SET hits = $newval WHERE url = ’...’;

COMMIT;

This might look silly, but it’s not so silly if the “internal computation” is

complex, or if you need data from multiple database rows to make the

computation, or if you’d like to know exactly what you just updated the hits

count to.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 17

READ COMMITTED case

In READ COMMITTED mode, this approach does not work:

CLIENT 1 CLIENT 2

reads row, sees hits = 531

computes $newval = 532

writes hits = 532

tries to write row, must wait

commit

re-reads row, sees hits = 532

re-computes $newval, still 532

writes hits = 532

commit

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 18

Solution #1: use SELECT FOR UPDATE, not just SELECT,

to read the input data

We can make it work by doing this:

BEGIN;

SELECT hits FROM webpages WHERE url = ’...’ FOR UPDATE;

-- client internally computes $newval = $hits + 1

UPDATE webpages SET hits = $newval WHERE url = ’...’;

COMMIT;

FOR UPDATE

causes the initial

SELECT

to acquire a row lock on the target

row, thus making it safe to do our internal computation and update the row.

Furthermore,

SELECT FOR UPDATE

returns the latest updated contents of

the row, so we aren’t working with stale data.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 19

How SELECT FOR UPDATE solution works

CLIENT 1 CLIENT 2

locks row, reads hits = 531

tries to lock row, must wait

computes $newval = 532

writes hits = 532

commit

locks row, reads hits = 532

computes $newval = 533

writes hits = 533

commit

We need both the delay till commit and the read of the updated value to

make this work. Notice

SELECT FOR UPDATE

may return data committed

after its start time, which is different from plain

SELECT

’s behavior in READ

COMMITTED mode.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 20

Solution #2: use SERIALIZABLE mode and retry on

serialization error

loop

BEGIN;

SELECT hits FROM webpages WHERE url = ’...’;

-- client internally computes $newval = $hits + 1

UPDATE webpages SET hits = $newval WHERE url = ’...’;

if (no error)

break out of loop;

else

ROLLBACK;

end loop

COMMIT;

This works because client will re-read the new hits value during retry.

The

UPDATE

will succeed only if the data read is still current.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 21

The client could get confused, too

Consider this small variant of the example, running in READ COMMITTED

mode:

BEGIN;

SELECT hits FROM webpages WHERE url = ’...’;

UPDATE webpages SET hits = hits + 1 WHERE url = ’...’;

COMMIT;

If someone else increments the hits count while the

SELECT

is running, the

UPDATE

will compute the correct updated value ... but it will be two more

than what we just read in the

SELECT

, not one more. (And that’s what we’d

see if we did another

SELECT

.) If your application logic could get confused

by this sort of thing, you need to use either

SELECT FOR UPDATE

SERIALIZABLE mode.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 22

Performance comparison

The READ COMMITTED SELECT FOR UPDATE approach is

essentially pessimistic locking: get the lock ﬁrst, then do your work.

The SERIALIZABLE

retry-loop approach is essentially optimistic locking

with retry. It avoids the overhead of getting the row lock beforehand, at the

cost of having to redo the whole transaction if there is a conﬂict.

SELECT FOR UPDATE wins if contention is heavy (since the serializable

approach will be wasting work pretty often). SERIALIZABLE wins if

contention for speciﬁc rows is light.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 23

What about updating multiple rows?

Example: transfer $100.00 from Alice’s account to Bob’s account.

Let’s try to do it in READ COMMITTED mode:

BEGIN;

UPDATE accounts SET balance = balance - 100.0

WHERE ownername = ’Alice’;

UPDATE accounts SET balance = balance + 100.0

WHERE ownername = ’Bob’;

COMMIT;

(Or we could do the arithmetic on the client side, in which case we’d need

SELECT FOR UPDATE

then

UPDATE

This is correct . . . but ...

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 24

We have trouble if the same rows can be updated in

different orders

Problem: suppose another transaction is concurrently transferring from

Bob’s account to Alice’s.

CLIENT 1 CLIENT 2

locks and updates Alice’s row

locks and updates Bob’s row

tries to lock Bob’s row, must wait

tries to lock Alice’s row, must wait

We have a classic deadlock situation. PostgreSQL will detect the deadlock

and get out of it by aborting one of the two transactions with a deadlock

error. (The other one will then be able to complete.)

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 25

So you end up needing a retry loop anyway

We can recover from such failures by placing a retry loop around the whole

transaction on the client side. The transaction that got killed to resolve the

deadlock will be retried, and eventually will complete successfully.

In such cases READ COMMITTED isn’t any simpler to program than

SERIALIZABLE mode: you need the same retry loop either way. (The

expected failures are slightly different, but the response to them is the

same.)

Unless you’re expecting lots of contention, you might as well use

SERIALIZABLE mode and avoid the row-locking overhead.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 26

Multi-row constraints, or why serializable mode isn’t

really serializable

Suppose we want to check that we always have at least $1000 total cash

in our checking and savings accounts. A typical transaction will look like:

BEGIN;

UPDATE my

accounts SET balance = balance - $withdrawal

WHERE accountid = ’checking’;

SELECT SUM(balance) FROM my

accounts;

if (sum

1000.00)

COMMIT;

else

ROLLBACK;

Is this safe? NO, not even in serializable mode.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 27

Multi-row constraints can fail

Suppose we have $600 in each account and we concurrently try to

withdraw $200 from each.

CLIENT 1 CLIENT 2

read checking balance, get 600

update checking balance to 400

read savings balance, get 600

update savings balance to 400

run

SUM

, get 400 600 1000

run

SUM

, get 600 400 1000

commit

Now the total is only $800; oops. Neither client saw the other’s

uncommitted change, so the constraint checks both succeeded.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 28

Some observations

This example proves that SERIALIZABLE mode isn’t really serializable,

because if we’d done the two transactions serially (in either order) the

second one would have seen the problem and aborted.

Technically, the difﬁculty here is that PostgreSQL doesn’t do predicate

locking, which is necessary for full serializability guarantees. (Predicate

locking means write-locking all rows that satisfy the

WHERE

condition of any

query executed by any open transaction. It’s horridly expensive. ..)

Note that it doesn’t matter whether the constraint check is done by a client

command or inside a trigger. The same visibility rules apply either way.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 29

Solution: use explicit locking

The only solution available in current PostgreSQL is to do explicit locking

at the table level:

BEGIN;

LOCK TABLE my

accounts IN SHARE ROW EXCLUSIVE MODE;

UPDATE my

accounts SET balance = balance - $withdrawal

WHERE accountid = ’checking’;

SELECT SUM(balance) FROM my

accounts;

-- commit if sum

1000.00, else abort

Since only one transaction can hold

SHARE ROW EXCLUSIVE

lock at a

time, we know that only our own transaction is writing the table, and so the

SUM

will not miss any uncommitted updates. Furthermore, any new writer

will have to wait at his

LOCK

command until we’ve committed our own

update, and then he’ll see it when he does his

SUM

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 30

Explicit locking and SERIALIZABLE mode

By the way, this solution works in either READ COMMITTED or

SERIALIZABLE mode:

BEGIN;

LOCK TABLE my

accounts IN SHARE ROW EXCLUSIVE MODE;

UPDATE my

accounts SET balance = balance - $withdrawal

WHERE accountid = ’checking’;

SELECT SUM(balance) FROM my

accounts;

-- commit if sum

1000.00, else abort

The reason it works in SERIALIZABLE mode is that the transaction

snapshot is not taken until the ﬁrst DML statement (the

UPDATE

). If we

have to wait at the

LOCK

for other writers, their commits will be included in

the snapshot. Note this means that any explicit locks taken in a

SERIALIZABLE transaction had better be taken at the top, or they may not

do what you want.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 31

What about concurrent inserts?

You might have noticed that I deﬁned concurrent writes as

UPDATE

DELETE

, or

SELECT FOR UPDATE

of the same existing row. What about

concurrent insertion cases?

Actually, it’s not possible for two transactions to try to insert “the same row”

– any inserted row is a unique object by deﬁnition. So multiple insertions

can happen in parallel as far as PostgreSQL is concerned.

The only way to get a conﬂict during insert is if you have a uniqueness

constraint (a unique index) on a table. If two concurrent transactions try to

insert rows having the same key value, then the second one will block until

the ﬁrst one ﬁnishes. If the ﬁrst transaction commits, the second one must

abort because of the uniqueness constraint; but if the ﬁrst one aborts the

second one can proceed.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 32

How do I manufacture unique row numbers?

If you want to assign a serial number to each row in a table, you might try

INSERT INTO mytable (id, ...)

VALUES( (SELECT MAX(id) + 1 FROM mytable), ...);

This will not work safely unless you take an explicit lock on the whole table,

which will prevent concurrent insertions. (It’ll also be quite slow, because

MAX

scans the whole table in PostgreSQL.) A variant is to use a single-row

table to hold the next ID number to assign:

SELECT next FROM mytable counter FOR UPDATE;

UPDATE mytable

counter SET next = $next + 1;

INSERT INTO mytable (id, ...) VALUES($next, ...);

This works (as long as you use FOR UPDATE), but you still have the

problem that only one insertion transaction can proceed at a time. The

implicit write lock on the counter row is the bottleneck.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 33

Solution: sequence objects

To get around this, PostgreSQL offers sequence objects, which are much

like the single-row counter table of the previous example:

CREATE SEQUENCE mytable counter;

...

INSERT INTO mytable (id, ...)

VALUES( nextval(’mytable

counter’), ...);

Sequences are special because

nextval

is a non-transactional operation:

it is never rolled back, and so there’s no need to hold a lock on the

sequence. When you do a

nextval

, you only gain exclusive access to the

sequence for long enough to compute the next value; then other people

can access the sequence while the rest of your transaction proceeds.

This allows multiple transactions to proceed with inserts concurrently.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 34

More about sequences

If you want to ﬁnd out what ID value you just inserted, you can do

INSERT INTO mytable (id, ...)

VALUES( nextval(’mytable

counter’), ...);

SELECT currval(’mytable

counter’);

Many people think this might be unsafe, but it is perfectly safe because

currval

is local to your session: it tells you the value that

nextval

last

returned for this sequence in your session, not the last value obtained by

anyone else. So concurrent transactions can’t affect the value you get.

A limitation when using sequences to assign serial numbers is that

aborted insertion transactions may leave “holes” in the set of used serial

numbers – when a transaction fails after having called

nextval

, it won’t

insert a row into the table, but the sequence doesn’t back up.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 35

Summary (the whole talk on one slide)

SERIALIZABLE mode:

snapshot isolation; no read locks

row locks on updated/deleted rows (block only writers, not readers)

can’t write row already written by concurrent transaction

no predicate locks (hence, not truly serializable)

simple to reason about, but you need a transaction retry loop

READ COMMITTED mode is similar except:

snapshot is updated at start of each new SQL command

can write row already written by concurrent transaction (update starts

from newest version)

ﬁne for single-row updates, doesn’t scale so well to complex cases

Use explicit locking to check multi-row consistency conditions.

Tom Lane O’Reilly Open Source Convention, July 2002

PostgreSQL Concurrency Issues 36