本文代码块建议复制到本地阅读,因为宽屏模式阅读更方便
MVCC,全称Multi-Version Concurrency Control,即多版本并发控制,是数据库并发领域的一个基础概念,也是在一定业务场景下解决读写并发问题的一种思路,在数据库领域,并发控制是一个很具有挑战性的领域,除了MVCC,常见的并发控制方式还有乐观并发控制、悲观并发控制等。
乐观并发控制
乐观并发控制(乐观锁)也是一种并发控制的方法。它假设多个并发事务彼此之间不会互相影响,各事务能够在无锁的情况下处理各自的那部分数据,它一般分为三个阶段:读阶段、检查阶段、写阶段。
读阶段: 数据库会执行事务中的全部读操作和写操作,并将所有写后的值存入临时变量中,并不会真正更新数据库中的内容;
检查阶段: 数据库程序会检查当前的改动是否合法,也就是是否有其他事务在 RAED PHASE 期间更新了数据。
写阶段: 如果数据通过检测那么直接就进入 WRITE PHASE 将所有存在临时变量中的改动全部写入数据库,没有通过测试的事务会直接被终止。
注:有点类似于memcache中CAS指令的感觉 _
悲观并发控制
悲观并发控制(悲观锁)它可以阻止一个事务影响其他用户来修改数据,当事务需要对资源进行操作时需要先获得资源对应的锁,保证其他事务不会访问该资源后,对资源进行各种操作,实现较为简单,主要用于数据争用激烈、发生并发冲突时使用锁保护数据的成本要低于回滚事务的成本的环境中。
数据库系统比较常用的悲观锁协议是两阶段锁协议(2PL,Two-Phase Locking),2PL就说一个事务被分成两个阶段:加锁阶段、释放锁阶段,其中加锁阶段必须要在释放锁阶段完成,释放锁阶段不能在获取新的锁。同时2PL还有很多衍生概念,如下:
保守两阶段锁(Conservative 2PL,C2PL): 事务在开始时对它依赖的所有资源进行加锁,在事务执行过程中可以释放部分不需要保护的资源的锁,不用等到事务结束释放锁。
严格两阶段锁(Strict 2PL,S2PL): 事务在开始时对资源逐步加锁,也就是说事务可以在执行过程中对资源加读写写锁,但是写锁只能在事务结束统一释放,读锁可以在食物执行过程中释放。
强严格两阶段锁(Strong Strict 2PL,SS2PL): 事务在开始时对资源逐步加锁,也就是说事务可以在执行过程中对资源加读写写锁,但是读锁、写锁只能在事务结束统一释放。
!!!!etcd在put的过程中使用的batchTxBuffered,这个事务是写bbolt数据库使用的事务,是对bbolt.Tx的一个封装,就是攒一批事务作为一个大事务,一次性提交到bbolt。etcd对外服务得像一个数据库,但是外部看到的不是bbolt,也就是说外部对etcd提交的事务和etcd用来写bbolt时使用的事务完全是两个东西,etcd使用的事务是STM(软件事务内存)
etcd smt在单个事务中对同一key的修改在提交的时候只有最终的修改有效
STM、ReadView
!!!!总的来说,etcd的事务模型是在客户端实现的,但事务的执行是在etcd集群中的成员节点上完成的。
apply的时候是一条一条的应用的,但是如果要原子的同时apply一批日志,那么就必须使用STM
STM内部包含一个wset和一个rset,保存了本次事务访问到的数据和版本,然后在提交的时候如果发现事务变了,那么就会报错
commited时日志的索引顺序和apply时revision顺序是一致的
!!!wal虽然是顺序写入的,apply的时候也是顺序提交到bbolt的,apply的时候他是会把从chan收到的数据包装成一个job,然后丢到一个fifo队列,这个fifo队列会等当前任务运行完毕才会运行下一个job,也就是apply的时候也必定是按顺序apply的,也就是说只有上一个事务提交到bbolt才会开始提交下一个事务(看了源码),这样在开始x事务的时候x以前的日志都已经写完了,也就是说如果x事务读取的数据被x-k版本的事务修改了,那么x事务是可以检测出来的,如果检测到冲突,那么就不会把该数据写入数据库,也即是说即使日志已经写入了磁盘,但是数据是不一定会写入数据库的。举个例子:一个事务t1,先读取key a,此时a的版本(即revision)为v1,然后事务t1在本地执行了很久才提交事务,然后t1提交到etcd的时候raft日志索引为index1,然后apply的时候对应的revision为 rev1,然后执行的时候检测到key a此时的版本是v1+x,但是他读的时候a的版本为v1,所以此时就检测到了冲突(从treeIndex检测,因为treeIndex包含所有key和key对应的revision,比较一下revision就行),那么事务就会执行失败,虽然事务执行失败,但是日志是apply成功的,也就是说事务执行的结果就是数据不写入数据库。再举个例子,假设事务t1对应的raft日志已经写入磁盘,然后apply但是还没apply完成的时候系统崩溃了,这个没关系,重做就是了,当再次重做到事务t1对应的日志的时候,因为t1以前的日志必定已经重做完了,所以此时还是可以再次检测到冲突的,所以只要wal日志已经持久化了,那么崩溃就对这些已经持久化的日志无影响。
STM内对同一个值多次修改,那么只有最后一次写会成功,因为他是先在本地执行函数,然后得到一个最终的结果,再在commited时候直接提交最终的结果
!!mvcc写,也就是说多个版本
Server上Txn请求流程,分Read和Write
//txn事务有两种,一种是读事务,一种是写事务,通通都是通过这个函数来处理,读事务比较简单,重点在于后半段的写事务
//!!!!etcd只读事务不走raft流程,直接本地读
//!!!!个人疑惑:只读事务里面读不需要readIndex吗?
v3rpc.quotaKVServer.Txn
if isReadOnly #如果是只读事务,那么不需要走raft请求
v3rpc.kvServer.Txn
etcdserver.EtcdServer.Txn
txn.Txn
mvcc.store.Read #这里只是创建一个事务并不执行事务
s.mu.RLock() #是整个store直接加一把read锁,以阻止snapshot和compact,
#直到读事务完成才会释放对数据库的这把读锁
#不会阻止put/delete,因为这两都是追加数据,不会修改旧数据
mvcc.newMetricsTxnRead #包装一下,创建一个可追踪事务
txn.compareToPath #!!检测是否冲突:通过比较版本号实现
mvcc.NewReadOnlyTxnWrite #包装到一个只读write里,如果有写操作就会panic,
#因为走到这里说明是一个读事务,读事务肯定不会有写
txn.txn #执行事务
txn.executeTxn #根据req类型分发(Range: 表示read,Put:表示写,Txn:子事务)
case *pb.RequestOp_RequestRange
txn.executeRange #执行读取事务。如果是非事务读取,那么他会在txn.Range函数里获取锁,
#然后直接调用txn.executeRange执行读取
mvcc.metricsTxnWrite.Range
mvcc.storeTxnCommon.Range
mvcc.storeTxnCommon.rangeKeys #读取key
if rev <= 0 { #请求中的rev=0表示要读取最新的版本,所以把当前etcd集群的revision赋给rev
#然后读取的时候就是读一个版本小于revision的最新版本
rev = curRev
}
mvcc.treeIndex.Revisions #根据要读取的key获取revision
backend.baseReadTx.UnsafeRange
backend.txReadBuffer.Range #先尝试从readbuff中读。在put一文里我们描述了apply时不但会把结果写到batchTx,
#还会把结果转存到readBuff,即readBuff中也包含了最新的数据。
backend.unsafeRange #去bbolt读。缓存中没读到足够的数据就会执行这里
mvcc.metricsTxnWrite.End #结束事务,释放锁
s.mu.RLock() #释放锁整个store的锁
else:
etcdserver.EtcdServer.raftRequest #如果包含写事务,那么写之前就需要走一遍raft流程同步一下日志,因为写事务会改变集群状态,
#个raft流程都是通用的,因为请求都会封装到日志的data字段,而raft流程中不会用到data字段
#raft流程就是从自己给自己发一个propose消息开始,所以这里就不再赘述了
......走一遍raft流程同步和commited日志,略,直接来到apply 线程......
another thread 1{
etcdserver.EtcdServer.run
for
select:
case ap <- applyc
......apply流程同put,直到dispatch才不一样,这里直接转到dispatch......
apply.uberApplier.dispatch #不管什么日志,apply时都会走到这里,然后分派,根据请求类型来调用不同的函数
case r.Txn != nil: #事务对应的请求类型为Txn
apply.authApplierV3.Txn #鉴权
apply.quotaApplierV3.Txn #检查份额
apply.applierV3backend.Txn
txn.Txn #到这里就和只读事务一样的流程了。之所以这样是因为只读事务不会改变集群状态,
#所以收到一个读事务请求时可以不经过raft流程直接去读数据库
#(个人疑惑的就是为什么事务读不需要readIndex)
#这里面会有个检测操作,如果是只读事务,但是有写操作,那么就会panic,
#如果是写事务,那么就必须先走一遍raft流程再来到这里
#也就是说txn.Txn这个函数是通用的,可以处理读事务和写事务,收到读事务可以直接走到这个函数,
#但是写事务必须先走一遍raft流程才能来走到这里
#因为函数是通用的,但是读写事务会执行不同的分支(里面有if-else),这里就主要记录写事务的相关流程
#txn.Txn函数流程就三步:
#1:创建事务对象(创建读事务的过程中会加s.mu.RLock,写事务则会加s.mu.RLock和batchTx.LockInsideApply)
#2:调用txn.txn函数完成事务。在此过程中访问treeIndex时会单独加锁解锁
#3:事务已经完成,解锁
isWrite := !txn.IsTxnReadonly(rt) #标记当前事务是不是只读事务,后续会根据这个标记来执行不同的分值
mode = mvcc.SharedBufReadTxMode #使用事务共享存储模式
mvcc.store.Read #1:创建一个读事务对象和加锁
s.mu.RLock() #加读锁,因为compare时需要读取数据(mvcc中put/delete也是对数据库加读锁)
#(底层会并发访问,比如compact线程会并发修改数据,所以读取要加锁)
backend.backend.ReadTx #返回一个已有的读事务对象
backend.readTx.RLock #因为SharedBufReadTxMode模式下返回的是一个共享的readTx,
#同一个backend(即同一个数据库)上都是用这个readTx来保存正在进行的所有读事务
#所以要手动对这个readTx加读锁,如果是ConcurrentReadTxMode模式,
#那么在创建事务的时候就会给backend.readTx加RLock
#所以ConcurrentReadTxMode模式下不需要我们手动加锁
#backend.commit就是batchTxbuffered.commit,最终调用batchTx.commit
#而batch.commit在提交前会调用backend.readTx.Lock,加写锁
#也就是说etcd在提交数据到bbolt之前会等待所有的读事务都完成
mvcc.newMetricsTxnRead #把readTx封装到一个metricsTxnRead对象中
txnPath:=txn.compareToPath #!!检测是否冲突:通过比较版本号实现
#compareToPath返回值有两种,true或false,
#如果是true,那么就执行req.Success路径
#如果是false,则执行req.failure路径
#STM事务的核心就是if(compare)then (do success)else(do failure)
#就是compare可能冲突(failure)或者没有冲突(success)
#根据对应的结果来执行对应的分支即txnpath
#!!!STM客户端api源码中只有Then分支(即Success),没有else分支,源码如下:
#s.client.Txn(s.ctx).If(s.conflicts()).Then(s.wset.puts()).Commit()
#笔记:不管客户端代码怎么样,最终客户端都是通过if-then-else来调用grpc
txn.applyCompares #内部有一个循环遍历所有的compare,一个compare表是一个比较器
#一个比较器包括两部分:
#(比较的字段(createRevisionon/modiRevision)、比较关系(大于小于等于))
txn.applyCompare #应用一个比较器。即对本次事务所访问的所有key都应用一次该比较器,
#如果有一个key返回失败则该比较器返回失败则该事务也失败
#客户端传过来的请求中包含wset(写事务用到的key和revision)
#和rset(读事务用到的key和key此刻对应的revision)
#compare就是读一下数据库,看数据库里key的revision和传过来的key的revision是否相同
#如果相同说明没有冲突,就执行success分支,即then分支对应的代码
#如果有冲突,就执行failure分支,即else分支对应的代码。
mvcc.metricsTxnWrite.Range #获取本次访问的key以及他们的revision。
#因为不同的比较器有不同的range终止条件,所以不同比较器获取的key不同,
#所以每次都需要重新获取所有的key
mvcc.storeTxnCommon.Range
mvcc.storeTxnCommon.rangeKeys
mvcc.TreeIndex.Revisions #获取key最新的版本号即revision,这个最新是指最靠近事务所到来时系统版本号v的一个版本
ti.RLock #给treeIndex上读锁,也就是说数据库的锁和treeIndex的锁是分开的
#事务开始以后一律给数据库加读锁,因为read/put/delete都不会修改旧数据,只会增加数据
#s.mu这把锁只是用来锁住旧数据,并不会阻止新数据的添加,
#虽然底层bbolt内有一个数据结构会同时存储新数据和旧数据
#但是如何安全的添加新数据到底层的数据结构,这是bbolt数据库的事情,在etcd无关
#旧数据和新数据是分开的,无需加锁
#(公用的treeIndex在修改时会单独加锁,所以读写事务相当于不加锁)
mvcc.TreeIndex.unsafeGet #unsafe的意思是这个函数内部没有加锁,所以在调用此函数时必须已经获得锁
mvcc.keyIndex.get #获取key对应的createRevision/modifieRevision/version
mvcc.keyIndex.findGeneration #当事务到达时系统版本号为v,此函数就是找到key x 的revision(即版本号)
#小于等于事务版本号x的第一个版本所在的generation
mvcc.generation.walk #从该generation中获取最新的版本号,
#这个最新是指最靠近事务所到来时系统版本号v的一个版本
ti.RULock #给treeIndex解锁
backend.baseReadTx.UnsafeRange #先从treeIndex中获取key对应的revision,然后用这个做key去readbuff读
#从数据库获取key和value,数据库里key=revision,我们前面已经获取了revision
#因为不知道compare要比较什么,所以把key,value都返回
txn.compareKV #根据cmpare比较器中指定的字段和指定的比较关系来判断是否发生了冲突
#没看懂ckv.Version和rev,为什么rev是巨大的值
txnPath = append(txnPath, compareToPath(rv, tv.RequestTxn)...)
#!compareToPath执行完本事务的比较后如果有子事务则执行子事务的compareToPath
mvcc.storeTxnRead.End #compare已经完成,可以释放数据库的读锁了,
#这个读锁是读已有数据,所以需要加个读锁,防止修改
#!!!!只要compare成功,那么commited的时候就必定不会发生冲突,
#因为compare只会读取历史数据,并且事务x-1一定在事务x之前完成
#如果事务x-1和事务x冲突了,那么事务x-1会成功,而事务x会因为冲突而放弃,
#因为事务x-1先运行,也就是冲突的两个事务,id小的事务可以commite成功,
#id大的事务会失败。所以事务x compare成功了,那么他必定可以成功commite,
#因为首先compare成功说明事务x与x之前的所有事务都不冲突,其次,如果事务x和他之后的事务x+1冲突,
#那么也会让事务x成功而事务x+1失败,因此一旦compare成功,那么事务x就必定可以成功commite
#所以compare和write可以是两个分开的阶段,代码里也是分开加锁的
s.mu.RULock() #读事务完成,释放读锁
mvcc.watchableStore.Write #前面需要compare,所以创建的是读事务,compare成功了,需要写了,所以这里创建写事务对象
mvcc.store.Write
s.mu.RLock() #加读锁,只有compact和snapshot时才会加写锁
#因为是mvcc,只有一个compact和snapshot操作会修改旧的数据,而delete/put等都是新增数据
#所以read/put/delete都只需加一个读锁来防止compact线程修改数据就行了
backend.batchTx.LockInsideApply #这是给txnbuffer加锁,上面的mu.RLock()是给数据库,
#也就是说同一时刻只会有一个事务在apply,其他的都会被阻塞
#现在有个疑问:read或read事务都会访问treeIndex,这
#按理说冲突了,所以应该有个地方互斥,还不知道????
#读取操作好像会先从txnbuffer读取,然后才去数据库读取,
#这个地方应该会有互斥操作,明天再来看,今天下班了
#20240429 22:59 还有1分钟下班
#20240430 9:33 已解决,treeIndex会单独加锁
txn.txn #2:compare成功后,开始执行事务
txn.executeTxn #执行事务
case *pb.RequestOp_RequestPut: #请求类型有:read/put/delete/txn,其中txn表示子事务
txn.put #走到这里后面的流程就是put的流程了,
#因为我们事务里是一条put语句,所以会走到这个put,
#如果是delete,那么就会走case delete了
......后面就是put流程,略.....
mvcc.metricsTxnWrite.End #3:事务已经完成,释放batchTx和s.mu这两把锁
mvcc.watchableStoreTxnWrite.End
mvcc.metricsTxnWrite.End
mvcc.batchTxBuffered.Unlock #释放batchtxbuffer的锁,对应前面LockInsideApply
backend.batchTx.Unlock
mvcc.storeTxnWrite.End
s.mu.RULock #释放store上的读锁
}
相关文章链接:
STM客户端api相关文章
https://juejin.cn/post/7134326187064557575
https://juejin.cn/post/7134326187064557575