Re: Problems with on line & locks

I recently ran into a deadlock problem where no deadlock seemed possible. I now have a number of answers to why this might be. The majority of the answers are to do with basic deadlock theory, the twin-locking problem and adjacent key locking, but the one documented here is actually different from any of those, and could affect almost any application. It is a problem which can affect any version of OnLine, up to and including Version 5.0. It may be fixed in Version 6.0 (but no promises). This message contains a statement of the problem, an explanation of the problem, and some conclusions about the problem. If you want more info, contact me and I will send you tons of info about it, including the programs used to test the problem. I am very greatful to Don Top for his help in resolving this. Any errors in the diagnosis are mine, not his. Yours, Jonathan Leffler (johnl@obelix.informix.com) -------------------------------------------------------------------------- PROBLEM There are a number of concurrent copies of a program running which are inserting values into two tables called MDTHEAD and MDTITEM. The database has a transaction log, and there is a single transaction covering all the inserts into MDTITEM. It does not matter whether the insert into MDTHEAD is part of the same transaction or not. It is important to note that there are no deletes or updates happening at the same time, that the key values inserted into MDTITEM by any one instance of the program are in ascending sequence, and that the range of key values for any program is distinct from the range of values being inserted by any other program. The program works when run one at a time, and when small numbers are run concurrently, but fails with a deadlock error when a large number of copies are run simultaneously. The deadlock errors occur in table MDTITEM, not MDTHEAD. CREATE TABLE Mdthead ( Mdt_id SERIAL(1), valres_id INTEGER, dec_name CHAR(4) ) EXTENT SIZE 30 next SIZE 30 LOCK MODE ROW; CREATE TABLE Mdtitem ( Mdt_id INTEGER NOT NULL, Age SMALLINT NOT NULL, Value FLOAT ) EXTENT SIZE 1200 next SIZE 1200 LOCK MODE ROW; CREATE UNIQUE INDEX mdthead_1 ON Mdthead(Mdt_id); CREATE UNIQUE INDEX mdtitem_1 ON Mdtitem(Mdt_id, Age); Each process inserts a row into MDTHEAD, and then inserts a number of rows into MDTITEM; in the code used to establish what was causing the problem, there were 150 inserts into MDTITEM for each row in MDTHEAD, with Age values 1..150. Various explanations of the problem have been hypothesised previously. Most of these referred to a property called "adjacent key locking", which sometimes manifests itself in what is called the "twin locking problem". Although these explanations are correct in general, they do not apply to the specific problem encountered because only insert operations are happening, and the previous explanations need a mixture of insert operations and either update or delete operations (or both). The problem can be stated as: how do insert statements which insert distinct values into a table with a single index become deadlocked? ---------------------------------------------------------------------------- EXPLANATION When a table has page level locking, both the data pages and the index leaf nodes are locked at page level. When a table has row level locking, the data pages are locked at the row level, and the index leaf nodes are locked at the key level. Key locks only apply to leaf nodes, never to branch nodes. The root node is only key locked when it is also the only node in the index. When a B-tree branch node needs to be split or merged or shuffled, the locking that occurs does not use the main lock table but uses buffer pool access control latches to ensure exclusive access for the duration of the operation, not for the duration of the transaction. (By extension, if a change needs to be rolled back, the relevant B-tree pages will be revised again, using the buffer pool access control latches.) Thus, the deadlock is not caused by locking above the leaf nodes of the index. When OnLine locks key values (items), the key value must be represented in 4 bytes. Obviously, keys can be longer than 4 bytes (the maximum size is 255 bytes), so OnLine uses a hashing algorithm which uses selected bits from the key value, the rowid and the key number (each index created on a table is numbered internally from 1 to n) to generate a 4-byte key value. The problem which occurring was that two different rowids and key values are being resolved into the exact same 4-byte "key value representation". Extensive testing has shown the following: Process A inserted (Mdt_id = 57, Age = 6) and got rowid 36695 for it. This turned into a lock on "key value" 0xC0F0C11F. Subsequently, in the same transaction, Process A had to wait for some other lock, so it is asleep waiting for this lock. Soon thereafter, Process B (which currently holds the most current Mdt_id value and therefore is the only process *not* waiting for the others -- since it has the "right-most" key value in the MDTITEM table's index) tries to insert (Mdt_id = 60, Age = 5) and gets rowid 38719 for it. Unfortunately, the "key value" for this is *also* 0xC0F0C11F and it runs into the lock held by Process A. Now Process A is sleeping, waiting for Process X which is waiting for Process Y which is waiting for Process Z which is ultimately waiting for Process B -- the process which wants to wait for the new lock. Of course, this represents a deadlock situation, so Process B must return the error. Part of the problem may stem from the fact that with 10 processes holding onto a contiguous range of 10 Mdt_id values and 1 to 150 contiguous Age values, the chances of "key value" duplication for the process which is actually doing some work increases rapidly, primarily because there can be from 10 to ~1500 "unique" values already held by the other processes which are all ultimately waiting for it to commit. For example, assume processes insert (x,y) x=constant, y runs from 1 to 150. A holds 1,1 1,2 1,3 ... 1,131 and waits for B due to lock on 2,1 B holds 2,1 2,2 2,3 ... 2,90 and waits for C due to lock on 3,1 C holds 3,1 3,2 3,3 ... 3,47 and waits for D due to lock on 4,1 D holds ... : I holds 9,1 9,2 9,3 ... 9,126 and waits for J due to lock on 10,1 J holds 10,1 10,2 10,3 ... and wants to insert 10,77. Unfortunately, the combination of the rowid and the key values (10,77) happen to have the same "key value representation" as 3,39, which is held by C (which waits for D, which waits for E, ... which waits for I, which is waiting for J -- BINGO! deadlock!). ---------------------------------------------------------------------------- CONCLUSION When a key is longer than 4 bytes, a hashing algorithm is used to represent the key value as a 4-byte hashed key value. There will always be a possibility that two distinct key values will be converted to the same hashed key value, and that a locking conflict will be detected when there would otherwi