Location>code7788 >text

Architecture and Thinking: CAS and ABA for Highly Concurrent Operations

Popularity:961 ℃/2024-10-10 08:09:21

1 Challenges in High Concurrency Scenarios

1.1 Typical Payment Scenarios

This is the most classic scenario. The payment process, which involves checking the buyer's account balance, then calculating the price of the item, and finally debiting the buyer, and distributed operations such as these.
If it's a case of low concurrency there's no problem at all, but if it's a concurrent deduction then there might be a consistency issue.In highly concurrent distributed business scenarios, operations such as "query+modify" are likely to lead to data inconsistency.
image

1.2 Online ordering scenarios

Similarly, a buyer placing an order on an e-commerce platform often involves two actions thatOne is to deduct inventory and the second is to update the status of the orderInventory and orders generally belong to different databases and require the use of distributed transactions to ensure data consistency.
image

1.3 Inter-bank transfer scenarios

The interbank transfer problem is also a typical distributed transaction, where a user, student A, transfers 500 to student B's account, to do first student A's account -500, and then student B's account +500, given that theDifferent banks, involving different business platforms, in order to ensure the consistency of these two operational steps, data consistency programs must necessarily be introduced
image

2 CAS Program

Distributed CAS (Compare-and-Swap) mode is a lock-free application of the idea, it is through the lock-free algorithm to achieve conflict-free access to shared resources between threads, not only to ensure high performance and efficiency, there is a guarantee of strong consistency of the data, to avoid the above centralized problem.
The CAS pattern consists of three basic operands: the memory address V, the old expected value A, and the new value to be modified B. When updating a variable, the value corresponding to memory address V is modified to B only if the variable's expected value A is the same as the actual value in the memory address V. The CAS pattern also consists of three basic operands.

We are based onSection 1.1 (used form a nominal expression)Typical Payment Scenarios Analyzed as an example (refer to the figure below):

  • Initial balance of 800
  • Operations 1 and 2 concurrently inquired about a balance of 800
  • Business 1 performs a Purchase Action and deducts 100, resulting in 700, which is the new balance. Theoretically, the deduction Action can only be executed successfully if the original balance is 800.
  • Business 2 performs a Life Payment Action (e.g. automatic payment of electricity bills), the original balance is 800, and the deduction removes 200, resulting in 600, which is the new balance. Theoretically, the Action of deducting can be executed successfully only when the original balance is 800. But in reality, the amount in the database at this time has changed to 600, so the concurrent deduction of operation 2 should not succeed.

According to the CAS principle above, theWhen Swap updates the balance, add the Compare condition to compare the balance with the initial read balance, and only allow Swap to succeed if the initial balance is unchanged, which is a common method to reduce read/write lock conflicts and ensure data consistency.
image

3 Introducing the ABA problem

The ABA problem is a common challenge in CAS (Compare-and-Swap) operations. This side assumes three operands - memory location (V), expected original value (A) and new value (B).
The ABA problem is when a thread reads a shared variable V with a value of A and later prepares to update it to B. Another thread may have already changed it from A to B and then back to A again.
At this point, the current thread still thinks that the value of V is the original A, so the CAS operation updates the value of V to B, but in reality the value of V has already been changed by another thread.

image

It has the following hazards:

1. Data consistency is compromised and leads to errors in business logic
In complex business logic, the values of shared variables often represent some kind of business state or condition.ABA issues can lead toThese states or conditions are accidentally changed, thus triggering business logic errors such as oversold inventory, duplicate release of funds, etc.
★ The following diagram describes in detail how ABA can cause an error in the inventory logic:
image

2. Difficulties in commissioning and orientation
ABA problems usually occur in multi-threaded environments, and their triggering conditions are relatively hidden. Therefore, when the system has an abnormality caused by ABA problems, it is often difficult to quickly locate the cause of the problem, which increases the complexity and time cost of debugging.

4 Treatment of different dimensions

ABA occurs because the CAS process only focuses on the checksum of the Value value. But ignored the value is still not the same value before, you can refer to the above inventory illustration. So in some cases, although the Value is the same, it is no longer the original data.

Solution: CAS can not only compare Value, but must also ensure that the original data in order to modify the success.
The general practice is to set a Version to the Value, which is used for comparison, one version for each data, and each time the data changes, the version follows the change, so that it will not be modified casually.

4.1 Application layer

Packages in Java provide tool classes for solving ABA problems.
In the Go language, concurrency is usually handled using the atomic operations provided by the sync/atomic package and introducing the concept of version numbers or timestamps.
The sample code is as follows:

type ValueWithVersion struct {
	Value int32
	Version int32
}  
  
var sharedValue // Use to storeValueWithVersionpointers
  
func updateValue(newValue, newVersion int32) bool {
	current := ().(*ValueWithVersion)
	if == newValue && == newVersion {
		// CASmanipulate:Only if the current value and version number both match,Just update the value
		newValueWithVersion := &ValueWithVersion{Value: newValue, Version: newVersion + 1}
		(newValueWithVersion)
		return true
	}  
	return false
}  

4.2 Data layer

  1. CAS Strategy
update stock set num_val=$num_new_val where sid=$sid and num_val=$num_old_val
  1. CAS strategy + Version to avoid ABA issues
# This way, please.,I've got a solution!version,There's no need to compare.old_val(modal particle intensifying preceding clause)
update stock set num=$num_new_val, version=$version_new where sid=$sid and version=$version_old

5 Summary

  1. Difficulties under high concurrency: payment, order placement, interbank transfers
  2. The CAS program and the ABA issues it raises
  3. Processing of different dimensions: application layer, data layer

La-la-la-la-la-la-la-la-la-la-la-la-la-la-la.,I'm going for a run.