Pessimistic locking

Pessimistic locks always assume the worst and assume that the data will be modified every time they go to fetch it. So it always locks when it gets the data. Others will block until they get the lock. Can be understood as the charger socket and plug, a socket can only be realized by a plug at the same time. The more common pessimistic locks are synchronized and ReentrantLock.

Optimistic locking

Optimistic locking is a best-case scenario in which every time you go to fetch data, you assume that the data will not be modified, so you don’t lock the read data. However, during the update, we will judge whether others have updated the data during this period, which can be achieved by using the version number mechanism and CAS algorithm.

Optimistic locking is often used for multi-read types to improve throughput.

Common optimistic locks have write_condition mechanism, atomic variable class under juC package is implemented using optimistic lock CAS.

The implementation of optimistic locking

Optimistic locking is commonly implemented by version number mechanism and CAS algorithm.

1. Version number mechanism

Version number mechanism, that is, to add a version number version field to the data. When data is modified, the version value is incremented by one.

Let’s take a simple example.

Let’s say I have two threads A and B. There is data with a value of 100 and version 1.

  • Thread A performs -50 operations on data. Read its version = 1, then execute 100-50 = 50.
  • Thread B performs +20 operations on data. Read version = 2, then 100 + 20 = 120.
  • Thread A completes the operation and changes version to 1, where version is 2. Together with the data 50 after the operation, it is submitted to the database for update. Because the version submitted is larger than the original version, the original data is updated. The database version changes to 2.
  • Thread B has completed the operation and is about to write version+1 to the data. However, the version in the database is no longer smaller than that in thread B. Therefore, the optimistic lock policy of “Update can be performed only when the version submitted is greater than the current version” is not met.

So thread B fails to commit.

Thus, the data of A and B will not be wrong.

2. CAS algorithm

CAS, Compare and Swap, is a lock-free algorithm. As you can see from the name, compare first and then decide whether to exchange. This is an algorithm that allows synchronization without locking, also known as non-blocking synchronization.

The CAS algorithm typically involves three values: the memory value V to read and write, the value A to compare, and the new value B to write. CAS can only replace V with A new value B if V is equal to A, otherwise it will keep spinning.

Problems with optimistic locking

Optimistic locks have their own limitations.

1. ABA problems

If the transaction first reads A value of 20, CAS will assume that the value of A has not been changed when we attempt to modify it and find that the value is still 20. Is it true that the value of A has not been changed in this process? Obviously not, because there’s A good chance that A has been changed, and then changed back to A.

This problem is known as the “ABA” problem.

2. Long cycle time and high cost

The CAS spin executes in a loop if the lock is not acquired for a long time, which incurs a significant execution overhead on the CPU.

3. Atomic operations of only one shared variable can be guaranteed

CAS is valid only for a single shared variable. CAS cannot be guaranteed to take effect once multiple shared variables are involved.

CAS and Synchronized

In general, CAS can be used for low-write scenarios, while synchronized is used for high-write scenarios.