高併发系统系列-使用lock & Interlocked CAS(compare and swap)

前言

在之前我有写一篇关于资料库的ACID分享RDBMS资料库基本原则

假如我们系统是一个多执行续高併发系统也要注意Atomic不然会造成资料会有Data Racing导致bug产生..

本文使用範例在我github上CAS_Lock有兴趣的人可以参考.

本篇同步发布在我的Blog 高併发系统系列-使用lock & Interlocked CAS(compare and swap)

没有注意Atomic会导致的问题

我是我们公司担任技术面试官之一，假如面试者说他实作过高併发系统。

我就会先问以下问题来辨别是否要更深入面试高併发系统相关问题.

下面Sample Code是这样.

我用Task假装高併发，下面有一个Member类别预设给100000元的Balance

有一个UpdateBalance每呼叫一次就扣10元，我透过For跑10000次

理论上我预期在跑完下面显示Balance会员余额是0 (因为 10000*10 = 100000).

class Program{static void Main(string[] args){Member member = new Member() { Balance = 100000 };List<Task> tasks = new List<Task>();for (int i = 0; i < 10000; i++){tasks.Add(Task.Run(() => member.UpdateBalance()));}Task.WaitAll(tasks.ToArray());Console.WriteLine($"member remaining balance is {member.Balance}");Console.ReadKey();}}public class Member {public decimal Balance { get; set; }public void UpdateBalance(){Balance -= 10;}}

但执行后蛮常会是不等于0!!

这时我会问面试者两个问题

为什么会不等于0如果要解决你会怎么解决这个问题?

如果知道的人可以跳到CAS部分，如果不知原因我下面会跟大家分享

为什么会不等于0

这个问题牵扯到Thread是如何对于变数操作的，Thread在操作变数之前会把资料複製一份进Thread Context中在操作我们要步骤

所以在Balance -= 10;这段程式码会拆成下面动作

将执行个体变数中的值载入至register。将载入值减10将异动后值放回原本值的Memory。

因为以上步骤，假如同一时间有两个不同的Thread取到的Balance都是1000，并个别对于Balance减10元，我们原本预期这是两个操作（预期资料为980）

但因为取的瞬间都是1000-10=990把数值放回变数中就导致少扣一个10元...

概念如下图.

知道原因了要解决就简单了.

使用Lock解决

因为这段程式码遇到Data Raceing在同一个时间有两个不同的Thread对于资料竞争

如果要避免竞争lock是一个比较方便的方式，他可以保证一瞬间只有一个Thread(Session)来执行某段程式码(通常会放在异动资料那部分)来保证Isolation.

下面是使用lock版本的程式码，能看到我在Balance -= 10;这一段使用lock来确保每一个瞬间只有一个Thread可以异动资料，其他的Thread需要blocking等他完成

class Program{static object _lock = new object();static void Main(string[] args){Member member = new Member() { Balance = 100000 };List<Task> tasks = new List<Task>();for (int i = 0; i < 10000; i++){tasks.Add(Task.Run(() => member.UpdateBalance()));}Task.WaitAll(tasks.ToArray());Console.WriteLine($"member remaining balance is {member.Balance}");Console.ReadKey();}}public class Member {//hereobject _lock = new object();public decimal Balance { get; set; }public void UpdateBalance(){lock (_lock){Balance -= 10;}}}

使用lock之后能发现不管执行几次资料都会如我们预期显示.

使用lock执行概念图如下.

在同一时间我们会把要执行程式 利用一个类似保护网的方式，确保同一时间只有一个Thread来做操作.

Thread2取得lock在操作Thread1就必须等待Thread2执行完,在取值=>改值..等等动作

只是使用lock会降低些许吞吐量(但资料正确性是最重要的)，所以要注意使用lock範围大小

CAS(compare and swap)提高效率

CAS是利用compare and swap来确保资料Atomic.

因为CAS可以取得数值记忆体空间来比较给值并且他也是一条CPU原语具有原子性 cpu 硬体同步原语

前面有说过在Balance -= 10;这段程式码会拆成下面动作

将执行个体变数中的值载入至register。将载入值减10将异动后值放回原本值的Memory。

balance -= 10;

会拆解成类似下面动作

int temp = balance;temp = temp -10;balance = temp;

假如在取balance(附值给temp)跟把值重新写入balance中间有其他Thread来操作，就会造成所谓Data Racing，因为对于我们来说上面后两部有不可分割性(Atomic).

而这时候我们就可以使用CAS算法来帮我们解决问题，在C#如果我们想要达成变数修改的Atomic可以透过Interlocked类别

使用Interlocked提高效率

在C#中我们可以使用Interlocked这个类别

对于Int,Long相关操作都有封装成method.

下面这段虚拟码解释balance -= 10;CAS中类似下面效果

//originalint temp = balance;temp = temp -10;balance = temp;//CAS int oldValue = balance;int newValue = oldValue - 1;//compare value source and setInterlocked.CompareExchange(ref balance,newValue,oldValue);//Interlocked.CompareExchange类似下面做法，但具有Atomic//if(ref balance == oldValue){//balance = newValue;//}

主要是把compare value source and set这段包成一个不可分割区段达到Atomic.

＞ 我上面用ref来表示从记忆体位置取得balance原始资料

Exchange:把值改成另一个数值 具有AtomicDecrement:把数值-- 具有AtomicIncrement:把数值++ 具有Atomic

除了上面我们还可以针对Reference Type做Atomic有兴趣的人在自行了解

class Program{static object _lock = new object();static void Main(string[] args){Stopwatch sw = new Stopwatch();int balanceValue = 10000000;Member member = new Member() { Balance = balanceValue };List<Task> tasks = new List<Task>();sw.Start();for (int i = 0; i < 1000000; i++){tasks.Add(Task.Run(() => member.UpdateBalance()));}Task.WaitAll(tasks.ToArray());sw.Stop();Console.WriteLine("Lock Version");Console.WriteLine($"member remaining balance is {member.Balance}");Console.WriteLine($"Exec Time Cost : {sw.ElapsedMilliseconds}");tasks.Clear();member.Balance = balanceValue;sw.Restart();for (int i = 0; i < 1000000; i++){tasks.Add(Task.Run(() => member.UpdateBalanceByInterlock()));}Task.WaitAll(tasks.ToArray());sw.Stop();Console.WriteLine("InterLocked Version:");Console.WriteLine($"member remaining balance is {member.Balance}");Console.WriteLine($"Exec Time Cost : {sw.ElapsedMilliseconds}");Console.ReadKey();}}public class Member {object _lock = new object();public int Balance { get; set; }public void UpdateBalance(){lock (_lock){Balance -= 10;}}public void UpdateBalanceByInterlock(){int val = 0;Balance = Interlocked.Exchange(ref val, Balance -= 10);}}

下图是比较两者执行时间还有併发计算数值，能发现数值两个都正确计算出0，但Interlocked执行时间少于lock版本.

Interlocked效率会比较高是因为block会造成Thread的blocking等待浪费,但Interlocked核心概念是在这段话Atomic取得资料跟原值比较(如果资料还没改就把值修改进Memory中)

所以效率就会比lock好很多

小结

在有些情境适合使用Lock(例如许多操作需要有一致的Atomic)就比较适合.

Interlocked适合用在对于数值的Atomic.

在多执行绪的世界中要顾虑的点真的很多，稍有不甚就会造成很多错误.

因为多执行绪有许多地方需要注意,不然执行效率会不如单执行绪.

我慢慢可以理解为什么Redis,Node.js一开始要使用sigel Thread来运作了...