Exponential behaviour with UPDATE collisions?

[David F. Skoll]

Hi,

I've been running some tests, and it seems that PostgreSQL has very
bad behavior when multiple clients try to update the same row at the
same time. I realize of course that concurrent updates are not a Good
Thing, but PostgreSQL's reaction to it makes them very dangerous.

I would expect that if N clients are all trying to update the same row,
that the N updates would be serialized and run in O(N) time. In other
words, I'd expect them to run one after another, with the Nth update
finally finishing after all the other N-1 have run.

However, I'm observing what appears to be exponential time behavior.
Furthermore, it doesn't look like N-1 back-end processes are sleeping waiting
for the Nth to finish; instead, all N processes seem to be spinning madly
and doing lots of semop system calls.

Is this the expected behaviour? Is it considered a problem?

I've appended the Perl script I used for testing, as well as the timing
results. First column is number of concurrent updaters running in the
background; second is number of seconds to do 10 UPDATEs. These
data look very scary when plotted with gnuplot...

Regards,

David.

TEST RESULTS:

0 0.132829
1 0.11119
2 0.242621
3 0.539851
4 0.653608
5 0.949711
6 1.693731
7 2.314808
8 2.225513
9 3.62441
10 4.495103
11 6.882162
12 6.096985
13 8.998476
14 8.648887
15 8.909721
16 13.788871
17 15.295838
18 20.553915
19 19.460736
20 18.8845
21 23.188682
22 32.175639
23 30.781272
24 37.861856
25 46.980381
26 47.25473
27 54.772536
28 58.465823
29 61.34098

TEST SCRIPT:

#!/usr/bin/perl
use Pg;
use POSIX ":sys_wait_h";
use Time::HiRes qw( usleep ualarm gettimeofday tv_interval );

use vars @KidPids;

sub create_db {
system("dropdb -U postgres perftest");
system("createdb -U postgres perftest");
system("echo 'create table foo (key text primary key not null, value integer)' | psql -U postgres perftest");
system("echo \"insert into foo(key, value) values('bar', 0)\" | psql -U postgres perftest");
}

sub do_update($) {
my($conn) = @_;
$conn->exec("UPDATE foo SET value = value + 1 WHERE key = 'bar'");
}

sub do_update_in_loop($) {
my($conn) = @_;
while(1) {
do_update($conn);
}
}

sub run_update_child () {
my $conn;
$conn = Pg::connectdb("user=postgres dbname=perftest");
die("Failed to connect to DB") unless defined($conn);
die("Failed to connect to DB") if $conn->status == PGRES_CONNECTION_BAD;
do_update_in_loop($conn);
}

sub fork_kid () {
my $f = fork();
if ($f) {
print STDERR "Forked a child: PID = $f\n";
push @KidPids, $f;
} else {
run_update_child();
}
}

sub kill_kids () {
my $pid;
foreach $pid (@KidPids) {
kill 15, $pid;
}
}

sub reap_kids () {
my $kid;
do {
$kid = waitpid(-1, WNOHANG);
} until $kid <= 0;
}
sub run_tests () {
print STDERR "Initializing database\n";
create_db();

my $i, $j;

for ($i=0; $i<30; $i++) {
undef @KidPids;
# Generate the children
for ($j=0; $j<$i; $j++) {
fork_kid();
}
my $conn;
$conn = Pg::connectdb("user=postgres dbname=perftest");
die("Failed to connect to DB") unless defined($conn);
die("Failed to connect to DB") if $conn->status == PGRES_CONNECTION_BAD;
print STDERR "Running 10 updates with $i children...";
my $t0;
$t0 = [gettimeofday];

for ($j=0; $j<50; $j++) {
do_update($conn);
}

my $t1 = [gettimeofday];
my $elapsed = tv_interval($t0, $t1);
kill_kids();
undef $conn;
print STDERR "$elapsed\n";
print "$i $elapsed\n";
}
}

run_tests();


---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

[Tom Lane]

Post by David F. Skoll
I would expect that if N clients are all trying to update the same row,
that the N updates would be serialized and run in O(N) time.

Possibly so; but your test case isn't a pure illustration of an O(N)
situation. You are measuring the time for the mainline to run 50
updates of a row (as fast as it can) while N other processes are
updating the same row as fast as they can. The run will presumably
generate somewhere around N*50 dead rows with the same key. Since
you're not doing any vacuums meanwhile, later updates will have to scan
through lots of dead rows looking for the one live row. In other words,
there's an O(N^2) behavior here that would occur without any parallelism
at all, just from the number of dead rows you're leaving behind.

Post by David F. Skoll
Is this the expected behaviour? Is it considered a problem?

It's the price we pay for MVCC semantics. If you have an application in
which the bottleneck is the number of updates that can be done on a
single row, you might be better off with a non-MVCC database.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org