Lost update
Lost update (including English lost update ) referred to in the computer science an error which may occur in a plurality of parallel write accesses to a shared information. If two transactions change the same information, the changes in the first can be immediately overwritten by the changes in the second.
It does not matter whether the "shared information" is in a file , in a database table or in the main memory .
Read and write without interaction with a user
example
A chain of advance booking offices stores the number of tickets sold for each event. 100 cards had already been sold when five cards were returned at a cash register. At the same time, three tickets are bought at a second cash register. The system of the first cash register subtracts the 5 returned cards from the 100 and writes the new value (95) back into the database. The second cash register system adds the three cards that have just been sold to 100 and also writes this value (103) into the database. The value written first is lost and the end result is incorrect (103 tickets sold, although there are actually only 98).
| time | Program 1
Take back 5 cards |
Stored number
tickets sold |
Program 2
Sell 3 cards |
|---|---|---|---|
| 0 | 100 | ||
| 1 |
Read the number of tickets sold
Result: 100 |
100 | |
| 2 | 100 |
Read the number of tickets sold
Result: 100 |
|
| 3 | 5 cards are withdrawn
Calculate new value: 100-5 = 95 Write a new value (95) |
95 | |
| 4th | 103 | 3 cards are sold
Calculate new value: 100 + 3 = 103 Write a new value (103) |
Methods to work around the problem
When the read access is carried out, the shared information is blocked so that it cannot be changed by another program in the meantime.
The locking mechanisms required for this are provided by the various data management systems:
- the share lock enables read access to any number of transactions.
- the exclusive lock only allows a single transaction write access. During this time, no other transaction may read the locked data.
These locking mechanisms are used by most operating systems and databases as well as by buffer managers in order to handle concurrent access.
The isolation level RR
The isolation level RR (Repeatable Read) is often mentioned as a solution to the lost update problem.
Most RDBMS offer different levels of isolation. Repeatable read means that a share lock remains in place until the end of a transaction and does not disappear again immediately after the read access.
If you use the isolation level RR, you have to make sure that no deadlocks occur.
The first program writes a share lock that is not removed again. The second program also writes a share lock. Now the first program wants to convert the share lock into an exclusive lock, but that is not possible as long as the second program still maintains its share lock. A little later, the second program also wants to convert its share lock into an exclusive lock. Now everyone is waiting for the other. This is the classic deadlock situation.
| time | Program 1
Take back 5 cards |
Locks from
Prog. 1 |
Stored number
tickets sold |
Locks from
Prog. 2 |
Program 2
Sell 3 new cards |
|---|---|---|---|---|---|
| 0 | 100 | ||||
| 1 |
Read the number of tickets sold
Result: 100 |
S-lock
from P1 |
100 | ||
| 2 | S-lock
from P1 |
100 | S-lock
from P2 |
Read the number of tickets sold
Result: 100 |
|
| 3 | 5 cards are withdrawn
Calculate new value: 100−5 = 95 Request exclusive lock waiting for P2 |
S-lock
from P1 |
100 | S-lock
from P2 |
|
| 4th | waiting for P2 | S-lock
from P1 |
100 | S-lock
from P2 |
3 cards are sold
Calculate new value: 100 + 3 = 103 Request exclusive lock waiting for P1 |
| 5 | waiting for P2 | S-lock
from P1 |
100 | S-lock
from P2 |
waiting for P1 |
Now it depends on how the RDBMS reacts in such a case. Some RDBMS - e.g. B. DB2 - you can parameterize so that a transaction only waits for a certain time for locked resources. As soon as this time has passed and the resource is still locked, the transaction is rolled back and the program receives an error message (SQLCODE −911). That would be a solution to the problem, because the rollback of the first transaction also removed the share lock and the second transaction now gets the exclusive lock that it was waiting for. If the SQLCODE −911 is specifically queried in the program, then the program can read the record again in such a case and now receives the value that the other program has just written. So no update is lost.
| time | Program 1
Take back 5 cards |
Locks from
Prog. 1 |
Stored number
tickets sold |
Locks from
Prog. 2 |
Program 2
Sell 3 new cards |
|---|---|---|---|---|---|
| 6th | SQLCODE −911
Rollback |
100 | S-lock
from P2 |
waiting for P1 | |
| 7th | 103 | X-Lock
from P2 |
Write a new value (103) | ||
| 8th | Read the number of tickets sold
Request share lock waiting for P2 |
103 | X-Lock
from P2 |
||
| 9 | Request share lock
waiting for P2 |
103 | commit | ||
| 10 |
Share lock received
Read the number of tickets sold Result: 103 |
S-lock
from P1 |
103 | ||
| 11 | 5 cards are withdrawn
Calculate new value: 103-5 = 98 Request X-Lock Write a new value (98) |
X-Lock
from P1 |
98 | ||
| 12 | Commit | 98 |
The second attempt, like the first attempt, can fail if a third program has set a share lock on the record in the meantime. Therefore, reading and writing in the program must be performed in a loop.
You can now consider whether the loop should be repeated as often as you like, or whether processing should be abandoned after n attempts and ended with an error message.
Schleife
Select ...
Neuen Wert berechnen
Update ...
if (sqlcode not in (0, −911)) return(FEHLER)
Until (sqlcode = 0 or Anz_Schleifen_Durchlaeufe > n)
if (sqlcode <> 0) return(FEHLER)
If the RDBMS waits until an administrator intervenes in the event of a deadlock, then this variant is not a good solution.
Serialize processing
If the first program blocks the information exclusively during read access, the second program has to wait with its read access. As soon as the first program has also carried out write access and releases the resource again, the second program can continue its processing. This variant is a forced serialization of the processing.
If the information is saved in a file , the program must open the file immediately for writing.
If the information is stored in a database table, then the sentence can e.g. B. can be read with a CURSOR FOR UPDATE, or the entire table can be locked with LOCK TABLE IN EXCLUSIVE MODE.
Atomize read and write access
If no further processing is required between read access and write access, these two accesses can also be combined (see Atomic Operation ).
For an RDBMS , the access for the example could be:
update Tab set Anzahl_verkaufte_Karten = Anzahl_verkaufte_Karten + :Aktueller_Verkauf
This eliminates the need for separate read access. A lost update can no longer occur.
Read and write with user interaction
In practice, the problem of the lost update also often occurs in connection with user interactions. This means that the information read is output to the user and can be changed by him. The changed information is then written back. If another user wants to change the same information, the changes made by the first user may be lost. The following is different with user interaction than without:
- Reading and writing cannot be merged.
- In most cases, reading and writing are carried out as two independent transactions.
- It must be taken into account that the user may take a long time typing (e.g. lunch break), which means that a lot of time can pass between reading and writing.
- The connection can break off during user interaction (network problem, the program is being terminated, ...).
This can be prevented by checking before writing whether the data has been changed in the meantime and by combining this read and write access into a single transaction. Not every single column value of the data record has to be checked. It is enough to know whether the record has been changed. This can be achieved by adding an additional column with an integer. This makes it possible to check whether the value of the read access is still before the data change during the write access. If so, the final read-write transaction must increase the value in this column by 1 accordingly. The other column values are also updated at the same time. So you only have to remember a single integer read_column-test- value. In SQL it looks something like this:
- The data record is read so that it can then be edited. ( read_column test value must be saved in a variable):
SELECT tabelle spalte_1, ..., gelesener_spaltentestwert WHERE id_tabelle;
- The data record is changed and then written back. (The check for changes by competing accesses and the write process are combined):
UPDATE tabelle SET spalte_1=spaltenwert_1, ..., gelesener_spaltentestwert=gelesener_spaltentestwert+1 WHERE spaltentestwert=gelesener_spaltentestwert AND id_tabelle;
- If no data record is found here, the read_column test value is no longer correct and an update has taken place through another access in the meantime. An error evaluation must now be carried out and an appropriate response must be made.
- If successful, the processing of the data record is now finished.
The column values are then of course to be specified as variables according to the programming language used.