deadlocks

[Marcus]

Hello all,

I am trying to figure out when it is appropriate to use shared and
exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits.

Using exclusive locks (for update) I cannot come up with a scenario that
results in a deadlock, since the very nature of the exclusive lock means
no other queries should be able to access the row(s) in question until I
commit.

If this is the case, my question then is this: why would I ever use a
shared lock if doing so can result in deadlocks? There must be a reason
because we have them, and going through tutorials I can see HOW they are
used, but I am not sure what advantage they would have over exclusive
locks. It seems to me that exclusive locks are "safer", but I know I
must be overlooking something.

Thank you all in advance for your help.

Marcus

[Mladen Gogala]

On Thu, 08 Sep 2005 23:20:44 +0000, Marcus wrote:

I am trying to figure out when it is appropriate to use shared and
exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits.

Deadlock is a circular wait: session 1 holds a lock on table A and wants
to lock table B, while the session 2 holds the lock on table B and wants
to lock table A. That will produce circular wait situation, otherwise
known as deadlock.
The solution for the deadlock problem is simple: always lock resources in
the same order. If one application locks table A and then locks table B,
don't allow any other application to lock table B first. That is how
deadlocks come into this world.
The problem is that many deadlocks are not actual deadlocks, there are
also hangs and infinite waits, with the same unpleasant effect for the
end-user. End users are rarely happier if you explain them the true
nature of their plight, they will usually come up with an unreasonable
request to get the [EXPLETIVE DELETED] thing done. Infinite waits happen
when user inserts a record into our lucky database, then receives a phone
call from a friend and goes to lunch. Application, on the other hand,
doesn't commit until the user answers the necessary question "Are you sure
[Y/N]:". Anybody else who wants to lock the same resource can only hope
that their colleague had opted for the fast food joint. Usually, fast food
is not fast enough to prevent the others from becoming somewhat unhappy.
The solution: don't create applications which do that. No locks of any
kind should be imposed on the system until the user decides to perform the
actual commit. Technically, that's not a deadlock, it's an infinite wait.
Make sure that your users are aware of that fine distinction.
The next type of lovely condition that resembles deadlocks are hangs.
Hangs are, essentially, infinite waits for the system resources or
deadlocks on them. Lock manager itself is usually implemented as a queue
manager, with locked resources as queueing points and locks as waiters in
those queues. Each lock needs a "lock block" or "enqueue resource". If you
don't have enough of those on the system then you cannot lock the resource
you need until some lock blocks are freed, usually by ending another
transaction. That can manifest itself both as a very long wait or a
condition that the end users call "slow f***ing database" with their
voices pitched to the high decibel levels, rivaling the local airport. The
solution for that is to create enough lock blocks. Those blocks are
typically something like 8 bytes in length, so if you put in 16384 more of
them, you'll end up using 256k more RAM, which really serious today when
desktop PC regularly has 512MB and server machines normally have
multi-gigabyte memories. Of course, it would help a lot if you could tell
us what garden variety of the database software you are using. In some
databases, readers block writers, some have lovely surprises like lock
escalation for the unwary users or come extremely under-configured, so
that you run out of lock resources when you look inquisitively at the
machine. Not all databases are created equal. Lock escalation is the event
of replacing bunch of row locks with a table lock, to prevent high
consumption of lock blocks. Unfortunately, that has unpleasant
consequences for anybody else who may wish to update that table and
effectively turns it into a single-user table.
Did I mention that some databases do not have row locks at all, but are
locking things on block or page level? Welcome to the lovely world of
an Oracle DBA. Do androids dream of electric sheep?

--
http://www.mgogala.com

[Gordon Burditt]

>I am trying to figure out when it is appropriate to use shared and

exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits.

Using exclusive locks (for update) I cannot come up with a scenario that
results in a deadlock, since the very nature of the exclusive lock means
no other queries should be able to access the row(s) in question until I
commit.

If this is the case, my question then is this: why would I ever use a
shared lock if doing so can result in deadlocks?
Because no other queries should be able to access the row(s) in
question until you commit. That means that if you go to lunch with
an uncommitted transaction, the CEO's hourly sales report won't be
ready on time, and you may come back to a pink slip. Worse, you'll
block the credit card billing process. It also may hang your web
server waiting on locks for just about every page containing info
from the database, depending on what you locked.

There must be a reason
because we have them, and going through tutorials I can see HOW they are
used, but I am not sure what advantage they would have over exclusive
locks. It seems to me that exclusive locks are "safer", but I know I
must be overlooking something.

Exclusive locks are in some ways like everyone in the world waiting
in line for ONE restroom. They may limit the number of users your
webserver(s) can handle regardless of how many parallel web servers
you add, or how much you spend on more RAM and fast CPUs.

Gordon L. Burditt

[Marcus]

Mladen Gogala wrote:

On Thu, 08 Sep 2005 23:20:44 +0000, Marcus wrote:

I am trying to figure out when it is appropriate to use shared and
exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits.

Deadlock is a circular wait: session 1 holds a lock on table A and wants
to lock table B, while the session 2 holds the lock on table B and wants
to lock table A. That will produce circular wait situation, otherwise
known as deadlock.
The solution for the deadlock problem is simple: always lock resources in
the same order. If one application locks table A and then locks table B,
don't allow any other application to lock table B first. That is how
deadlocks come into this world.
The problem is that many deadlocks are not actual deadlocks, there are
also hangs and infinite waits, with the same unpleasant effect for the
end-user. End users are rarely happier if you explain them the true
nature of their plight, they will usually come up with an unreasonable
request to get the [EXPLETIVE DELETED] thing done. Infinite waits happen
when user inserts a record into our lucky database, then receives a phone
call from a friend and goes to lunch. Application, on the other hand,
doesn't commit until the user answers the necessary question "Are you sure
[Y/N]:". Anybody else who wants to lock the same resource can only hope
that their colleague had opted for the fast food joint. Usually, fast food
is not fast enough to prevent the others from becoming somewhat unhappy.
The solution: don't create applications which do that. No locks of any
kind should be imposed on the system until the user decides to perform the
actual commit. Technically, that's not a deadlock, it's an infinite wait.
Make sure that your users are aware of that fine distinction.
The next type of lovely condition that resembles deadlocks are hangs.
Hangs are, essentially, infinite waits for the system resources or
deadlocks on them. Lock manager itself is usually implemented as a queue
manager, with locked resources as queueing points and locks as waiters in
those queues. Each lock needs a "lock block" or "enqueue resource". If you
don't have enough of those on the system then you cannot lock the resource
you need until some lock blocks are freed, usually by ending another
transaction. That can manifest itself both as a very long wait or a
condition that the end users call "slow f***ing database" with their
voices pitched to the high decibel levels, rivaling the local airport. The
solution for that is to create enough lock blocks. Those blocks are
typically something like 8 bytes in length, so if you put in 16384 more of
them, you'll end up using 256k more RAM, which really serious today when
desktop PC regularly has 512MB and server machines normally have
multi-gigabyte memories. Of course, it would help a lot if you could tell
us what garden variety of the database software you are using. In some
databases, readers block writers, some have lovely surprises like lock
escalation for the unwary users or come extremely under-configured, so
that you run out of lock resources when you look inquisitively at the
machine. Not all databases are created equal. Lock escalation is the event
of replacing bunch of row locks with a table lock, to prevent high
consumption of lock blocks. Unfortunately, that has unpleasant
consequences for anybody else who may wish to update that table and
effectively turns it into a single-user table.
Did I mention that some databases do not have row locks at all, but are
locking things on block or page level? Welcome to the lovely world of
an Oracle DBA. Do androids dream of electric sheep?

Thank you very much for the detailed reply, Mladen. In response to your
question, I am running MySQL 4.0.22 using InnoDB table types.

With regards to your explanation, the original scenario I explained:

"I am trying to figure out when it is appropriate to use shared and
exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits."

this may not be a deadlock in the sense that you explained, but MySQL
still reports it as a deadlock:

ERROR 1213: Deadlock found when trying to get lock; Try restarting
transaction

I don't think I can avoid this situation above solely by ordering my
queries in a certain order. I have various scripts that access the same
table and do different updates of it, so it is more than just making
sure my queries all execute in a predetermined order.

This is why I am confused as to why I would use a shared lock, since
using an exclusive lock seems to avoid these issues. I should also note
that all my locks are executed in transactions, so there is never a
situation where the database hangs and waits for the user to commit a
transaction. Thanks again in advance.

[Marcus]

Gordon Burditt wrote:

I am trying to figure out when it is appropriate to use shared and
exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits.

Using exclusive locks (for update) I cannot come up with a scenario that
results in a deadlock, since the very nature of the exclusive lock means
no other queries should be able to access the row(s) in question until I
commit.

If this is the case, my question then is this: why would I ever use a
shared lock if doing so can result in deadlocks?

Because no other queries should be able to access the row(s) in
question until you commit. That means that if you go to lunch with
an uncommitted transaction, the CEO's hourly sales report won't be
ready on time, and you may come back to a pink slip. Worse, you'll
block the credit card billing process. It also may hang your web
server waiting on locks for just about every page containing info
from the database, depending on what you locked.

There must be a reason
because we have them, and going through tutorials I can see HOW they are
used, but I am not sure what advantage they would have over exclusive
locks. It seems to me that exclusive locks are "safer", but I know I
must be overlooking something.

Exclusive locks are in some ways like everyone in the world waiting
in line for ONE restroom. They may limit the number of users your
webserver(s) can handle regardless of how many parallel web servers
you add, or how much you spend on more RAM and fast CPUs.

Gordon L. Burditt

Thanks for the answer, Gordon. I was just wondering, if all my
transactions either commit or rollback immediately, i.e. are not
dependent on any user input once the transaction is started, is this
still an issue?

Let me give a real world example, it would help to clarify things a lot
for me. Say I am booking a hotel online. For the transaction where I
am actually updating the database with my reservation, should I use a
shared or exclusive lock? It seems to me that with a shared lock,
"potentially" someone could see that same room as being available even
though once my transaction finishes, it will be gone. With an exclusive
lock, no one could search room availability until I am done making my
reservation (I am only talking about locking the rows once the user has
actually confirmed everything, i.e. no more user input is involved).

Thanks again!

[Gordon Burditt]

>The problem is that many deadlocks are not actual deadlocks, there are

also hangs and infinite waits, with the same unpleasant effect for the
end-user. End users are rarely happier if you explain them the true
nature of their plight, they will usually come up with an unreasonable
request to get the [EXPLETIVE DELETED] thing done. Infinite waits happen
when user inserts a record into our lucky database, then receives a phone
call from a friend and goes to lunch. Application, on the other hand,
doesn't commit until the user answers the necessary question "Are you sure
[Y/N]:". Anybody else who wants to lock the same resource can only hope
that their colleague had opted for the fast food joint. Usually, fast food
is not fast enough to prevent the others from becoming somewhat unhappy.
.... and in Texas, getting out The Rope.
The solution: don't create applications which do that. No locks of any
kind should be imposed on the system until the user decides to perform the
actual commit. Technically, that's not a deadlock, it's an infinite wait.
It's not really an *infinite* wait until the guy goes to lunch,
then gets hit by a bus or is fired before he gets back. It may
seem like it to everyone else in the office, and they may start
chartering busses.
Make sure that your users are aware of that fine distinction.

That's important, because the users may need to make you aware of
the fine distinction between a hanging and a lynching, by demonstrating
on you.

However, the application may NEED locks or the equivalent in this
situation in order to preserve data integrity, or some way to
indicate a "virtual deadlock", otherwise known as "somebody edited
the record out from under you". Assuming that the process is that
the customer service rep brings up the user's account, then uses
that information plus the customer request to make changes, with
possibly a long time in between, bad things can happen to the
customer info when two reps edit the same record at the same time.
A lot of this may be computed in the rep's or the customer's brain.

Customer to Rep A: How many mailboxes do I have?
Customer's wife to Rep B: How many mailboxes do I have?
Rep A to Customer: (brings up account screen) 8
Rep B to Customer's wife: (brings up account screen) 8
Customer to Rep A: I need 9 total. Add another one.
Customer's wife to Rep B: I need 9 total. Add another one.
Rep A to Customer: (Clicks SUBMIT on update, gets result)
Ok, we've added another one.
Rep B to Customer's wife: (Clicks SUBMIT on update, gets result)
Ok, we've added another one.
.... Later ...
Customer to Rep C: How the #*&(*^#@ did I end up with 10 mailboxes?
I didn't ask for that!
One way around this (in the web environment, especially) is to hide
the old record contents in the form. After the rep hits the SUBMIT
button, the code compares the old record contents in the form with
those in the record. If they changed in a significant way (figuring
out what is significant and what isn't may be subject to debate),
reject the update, indicating that the record has been changed.
This does have a disadvantage that it's likely to reject completely
independent changes that aren't really conflicting.

Gordon L. Burditt

[Gordon Burditt]

>>>I am trying to figure out when it is appropriate to use shared and

exclusive locks with InnoDB. Using shared locks (lock in share mode), I
can easily create a scenario with 2 clients that deadlocks - start 2
transactions, open 2 shared locks, and both try to insert a new row
before either commits.

Using exclusive locks (for update) I cannot come up with a scenario that
results in a deadlock, since the very nature of the exclusive lock means
no other queries should be able to access the row(s) in question until I
commit.

If this is the case, my question then is this: why would I ever use a
shared lock if doing so can result in deadlocks?

Because no other queries should be able to access the row(s) in
question until you commit. That means that if you go to lunch with
an uncommitted transaction, the CEO's hourly sales report won't be
ready on time, and you may come back to a pink slip. Worse, you'll
block the credit card billing process. It also may hang your web
server waiting on locks for just about every page containing info
from the database, depending on what you locked.

There must be a reason
because we have them, and going through tutorials I can see HOW they are
used, but I am not sure what advantage they would have over exclusive
locks. It seems to me that exclusive locks are "safer", but I know I
must be overlooking something.

Exclusive locks are in some ways like everyone in the world waiting
in line for ONE restroom. They may limit the number of users your
webserver(s) can handle regardless of how many parallel web servers
you add, or how much you spend on more RAM and fast CPUs.

Gordon L. Burditt

Thanks for the answer, Gordon. I was just wondering, if all my
transactions either commit or rollback immediately, i.e. are not
dependent on any user input once the transaction is started, is this
still an issue?

The "gone to lunch" isn't an issue. The bottleneck may still remain,
as the database does not execute transactions "immediately", and
if most transactions need to hold locks, you can't speed up the
database server by adding more CPUs as only one thread can run.
This does depend on how granular your locks are and how much updates
tend to update the same records, but you can still have the "world
waiting to use one restroom" problem.

Note that for data integrity, you may *NEED* at least a "virtual" lock
on the data before you bring up the data screen to after you commit
the transaction, and this problem won't go away. You (and perhaps the
customer on the phone) look at the data and together compute a set of
changes, which may not be valid if the original data changes out from
under you. In the web environment, a "virtual" lock is sometimes
implemented by putting the original record data in hidden fields on
a web page. When you submit, if the record in the database doesn't
match the record data in the hidden fields, reject the update. (This
can also avoid the user using the BACK button and submitting the
same update twice.)
Let me give a real world example, it would help to clarify things a lot
for me. Say I am booking a hotel online. For the transaction where I
am actually updating the database with my reservation, should I use a
shared or exclusive lock? It seems to me that with a shared lock,
"potentially" someone could see that same room as being available even
though once my transaction finishes, it will be gone. With an exclusive
lock, no one could search room availability until I am done making my
reservation (I am only talking about locking the rows once the user has
actually confirmed everything, i.e. no more user input is involved).

And with heavy reservation traffic, the wait time to get a reservation,
or even search for possibilities, may become unacceptable, and the
800 reservation line phone bill may skyrocket.

You *CANNOT* always eliminate the user interaction. For example,
after the reservation is confirmed, you discover the price on the
room has changed, and the customer cancels the reservation or asks
to try for a cheaper room. Or the customer asks for a particular
room. Or five adjacent rooms. It may also depend on what you can
do in one transaction. For example, how do you deal with the guy
who wants 120 rooms, or forget the whole thing, when you are limited
to reserving 3 rooms at a time, or he refuses to give you 120 names,
addresses, and credit card numbers until you GUARANTEE him reservations
for all 120? Oh, yes, there's a another guy with another convention
asking for a lot of rooms on another line for the same weekend, and
you don't have enough rooms for both.

Gordon L. Burditt

[Mladen Gogala]

On Fri, 09 Sep 2005 02:39:52 +0000, Marcus wrote:

This is why I am confused as to why I would use a shared lock, since
using an exclusive lock seems to avoid these issues. I should also note
that all my locks are executed in transactions, so there is never a
situation where the database hangs and waits for the user to commit a
transaction. Thanks again in advance.

Now, that's simple: only one person at the time can hold an exclusive lock,
while more people can hold shared locks. MySQL has several unpleasant
characteristics:
1) MySQL allows other users to see uncommitted data in the other
transactions, unless every select is protected by a shared lock.
That is so called "dirty read". The problem is this: I want to
pay my phone bill on-line. I go to my bank account, invoke the
appropriate form and enter the amount. The officer of the phone
company, having the bank account at the same bank is running
financial report at the same time. His report sees my payment
and puts it on the report, before I actually committed the transaction.
In the mean time, I decide to pay my cable bill instead, and roll the
transaction back. Result: the officer of the phone company has just
produced a false financial statement. Dirty reads are bad and,
unfortunately, are the basis for the blinding speed of MySQL.
2) You can guard against that by requiring that each query is protected
by the shared lock on the underlying tables. Unfortunately, shared lock
is incompatible with an exclusive one, they cannot coexist on the same
table at the same time. To do updates, inserts or deletes, also known
as DML (Data Modification Language) you need an exclusive lock, which
will prevent anybody to see the data while you're updating the table,
therefore also preventing dirty reads.
Using exclusive locks extensively will, effectively, turn your database
into a single user database. That might be what you want, but I don't
see many of those.

Have you ever considered PostgresSQL? It is by far superior to MySQL with
respect to the transaction mechanism.

--
http://www.mgogala.com