preface
Kids make choices. I want all of them. Today, I want to write the interview questions: optimistic locks and pessimistic locks. Mainly from the following aspects:
- What is optimism lock
- What is pessimism lock
- Optimistic locks are commonly implemented
- Pessimistic locks are commonly implemented
- Disadvantages of optimistic locking
- Disadvantages of pessimistic locks
I was writing an article when I received a message from my friend that Uzi had retired and player LPL0006 was disconnected. Wish you fresh clothes angry horse, a day to see all the changan flowers, through the mountains and rivers, return is still that boy. Come on, shout with me: the road is simple – only I am proud
1. What is optimistic lock
Optimism locks always assume that things will go well, as some people are born to be optimistic and sunny!
Optimistic locking always assumes a best-case scenario. Every time you pick up data, you assume that no one else will change it, so you don’t lock it, but when you update it, you decide whether someone else has updated it in the meantime. Optimistic locking is suitable for multi-read applications, because optimistic locking does not lock data when reading data, which saves the overhead of locking and increases the overall throughput of the system. Even if there is an occasional conflict, it doesn’t hurt to either try again or report back to the user with a new failure, of course, if there is an occasional conflict, but if there is a frequent conflict, the upper application will continue to spin retry, which degrades performance more than it costs.
What is the pessimistic lock
Pessimistic lock always assumes that things will develop in a bad direction, such as some people experienced something, may not trust others, only trust themselves, in the dark, step on the light!
Pessimistic lock every time when I go to get data, I think others will modify it, so every time WHEN I get data, I will lock it, so that others want to take the data will be blocked, until I release the lock, others can get the lock, so that only one thread of data itself is modifying, to ensure the accuracy of data. Therefore, pessimistic locking is suitable for the type of application that has a lot of write.
3. Optimistic lock is commonly implemented
3.1 Version Number mechanism
The version number mechanism is to add a new field, version, in the table, when changing the record, first query the record, and then change the value of this field by 1, the judgment condition is you just query the value. Take a look at the following process:
- 3.1.1 Adding a User information table
CREATE TABLE `user_info` (
`id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT 'primary key ID'. `user_name` varchar(64) DEFAULT NULL COMMENT 'User name'. `money` decimal(15.0) DEFAULT '0' COMMENT 'Remaining Amount (cent)'. `version` bigint(20) DEFAULT '1' COMMENT 'Version number'. PRIMARY KEY (`id`) USING BTREE ) ENGINE=InnoDB COMMENT='User Information Table'; Copy the code- 3.1.2 Adding a Data item
INSERT INTO `user_info` (`user_name`.`money`.`version`) VALUES ('Joe'.1000.1);
Copy the code- 3.1.3 Procedure
| steps | Thread A | Thread B |
|---|---|---|
| 1 | SELECT * FROM user_info WHERE user_name = ‘user_info ‘; | |
| 2 | SELECT * FROM user_info WHERE user_name = ‘user_info ‘; | |
| 3 | To modify the amount of bill 3, UPDATE user_info SET money = money + 100, version = version +1 WHERE user_name = ‘chang3’ AND version = 1; , returns the number of changes to 1 | |
| 4 | Modify the amount of Bill 3, add 200, UPDATE user_info SET money = money + 200, version = version +1 WHERE user_name = ‘chang3’ AND version = 1; , returns the number of changes to 0 | |
| 5 | Check whether the number of modification items is 0. If yes, failure is displayed; otherwise, success is displayed | |
| 6 | Check whether the number of modification items is 0. If yes, failure is displayed; otherwise, success is displayed | |
| 7 | Return to success | |
| 8 | Returns the failure |
3.2 the CAS algorithm
CAS, which stands for Compare and swap, is a well-known lock-free algorithm. Lockless programming is the Synchronization of variables between multiple threads without locking (no threads are blocked), so it is also called non-blocking Synchronization. The CAS algorithm involves three operands:
- Memory value V(variable value in main memory)
- The comparison value A(the value of A variable cloned from thread local memory)
- New value B to write (new value to update)
CAS updates the value of V atomically with A new value B if and only if the value of V is equal to A, otherwise no operation is performed (compare and replace is A native atomic operation). In general, this is a spin operation, i.e. continuous retries, see the following flow:
- 3.2.1 CAS algorithm simulates database updating data (the table is the same as before, and the initial value of the amount of the user’s triple card is 1000), and increases the amount of the user’s triple card by 100:
private void updateMoney(String userName){
/ / death cycle
for(;;) { // Get the amount of Zhang SAN
BigDecimal money = this.userMapper.getMoneyByName(userName);
User user = new User(); user.setMoney(money); user.setUserName(userName); // Update by username and amount (amount +100) Integer updateCount = this.userMapper.updateMoneyByNameAndMoney(user); if(updateCount ! =null && updateCount.equals(1)) { // If the update succeeds, the loop is broken break; } } } Copy the code- 3.2.2 Flow chart is as follows:
| steps | Thread A | Thread B |
|---|---|---|
| 1 | Select money + 100 = 1100(V:1000–A:1000–B:1100) select money + 100 = 1100(V:1000–A:1000–B:1100) | |
| 2 | Select money + 100 = 1100(V:1000–A:1000–B:1100) select money + 100 = 1100(V:1000–A:1000–B:1100) | |
| 3 | UPDATE user_info SET money = money + 100 WHERE user_name = ‘money’ AND money = 1000; The number of updates is 1 | |
| 4 | UPDATE user_info SET money = money + 100 WHERE user_name = ‘money’ AND money = 1000; , returns 0 updates | |
| 5 | Out of the loop, return update success | |
| 6 | Money + 100 = 1200(V:1100–A:1100–B:1200) | |
| 7 | UPDATE user_info SET money = money + 100 WHERE user_name = ‘money’ AND money = 1100; The number of updates is 1 | |
| 8 | Out of the loop, return update success |
As to what the problem is and how to solve it, it will be explained in the following sections, otherwise there will be no more information in the following sections.
Note that the version number plus mechanism is not the same as the version number plus mechanism for CAS to resolve ABA problems.
4. Pessimistic lock is commonly implemented
4.1 already
Reentrant locks are pessimistic locks. If you have read the previous two articles, the principle of reentrant locks is clear. If not, take a look at the following flow:
- Assume that 0 indicates that the synchronization status is not locked, and 1 indicates that the lock is successful
| steps | Thread A | Thread B |
|---|---|---|
| 1 | Clone synchronization status value 0 from main memory, set the comparison value to 0, and write the new value to 1(V:0–A:0–B:1) | |
| 2 | Clone synchronization status value 0 from main memory, set the comparison value to 0, and write the new value to 1(V:0–A:0–B:1) | |
| 3 | Update main memory, compare the value of A and main memory, 0 = 0, lock success, at this time the main memory value is 1 | |
| 4 | Update main memory, compare A with main memory, 0! = 1, lock failed. | |
| 5 | The locking succeeded | |
| 6 | Execute business logic | Spin tries to update main memory again, comparing the value of A and main memory, 0! = 1, lock failed |
| 7 | Spin tries to update main memory again, comparing the value of A and main memory, 0! = 1, lock failed | |
| 8 | Block the thread by calling the parkAndCheckInterrupt() method | |
| 9 | Release the lock and set the synchronization status value to 0 | |
| 10 | After the precursor node leaves the queue and wakes up, it tries to update the main memory again. Comparing the value of A and the main memory, 0 = 0, locking is successful, and the main memory value is 1 at this time |
As you can see, as long as the thread A acquire the lock, haven’t release, then thread B is unable to get the lock, unless A release the lock, B to acquire the lock, lock the way is through the CAS to compare to exchange, B will attempt to spin to set value, after trying A few times, can block the thread, the team after the notice until the precursor node try again to obtain the lock, This explains why pessimistic locks cost more performance than optimistic locks.
4.2 synchronized
A volatile int is used to obtain and release locks. Synchronized uses a volatile int to determine whether a lock is acquired or released.
public class synchronizedTest {
.
public void synchronizedTest(a){
synchronized (this) { mapper.updateMoneyByName("Zhang"); } } } Copy the codeThe flow chart corresponding to the above code is as follows:
| steps | Thread A | Thread B |
|---|---|---|
| 1 | Call the synchronizedTest() method | |
| 2 | Call the synchronizedTest() method | |
| 3 | Insert monitorenter directive | |
| 4 | Execute business logic | Try to obtain ownership of the Monitorenter directive |
| 5 | Execute business logic | Try to obtain ownership of the Monitorenter directive |
| 6 | Execute business logic | Try to obtain ownership of the Monitorenter directive |
| 7 | After executing the business logic, insert the Monitorexit directive | Try to obtain ownership of the Monitorenter directive. With success, insert the Monitorenter directive |
| 8 | Execute business logic | |
| 9 | Execute business logic | |
| 10 | After executing the business logic, insert the Monitorexit directive |
If an exception occurs while executing synchronizedTest(), monitorexit inserts the exception. ReentrantLock requires you to manually lock and release the lock, whereas synchronized is done by the JVM.
5. Disadvantages of optimistic locking
5.1.1 ABA problem
There is a problem when optimistic lock is implemented in CAS mode, which can be found by discerning people. I don’t know if you have found it. The problem is as follows:
| steps | Thread A | Thread B |
|---|---|---|
| 1 | Select money + 100 = 1100(V:1000–A:1000–B:1100) select money + 100 = 1100(V:1000–A:1000–B:1100) | |
| 2 | Select money + 100 = 1100(V:1000–A:1000–B:1100) select money + 100 = 1100(V:1000–A:1000–B:1100) | |
| 3 | UPDATE user_info SET money = money + 100 WHERE user_name = ‘money’ AND money = 1000; The number of updates is 1 | |
| 4 | UPDATE user_info SET money = money + 100 WHERE user_name = ‘money’ AND money = 1000; , returns 0 updates | |
| 5 | Out of the loop, return update success | |
| 6 | Money + 100 = 1200(V:1100–A:1100–B:1200) | |
| 7 | UPDATE user_info SET money = money + 100 WHERE user_name = ‘money’ AND money = 1100; In step 6, we found money=1100. Can we be sure that money has not been modified by another thread? The answer is no, there are threads that can add 100 to C and subtract 100 from D, and the money is still 1100. This problem is known as the “ABA” problem for CAS operations.) | |
| 8 | Out of the loop, return update success |
- Solution:
Add a version field to the table and increment it by 1 each time it is changed.
| steps | Thread A | Thread B |
|---|---|---|
| 1 | Select money=1000, version=1 from table | |
| 2 | Select money=1000, version=1 from table | |
| 3 | UPDATE user_info SET money = money + 100, Version = version + 1 WHERE user_name = ‘c’ AND money = 1000 AND version = 1;) The number of updates is 1 | |
| 4 | UPDATE user_info SET money = money + 100, Version = version + 1 WHERE user_name = ‘c’ AND money = 1000 AND version = 1;) , returns 0 updates | |
| 5 | Out of the loop, return update success | |
| 6 | Spinner = money=1100, version = 2 | |
| 7 | UPDATE user_info SET money = money + 100, Select user_name from user_name WHERE user_name = ‘c’ AND money = 1100 AND version = 2;) The number of updates is 1 | |
| 8 | Out of the loop, return update success |
5.1.2 Long cycle time and high overhead
Spin CAS (that is, if it fails, it loops until it succeeds) can be very expensive for the CPU to execute if it fails for a long time. My idea is to add the number of attempts in an endless loop and return failure if the number of attempts is not successful. Not sure if there is any problem, welcome to point out.
5.1.3 Atomic operations of only one shared variable can be guaranteed
CAS is valid only for a single shared variable, and not when the operation involves spanning multiple shared variables. However, since JDK 1.5, the AtomicReference class has been provided to ensure atomicity between reference objects, and you can put multiple variables into one object to perform CAS operations. So we can use locks or use the AtomicReference class to merge multiple shared variables into a single shared variable.
6. Disadvantages of pessimistic locking
6.1 synchronized
- The release of the lock is rare, only when the program completes normal execution and throws exceptions to release the lock;
- Attempts to acquire locks cannot be set to timeout;
- You cannot interrupt a thread that is trying to acquire a lock;
- There is no way to know if the lock was successfully acquired;
6.2 already
- You need to import related classes using import;
- Don’t forget to release locks in the finally module, which looks uglier than synchronized;
- Synchronized can be placed in method definitions, whereas ReentrantLock can only be placed in blocks. Synchronized, by contrast, reduces nesting;
At the end
If you think my article is helpful to you, please pay attention to my wechat official account :” A happy and painful programmer “(no advertising, simply share original articles, pJ practical tools, a variety of Java learning resources, looking forward to common progress with you).
