锁原理 #

首先，如果要你实现一把锁，该如何实现呢？就从简单到复杂,慢慢考虑性能等一些因素。

一个变量
一个抢占动作:
  抢占失败(比如已经被其他线程抢占了)处理:
    immediately-retry
    yield
    sleep
    park
    mix(immediately-retry, yield/sleep/park)
  重试

下面是它的伪代码:

var v = 0

func unlock(){ //解锁
  v=0
}

func lock(){ //加锁
  retry:
    if !CompareAndSet(0, 1){
       handleErr()
       goto retry
  }
}

func handleErr(){ // 处理方式有如下几种
  // immediately-retry
  // yield             
  // sleep
  // park
  // mix(immediately-retry, yield/sleep/park)
}

func CompareAndSet(except, newValue int)bool{
	//cas操作,如果修改v则返回true
}

下面我们来讲讲这几种CAS失败后处理方式。

自旋 #

最容易想到可能是自旋：

func handleErr(){
  // 可以使用CPU提供的PAUSE指令来实现「忙等待」，因为可以减少循环等待时的耗电量
  return // 直接返回，马上重试// immediately-retry
}

这样实现的锁显然有个致命的缺点：耗费cpu资源。没有竞争到锁的线程会一直占用cpu资源进行cas操作，假如一个线程获得锁后要花费10s处理业务逻辑，那另外一个线程就会白白的花费10s的cpu资源。（假设系统中就只有这两个线程的情况）。

yield #

要解决自旋锁的性能问题必须让竞争锁失败的线程不忙等,而是在获取不到锁的时候能把cpu资源给让出来，说到让cpu资源，你可能想到了yield()方法，看看下面的例子：

func handleErr(){
  return yield() // yield             
}

当线程竞争锁失败时，会调用yield方法让出cpu。需要注意的是该方法只是当前让出cpu，有可能操作系统下次还是选择运行该线程。其实现是将当期线程移动到所在优先调度队列的末端（操作系统线程调度了解一下？有时间的话，下次写写这块内容）。也就是说，如果该线程处于优先级最高的调度队列且该队列只有该线程，那操作系统下次还是运行该线程。

自旋+yield的方式并没有完全解决问题，当系统只有两个线程竞争锁时，yield是有效的。但是如果有100个线程竞争锁，当线程1获得锁后，还有99个线程在反复的自旋+yield，线程2调用yield后，操作系统下次运行的可能是线程3；而线程3CAS失败后调用yield后，操作系统下次运行的可能是线程4… 假如运行在单核cpu下，在竞争锁时最差只有1%的cpu利用率，导致获得锁的线程1一直被中断，执行实际业务代码时间变得更长，从而导致锁释放的时间变的更长。

sleep #

你可能从一开始就想到了，当竞争锁失败后，可以将用Thread.sleep将线程休眠，从而不占用cpu资源：

func handleErr(){
  sleep(10) // sleep
}

上述方式我们可能见的比较多，通常用于实现上层锁。该方式不适合用于操作系统级别的锁，因为作为一个底层锁，其sleep时间很难设置。sleep的时间取决于同步代码块的执行时间，sleep时间如果太短了，会导致线程切换频繁（极端情况和yield方式一样）；sleep时间如果设置的过长，会导致线程不能及时获得锁。因此没法设置一个通用的sleep值。就算sleep的值由调用者指定也不能完全解决问题：有的时候调用锁的人也不知道同步块代码会执行多久。

park #

那可不可以在获取不到锁的时候让线程释放cpu资源进行等待，当持有锁的线程释放锁的时候将等待的线程唤起，然后再次进行竞争呢?

Queue parkQueue;

func handleErr(){
  lock_wait() // park
}

func lock_wait(){
	//将当期线程加入到等待队列
	parkQueue.lpush(nowThread)
	//将当期线程释放cpu
	releaseCpu()
}

func unlock(){
	lock_notify()
}

func lock_notify(){
	//得到要唤醒的线程
	Thread t=parkList.rpull()
	//唤醒等待线程
	wakeAThread(t)
}

上面是伪代码，描述这种设计思想，至于释放cpu资源、唤醒等待线程的的具体实现，后文会再说。这种方案相比于sleep而言，只有在锁被释放的时候，竞争锁的线程才会被唤醒，不会存在过早或过晚唤醒的问题。

小结 #

当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。所以线程切换是有代价的，如果当锁冲突不严重，用第一种方式(自旋锁)更适合，试想每个线程获得锁后很短的一段时间内就释放锁，竞争锁的线程只要经历几次自旋运算后就能获得锁，比上下文切换的开销少。

现在的锁实现是比较复杂，至少会包含自旋+等待相结合的方式：在锁失败后会先自旋一定次数，如果还没获得锁再进行等待。(当然还有更加复杂的结合形式，比如golang里面的锁实现)

死锁 #

在多个并发程序中，互相持有对方线程的独占锁
死锁的另一个常见来源是在goroutine中重复获取锁:

// ----------------1-----------------------------------
// 死锁最常见的来源之一是不一致的锁排序:比方说，您有两个互斥体A和B，在某些goroutines中:
A.Lock() // defer A.Unlock() or similar.
...
B.Lock() // defer B.Unlock() or similar.

// 在其他goroutine中，获取锁的顺序是反的
B.Lock() // defer B.Unlock() or similar.
...
A.Lock() // defer A.Unlock() or similar.

// ----------------2-----------------------------------

// 在goroutine中重复获取锁:
A.Rlock() or lock()

A.lock() or A.RLock()

互斥条件：一个资源每次只能被一个线程使用。
请求与保持条件：一个线程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：线程已获得的资源，在未使用完之前，不能强行剥夺。
循环等待条件：若干线程之间形成一种头尾相接的循环等待资源关系。
互斥条件 —> 独占锁的特点之一。
请求与保持条件 —> 独占锁的特点之一，尝试获取锁时并不会释放已经持有的锁
不剥夺条件 —> 独占锁的特点之一。
循环等待条件 —> 唯一需要记忆的造成死锁的条件。

在并发程序中，避免了逻辑中出现复数个线程互相持有对方线程所需要的独占锁的的情况，就可以避免死锁。

使用资源有序分配法;按照同一顺序来获取资源锁。

package main

import (
	"fmt"
	"sync"
)
import "time"

var lockA sync.Mutex
var lockB sync.Mutex

func funcA(flag chan<- int) {
	lockA.Lock()
	time.Sleep(time.Second)
	lockB.Lock()

	lockB.Unlock()
	lockA.Unlock()
	flag <- 1
	return
}

func funcB(flag chan<- int) {
	lockB.Lock()
	time.Sleep(time.Second)
	lockA.Lock()

	lockA.Unlock()
	lockB.Unlock()
	flag <- 1
	return
}

func main() {
	var (
		tick    = time.NewTicker(10 * time.Second)
		flag    = make(chan int, 2)
		flagNum int
	)

	go funcA(flag)
	go funcB(flag)

	for {
		select {
		case <-tick.C:
			fmt.Println("overtime")
			return
		case <-flag:
			if flagNum == 1 {
				fmt.Println("all goroutine exist")
				return
			} else {
				flagNum++
			}
		}
	}
}

读写锁 #

读锁和写锁都可以看作可以上锁的东西，只是写锁是排他性的，如果它上了锁，其他读/写锁就没办法加锁，而读锁它上锁后，其他读锁可以继续上锁，但排斥写锁。

一般可分为三类:公平读写锁，读优先(可能导致写饥饿)，写优先(读饥饿)三类。

按照写锁->读锁的逻辑顺序去看:

写锁加上了以后，是把v减去一个很大的值，使得它可以容纳一个很大的读锁。

var maxReadLockSize int32 = 1<<30
// ------------------------------
var (
  lock LOCK // 前面所说的锁
  v = int32(0) // 0 not lock; 1 write lock; 2 read lock;
  notifyWLockAfterReaderWait int32 = 0 
)

func RLock(){
  retry:
    if Add(&v, 1)<0{
      // 写锁在占用
      handleErr()
      goto retry
    }
    // 读抢到锁
}
func RUnlock(){
    
    if r := Add(&v, -1); r < 0 {

      if Add(&notifyWLockAfterReaderWait, -1) == 0{
          // 所有的读完成了，应该去唤醒写
          lock_notify()
      }
    }

}

func WLock(){
  lock.Lock() // 先用前面的自旋/互斥锁锁住,同一时间只有一个写能进入这里面。
  retry:
    r := Add(&v, -maxReadLockSize) + maxReadLockSize
    // 不等于0证明有正在读的动作
    if r!=0 && Add(&notifyWLockAfterReaderWait, r){
      handleErr()
      goto retry
    }
}

func unlock(){ //解锁
  v=0
}

func lock(){ //加锁
}

https://zhuanlan.zhihu.com/p/98443808

悲观与乐观锁 #

乐观锁和悲观锁是两种思想，它们的使用是非常广泛的，不局限于某种编程语言或数据库

悲观是先一定要加上锁，然后继续执行其他逻辑乐观是提交的时候才进行判断，是无锁的，而且这里提交与更新有可能是同一个动作，导致提交更新判断是原子性的。

乐观锁 #

CAS #

缺点是

ABA问题假设有两个线程——线程1和线程2，两个线程按照顺序进行以下操作：

(1)线程1读取内存中数据为A；

(2)线程2将该数据修改为B；

(3)线程2将该数据修改为A；

(4)线程1对数据进行CAS操作

在第(4)步中，由于内存中数据仍然为A，因此CAS操作成功，但实际上该数据已经被线程2修改过了。这就是ABA问题。

在AtomicInteger的例子中，ABA似乎没有什么危害。但是在某些场景下，ABA却会带来隐患，例如栈顶问题：一个栈的栈顶经过两次(或多次)变化又恢复了原值，但是栈可能已发生了变化。

对于ABA问题，比较有效的方案是引入版本号，内存中的值每发生一次变化，版本号都+1；在进行CAS操作时，不仅比较内存中的值，也会比较版本号，只有当二者都没有变化时，CAS才能执行成功。Java中的AtomicStampedReference类便是使用版本号来解决ABA问题的。

只能应用于单值问题，CAS只能保证单个变量（或者说单个内存值）操作的原子性，这意味着：(1)原子性不一定能保证线程安全，例如在Java中需要与volatile配合来保证线程安全；(2)当涉及到多个变量(内存值)时，CAS也无能为力

加版本号 #

玩家信息增加一个字段：version。在初次查询玩家信息时，同时查询出version信息；在执行update操作时，校验version是否发生了变化，如果version变化，则不进行更新。

public void updateCoins(Integer playerId){
    //根据player_id查询玩家信息，包含version信息
    Player player = query("select coins, level, version from player where player_id = {0}", playerId);
    //根据玩家当前信息及其他信息，计算新的金币数
    Long newCoins = ……;
    //更新金币数，条件中增加对version的校验
    update("update player set coins = {0}, version = version + 1 where player_id = {1} and version = {2}", newCoins, playerId, player.version);
}

可见性,内存屏障与原子性， #

可见性:通常是指在cpu多级缓存下如何保证缓存的一致性，即在一个CPU上修改了了某个数据在其他的CPU上不会继续读取旧的数据，内存屏障:通常是为了CPU为了提高流水线性能，而对指令进行重排序而来，原子性:是指的执行某个操作的过程的不可分割

# atomic/asm_amd64.s TEXT runtime∕internal∕atomic·Xadd(SB)
    LOCK # LOCK指令配合CPU的MESI协议，实现可见性和内存屏障
    XADDL   AX, 0(BX) # 通过XADDL则用来保证原子性

https://java366.com/blog/detail/409a3d2f952c92cbb84f4a1438b1dc0c

mysql锁 #

一个是悲观锁（行锁/grap锁/next-key锁）一个是乐观锁（mvcc使用undo log来实现的一致性非锁定读, 利用事务版本的概念来实现的锁）

悲观锁 #

乐观锁 #

ACID #

隔离性 #

MySQL默认的隔离级别是RR

Isolution

四种隔离级别: 读未提交/读已提交/可重复读/串行

读过程可能会发生的三种错误: 脏读/不可重复读/幻读

\	脏读	不可重复读	幻读
串行	x	x	x
可重复读	x	x	o
读已提交	x	o	o
读未提交	o	o	o

明确一点，如果当前有多个事物在写同一条记录，会存在竞争，也就是都是写的同一份记录所在的磁盘文件/内存。 MVCC的应用场景是在读的时候其他事物同时在写，不会影响我读的结果，也就是一致性非锁定读

所以我们看下读未提交隔离级别，它本身就需要读到记录最新的结果，而串行隔离级别，每次只有一个事务在操作，不会出现读过程三种错误

快照 #

创建ReadView(一致性读/快照)时机 #

读提交隔离级别中每个SQL开始时都会创建一个ReadView 可重复读级别中每个事物开始时都会创建一个ReadView

事物开启的时机 #

一般有两种情况:

begin/start transaction; # 单独只执行此指令，事物不会真正发生,也不会创建ReadView
select/udpate/insert/delete ... # 只有继续执行了增删查改操作的 SQL 语句，才是事务真正启动的时机

start transaction with consistent snapshot; // 马上就会开始事物，且创建ReadView

创建ReadView(一致性读/快照)逻辑 #

可重复读隔离级别: 当一个事务开启的时候，会向系统申请一个新事务id, 此时，可能还有多个正在进行的其他事务没有提交，因此在瞬时时刻，是有多个活跃的未提交事务id, 将这些未提交的事务id组成一个数组，数组里面最小的事务id记录为低水位，当前系统创建过的事务id的最大值记录为高水位, 这个数组array 和高水位，就组成了“一致性视图”。

可见性判断 #

    未提及的事务
   |_______________________________|            |
 notCommitMinTxID    notCommitMaxTxID    systemMaxTxID
  低水位                                        高水位

四个范围：

可见：(0, notCommitMinTxID)
不可见：[notCommitMinTxID, notCommitMaxTxID]
可见：(notCommitMaxTxID, systemMaxTxID]
不可见：(systemMaxTxID, infine)

innodb是否解决幻读问题 #

当前读：next-key lock（行锁+间隙锁）解决了快照读：没有彻底解决，当快照读中混入当前读

当前DB已有id 5, 10, 15三条数据。
事务A查询id < 10的数据，可以查出一行记录id = 5
事务B插入id = 6的数据
事务A再查询id < 10的数据，可以查出一行记录id = 5，查不出id = 6的数据（读场景，解决了幻读）
事务A可以更新/删除id = 6的数据，不能插入id = 6的数据（写场景，幻读不彻底）

这个很好理解，MySQL虽然通过MVCC的版本号来解决了读场景下的幻读，但对于上面第5步那种写场景的情况，其实是无能为力的，因为MVCC毕竟是无锁实现。

所以如果后续要对数据进行写操作，还是用for update语句先上锁,进入当前读，加上next-key lock比较稳妥，不然就可能会出现上面第5步那样的问题。

mysql隔离级别的可重复读本身不能解决幻读问题，但是现在mysql借助MVCC多版本控制和行锁解决了绝大部分的幻读问题。指出一下，第二个测试里事务B的序号 4 是可以查询出事务A所插入的数据吧。测试二中事务B出现幻读问题主要是，在事务A提交事务之后进行一次update操作，相当于select….for update，是当前读操作，会更新Read View，所以，当事务A提交之后，事务B进行update操作，读取的是最新版本的数据，也就是说事务A的操作对于事务B操作是可见性的。往往就是，RR级别下的幻读，是直接或间接的执行了当前读，导致Read View被更新，所以会读取最新版本的数据。个人觉得，mysql在RR级别下利用MCVV和行锁机制会出现幻读应该就是这个原因吧。

https://www.yasinshaw.com/articles/125

原子性 #

(atomic)

使用undo log 来记录修改之前的旧记录, 是一个逻辑日志，不是物理的

在对数据库进行修改时，innoDB引擎除了会产生redo log，还会产生undo log。InnoDB实现回滚，靠的是undo log：当事务对数据库进行修改时，InnoDB会生成对应的undo log；如果事务执行失败导致事务需要回滚，就利用undo log中的信息将数据回滚到修改之前的样子。

有人认为undo log是redo log的逆过程，其实是不对的。两个日志文件其实都能看作是一种对数据的恢复操作，redo log恢复事务导致的数据页的修改，而undo log能够恢复数据记录到某个特定的版本。

所以redo log是一种物理日志（数据页的修改），而undo log是一种逻辑日志（数据记录）。

undo log还要另外一个重要作用，就是用于mvcc中，进行多版本控制，也就是实现事务隔离性的基础，当用户读取一行记录时，如果这个记录已接被其他事务占用，那么当前事务就可以通过undo读取之前的行版本信息，用来实现非锁定读取，就是“快照读”。

持久性 #

(duration)

write ahead log WAL

二阶段提交: 事务提交前，将 redo log 的写入拆成了两个步骤，prepare 和 commit。

通常我们说 MySQL 的“双 1”配置，指的就是 sync_binlog 和 innodb_flush_log_at_trx_commit 都设置成 1。也就是说，一个事务完整提交前，需要等待两次刷盘，一次是 redo log（prepare 阶段），一次是 binlog。

redo log是innodb的存储引擎产生的，而binlog是数据库的server层实现的。换句话说，如果你使用MySQL，换其他存储引擎，那么可能没有redo log，但是还是会有binlog。

日志记录的内容形式不同。 binlog是一种逻辑日志，记录对应的SQL语句，而redo log记录了物理日志，是针对每个数据页的修改。

日志写入磁盘时间不同。 binlog只有在事务提交后完成一次写入，对于一个事物而言，在binlog中只有一条记录。而redo log在事务进行中不断被写入，而且是并发写入的，不是顺序写入的。

保存方式不同。 redo log 是循环写的，空间固定会用完；binlog 是可以追加写入的。“追加写”是指 binlog 文件写到一定大小后会切换到下一个，并不会覆盖以前的日志。

inner join <-> join
- They are functionally equivalent, but INNER JOIN can be a bit clearer to read, especially if the query has other join types (i.e. LEFT or RIGHT or CROSS) included in it.
如何锁住一个范围
5.7mysql的innodb的默认级别是RR RC? 为什么RR能防止幻读，而RC不能防止幻读，由于间隙锁加行锁？next-key lock

数据库事务ACID特性数据库事务的4个特性：

原子性(Atomic): 事务中的多个操作，不可分割，要么都成功，要么都失败； All or Nothing.

一致性(Consistency): 事务操作之后, 数据库所处的状态和业务规则是一致的; 比如a,b账户相互转账之后，总金额不变；

隔离性(Isolation): 多个事务之间就像是串行执行一样，不相互影响;

持久性(Durability): 事务提交后被持久化到永久存储.

MySQL 中RC和RR隔离级别的区别 MySQL数据库中默认隔离级别为RR，但是实际情况是使用RC 和 RR隔离级别的都不少。好像淘宝、网易都是使用的 RC 隔离级别。那么在MySQL中 RC 和 RR有什么区别呢？我们该如何选择呢？为什么MySQL将RR作为默认的隔离级别呢？

5.1 RC 与 RR 在锁方面的区别 1> 显然 RR 支持 gap lock(next-key lock)，而RC则没有gap lock。因为MySQL的RR需要gap lock来解决幻读问题。而RC隔离级别则是允许存在不可重复读和幻读的。所以RC的并发一般要好于RR；

2> RC 隔离级别，通过 where 条件过滤之后，不符合条件的记录上的行锁，会释放掉(虽然这里破坏了“两阶段加锁原则”)；但是RR隔离级别，即使不符合where条件的记录，也不会是否行锁和gap lock；所以从锁方面来看，RC的并发应该要好于RR；另外 insert into t select … from s where 语句在s表上的锁也是不一样的。

I(Isolation)：https://zhuanlan.zhihu.com/p/118658549
- 锁+MVCC
  - 快照读
  - 当前读
    - Lock：https://zhuanlan.zhihu.com/p/109129926
ACD()：https://zhuanlan.zhihu.com/p/129860691

InnoDB存储引擎有三种行锁算法：

行锁：在单行记录上的锁
间隙锁：Gap Lock，锁定一个范围，但不包含记录本身
Next-Key Lock:就是行锁+间隙锁，同时锁上一个范围，并且锁定记录本身

https://zhuanlan.zhihu.com/p/161933980

https://www.cnblogs.com/kisun168/p/11320549.html

mvcc 的实现 undolog

实践next-key Lock https://mp.weixin.qq.com/s/i5QWx3QPZNkV51ghFbtXCw

锁 #

what:
- InnoDB锁:
  - 1. 共享锁（S）：允许一个事务去读一行，阻止其他事务获得相同数据集的排他锁。
  - 1. 排他锁（X）：允许获得排他锁的事务更新数据，阻止其他事务取得相同数据集的共享读锁和排他写锁。
  为了允许行锁和表锁共存，实现多粒度锁机制，InnoDB 还有两种内部使用的意向锁（Intention Locks），这两种意向锁都是表锁：
  - 1. 意向共享锁（IS）：事务打算给数据行加行共享锁，事务在给一个数据行加共享锁前必须先取得该表的 IS 锁。
  - 1. 意向排他锁（IX）：事务打算给数据行加行排他锁，事务在给一个数据行加排他锁前必须先取得该表的 IX 锁。

（如果一个事务请求的锁模式与当前的锁兼容， InnoDB 就将请求的锁授予该事务；反之，如果两者不兼容，该事务就要等待锁释放。）

why:
- 防止并发修改数据。
how:
- InnoDB加锁方法：
  - 对于普通SELECT语句，InnoDB 不会加任何锁；
  - 对于 UPDATE、 DELETE 和 INSERT 语句， InnoDB会自动给涉及数据集加排他锁（X)；
  - 事务可以通过以下语句显式给记录集加共享锁或排他锁：
    - 共享锁（S）：SELECT * FROM table_name WHERE ... LOCK IN SHARE MODE。其他 session 仍然可以查询记录，并也可以对该记录加 share mode 的共享锁。但是如果当前事务需要对该记录进行更新操作，则很有可能造成死锁。
    - 排他锁（X)：SELECT * FROM table_name WHERE ... FOR UPDATE。其他 session 可以查询该记录，但是不能对该记录加共享锁或排他锁，而是等待获得锁
  - ~~意向锁是 InnoDB 自动加的，不需用户干预。~~

参考 #

乐观锁和悲观锁: https://www.cnblogs.com/kismetv/p/10787228.html